放翁（文初）的一畝三分地

Author：文初

Email：wenchu.cenwc@alibaba-inc.com

Blog：http://blog.csdn.net/cenwenchu79

         什么是Dynamo? Dynamo是Amazon的高效Key-Value存儲基礎組件（類似于現在被廣泛應用的Memcached Cache），當前被用于Amazon很多系統中作為狀態管理組件。在2007年年底Amazon的CTO就寫了一篇介紹Dynamo設計的文章，今年年底又在日志中提出了對于那篇文章的一個補充：“Eventual consistency”。這也讓我再次仔細的去回顧了一下Dynamo的設計思想，其中很多設計技巧是當前分布式系統設計也可以借鑒的。

         在說幾個設計技巧以前先說幾個分布式設計的需求和概念。

1．  Eventual consistency。這個概念在阿里系中支付寶架構設計貫徹的最徹底，記得看魯肅的關于支付寶事務處理中提出的軟事務的概念其實就是Eventual consistency的一種表現。對于系統設計來說，系統中的事件往往都會相互關聯，孤立的事件在當前的互聯網行業中變得微乎其微。事件與事件之間存在著一系列的約束和因果關聯，就需要靠事務來保證。事務的特質就是ACID，而ACID在當前分布式系統設計的模式下常常會和可用性以及高效性產生沖突。ACID中其他三者都很好理解，而C “一致性”往往是初學者比較難以理解的一個特質。用銀行存款操作的比喻就較為容易理解，銀行帳戶在操作前有100元，存入了50元以后，就有了150元，操作前和操作后保持了銀行帳戶的一致性，存入50元以后帳戶僅僅增加了50元，總額沒有超過150或者少于150，在常規看來是在正常不過的了，但是試想，如果有兩個操作在一個瞬間作操作，一個需要給賬戶增加50元，一個要給賬戶增加30元，前一個操作是基于100元的基礎增加，后一個也是基于100元增加，然后后一個操作晚于前一個操作提交，那么最后帳號里面就只有130，這就是可以認為銀行帳號在兩次操作以后出現了狀態不一致性。一致性就好比自然界平衡，降水、蒸發維持生態平常。Eventual consistency其實是對一致性的一種延展，過程中允許部分不一致，但是在事務處理結束或者有限的時間內保持事務的一致性。一句話簡單概括就是：“過程松，結果緊，最終結果必須保持一致性”。

2．   可用性，容錯性，高效性。這三個非功能性需求在當前架構設計中已經成為最基本的設計要求，但三者常常在設計中又存在矛盾。容錯性要高就需要作更多額外的工作，而更多的額外工作必將降低高效的特點，同時額外工作也會間接增加系統復雜度進而影響可用性。在設計中協調者三者的關系，沒有什么準則可以遵循，只有根據實際的系統狀況來判斷如何達到最好的效果，在后面的Dynamo的三個參數配置設計就可以看到通過配置如何平衡三者關系并且將組件應用到上層系統中。

3．  分布式設計中兩類一致性問題：單點數據讀寫一致性問題和分布式數據讀寫一致性問題。前者通常通過數據存儲的服務端控制即可（類似于DB的控制），后者通常通過消息傳播的方式來實現（類似于JGroup在多播通道傳播同步消息）。

4．  沖突解決。這個我想大部分開發者每天都會接觸到，代碼控制（SVN）就是版本控制發現沖突的具體體現。沖突檢測通常最簡單采用last write的方式，也就好比數據庫的解決方式，誰最后修改就以誰的為準。其他沖突檢測和版本合并就十分復雜，有些不得不靠人工干預。這點也是在數據一致性通過多版本方式來解決的時候遇到的問題。

Dynamo設計中的學習點

1．  Consistent hashing算法支持分布式多節點

簡單hash算法：N為node數量。處理主鍵為key的節點為：key.hashValue() mod N。

Consistent hashing算法：環狀結構。虛擬節點來替換實體節點被分配到環狀某一位置上（根據處理能力不同可以將一個實體節點映射到多個虛擬節點上）。主鍵為key的節點position = hash(key),在環上按照順時針查找value大于position的第一個虛擬節點，由它對應的實體節點處理。下圖中k就優先由虛擬節點 B來處理。

