在上一篇文章中，我?guī)懔私饬朔植际酱鎯ο到y(tǒng)的三個要素：顧客、導(dǎo)購和貨架（分布式存儲系統(tǒng)三要素，掌握這些就離成功不遠(yuǎn)了）。其中，導(dǎo)購實(shí)現(xiàn)了分布式數(shù)據(jù)存儲系統(tǒng)中數(shù)據(jù)索引的功能，包括存儲數(shù)據(jù)時確定存儲位置，以及獲取數(shù)據(jù)時確定數(shù)據(jù)所在位置。
那么，在分布式系統(tǒng)中，具體是如何實(shí)現(xiàn)數(shù)據(jù)索引或數(shù)據(jù)分布的呢？目前最常用的方法就是哈希和一致性哈希。
接下來，我們就一起打卡數(shù)據(jù)分布式方式中的哈希與一致性哈希吧。
首先，我們來看一下數(shù)據(jù)分布設(shè)計(jì)的原則。數(shù)據(jù)分布設(shè)計(jì)原則是分布式存儲系統(tǒng)設(shè)計(jì)的基本原則，指導(dǎo)了哈希和一致性哈希方法的選擇和應(yīng)用。
其實(shí)，這里的數(shù)據(jù)分布，主要就是數(shù)據(jù)分片。相信你還記得，我在第 24 篇文章中與你分享分布式存儲系統(tǒng)的導(dǎo)購時，已經(jīng)和你提到數(shù)據(jù)分片技術(shù)，它解決了確定數(shù)據(jù)位置的問題，并著重與你講述了按照數(shù)據(jù)特征進(jìn)行劃分的分片方法。今天，我主要與你講解按照數(shù)據(jù)范圍，采用哈希、一致性哈希等對數(shù)據(jù)劃分的方法。
假設(shè)，現(xiàn)在有上百 G 數(shù)據(jù)需要進(jìn)行分布式存儲，也就是要存儲到不同的節(jié)點(diǎn)上。提到這個問題，你可能立刻就會想到很多種方法，比如隨機(jī)分布、范圍分布、映射分布等。那么，我們應(yīng)該如何選擇到底要使用哪種方法呢？
在分布式數(shù)據(jù)存儲系統(tǒng)中，存儲方案選型時，通常會考慮數(shù)據(jù)均勻、數(shù)據(jù)穩(wěn)定和節(jié)點(diǎn)異構(gòu)性這三個維度。
從數(shù)據(jù)均勻的維度考慮，主要包括兩個方面：
從數(shù)據(jù)穩(wěn)定的維度考慮，當(dāng)存儲節(jié)點(diǎn)出現(xiàn)故障需要移除或者擴(kuò)增時，數(shù)據(jù)按照分布規(guī)則得到的結(jié)果應(yīng)該盡量保持穩(wěn)定，不要出現(xiàn)大范圍的數(shù)據(jù)遷移。
比如，現(xiàn)有 100G 數(shù)據(jù)，剛開始有 4 個同類型節(jié)點(diǎn)（節(jié)點(diǎn) 1~4），每個節(jié)點(diǎn)存儲 25G 數(shù)據(jù)，現(xiàn)在節(jié)點(diǎn) 2 故障了，也就是說每個節(jié)點(diǎn)需要存儲 100G/3 數(shù)據(jù)。
數(shù)據(jù)穩(wěn)定，就是盡可能只遷移節(jié)點(diǎn) 2 上的數(shù)據(jù)到其他節(jié)點(diǎn)上，而不需要對大范圍或所有數(shù)據(jù)進(jìn)行遷移存儲。當(dāng)然，如果有擴(kuò)展同類型節(jié)點(diǎn)，也是盡可能小范圍遷移數(shù)據(jù)到擴(kuò)展的節(jié)點(diǎn)上。具體的遷移方法，可以采用下文介紹的一致性哈希方法。
從節(jié)點(diǎn)異構(gòu)性的維度考慮，不同存儲節(jié)點(diǎn)的硬件配置可能差別很大。比如，有的節(jié)點(diǎn)硬件配置很高，可以存儲大量數(shù)據(jù)，也可以承受更多的請求；但，有的節(jié)點(diǎn)硬件配置就不怎么樣，存儲的數(shù)據(jù)量不能過多，用戶訪問也不能過多。
如果這種差別很大的節(jié)點(diǎn)，分到的數(shù)據(jù)量、用戶訪問量都差不多，本質(zhì)就是一種不均衡。所以，一個好的數(shù)據(jù)分布算法應(yīng)該考慮節(jié)點(diǎn)異構(gòu)性。
當(dāng)然，除了上面這 3 個維度外，我們一般還會考慮隔離故障域、性能穩(wěn)定性等因素。
隔離故障域，是為了保證數(shù)據(jù)的可用和可靠性。比如，我們通常通過備份來實(shí)現(xiàn)數(shù)據(jù)的可靠性。但如果每個數(shù)據(jù)及它的備份，被分布到了同一塊硬盤或節(jié)點(diǎn)上，就有點(diǎn)違背備份的初衷了。所以，一個好的數(shù)據(jù)分布算法，應(yīng)該為每個數(shù)據(jù)映射一組存儲節(jié)點(diǎn)，這些節(jié)點(diǎn)應(yīng)該盡量在不同的故障域，比如不同機(jī)房、不同機(jī)架等。
性能穩(wěn)定性是指，數(shù)據(jù)存儲和查詢的效率要有保證，不能因?yàn)楣?jié)點(diǎn)的添加或者移除，造成存儲或訪問性能的嚴(yán)重下降。
了解了數(shù)據(jù)分布的設(shè)計(jì)原則后，接下來我們再看看主流的數(shù)據(jù)分布式方法，哈希和一致性哈希吧。其中，哈希和一致性哈希是數(shù)據(jù)分布的基礎(chǔ)方法，在不同場景下，數(shù)據(jù)分布設(shè)計(jì)的原則需要考慮的維度也不一樣。隨著維度的增加，一致性哈希又可進(jìn)一步演進(jìn)為帶有限負(fù)載的一致性哈希和帶虛擬節(jié)點(diǎn)的一致性哈希方法。
接下來，我們就一起看看這 4 種方法的具體原理和應(yīng)用場景吧。
哈希是指，將數(shù)據(jù)按照提前規(guī)定好的函數(shù)（哈希函數(shù)）映射到相應(yīng)的存儲節(jié)點(diǎn)，即進(jìn)行一個哈希計(jì)算，得到的結(jié)果就是數(shù)據(jù)應(yīng)該存儲的節(jié)點(diǎn)。
一致性哈希同樣是采用哈希函數(shù)，進(jìn)行兩步哈希：
總結(jié)來講，哈希是一步計(jì)算直接得到相應(yīng)的存儲節(jié)點(diǎn)，而一致性哈希需要兩步才可以找到相應(yīng)的存儲節(jié)點(diǎn)。這，是不是就是“掐指一算”與“掐指兩算”的事呢？
接下來，我們先一起看看哈希的具體原理吧。
哈希
哈希是一種非常常用的數(shù)據(jù)分布方法，其核心思想是，首先確定一個哈希函數(shù)，然后通過計(jì)算得到對應(yīng)的存儲節(jié)點(diǎn)。我們通過一個具體的例子來看一下吧。
假設(shè)，有三個存儲節(jié)點(diǎn)，分別為 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è)，哈希函數(shù)為“id% 節(jié)點(diǎn)個數(shù)”，通過計(jì)算可以得到每個數(shù)據(jù)應(yīng)該存入的節(jié)點(diǎn)。在這個例子中，哈希函數(shù)是“id%3”，結(jié)果為 0 的數(shù)據(jù)存入 Node1、結(jié)果為 1 的數(shù)據(jù)存入 Node2、結(jié)果為 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)點(diǎn)是，只要哈希函數(shù)設(shè)置得當(dāng)，可以很好地保證數(shù)據(jù)均勻性，但有一個較為嚴(yán)重的缺點(diǎn)，就是穩(wěn)定性較差。
比如，隨著數(shù)據(jù)量的增加，三個節(jié)點(diǎn)的容量無法再滿足存儲需求了，需要再添加一個節(jié)點(diǎn)。這時，哈希函數(shù)變成了 id%4，原先存儲在那三個節(jié)點(diǎn)的數(shù)據(jù)需要重新計(jì)算，然后存入相應(yīng)節(jié)點(diǎn)，即需要大規(guī)模的數(shù)據(jù)遷移，顯然會降低穩(wěn)定性。
所以，哈希方法適用于同類型節(jié)點(diǎn)且節(jié)點(diǎn)數(shù)量比較固定的場景。目前，Redis 就使用了哈希方法，你可以再回顧下第 10 篇文章“分布式體系結(jié)構(gòu)之非集中式結(jié)構(gòu)：眾生平等”中的相關(guān)內(nèi)容。
接下來，我們再看看一致性哈希吧。
一致性哈希
一致性哈希是指將存儲節(jié)點(diǎn)和數(shù)據(jù)都映射到一個首尾相連的哈希環(huán)上，存儲節(jié)點(diǎn)可以根據(jù) IP 地址進(jìn)行哈希，數(shù)據(jù)通常通過順時針方向?qū)ふ业姆绞?，來確定自己所屬的存儲節(jié)點(diǎn)，即從數(shù)據(jù)映射在環(huán)上的位置開始，順時針方向找到的第一個存儲節(jié)點(diǎn)。
我們看看如何用一致性哈希方法，來實(shí)現(xiàn)上述案例的數(shù)據(jù)存儲吧。
如圖所示，假設(shè)數(shù)據(jù) D0～D7 按照 ID 進(jìn)行等值映射，即映射值與 ID 值相等，比如數(shù)據(jù) D0 映射到哈希環(huán)上的值為 100，數(shù)據(jù) D1 映射到哈希環(huán)上的值為 200······；同時，假設(shè)存儲節(jié)點(diǎn) Node1、Node2 和 Node3 映射到哈希環(huán)上的值分別為 400、600、900。
按照規(guī)則，D0，D1，D2 和 D3 順時針方向的下一個存儲節(jié)點(diǎn)為 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）。
可以看出，一致性哈希是對哈希方法的改進(jìn)，在數(shù)據(jù)存儲時采用哈希方式確定存儲位置的基礎(chǔ)上，又增加了一層哈希，也就是在數(shù)據(jù)存儲前，對存儲節(jié)點(diǎn)預(yù)先進(jìn)行了哈希。
這種改進(jìn)可以很好地解決哈希方法存在的穩(wěn)定性問題。當(dāng)節(jié)點(diǎn)加入或退出時，僅影響該節(jié)點(diǎn)在哈希環(huán)上順時針相鄰的后繼節(jié)點(diǎn)。比如，當(dāng) Node2 發(fā)生故障需要移除時，由于 Node3 是 Node2 順時針方向的后繼節(jié)點(diǎn)，本應(yīng)存儲到 Node2 的數(shù)據(jù)就會存儲到 Node3 中，其他節(jié)點(diǎn)不會受到影響，因此不會發(fā)生大規(guī)模的數(shù)據(jù)遷移。
所以，一致性哈希方法比較適合同類型節(jié)點(diǎn)、節(jié)點(diǎn)規(guī)模會發(fā)生變化的場景。目前，Cassandra 就使用了一致性哈希方法，你可以再回顧下第 10 篇文章“分布式體系結(jié)構(gòu)之非集中式結(jié)構(gòu)：眾生平等”中的相關(guān)內(nèi)容。
一致性哈希方法雖然提升了穩(wěn)定性，但隨之而來的均勻性問題也比較明顯，即對后繼節(jié)點(diǎn)的負(fù)載會變大。有節(jié)點(diǎn)退出后，該節(jié)點(diǎn)的后繼節(jié)點(diǎn)需要承擔(dān)該節(jié)點(diǎn)的所有負(fù)載，如果后繼節(jié)點(diǎn)承受不住，便會出現(xiàn)節(jié)點(diǎn)故障，導(dǎo)致后繼節(jié)點(diǎn)的后繼節(jié)點(diǎn)也面臨同樣的問題。
那么，有沒有更好的方法來解決這個問題呢？
Google 在 2017 年提出了帶有限負(fù)載的一致性哈希算法，就對這個問題做了一些優(yōu)化
帶有限負(fù)載的一致性哈希方法的核心原理是，給每個存儲節(jié)點(diǎn)設(shè)置了一個存儲上限值來控制存儲節(jié)點(diǎn)添加或移除造成的數(shù)據(jù)不均勻。當(dāng)數(shù)據(jù)按照一致性哈希算法找到相應(yīng)的存儲節(jié)點(diǎn)時，要先判斷該存儲節(jié)點(diǎn)是否達(dá)到了存儲上限；如果已經(jīng)達(dá)到了上限，則需要繼續(xù)尋找該存儲節(jié)點(diǎn)順時針方向之后的節(jié)點(diǎn)進(jìn)行存儲。
我們看看如何用帶有限負(fù)載的一致性哈希方法，來實(shí)現(xiàn)上述案例的數(shù)據(jù)存儲吧。
如圖所示，假設(shè)每個存儲節(jié)點(diǎn)設(shè)置的上限值為 3，按照一致性哈希算法，當(dāng)存儲數(shù)據(jù) D3（id = 400）時，會發(fā)現(xiàn)應(yīng)該存儲到 Node1 中，但 Node1 已經(jīng)存儲了三個數(shù)據(jù) D0（id = 100）、D1（id = 200）和 D2（id = 300），達(dá)到了存儲上限，因此會存儲到該節(jié)點(diǎn)順時針方向的下一個節(jié)點(diǎn) Node2 中。當(dāng)然，在存儲前，也會先檢查 Node2 是否達(dá)到了存儲上限，如果達(dá)到了，會繼續(xù)尋找其他節(jié)點(diǎn)。
帶有限負(fù)載的一致性哈希方法比較適合同類型節(jié)點(diǎn)、節(jié)點(diǎn)規(guī)模會發(fā)生變化的場景。目前，在 Google Cloud Pub/Sub、HAProxy 中已經(jīng)實(shí)現(xiàn)該方法，應(yīng)用于 Google、Vimeo 等公司的負(fù)載均衡項(xiàng)目中。
其實(shí)，哈希、一致性哈希、帶有限負(fù)載的一致性哈希，都沒有考慮節(jié)點(diǎn)異構(gòu)性的問題。如果存儲節(jié)點(diǎn)的性能好壞不一，數(shù)據(jù)分布方案還按照這些方法的話，其實(shí)還是沒做到數(shù)據(jù)的均勻分布。
接下來，我們再看一種主要針對存儲節(jié)點(diǎn)為異構(gòu)節(jié)點(diǎn)場景的方法，即帶虛擬節(jié)點(diǎn)的一致性哈希吧。
帶虛擬節(jié)點(diǎn)的一致性哈希方法，核心思想是根據(jù)每個節(jié)點(diǎn)的性能，為每個節(jié)點(diǎn)劃分不同數(shù)量的虛擬節(jié)點(diǎn)，并將這些虛擬節(jié)點(diǎn)映射到哈希環(huán)中，然后再按照一致性哈希算法進(jìn)行數(shù)據(jù)映射和存儲。
假設(shè)，Node1 性能最差，Node2 性能一般，Node3 性能最好。以 Node1 的性能作為參考基準(zhǔn)，Node2 是 Node1 的 2 倍，Node3 是 Node1 的 3 倍。
因此，Node1 對應(yīng)一個虛擬節(jié)點(diǎn) Node1_1，Node2 對應(yīng) 2 個虛擬節(jié)點(diǎn) Node2_1 和 Node2_2，Node3 對應(yīng) 3 個虛擬節(jié)點(diǎn) Node3_1、Node3_2 和 Node3_3。
假設(shè)，虛擬節(jié)點(diǎn) Node1_1、Node2_1、Node2_2、Node3_1、Node3_2、Node3_3 的哈希值，分別為 100、200、300、400、500、600。
那么，按照帶虛擬節(jié)點(diǎn)的哈希一致性方法， 數(shù)據(jù) D0 和 D6 按順時針方向的下一個虛擬存儲節(jié)點(diǎn)為 Node 1-1，因此節(jié)點(diǎn) 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é)點(diǎn)的一致性哈希方法比較適合異構(gòu)節(jié)點(diǎn)、節(jié)點(diǎn)規(guī)模會發(fā)生變化的場景。目前 Memcached 緩存系統(tǒng)實(shí)現(xiàn)了該方法，我會在后面文章中與你詳細(xì)分析。
這種方法不僅解決了節(jié)點(diǎn)異構(gòu)性問題，還提高了系統(tǒng)的穩(wěn)定性。當(dāng)節(jié)點(diǎn)變化時，會有多個節(jié)點(diǎn)共同分擔(dān)系統(tǒng)的變化，因此穩(wěn)定性更高。
比如，當(dāng)某個節(jié)點(diǎn)被移除時，對應(yīng)該節(jié)點(diǎn)的多個虛擬節(jié)點(diǎn)均會移除，而這些虛擬節(jié)點(diǎn)按順時針方向的下一個虛擬節(jié)點(diǎn)，可能會對應(yīng)不同的物理節(jié)點(diǎn)，即這些不同的物理節(jié)點(diǎn)共同分擔(dān)了節(jié)點(diǎn)變化導(dǎo)致的壓力。
當(dāng)然，這種方法引入了虛擬節(jié)點(diǎn)，增加了節(jié)點(diǎn)規(guī)模，從而增加了節(jié)點(diǎn)的維護(hù)和管理的復(fù)雜度，比如新增一個節(jié)點(diǎn)或一個節(jié)點(diǎn)故障時，對應(yīng)到虛擬節(jié)點(diǎn)構(gòu)建的哈希環(huán)上需要新增和刪除多個節(jié)點(diǎn)，數(shù)據(jù)的遷移等操作相應(yīng)地也會很復(fù)雜。
為方便理解與記憶，我再通過一個表格和你對比分析下這四種方法吧。請注意，以下方法之間的對比都是相對的比較，實(shí)際性能優(yōu)劣與哈希函數(shù)的設(shè)定以及具體的數(shù)據(jù)場景密切相關(guān)。
今天，我主要帶你學(xué)習(xí)了數(shù)據(jù)分布式方法中的哈希與一致性哈希。
首先，我?guī)懔私饬朔植际綌?shù)據(jù)存儲系統(tǒng)中，設(shè)計(jì)數(shù)據(jù)分布方法需要考慮的原則，主要包括數(shù)據(jù)均勻性、穩(wěn)定性和節(jié)點(diǎn)異構(gòu)性。
其次，基于數(shù)據(jù)分布設(shè)計(jì)原則，我為你介紹了哈希、一致性哈希、帶有限負(fù)載的一致性哈希和帶虛擬節(jié)點(diǎn)的一致性哈希方法，并以例子進(jìn)行輔助講解，以便于你理解和學(xué)習(xí)。
最后，我再通過一張思維導(dǎo)圖來歸納一下今天的核心知識點(diǎn)吧。
加油，相信你通過對本講的學(xué)習(xí)，對分布式數(shù)據(jù)存儲系統(tǒng)中“導(dǎo)購”的角色有了更深入的理解，對分布式數(shù)據(jù)分布方法的原理，以及如何針對不同場景進(jìn)行選型有了一定的認(rèn)知。加油，趕緊行動起來，為你的應(yīng)用場景選擇一種合適的數(shù)據(jù)分布方法，并實(shí)踐起來吧！
在公眾號【架構(gòu)師修煉】菜單中可自行獲取專屬架構(gòu)視頻資料，無套路分享，包括不限于 java架構(gòu)、python系列、人工智能系列、架構(gòu)系列，以及最新面試、小程序、大前端均無私奉獻(xiàn)，你會感謝我的哈！
下一篇預(yù)告：分布式數(shù)據(jù)復(fù)制技術(shù)
