1. 前言

在Redis 集群模式Cluster中，Redis采用的是分片Sharding的方式，也就是將數(shù)據(jù)采用一定的分區(qū)策略，分發(fā)到相應的集群節(jié)點中。但是我們使用上述HASH算法進行緩存時，會出現(xiàn)一些缺陷，主要體現(xiàn)在服務器數(shù)量變動的時候，所有緩存的位置都要發(fā)生改變！具體來講就是說第一當緩存服務器數(shù)量發(fā)生變化時，會引起緩存的雪崩，可能會引起整體系統(tǒng)壓力過大而崩潰（大量緩存同一時間失效）。第二當緩存服務器數(shù)量發(fā)生變化時，幾乎所有緩存的位置都會發(fā)生改變。

2. 一致性哈希的基本概念

一致性Hash算法也是使用取模的方法，只是，剛才描述的取模法是對服務器的數(shù)量進行取模，而一致性Hash算法是對2^{32取模，什么意思呢？簡單來說，一致性Hash算法將整個哈希值空間組織成一個虛擬的圓環(huán)，如假設某哈希函數(shù)H的值空間為0-2}32-1（即哈希值是一個32位無符號整形），整個哈希環(huán)如下：

整個空間按順時針方向組織，圓環(huán)的正上方的點代表0，0點右側的第一個點代表1，以此類推，2、3、4、5、6……直到2^{32-1，也就是說0點左側的第一個點代表2}32-1， 0和2^{32-1在零點中方向重合，我們把這個由2}32個點組成的圓環(huán)稱為Hash環(huán)。

那么，一致性哈希算法與上圖中的圓環(huán)有什么關系呢？我們繼續(xù)聊，仍然以之前描述的場景為例，假設我們有4臺緩存服務器，服務器A、服務器B、服務器C，服務器D，那么，在生產(chǎn)環(huán)境中，這4臺服務器肯定有自己的IP地址或主機名，我們使用它們各自的IP地址或主機名作為關鍵字進行哈希計算，使用哈希后的結果對2^32取模，可以使用如下公式示意：

hash（服務器A的IP地址） % 2^32

通過上述公式算出的結果一定是一個0到2^{32-1之間的一個整數(shù)，我們就用算出的這個整數(shù)，代表服務器A，既然這個整數(shù)肯定處于0到2}32-1之間，那么，上圖中的hash環(huán)上必定有一個點與這個整數(shù)對應，而我們剛才已經(jīng)說明，使用這個整數(shù)代表服務器A，那么，服務器A就可以映射到這個環(huán)上。

以此類推，下一步將各個服務器使用類似的Hash算式進行一個哈希，這樣每臺機器就能確定其在哈希環(huán)上的位置，這里假設將上文中四臺服務器使用IP地址哈希后在環(huán)空間的位置如下：

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

3. 一致性Hash算法的容錯性和可擴展性

現(xiàn)假設Node C不幸宕機，可以看到此時對象A、B、D不會受到影響，只有C對象被重定位到Node D。一般的，在一致性Hash算法中，如果一臺服務器不可用，則受影響的數(shù)據(jù)僅僅是此服務器到其環(huán)空間中前一臺服務器（即沿著逆時針方向行走遇到的第一臺服務器）之間數(shù)據(jù)，其它不會受到影響，如下所示：

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

此時對象Object A、B、D不受影響，只有對象C需要重定位到新的Node X ！一般的，在一致性Hash算法中，如果增加一臺服務器，則受影響的數(shù)據(jù)僅僅是新服務器到其環(huán)空間中前一臺服務器（即沿著逆時針方向行走遇到的第一臺服務器）之間數(shù)據(jù)，其它數(shù)據(jù)也不會受到影響。

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

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

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

此時必然造成大量數(shù)據(jù)集中到Node A上，而只有極少量會定位到Node B上，從而出現(xiàn)hash環(huán)偏斜的情況，當hash環(huán)偏斜以后，緩存往往會極度不均衡的分布在各服務器上，如果想要均衡的將緩存分布到2臺服務器上，最好能讓這2臺服務器盡量多的、均勻的出現(xiàn)在hash環(huán)上，但是，真實的服務器資源只有2臺，我們怎樣憑空的讓它們多起來呢，沒錯，就是憑空的讓服務器節(jié)點多起來，既然沒有多余的真正的物理服務器節(jié)點，我們就只能將現(xiàn)有的物理節(jié)點通過虛擬的方法復制出來。

這些由實際節(jié)點虛擬復制而來的節(jié)點被稱為"虛擬節(jié)點"，即對每一個服務節(jié)點計算多個哈希，每個計算結果位置都放置一個此服務節(jié)點，稱為虛擬節(jié)點。具體做法可以在服務器IP或主機名的后面增加編號來實現(xiàn)。

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

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

總結

以上是生活随笔為你收集整理的Redis：一致性Hash算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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