在上一篇文章中，我?guī)懔私饬朔植际酱鎯ο到y(tǒng)的三個要素：顧客、導購和貨架（分布式存儲系統(tǒng)三要素，掌握這些就離成功不遠了）。其中，導購實現(xiàn)了分布式數(shù)據(jù)存儲系統(tǒng)中數(shù)據(jù)索引的功能，包括存儲數(shù)據(jù)時確定存儲位置，以及獲取數(shù)據(jù)時確定數(shù)據(jù)所在位置。

那么，在分布式系統(tǒng)中，具體是如何實現(xiàn)數(shù)據(jù)索引或數(shù)據(jù)分布的呢？目前最常用的方法就是哈希和一致性哈希。

接下來，我們就一起打卡數(shù)據(jù)分布式方式中的哈希與一致性哈希吧。

首先，我們來看一下數(shù)據(jù)分布設計的原則。數(shù)據(jù)分布設計原則是分布式存儲系統(tǒng)設計的基本原則，指導了哈希和一致性哈希方法的選擇和應用。

數(shù)據(jù)分布設計原則

其實，這里的數(shù)據(jù)分布，主要就是數(shù)據(jù)分片。相信你還記得，我在第 24 篇文章中與你分享分布式存儲系統(tǒng)的導購時，已經(jīng)和你提到數(shù)據(jù)分片技術，它解決了確定數(shù)據(jù)位置的問題，并著重與你講述了按照數(shù)據(jù)特征進行劃分的分片方法。今天，我主要與你講解按照數(shù)據(jù)范圍，采用哈希、一致性哈希等對數(shù)據(jù)劃分的方法。

假設，現(xiàn)在有上百 G 數(shù)據(jù)需要進行分布式存儲，也就是要存儲到不同的節(jié)點上。提到這個問題，你可能立刻就會想到很多種方法，比如隨機分布、范圍分布、映射分布等。那么，我們應該如何選擇到底要使用哪種方法呢？

在分布式數(shù)據(jù)存儲系統(tǒng)中，存儲方案選型時，通常會考慮數(shù)據(jù)均勻、數(shù)據(jù)穩(wěn)定和節(jié)點異構性這三個維度。

從數(shù)據(jù)均勻的維度考慮，主要包括兩個方面：

• 不同存儲節(jié)點中存儲的數(shù)據(jù)要盡量均衡，避免讓某一個或某幾個節(jié)點存儲壓力過大，而其他節(jié)點卻幾乎沒什么數(shù)據(jù)。比如，現(xiàn)在有 100G 數(shù)據(jù)，4 個同類型節(jié)點，通常希望數(shù)據(jù)存儲時盡可能均衡，比如每個節(jié)點存儲 25G 數(shù)據(jù)。

• 另外，用戶訪問也要做到均衡，避免出現(xiàn)某一個或某幾個節(jié)點的訪問量很大，但其他節(jié)點卻無人問津的情況。比如，現(xiàn)在有 1000 個請求，對于上述存儲數(shù)據(jù)的 4 個節(jié)點，處理用戶訪問請求盡量均衡，比如每個節(jié)點處理 250 個請求，當然這是非常理想的情況，實際情況下，每個節(jié)點之間相差不太大即可。

從數(shù)據(jù)穩(wěn)定的維度考慮，當存儲節(jié)點出現(xiàn)故障需要移除或者擴增時，數(shù)據(jù)按照分布規(guī)則得到的結果應該盡量保持穩(wěn)定，不要出現(xiàn)大范圍的數(shù)據(jù)遷移。

比如，現(xiàn)有 100G 數(shù)據(jù)，剛開始有 4 個同類型節(jié)點（節(jié)點 1~4），每個節(jié)點存儲 25G 數(shù)據(jù)，現(xiàn)在節(jié)點 2 故障了，也就是說每個節(jié)點需要存儲 100G/3 數(shù)據(jù)。

