如何理解分布式系統(tǒng)中的哈希算法

這篇文章主要介紹“如何理解分布式系統(tǒng)中的哈希算法”，在日常操作中，相信很多人在如何理解分布式系統(tǒng)中的哈希算法問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”如何理解分布式系統(tǒng)中的哈希算法”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

哈希

Hash也稱(chēng)散列、哈希，原理是把任意長(zhǎng)度的字符串當(dāng)作輸入，然后通過(guò)Hash算法變成固定長(zhǎng)度輸出。Hash是一個(gè)映射的過(guò)程，因此是一定會(huì)產(chǎn)生沖突的，一般使用鏈地址法，開(kāi)放尋址法等方法來(lái)解決hash沖突。

分布式下的哈希

在分布式的情景下，為了解決數(shù)據(jù)和請(qǐng)求的定向問(wèn)題，我們也會(huì)常常使用到哈希算法。接下來(lái)，就會(huì)介紹幾種常常在分布式環(huán)境下運(yùn)用的hash算法。

普通哈希

哪怕是在分布式的環(huán)境下，我們也可以使用最簡(jiǎn)單的hash算法，通過(guò)設(shè)定好每臺(tái)服務(wù)器對(duì)應(yīng)的結(jié)果值，在請(qǐng)求或者數(shù)據(jù)進(jìn)來(lái)時(shí)進(jìn)行計(jì)算，將數(shù)據(jù)分別映射到相應(yīng)的服務(wù)器上，由于計(jì)算規(guī)則是一致的，因此無(wú)論進(jìn)行多少次的計(jì)算，數(shù)據(jù)的映射是不會(huì)進(jìn)行變化的。

這種普通的哈希的方式優(yōu)缺點(diǎn)分明，優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，清晰明了。缺點(diǎn)是由于分布式系統(tǒng)中的節(jié)點(diǎn)充滿了不確定性，可能會(huì)縮容或者擴(kuò)容或者節(jié)點(diǎn)宕機(jī)，如果在這些情況下，意味著哈希的映射將會(huì)發(fā)生變化，同時(shí)之前的那些映射的數(shù)據(jù)需要進(jìn)行遷移，以便之后能夠正確的訪問(wèn)。而這種方式的哈希在這種情況下產(chǎn)生的數(shù)據(jù)遷移量將會(huì)是非常巨大的。

上圖是一個(gè)普通的分布式系統(tǒng)的哈希映射關(guān)系，3臺(tái)服務(wù)器分別接受哈希值為0，1，2的請(qǐng)求（一般為計(jì)算%2的值）。

于是當(dāng)我們新增一臺(tái)服務(wù)器之后，原本3臺(tái)服務(wù)器變成了4臺(tái)，哈希映射需要隨之修改，大量的數(shù)據(jù)需要遷移。

一致性哈希

一致性哈希是為了解決之前說(shuō)到的哈希造成的大量數(shù)據(jù)遷移的問(wèn)題。

一致性哈希和普通哈希相比，同樣是有一定的映射關(guān)系的，但是不同的是，我們會(huì)在開(kāi)始創(chuàng)建一個(gè)哈希環(huán)，在環(huán)上分布著大量的節(jié)點(diǎn)值，一般的范圍為0 ~ 2^32-1

之后我們會(huì)根據(jù)一定的規(guī)則，將服務(wù)器節(jié)點(diǎn)落在環(huán)上，如下圖

之后的邏輯就比較簡(jiǎn)單了，當(dāng)請(qǐng)求發(fā)往服務(wù)器后，經(jīng)過(guò)計(jì)算找到其在環(huán)上的對(duì)應(yīng)位置，然后檢查該位置上是否有對(duì)應(yīng)服務(wù)器節(jié)點(diǎn)，如果有就將請(qǐng)求轉(zhuǎn)發(fā)過(guò)去，如果沒(méi)有就沿著哈希環(huán)順時(shí)針尋找，直到找到節(jié)點(diǎn)位置。

