一. 簡介
Dynamo是亞馬遜的一個高可用分布式存儲系統，《Dynamo: Amazon’s Highly Available Key-value Store》一文較長的描述了該系統的整個架構及思考。Dynamo作為亞馬遜的資料存儲系統，最關鍵的在于滿足使用者的需求，保持極高的可用性，因為哪怕幾秒的無法使用也可能造成極大的經濟損失。是以Dynamo的建立初衷為強可用性弱一緻性（最終一緻性）AP模型。
上圖是一個Dynamo技術棧的大緻分布圖，Dynamo使用了衆多技術，包括K-V映射，同步技術，沖突檢測，異步複制，出錯檢測，分區還原等。本文對Dynamo的各層結構進行簡單概括并記錄，下圖是Dynamo中采用的技術。
二. 資料的定位Consistent Hashing
無論是讀寫，我們首先需要的是确認資料的位置，即K-V映射關系的建立。在Dynamo中，采用的是一緻性哈希（Consistent Hashing）實作。其核心思想是一個Key可以映射到多個節點，即多個備份。這種做法有幾個好處：
- 對于用戶端來說，可以就近查詢數值而不需要多條請求遠端資料
- 友善資料丢失時恢複資料
- 利于實作負載均衡
如上圖所示為一緻性哈希采取的環形存儲，箭頭表示key計算出的值得分布。A，B，C是三個不同的節點，政策1是随機計算T個值并存儲，政策2是随機計算并等分存儲，而政策3則是有規律的計算并存儲。Dynamo通過測試發現政策3相對來說有着最佳的負載均衡率，而政策2最差。具體測試結果如下圖所示。
三. 分區一緻性Sloopy Quorum
當我們通過一緻性哈希解決了資料存放位置的問題後，需要解決的問題就在于資料的同步性問題，即共識問題。類似于Paxos，Raft等共識算法，Dynamo采取的是Sloopy Quorum而不是嚴格Quorum。這樣做的原因顯然也是為了高可用性考慮：嚴格Quorum需要大多數人投票同意才可達成共識，而Sloopy Quorum僅需要寫和讀部分節點并比較，核心思想為：
- 使用者選擇一定數量的W/N個節點去寫入
- 使用者從R/N個節點中讀取資料
通常，我們需要保證R + W > N，進而實作至少有一個節點覆寫了讀和寫的操作。關于R和W的選值，其實反應了模型的不同要求：
- R = 1, W = N：快速讀，慢速寫
- R = N, W = 1：快速寫，慢速讀
- R = N / 2, W = N / 2 + 1，适中選擇
在實際中，很少使用N超過3的模型，因為多個備份會極大的增加系統的存儲量，是極大的負擔。是以，一般針對性的會選擇N=3， R, W 在1和2之間變化的模型。比如
- Basho’s Riak采用N = 3, R = 2, W = 2
- Linkedin’s Voldmort采用N = 2 或 3, R = 1, W = 1
- Apache’s Cassandra采用N = 3, R = 1, W = 1
四. 寫入同步 Vector Clock
對于寫入的沖突檢測和融合，Dynamo采取類似vector clock的方式進行處理，在vector clock一文中詳細介紹實作細節和可能存在的問題。下圖為一個簡單的沖突融合過程。
五. 錯誤檢測Gossip算法以及資料恢複的Merkle Tree
gossip是一種用于錯誤檢測的機率性算法，詳細介紹可以見該文。而Merkle Tree，即哈希樹，是常用的統計、檢測用的存儲方式，在資料檢測、下載下傳檢測等多出均有使用。基本原理是采用二分法将檔案分為多個小塊，然後依次求哈希。根節點根據葉子結點求哈希，依次求得。比較的适合，從根節點開始比較，進而避免整個檔案全部拷貝，隻需要針對性的恢複出錯的一小部分即可。
六. 總結
本文大緻分析了Dynamo架構各個方面的實作細節和特點，但是論文原文中還有很多内容是本文沒有涵蓋的，比如其他公司的産品介紹、比如Dynamo開發中獲得的經驗教訓、比如後續優化改進等等，有興趣還是深入研究原文為佳。