數(shù)據(jù)穩(wěn)定，就是盡可能只遷移節(jié)點 2 上的數(shù)據(jù)到其他節(jié)點上，而不需要對大范圍或所有數(shù)據(jù)進行遷移存儲。當然，如果有擴展同類型節(jié)點，也是盡可能小范圍遷移數(shù)據(jù)到擴展的節(jié)點上。具體的遷移方法，可以采用下文介紹的一致性哈希方法。

從節(jié)點異構性的維度考慮，不同存儲節(jié)點的硬件配置可能差別很大。比如，有的節(jié)點硬件配置很高，可以存儲大量數(shù)據(jù)，也可以承受更多的請求；但，有的節(jié)點硬件配置就不怎么樣，存儲的數(shù)據(jù)量不能過多，用戶訪問也不能過多。

如果這種差別很大的節(jié)點，分到的數(shù)據(jù)量、用戶訪問量都差不多，本質(zhì)就是一種不均衡。所以，一個好的數(shù)據(jù)分布算法應該考慮節(jié)點異構性。

當然，除了上面這 3 個維度外，我們一般還會考慮隔離故障域、性能穩(wěn)定性等因素。

隔離故障域，是為了保證數(shù)據(jù)的可用和可靠性。比如，我們通常通過備份來實現(xiàn)數(shù)據(jù)的可靠性。但如果每個數(shù)據(jù)及它的備份，被分布到了同一塊硬盤或節(jié)點上，就有點違背備份的初衷了。所以，一個好的數(shù)據(jù)分布算法，應該為每個數(shù)據(jù)映射一組存儲節(jié)點，這些節(jié)點應該盡量在不同的故障域，比如不同機房、不同機架等。

性能穩(wěn)定性是指，數(shù)據(jù)存儲和查詢的效率要有保證，不能因為節(jié)點的添加或者移除，造成存儲或訪問性能的嚴重下降。

了解了數(shù)據(jù)分布的設計原則后，接下來我們再看看主流的數(shù)據(jù)分布式方法，哈希和一致性哈希吧。其中，哈希和一致性哈希是數(shù)據(jù)分布的基礎方法，在不同場景下，數(shù)據(jù)分布設計的原則需要考慮的維度也不一樣。隨著維度的增加，一致性哈希又可進一步演進為帶有限負載的一致性哈希和帶虛擬節(jié)點的一致性哈希方法。

接下來，我們就一起看看這 4 種方法的具體原理和應用場景吧。

數(shù)據(jù)分布方法

哈希是指，將數(shù)據(jù)按照提前規(guī)定好的函數(shù)（哈希函數(shù)）映射到相應的存儲節(jié)點，即進行一個哈希計算，得到的結果就是數(shù)據(jù)應該存儲的節(jié)點。

一致性哈希同樣是采用哈希函數(shù)，進行兩步哈希：

1. 對存儲節(jié)點進行哈希計算，也就是對存儲節(jié)點做哈希映射；
2. 當對數(shù)據(jù)進行存儲或訪問時，首先對數(shù)據(jù)進行映射得到一個結果，然后找到比該結果大的第一個存儲節(jié)點，就是該數(shù)據(jù)應該存儲的地方。我會在下面的內(nèi)容中，與你詳細介紹其中的原理。

總結來講，哈希是一步計算直接得到相應的存儲節(jié)點，而一致性哈希需要兩步才可以找到相應的存儲節(jié)點。這，是不是就是“掐指一算”與“掐指兩算”的事呢？

接下來，我們先一起看看哈希的具體原理吧。

哈希

哈希是一種非常常用的數(shù)據(jù)分布方法，其核心思想是，首先確定一個哈希函數(shù)，然后通過計算得到對應的存儲節(jié)點。我們通過一個具體的例子來看一下吧。

