在最近的一週時間裡，一直都在研究和閱讀 Amazon 的一篇論文 《Dynamo: Amazon’s Highly Available Key-value Store》，論文中描述了 Amazon 的高可用分佈式鍵值存儲服務 Dynamo 的實現原理。

之前在閱讀 Google 的《Bigtable: A Distributed Storage System for Structured Data》時寫了一篇《淺析 Bigtable 和 LevelDB的實現》文章，分析了 Bigtable 的單機版 LevelDB 的實現原理；在研究 Dynamo 時，作者發現 Dynamo 雖然和 Bigtable 同為 NoSQL，但是它們的實現卻有著很大的不同，最主要的原因來自不同的應用場景和不同的目的。

Bigtable 和 Dynamo

Bigtable 和 Dynamo 兩者分別是 Google 和 Amazon 兩大巨頭給出的存儲海量數據的解決方法，作為 NoSQL 兩者都具有分佈式、容錯以及可擴展的幾大特性。

雖然兩者都是 NoSQL，並且有著相似的特性，但是它們在側重的方向上有非常明顯的不同，從兩個數據庫論文的標題中，我們就能看到 Amazon 的 Dynamo 追求的是高可用性並且提供的是類似 MongoDB 的 Key-value 文檔存儲，而 Bigtable 中描述的數據庫卻可以用於結構化的數據存儲。

由於 Bigtable 和 Dynamo 都屬於同一個類別 - NoSQL，所以它們經常會被放在一起進行對比，這篇文章不僅會介紹 Dynamo 的設計理念以及架構等問題，還會就其中的部分問題與 Bigtable 中相對應的概念進行對比，這樣能夠讓我們更加清楚地瞭解不同的數據庫對不同問題，因設計理念的差異做出的權衡。

架構

在數據庫領域中尤其是分佈式數據庫，最重要的就是服務的架構，多數的分佈式系統在設計時都會假設服務運行在廉價的節點上，並沒有出眾的性能和也不能提供穩定的服務，所以水平擴展和容錯的能力是分佈式數據庫的標配；但是不同的分佈式數據庫選用了不同的架構來組織大量的節點。

很多的分佈式服務例如 GFS 和 Bigtable 都使用了帶有主節點的架構來維護整個系統中的元數據，包括節點的位置等信息，而 Dynamo 的實現不同於這些中心化的分佈式服務，在 Dynamo 中所有的節點都有著完全相同的職責，會對外界提供同樣的服務，所以在整個系統中並不會出現單點故障的問題。

去中心化的架構使得系統的水平擴展非常容易，節點可以在任何時候直接加入到整個 Dynamo 的集群中，並且只會造成集群中少量數據的遷移。

Bigtable 使用了中心化的架構，通過主節點來維護整個系統中全部的元數據信息，但是 Bigtable 本身其實並不會處理來自客戶端的讀寫請求，所有請求都會由客戶端直接和從節點通信，不過由於有了中心化的主節點，所以主節點一旦發生故障宕機就會造成服務的不可用，雖然 Bigtable 以及類似的服務通過其他方式解決這個問題，但是這個問題仍然是中心化的設計所造成的。

中心化或者去中心化並不是一個絕對好或者絕對壞的選擇，選擇中心化的解決方案能夠降低系統實現的複雜度，而去中心化的方式能夠避免單點故障，讓系統能夠更好更快地增加新的節點，提供優秀的水平擴展能力。

分片和複製

Dynamo 在設計之初就定下了增量擴展（Incremental Scalability）的核心需求，這也就需要一種能夠在一組節點中動態分片的機制，Dynamo 的分片策略依賴於一致性哈希，通過這種策略 Dynamo 能夠將負載合理的分配到不同的存儲節點上。

所有的鍵在存儲之前都會通過哈希函數得到一個唯一的值，哈希函數的輸出被看做是一個固定長度的環，也就是其輸出的最大值和最小值是『連接』到一起的：