Consistent hashing的優點：（其實主要作用是在虛擬節點以及環狀負責制上）

a．  支持不同能力節點的權重設置。由于采用了虛擬節點，通過虛擬節點和實體節點多對一的配置可以實現處理能力權重配置。

b．  新增或者刪除節點動態配置成為可能，比較上一種簡單算法，由于實體節點的數目直接影響到了hash算法，因此導致新增或者刪除節點影響全局數據的重新映射。而Consistent hashing算法不受節點數目影響，它的區間負責以及多節點冗余處理降低動態增減節點的內容失效影響。在一些情況下需要不重新啟動而動態的增加或者減少處理節點，因此采用了Consistent hashing的區間負責制，就好比上圖key k的內容落在了A和B的區間內，根據規則由B優先來處理，當B失效的時候也可以由C,D來處理，根據環狀最近可用節點來選擇。如果在B節點和A節點新增一個節點或者刪除B節點，影響的數據處理映射也僅僅是是A和B區間內數據。

c．  同時對于壓力分攤也有幫助。這個優勢還是沿用B來說，新增、刪除或者失效一個實體節點，它可能對應的是多個虛擬節點，此時數據壓力會分攤到環狀其他的多個節點，新增也是同樣，這樣可以降低壓力分攤的風險。

Consistent hashing算法其實也可以采用Tree方式來實現,Memcached的客戶端版本中就有支持采用Tree的。

2．  Vector clock管理數據多版本

為什么會存在數據多版本，其實這個在高并發分布式處理中經常會遇到，同時也是容錯性和高可用性的一種解決方式。兩方面來看，首先在高并發分布式處理過程中，對于單個資源的操作要么采用阻塞方式要么采用多版本方式，前者效率相對較低但是處理簡單，后者效率高但是處理復雜。對于容錯性和高可用性要求高的情況下，多版本也是一種解決手段，就好比Amazon的購物車就要求任何時候都要支持修改，如果某一些處理節點當前不可用，那么就需要支持多個節點的處理以及數據多點的存儲，這樣就出現了不同節點數據的不同版本問題。

Vector clock根據操作者的不同為一個對象創建了多個版本計數器，并且通過多個版本計數器來判斷這些版本是否屬于并行分支還是串行分支，由此來確定是否需要解決沖突。

解決沖突分成兩種方式，一種是客戶端選擇如何解決沖突，一種是服務端解決沖突。前者適用于較為復雜的沖突解決，后者適用于簡單的版本沖突解決。不過不論哪一種方式，在Dynamo的處理中，客戶端和服務端之間對于對象的操作交互過程都會帶有版本歷史信息。

         上圖是描述一個對象D的Vector clock歷史狀況。首先D被Sx節點處理，那么處理以后產生了第一個版本D1([Sx,1])，然后又被Sx處理了，產生了第二個版本D1([Sx,2])，因此需要判斷是否需要版本沖突解決。判斷版本沖突主要是檢查Vector clock中的多個版本與上一個歷史Vector clock的關系，如果歷史的和當前的Vector clock中所有的節點版本都是大于等于的關系，那么就認為兩個版本不沖突，可以忽略前一個版本。就拿D2和D1來看，里面只有一個Sx的版本記錄，對比2大于1，因此就認為可以忽略前一個版本。D3和D4分別是基于D2版本，兩個不同節點處理后的結果，根據上面的沖突檢測可以認為D3和D4版本無法忽略任何一個版本，因此此時對于D對象來說存在兩個版本D3和D4，當Sx從服務端獲取到數據以后做處理，此時就產生了三個版本。至于這三個版本由客戶端Sx來解決還是服務端后期自動通過后臺完成這個就需要根據應用來決定了。

         Vector clock只是提供了一種手段來解決多版本的問題，至于客戶端解決沖突還是服務端解決沖突這個需要根據具體情況來選擇。

3．  load balance的幾種模式。

a.       客戶端實施load balance。采用客戶端包來實現分發算法，同時配置分發節點情況。Memcached Cache客戶端使用的一種基本方式。

b.       服務端硬件實現load balance。

c.       客戶端改進模式。配制節點以及算法都可以采用集中的Master來管理和維護，包括心跳檢測等手段由Master來實現。當然支持Master失效的容錯性策略實施。

