又被微信問懵了！

大家好，我是小林。

在逛牛客網(wǎng)的面經(jīng)的時候，發(fā)現(xiàn)有位同學(xué)在面微信的時候，被問到這個問題：

第一個問題就是：一致性哈希是什么，使用場景，解決了什么問題？

這個問題還挺有意思的，所以今天就來聊聊這個。

發(fā)車！

如何分配請求？

大多數(shù)網(wǎng)站背后肯定不是只有一臺服務(wù)器提供服務(wù)，因?yàn)閱螜C(jī)的并發(fā)量和數(shù)據(jù)量都是有限的，所以都會用多臺服務(wù)器構(gòu)成集群來對外提供服務(wù)。

但是問題來了，現(xiàn)在有那么多個節(jié)點(diǎn)（后面統(tǒng)稱服務(wù)器為節(jié)點(diǎn)，因?yàn)樯僖粋€字），要如何分配客戶端的請求呢？

其實(shí)這個問題就是「負(fù)載均衡問題」。解決負(fù)載均衡問題的算法很多，不同的負(fù)載均衡算法，對應(yīng)的就是不同的分配策略，適應(yīng)的業(yè)務(wù)場景也不同。

最簡單的方式，引入一個中間的負(fù)載均衡層，讓它將外界的請求「輪流」的轉(zhuǎn)發(fā)給內(nèi)部的集群。比如集群有 3 個節(jié)點(diǎn)，外界請求有 3 個，那么每個節(jié)點(diǎn)都會處理 1 個請求，達(dá)到了分配請求的目的。

考慮到每個節(jié)點(diǎn)的硬件配置有所區(qū)別，我們可以引入權(quán)重值，將硬件配置更好的節(jié)點(diǎn)的權(quán)重值設(shè)高，然后根據(jù)各個節(jié)點(diǎn)的權(quán)重值，按照一定比重分配在不同的節(jié)點(diǎn)上，讓硬件配置更好的節(jié)點(diǎn)承擔(dān)更多的請求，這種算法叫做加權(quán)輪詢。

加權(quán)輪詢算法使用場景是建立在每個節(jié)點(diǎn)存儲的數(shù)據(jù)都是相同的前提。所以，每次讀數(shù)據(jù)的請求，訪問任意一個節(jié)點(diǎn)都能得到結(jié)果。

但是，加權(quán)輪詢算法是無法應(yīng)對「分布式系統(tǒng)」的，因?yàn)榉植际较到y(tǒng)中，每個節(jié)點(diǎn)存儲的數(shù)據(jù)是不同的。

當(dāng)我們想提高系統(tǒng)的容量，就會將數(shù)據(jù)水平切分到不同的節(jié)點(diǎn)來存儲，也就是將數(shù)據(jù)分布到了不同的節(jié)點(diǎn)。比如一個分布式 KV（key-valu） ?緩存系統(tǒng)，某個 key 應(yīng)該到哪個或者哪些節(jié)點(diǎn)上獲得，應(yīng)該是確定的，不是說任意訪問一個節(jié)點(diǎn)都可以得到緩存結(jié)果的。

因此，我們要想一個能應(yīng)對分布式系統(tǒng)的負(fù)載均衡算法。

使用哈希算法有什么問題？

有的同學(xué)可能很快就想到了：哈希算法。因?yàn)閷ν粋€關(guān)鍵字進(jìn)行哈希計算，每次計算都是相同的值，這樣就可以將某個 key 確定到一個節(jié)點(diǎn)了，可以滿足分布式系統(tǒng)的負(fù)載均衡需求。

哈希算法最簡單的做法就是進(jìn)行取模運(yùn)算，比如分布式系統(tǒng)中有 3 個節(jié)點(diǎn)，基于 hash(key) % 3 公式對數(shù)據(jù)進(jìn)行了映射。

如果客戶端要獲取指定 key 的數(shù)據(jù)，通過下面的公式可以定位節(jié)點(diǎn)：

hash(key)?%?3

如果經(jīng)過上面這個公式計算后得到的值是 0，就說明該 key 需要去第一個節(jié)點(diǎn)獲取。

但是有一個很致命的問題，如果節(jié)點(diǎn)數(shù)量發(fā)生了變化，也就是在對系統(tǒng)做擴(kuò)容或者縮容時，必須遷移改變了映射關(guān)系的數(shù)據(jù)，否則會出現(xiàn)查詢不到數(shù)據(jù)的問題。

舉個例子，假設(shè)我們有一個由 A、B、C 三個節(jié)點(diǎn)組成分布式 KV 緩存系統(tǒng)，基于計算公式 hash(key) % 3 ?將數(shù)據(jù)進(jìn)行了映射，每個節(jié)點(diǎn)存儲了不同的數(shù)據(jù)：