每一個節點都會被 Dynamo 在這個環中分配一個隨機的位置，而這個節點會處理從哈希的輸出在當前節點前的所有鍵；假設我們有一個鍵值對 (draven, developer)，Hash(draven) 的結果位於上圖中的綠色區域，從環中的位置開始按照順時針的順序尋找，找到的以第一個節點 B 就會成為協調者（coordinator）負責處理當前的鍵值對，上圖中的每一個節點都會負責與其顏色相同的部分。

由於 Dynamo 系統中的每一個節點在剛剛加入當前的集群時，會被分配一個隨機的位置，所以由於算法的隨機性可能會導致不同節點處理的範圍有所不同，最終每一個節點的負載也並不相同；為了解決這個問題，Dynamo 使用了一致性哈希算法的變種，將同一個物理節點分配到環中的多個位置（標記），成為多個虛擬節點，但是在這種策略下，如果當前的 Dynamo 節點一天處理上百萬的請求，那麼新增節點為了不影響已有節點的性能，會在後臺進行啟動，整個過程大約會消耗一整天的時間，這其實是很難接受的，除此之外這種策略還會造成系統進行日常歸檔極其緩慢。

為了解決負載的不均衡的問題，除了上面使用虛擬節點的策略之外，Dynamo 論文中還提供了另外兩種策略，其中性能相對較好的是將數據的哈希分成 Q 個大小相等的區域，S 個節點每一個處理 Q/S 個分區，當某一個節點因為故障或者其他原因需要退出集群時，會將它處理的數據分片隨機分配給其它的節點，當有節點加入系統時，會從其它的節點中『接管』對應的數據分片。上圖只是對這種策略下的分片情況簡單展示，在真實環境中分片數 Q 的值遠遠大於節點數 S。

Dynamo 為了達到高可用性和持久性，防止由於節點宕機故障或者數據丟失，將同一份數據在協調者和隨後的 N-1 個節點上備份了多次，N 是一個可以配置的值，在一般情況下都為 3。

也就是說，上圖中黃色區域的值會存儲在三個節點 A、B 和 C 中，綠色的區域會被 B、C、D 三個節點處理，從另一個角度來看，A 節點會處理範圍在 (C, A] 之間的值，而 B 節點會處理從 (D, B] 區域內的值。

負責存儲某一個特定鍵值對的節點列表叫做偏好列表（preference list），因為虛擬節點在環中會隨機存在，為了保證出現節點故障時不會影響可用性和持久性，偏好列表中的全部節點必須都為不同的物理節點。

Bigtable 中對分片和複製的實現其實就與 Dynamo 中完全不同，這不僅是因為 Bigtable 的節點有主從之分，還因為 Bigtable 的設計理念與 Dynamo 完全不同。在 Bigtable 中，數據是按照鍵的順序存儲的，數據存儲的單位都是 tablet，每一張表都由多個 tablet 組成，而每一個的 tablet 都有一個 tablet 服務器來處理，而 tablet 的位置都存儲在 METADATA 表中。

在 Bigtable 中，所有的 tablet 都在 GFS 中以 SSTable 的格式存儲起來，這些 SSTable 都被分成了固定大小的塊在 chunkserver 上存儲，而每一個塊也都會在存儲在多個 chunkserver 中。

讀寫請求的執行

Dynamo 集群中的任意節點都能夠接受來自客戶端的對於任意鍵的讀寫請求，所有的請求都通過 RPC 調用執行，客戶端在選擇節點時有兩種不同的策略：一種是通過一個負載均衡器根據負載選擇不同的節點，另一種是通過一個清楚當前集群分片的庫直接請求相應的節點。

從上面我們就已經知道了處理讀寫請求的節點就叫做協調者（coordinator），前 N 個『健康』的節點會參與讀寫請求的處理；Dynamo 使用了 Quorum 一致性協議來保證系統中的一致性，協議中有兩個可以配置的值：R 和 W，其中 R 是成功參與一個讀請求的最小節點數，而 W 是成功參與寫請求的最小節點數。

