既然看到一致性哈希了，那就必然有不一致性哈希，我們平時(shí)說(shuō)的哈希算法都是不一致的哈希，這個(gè)不用多說(shuō)了，大家都熟悉的不能再熟悉了

說(shuō)不熟悉的拉出去打一頓

哈希一般都是將一個(gè)大數(shù)字取模然后分散到不同的桶里，假設(shè)我們只有兩個(gè)桶，有 2、3、4、5 四個(gè)數(shù)字，那么模 2 分桶的結(jié)果就是：

這時(shí)我們嫌桶太少要給哈希表擴(kuò)容加了一個(gè)新桶，這時(shí)候所有的數(shù)字就需要模 3 來(lái)確定分在哪個(gè)桶里，結(jié)果就變成了：

可以看到新加了一個(gè)桶后所有數(shù)字的分布都變了，這就意味著哈希表的每次擴(kuò)展和收縮都會(huì)導(dǎo)致所有條目分布的重新計(jì)算，這個(gè)特性在某些場(chǎng)景下是不可接受的。

那一致性哈希是個(gè)什么東西呢，就是屬于哈希的一個(gè)升級(jí)版

在解決分布式系統(tǒng)負(fù)載均衡這個(gè)問(wèn)題上，可以使用哈希算法讓固定的一部分請(qǐng)求落到同一臺(tái)服務(wù)器上，就是根據(jù)服務(wù)器的個(gè)數(shù)來(lái)進(jìn)行相應(yīng)哈希算法的設(shè)計(jì)，這樣每臺(tái)服務(wù)器固定處理一部分請(qǐng)求，并且維護(hù)這些請(qǐng)求的信息，起到負(fù)載均衡的作用

但是呢，如果使用普通的哈希算法就存在一個(gè)很大的問(wèn)題，就是算法的伸縮性很差，當(dāng)新增或者下線的時(shí)候，服務(wù)器的個(gè)數(shù)改變了，用戶ID和服務(wù)器的映射關(guān)系就會(huì)出現(xiàn)大量的失效

這樣就會(huì)導(dǎo)致大量的請(qǐng)求出現(xiàn)服務(wù)器的遷移，比如我們r(jià)edis的服務(wù)器還是是五臺(tái)，經(jīng)過(guò)%5之后映射到相應(yīng)的服務(wù)器上

服務(wù)器變成了8臺(tái)之后，那就變成了%8，那哈希值大多可能就改變了，這樣導(dǎo)致映射的就不是原來(lái)的服務(wù)器上了

有服務(wù)器宕機(jī)的時(shí)候，這個(gè)負(fù)載均衡映射也會(huì)改變，服務(wù)器恢復(fù)之后，負(fù)載均衡映射還是會(huì)改變

一致性哈希算法

一致性Hash算法也是使用取模的方法，不過(guò)，上述的取模方法是對(duì)服務(wù)器的數(shù)量進(jìn)行取模，而一致性的Hash算法是對(duì)2的32方取模。

即，一致性Hash算法將整個(gè)Hash空間組織成一個(gè)虛擬的圓環(huán)，Hash函數(shù)的值空間為0 ~ 2^32 - 1(一個(gè)32位無(wú)符號(hào)整型)，整個(gè)哈希環(huán)如下：

整個(gè)圓環(huán)以順時(shí)針?lè)较蚪M織，圓環(huán)正上方的點(diǎn)代表0，0點(diǎn)右側(cè)的第一個(gè)點(diǎn)代表1，以此類推。

第二步，我們將各個(gè)服務(wù)器使用Hash進(jìn)行一個(gè)哈希，具體可以選擇服務(wù)器的IP或主機(jī)名作為關(guān)鍵字進(jìn)行哈希，這樣每臺(tái)服務(wù)器就確定在了哈希環(huán)的一個(gè)位置上，比如我們有三臺(tái)機(jī)器，使用IP地址哈希后在環(huán)空間的位置如下圖所示：