這樣設(shè)計(jì)的好處是顯而易見(jiàn)的，如果我們需要新增或者刪除節(jié)點(diǎn)的時(shí)候，每次只會(huì)影響至多2個(gè)節(jié)點(diǎn)的數(shù)據(jù)，相比較之前的普通哈希，消耗顯然是更少的。并且當(dāng)某些服務(wù)器因故障突然宕機(jī)的時(shí)候，請(qǐng)求也可以順延到下個(gè)節(jié)點(diǎn)進(jìn)行處理。

節(jié)點(diǎn)分布不均問(wèn)題

一致性哈希的特點(diǎn)決定了如果節(jié)點(diǎn)分布的不夠均勻會(huì)導(dǎo)致其中部分節(jié)點(diǎn)壓力過(guò)大，而部分節(jié)點(diǎn)有很多資源的空閑。如下圖

圖中的A，B節(jié)點(diǎn)顯然是不均衡的，請(qǐng)求會(huì)更多地發(fā)往A節(jié)點(diǎn)而B(niǎo)節(jié)點(diǎn)只能獲取A節(jié)點(diǎn)約1/3的請(qǐng)求。

于是一致性哈希往往會(huì)引入這么一個(gè)概念：虛擬節(jié)點(diǎn)。盡管我們的服務(wù)器分布不夠均勻，但是我們可以認(rèn)為的創(chuàng)建一些虛擬節(jié)點(diǎn)，并且創(chuàng)建相應(yīng)的映射，幫助虛擬節(jié)點(diǎn)把請(qǐng)求轉(zhuǎn)發(fā)到實(shí)際節(jié)點(diǎn)。

如圖，我們可以創(chuàng)建對(duì)應(yīng)的虛擬節(jié)點(diǎn)A'，B'，然后把發(fā)往B'的請(qǐng)求轉(zhuǎn)發(fā)到B，A'的請(qǐng)求轉(zhuǎn)發(fā)到A，這樣就不會(huì)存在失衡的問(wèn)題了。

哈希槽

哈希槽的典型是redis的分布式實(shí)現(xiàn)。

redis的分布式實(shí)現(xiàn)中，會(huì)在啟動(dòng)集群的時(shí)候確認(rèn)所有的服務(wù)器數(shù)量，然后將數(shù)量為16384的哈希槽平均分配給所有的master服務(wù)器，然后所有的數(shù)據(jù)都會(huì)存放在指定的節(jié)點(diǎn)之中。

redis的哈希槽的實(shí)現(xiàn)和一致性哈希有相同之處，也有不同之處。最主要的原因是redis采用了不同的高可用策略。一致性哈希在服務(wù)器宕機(jī)時(shí)會(huì)把流量轉(zhuǎn)到下一個(gè)服務(wù)器，但是redis不同，redis的集群模式會(huì)保證服務(wù)器節(jié)點(diǎn)擁有的主備模式。備份節(jié)點(diǎn)不會(huì)直接參與到哈希槽的分配中，但是當(dāng)主節(jié)點(diǎn)宕機(jī)后，從節(jié)點(diǎn)會(huì)頂替主節(jié)點(diǎn)處理任務(wù)。

分布式哈希表

分布式哈希表（DHT）是一種分布式的哈希手段。和一致性哈希不同的是，DHT不需要中心節(jié)點(diǎn)來(lái)分配數(shù)據(jù)的流向。他有自己的一套機(jī)制保證無(wú)論數(shù)據(jù)剛開(kāi)始走的是哪一個(gè)服務(wù)器，都可以找到自己需要前往的正確服務(wù)器。

Kademlia算法

Kademlia算法是一種典型的分布式的哈希表算法，多用于p2p網(wǎng)絡(luò)的構(gòu)建，由Petar Maymounkov 和 David Mazieres共同創(chuàng)造。Kademlia論文源地址：Kademlia

分布式環(huán)境下的哈希表的難點(diǎn)在于以下幾點(diǎn)：

