一、系統(tǒng)概述
1、Amazon平臺(tái)概述      
Amazon平臺(tái)是一個(gè)由數(shù)百服務(wù)組成的面向服務(wù)的架構(gòu)，其秉承高度去中心化、松散耦合、完全分布式的原則，具體架構(gòu)參考下圖。

在這種環(huán)境中，尤其需要一個(gè)始終可用的存儲(chǔ)系統(tǒng)，由此，Dynamo誕生了。

2、Dynamo概述
Dynamo是Amazon提供的一款高可用的分布式Key-Value存儲(chǔ)系統(tǒng)，其滿(mǎn)足可伸縮性、可用性、可靠性。
CAP原理滿(mǎn)足：通過(guò)一致性哈希滿(mǎn)足P，用復(fù)制滿(mǎn)足A，用對(duì)象版本與向量時(shí)鐘滿(mǎn)足C。用犧牲C來(lái)滿(mǎn)足高可用的A，但是最終會(huì)一致。但是，是犧牲C滿(mǎn)足A，還是犧牲A滿(mǎn)足C，可以根據(jù)NWR模型來(lái)調(diào)配，以達(dá)到收益成本平衡。
Dynamo內(nèi)部有3個(gè)層面的概念：
Key-Value：Key唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)對(duì)象，Value標(biāo)識(shí)數(shù)據(jù)對(duì)象實(shí)體，通過(guò)對(duì)Key來(lái)完成對(duì)數(shù)據(jù)對(duì)象的讀寫(xiě)操作。
節(jié)點(diǎn)node：節(jié)點(diǎn)是指一個(gè)物理主機(jī)。在每個(gè)節(jié)點(diǎn)上，會(huì)有3個(gè)必備組件：請(qǐng)求協(xié)調(diào)器（request coordination）、成員與失敗檢測(cè)、本地持久引擎（local persistence engine），這些組件都由Java實(shí)現(xiàn)。本地持久引擎支持不同的存儲(chǔ)引擎，最主要的引擎是Berkeley Database Transactional Data Store（存儲(chǔ)數(shù)百K的對(duì)象更合適），其它還有BDB Java Edtion、MySQL以及一致性?xún)?nèi)存Cache。本地持久化引擎組件是一個(gè)可插拔的持久化組件，應(yīng)用程序可以根據(jù)需要選擇最合適的存儲(chǔ)引擎，比如：如果存儲(chǔ)對(duì)象的通常為數(shù)千字節(jié)則可以選擇BDB，如果是更多尺寸則可以選擇MySQL。生產(chǎn)中，Dynamo通常使用BDB事物數(shù)據(jù)存儲(chǔ)。
實(shí)例instance：從應(yīng)用的角度來(lái)看就是一個(gè)服務(wù)，提供IO功能。每個(gè)實(shí)例由一組節(jié)點(diǎn)組成，這些節(jié)點(diǎn)可能位于不同的IDC，這樣IDC出現(xiàn)問(wèn)題也不會(huì)導(dǎo)致數(shù)據(jù)丟失，這樣會(huì)有更好的容災(zāi)和可靠性。

二、背景條件
1、系統(tǒng)假設(shè)與要求
（1）查詢(xún)模型
基于Key-Value模型，而不是SQL即關(guān)系模型。存儲(chǔ)對(duì)象比較小，通常小于1MB。

（2）ACID屬性
傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)中，用ACID（A原子性、C一致性、I隔離性、D持久性）來(lái)保證事務(wù)，在保證ACID的前提下往往有很差的可用性。Dynamo用弱一致性C來(lái)達(dá)到高可用，不提供數(shù)據(jù)隔離I，只允許單Key更新。

（3）效率
在廉價(jià)的機(jī)器上滿(mǎn)足SLA，通過(guò)配置來(lái)滿(mǎn)足延時(shí)和吞吐量的要求，因此，必須在性能、成本、可用性和持久性保證之間做權(quán)衡。

（4）其它假設(shè)
Dynamo僅在Amazon內(nèi)部使用，因此，認(rèn)為其使用環(huán)境是可信賴(lài)的。