d.       服務端模式改進。采用preference list來分離接受和處理任務的節點。

首先采用A模式可以防止B模式在單點的情況下出現的不可用風險，也可以減輕高并發下單點的壓力，提高效率（這點淘寶的同學有和我提到過，他們采用的“軟負載”方式）。但是A模式會增加對于客戶端包的依賴性，對于擴展和升級都會有一定的限制。

           其次B模式是最省心的方式，擴展性也比較好，但是就是在上面提到的單點問題會有所限制。

           C方式是對于A方式的一種改進，我以前的一篇文章中提到過，這樣可以提高A的可擴展性以及可維護性，減小對于客戶端包的依賴，但是增加了系統復雜度，同時Master也是會有單點的問題，不過問題不大（失效的情況下就是退化到了A模式）。

           D方式是解決服務端簡單的分發而導致處理的不均衡性，其實這種模式也可以改進客戶端的算法。因為通過Hash算法未必能夠將壓力分攤均勻，就好比一些處理需要耗時比較久一些處理耗時比較少，系統對于key的映射不均衡等等問題，不過在Dynamo中描述的并不很明確，其中的算法還是要根據實際情況來做的。

4．  三個參數平衡可用性和容錯性。

在Dynamo系統中通過三個參數（N，R，W）來實現可用性和容錯性的平衡。對于數據存儲系統來說，Dynamo的節點采用冗余存儲是保證容錯性的必要手段，N就代表一份數據將會在系統多少個節點存儲。R表示在讀取某一存儲的數據時，最少參與節點數，也就是最少需要有多少個節點返回存儲的信息才算是成功讀取了該數據內容。W表示在存儲某一個數據時，最少參與節點數，也就是最少要有多少個節點表示存儲成功才算是成功存儲了該數據，通常情況下對于N的復制可以阻塞等待也可以后臺異步處理，因此W可以和N不一致。這里的R,W的配置僅僅表示參與數量的配置，但是當環狀節點其中一個失效的時候，會遞推到下一個節點來處理。

很明顯的R,W的數字越大直接會影響系統的性能和可用性，但是R,W越大卻能夠保證容錯性的增強。因此如何配置N,R,W成為平衡容錯性和可用性的一種重要方式。對于一個系統結構中，節點本身穩定性較高的情況下，將R,W配置的較小，提升系統的可用性。對于節點穩定性不可靠的情況下，適當增大R,W配置，提升系統的容錯性，同時也對可用性有一定幫助。

另一方面，從讀寫能力和業務操作讀寫比例修改R,W的配置來優化系統的性能。對于讀操作十分密集寫相對來說較少的情況來說，配置R=1,W=N，則可以實現高讀引擎，系統只要還有一個節點可以讀取數據就可以讀到數據。對于寫比較頻繁的情況來說，那么可以配置R=N,W=1實現高寫引擎，系統只要還有一個節點可以寫入，就可以保證業務寫入的正常，不過讀取數據進行沖突解決會比較復雜一些。

除了配置這三個參數以外，通過讀寫配置本地緩存的方式可以提高系統整體性能以及容錯性。

5．  異步處理容錯數據復制

當一個數據存儲節點出現問題以后，數據存儲交由給下一個節點處理，此時除了在下一個節點存儲數據內容以外，還會記錄下原本數據所應該存儲的節點以及當前存儲的節點和數據內容，可以放在后臺的數據庫或者存儲中，后臺定時處理這些記錄，將數據遷移并且刪除復制任務。

這部分在我優化Memcache客戶端的時候采用的是客戶端集群配置lazy復制的方式，當發現配置成集群的節點中優先處理節點沒有數據就考慮從其他節點獲取，如果存在就異步復制，不過這種方式對于有timestamp的數據就會有問題。

6．  采用merkle tree來交驗節點存儲數據一致性。每一個節點所處理的key range將會被保存在本地節點中，通過tree的方式在組織存儲，通過對比節點之間的tree可以快速高效的判斷出是否有數據不同步需要異步復制和同步。

Merkle tree的具體算法和使用方式可以參看BT交驗改進的文章來學習一下，這片文章寫得很通俗易懂，推薦一下：http://www.cnblogs.com/neoragex2002/archive/2006/04/26/385077.html