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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了達到增量可伸縮性的目地，Dynamo采用一致性哈希來完成數(shù)據(jù)分區(qū)。在一致性哈希中，哈希函數(shù)的輸出范圍為一個圓環(huán)，如圖2所示，系統(tǒng)中每個節(jié)點映射到環(huán)中某個位置，而Key也被Hash到環(huán)中某個位置，Key從其被映射的位置開始沿順時針方向找到第一個位置比其大的節(jié)點作為其存儲節(jié)點，換個角度說，就是每個系統(tǒng)節(jié)點負責從其映射的位置起到逆時針方向的第一個系統(tǒng)節(jié)點間的區(qū)域。

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

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

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

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

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

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

在Dynamo中，當客戶端更新一個對象時，必須指定更新哪個版本數(shù)據(jù)，更新版本依賴于早期get操作時獲得的向量時鐘。

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

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

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

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

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

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

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

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

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

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

五、解決問題
1、可用性
完全去中心化，無單點，永遠可寫。

2、伸縮性
帶虛擬機節(jié)點的一致性hash：一致性hash解決擴容/縮容問題，虛擬節(jié)點解決機器異質(zhì)性問題。

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

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