聊聊一致性哈希

既然有一致性哈希，就肯定還有不一致哈希，為啥平時(shí)沒人說不一致哈希呢？因?yàn)槌Ｒ姷墓６际遣灰恢碌模跃筒恍揎椓耍搅艘恢滦怨２盘厥饧觽€(gè)描述詞修飾一下。

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

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

可以看到新加了一個(gè)桶后所有數(shù)字的分布都變了，這就意味著哈希表的每次擴(kuò)展和收縮都會導(dǎo)致所有條目分布的重新計(jì)算，這個(gè)特性在某些場景下是不可接受的。比如分布式的存儲系統(tǒng)，每個(gè)桶就相當(dāng)于一個(gè)機(jī)器，文件分布在哪臺機(jī)器由哈希算法來決定，這個(gè)系統(tǒng)想要加一臺機(jī)器時(shí)就需要停下來等所有文件重新分布一次才能對外提供服務(wù)，而當(dāng)一臺機(jī)器掉線的時(shí)候盡管只掉了一部分?jǐn)?shù)據(jù)，但所有數(shù)據(jù)訪問路由都會出問題。這樣整個(gè)服務(wù)就無法平滑的擴(kuò)縮容，成為了有狀態(tài)的服務(wù)。

要想實(shí)現(xiàn)無狀態(tài)化，就要用到一致性哈希了，一致性哈希中假想我們有很多個(gè)桶，先定一個(gè)小目標(biāo)比如 7 個(gè)，但一開始真實(shí)還是只有兩個(gè)桶，編號是 3 和 6。哈希算法還是同樣的取模，只不過現(xiàn)在分桶分到的很可能是不存在的桶，那么就往下找找到第一個(gè)真實(shí)存在的桶放進(jìn)去。這樣 2 和 3 都被分到了編號為 3 的桶， 4 和 5 被分到了編號為 6 的桶。

這時(shí)候再添加一個(gè)新的桶，編號是 4，取模方法不變還是模 7：

因?yàn)?3 號桶里都是取模小于等于 3 的，4 號桶只需要從 6 號桶里拿走屬于它的數(shù)字就可以了，這種情況下只需要調(diào)整一個(gè)桶的數(shù)字就可分成了重新分布。可以想象下即使有 1 億個(gè)桶，增加減少一個(gè)桶也只會影響一個(gè)桶的數(shù)據(jù)分布。

這樣增加一個(gè)機(jī)器只需要和他后面的機(jī)器同步一下數(shù)據(jù)就可以開始工作了，下線一個(gè)機(jī)器需要先把他的數(shù)據(jù)同步到后面一臺機(jī)器再下線。如果突然掉了一臺機(jī)器也只會影響這臺機(jī)器上的數(shù)據(jù)。實(shí)現(xiàn)中可以讓每臺機(jī)器同步一份自己前面機(jī)器的數(shù)據(jù)，這樣即使掉線也不會影響這一部分的數(shù)據(jù)服務(wù)。

這里還有個(gè)小問題要是編號為 6 的機(jī)桶下線了，它沒有后一個(gè)桶了，數(shù)據(jù)該咋辦？為了解決這個(gè)問題，實(shí)現(xiàn)上通常把哈希空間做成環(huán)狀，這樣 3 就成了 6 的下一桶，數(shù)據(jù)給 3 就好了：

用一致性哈希還能實(shí)現(xiàn)部分的分布式系統(tǒng)無鎖化，每個(gè)任務(wù)有自己的編號，由于哈希算法的確定性，分到哪個(gè)桶也是確定的就不存在爭搶，也就不需要分布式鎖了。

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

當(dāng)然 O(k) 的時(shí)間復(fù)雜度對于哈希來說還是不能忍的，想一下都是O(k) 這個(gè)量級了用哈希的意義在哪里？既然是在排好序的桶里查詢，很自然的想法就是二分了，能把時(shí)間復(fù)雜度降到 O(logk)，然而桶的組合需要不斷的增減，所以是個(gè)鏈表的實(shí)現(xiàn)，二分肯定就不行了，還好可以用跳轉(zhuǎn)表進(jìn)行一個(gè)快速的跳轉(zhuǎn)也能實(shí)現(xiàn) O(logk) 的時(shí)間復(fù)雜度。

在這個(gè)跳轉(zhuǎn)表中，每個(gè)桶記錄距離自己 1，2，4 距離的數(shù)字所存的桶，這樣不管查詢落在哪個(gè)節(jié)點(diǎn)上，對整個(gè)哈希環(huán)上任意的查詢一次都可以至少跳過一半的查詢空間，這樣遞歸下去很快就可以定位到數(shù)據(jù)是存在哪個(gè)桶上。

當(dāng)然這寫都只是一致性哈希實(shí)現(xiàn)方式中的一種，還有很多實(shí)現(xiàn)上的變體。比如選擇數(shù)字放在哪個(gè)桶，上面的介紹里是選擇順著數(shù)字下去出現(xiàn)的第一個(gè)桶，其實(shí)也可以選擇距離這個(gè)數(shù)字最近的桶，這樣實(shí)現(xiàn)和后面的跳轉(zhuǎn)表規(guī)則也會有變化。同樣跳轉(zhuǎn)表也有多種不同的算法實(shí)現(xiàn)，感興趣的可以去看一下 CAN，Chord，Tapestry，Pastry 這四種 DHT 的實(shí)現(xiàn)，有意思的是它們都是 2001 年發(fā)出來的 paper，所以 2001 年大概是 P2P 下載的元年吧。

文章來源: https://zhuanlan.zhihu.com/p/24440059