經(jīng)典的一致哈希算法解決了模塊化哈希算法的問(wèn)題，其中哈希函數(shù)(鍵K的位置)與存儲(chǔ)單元的數(shù)量相關(guān)，需要在按比例放大和縮小時(shí)重新分配所有鍵。

# modular hashinghash = key % N of nodes

另一方面，利用一致哈希，哈希功能與存儲(chǔ)節(jié)點(diǎn)的數(shù)量無(wú)關(guān)。這使我們能夠在添加或刪除節(jié)點(diǎn)時(shí)動(dòng)態(tài)地對(duì)數(shù)據(jù)進(jìn)行分區(qū)，從而逐步擴(kuò)展。

哈希空間保持巨大且恒定。它通常被稱為 “環(huán)”。每個(gè)存儲(chǔ)節(jié)點(diǎn)都在此散列空間ring中分配了一個(gè)隨機(jī)位置。

通過(guò)哈希數(shù)據(jù)項(xiàng)的鍵以獲取其在環(huán)上的位置，然后順時(shí)針旋轉(zhuǎn)環(huán)以找到位置大于該項(xiàng)位置的第一個(gè)節(jié)點(diǎn)，將每個(gè)數(shù)據(jù)項(xiàng)分配給一個(gè)節(jié)點(diǎn)。

因此，每個(gè)節(jié)點(diǎn)都負(fù)責(zé)它與其前任節(jié)點(diǎn)之間的環(huán)中區(qū)域。因此，添加或刪除節(jié)點(diǎn)僅需要重新分配屬于其區(qū)域的密鑰，而不需要像模塊化哈希那樣重新分配所有密鑰。

模塊化與一致性哈希

一致性哈希提出了一些挑戰(zhàn)。最明顯的是圍繞環(huán)上節(jié)點(diǎn)位置的隨機(jī)分配，從而導(dǎo)致數(shù)據(jù)和負(fù)載分布不均勻。此外，當(dāng)添加或刪除節(jié)點(diǎn)時(shí)，必須通過(guò)從單個(gè)節(jié)點(diǎn)檢索一組鍵來(lái)復(fù)制一些數(shù)據(jù)，這通常效率低下且速度慢。

受AWS DynamoDB的啟發(fā)，本文討論了經(jīng)典的一致性哈希所帶來(lái)的挑戰(zhàn)，涉及了不同的擴(kuò)展方面，例如可用性，一致性，性能和持久性。此外，它還討論了數(shù)據(jù)版本控制和協(xié)調(diào)，節(jié)點(diǎn)成員資格以及故障檢測(cè)和處理。它只是參考AWS DynamoDB已發(fā)表論文的一般想法和個(gè)人注釋的摘要。DynamoDB是Amazon的高可用性鍵值存儲(chǔ)。

將節(jié)點(diǎn)映射到T令牌

每個(gè)節(jié)點(diǎn)T個(gè)令牌

為了使用經(jīng)典的一致性哈希解決非均勻數(shù)據(jù)和負(fù)載分配問(wèn)題，我們可以將每個(gè)節(jié)點(diǎn)映射到環(huán)中的T個(gè)位置(稱為“令牌”)。添加新節(jié)點(diǎn)時(shí)，會(huì)在環(huán)上為其分配隨機(jī)散布的T位置(令牌)。這具有以下好處：

• 添加節(jié)點(diǎn)后，與現(xiàn)有可用節(jié)點(diǎn)相比，其負(fù)載量大致相等。

• 當(dāng)某個(gè)節(jié)點(diǎn)被刪除或由于故障而變得不可用時(shí)，該節(jié)點(diǎn)處理的負(fù)載將以相反的過(guò)程分配回來(lái)，從而有效地將負(fù)載平均分配到其余可用節(jié)點(diǎn)上。

可用性

— 復(fù)制

