Hash算法

Hash 算法在路由算法應(yīng)用中，為了保證數(shù)據(jù)均勻的分布，例如有 3 個(gè)桶，分別是 0 號(hào)桶， 1 號(hào)桶和 2 號(hào)桶；現(xiàn)在有 12 個(gè)球，怎么樣才能讓 12 個(gè)球平均分布到 3 個(gè)桶中呢？使用 Hash 算法的做法是，將 12 個(gè)球從 0 開始編號(hào)，得到這樣的一個(gè)序列： 0，1，2，3，4，5，6，7，8，9，10，11 。將這個(gè)序列中的每個(gè)值模3，不管數(shù)字是什么，得到的結(jié)果都是 0,1,2 ，不會(huì)超過(guò) 3 ，將結(jié)果為 0 的數(shù)字放入 0 號(hào)桶，結(jié)果為 1 的數(shù)子放入 1 號(hào)桶，結(jié)果為 2 的數(shù)字放入2號(hào)桶，12個(gè)球就均勻的分布到 3 個(gè)桶中， 0,3,6,9,12 號(hào)球放入 0 號(hào)桶， 1,4,7,10 號(hào)球放入 1 號(hào)桶， 2,5,8,11 號(hào)球放入 2 號(hào)桶。

一致性Hash算法

一致性 Hash 算法在 1997 年由麻省理工學(xué)院提出的一種分布式哈希 (DHT) 實(shí)現(xiàn)算法，設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn) (Hot Spot) 問(wèn)題，初衷和 CARP 十分相似。一致性 Hash 修正了 CARP 使用的簡(jiǎn)單哈希算法帶來(lái)的問(wèn)題，使得分布式哈希 (DHT) 可以在 P2P 環(huán)境中真正得到應(yīng)用。

一致性 Hash 算法也是使用取模的方法，只是，剛才描述的取模法是對(duì)服務(wù)器的數(shù)量進(jìn)行取模，而一致性Hash算法是對(duì) 2^32 取模，什么意思呢？簡(jiǎn)單來(lái)說(shuō)，一致性 Hash 算法將整個(gè)哈希值空間組織成一個(gè)虛擬的圓環(huán)，如假設(shè)某哈希函數(shù)H的值空間為 0-2^32-1 (即哈希值是一個(gè)32位無(wú)符號(hào)整形)。整個(gè)空間按 順時(shí)針?lè)较蚪M織 ，圓環(huán)的正上方的點(diǎn)代表 0，0 點(diǎn)右側(cè)的第一個(gè)點(diǎn)代表 1 ，以此類推， 2、3、4、5、6 ……直到 2^32-1 ，也就是說(shuō) 0 點(diǎn)左側(cè)的第一個(gè)點(diǎn)代表 2^32-1 ， 0 和 2^32-1 在零點(diǎn)中方向重合，我們把這個(gè)由 2^32 個(gè)點(diǎn)組成的圓環(huán)稱為 Hash環(huán) 。

特性定義

一致性 Hash 算法提出了在動(dòng)態(tài)變化的 Cache 環(huán)境中，判定哈希算法好壞的四個(gè)定義：

1、平衡性(Balance)：平衡性是指哈希的結(jié)果能夠盡可能分布在所有的緩沖 (Cache) 中去，這樣可以使得所有的緩沖空間得到利用。很多哈希算法都能夠滿足這一條件。

2、單調(diào)性(Monotonicity)：單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過(guò)哈希分派到了相應(yīng)的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)該能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去，而不會(huì)映射到舊的緩沖集合中的其他緩沖區(qū)。

3、分散性(Spread)：在分布式環(huán)境中，終端有可能看不到所有的緩沖，而只能看到其中的一部分。當(dāng)終端希望通過(guò)哈希過(guò)程將內(nèi)容映射到緩沖上去，由于不同終端所見(jiàn)的緩沖范圍有可能不同，從而導(dǎo)致哈希的結(jié)果不一致，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中。這種情況顯然是應(yīng)該避免的，因?yàn)樗鼘?dǎo)致相同內(nèi)容被存儲(chǔ)到不同緩沖中去，降低了系統(tǒng)存儲(chǔ)的效率。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度。好的哈希算法應(yīng)該能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性。

4、負(fù)載(Load)：負(fù)載問(wèn)題實(shí)際上是從另一個(gè)角度看待分散性問(wèn)題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中，那么對(duì)于一個(gè)特定的緩沖區(qū)而言，也可能被不同的用戶映射到不同的內(nèi)容。與分散性一樣，這種情況也是應(yīng)當(dāng)避免的，因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。

下一步將各個(gè)服務(wù)器使用Hash進(jìn)行一個(gè)哈希，具體可以選擇 服務(wù)器的IP或主機(jī)名 作為 關(guān)鍵字 進(jìn)行哈希，這樣每臺(tái)機(jī)器就能確定其在哈希環(huán)上的位置，這里假設(shè)將上文中四臺(tái)服務(wù)器使用IP地址哈希后在環(huán)空間的位置如下：