1. 分布式環(huán)境下每個(gè)服務(wù)器不可能掌握所有服務(wù)器的情況，因此如何保證你的請(qǐng)求能在沒(méi)有中央節(jié)點(diǎn)定位的情況下找到對(duì)應(yīng)的服務(wù)器是一大難點(diǎn)。

2. 同樣由于分布式環(huán)境的服務(wù)器的掌握信息有限，那么服務(wù)器的加入和退出如何能夠被集群知曉也是一大難點(diǎn)。

那么我們來(lái)看Kademlia算法是如何解決這些問(wèn)題的吧。

異或運(yùn)算

Kademlia使用到了異或來(lái)進(jìn)行距離的計(jì)算。我們先來(lái)看看異或的定義。

異或的運(yùn)算法則為：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同為0，異為1）

然后我們來(lái)看看為什么用異或來(lái)計(jì)算距離。

a⊕b = b⊕a // 異或符合交換律，a節(jié)點(diǎn)到b節(jié)點(diǎn)的距離和b節(jié)點(diǎn)到a結(jié)點(diǎn)的距離相同
a⊕a = 0    // 自己和自己的距離為0
a⊕b >= 0   // 兩個(gè)節(jié)點(diǎn)之間的距離大于0
a⊕b + b⊕c >= a⊕c // a到b再到c的距離大于等于直接到c的距離

根據(jù)上述的一些異或的規(guī)則，我們可以發(fā)現(xiàn)異或和距離的一些特性可以說(shuō)是絕配，真的很佩服算法的作者能夠想到如此精巧的設(shè)計(jì)。

二叉樹(shù)的構(gòu)建

確定了用異或來(lái)計(jì)算距離后，那么具體集群是如何構(gòu)建并存儲(chǔ)信息使得可以查找到正確的信息呢？

Kademlia算法理論中每個(gè)集群的節(jié)點(diǎn)都會(huì)存儲(chǔ)一部分節(jié)點(diǎn)的信息（不可能存儲(chǔ)所有節(jié)點(diǎn)的信息，因?yàn)樾蕰?huì)低，并且無(wú)法保證實(shí)時(shí)性）。

所有的節(jié)點(diǎn)會(huì)構(gòu)建成一棵獨(dú)特的二叉樹(shù)如下圖：

首先把每個(gè)節(jié)點(diǎn)的id經(jīng)過(guò)一定的哈希計(jì)算得到該節(jié)點(diǎn)的一串01字符串以表示其在樹(shù)中的位置，從高位開(kāi)始，1則往左子樹(shù)走，0往右子樹(shù)走，直到結(jié)束?？梢钥闯鰣D中的黑色節(jié)點(diǎn)的哈希值為0011

二叉樹(shù)的拆分

Kademlia的二叉樹(shù)中的每一個(gè)節(jié)點(diǎn)都可以根據(jù)自己的視角進(jìn)行二叉樹(shù)的拆分

拆分規(guī)則是從根節(jié)點(diǎn)開(kāi)始依次把不包含自己的子樹(shù)拆分出來(lái)，以此類(lèi)推，最后只剩下自己。之前的二叉樹(shù)拆分如之前的圖。對(duì)于黑色節(jié)點(diǎn)來(lái)說(shuō)，外部有拆分出了四個(gè)不包含自己的子樹(shù)。

K-bucket機(jī)制

在二叉樹(shù)拆分之后每一個(gè)拆分過(guò)后的子樹(shù)實(shí)際上對(duì)應(yīng)的就是一個(gè)一個(gè)bucket，每個(gè)bucket對(duì)于當(dāng)前節(jié)點(diǎn)的距離是不同的范圍，距離越遠(yuǎn)，高位不同，因此異或結(jié)果差距越大（距離越遠(yuǎn)）：

所以實(shí)際上每一個(gè)節(jié)點(diǎn)再進(jìn)行拆分后只需要在對(duì)應(yīng)的每個(gè)bucket中存儲(chǔ)一份該bucket的節(jié)點(diǎn)就可以遍歷整個(gè)二叉樹(shù)（集群）。當(dāng)然為了容錯(cuò)，一般來(lái)說(shuō)每個(gè)bucket的節(jié)點(diǎn)都會(huì)保留幾個(gè)，而不僅僅是一個(gè)。