現(xiàn)在有 3 個查詢 key 的請求，分別查詢 key-01，key-02，key-03 的數(shù)據(jù)，這三個 key 分別經(jīng)過 hash() 函數(shù)計算后的值為 hash( key-01) = 6、hash( key-02) = 7、hash(key-03) = 8，然后再對這些值進(jìn)行取模運(yùn)算。

通過這樣的哈希算法，每個 key 都可以定位到對應(yīng)的節(jié)點(diǎn)。

當(dāng) 3 個節(jié)點(diǎn)不能滿足業(yè)務(wù)需求了，這時我們增加了一個節(jié)點(diǎn)，節(jié)點(diǎn)的數(shù)量從 3 變化為 4，意味取模哈希函數(shù)中基數(shù)的變化，這樣會導(dǎo)致大部分映射關(guān)系改變，如下圖：

比如，之前的 hash(key-01) % 3 = 0，就變成了 hash(key-01) % 4 = 2，查詢 key-01 數(shù)據(jù)時，尋址到了節(jié)點(diǎn) C，而 ?key-01 的數(shù)據(jù)是存儲在節(jié)點(diǎn) A 上的，不是在節(jié)點(diǎn) C，所以會查詢不到數(shù)據(jù)。

同樣的道理，如果我們對分布式系統(tǒng)進(jìn)行縮容，比如移除一個節(jié)點(diǎn)，也會因?yàn)槿∧９：瘮?shù)中基數(shù)的變化，可能出現(xiàn)查詢不到數(shù)據(jù)的問題。

要解決這個問題的辦法，就需要我們進(jìn)行遷移數(shù)據(jù)，比如節(jié)點(diǎn)的數(shù)量從 3 變化為 4 時，要基于新的計算公式 hash(key) % 4 ，重新對數(shù)據(jù)和節(jié)點(diǎn)做映射。

假設(shè)總數(shù)據(jù)條數(shù)為 M，哈希算法在面對節(jié)點(diǎn)數(shù)量變化時，最壞情況下所有數(shù)據(jù)都需要遷移，所以它的數(shù)據(jù)遷移規(guī)模是 O(M)，這樣數(shù)據(jù)的遷移成本太高了。

所以，我們應(yīng)該要重新想一個新的算法，來避免分布式系統(tǒng)在擴(kuò)容或者縮容時，發(fā)生過多的數(shù)據(jù)遷移。

使用一致性哈希算法有什么問題？

一致性哈希算法就很好地解決了分布式系統(tǒng)在擴(kuò)容或者縮容時，發(fā)生過多的數(shù)據(jù)遷移的問題。

一致哈希算法也用了取模運(yùn)算，但與哈希算法不同的是，哈希算法是對節(jié)點(diǎn)的數(shù)量進(jìn)行取模運(yùn)算，而一致哈希算法是對 2^32 進(jìn)行取模運(yùn)算，是一個固定的值。

我們可以把一致哈希算法是對 2^32 進(jìn)行取模運(yùn)算的結(jié)果值組織成一個圓環(huán)，就像鐘表一樣，鐘表的圓可以理解成由 60 個點(diǎn)組成的圓，而此處我們把這個圓想象成由 2^32 個點(diǎn)組成的圓，這個圓環(huán)被稱為哈希環(huán)，如下圖：

一致性哈希要進(jìn)行兩步哈希：

• 第一步：對存儲節(jié)點(diǎn)進(jìn)行哈希計算，也就是對存儲節(jié)點(diǎn)做哈希映射，比如根據(jù)節(jié)點(diǎn)的 IP 地址進(jìn)行哈希；
• 第二步：當(dāng)對數(shù)據(jù)進(jìn)行存儲或訪問時，對數(shù)據(jù)進(jìn)行哈希映射；

所以，一致性哈希是指將「存儲節(jié)點(diǎn)」和「數(shù)據(jù)」都映射到一個首尾相連的哈希環(huán)上。

問題來了，對「數(shù)據(jù)」進(jìn)行哈希映射得到一個結(jié)果要怎么找到存儲該數(shù)據(jù)的節(jié)點(diǎn)呢？

答案是，映射的結(jié)果值往順時針的方向的找到第一個節(jié)點(diǎn)，就是存儲該數(shù)據(jù)的節(jié)點(diǎn)。

舉個例子，有 3 個節(jié)點(diǎn)經(jīng)過哈希計算，映射到了如下圖的位置：

接著，對要查詢的 key-01 進(jìn)行哈希計算，確定此 ?key-01 映射在哈希環(huán)的位置，然后從這個位置往順時針的方向找到第一個節(jié)點(diǎn)，就是存儲該 ?key-01 數(shù)據(jù)的節(jié)點(diǎn)。

比如，下圖中的 ? key-01 映射的位置，往順時針的方向找到第一個節(jié)點(diǎn)就是節(jié)點(diǎn) A。

