Dynamo采用一致性哈希算法的主要原因是每個節(jié)點只需處理落在它和它的前驅(qū)節(jié)點之間的數(shù)據(jù)，這樣增/刪節(jié)點時系統(tǒng)振蕩較小。一致性哈希函數(shù)是一種隨機性的函數(shù)，在節(jié)點數(shù)量較少的情況下很可能造成環(huán)上節(jié)點分布的不均勻，導(dǎo)致負載不均勻；在選擇節(jié)點位置時，并沒有考慮環(huán)上不同節(jié)點的性能差異。為了解決這些問題，Amazon在Dynamo中引入了虛擬節(jié)點的概念。每個虛擬節(jié)點都屬于某一個實際的物理節(jié)點，一個物理節(jié)點根據(jù)其性能的差異可能擁有一個或多個虛擬節(jié)點。每個虛擬節(jié)點能力基本相當，并隨機分布在哈?？臻g中。存儲時，數(shù)據(jù)按照哈希值落到某個虡擬節(jié)點負責的區(qū)域，然后被存儲在該虛擬節(jié)點所對應(yīng)的物理節(jié)點中，如圖3-4所示。
假設(shè)將一個值域為2^n 的Hash環(huán)劃分成2個等份，每個等份稱做一個數(shù)據(jù)分區(qū) (Partiti0n),有S個虛擬節(jié)點，并且滿足Q〉〉S，則每個虛擬節(jié)點對應(yīng)的分區(qū)數(shù)V=Q/S，將兩個虛擬節(jié)點之間的所有分區(qū)稱為一個鍵值區(qū)間，如圖3-5所示。這種數(shù)據(jù)分區(qū)和等份存儲的好處在于：首先，數(shù)據(jù)以分區(qū)為單元進行存儲，實現(xiàn)了數(shù)據(jù)劃分（Datj Partitioning)和數(shù)據(jù)存儲（Data Placement)的分離。在增/刪節(jié)點時，只是引起鍵值區(qū)間的變化，不需要改變相應(yīng)節(jié)點內(nèi)數(shù)據(jù)的存儲位置，對于存儲大量數(shù)據(jù)的系統(tǒng)是非常有效的。其次，當刪除節(jié)點時，該節(jié)點的負載會比較均勻地分攤到其他節(jié)點，因為該節(jié)點所對應(yīng)的虛擬節(jié)點比較均勻地分布在環(huán)上；同樣的道理，當添加新節(jié)點時，其他虛擬節(jié)點的負載會比較均勻地轉(zhuǎn)移到新節(jié)點上。另外，通過虛擬節(jié)點和物理節(jié)點多對一的配置可以實現(xiàn)處理能力權(quán)重配置，可以解決基本一致性哈希算法未考慮節(jié)點處理能力差異的問題。注意，隨著節(jié)點的增加，特別是Q接近S后，Dynamo的性能會急劇下降，因此在設(shè)計之初，要選擇好Q值。
數(shù)據(jù)備份
當數(shù)據(jù)被均勻存儲到環(huán)上各節(jié)點后，0ynamo將冗余存儲數(shù)據(jù)（備份數(shù)據(jù)）。設(shè)N代表每份數(shù)據(jù)保存在系統(tǒng)中的副本數(shù)，考慮到存在節(jié)點失效的情況，preference list大于N并且只存儲實際的物理節(jié)點而不存儲虛擬節(jié)點。Dynamo中N—般取3,節(jié)點的數(shù)據(jù)副本備份在環(huán)上它的順時針方向后繼節(jié)點中。例如，圖3-5中鍵k對應(yīng)的數(shù)據(jù)存儲在虛擬節(jié)點A中，而它的數(shù)據(jù)副本將按順時針方向備份在虛擬節(jié)點B、C上。根據(jù)這個規(guī)定，上面提到的鍵值區(qū)間實際存儲的就是它和它的前個前驅(qū)鍵值運間的數(shù)據(jù)。這種設(shè)計提高了系統(tǒng)的可用性。由于在寫操作的同時進行副本備份，會使用戶每次的寫操作時延變長，因此Dynamo在寫操作時采用了優(yōu)化的方式，寫操作時，保證一個副本必須寫入硬盤，其他副本只要寫入節(jié)點的內(nèi)存即返回寫成功。這樣既保證了副本的數(shù)量又減少了時延。實際上Amazon提供了更高的可靠性保證，它可以保證相鄰的節(jié)點分別位于不同地區(qū)區(qū)域，即使某個數(shù)據(jù)中心由于自然災(zāi)害或斷電的原因整體癱瘓，仍可以保證在世界上其他數(shù)據(jù)中心中保存有數(shù)據(jù)的備份。這里就有一個非常重要的問題，如何進行節(jié)點分布，保證相鄰節(jié)點位于不同的數(shù)據(jù)中心，有興趣的讀者可以自己思考一下。