2、服務(wù)水平協(xié)議（SLA）
        所謂服務(wù)水平協(xié)議是指客戶(hù)端和服務(wù)端在某幾個(gè)指標(biāo)上達(dá)成一致的一個(gè)協(xié)議，通常包括客戶(hù)端請(qǐng)求API的速率、服務(wù)端的預(yù)期延時(shí)，比如：在客戶(hù)端每秒500個(gè)請(qǐng)求負(fù)載的高峰時(shí)，99.9%的響應(yīng)時(shí)間為300毫秒。
        一般業(yè)界，對(duì)這種面向性能的SLA采用平均數(shù)（average）、中值（median）和預(yù)期變化（expected variance）。但是這些指標(biāo)只能對(duì)大多數(shù)客戶(hù)端有良好體驗(yàn)，而不是所有。為了解決這個(gè)問(wèn)題，Dynamo采用99.9%百分位來(lái)代替這些指標(biāo)。

3、設(shè)計(jì)考慮（復(fù)制數(shù)據(jù)）
傳統(tǒng)的數(shù)據(jù)復(fù)制算法，在出現(xiàn)故障時(shí)，為了保證數(shù)據(jù)一致性被迫犧牲掉可用性，即：與其不能確定數(shù)據(jù)是否正確，不如讓數(shù)據(jù)一直不可用直到數(shù)據(jù)絕對(duì)正確時(shí)。

但是，一個(gè)高度靈活的系統(tǒng)應(yīng)該能夠讓用戶(hù)知道在何種情況下能到達(dá)哪些屬性，Dynamo就是如此。

對(duì)于故障是常態(tài)的系統(tǒng)來(lái)說(shuō)，采用樂(lè)觀復(fù)制技術(shù)可以提供系統(tǒng)的可用性，但帶來(lái)的問(wèn)題是需要檢測(cè)并協(xié)調(diào)解決沖突，協(xié)調(diào)解決沖突的過(guò)程又包含兩個(gè)問(wèn)題，即：何時(shí)協(xié)調(diào)和由誰(shuí)協(xié)調(diào)。Dynamo的設(shè)計(jì)是數(shù)據(jù)存儲(chǔ)最終一致，即所有更新操作最終到達(dá)所有副本。

（1）何時(shí)協(xié)調(diào)
無(wú)外乎兩種情況：寫(xiě)或者讀時(shí)協(xié)調(diào)沖突。
傳統(tǒng)數(shù)據(jù)存儲(chǔ)在寫(xiě)時(shí)協(xié)調(diào)沖突，即如果給定時(shí)間內(nèi)數(shù)據(jù)不能達(dá)到所要求的所有或大多數(shù)副本數(shù)，則寫(xiě)入可能會(huì)被拒絕。
Amazon認(rèn)為拒絕客戶(hù)的更新操作會(huì)導(dǎo)致糟糕的用戶(hù)體驗(yàn)，典型應(yīng)用是購(gòu)物車(chē)服務(wù)，即使出現(xiàn)故障，客戶(hù)仍然可以向購(gòu)物車(chē)添加或者刪除物品，基于此，Dynamo的目標(biāo)定位為“永遠(yuǎn)可寫(xiě)”（always writable）即數(shù)據(jù)存儲(chǔ)的“寫(xiě)”是高可用的。也就是說(shuō)Dynamo為了確保“寫(xiě)”永遠(yuǎn)不會(huì)被拒絕，那么數(shù)據(jù)存儲(chǔ)在讀時(shí)協(xié)調(diào)沖突。

（2）由誰(shuí)協(xié)調(diào)
無(wú)外乎兩種情況：由數(shù)據(jù)存儲(chǔ)本身或客戶(hù)端應(yīng)用程序來(lái)協(xié)調(diào)。
如果是數(shù)據(jù)存儲(chǔ)本身協(xié)調(diào)，則只能使用簡(jiǎn)單策略來(lái)協(xié)調(diào)沖突的更新操作，比如：“最后一次寫(xiě)入獲勝”（last write wins）。
如果是客戶(hù)端應(yīng)用程序協(xié)調(diào)，則應(yīng)用程序可以根據(jù)業(yè)務(wù)需求來(lái)選擇最適合協(xié)調(diào)沖突的方法。
Dynamo選擇了后者，典型應(yīng)用還是購(gòu)物車(chē)服務(wù)，返回所有數(shù)據(jù)對(duì)象版本，最后選擇合并完沖突的版本。