所以，當(dāng)需要對指定 key 的值進(jìn)行讀寫的時候，要通過下面 2 步進(jìn)行尋址：

• 首先，對 key 進(jìn)行哈希計算，確定此 key 在環(huán)上的位置；
• 然后，從這個位置沿著順時針方向走，遇到的第一節(jié)點(diǎn)就是存儲 key 的節(jié)點(diǎn)。

知道了一致哈希尋址的方式，我們來看看，如果增加一個節(jié)點(diǎn)或者減少一個節(jié)點(diǎn)會發(fā)生大量的數(shù)據(jù)遷移嗎？

假設(shè)節(jié)點(diǎn)數(shù)量從 3 增加到了 4，新的節(jié)點(diǎn) D 經(jīng)過哈希計算后映射到了下圖中的位置：

你可以看到，key-01、key-03 都不受影響，只有 key-02 ?需要被遷移節(jié)點(diǎn) D。

假設(shè)節(jié)點(diǎn)數(shù)量從 3 減少到了 2，比如將節(jié)點(diǎn) A 移除：

你可以看到，key-02 和 key-03 不會受到影響，只有 key-01 需要被遷移節(jié)點(diǎn) B。

因此，在一致哈希算法中，如果增加或者移除一個節(jié)點(diǎn)，僅影響該節(jié)點(diǎn)在哈希環(huán)上順時針相鄰的后繼節(jié)點(diǎn)，其它數(shù)據(jù)也不會受到影響。

上面這些圖中 3 個節(jié)點(diǎn)映射在哈希環(huán)還是比較分散的，所以看起來請求都會「均衡」到每個節(jié)點(diǎn)。

但是一致性哈希算法并不保證節(jié)點(diǎn)能夠在哈希環(huán)上分布均勻，這樣就會帶來一個問題，會有大量的請求集中在一個節(jié)點(diǎn)上。

比如，下圖中 3 個節(jié)點(diǎn)的映射位置都在哈希環(huán)的右半邊：

這時候有一半以上的數(shù)據(jù)的尋址都會找節(jié)點(diǎn) A，也就是訪問請求主要集中的節(jié)點(diǎn) A 上，這肯定不行的呀，說好的負(fù)載均衡呢，這種情況一點(diǎn)都不均衡。

另外，在這種節(jié)點(diǎn)分布不均勻的情況下，進(jìn)行容災(zāi)與擴(kuò)容時，哈希環(huán)上的相鄰節(jié)點(diǎn)容易受到過大影響，容易發(fā)生雪崩式的連鎖反應(yīng)。

比如，上圖中如果節(jié)點(diǎn) A 被移除了，當(dāng)節(jié)點(diǎn) A 宕機(jī)后，根據(jù)一致性哈希算法的規(guī)則，其上數(shù)據(jù)應(yīng)該全部遷移到相鄰的節(jié)點(diǎn) B 上，這樣，節(jié)點(diǎn) B 的數(shù)據(jù)量、訪問量都會迅速增加很多倍，一旦新增的壓力超過了節(jié)點(diǎn) B 的處理能力上限，就會導(dǎo)致節(jié)點(diǎn) B 崩潰，進(jìn)而形成雪崩式的連鎖反應(yīng)。

所以，一致性哈希算法雖然減少了數(shù)據(jù)遷移量，但是存在節(jié)點(diǎn)分布不均勻的問題。

要想解決節(jié)點(diǎn)能在哈希環(huán)上分配不均勻的問題，就是要有大量的節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)越多，哈希環(huán)上的節(jié)點(diǎn)分布的就越均勻。

但問題是，實(shí)際中我們沒有那么多節(jié)點(diǎn)。所以這個時候我們就加入虛擬節(jié)點(diǎn)，也就是對一個真實(shí)節(jié)點(diǎn)做多個副本。

具體做法是，不再將真實(shí)節(jié)點(diǎn)映射到哈希環(huán)上，而是將虛擬節(jié)點(diǎn)映射到哈希環(huán)上，并將虛擬節(jié)點(diǎn)映射到實(shí)際節(jié)點(diǎn)，所以這里有「兩層」映射關(guān)系。

比如對每個節(jié)點(diǎn)分別設(shè)置 3 個虛擬節(jié)點(diǎn)：

• 對節(jié)點(diǎn) A 加上編號來作為虛擬節(jié)點(diǎn)：A-01、A-02、A-03
• 對節(jié)點(diǎn) B 加上編號來作為虛擬節(jié)點(diǎn)：B-01、B-02、B-03
• 對節(jié)點(diǎn) C 加上編號來作為虛擬節(jié)點(diǎn)：C-01、C-02、C-03

