對于容許數據副本不一致的協議， 我們很難用一個單一的維度來定義或者歸類這些協議，對于這些協議來說荤西，更關鍵的問題在于他們提供的一致性保證，抽象和API是不是對用戶有用嗅钻，盡管這些協議允許副本有某種程度的不一致皂冰，但是往往某些業(yè)務是可以容忍的。

那么养篓，為什么弱一致性系統還沒有一天下呢秃流？

實際上是因為分布式系統主要是處理‘分布’帶來的兩個后果：

1.信息是以光速傳播的，（意味著一定會有一些延遲）

2.互相獨立的組件或節(jié)點會獨立的發(fā)生失敗

信息傳播速度有限說明分布式系統中每個節(jié)點的對外界的感知都是獨一無二的柳弄，在單個節(jié)點上計算很簡單舶胀，因為所有事情都會按照一個可預測的全局全序關系發(fā)生概说。在分布式系統上的計算很困難，因為沒有一個全局的全序序列嚣伐。

顯然在分布式系統中實現順序代價是很高的糖赔，特別是對于大型的互聯網應用，這種應用往往必須保持時刻可用轩端。強一致性往往不是分布式系統的特點放典， 強一致性系統的行為就像一個單獨的系統，這種系統在網絡分割的情況下往往會不可用基茵。

更進一步說奋构，強一致性對于每個操作而言，往往需要和系統中的多數節(jié)點進行通信拱层，而且往往不只一次（一個來回）弥臼，而是至少兩次（例如2PC）,這對于地理上分布的，但是又要提供足夠好性能的系統來說是很困難的根灯。

也許我們想要的是一個并不需要代價很高的協同径缅，但是依然可以返回有用的響應給客戶的系統。我們放棄數據唯一真實的條件烙肺，轉而允許不同的數據副本之間有沖突,并通過某些手段來解決這些數據沖突纳猪，同時保證系統的效率和網絡容錯性。最終一致性表達了這樣的理念：不同的節(jié)點之間的狀態(tài)和數據可能會在某一時段不一致茬高，但是最終他們會就某個值達成共識兆旬。

提供最終一致性的系統往往有兩種不同的設計理念：

1. 概率性最終一致：這種系統能檢測到互相沖突的寫操作，但是不能保證最終的結果和順序執(zhí)行寫操作序列的結果保持一致怎栽。也就是說，老的寫操作的值可能會覆蓋較新的寫操作的值宿饱。在網絡分割發(fā)生的時候可能會有些異常結果產生熏瞄。

最近這些年最有影響的提供單一數據正確性的系統是Amazon的Dynamo, 該系統就采用了上述理念。

2. 絕對最終一致谬以，這種系統保證系統的值和順序執(zhí)行的結果一致强饮。也就是說，這種系統不會產生任何異常結果为黎；你可以自由的增加某個服務的副本邮丰，這些副本之間可以以任何形式通信，他們獲得數據更新的順序可以是任意的铭乾，只要他們能夠最終獲得相同的信息他們就能對最終結果達成一致剪廉。