三、關(guān)鍵技術(shù)
Dynamo作為一類(lèi)分布式系統(tǒng)的典型代表，其眾多關(guān)鍵技術(shù)給其帶來(lái)一系列的優(yōu)勢(shì)，具體參看下表：

1、數(shù)據(jù)分區(qū)
Hash算法：使用MD5對(duì)Key進(jìn)行Hash以產(chǎn)生一個(gè)128位的標(biāo)示符，以此來(lái)確定Key的存儲(chǔ)節(jié)點(diǎn)。

為了達(dá)到增量可伸縮性的目地，Dynamo采用一致性哈希來(lái)完成數(shù)據(jù)分區(qū)。在一致性哈希中，哈希函數(shù)的輸出范圍為一個(gè)圓環(huán)，如圖2所示，系統(tǒng)中每個(gè)節(jié)點(diǎn)映射到環(huán)中某個(gè)位置，而Key也被Hash到環(huán)中某個(gè)位置，Key從其被映射的位置開(kāi)始沿順時(shí)針?lè)较蛘业降谝粋€(gè)位置比其大的節(jié)點(diǎn)作為其存儲(chǔ)節(jié)點(diǎn)，換個(gè)角度說(shuō)，就是每個(gè)系統(tǒng)節(jié)點(diǎn)負(fù)責(zé)從其映射的位置起到逆時(shí)針?lè)较虻牡谝粋€(gè)系統(tǒng)節(jié)點(diǎn)間的區(qū)域。

一致性哈希最大的優(yōu)點(diǎn)在于節(jié)點(diǎn)的擴(kuò)容與縮容，只影響其直接的鄰居節(jié)點(diǎn)，而對(duì)其它節(jié)點(diǎn)沒(méi)有影響。這樣看似很完美了，但是亞馬遜沒(méi)有因此而停止腳本，這是其偉大之處，其實(shí)還存在兩個(gè)問(wèn)題：節(jié)點(diǎn)數(shù)據(jù)分布不均勻和無(wú)視節(jié)點(diǎn)性能的異質(zhì)性。為了解決這兩個(gè)問(wèn)題，Dynamo對(duì)一致性哈希進(jìn)行了改進(jìn)而引入了虛擬節(jié)點(diǎn)，即每個(gè)節(jié)點(diǎn)從邏輯上切分為多個(gè)虛擬節(jié)點(diǎn)，每個(gè)虛擬節(jié)點(diǎn)從邏輯上看像一個(gè)真實(shí)節(jié)點(diǎn)，這樣每個(gè)節(jié)點(diǎn)就被分配到環(huán)上多個(gè)點(diǎn)而不是一個(gè)單點(diǎn)。

2、數(shù)據(jù)復(fù)制
為了實(shí)現(xiàn)高可用，Dynamo將每個(gè)數(shù)據(jù)復(fù)制到N臺(tái)主機(jī)上，其中N是每個(gè)實(shí)例（per-instance）的配置參數(shù)，建議值為3。每個(gè)Key被分配到一個(gè)協(xié)調(diào)器（coordinator）節(jié)點(diǎn)，協(xié)調(diào)器節(jié)點(diǎn)管理其負(fù)責(zé)范圍內(nèi)的復(fù)制數(shù)據(jù)項(xiàng)，其除了在本地存儲(chǔ)其責(zé)任范圍內(nèi)的每個(gè)Key外，還復(fù)制這些Key到環(huán)上順時(shí)針?lè)较虻腘-1個(gè)后繼節(jié)點(diǎn)。這樣，系統(tǒng)中每個(gè)節(jié)點(diǎn)負(fù)責(zé)環(huán)上從其自己位置開(kāi)始到第N個(gè)前驅(qū)節(jié)點(diǎn)間的一段區(qū)域。具體邏輯見(jiàn)圖2，圖中節(jié)點(diǎn)B除了在本地存儲(chǔ)鍵K外，還在節(jié)點(diǎn)C和D處復(fù)制鍵K，這樣節(jié)點(diǎn)D將存儲(chǔ)落在范圍(A, B]、(B, C]和(C, D]上的所有鍵：