引入虛擬節(jié)點(diǎn)后，原本哈希環(huán)上只有 3 個節(jié)點(diǎn)的情況，就會變成有 9 個虛擬節(jié)點(diǎn)映射到哈希環(huán)上，哈希環(huán)上的節(jié)點(diǎn)數(shù)量多了 3 倍。

你可以看到，節(jié)點(diǎn)數(shù)量多了后，節(jié)點(diǎn)在哈希環(huán)上的分布就相對均勻了。這時候，如果有訪問請求尋址到「A-01」這個虛擬節(jié)點(diǎn)，接著再通過「A-01」虛擬節(jié)點(diǎn)找到真實(shí)節(jié)點(diǎn) A，這樣請求就能訪問到真實(shí)節(jié)點(diǎn) A 了。

上面為了方便你理解，每個真實(shí)節(jié)點(diǎn)僅包含 3 個虛擬節(jié)點(diǎn)，這樣能起到的均衡效果其實(shí)很有限。而在實(shí)際的工程中，虛擬節(jié)點(diǎn)的數(shù)量會大很多，比如 Nginx 的一致性哈希算法，每個權(quán)重為 1 的真實(shí)節(jié)點(diǎn)就含有160 個虛擬節(jié)點(diǎn)。

另外，虛擬節(jié)點(diǎn)除了會提高節(jié)點(diǎn)的均衡度，還會提高系統(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)不同的真實(shí)節(jié)點(diǎn)，即這些不同的真實(shí)節(jié)點(diǎn)共同分擔(dān)了節(jié)點(diǎn)變化導(dǎo)致的壓力。

而且，有了虛擬節(jié)點(diǎn)后，還可以為硬件配置更好的節(jié)點(diǎn)增加權(quán)重，比如對權(quán)重更高的節(jié)點(diǎn)增加更多的虛擬機(jī)節(jié)點(diǎn)即可。

因此，帶虛擬節(jié)點(diǎn)的一致性哈希方法不僅適合硬件配置不同的節(jié)點(diǎn)的場景，而且適合節(jié)點(diǎn)規(guī)模會發(fā)生變化的場景。

總結(jié)

不同的負(fù)載均衡算法適用的業(yè)務(wù)場景也不同的。

輪訓(xùn)這類的策略只能適用與每個節(jié)點(diǎn)的數(shù)據(jù)都是相同的場景，訪問任意節(jié)點(diǎn)都能請求到數(shù)據(jù)。但是不適用分布式系統(tǒng)，因?yàn)榉植际较到y(tǒng)意味著數(shù)據(jù)水平切分到了不同的節(jié)點(diǎn)上，訪問數(shù)據(jù)的時候，一定要尋址存儲該數(shù)據(jù)的節(jié)點(diǎn)。

哈希算法雖然能建立數(shù)據(jù)和節(jié)點(diǎn)的映射關(guān)系，但是每次在節(jié)點(diǎn)數(shù)量發(fā)生變化的時候，最壞情況下所有數(shù)據(jù)都需要遷移，這樣太麻煩了，所以不適用節(jié)點(diǎn)數(shù)量變化的場景。

為了減少遷移的數(shù)據(jù)量，就出現(xiàn)了一致性哈希算法。

一致性哈希是指將「存儲節(jié)點(diǎn)」和「數(shù)據(jù)」都映射到一個首尾相連的哈希環(huán)上，如果增加或者移除一個節(jié)點(diǎn)，僅影響該節(jié)點(diǎn)在哈希環(huán)上順時針相鄰的后繼節(jié)點(diǎn)，其它數(shù)據(jù)也不會受到影響。

但是一致性哈希算法不能夠均勻的分布節(jié)點(diǎn)，會出現(xiàn)大量請求都集中在一個節(jié)點(diǎn)的情況，在這種情況下進(jìn)行容災(zāi)與擴(kuò)容時，容易出現(xiàn)雪崩的連鎖反應(yīng)。

為了解決一致性哈希算法不能夠均勻的分布節(jié)點(diǎn)的問題，就需要引入虛擬節(jié)點(diǎn)，對一個真實(shí)節(jié)點(diǎn)做多個副本。不再將真實(shí)節(jié)點(diǎn)映射到哈希環(huán)上，而是將虛擬節(jié)點(diǎn)映射到哈希環(huán)上，并將虛擬節(jié)點(diǎn)映射到實(shí)際節(jié)點(diǎn)，所以這里有「兩層」映射關(guān)系。

引入虛擬節(jié)點(diǎn)后，可以會提高節(jié)點(diǎn)的均衡度，還會提高系統(tǒng)的穩(wěn)定性。所以，帶虛擬節(jié)點(diǎn)的一致性哈希方法不僅適合硬件配置不同的節(jié)點(diǎn)的場景，而且適合節(jié)點(diǎn)規(guī)模會發(fā)生變化的場景。

完！