節(jié)點(diǎn)查詢(xún)

大致了解了原理之后，我們回過(guò)頭來(lái)看每次請(qǐng)求是如何定位節(jié)點(diǎn)的。

首先一個(gè)請(qǐng)求進(jìn)入集群中的某個(gè)服務(wù)器。然后我們將請(qǐng)求帶著的目的地服務(wù)器的id和當(dāng)前服務(wù)器的id計(jì)算兩者的距離。然后計(jì)算出了一個(gè)值，之后從服務(wù)器的bucket列表中尋找對(duì)應(yīng)的bucket（即這個(gè)距離范圍對(duì)應(yīng)的bucket）。我們的目標(biāo)服務(wù)器就可以鎖定在了那個(gè)bucket的范圍之內(nèi)，之后，在bucket中尋找距離該節(jié)點(diǎn)最近的K個(gè)服務(wù)節(jié)點(diǎn)（此參數(shù)可以自行設(shè)定大?。?，將請(qǐng)求重定向到這幾個(gè)節(jié)點(diǎn)。之后重復(fù)上述的步驟，如果該集群中真的有目標(biāo)節(jié)點(diǎn)，那么就可以成功的返回。

基本的機(jī)制如此，當(dāng)然在實(shí)際的環(huán)境中我們考慮到現(xiàn)實(shí)情況會(huì)對(duì)請(qǐng)求做超時(shí)處理，避免大量的節(jié)點(diǎn)間的查詢(xún)?cè)斐刹槐匾呢?fù)載。

節(jié)點(diǎn)變動(dòng)

一個(gè)新節(jié)點(diǎn)是想加入網(wǎng)絡(luò)，首先有一個(gè)前提條件：他需要有一個(gè)處于網(wǎng)絡(luò)中的節(jié)點(diǎn)的信息，然后才能開(kāi)啟加入流程。

加入流程：

1. 新節(jié)點(diǎn)A以之前就有的節(jié)點(diǎn)T為起點(diǎn)，將其加入自己的K-bucket中，并且生成一個(gè)自己的節(jié)點(diǎn)id

2. 節(jié)點(diǎn)A項(xiàng)節(jié)點(diǎn)B進(jìn)行請(qǐng)求，以自己的id為參數(shù)請(qǐng)求節(jié)點(diǎn)定位自己的位置

3. 之后就是查詢(xún)結(jié)點(diǎn)的流程了，每一個(gè)路經(jīng)的節(jié)點(diǎn)都會(huì)找到自己節(jié)點(diǎn)中存儲(chǔ)的距離節(jié)點(diǎn)最近的節(jié)點(diǎn)，然后A把這些節(jié)點(diǎn)放入自己的bucket中以完善自己的路由表。同時(shí)，這些路經(jīng)節(jié)點(diǎn)也會(huì)把A節(jié)點(diǎn)放入自己的路由表中，以待后用。

4. 等到大部分節(jié)點(diǎn)返回后，A的路由表建立完成，一些節(jié)點(diǎn)也已經(jīng)將A節(jié)點(diǎn)加入自己的路由表。至此A節(jié)點(diǎn)加入網(wǎng)絡(luò)成功。

算法的參數(shù)

算法中我們用到的一些參數(shù)其實(shí)是可以自己定義的：

1. k-bucket中的k：定義了每一層bucket會(huì)存儲(chǔ)k個(gè)節(jié)點(diǎn)信息

2. 每一次請(qǐng)求會(huì)向s個(gè)節(jié)點(diǎn)發(fā)送信息

3. id的長(zhǎng)度也是可以自定義的，注意id的長(zhǎng)度會(huì)決定二叉樹(shù)的高度

到此，關(guān)于“如何理解分布式系統(tǒng)中的哈希算法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！