跨多個(gè)節(jié)點(diǎn)復(fù)制數(shù)據(jù)對(duì)于實(shí)現(xiàn)高可用性至關(guān)重要。每個(gè)數(shù)據(jù)項(xiàng)都在N個(gè)節(jié)點(diǎn)上復(fù)制。節(jié)點(diǎn)協(xié)調(diào)寫(xiě)請(qǐng)求，負(fù)責(zé)復(fù)制環(huán)中N-1個(gè)順時(shí)針后繼位置(令牌)中屬于其范圍內(nèi)的數(shù)據(jù)項(xiàng)。第一后繼位置可能是由另一個(gè)哈希函數(shù)確定的隨機(jī)性，也可能是跨不同的數(shù)據(jù)中心確定的以提高可用性。

一些有用的定義：N是每個(gè)數(shù)據(jù)項(xiàng)的副本數(shù)，公共值為3；R是要確認(rèn)/回復(fù)讀請(qǐng)求的副本數(shù)；W則是要確認(rèn)/保留寫(xiě)請(qǐng)求的副本數(shù)；S是系統(tǒng)中的節(jié)點(diǎn)數(shù)；T是環(huán)上物理節(jié)點(diǎn)的令牌(位置)數(shù)；密鑰范圍是指環(huán)上與令牌相關(guān)聯(lián)的一組密鑰(令牌由節(jié)點(diǎn)擁有)。

— 始終可寫(xiě)

我們都知道，在分布式系統(tǒng)世界中，網(wǎng)絡(luò)故障和數(shù)據(jù)沖突并不少見(jiàn)，因此無(wú)法同時(shí)實(shí)現(xiàn)高一致性和數(shù)據(jù)可用性。傳統(tǒng)算法會(huì)在故障情況下權(quán)衡數(shù)據(jù)的可用性，因此在絕對(duì)確定數(shù)據(jù)正確之前，使數(shù)據(jù)不可用。

相反，我們可以通過(guò)解決答案的正確性的不確定性來(lái)提高可用性，允許更改傳播到后臺(tái)的副本中，并且允許并發(fā)的，斷開(kāi)的工作。

這種方法的挑戰(zhàn)在于，它可能導(dǎo)致沖突的變化，必須加以檢測(cè)和解決。解決沖突的過(guò)程引入了兩個(gè)問(wèn)題：何時(shí)解決問(wèn)題以及誰(shuí)來(lái)解決。

一致性

— 解決沖突：何時(shí)

在讀取或?qū)懭肫陂g是否應(yīng)解決沖突。許多傳統(tǒng)的數(shù)據(jù)存儲(chǔ)解決了寫(xiě)入期間的沖突，并使讀取的復(fù)雜性保持簡(jiǎn)單。如果數(shù)據(jù)存儲(chǔ)無(wú)法到達(dá)W節(jié)點(diǎn)，則會(huì)以拒絕寫(xiě)入為代價(jià)，從而有效地降低了系統(tǒng)可用性。將沖突解決方案推送至讀取可確保永不拒絕寫(xiě)入。檢測(cè)到數(shù)據(jù)版本沖突時(shí)，不會(huì)拒絕讀取；現(xiàn)在的問(wèn)題是誰(shuí)以及如何解決？

— 解決沖突：誰(shuí)

這可以通過(guò)數(shù)據(jù)存儲(chǔ)本身或應(yīng)用程序客戶端來(lái)完成。

應(yīng)用程序客戶端知道數(shù)據(jù)模式和業(yè)務(wù)邏輯，因此可以決定沖突的解決方案。以購(gòu)物車(chē)示例為例，當(dāng)客戶要將商品添加到購(gòu)物車(chē)(或從購(gòu)物車(chē)中刪除)而最新版本不可用時(shí)，則將商品添加到舊版本(或從舊版本中刪除)，并且將不同版本以后和解。這種變化仍然有意義，應(yīng)該保留。讀取時(shí)，當(dāng)檢測(cè)到?jīng)_突版本時(shí)，應(yīng)用程序客戶端可以選擇“合并”沖突版本并返回單個(gè)統(tǒng)一購(gòu)物車(chē)。