假設，有三個存儲節(jié)點，分別為 Node1、Node2 和 Node3；現(xiàn)有以下數(shù)據(jù)，ID 的范圍為[0,1000]：D0:{ id:100, name:‘a(chǎn)0’}、D1:{ id:200, name:‘a(chǎn)1’} 、D2:{ id:300, name:‘a(chǎn)2’}、D3:{ id:400, name:‘a(chǎn)3’}、D4:{ id:500, name:‘a(chǎn)4’}、D5:{ id:600, name:‘a(chǎn)5’}和 D6:{ id:700, name:‘a(chǎn)6’}。

假設，哈希函數(shù)為“id% 節(jié)點個數(shù)”，通過計算可以得到每個數(shù)據(jù)應該存入的節(jié)點。在這個例子中，哈希函數(shù)是“id%3”，結果為 0 的數(shù)據(jù)存入 Node1、結果為 1 的數(shù)據(jù)存入 Node2、結果為 2 的數(shù)據(jù)存入 Node3。

如圖所示，Node1 將存儲數(shù)據(jù) D2（300%3=0）和 D5（600%3=0），Node2 將存儲數(shù)據(jù) D0（100%3=1）、D3（400%3=1）和 D6（700%3=1），Node3 將存儲數(shù)據(jù) D1（200%3=2）和 D4（500%3=2）。

可以看出，哈希算法的一個優(yōu)點是，只要哈希函數(shù)設置得當，可以很好地保證數(shù)據(jù)均勻性，但有一個較為嚴重的缺點，就是穩(wěn)定性較差。

比如，隨著數(shù)據(jù)量的增加，三個節(jié)點的容量無法再滿足存儲需求了，需要再添加一個節(jié)點。這時，哈希函數(shù)變成了 id%4，原先存儲在那三個節(jié)點的數(shù)據(jù)需要重新計算，然后存入相應節(jié)點，即需要大規(guī)模的數(shù)據(jù)遷移，顯然會降低穩(wěn)定性。

所以，哈希方法適用于同類型節(jié)點且節(jié)點數(shù)量比較固定的場景。目前，Redis 就使用了哈希方法，你可以再回顧下第 10 篇文章“分布式體系結構之非集中式結構：眾生平等”中的相關內(nèi)容。

接下來，我們再看看一致性哈希吧。

一致性哈希

一致性哈希是指將存儲節(jié)點和數(shù)據(jù)都映射到一個首尾相連的哈希環(huán)上，存儲節(jié)點可以根據(jù) IP 地址進行哈希，數(shù)據(jù)通常通過順時針方向尋找的方式，來確定自己所屬的存儲節(jié)點，即從數(shù)據(jù)映射在環(huán)上的位置開始，順時針方向找到的第一個存儲節(jié)點。

我們看看如何用一致性哈希方法，來實現(xiàn)上述案例的數(shù)據(jù)存儲吧。

如圖所示，假設數(shù)據(jù) D0～D7 按照 ID 進行等值映射，即映射值與 ID 值相等，比如數(shù)據(jù) D0 映射到哈希環(huán)上的值為 100，數(shù)據(jù) D1 映射到哈希環(huán)上的值為 200······；同時，假設存儲節(jié)點 Node1、Node2 和 Node3 映射到哈希環(huán)上的值分別為 400、600、900。

按照規(guī)則，D0，D1，D2 和 D3 順時針方向的下一個存儲節(jié)點為 Node1，因此 Node1 將存儲數(shù)據(jù) D0（id = 100）、D1（id = 200）、D2（id = 300）和 D3（id = 400）；同理，Node2 將存取數(shù)據(jù) D4（id = 500）和 D5（id = 600），Node3 將存取數(shù)據(jù) D6（id = 700）。

可以看出，一致性哈希是對哈希方法的改進，在數(shù)據(jù)存儲時采用哈希方式確定存儲位置的基礎上，又增加了一層哈希，也就是在數(shù)據(jù)存儲前，對存儲節(jié)點預先進行了哈希。