CRDT(復制收斂的數據類型） 是在有網絡延遲，分割炕檩，或者消息亂序的情況下斗蒋，仍然能保證數據收斂的數據類型。這些數據類型可以從理論上證明是收斂的，但是能夠支持理論的實現很有限泉沾。

另一種相似的理論叫做CALM,基于邏輯單一性的一致性:如果我們能夠證明某個系統從邏輯上說是單調一致的捞蚂，那么在沒有協同（通信）的情況下，系統任然是正確的跷究。

協調系統執(zhí)行順序

如果一個系統不支持絕對數據一致性姓迅，那么它的行為會是什么樣的呢，我們來看幾個例子：

一個顯然的特點是數據副本之間的不一致俊马，這意味著系統沒有嚴格定義的通信范式队贱，各個數據副本可以互相隔離，而且同時也能夠單獨的接受寫操作潭袱。

假設有三個數據副本柱嫌，每個副本之間現在互相是隔離的（網路上分割），比如三個副本在三個不同的數據中心屯换，他們之間網絡不通编丘。三個數據都是可用的，可以接受讀寫操作彤悔。

[Clients]? - > [A]

--- Partition ---

[Clients]? - > [B]

--- Partition ---

[Clients]? - > [C]

一段時間以后嘉抓，網絡恢復了，每個副本之間開始交換數據晕窑，他們都收到不同client端的update操作抑片，所以需要進行沖突合并，我們希望所有的數據副本最終能一致杨赤，

[A] \

--> [merge]

[B] /? ? |

|

[C] ----[merge]---> result

另一種看待弱一致性的方式是敞斋，假設有一組client向兩個數據副本發(fā)送消息，因為副本之間沒有同步數據的協議疾牲，那么消息可能會議完全不同的順序到達兩個副本：

[Clients]? --> [A]? 1, 2, 3

[Clients]? --> [B]? 2, 3, 1

這就是為什么我們需要數據同步的協議植捎，例如我們需要拼接一個字符串，分別有如下三個消息;

1: { operation: concat('Hello ') }

2: { operation: concat('World') }

3: { operation: concat('!') }

沒有數據同步的情況下阳柔，A可能產生"Hello World!",但是B會產生"World!Hello"

A: concat(concat(concat('', 'Hello '), 'World'), '!') = 'Hello World!'

B: concat(concat(concat('', 'World'), '!'), 'Hello ') = 'World!Hello '

這當然是不正確的焰枢，我們希望所有副本之間的最終數據保持一致。 有了這兩個例子之后舌剂，我們來看一下Dynamo济锄，我們可以有一個基線，然后討論一下構建弱一致

系統的幾種方式霍转，例如CRDT和CALM.

Amazon的Dynamo

Dynamo是最有名的弱一致的高可用系統荐绝。他的原理是很多其他系統基礎，包括Linkedin的Voldermort,Cassandra和Riak.

Dynamo是一個最終一致谴忧，高可用的kv store. kv store像一個大的哈希表很泊，client可以通過set(key,value)保存數據角虫，并通過get方法獲取數據。

一個Dynamo 集群包含N個對等節(jié)點委造，每個節(jié)點負責存儲一組key和對應的value.

Dynamo優(yōu)先保證可用性戳鹅，（犧牲一致性），他并不保證單一數據一致昏兆。 數據副本之間可能會不一致枫虏，當讀某個數據的時候，在返回給客戶端之前有一個步驟會嘗試消除多個副本之間的數據不一致爬虱。

對于Amazon來說隶债，很多場景下，系統可用性比絕對一致性更重要跑筝，因為系統不工作可能會導致業(yè)務流失或者信譽受損死讹。 如果某些數據不是特別重要，那么相對傳統的RDMBS,弱一致系統可以提供更好的性能和可用性曲梗。

下面的圖演示了一個寫操作是如何route到一個節(jié)點赞警，并同時又是怎么寫到多個數據副本中的：

[ Client ]

|

( Mapping keys to nodes )

|

V

[ Node A ]

|? ? \

( Synchronous replication task: minimum durability )

|? ? ? ? \

[ Node B]? [ Node C ]

A

|

( Conflict detection; asynchronous replication task:

ensuring that partitioned / recovered nodes recover )

|

V

[ Node D]

現在我們再看一下如何進行沖突檢測和異步數據復制。高可用性的目標要求必須有數據復制虏两，有些復制目標節(jié)點可能會由于網絡分割而暫時不可用愧旦，副本同步任務確保節(jié)點在恢復以后能快速更新到最新狀態(tài)。

一致Hash

無論是讀還是寫定罢，我們首先要做數據路由笤虫，那么一定會有key到某個Node的映射算法。Dynamo里使用一致哈希來做key到節(jié)點的映射祖凫，這個計算由client端完成琼蚯，這種方式是的client不需要進行查詢來獲得目標節(jié)點， 這樣做的好處是hash運算比rpc的成本要低蝙场。

部分仲裁

一旦我們知道key在哪里存儲凌停，我們就要持久化這個值，這是一個同步過過程售滤，需要立即將值寫入多個節(jié)點的原因是保持更高的持久化能力，例如防止剛好在寫操作時某個節(jié)點失敗了台诗。

Dynamo基于一個quroum進行數據復制完箩，但是Dynamo實現的是一個非嚴格的quroum復制。

一個嚴格的quroum系統有如下屬性：任何兩個quroum之間是有交集的拉队。在實際接收一個寫操作之前要求得到多數節(jié)點的確認弊知，這樣能保證對一個數據寫操作的歷史是全局一致的，

因為在兩個多數quroum之間至少有個一個相交的節(jié)點（這個節(jié)點會記錄正確的數據寫操作序列）粱快。Paxos協議基于這個規(guī)則秩彤。

但是部分Quroum就沒有這個特性叔扼，這意味著寫操作不需要多數node參與，那么對同一項數據漫雷，不同的節(jié)點子集可能有不同的數據版本瓜富。對于讀寫操作，用戶可以自己選擇需要多少節(jié)點參與：

1.用戶可以選擇W個節(jié)點參與寫操作

2.用戶可以選擇R個節(jié)點參與讀操作

一般建議R+W>N, (N為一個數據的所有副本個數）降盹，這意味著read和write至少會hit一個公共的節(jié)點与柑，這樣范圍過期的值得可能會變小。一般的配置都是N=3,那么用戶

可以選擇：

R = 1, W = 3;

R = 2, W = 2 or

R = 3, W = 1

假如我們有如下配置：

1. R=1蓄坏，W=N价捧， :讀的速度快，寫的速度慢

2. R=N,W=1涡戳， :寫的速度快结蟋，讀的速度慢

3. R=N/2 W=N/2+1 二者兼顧

N很少會大于3,因為將數據冗余太多副本會帶來很高的成本。下面是其他一些產品的R/W配置：

Riak N=3,R=2,W=2

Voldemort N=2 or 3? R=w=1

Cassandra N=3, R=1,W=1

另一個細節(jié)是當發(fā)出讀寫請求是渔彰，是不是所有N個節(jié)點都需要響應嵌屎，或者說只有一個部分節(jié)點需要響應，

如果給所有數據副本節(jié)點發(fā)請求胳岂，那么響應更快编整，因為他只需要等待最快的R/W個節(jié)點返回即可。如果是

僅僅發(fā)送給最小個數的R/W個節(jié)點那么需要等待所有節(jié)點的返回乳丰，但是網絡發(fā)送的消息數量會小一些掌测。

如果讀寫的Quroum發(fā)生重疊，也就是R+W>N的時候产园，這種情況下的一致性是否就是強一致性汞斧？

答案是否定的。 如果一個系統的R+W>N,那么會檢測到副本之間的數據沖突什燕，因為任何讀寫都至少會在一個節(jié)點上都發(fā)生:

1? ? 2? N/2+1? ? N/2+2? ? N

[...] [R]? [R + W]? [W]? ? [...]

這樣就保證了一個寫操作的結果會被后面的讀操作獲取粘勒。但是，這個結論僅僅在N個節(jié)點不發(fā)生變化的情況下是正確的屎即。所以Dynamo并不能算是強一致因為他的集群節(jié)點可能會動態(tài)變化庙睡。（在某些節(jié)點失效時）

Dynamo的設計目標是總是保持可寫。如果負責某些key結合的服務器宕機了技俐，那么它加入一個新的server到集群中來處理請求乘陪，這就意味著quorum數量的server可能不會有交集，甚至R=W=N 這樣的配置都不行雕擂，因為當quroum數量為N時啡邑，所有N臺server可能都會因為failure發(fā)生改變。當網絡分割發(fā)生時井赌，如果有足夠數量的server不能聯網谤逼，Dynamo就會自動增加一些server節(jié)點贵扰，這些節(jié)點沒有數據但是可以訪問。

另外Dynamo處理網絡分割的方式和強一致系統的方式也不一樣:在兩個分割區(qū)都可以進行寫操作流部，這以為這至少在一個時間段內系統內的同一數據可能有不同的值戚绕，所以R+W>N不等于強一致，這里的強一致僅僅是一個概率的概念贵涵。

沖突檢測和寫修復

容許數據副本有沖突的系統必須有一套最終能消除沖突的方法列肢，一種方式在讀數據的時候消除沖突。一般來說這種方法是記錄數據改動的因果序列宾茂，客戶端需要有數據的元數據瓷马，然后根據元數據來消除沖突，在寫數據的時候系統要返回數據的元數據（因果序列）

之前已經指出了一個實現方法跨晴，就是使用向量時鐘欧聘，一開始Dynamo就是使用向量時鐘來消除沖突的。但是也還有其他的方法端盆，有些系統基于元數據實現了其他的方法：

1.沒有元數據的方法怀骤。系統并不跟蹤記錄元數據，就直接返回得到的數值焕妙，這種系統對并發(fā)寫無能為力蒋伦，僅僅就是簡單的最后寫勝出，(Last-WRITE-WIN)焚鹊，如果有兩個并發(fā)的寫痕届，那么最慢的值會是最終的值。

2.使用時間戳末患。系統保留有較高時間戳值得寫操作的結果研叫。但是，如果時間不同步可能會發(fā)生意想不到的情況璧针，可能叫老的寫操作發(fā)生在時鐘有問題的節(jié)點上嚷炉，那么它可能最終會被保留。Cassandra使用了這種方式而不是向量時鐘探橱。

3.版本號申屹。版本號避免了時間不同步的問題，但是表達因果順序的最簡單的方式任然是向量時鐘隧膏。

4.向量時鐘独柑。向量時鐘可以檢測到沖突的寫操作，然后進行讀修復私植，但有時候必須讓客戶端進行選擇，如果有數據沖突车酣，但是又沒有元數據為依據來解決沖突曲稼，那么只能將數據丟棄索绪。

客戶端會和R個節(jié)點通信進行讀取，它拿到所有的響應贫悄，然后根據向量時鐘丟棄老的數據瑞驱，如果最后只有一個數據和向量時鐘，那么就返回這個數據窄坦，如果有多個無法決定先后的向量時鐘和數值唤反，那么久返回所有的數值。這種情況下客戶端需要根據具體的case選擇一個值鸭津。

另外實際應用的向量時鐘實現不能讓時鐘無限制的增加彤侍，需要有一個垃圾回收過期時鐘的方式以避免消耗過多的存儲。

數據副本同步 Gossip和Merkle Tree

Dynamo系統既然允許節(jié)點失效或者網絡分割逆趋，那么它會有一個機制來處理重新加入集群的失效節(jié)點盏阶。當失效節(jié)點重新恢復后，需要進行副本復制闻书，并定期執(zhí)行副本同步名斟。

Gossip是一個副本同步的方法，（概率性的）魄眉，節(jié)點之間的通信方式是隨機的砰盐，每隔t秒，每隔節(jié)點隨機選擇另外一個節(jié)點進行同步坑律，實際上在別的問題上比如quroum寫上面也可以用這種方式岩梳。

Gossip是擴展的，沒有單點失效脾歇，但是不能夠絕對保證數據同步的正確性蒋腮。為了保證數據同步的效率，Dynamo使用了merkle tree的技術藕各，他的思想是一個數據存儲單元可以整體進行hash池摧，或者每一半個key進行hash她渴，等等荸型。

總結，目前為止討論了Dynamo的主要設計要點：

1.一致哈希來決定key的存儲路由

2.讀寫是部分quorum

3.通過向量時鐘做沖突檢測和讀修復

4.數據副本同步用Gossip協議