當 R = 2 時，所有的讀請求必須等待兩個節點成功返回對應鍵的結果，才認為當前的請求結束了，也就是說讀請求的時間取決於返回最慢的節點，對於寫請求來說也是完全相同的；當協調者接收到了來自客戶端的寫請求 put() 時，它會創建一個新的向量時鐘（vector clock），然後將新版本的信息存儲在本地，之後向偏好列表（preference list）中的前 N-1 個節點發送消息，直到其中的 W-1 個返回這次請求才成功結束，讀請求 get() 與上述請求的唯一區別就是，如果協調者發現節點中的數據出現了衝突，就會對衝突嘗試進行解決並將結果重新寫回對應的節點。

衝突和向量時鐘

Dynamo 與目前的絕大多數分佈式系統一樣都提供了最終一致性，最終一致性能夠允許我們異步的更新集群中的節點，put() 請求可能會在所有的節點後更新前就返回對應的結果了，在這時隨後的 get() 就可能獲取到過期的數據。

如果在系統中出現了節點故障宕機，那麼數據的更新可能在一段時間內都不會到達失效的節點，這也是在使用 Dynamo 或者使用相似原理的系統時會遇到的問題，Amazon 中的很多應用雖然都能夠忍受這種數據層面可能發生的不一致性，但是有些對業務數據一致性非常高的應用在選擇 Dynamo 時就需要好好考慮了。

因為 Dynamo 在工作的過程中不同的節點可能會發生數據不一致的問題，這種問題肯定是需要解決的，Dynamo 能夠確保一旦數據之間發生了衝突不會丟失，但是可能會有已被刪除的數據重新出現的問題。

在多數情況下，Dynamo 中的最新版本的數據都會取代之前的版本，系統在這時可以通過語法調解（syntactic reconcile）數據庫中的正確版本。但是版本也可能會出現分支，在這時，Dynamo 就會返回所有它無法處理的數據版本，由客戶端在多個版本的數據中選擇或者創建（collapse）合適的版本返回給 Dynamo，其實這個過程比較像出現衝突的 git merge 操作，git 沒有辦法判斷當前的哪個版本是合適的，所以只能由開發者對分支之間的衝突進行處理。

上圖中的每一個對象的版本 Dx 中存儲著一個或多個向量時鐘 [Sn, N]，每次 Dynamo 對數據進行寫入時都會更新向量時鐘的版本，節點 Sx 第一次寫入時向量時鐘為 [Sx, 1]，第二次為 [Sx, 2]，在這時假設節點 Sy 和 Sz 都不知道 Sx 已經對節點進行寫入了，它們接收到了來自其他客戶端的請求，在本地也對同樣鍵做出了寫入並分別生成了不同的時鐘 [Sy, 1] 和 [Sz, 1]，當客戶端再次使用 get() 請求時就會發現數據出現了衝突，由於 Dynamo 無法根據向量時鐘自動解決，所以它需要手動合併三個不同的數據版本。

論文中對 24 小時內的請求進行了統計，其中 99.94% 的請求僅會返回一個版本，0.00057% 的請求會返回兩個版本，0.00047 的請求會返回三個版本，0.000009% 的請求會返回四個版本，雖然論文中說：

This shows that divergent versions are created rarely.

但是作者仍然認為在海量的數據面前 99.94% 並不是一個特別高的百分比，處理分歧的數據版本仍然會帶來額外的工作量和負擔。雖然在這種情況下，數據庫本身確實沒有足夠的信息來解決數據的不一致問題，也確實只能由客戶端去解決衝突，但是這種將問題拋給上層去解決的方式並不友好，論文中也提到了 Amazon 中使用 Dynamo 的應用程序也都是能夠適應並解決這些數據不一致的問題的，不過對於作者來說，僅僅這一個問題就成為不選擇 Dynamo 的理由了。