這種改進可以很好地解決哈希方法存在的穩(wěn)定性問題。當節(jié)點加入或退出時，僅影響該節(jié)點在哈希環(huán)上順時針相鄰的后繼節(jié)點。比如，當 Node2 發(fā)生故障需要移除時，由于 Node3 是 Node2 順時針方向的后繼節(jié)點，本應存儲到 Node2 的數(shù)據(jù)就會存儲到 Node3 中，其他節(jié)點不會受到影響，因此不會發(fā)生大規(guī)模的數(shù)據(jù)遷移。

所以，一致性哈希方法比較適合同類型節(jié)點、節(jié)點規(guī)模會發(fā)生變化的場景。目前，Cassandra 就使用了一致性哈希方法，你可以再回顧下第 10 篇文章“分布式體系結構之非集中式結構：眾生平等”中的相關內(nèi)容。

一致性哈希方法雖然提升了穩(wěn)定性，但隨之而來的均勻性問題也比較明顯，即對后繼節(jié)點的負載會變大。有節(jié)點退出后，該節(jié)點的后繼節(jié)點需要承擔該節(jié)點的所有負載，如果后繼節(jié)點承受不住，便會出現(xiàn)節(jié)點故障，導致后繼節(jié)點的后繼節(jié)點也面臨同樣的問題。

那么，有沒有更好的方法來解決這個問題呢？

Google 在 2017 年提出了帶有限負載的一致性哈希算法，就對這個問題做了一些優(yōu)化

帶有限負載的一致性哈希

帶有限負載的一致性哈希方法的核心原理是，給每個存儲節(jié)點設置了一個存儲上限值來控制存儲節(jié)點添加或移除造成的數(shù)據(jù)不均勻。當數(shù)據(jù)按照一致性哈希算法找到相應的存儲節(jié)點時，要先判斷該存儲節(jié)點是否達到了存儲上限；如果已經(jīng)達到了上限，則需要繼續(xù)尋找該存儲節(jié)點順時針方向之后的節(jié)點進行存儲。

我們看看如何用帶有限負載的一致性哈希方法，來實現(xiàn)上述案例的數(shù)據(jù)存儲吧。

如圖所示，假設每個存儲節(jié)點設置的上限值為 3，按照一致性哈希算法，當存儲數(shù)據(jù) D3（id = 400）時，會發(fā)現(xiàn)應該存儲到 Node1 中，但 Node1 已經(jīng)存儲了三個數(shù)據(jù) D0（id = 100）、D1（id = 200）和 D2（id = 300），達到了存儲上限，因此會存儲到該節(jié)點順時針方向的下一個節(jié)點 Node2 中。當然，在存儲前，也會先檢查 Node2 是否達到了存儲上限，如果達到了，會繼續(xù)尋找其他節(jié)點。

帶有限負載的一致性哈希方法比較適合同類型節(jié)點、節(jié)點規(guī)模會發(fā)生變化的場景。目前，在 Google Cloud Pub/Sub、HAProxy 中已經(jīng)實現(xiàn)該方法，應用于 Google、Vimeo 等公司的負載均衡項目中。

其實，哈希、一致性哈希、帶有限負載的一致性哈希，都沒有考慮節(jié)點異構性的問題。如果存儲節(jié)點的性能好壞不一，數(shù)據(jù)分布方案還按照這些方法的話，其實還是沒做到數(shù)據(jù)的均勻分布。

接下來，我們再看一種主要針對存儲節(jié)點為異構節(jié)點場景的方法，即帶虛擬節(jié)點的一致性哈希吧。

帶虛擬節(jié)點的一致性哈希

帶虛擬節(jié)點的一致性哈希方法，核心思想是根據(jù)每個節(jié)點的性能，為每個節(jié)點劃分不同數(shù)量的虛擬節(jié)點，并將這些虛擬節(jié)點映射到哈希環(huán)中，然后再按照一致性哈希算法進行數(shù)據(jù)映射和存儲。

假設，Node1 性能最差，Node2 性能一般，Node3 性能最好。以 Node1 的性能作為參考基準，Node2 是 Node1 的 2 倍，Node3 是 Node1 的 3 倍。