另一方面，如果數(shù)據(jù)存儲(chǔ)區(qū)正在處理沖突，則其選擇相當(dāng)有限，并且只能使用簡(jiǎn)單的策略，例如基于時(shí)間戳的“最后寫(xiě)入獲勝”對(duì)帳邏輯(即，選擇具有最新時(shí)間戳值的項(xiàng)目)作為正確的版本)。維護(hù)客戶會(huì)話信息的服務(wù)就是該用例的一個(gè)很好的例子。

— 解決沖突：如何

版本沖突對(duì)帳

數(shù)據(jù)版本控制使我們能夠檢測(cè)，解決沖突的版本，從而確保數(shù)據(jù)的一致性。節(jié)點(diǎn)執(zhí)行的每次更新都被視為數(shù)據(jù)的新的和不變的版本。一個(gè)版本由(節(jié)點(diǎn)，計(jì)數(shù)器)對(duì)組成，即[(N，c)，…]，其中N是協(xié)調(diào)寫(xiě)請(qǐng)求的節(jié)點(diǎn)。

在大多數(shù)情況下，新版本包含以前的版本，并且數(shù)據(jù)存儲(chǔ)本身可以確定權(quán)威版本。

但是，在出現(xiàn)故障并發(fā)更新的情況下，可能會(huì)發(fā)生版本(并行)分支，從而導(dǎo)致項(xiàng)目的版本沖突。在這種情況下，數(shù)據(jù)的多個(gè)分支折疊為一個(gè)。前面解釋的一個(gè)典型示例是應(yīng)用程序客戶端“合并”客戶購(gòu)物車(chē)的不同版本。

為了說(shuō)明讀寫(xiě)工作流程：

讀

協(xié)調(diào)讀取請(qǐng)求的節(jié)點(diǎn)將從所有N個(gè)節(jié)點(diǎn)中獲取給定項(xiàng)的鍵來(lái)請(qǐng)求該項(xiàng)的現(xiàn)有版本。

然后它將等待N個(gè)節(jié)點(diǎn)中的R個(gè)節(jié)點(diǎn)進(jìn)行回復(fù)。

返回結(jié)果。如果檢測(cè)到版本沖突，特別是數(shù)據(jù)存儲(chǔ)無(wú)法協(xié)調(diào)的并行分支，它將把沖突的項(xiàng)目及其版本上下文信息返回給客戶端。客戶端通過(guò)將分支折疊成一個(gè)版本來(lái)協(xié)調(diào)不同版本后，執(zhí)行更新。

寫(xiě)

協(xié)調(diào)寫(xiě)請(qǐng)求的節(jié)點(diǎn)將在本地存儲(chǔ)它，生成一個(gè)新版本，并在N-1個(gè)位置(令牌)之間復(fù)制它。客戶端必須指定要更新的版本。通過(guò)傳遞從較早的讀取操作獲得的上下文來(lái)完成此操作。

一旦N個(gè)節(jié)點(diǎn)中的W個(gè)節(jié)點(diǎn)作出響應(yīng)，就認(rèn)為寫(xiě)入請(qǐng)求成功。

性能

為讀和寫(xiě)操作提供一致的高性能非常困難，因?yàn)樾阅苁艿絉或W副本中最慢的限制。

一些應(yīng)用需要高水平的性能，并且可以權(quán)衡耐用性與性能(即R = 1，W = 1)。為此，每個(gè)存儲(chǔ)節(jié)點(diǎn)在其主內(nèi)存中維護(hù)一個(gè)對(duì)象緩沖區(qū)。每個(gè)寫(xiě)操作都存儲(chǔ)在緩沖區(qū)中，并定期寫(xiě)入持久性存儲(chǔ)中。每個(gè)讀取操作首先檢查緩沖區(qū)中是否存在請(qǐng)求的密鑰。如果是這樣，則從緩沖區(qū)而不是存儲(chǔ)引擎中讀取對(duì)象。

這將導(dǎo)致延遲降低很多，但要兼顧耐久性。服務(wù)器崩潰可能導(dǎo)致丟失在緩沖區(qū)中排隊(duì)的寫(xiě)操作。

持久性