節點的增刪

因為在分佈式系統中節點的失效是非常常見的事情，而節點也很少會因為某些原因永久失效，往往大部分節點會臨時宕機然後快速重新加入系統；由於這些原因，Dynamo 選擇使用了顯式的機制向系統中添加和移除節點。

添加節點時可以使用命令行工具或者瀏覽器連接 Dynamo 中的任意節點後觸發一個成員變動的事件，這個事件會從當前的環中移除或者向環中添加一個新的節點，當節點的信息發生改變時，該節點會通過 Gossip 協議通知它所能通知的最多的節點。

在 Gossip 協議中，每次通訊的兩個節點會對當前系統中的節點信息達成一致；通過節點之間互相傳遞成員信息，最終整個 Dyanmo 的集群中所有的節點都會就成員信息達成一致，如上圖所示，”gossip” 首先會被 C 節點接收，然後它會傳遞給它能接觸到的最多的節點 A、D、F、G 四個節點，然後 “gossip” 會進行二次傳播傳遞給系統中的灰色節點，到此為止系統中的所有節點都得到了最新的 “gossip” 消息。

當我們向 Dynamo 中加入了新的節點時，會發生節點之間的分片轉移，假設我們連接上了 Dynamo 數據庫，然後添加了一個 X 節點，該節點被分配到了如下圖所示的 A 和 B 節點之間。

新引入的節點 X 會從三個節點 C、D、E 中接受它們管理的分片的一部分，也就是上圖中彩色的 (E, A]、(A, B] 和 (B, X] 三個部分，在 X 節點加入集群之前分別屬於與其顏色相同的節點管理。

Dynamo 由於其去中心化的架構，節點增刪的事件都需要通過 Gossip 協議進行傳遞，然而擁有主從節點之分的 Bigtable 就不需要上述的方式對集群中的節點進行增刪了，它可以直接通過用於管理其他從節點的服務直接註冊新的節點或者撤下已有的節點。

副本同步

在 Dynamo 運行的過程中，由於一些情況會造成不同節點中的數據不一致的問題，Dynamo 使用了反信息熵（anti-entropy）的策略保證所有的副本存儲的信息都是同步的。

為了快速確認多個副本之間的數據的一致性並避免大量的數據傳輸，Dynamo 使用了 Merkle tree 對不同節點中的數據進行快速驗證。

在 Merkle 樹中，所有父節點中的內容都是葉子節點的哈希，通過這種方式構建的樹形結構能夠保證整棵樹不會被篡改，任何的改動都能被立刻發現。

Dynamo 中的每一個節點都為其持有的鍵的範圍維護了一顆 Merkle 樹，在驗證兩份節點中的數據是否相同時，只需要發送根節點中的哈希值，如果相同那麼說明兩棵樹的內容全部相同，否則就會依次對比不同層級節點中的內容，直到找出不同的副本，這種做法雖然能夠減少數據的傳輸並能夠快速找到副本之間的不同，但是當有新的節點加入或者舊的節點退出時會導致大量的 Merkle 樹重新計算。

總結

在 Dynamo 的論文公開之後，有一篇文章將 Dynamo 的設計稱作 “A flawed architecture”，這篇文章的作者在文中對 Dynamo 的實現進行了分析，主要對其最終一致性和 Quorom 機制進行了批評，它在 HackerNews 上也引起了廣泛的討論，帖子中的很多內容都值得一看，能夠幫助我們瞭解 Dynamo 的設計原理，而 Amazon 的 CTO 對於這篇文章也發了一條 Twitter：

不管如何，Dynamo 作為支撐亞馬遜業務的底層服務，其實現原理和思想對於整個社區都是非常有價值的，然而它使用的去中心化的策略也帶了很多問題，雖然作者可能會因為這個原因在選擇數據庫時不會 Dynamo，不過相信它也是有合適的應用場景的。

原文地址：https://draveness.me/dynamo

作 者： Draveness