相比傳統的集中式存儲系統,Dynamo在設計之初就被定位為一個髙可靠、高可用且多有良好容錯性的系統。實踐表明Dynamo是一種非常成功的分布式存儲架構。表3-1列出了Dynamo設計時面臨的主要問題及最終采取的解決辦法。

在對表中內容作詳細介紹之前,先了解Dynamo中的兩個概念:coordinator和preference list。其中coordinator是執行一次讀或寫操作的節點,preference list是存儲與某個特定鍵值相對應的數據的節點列表。一般來說,coordinator是preference list上的第一個節點。
數據均衡分布的問題
Dynamo釆取的是數據分布式存儲的架構,均勻分布數據才可以保證負載平衡和系統良好的擴展性,因此如何在各個節點上分布數據是非常關鍵的問題。Dynamo使用改進后的一致性哈希算法解決這個問題,同時Dynamo備份了每個數據,以提髙系統的可用性。
1)一致性哈希算法
一致性哈希算法是目前主流的分布式哈希表(Distributed Hash Table, DHT)協議之一,由麻省理工學院于1997年提出。一致性哈希算法通過修正簡單哈希算法,解決了網絡中的熱點(HotPot)問題,使得DHT可以真正的應甩于P2P環境中。
一致性哈希算法滿足以下四個要求。
(1)平衡性:哈希算法運算后的結果能充分分散到整個緩沖空間,提高了緩沖空間的利用率。
(2)單調性:致性哈希算法保證當加入新的緩沖區域時,舊的緩沖空間會被映射到新的空間中,而不會出現已分配的空間被映射到舊的緩沖集合的其他區域的情況。這主要是避免在新的節點加入時頻繁改動原有映射關系所帶來的巨大開銷。
(3)分散性:在分布式環境中,不同的終端可能只看見整個緩沖區的某個部分,這樣可能會導致對于同一數據,不同的終端將其映射到不同的緩沖區,這顯然降低了數據存儲的效率。一致性哈希算法就要求盡量避免和降低分散性。
(4)負載:既然不同的終端可以將相同的內容映射到不同的緩沖區,那么同一緩沖區也可能被不同的終端映射成不同的內容。一致性哈希算法可以有效避免這種情況的出現。
一致性哈希算法一般分兩步進行。首先求出設備節點的哈希值,將設備配置到環上的一個點(環上的每個點代表一個哈希值);接著計算數據的哈希值,按順時針方向將其映射到環上距其最近的節點,如圖3-2所示。添加新節點時,按照上述規則,調整相關數據到新的節點上,如圖3-3所示。刪除節點和添加節點過程相反。