為了降低持久性風(fēng)險(xiǎn)，處理寫(xiě)請(qǐng)求的協(xié)調(diào)器節(jié)點(diǎn)從N-1個(gè)副本中選擇一個(gè)，將數(shù)據(jù)寫(xiě)到其持久性存儲(chǔ)中。并且由于協(xié)調(diào)器節(jié)點(diǎn)僅等待W響應(yīng)，因此寫(xiě)操作的性能不會(huì)受到影響。

通常，增加成功寫(xiě)入操作時(shí)需要確認(rèn)的節(jié)點(diǎn)數(shù)量可以提高持久性，但同時(shí)也要犧牲可用性。如果沒(méi)有足夠多的活動(dòng)節(jié)點(diǎn)可以答復(fù)，則寫(xiě)入請(qǐng)求可能會(huì)被拒絕。

跨數(shù)據(jù)中心復(fù)制數(shù)據(jù)項(xiàng)以承受因斷電，網(wǎng)絡(luò)故障和自然災(zāi)害導(dǎo)致的故障很重要。

節(jié)點(diǎn)成員資格

節(jié)點(diǎn)之間基于gossip的協(xié)議傳播成員身份更改(節(jié)點(diǎn)加入或離開(kāi)環(huán))并維護(hù)成員身份的最終一致性。

每個(gè)節(jié)點(diǎn)每秒都與隨機(jī)選擇的一個(gè)對(duì)等方聯(lián)系，并且兩個(gè)節(jié)點(diǎn)有效地協(xié)調(diào)了其持久的成員資格更改歷史記錄。

因此，每個(gè)存儲(chǔ)節(jié)點(diǎn)都知道其對(duì)等節(jié)點(diǎn)處理的令牌。這允許每個(gè)節(jié)點(diǎn)直接將密鑰的讀/寫(xiě)操作轉(zhuǎn)發(fā)到正確的節(jié)點(diǎn)集。

這消除了維護(hù)故障狀態(tài)的集中全局一致視圖的需要。

故障檢測(cè)與處理

故障檢測(cè)和處理可以避免失敗的讀取或?qū)懭雵L試，即使在最簡(jiǎn)單的故障條件下，這樣做也會(huì)降低可用性和耐久性。

—臨時(shí)故障：提示切換

如果節(jié)點(diǎn)B不響應(yīng)節(jié)點(diǎn)A的消息，則節(jié)點(diǎn)A可能認(rèn)為節(jié)點(diǎn)B暫時(shí)處于關(guān)閉狀態(tài)。然后，節(jié)點(diǎn)A使用備用節(jié)點(diǎn)執(zhí)行請(qǐng)求；節(jié)點(diǎn)A定期重試B以檢查后者的恢復(fù)情況。

在沒(méi)有客戶端請(qǐng)求來(lái)驅(qū)動(dòng)兩個(gè)節(jié)點(diǎn)之間的流量的情況下，兩個(gè)節(jié)點(diǎn)都不真正需要知道另一個(gè)節(jié)點(diǎn)是否可訪問(wèn)且是否響應(yīng)。

為了處理此問(wèn)題，通常將原本存在于B上的數(shù)據(jù)項(xiàng)現(xiàn)在將發(fā)送到節(jié)點(diǎn)X(B的臨時(shí)副本)。發(fā)送到副本X的數(shù)據(jù)項(xiàng)將在其元數(shù)據(jù)中具有提示，提示哪個(gè)節(jié)點(diǎn)是副本的預(yù)期接收者(在本例中為B)。

接收提示數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)會(huì)將它們保存在單獨(dú)的本地?cái)?shù)據(jù)庫(kù)中，該數(shù)據(jù)庫(kù)會(huì)定期進(jìn)行掃描。在檢測(cè)到B已恢復(fù)后，X將嘗試將數(shù)據(jù)傳遞給B。一旦傳輸成功，X可能會(huì)從其本地存儲(chǔ)中刪除該數(shù)據(jù)項(xiàng)。

