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

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

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

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

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

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

Dynamo設(shè)計中的學(xué)習(xí)點

1．  Consistent hashing算法支持分布式多節(jié)點

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

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

Consistent hashing的優(yōu)點：（其實主要作用是在虛擬節(jié)點以及環(huán)狀負責(zé)制上）

a．  支持不同能力節(jié)點的權(quán)重設(shè)置。由于采用了虛擬節(jié)點，通過虛擬節(jié)點和實體節(jié)點多對一的配置可以實現(xiàn)處理能力權(quán)重配置。

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

c．  同時對于壓力分攤也有幫助。這個優(yōu)勢還是沿用B來說，新增、刪除或者失效一個實體節(jié)點，它可能對應(yīng)的是多個虛擬節(jié)點，此時數(shù)據(jù)壓力會分攤到環(huán)狀其他的多個節(jié)點，新增也是同樣，這樣可以降低壓力分攤的風(fēng)險。

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

2．  Vector clock管理數(shù)據(jù)多版本

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

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

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

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

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

3．  load balance的幾種模式。

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

b.       服務(wù)端硬件實現(xiàn)load balance。

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

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

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

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

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

           D方式是解決服務(wù)端簡單的分發(fā)而導(dǎo)致處理的不均衡性，其實這種模式也可以改進客戶端的算法。因為通過Hash算法未必能夠?qū)毫Ψ謹偩鶆?，就好比一些處?需要耗時比較久一些處理耗時比較少，系統(tǒng)對于key的映射不均衡等等問題，不過在Dynamo中描述的并不很明確，其中的算法還是要根據(jù)實際情況來做的。

4．  三個參數(shù)平衡可用性和容錯性。

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

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

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

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

5．  異步處理容錯數(shù)據(jù)復(fù)制

當一個數(shù)據(jù)存儲節(jié)點出現(xiàn)問題以后，數(shù)據(jù)存儲交由給下一個節(jié)點處理，此時除了在下一個節(jié)點存儲數(shù)據(jù)內(nèi)容以外，還會記錄下原本數(shù)據(jù)所應(yīng)該存儲的節(jié)點以及當前存儲的節(jié)點和數(shù)據(jù)內(nèi)容，可以放在后臺的數(shù)據(jù)庫或者存儲中，后臺定時處理這些記錄，將數(shù)據(jù)遷移并且刪除復(fù)制任務(wù)。

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

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

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

         以上的都是自己看Dynamo設(shè)計中覺得對自己比較有幫助的內(nèi)容，其中一些思想可能會和原有設(shè)計有些出入，各位僅作參考。