因此，Node1 對應一個虛擬節(jié)點 Node1_1，Node2 對應 2 個虛擬節(jié)點 Node2_1 和 Node2_2，Node3 對應 3 個虛擬節(jié)點 Node3_1、Node3_2 和 Node3_3。

假設，虛擬節(jié)點 Node1_1、Node2_1、Node2_2、Node3_1、Node3_2、Node3_3 的哈希值，分別為 100、200、300、400、500、600。

那么，按照帶虛擬節(jié)點的哈希一致性方法， 數(shù)據(jù) D0 和 D6 按順時針方向的下一個虛擬存儲節(jié)點為 Node 1-1，因此節(jié)點 Node1 將會存儲數(shù)據(jù) D0（id = 100）和 D6（id = 700）；同理，Node2 將會存儲數(shù)據(jù) D1（id = 200）和 D2（id = 300），Node3 將會存儲數(shù)據(jù) D3（id = 400）、D4（id = 500）和 D5（id = 600）。

可以看出，帶虛擬節(jié)點的一致性哈希方法比較適合異構節(jié)點、節(jié)點規(guī)模會發(fā)生變化的場景。目前 Memcached 緩存系統(tǒng)實現(xiàn)了該方法，我會在后面文章中與你詳細分析。

這種方法不僅解決了節(jié)點異構性問題，還提高了系統(tǒng)的穩(wěn)定性。當節(jié)點變化時，會有多個節(jié)點共同分擔系統(tǒng)的變化，因此穩(wěn)定性更高。

比如，當某個節(jié)點被移除時，對應該節(jié)點的多個虛擬節(jié)點均會移除，而這些虛擬節(jié)點按順時針方向的下一個虛擬節(jié)點，可能會對應不同的物理節(jié)點，即這些不同的物理節(jié)點共同分擔了節(jié)點變化導致的壓力。

當然，這種方法引入了虛擬節(jié)點，增加了節(jié)點規(guī)模，從而增加了節(jié)點的維護和管理的復雜度，比如新增一個節(jié)點或一個節(jié)點故障時，對應到虛擬節(jié)點構建的哈希環(huán)上需要新增和刪除多個節(jié)點，數(shù)據(jù)的遷移等操作相應地也會很復雜。

四種數(shù)據(jù)分布方法對比

為方便理解與記憶，我再通過一個表格和你對比分析下這四種方法吧。請注意，以下方法之間的對比都是相對的比較，實際性能優(yōu)劣與哈希函數(shù)的設定以及具體的數(shù)據(jù)場景密切相關。

總結

今天，我主要帶你學習了數(shù)據(jù)分布式方法中的哈希與一致性哈希。

首先，我?guī)懔私饬朔植际綌?shù)據(jù)存儲系統(tǒng)中，設計數(shù)據(jù)分布方法需要考慮的原則，主要包括數(shù)據(jù)均勻性、穩(wěn)定性和節(jié)點異構性。

其次，基于數(shù)據(jù)分布設計原則，我為你介紹了哈希、一致性哈希、帶有限負載的一致性哈希和帶虛擬節(jié)點的一致性哈希方法，并以例子進行輔助講解，以便于你理解和學習。

最后，我再通過一張思維導圖來歸納一下今天的核心知識點吧。

加油，相信你通過對本講的學習，對分布式數(shù)據(jù)存儲系統(tǒng)中“導購”的角色有了更深入的理解，對分布式數(shù)據(jù)分布方法的原理，以及如何針對不同場景進行選型有了一定的認知。加油，趕緊行動起來，為你的應用場景選擇一種合適的數(shù)據(jù)分布方法，并實踐起來吧！

在公眾號【架構師修煉】菜單中可自行獲取專屬架構視頻資料，無套路分享，包括不限于 java架構、python系列、人工智能系列、架構系列，以及最新面試、小程序、大前端均無私奉獻，你會感謝我的哈！

下一篇預告：分布式數(shù)據(jù)復制技術