對(duì)于一個(gè)特定的鍵都有一個(gè)首選節(jié)點(diǎn)列表，由于虛擬節(jié)點(diǎn)的存在，為了解決節(jié)點(diǎn)故障的問(wèn)題，構(gòu)建首先節(jié)點(diǎn)列表時(shí)會(huì)跳過(guò)環(huán)上某些位置，讓這些節(jié)點(diǎn)分別位于不同的物理節(jié)點(diǎn)上，以保證高可用。

為了保證復(fù)制時(shí)數(shù)據(jù)副本的一致性，Dynamo采用類(lèi)似于Quorum系統(tǒng)的一致性協(xié)議實(shí)現(xiàn)。這里涉及到三個(gè)關(guān)鍵參數(shù)(N, R, W)，其中，N是指數(shù)據(jù)對(duì)象復(fù)制到N臺(tái)主機(jī)，協(xié)調(diào)器負(fù)責(zé)將數(shù)據(jù)復(fù)制到N-1個(gè)節(jié)點(diǎn)上，亞馬遜建議N配置為3，R代表一次成功的讀取操作中最小參與節(jié)點(diǎn)數(shù)量，W代表一次成功的寫(xiě)操作中最小參與節(jié)點(diǎn)數(shù)量。R+W>N，則會(huì)產(chǎn)生類(lèi)似于Quorum的效果。該模型中，讀（寫(xiě)）延遲由最慢的R(W)復(fù)制副本決定，為了得到比較小的延遲，R和W通常配置為小于N。亞馬遜建議(N, R, W)設(shè)置為(3, 2, 2)以兼顧性能與可用性。R和W直接影響性能、擴(kuò)展性和一致性，如果W設(shè)置為1，則一個(gè)實(shí)例中只要有一個(gè)節(jié)點(diǎn)可用，也不影響寫(xiě)操作，如果R設(shè)置為1，只要有一個(gè)節(jié)點(diǎn)可用，也不會(huì)影響讀請(qǐng)求，R和W值過(guò)小則影響一致性，過(guò)大則可用性，因此，需要在R和W兩個(gè)值之間平衡，這也是Dynamo的一個(gè)亮點(diǎn)之一。

3、版本合并
由前文可知，Dynamo為了保證高可用，對(duì)每份數(shù)據(jù)都復(fù)制了多份（建議3份），在數(shù)據(jù)沒(méi)有被異步復(fù)制到所有副本前，如果有g(shù)et操作會(huì)取到不一致的數(shù)據(jù)，但是Dynamo提供最終一致性。在亞馬遜平臺(tái)中，購(gòu)物車(chē)就是這種情況的典型應(yīng)用，為了保證購(gòu)物車(chē)永遠(yuǎn)可用，對(duì)任何一個(gè)副本的任何一次更改操作的結(jié)果都會(huì)當(dāng)做一個(gè)數(shù)據(jù)版本存儲(chǔ)起來(lái)，這樣當(dāng)用戶(hù)get時(shí)就會(huì)取到多個(gè)版本，這樣也就需要做數(shù)據(jù)版本合并了。Dynamo將合并工作推給應(yīng)用程序，在這里就是購(gòu)物車(chē)get時(shí)處理。

Dynamo用向量時(shí)鐘來(lái)標(biāo)識(shí)同一數(shù)據(jù)在不同節(jié)點(diǎn)上多個(gè)副本之間的因果關(guān)系。向量時(shí)鐘實(shí)際上就是一個(gè)列表，列表的每個(gè)節(jié)點(diǎn)是一個(gè)(node, counter)對(duì)，即(節(jié)點(diǎn)，計(jì)數(shù)器)列表。數(shù)據(jù)版本之間的關(guān)系要么是因果關(guān)系，要么是平行關(guān)系，關(guān)系判斷依賴(lài)于計(jì)數(shù)器值大小，如果第一個(gè)時(shí)鐘對(duì)象的計(jì)數(shù)器小于或等于所有其它時(shí)鐘對(duì)象的計(jì)數(shù)器時(shí)則是因果關(guān)系，那么因是果的祖先可以認(rèn)為是舊版數(shù)據(jù)而直接忽略，否則是平行關(guān)系，那么就認(rèn)為數(shù)據(jù)版本產(chǎn)生了沖突，需要協(xié)調(diào)并合并。