現(xiàn)在，我們使用以下算法定位數(shù)據(jù)訪問(wèn)到相應(yīng)的服務(wù)器：

將數(shù)據(jù)Key使用相同的函數(shù)Hash計(jì)算出哈希值，并確定此數(shù)據(jù)在環(huán)上的位置

從此位置沿環(huán)順時(shí)針查找，遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器。

例如，現(xiàn)在有ObjectA，ObjectB，ObjectC三個(gè)數(shù)據(jù)對(duì)象，經(jīng)過(guò)哈希計(jì)算后，在環(huán)空間上的位置如下：

根據(jù)一致性算法，Object -> NodeA，ObjectB -> NodeB, ObjectC -> NodeC

一致性Hash算法的容錯(cuò)性和可擴(kuò)展性

現(xiàn)在，假設(shè)我們的Node C宕機(jī)了，我們從圖中可以看到，A、B不會(huì)受到影響，只有Object C對(duì)象被重新定位到Node A。

所以我們發(fā)現(xiàn)，在一致性Hash算法中，如果一臺(tái)服務(wù)器不可用，受影響的數(shù)據(jù)僅僅是此服務(wù)器到其環(huán)空間前一臺(tái)服務(wù)器之間的數(shù)據(jù)(這里為Node C到Node B之間的數(shù)據(jù))，其他不會(huì)受到影響。

如下圖所示：

另外一種情況，現(xiàn)在我們系統(tǒng)增加了一臺(tái)服務(wù)器Node X，如圖所示：

此時(shí)對(duì)象ObjectA、ObjectB沒(méi)有受到影響，只有Object C重新定位到了新的節(jié)點(diǎn)X上。如上所述：一致性Hash算法對(duì)于節(jié)點(diǎn)的增減都只需重定位環(huán)空間中的一小部分?jǐn)?shù)據(jù)，有很好的容錯(cuò)性和可擴(kuò)展性。

數(shù)據(jù)傾斜問(wèn)題

在一致性Hash算法服務(wù)節(jié)點(diǎn)太少的情況下，容易因?yàn)楣?jié)點(diǎn)分布不均勻面造成數(shù)據(jù)傾斜(被緩存的對(duì)象大部分緩存在某一臺(tái)服務(wù)器上)問(wèn)題，如圖特例：

這時(shí)我們發(fā)現(xiàn)有大量數(shù)據(jù)集中在節(jié)點(diǎn)A上，而節(jié)點(diǎn)B只有少量數(shù)據(jù)。

為了解決數(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)，實(shí)現(xiàn)如圖所示：

數(shù)據(jù)定位算法不變，只需要增加一步：虛擬節(jié)點(diǎn)到實(shí)際點(diǎn)的映射。

所以加入虛擬節(jié)點(diǎn)之后，即使在服務(wù)節(jié)點(diǎn)很少的情況下，也能做到數(shù)據(jù)的均勻分布。

既然一致性哈希有這么多好的特性，那為啥主流的哈希都是非一致的呢?

主要一個(gè)原因在于查找效率上，普通的哈希查詢一次哈希計(jì)算就可以找到對(duì)應(yīng)的桶了，算法時(shí)間復(fù)雜度是 O(1)，而一致性哈希需要將排好序的桶組成一個(gè)鏈表，然后一路找下去，k 個(gè)桶查詢時(shí)間復(fù)雜度是 O(k)，所以通常情況下的哈希還是用不一致的實(shí)現(xiàn)。

這里再提一嘴

之所以說(shuō)一致性哈希有用，這是一個(gè)思想，一個(gè)方案，我們?cè)谄綍r(shí)中很多地方都會(huì)涉及到這種思想，比如Redis集群，采用這種方案可以更好的去應(yīng)對(duì)集群節(jié)點(diǎn)的動(dòng)態(tài)的增刪，再比如分庫(kù)分表，這也是一種思路