iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 4
1
Software Development

分散式系統 - 在分散的世界中保持一致系列 第 4

Day 4 - DynamoDB設計裡Consistency與Availability的爭奪 - Quorum System(上)

先看一個例子

昨天的分散式儲存系統,要求寫入只能寫入primary server,讀取則可以從replica servers讀取。因此問題:

  1. 在於要多久的時間才能從primary server把更新的結果傳遞同步到replica servers上
  2. 以及當Client從系統讀取資料時(可能從replica server,client不知道) 對這個資料是否是最新的結果有多強的保證。

但是系統如果只允許寫入是寫到primary server,為免效能與Availability也太差了。不如我們取消primary server的設計,寫入可以也要同時寫到所有的replicas身上,你的set(k,v)一次傳給所有的replica servers。

這種 Leaderless Replication 就是隨著 DynamoDB論文 的提出而開始興起,也啟發了更多在CAP選擇AP的分散式系統,當雲端服務商設計分散式資料庫系統,為了Availability而做Data Replication時,他們怎麼在Consistency和Availability做取捨呢?

採用 Leaderless Replication 另一個問題浮現就會出現,
假設今天有兩個Client C1, C2同時分別對系統裡所有replicas R1, R2, R3做寫入

  1. C1 寫入 ("system", 1)
  2. C2 寫入 ("system", 2)

但是因為網路傳輸速度有別,因此收到操作的順序不一樣

  1. R1 ("system", 1)->("system", 2)
  2. R2 ("system", 2)->("system", 1)
  3. R3 ("system", 1)->("system", 2)

此時
C1從replica R1讀取資料 get("system") = 2
C2從replica R2讀取資料 get("system") = 1

結果居然不一致了,究竟怎麼在這個情境下處理多個client「同時寫入」呢? 其中一個答案就是 Quorum System

Quorum System

問題

將上面的問題 formalize 成

Q: 在有N個replica的系統裡,我們如何保證 Serializability。 也就是我們希望找出讀寫請求的 total order。

方法

Lock

最間單的方法就是使用Lock,使得每一次的寫入都一定要先將取得N個replica得Lock,在寫入資料,最後釋放Lock。

因為讀寫被保證每一次一定會等所有的Replicas都同步操作後才算結束,沒有取得Lock的就必須等待,使得讀寫操作被serialized了,因此讀取時不管從哪一個replica都會讀到一致的資料。

取得多少replicas的Lock才被允許讀寫?

我們說

  • 對於寫入操作,一個client必須取得W個replicas的Lock才被允許寫入
  • 對於讀的操作,一個client必須取得R個replicas的Lock才被允許寫入

如果我們想在這樣的model底下達成Strong Consistency

  1. set()/get()操作是total order
  2. get(k)一定返回最新的set(k,v)的值

這個W/R應該要怎麼設計呢?
先說結論

  1. W+R > N 就可以避免concurrent 的發生
  2. W+W > N 就可以避免concurrent 的發生

以下直接用圖來解釋

W+W > N

首先N=5,因此只要取得3個以上的replicas的lock搭配timestamp即可進行寫入

  1. c1 先取得R1,R2,R3的locks與k目前的timestamp,更新timestamp成t1後set(k, v1)。

  1. 接著c2因為沒有辦法搶到3個lock,等了一回合,接著取得R3,R4,R5的locks,更新timestamp成t2後set(k, v2)

可以看到在W+W>N的情況下,已經保證一次只能有一個client可以寫入,而且下一個client寫入時一定會複寫掉至少一個replica。

W+R > N

接著我們看在這種寫入條件下搭配W+R>N的讀限制,我們的讀取一定可以讀到最新的值嗎?

  1. (左圖) 如果 W + R <= N,剛剛已經規定W>=3,因此R<=2,規定R=2
    會發現他有可能讀到R1,R2的值,但是這兩個剛剛好沒有被覆寫掉,上面的值是舊的timestamp也是t1而非t2。

  2. (右圖) 如果 W + R > N,R >= 3,規定R=3,會發現他一樣至少會讀到一個被複寫過的replica R3,而透過timestamp t2 來找到最新的值v2。

結論

因此在分散式儲存系統中,我們也不一定規定寫入只能寫進primary server再讓primary server來同步值給replica server。我們也可以透過Quorum System理論的Lock和W/R數量限制來取消掉primary server的角色,一樣可以做到Strong Consistency。

BTW,這些理論應用在大家使用的服務本身裡面,而不是後來兜服務時的application level上。
比方說你使用 "一個" DynamoDB,Amazon內部的datacenter可能把你的DynamoDB做好幾個備份到地球其他角落的datacenter,讓你不管從哪一個地方讀自己的DB都有一個local replica加速。
這時他就要考量設計這種備份的Consistency,也因此他的Strong Consistency read只限定同一Region,這關乎他系統在幫你解決DB備份問題的Consistency實作的限制。又或者當它東京機房失效,他要透過備份讓你仍然保有Availability或是幫你復原資料就是要靠這些Replication機制和Consistency。

但是從你的角度來看他就是 "一個" DB,你只管讀寫就好。

預告

雖然Quorum System可以使得系統達到Strong Consistency,但是可以看到這其中犧牲了Availability,為了讀取最新的資料,就必須要讀取超過半數的replicas才行。
因此DynamoDB的論文裡就提到他們採用Sloppy Quorum來提高Availability,且可以在Network Partition時繼續運作!
明天就來看看Sloppy Quorum是什麼吧,期望以後看這些系統論文時,可以懂裡面用到的理論與術語。


上一篇
Day 3 - 從Replica Server讀到的資料一定正確嗎? Data Replication and Consistency
下一篇
Day 5 - DynamoDB設計裡Consistency與Availability的爭奪 - Quorum System(下)
系列文
分散式系統 - 在分散的世界中保持一致30

尚未有邦友留言

立即登入留言