在Dynamo中，當(dāng)客戶(hù)端更新一個(gè)對(duì)象時(shí)，必須指定更新哪個(gè)版本數(shù)據(jù)，更新版本依賴(lài)于早期get操作時(shí)獲得的向量時(shí)鐘。

向量時(shí)鐘的使用過(guò)程圖上圖3所示，具體流程解析如下：
客戶(hù)端寫(xiě)入一個(gè)新對(duì)象。節(jié)點(diǎn)Sx處理了這個(gè)請(qǐng)求，處理對(duì)key的寫(xiě)：序列號(hào)遞增，并創(chuàng)建數(shù)據(jù)的向量時(shí)鐘，這樣在該節(jié)點(diǎn)上生成對(duì)象D1和向量時(shí)鐘[(Sx, 1)]。
客戶(hù)端更新該對(duì)象。假設(shè)由同樣的節(jié)點(diǎn)即Sx處理了這個(gè)請(qǐng)求，由于該節(jié)點(diǎn)有了D1和向量時(shí)鐘[(Sx, 1)]，則更新該對(duì)象后在該節(jié)點(diǎn)上生成對(duì)象D2和向量時(shí)鐘[(Sx, 2)]，D2繼承自D1，即D2覆寫(xiě)D1，計(jì)數(shù)器增1，但其它節(jié)點(diǎn)此時(shí)可能是D1，也可能是D2，這取決于網(wǎng)絡(luò)和節(jié)點(diǎn)狀態(tài)。
假設(shè)同一客戶(hù)端更新該對(duì)象但被不同的服務(wù)器處理了。節(jié)點(diǎn)Sy處理了這個(gè)請(qǐng)求，則更新該對(duì)象后在該節(jié)點(diǎn)上生成對(duì)象D3和向量時(shí)鐘[(Sx, 2), (Sy, 1)]。
假設(shè)另一客戶(hù)端讀取到了D2并嘗試更新它但被另一個(gè)不同的服務(wù)器處理了。節(jié)點(diǎn)Sz處理了這個(gè)請(qǐng)求，則更新該對(duì)象后在該節(jié)點(diǎn)上生成對(duì)象D4和向量時(shí)鐘[(Sx, 2), (Sz, 1)]。
節(jié)點(diǎn)數(shù)據(jù)版本回收?，F(xiàn)在有4個(gè)版本的數(shù)據(jù)存在并在各個(gè)節(jié)點(diǎn)之間傳遞了，當(dāng)節(jié)點(diǎn)收到D3或D4時(shí)，會(huì)根據(jù)向量時(shí)鐘將D1和D2回收掉，因?yàn)槠涫荄3和D4的祖先。但是收到D3和D4的節(jié)點(diǎn)，根據(jù)向量時(shí)鐘發(fā)現(xiàn)它們之間是并行關(guān)系，則保留二者，并在客戶(hù)端get時(shí)將二者都提交給客戶(hù)端由其來(lái)協(xié)調(diào)并合并版本。
假設(shè)客戶(hù)端讀取數(shù)據(jù)，則會(huì)獲取到D3和D4，根據(jù)兩者的向量時(shí)鐘，會(huì)合并為D5和向量時(shí)鐘[(Sx, 2), (Sy, 1), (Sz, 1)]，節(jié)點(diǎn)Sx協(xié)調(diào)寫(xiě)操作，并更新對(duì)象和向量時(shí)鐘。
從上面的過(guò)程中可以看出，在節(jié)點(diǎn)比較多且情況極端時(shí)，向量時(shí)鐘列表會(huì)增長(zhǎng)，Dynamo對(duì)此采用時(shí)鐘截?cái)喾桨竵?lái)解決此問(wèn)題，即(node, counter)對(duì)帶有時(shí)間戳，在數(shù)目達(dá)到閾值（比如：10）時(shí)，將最早的一對(duì)從向量時(shí)鐘中刪除。

