[論文筆記]Dynamo:Amazons KV Store

來自專欄分散式領域經典論文4 人贊了文章

論文全名：Dynamo: Amazon』s Highly Available Key-value Store

這篇論文敘述的是 Amazon 研發的高可用 Key-Value 存儲系統，Dynamo。很多 Amazon 的核心服務依賴於它，它通過犧牲在某些特定失效情況下的數據一致性來保證高度可用。它採用一致性哈希來獲得可伸縮性和提高可用性，並且通過對象版本（Object Versioning）來保證一致性。在更新數據過程中，副本之間的一致性通過一種 quorum-like 技術和去中心化的同步複製協議保證。Dynamo 採用基於 gossip 的失效探測和成員協議。Dynamo 是完全去中心化的系統，節點增加和刪除不需要人工操作。

設計思考

這裡作者指出 Dynamo 兩個設計權衡點，一個是什麼時候解決更新數據的衝突，一個是誰來解決衝突。前者 Dynamo 決定在 read 的時候解決為了保證 wirte 一直可用提供良好的用戶體驗；後者覺得由應用來解決而不是 data store 已獲得靈活性。

比較討論

這部分作者提到了一些中心化的存儲系統，指出 Dynamo 由於特殊需求從而設計也與這些系統不同。主要的特殊需求體現在：（一）永遠可寫，不能拒絕寫請求；（二）建立在所有節點均可信任的基礎設施上；（三）使用 Dynamo 的應用不依賴層次結構的命名服務；（四）低延遲和高性能決定了不能將請求進行過多的路由轉發

系統架構

論文聚焦於系統的數據分區、複製、版本、成員、容錯和伸縮。

系統介面

Dynamo 提供 get 和 put 兩個介面。get(key) 操作定位到數據的副本且返回一個單獨對象或者版本不同的對象列表和 context。put(key, context, object) 操作決定數據存到哪個副本且將副本刷回磁碟持久化。context 包含了對象的元數據例如版本信息，對 caller 不透明。Dynamo將 caller 提供的 key 和對象當成一個不透明的位元組數組。它使用 MD5 對 key 進行 Hash 以產生一個 128 位的標識符，它是用來確定負責那個 key 的存儲節點。

分區演算法

Dynamo 對 key 的設計要求是必須可以增量擴張，這就要求一種機制來動態在系統中的一系列節點上進行數據分區。採用一致性哈希演算法來在不同的存儲宿主機上進行負載均衡，一致性哈希演算法此處不再贅述，可以看其他介紹性的文章。Dynamo 中的一致性哈希加入了虛擬節點層已達到更好的均衡效果。

複製

為了實現高可用性和耐用性，Dynamo 將數據複製到多台主機上，其中每個數據項被複制到 N 台主機，N 的值可配。每個鍵，K，被分配到一個 coordinator 節點。coordinator 節點掌控其負責範圍內的複製數據項。除了在本地存儲其範圍內的每個 key 外，協調器節點複製這些 key 到環上順時針方向的 N-1 後繼節點。這樣的結果是，系統中每個節點負責環上的從其自己到第N個前繼節點間的一段區域。在 Figure 2 中，節點 B 除了在本地存儲鍵 K 外，在節點 C 和 D 處複製鍵 K。節點 D 將存儲落在範圍 (A,B], (B,C] 和 (C,D] 上的所有鍵。

數據版本

Dynamo 保證數據的最終一致性，從而允許 update 操作可以非同步地傳播到所有副本。Dynamo 給客戶端返回結果時，所有副本可能還沒有都更新完畢，這會導致 get 操作拿到不同的數據，在一些故障情況下，更新操作可能無法傳播到每個副本導致系統環境中存在不一致。

而作者指出在 Amazon 的應用下，有些需求例如添加購物車等可以容許這種不一致的產生，所以 Dynamo 會為每個變更操作記錄一個新的且不可變的版本。Dynamo 使用 vector clock 來協調某個對象的不同版本間的因果關係。矢量時鐘實際上是一個 [node,counter] 對組成的列表。矢量時鐘是與每個對象的每個版本相關聯。通過查看其向量時鐘，我們可以判斷一個對象的兩個版本是平行分枝或者有因果關係。如果第一個時鐘對象上的計數器在第二個時鐘對象上小於或等於其他所有節點的計數器，那麼第一個是第二個的祖先，可以被人忽略。否則，這兩個變化被認為是衝突，並要求協調。put 操作要求用戶必須指定更新哪個版本，這個版本信息可以由 get 操作返回的 context 得到。

仲裁協議

為了保持副本的一致性，Dynamo 使用 quorum-like 的一致性協議。該協議有兩個關鍵配置值：R 和 W。

1. R 是必須參與一個成功的讀取操作的最少數節點數目。
2. W是必須參加一個成功的寫操作的最少節點數。

設定R和W，使得 R + W > N 產生類似仲裁的系統。在此模型中，一個get/put 操作延時是由最慢的 R/W 副本決定的。基於這個原因，R 和 W 配置通常小於 Ｎ，為客戶提供更小的延時。

當收到對 key 的 put 操作時，協調員生成新版本向量時鐘並在本地寫入新版本。協調員然後將新版本與新的向量時鐘一起，發送給首選列表中排名前 Ｎ 個的可達節點。如果至少 Ｗ-1 個節點返回了響應，那麼這個寫操作被認為是成功的。

同樣，對於一個 get 請求，協調員為 key 從首選列表中排名前 Ｎ 個可達節點處，請求所有現有版本的數據。然後等待 Ｒ 個響應，然後返回結果給客戶端。如果最終協調員收集的數據的多個版本，它返回所有它認為沒有因果關係的版本。不同版本將被協調，並且取代當前的版本，最後寫回。

暫時性故障處理

圖 2 舉例，配置 N = 3。如果寫操作過程中節點 A 無法連接，本來在 A 上的一個副本現在將發送到節點 D 為了保持可用性和耐用性。發送到 D 的副本在其原數據中將有一個 hint，表明哪個節點才是在副本預期的接收者即Ａ。接收暗示副本的節點將數據保存在一個單獨的本地存儲中，它們被定期掃描。在檢測到了 A 復甦後，D 會嘗試發送副本給 A。一旦傳送成功，D 將數據從本地存儲中刪除，且不會降低系統中的副本總數。

永久性故障處理

Dynamo 採用 MerkleTree 更快地檢測副本之間的不一致性，並且減少傳輸的數據量。

結論

論文介紹了 Dynamo，一個高度可用和可擴展的數據存儲系統，被 Amazon 電子商務平台用來存儲許多核心服務的狀態。Dynamo 已經提供了所需的可用性和性能水平，並已成功處理伺服器故障，數據中心故障和網路分區。Dynamo是增量擴展，並允許服務的擁有者根據請求負載按比例增加或減少。Dynamo讓服務的所有者通過調整參數 N、R 和 W 來達到他們渴求的性能，耐用性和一致性的 SLA。