使用提示切換，我們確保寫(xiě)操作不會(huì)由于臨時(shí)節(jié)點(diǎn)或網(wǎng)絡(luò)故障而失敗。

—持久故障：副本同步

在某些情況下(例如節(jié)點(diǎn)中斷)，節(jié)點(diǎn)B可能會(huì)長(zhǎng)時(shí)間不可用，并且提示的數(shù)據(jù)項(xiàng)甚至可能無(wú)法返回。為解決此問(wèn)題，使用了使用Merkle樹(shù)的副本同步協(xié)議來(lái)使副本保持同步并檢測(cè)不一致之處。

Merkle樹(shù)遍歷

Merkle樹(shù)是一種哈希樹(shù)，其中的葉子是各個(gè)鍵的值的哈希值。樹(shù)中較高的父節(jié)點(diǎn)是其各自子節(jié)點(diǎn)的哈希。Merkle樹(shù)的主要優(yōu)點(diǎn)是，樹(shù)的每個(gè)分支都可以獨(dú)立且并行地進(jìn)行檢查。此外，Merkle樹(shù)有助于減少需要傳輸?shù)臄?shù)據(jù)量并減少執(zhí)行的磁盤(pán)讀取次數(shù)。兩個(gè)節(jié)點(diǎn)可以遍歷其Merkle樹(shù)，以共同擁有的關(guān)鍵范圍來(lái)確定它們是否存在差異。

每個(gè)節(jié)點(diǎn)為其承載的每個(gè)密鑰范圍(與令牌關(guān)聯(lián)的密鑰集)維護(hù)一個(gè)單獨(dú)的Merkle樹(shù)。這允許節(jié)點(diǎn)比較密鑰范圍內(nèi)的密鑰是否為最新。

回顧

因此，總結(jié)一下添加和刪除節(jié)點(diǎn)以及讀取和寫(xiě)入的工作流程：

添加節(jié)點(diǎn)

• 當(dāng)節(jié)點(diǎn)X加入時(shí)，它會(huì)在環(huán)上選擇其隨機(jī)令牌集。

• 對(duì)于分配給節(jié)點(diǎn)X的每個(gè)密鑰范圍，當(dāng)前可能有許多節(jié)點(diǎn)負(fù)責(zé)處理屬于其令牌范圍內(nèi)的密鑰。由于將密鑰范圍分配給X，因此現(xiàn)有節(jié)點(diǎn)不再需要存儲(chǔ)這些密鑰，這些節(jié)點(diǎn)會(huì)將這些密鑰轉(zhuǎn)移到 X。

• 通過(guò)上面討論的基于八卦的協(xié)議，協(xié)調(diào)成員資格更改歷史并維護(hù)成員資格的最終一致性視圖。

刪除節(jié)點(diǎn)

• 當(dāng)節(jié)點(diǎn)被刪除或由于故障而變得不可用時(shí)，這表示永久離開(kāi)，因此，成員資格更改會(huì)傳播，以通知其他節(jié)點(diǎn)有關(guān)節(jié)點(diǎn)刪除的信息。

• 對(duì)于由已刪除節(jié)點(diǎn)處理的密鑰范圍，它們被隨機(jī)分配到其余節(jié)點(diǎn)，因此，將負(fù)載平均分配到其余可用節(jié)點(diǎn)上。

讀

客戶端請(qǐng)求由負(fù)載均衡器統(tǒng)一分配給環(huán)中的節(jié)點(diǎn)。任何節(jié)點(diǎn)都可以充當(dāng)讀取請(qǐng)求的協(xié)調(diào)器。

協(xié)調(diào)讀取請(qǐng)求的節(jié)點(diǎn)會(huì)將請(qǐng)求發(fā)送到密鑰K的所有N個(gè)節(jié)點(diǎn)，并等待N個(gè)節(jié)點(diǎn)中的R個(gè)。

收集數(shù)據(jù)，確定是否需要對(duì)帳(如前所述)。此過(guò)程稱為“讀取修復(fù)”，因?yàn)樗鼤?huì)修復(fù)錯(cuò)過(guò)了最近更新的副本，并使副本同步協(xié)議不必執(zhí)行此操作。

