先看一個例子

昨天的分散式儲存系統，要求寫入只能寫入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)。

2. 接著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是什麼吧，期望以後看這些系統論文時，可以懂裡面用到的理論與術語。