一、系統概述
1、Amazon平臺概述
Amazon平臺是一個由數百服務組成的面向服務的架構，其秉承高度去中心化、松散耦合、完全分布式的原則，具體架構參考下圖。
在這種環境中，尤其需要一個始終可用的存儲系統，由此，Dynamo誕生了。
2、Dynamo概述
Dynamo是Amazon提供的一款高可用的分布式Key-Value存儲系統，其滿足可伸縮性、可用性、可靠性。
CAP原理滿足：通過一致性哈希滿足P，用復制滿足A，用對象版本與向量時鐘滿足C。用犧牲C來滿足高可用的A，但是最終會一致。但是，是犧牲C滿足A，還是犧牲A滿足C，可以根據NWR模型來調配，以達到收益成本平衡。
Dynamo內部有3個層面的概念：
Key-Value：Key唯一標識一個數據對象，Value標識數據對象實體，通過對Key來完成對數據對象的讀寫操作。
節點node：節點是指一個物理主機。在每個節點上，會有3個必備組件：請求協調器（request coordination）、成員與失敗檢測、本地持久引擎（local persistence engine），這些組件都由Java實現。本地持久引擎支持不同的存儲引擎，最主要的引擎是Berkeley Database Transactional Data Store（存儲數百K的對象更合適），其它還有BDB Java Edtion、MySQL以及一致性內存Cache。本地持久化引擎組件是一個可插拔的持久化組件，應用程序可以根據需要選擇最合適的存儲引擎，比如：如果存儲對象的通常為數千字節則可以選擇BDB，如果是更多尺寸則可以選擇MySQL。生產中，Dynamo通常使用BDB事物數據存儲。
實例instance：從應用的角度來看就是一個服務，提供IO功能。每個實例由一組節點組成，這些節點可能位于不同的IDC，這樣IDC出現問題也不會導致數據丟失，這樣會有更好的容災和可靠性。
二、背景條件
1、系統假設與要求
（1）查詢模型
基于Key-Value模型，而不是SQL即關系模型。存儲對象比較小，通常小于1MB。
（2）ACID屬性
傳統的關系數據庫中，用ACID（A原子性、C一致性、I隔離性、D持久性）來保證事務，在保證ACID的前提下往往有很差的可用性。Dynamo用弱一致性C來達到高可用，不提供數據隔離I，只允許單Key更新。
（3）效率
在廉價的機器上滿足SLA，通過配置來滿足延時和吞吐量的要求，因此，必須在性能、成本、可用性和持久性保證之間做權衡。
（4）其它假設
Dynamo僅在Amazon內部使用，因此，認為其使用環境是可信賴的。
2、服務水平協議（SLA）
所謂服務水平協議是指客戶端和服務端在某幾個指標上達成一致的一個協議，通常包括客戶端請求API的速率、服務端的預期延時，比如：在客戶端每秒500個請求負載的高峰時，99.9%的響應時間為300毫秒。
一般業界，對這種面向性能的SLA采用平均數（average）、中值（median）和預期變化（expected variance）。但是這些指標只能對大多數客戶端有良好體驗，而不是所有。為了解決這個問題，Dynamo采用99.9%百分位來代替這些指標。
3、設計考慮（復制數據）
傳統的數據復制算法，在出現故障時，為了保證數據一致性被迫犧牲掉可用性，即：與其不能確定數據是否正確，不如讓數據一直不可用直到數據絕對正確時。
但是，一個高度靈活的系統應該能夠讓用戶知道在何種情況下能到達哪些屬性，Dynamo就是如此。
對于故障是常態的系統來說，采用樂觀復制技術可以提供系統的可用性，但帶來的問題是需要檢測并協調解決沖突，協調解決沖突的過程又包含兩個問題，即：何時協調和由誰協調。Dynamo的設計是數據存儲最終一致，即所有更新操作最終到達所有副本。
（1）何時協調
無外乎兩種情況：寫或者讀時協調沖突。
傳統數據存儲在寫時協調沖突，即如果給定時間內數據不能達到所要求的所有或大多數副本數，則寫入可能會被拒絕。
Amazon認為拒絕客戶的更新操作會導致糟糕的用戶體驗，典型應用是購物車服務，即使出現故障，客戶仍然可以向購物車添加或者刪除物品，基于此，Dynamo的目標定位為“永遠可寫”（always writable）即數據存儲的“寫”是高可用的。也就是說Dynamo為了確保“寫”永遠不會被拒絕，那么數據存儲在讀時協調沖突。
（2）由誰協調
無外乎兩種情況：由數據存儲本身或客戶端應用程序來協調。
如果是數據存儲本身協調，則只能使用簡單策略來協調沖突的更新操作，比如：“最后一次寫入獲勝”（last write wins）。
如果是客戶端應用程序協調，則應用程序可以根據業務需求來選擇最適合協調沖突的方法。
Dynamo選擇了后者，典型應用還是購物車服務，返回所有數據對象版本，最后選擇合并完沖突的版本。
三、關鍵技術
Dynamo作為一類分布式系統的典型代表，其眾多關鍵技術給其帶來一系列的優勢，具體參看下表：
1、數據分區
Hash算法：使用MD5對Key進行Hash以產生一個128位的標示符，以此來確定Key的存儲節點。
為了達到增量可伸縮性的目地，Dynamo采用一致性哈希來完成數據分區。在一致性哈希中，哈希函數的輸出范圍為一個圓環，如圖2所示，系統中每個節點映射到環中某個位置，而Key也被Hash到環中某個位置，Key從其被映射的位置開始沿順時針方向找到第一個位置比其大的節點作為其存儲節點，換個角度說，就是每個系統節點負責從其映射的位置起到逆時針方向的第一個系統節點間的區域。
一致性哈希最大的優點在于節點的擴容與縮容，只影響其直接的鄰居節點，而對其它節點沒有影響。這樣看似很完美了，但是亞馬遜沒有因此而停止腳本，這是其偉大之處，其實還存在兩個問題：節點數據分布不均勻和無視節點性能的異質性。為了解決這兩個問題，Dynamo對一致性哈希進行了改進而引入了虛擬節點，即每個節點從邏輯上切分為多個虛擬節點，每個虛擬節點從邏輯上看像一個真實節點，這樣每個節點就被分配到環上多個點而不是一個單點。
2、數據復制
為了實現高可用，Dynamo將每個數據復制到N臺主機上，其中N是每個實例（per-instance）的配置參數，建議值為3。每個Key被分配到一個協調器（coordinator）節點，協調器節點管理其負責范圍內的復制數據項，其除了在本地存儲其責任范圍內的每個Key外，還復制這些Key到環上順時針方向的N-1個后繼節點。這樣，系統中每個節點負責環上從其自己位置開始到第N個前驅節點間的一段區域。具體邏輯見圖2，圖中節點B除了在本地存儲鍵K外，還在節點C和D處復制鍵K，這樣節點D將存儲落在范圍(A, B]、(B, C]和(C, D]上的所有鍵：
對于一個特定的鍵都有一個首選節點列表，由于虛擬節點的存在，為了解決節點故障的問題，構建首先節點列表時會跳過環上某些位置，讓這些節點分別位于不同的物理節點上，以保證高可用。
為了保證復制時數據副本的一致性，Dynamo采用類似于Quorum系統的一致性協議實現。這里涉及到三個關鍵參數(N, R, W)，其中，N是指數據對象復制到N臺主機，協調器負責將數據復制到N-1個節點上，亞馬遜建議N配置為3，R代表一次成功的讀取操作中最小參與節點數量，W代表一次成功的寫操作中最小參與節點數量。R+W>N，則會產生類似于Quorum的效果。該模型中，讀（寫）延遲由最慢的R(W)復制副本決定，為了得到比較小的延遲，R和W通常配置為小于N。亞馬遜建議(N, R, W)設置為(3, 2, 2)以兼顧性能與可用性。R和W直接影響性能、擴展性和一致性，如果W設置為1，則一個實例中只要有一個節點可用，也不影響寫操作，如果R設置為1，只要有一個節點可用，也不會影響讀請求，R和W值過小則影響一致性，過大則可用性，因此，需要在R和W兩個值之間平衡，這也是Dynamo的一個亮點之一。
3、版本合并
由前文可知，Dynamo為了保證高可用，對每份數據都復制了多份（建議3份），在數據沒有被異步復制到所有副本前，如果有get操作會取到不一致的數據，但是Dynamo提供最終一致性。在亞馬遜平臺中，購物車就是這種情況的典型應用，為了保證購物車永遠可用，對任何一個副本的任何一次更改操作的結果都會當做一個數據版本存儲起來，這樣當用戶get時就會取到多個版本，這樣也就需要做數據版本合并了。Dynamo將合并工作推給應用程序，在這里就是購物車get時處理。
Dynamo用向量時鐘來標識同一數據在不同節點上多個副本之間的因果關系。向量時鐘實際上就是一個列表，列表的每個節點是一個(node, counter)對，即(節點，計數器)列表。數據版本之間的關系要么是因果關系，要么是平行關系，關系判斷依賴于計數器值大小，如果第一個時鐘對象的計數器小于或等于所有其它時鐘對象的計數器時則是因果關系，那么因是果的祖先可以認為是舊版數據而直接忽略，否則是平行關系，那么就認為數據版本產生了沖突，需要協調并合并。
在Dynamo中，當客戶端更新一個對象時，必須指定更新哪個版本數據，更新版本依賴于早期get操作時獲得的向量時鐘。
向量時鐘的使用過程圖上圖3所示，具體流程解析如下：
客戶端寫入一個新對象。節點Sx處理了這個請求，處理對key的寫：序列號遞增，并創建數據的向量時鐘，這樣在該節點上生成對象D1和向量時鐘[(Sx, 1)]。
客戶端更新該對象。假設由同樣的節點即Sx處理了這個請求，由于該節點有了D1和向量時鐘[(Sx, 1)]，則更新該對象后在該節點上生成對象D2和向量時鐘[(Sx, 2)]，D2繼承自D1，即D2覆寫D1，計數器增1，但其它節點此時可能是D1，也可能是D2，這取決于網絡和節點狀態。
假設同一客戶端更新該對象但被不同的服務器處理了。節點Sy處理了這個請求，則更新該對象后在該節點上生成對象D3和向量時鐘[(Sx, 2), (Sy, 1)]。
假設另一客戶端讀取到了D2并嘗試更新它但被另一個不同的服務器處理了。節點Sz處理了這個請求，則更新該對象后在該節點上生成對象D4和向量時鐘[(Sx, 2), (Sz, 1)]。
節點數據版本回收。現在有4個版本的數據存在并在各個節點之間傳遞了，當節點收到D3或D4時，會根據向量時鐘將D1和D2回收掉，因為其是D3和D4的祖先。但是收到D3和D4的節點，根據向量時鐘發現它們之間是并行關系，則保留二者，并在客戶端get時將二者都提交給客戶端由其來協調并合并版本。
假設客戶端讀取數據，則會獲取到D3和D4，根據兩者的向量時鐘，會合并為D5和向量時鐘[(Sx, 2), (Sy, 1), (Sz, 1)]，節點Sx協調寫操作，并更新對象和向量時鐘。
從上面的過程中可以看出，在節點比較多且情況極端時，向量時鐘列表會增長，Dynamo對此采用時鐘截斷方案來解決此問題，即(node, counter)對帶有時間戳，在數目達到閾值（比如：10）時，將最早的一對從向量時鐘中刪除。
4、故障檢測
（1）Ring Membership
每個節點啟動時存儲自己在環上的映射信息并持久化到磁盤上，然后每個節點每隔一秒隨機選擇一個對等節點，通過Gossip協議傳播節點的映射i信息，最終每個節點都知道對等節點所處理范圍，即每個節點都可以直接轉發一個key的讀/寫操作到正確的數據集節點，而不需要經過中間路由或者跳。
（2）External Discovery
如果人工分別往Dynamo環中加入節點A和B，則Ring Membership不會立即檢測到這一變化，而出現暫時邏輯分裂的Dynamo環（A和B都認為自己在環中，但是互相不知道對方存在）。Dynamo用External Discovery來解決這個問題，即有些Dynamo節點充當種子節點的角色，在非種子節點中配置種子節點的IP，所有非種子節點都與種子節點協調成員關系 。
（3）Failure Detection
Dynamo采用類Gossip協議來實現去中心化的故障檢測，使系統中的每個節點都可以了解其它節點的加入和likai
5、故障處理
傳統的Quorum，在節點故障或者網絡故障情況下，系統不可用。為了提高可用性，Dynamo采用Sloppy Quorum和Hinted Handoff，即所有讀寫操作由首選列表中的前N個健康節點執行，而發往故障節點的數據做好標記后被發往健康節點，故障節點重新可用時恢復副本。
如上面所示Dynamo配置N為3。如果在寫過程中節點A暫時不可用（Down或無法連接），則發往A的副本將被發送到節點D，發到D的副本在其原始數據中有一個hint以表明節點A才是副本的預期接收者，D將副本數據保存在一個單獨的本地存儲中，在檢測到A可用時，D嘗試將副本發到A，如果發送成功，D會將數據從本地存儲中刪除而不會降低系統中的副本總數。
一個高可用的存儲系統具備處理整個IDC故障（斷電、自然災害、網絡故障燈）的能力是非常重要的，Dynamo就具備此能力。Dynamo可以配置成跨多個IDC復制對象，即key的首選列表由跨多個IDC的節點組成，這些IDC之間由高速專線連接，跨多個IDC的復制方案使得Dynamo能夠處理整個IDC故障。
此外，為了處理在hinted副本移交會預期節點之前該副本不可用的情況，Dynamo實現了anti-entropy協議來保持副本同步，為了更快遞檢測副本之間的不一致性并減少傳輸量，Dynamo采用MerkleTree。
6、擴容/縮容
（1）擴容
當一個新節點X加入到系統中時，其得到一些隨機分配到環上的token，節點X會負責處理一個key range，而這些key在節點X加入前由現有的一些節點負責，當節點X加入后，這些節點將這些key傳遞給節點X。以圖2為例，假設節點X添加到環中A和B之間的位置，當X加入到系統中后，其負責的key范圍為(F, G], (G, A], (A, X]，節點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]。節點B、C和D在收到節點X加入的確認信號后出發這一過程。
（2）縮容
當從系統中刪除一個節點時，key的重新分配情況與步驟（1）正好相反。
7、讀/寫操作
讀取和寫入由請求協調組件執行，每個客戶端請求都將導致在處理該請求的節點上創建一個狀態機，每個狀態機都包含以下邏輯：
標識負責一個key的節點；
發送請求；
等待回應；
可能的重試處理；
加工和包裝返回客戶端響應。
每個狀態機實例只處理一個客戶端請求，如果是一個讀請求，則狀態機如下：
發送讀請求到相應結點；
等待所需的最低數量的響應；
如果在給定的時間內收到的響應太少，則請求失敗；
否則收集所有數據的版本，并確定要返回的版本；
如果啟用版本合并，則執行語法協調并生成一個對客戶端不透明的寫上下文，其中包含一個囊括所有版本的向量時鐘。
返回讀取響應給客戶端后，狀態機等待一段時間以接受任何懸而未決的響應，如果任何響應返回了過時的版本，則協調員用最新版本更新這些節點，以完成讀修復。
寫請求通常跟隨在讀請求之后，則協調員由讀操作答復最快的節點充當，這種優化能提高讀寫一致性。
五、解決問題
1、可用性
完全去中心化，無單點，永遠可寫。
2、伸縮性
帶虛擬機節點的一致性hash：一致性hash解決擴容/縮容問題，虛擬節點解決機器異質性問題。
3、可靠性
數據復制多份副本，用向量時鐘解決版本合并問題。
4、可配置
平衡性可調，即根據（N,W,R）模型平衡可用性和一致性，建議模型參數為（3,2,2）。