寫(xiě)

與讀取不同，寫(xiě)請(qǐng)求由帶有密鑰K的數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)副本之一協(xié)調(diào)。如果接收到請(qǐng)求的節(jié)點(diǎn)不是該數(shù)據(jù)項(xiàng)的密鑰的節(jié)點(diǎn)副本，它將把請(qǐng)求轉(zhuǎn)發(fā)到N個(gè)副本之一此限制是由于這些首選節(jié)點(diǎn)還具有創(chuàng)建新版本標(biāo)記的責(zé)任。如果版本控制方案基于物理時(shí)間戳，則任何節(jié)點(diǎn)都可以協(xié)調(diào)寫(xiě)請(qǐng)求。

等待N個(gè)節(jié)點(diǎn)之外的W個(gè)節(jié)點(diǎn)作出響應(yīng)。

應(yīng)用程序客戶端庫(kù)可以是可感知分區(qū)的客戶端庫(kù)，可將請(qǐng)求直接路由到適當(dāng)?shù)膮f(xié)調(diào)器節(jié)點(diǎn)。在這種情況下，我們可以實(shí)現(xiàn)較低的延遲，因?yàn)槿绻?fù)載均衡器將請(qǐng)求分配給隨機(jī)節(jié)點(diǎn)，它會(huì)跳過(guò)額外的網(wǎng)絡(luò)躍點(diǎn)。

挑戰(zhàn)性

由于令牌是在環(huán)上隨機(jī)選擇的，因此范圍的大小會(huì)有所不同。隨著節(jié)點(diǎn)的加入和離開(kāi)系統(tǒng)，令牌集也會(huì)更改，因此范圍也會(huì)更改。因此，“將節(jié)點(diǎn)映射到T令牌”策略提出了以下挑戰(zhàn)：

• 當(dāng)新節(jié)點(diǎn)加入系統(tǒng)時(shí)，在關(guān)鍵范圍內(nèi)處理該數(shù)據(jù)的節(jié)點(diǎn)到新節(jié)點(diǎn)必須掃描其本地持久性存儲(chǔ)以檢索適當(dāng)?shù)臄?shù)據(jù)項(xiàng)集。掃描操作占用大量資源，因此需要在后臺(tái)執(zhí)行，而又不影響客戶性能。此外，以最低優(yōu)先級(jí)運(yùn)行引導(dǎo)任務(wù)會(huì)極大地減慢引導(dǎo)過(guò)程，并在繁忙時(shí)段變得很麻煩。

• 當(dāng)一個(gè)節(jié)點(diǎn)加入或離開(kāi)系統(tǒng)時(shí)，其他一些節(jié)點(diǎn)處理的關(guān)鍵范圍將發(fā)生變化，并且需要重新計(jì)算新范圍的Merkle樹(shù)，這對(duì)于在生產(chǎn)系統(tǒng)上執(zhí)行來(lái)說(shuō)是一項(xiàng)不平凡的操作。

• 最后，由于密鑰范圍的隨機(jī)性，沒(méi)有簡(jiǎn)單的方法可以對(duì)整個(gè)密鑰空間進(jìn)行快照，這使歸檔過(guò)程變得復(fù)雜。在這種情況下，歸檔整個(gè)密鑰空間需要分別從每個(gè)節(jié)點(diǎn)檢索密鑰，這是非常低效的。

這種策略的根本問(wèn)題是數(shù)據(jù)分區(qū)(按令牌劃分)和數(shù)據(jù)放置(存儲(chǔ)節(jié)點(diǎn))是相互依賴的。在不影響數(shù)據(jù)分區(qū)的情況下添加或刪除節(jié)點(diǎn)是不可能的。

將節(jié)點(diǎn)映射到T令牌和相等大小的Q分區(qū)

每個(gè)節(jié)點(diǎn)T個(gè)令牌和相等大小的Q分區(qū)

