相比傳統(tǒng)的集中式存儲(chǔ)系統(tǒng)，Dynamo在設(shè)計(jì)之初就被定位為一個(gè)髙可靠、高可用且多有良好容錯(cuò)性的系統(tǒng)。實(shí)踐表明Dynamo是一種非常成功的分布式存儲(chǔ)架構(gòu)。表3-1列出了Dynamo設(shè)計(jì)時(shí)面臨的主要問(wèn)題及最終采取的解決辦法。
在對(duì)表中內(nèi)容作詳細(xì)介紹之前，先了解Dynamo中的兩個(gè)概念：coordinator和preference list。其中coordinator是執(zhí)行一次讀或?qū)懖僮鞯墓?jié)點(diǎn)，preference list是存儲(chǔ)與某個(gè)特定鍵值相對(duì)應(yīng)的數(shù)據(jù)的節(jié)點(diǎn)列表。一般來(lái)說(shuō)，coordinator是preference list上的第一個(gè)節(jié)點(diǎn)。
數(shù)據(jù)均衡分布的問(wèn)題
Dynamo釆取的是數(shù)據(jù)分布式存儲(chǔ)的架構(gòu)，均勻分布數(shù)據(jù)才可以保證負(fù)載平衡和系統(tǒng)良好的擴(kuò)展性，因此如何在各個(gè)節(jié)點(diǎn)上分布數(shù)據(jù)是非常關(guān)鍵的問(wèn)題。Dynamo使用改進(jìn)后的一致性哈希算法解決這個(gè)問(wèn)題，同時(shí)Dynamo備份了每個(gè)數(shù)據(jù)，以提髙系統(tǒng)的可用性。
1)一致性哈希算法
一致性哈希算法是目前主流的分布式哈希表(Distributed Hash Table, DHT)協(xié)議之一，由麻省理工學(xué)院于1997年提出。一致性哈希算法通過(guò)修正簡(jiǎn)單哈希算法，解決了網(wǎng)絡(luò)中的熱點(diǎn)（HotPot)問(wèn)題，使得DHT可以真正的應(yīng)甩于P2P環(huán)境中。
一致性哈希算法滿(mǎn)足以下四個(gè)要求。
(1)平衡性：哈希算法運(yùn)算后的結(jié)果能充分分散到整個(gè)緩沖空間，提高了緩沖空間的利用率。
(2)單調(diào)性：致性哈希算法保證當(dāng)加入新的緩沖區(qū)域時(shí)，舊的緩沖空間會(huì)被映射到新的空間中，而不會(huì)出現(xiàn)已分配的空間被映射到舊的緩沖集合的其他區(qū)域的情況。這主要是避免在新的節(jié)點(diǎn)加入時(shí)頻繁改動(dòng)原有映射關(guān)系所帶來(lái)的巨大開(kāi)銷(xiāo)。
(3)分散性：在分布式環(huán)境中，不同的終端可能只看見(jiàn)整個(gè)緩沖區(qū)的某個(gè)部分，這樣可能會(huì)導(dǎo)致對(duì)于同一數(shù)據(jù)，不同的終端將其映射到不同的緩沖區(qū)，這顯然降低了數(shù)據(jù)存儲(chǔ)的效率。一致性哈希算法就要求盡量避免和降低分散性。
(4)負(fù)載：既然不同的終端可以將相同的內(nèi)容映射到不同的緩沖區(qū)，那么同一緩沖區(qū)也可能被不同的終端映射成不同的內(nèi)容。一致性哈希算法可以有效避免這種情況的出現(xiàn)。
一致性哈希算法一般分兩步進(jìn)行。首先求出設(shè)備節(jié)點(diǎn)的哈希值，將設(shè)備配置到環(huán)上的一個(gè)點(diǎn)（環(huán)上的每個(gè)點(diǎn)代表一個(gè)哈希值)；接著計(jì)算數(shù)據(jù)的哈希值，按順時(shí)針?lè)较驅(qū)⑵溆成涞江h(huán)上距其最近的節(jié)點(diǎn)，如圖3-2所示。添加新節(jié)點(diǎn)時(shí)，按照上述規(guī)則，調(diào)整相關(guān)數(shù)據(jù)到新的節(jié)點(diǎn)上，如圖3-3所示。刪除節(jié)點(diǎn)和添加節(jié)點(diǎn)過(guò)程相反。