4、故障檢測(cè)
（1）Ring Membership
每個(gè)節(jié)點(diǎn)啟動(dòng)時(shí)存儲(chǔ)自己在環(huán)上的映射信息并持久化到磁盤(pán)上，然后每個(gè)節(jié)點(diǎn)每隔一秒隨機(jī)選擇一個(gè)對(duì)等節(jié)點(diǎn)，通過(guò)Gossip協(xié)議傳播節(jié)點(diǎn)的映射i信息，最終每個(gè)節(jié)點(diǎn)都知道對(duì)等節(jié)點(diǎn)所處理范圍，即每個(gè)節(jié)點(diǎn)都可以直接轉(zhuǎn)發(fā)一個(gè)key的讀/寫(xiě)操作到正確的數(shù)據(jù)集節(jié)點(diǎn)，而不需要經(jīng)過(guò)中間路由或者跳。

（2）External Discovery
如果人工分別往Dynamo環(huán)中加入節(jié)點(diǎn)A和B，則Ring Membership不會(huì)立即檢測(cè)到這一變化，而出現(xiàn)暫時(shí)邏輯分裂的Dynamo環(huán)（A和B都認(rèn)為自己在環(huán)中，但是互相不知道對(duì)方存在）。Dynamo用External Discovery來(lái)解決這個(gè)問(wèn)題，即有些Dynamo節(jié)點(diǎn)充當(dāng)種子節(jié)點(diǎn)的角色，在非種子節(jié)點(diǎn)中配置種子節(jié)點(diǎn)的IP，所有非種子節(jié)點(diǎn)都與種子節(jié)點(diǎn)協(xié)調(diào)成員關(guān)系 。

（3）Failure Detection
Dynamo采用類(lèi)Gossip協(xié)議來(lái)實(shí)現(xiàn)去中心化的故障檢測(cè)，使系統(tǒng)中的每個(gè)節(jié)點(diǎn)都可以了解其它節(jié)點(diǎn)的加入和likai

5、故障處理
傳統(tǒng)的Quorum，在節(jié)點(diǎn)故障或者網(wǎng)絡(luò)故障情況下，系統(tǒng)不可用。為了提高可用性，Dynamo采用Sloppy Quorum和Hinted Handoff，即所有讀寫(xiě)操作由首選列表中的前N個(gè)健康節(jié)點(diǎn)執(zhí)行，而發(fā)往故障節(jié)點(diǎn)的數(shù)據(jù)做好標(biāo)記后被發(fā)往健康節(jié)點(diǎn)，故障節(jié)點(diǎn)重新可用時(shí)恢復(fù)副本。

如上面所示Dynamo配置N為3。如果在寫(xiě)過(guò)程中節(jié)點(diǎn)A暫時(shí)不可用（Down或無(wú)法連接），則發(fā)往A的副本將被發(fā)送到節(jié)點(diǎn)D，發(fā)到D的副本在其原始數(shù)據(jù)中有一個(gè)hint以表明節(jié)點(diǎn)A才是副本的預(yù)期接收者，D將副本數(shù)據(jù)保存在一個(gè)單獨(dú)的本地存儲(chǔ)中，在檢測(cè)到A可用時(shí)，D嘗試將副本發(fā)到A，如果發(fā)送成功，D會(huì)將數(shù)據(jù)從本地存儲(chǔ)中刪除而不會(huì)降低系統(tǒng)中的副本總數(shù)。

一個(gè)高可用的存儲(chǔ)系統(tǒng)具備處理整個(gè)IDC故障（斷電、自然災(zāi)害、網(wǎng)絡(luò)故障燈）的能力是非常重要的，Dynamo就具備此能力。Dynamo可以配置成跨多個(gè)IDC復(fù)制對(duì)象，即key的首選列表由跨多個(gè)IDC的節(jié)點(diǎn)組成，這些IDC之間由高速專(zhuān)線連接，跨多個(gè)IDC的復(fù)制方案使得Dynamo能夠處理整個(gè)IDC故障。

此外，為了處理在hinted副本移交會(huì)預(yù)期節(jié)點(diǎn)之前該副本不可用的情況，Dynamo實(shí)現(xiàn)了anti-entropy協(xié)議來(lái)保持副本同步，為了更快遞檢測(cè)副本之間的不一致性并減少傳輸量，Dynamo采用MerkleTree。