在這種策略中，將哈希空間劃分為Q個(gè)大小相等的固定分區(qū)(或鍵范圍)，并且為每個(gè)節(jié)點(diǎn)分配T個(gè)隨機(jī)令牌。這里的令牌不決定分區(qū)，因此兩個(gè)連續(xù)的令牌不定義鍵范圍或分區(qū)(它們僅定義環(huán)上的節(jié)點(diǎn)位置)。

通過(guò)這種策略，我們可以獲得以下好處：

• 分區(qū)和分區(qū)放置的分離。數(shù)據(jù)項(xiàng)在給定鍵K的情況下映射到Q個(gè)分區(qū)中的一個(gè)，而負(fù)責(zé)存儲(chǔ)該數(shù)據(jù)項(xiàng)的節(jié)點(diǎn)是通過(guò)從包含鍵K的分區(qū)的末尾順時(shí)針旋轉(zhuǎn)環(huán)來(lái)選擇的，從而找到第一個(gè)令牌的方式，然后找到它的存儲(chǔ)節(jié)點(diǎn)。

• 啟用在運(yùn)行時(shí)更改放置方案的可能性。添加或刪除節(jié)點(diǎn)不會(huì)更改任何數(shù)據(jù)項(xiàng)的分區(qū)(鍵范圍)。

通常將Q設(shè)置為Q > S * T，其中S是系統(tǒng)中的節(jié)點(diǎn)數(shù)。

但是，分配的T令牌的隨機(jī)性以及密鑰范圍仍然是一個(gè)難題。傳遞數(shù)據(jù)的節(jié)點(diǎn)會(huì)掃描其本地持久性存儲(chǔ)，從而導(dǎo)致引導(dǎo)速度變慢；重新計(jì)算Merkle樹(shù)；并沒(méi)有簡(jiǎn)單的快照方法。

將節(jié)點(diǎn)映射到Q / S令牌和相等大小的Q分區(qū)

每個(gè)節(jié)點(diǎn)的Q / S令牌和相等大小的Q分區(qū)

與策略2相似，此策略將哈希空間劃分為Q個(gè)大小相等的分區(qū)，并且數(shù)據(jù)放置與數(shù)據(jù)分區(qū)分離。

此外，為每個(gè)節(jié)點(diǎn)分配Q / S令牌(即T = Q / S)。令牌數(shù)量隨著我們添加或刪除節(jié)點(diǎn)而改變。

當(dāng)節(jié)點(diǎn)離開(kāi)系統(tǒng)時(shí)，其令牌將隨機(jī)分配到其余節(jié)點(diǎn)，以便保留這些屬性。同樣，當(dāng)節(jié)點(diǎn)加入系統(tǒng)時(shí)，它會(huì)以保留這些屬性的方式從系統(tǒng)中的節(jié)點(diǎn)竊取令牌。

此策略具有以下優(yōu)點(diǎn)：

• 更快的引導(dǎo)和恢復(fù)。由于分區(qū)鍵范圍是固定的，因此可以將它們存儲(chǔ)在單獨(dú)的文件中，因此，只需簡(jiǎn)單地傳輸文件，就可以將分區(qū)作為一個(gè)單元重新放置，從而避免了定位特定項(xiàng)目所需的隨機(jī)訪問(wèn)。

• 易于歸檔：分區(qū)文件可以單獨(dú)歸檔。相比之下，與以前的策略相比，令牌是隨機(jī)選擇的，并且對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行歸檔需要分別從各個(gè)節(jié)點(diǎn)檢索密鑰，并且通常效率低下且速度慢。

這種策略的缺點(diǎn)是添加或刪除節(jié)點(diǎn)需要我們保留其屬性(即T = Q / S)。

參考文獻(xiàn)：

• Dynamo：亞馬遜的高可用鍵值存儲(chǔ)

鏈接：

https://medium.com/omarelgabrys-blog/consistent-hashing-beyond-the-basics-525304a12ba

翻譯：奶酪二哈-BKing

The article is only for learning,?if? infringement, please contact BKing8@88.com to delete.

總結(jié)

以上是生活随笔為你收集整理的版本不一致_一致哈希：Beyond the basics的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。