接下來(lái)使用如下算法定位數(shù)據(jù)訪問(wèn)到相應(yīng)服務(wù)器：將數(shù)據(jù) key 使用相同的函數(shù) Hash 計(jì)算出哈希值，并確定此數(shù)據(jù)在環(huán)上的位置，從此位置沿環(huán)順時(shí)針“行走”，第一臺(tái)遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器！

例如我們有 Object A 、 Object B 、 Object C 、 Object D 四個(gè)數(shù)據(jù)對(duì)象，經(jīng)過(guò)哈希計(jì)算后，在環(huán)空間上的位置如下：

根據(jù)一致性 Hash 算法，數(shù)據(jù) A 會(huì)被定為到 Node A 上， B 被定為到 Node B 上， C 被定為到 Node C 上， D 被定為到 Node D 上。

容錯(cuò)和可擴(kuò)展

現(xiàn)假設(shè) Node C 不幸宕機(jī)，可以看到此時(shí)對(duì)象 A、B、D 不會(huì)受到影響，只有 C 對(duì)象被重定位到 Node D 。一般的，在一致性 Hash 算法中，如果一臺(tái)服務(wù)器不可用，則受影響的數(shù)據(jù)僅僅是此服務(wù)器到其環(huán)空間中前一臺(tái)服務(wù)器(即沿著逆時(shí)針?lè)较蛐凶哂龅降牡谝慌_(tái)服務(wù)器)之間數(shù)據(jù)，其它不會(huì)受到影響，如下所示：

下面考慮另外一種情況，如果在系統(tǒng)中增加一臺(tái)服務(wù)器 Node X ，如下圖所示：

此時(shí)對(duì)象 Object A、B、D 不受影響，只有對(duì)象 C 需要重定位到新的 Node X ！一般的，在一致性 Hash 算法中，如果增加一臺(tái)服務(wù)器，則受影響的數(shù)據(jù)僅僅是新服務(wù)器到其環(huán)空間中前一臺(tái)服務(wù)器(即沿著逆時(shí)針?lè)较蛐凶哂龅降牡谝慌_(tái)服務(wù)器)之間數(shù)據(jù)，其它數(shù)據(jù)也不會(huì)受到影響。

綜上所述，一致性 Hash 算法對(duì)于節(jié)點(diǎn)的增減都只需重定位環(huán)空間中的一小部分?jǐn)?shù)據(jù)，具有較好的容錯(cuò)性和可擴(kuò)展性。

Hash環(huán)的數(shù)據(jù)傾斜問(wèn)題

一致性 Hash 算法在 服務(wù)節(jié)點(diǎn)太少時(shí) ，容易因?yàn)楣?jié)點(diǎn)分部不均勻而造成 數(shù)據(jù)傾斜 (被緩存的對(duì)象大部分集中緩存在某一臺(tái)服務(wù)器上)問(wèn)題，例如系統(tǒng)中只有兩臺(tái)服務(wù)器，其環(huán)分布如下：

此時(shí)必然造成大量數(shù)據(jù)集中到 Node A 上，而只有極少量會(huì)定位到 Node B 上。為了解決這種數(shù)據(jù)傾斜問(wèn)題，一致性 Hash 算法引入了虛擬節(jié)點(diǎn)機(jī)制，即對(duì)每一個(gè)服務(wù)節(jié)點(diǎn)計(jì)算多個(gè)哈希，每個(gè)計(jì)算結(jié)果位置都放置一個(gè)此服務(wù)節(jié)點(diǎn)，稱為虛擬節(jié)點(diǎn)。具體做法可以在 服務(wù)器IP 或 主機(jī)名 的后面增加編號(hào)來(lái)實(shí)現(xiàn)。

例如上面的情況，可以為每臺(tái)服務(wù)器計(jì)算三個(gè)虛擬節(jié)點(diǎn)，于是可以分別計(jì)算 “ Node A#1 ”、“ Node A#2 ”、“ Node A#3 ”、“ Node B#1 ”、“ Node B#2 ”、“ Node B#3 ”的哈希值，于是形成六個(gè)虛擬節(jié)點(diǎn)：

同時(shí)數(shù)據(jù)定位算法不變，只是多了一步虛擬節(jié)點(diǎn)到實(shí)際節(jié)點(diǎn)的映射，例如定位到“ Node A#1 ”、“ Node A#2 ”、“ Node A#3” 三個(gè)虛擬節(jié)點(diǎn)的數(shù)據(jù)均定位到 Node A 上。這樣就解決了服務(wù)節(jié)點(diǎn)少時(shí)數(shù)據(jù)傾斜的問(wèn)題。在實(shí)際應(yīng)用中，通常將虛擬節(jié)點(diǎn)數(shù)設(shè)置為 32 甚至更大，因此即使很少的服務(wù)節(jié)點(diǎn)也能做到相對(duì)均勻的數(shù)據(jù)分布。

總結(jié)

以上是生活随笔為你收集整理的一致性hash算法虚拟节点_Hash算法和一致性Hash算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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