如何理解一致性哈希

這篇文章主要講解了“如何理解一致性哈?！?，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“如何理解一致性哈?！卑?！

一技能：哈希算法

分組

韓信的一技能哈希算法：將士兵的編號 num 值當做一個哈希值，再和總做小組數(shù) N 做取余操作，得出的結果在 0 到 N - 1  之間，這個士兵就屬于那個組。

如下圖所示，每來一個士兵都有一個六位的 hash 值(也可以稱作編號)，然后被韓信用除以 3 取余數(shù)的方式分配到三個組。比如第一組中的編號為 123456  的士兵，除以 3 之后，整除，余數(shù)為 0，所以分配到第一組。

哈希算法

查找士兵

現(xiàn)在已經(jīng)分好組了，假如想找到編號為 666666 的士兵該怎么找?首先將 666666 除以 3，得到余數(shù)  0，說明在第一個組，然后去第一個組里面找就可以了。

這里有小伙伴可能會問，為什么不是把所有士兵放到一個組?

因為一個組太大了，影響行軍速度。映射到互聯(lián)網(wǎng)架構中，就是通過增加節(jié)點從而減小單節(jié)點的負載壓力。

哈希分組弊端

劉邦看了這個一技能后，大呼：

韓將軍真是厲害。

哈希算法看起來很完美，那我再給你五百士兵，需要分成四個組怎么辦?

這時，韓信的副將說話了：

這還不簡單，再用 4 取余不就好了嗎?

劉邦摸著下巴思索片刻后，對副將說：

這個方案可行，但很多士兵都被重新分組了，剛剛建立的團隊友情就被分解了。

我們來看下劉邦為什么覺得方案不可行。

比如原來分配到一組的編號為 3 的士兵，當分成四組的時候，通過公式計算：3%4=3，所以會分配到到第四組。

依次類推，會發(fā)現(xiàn)很多士兵進行了重新分配，只有小部分不會變換分組，比如 1，2，12 不會被重新分組。

韓信對著劉邦點點頭，對著主公說道：

主公，您說得沒錯，這就是我的一技能的弱點所在。

不過我還有一個技能：一致性哈希。

二技能：一致性哈希哈希環(huán)

一致性哈希算法也用了取模運算，但是它與哈希算法不同的地方：

• 哈希算法：對節(jié)點的數(shù)量進行取模運算。

• 一致性哈希算法：對 2^32 進行取模運算。

可以想象一下，一致性哈希算法，是將整個哈希值空間組成了一個虛擬的圓環(huán)，也就是哈希環(huán)。

如下圖，把 3 個組映射到固定大小為 2^32  的哈希環(huán)中。三個組一共將整個環(huán)分成了三個區(qū)域，C-A(第一組)、A-B(第二組)、B-C(第三組)。如下圖所示：

分成三組

• 第一組負責存儲落在 C-A 區(qū)間內的數(shù)據(jù)。

• 第二組負責存儲落在 A-B 區(qū)間內的數(shù)據(jù)。

• 第三組負責存儲落在 B-C 區(qū)間內的數(shù)據(jù)。

士兵分配

假定編號為 9527 的士兵，進行哈希運算后，落到 C-A 區(qū)域。如下圖所示：

士兵所站位置

第二步，讓這個士兵順時針往前走，遇到的第一個節(jié)點 A 就是他所在的組了。如下圖所示:

順時針遇到第一個節(jié)點

增加分組

目前三個節(jié)點的時候，假定編號為 89757 的士兵經(jīng)過哈希運算后，分配到了 B-C 區(qū)域(第三組)，也就是屬于 C 節(jié)點管控。如下圖所示：

屬于 C 節(jié)點

回到劉邦剛問的問題，如果分組變成四組，該怎么進行士兵分配。

如下圖所示，增加一個節(jié)點 D，原來的區(qū)域 B-C 變成了區(qū)域 B-D(第三組) 和 D-C(第四組)。

增加 D 節(jié)點

那么這名士兵屬于哪個節(jié)點管控呢?如下圖所示，士兵順時針往前走，先走到了 D 節(jié)點，所以屬于 D  節(jié)點管控。雖然還是屬于第三組，但是這名士兵的領導者已經(jīng)變了：由 C 變成了 D。

領導者變了

從上面的變化來看，只有 B-C 區(qū)域中的部分數(shù)據(jù)會進行遷移：B-D 之間的數(shù)據(jù)會由 C 節(jié)點遷移到 D 節(jié)點。

而其他數(shù)據(jù)不受影響，也不用進行遷移。而且節(jié)點越多，需要遷移的數(shù)據(jù)就越少。這就是多多益善了~

劉邦看了后，大贊韓信：

不虧是大將軍，蕭何當時月下追你，值了!

哈希環(huán)缺陷

蕭何看了韓信畫的哈希環(huán)后，覺得有些不對勁，思索片刻后，對韓信說：

將軍，你這個哈希環(huán)上的節(jié)點分布不太均勻啊，你看第三組和第四組的的區(qū)域好小啊。

蕭何說得沒錯，確實存在這個問題，放到互聯(lián)網(wǎng)架構中，就存在如下問題：

節(jié)點分布不均勻，導致業(yè)務對節(jié)點的訪問冷熱不均。

韓信眼中充滿著贊賞，知我者莫若蕭何。然后胸有成竹地說道：

你說得沒錯，不過我還有一個技能，虛擬節(jié)點映射。

三技能：虛擬節(jié)點

一般虛擬節(jié)點比物理節(jié)點要多，并相對均勻地分布在哈希環(huán)上。如下圖所示，12 個虛擬節(jié)點  N1~N12，相對均勻地分布在虛擬節(jié)點上。如果有士兵屬于 N2/N3/N4 中的某一個，都會重新映射到 A 節(jié)點，依次類推，N5/N6/N7 屬于 B  節(jié)點的虛擬節(jié)點映射。

虛擬節(jié)點

我們來看下蕭何的提出的問題，真實的 B-D 區(qū)域比較小，用虛擬節(jié)點后，N5/N6/N7 屬于 B 節(jié)點，N8/N9/N10 屬于 D  節(jié)點，他們分到的虛擬節(jié)點一樣多，而且區(qū)域大致相等。所以士兵的分配也比較均勻。

感謝各位的閱讀，以上就是“如何理解一致性哈希”的內容了，經(jīng)過本文的學習后，相信大家對如何理解一致性哈希這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！