6、擴(kuò)容/縮容
（1）擴(kuò)容
當(dāng)一個(gè)新節(jié)點(diǎn)X加入到系統(tǒng)中時(shí)，其得到一些隨機(jī)分配到環(huán)上的token，節(jié)點(diǎn)X會(huì)負(fù)責(zé)處理一個(gè)key range，而這些key在節(jié)點(diǎn)X加入前由現(xiàn)有的一些節(jié)點(diǎn)負(fù)責(zé)，當(dāng)節(jié)點(diǎn)X加入后，這些節(jié)點(diǎn)將這些key傳遞給節(jié)點(diǎn)X。以圖2為例，假設(shè)節(jié)點(diǎn)X添加到環(huán)中A和B之間的位置，當(dāng)X加入到系統(tǒng)中后，其負(fù)責(zé)的key范圍為(F, G], (G, A], (A, X]，節(jié)點(diǎn)B、C和D都各自有一部分不再需要存儲(chǔ)的key范圍，即在X加入前，B負(fù)責(zé)(F, G], (G, A], (A, B]；C負(fù)責(zé)(G, A], (A, B], (B, C]；D負(fù)責(zé)(A, B], (B, C], (C, D]，而在X加入后，B負(fù)責(zé)(G, A], (A, X], (X, B]；C負(fù)責(zé)(A, X], (X, B], (B, C]；D負(fù)責(zé)(X, B], (B, C], (C, D]。節(jié)點(diǎn)B、C和D在收到節(jié)點(diǎn)X加入的確認(rèn)信號(hào)后出發(fā)這一過(guò)程。
（2）縮容
當(dāng)從系統(tǒng)中刪除一個(gè)節(jié)點(diǎn)時(shí)，key的重新分配情況與步驟（1）正好相反。
       
7、讀/寫(xiě)操作
讀取和寫(xiě)入由請(qǐng)求協(xié)調(diào)組件執(zhí)行，每個(gè)客戶(hù)端請(qǐng)求都將導(dǎo)致在處理該請(qǐng)求的節(jié)點(diǎn)上創(chuàng)建一個(gè)狀態(tài)機(jī)，每個(gè)狀態(tài)機(jī)都包含以下邏輯：
標(biāo)識(shí)負(fù)責(zé)一個(gè)key的節(jié)點(diǎn)；
發(fā)送請(qǐng)求；
等待回應(yīng)；
可能的重試處理；
加工和包裝返回客戶(hù)端響應(yīng)。

每個(gè)狀態(tài)機(jī)實(shí)例只處理一個(gè)客戶(hù)端請(qǐng)求，如果是一個(gè)讀請(qǐng)求，則狀態(tài)機(jī)如下：
發(fā)送讀請(qǐng)求到相應(yīng)結(jié)點(diǎn)；
等待所需的最低數(shù)量的響應(yīng)；
如果在給定的時(shí)間內(nèi)收到的響應(yīng)太少，則請(qǐng)求失敗；
否則收集所有數(shù)據(jù)的版本，并確定要返回的版本；
如果啟用版本合并，則執(zhí)行語(yǔ)法協(xié)調(diào)并生成一個(gè)對(duì)客戶(hù)端不透明的寫(xiě)上下文，其中包含一個(gè)囊括所有版本的向量時(shí)鐘。
返回讀取響應(yīng)給客戶(hù)端后，狀態(tài)機(jī)等待一段時(shí)間以接受任何懸而未決的響應(yīng)，如果任何響應(yīng)返回了過(guò)時(shí)的版本，則協(xié)調(diào)員用最新版本更新這些節(jié)點(diǎn)，以完成讀修復(fù)。
寫(xiě)請(qǐng)求通常跟隨在讀請(qǐng)求之后，則協(xié)調(diào)員由讀操作答復(fù)最快的節(jié)點(diǎn)充當(dāng)，這種優(yōu)化能提高讀寫(xiě)一致性。

五、解決問(wèn)題
1、可用性
完全去中心化，無(wú)單點(diǎn)，永遠(yuǎn)可寫(xiě)。

2、伸縮性
帶虛擬機(jī)節(jié)點(diǎn)的一致性hash：一致性hash解決擴(kuò)容/縮容問(wèn)題，虛擬節(jié)點(diǎn)解決機(jī)器異質(zhì)性問(wèn)題。

3、可靠性
數(shù)據(jù)復(fù)制多份副本，用向量時(shí)鐘解決版本合并問(wèn)題。

4、可配置
平衡性可調(diào)，即根據(jù)（N,W,R）模型平衡可用性和一致性，建議模型參數(shù)為（3,2,2）。