這個算法零內(nèi)存恩掷、分布均勻倡鲸、計算快速，全是優(yōu)點了黄娘。但是峭状。克滴。。
一宁炫、背景
三年前在《一致性hash基礎(chǔ)知識》文章中，曾提到 google 有一個算法簡單的計算就做到了一致性哈希需要做到的事情氮凝。
上個月在《一致性HASH技術(shù)的困境》文章的留言中羔巢，也有小伙伴提到，有一個 Jump consistent hash 算法可以做到一致性哈希的事情罩阵。
其實這兩個說的是一個事情竿秆，那就是 google 有一個 Jump consistent hash 算法，可以通過數(shù)學(xué)運(yùn)算做到和一致性哈希效果一樣好的平衡性稿壁。
那今天就來看看這個算法吧幽钢。
二、看代碼
先看代碼傅是，下面就是全部的代碼匪燕。
是不是感覺不可思議，這個代碼的語法全部都懂喧笔，但是合在一起我們就看不懂了帽驯。
我第一眼看到這個代碼的時候，也是一臉懵逼的书闸。
這個算法是 Google 的 John Lamping 和 Eric Veach 創(chuàng)造的尼变。
他們?yōu)檫@個算法寫了一篇論文：《A Fast, Minimal Memory, Consistent Hash Algorithm》。
看了論文后浆劲，我才恍然大悟嫌术，原來是這樣，果然是合理的牌借。
如果你要閱讀原文論文度气，可以公眾號后臺回復(fù)“谷歌算法”獲取論文。
三膨报、算法原理
一致性哈希算法有兩個目標(biāo)：
平衡性蚯嫌。即把數(shù)據(jù)平均的分布在所有節(jié)點中。
單調(diào)性丙躏。即節(jié)點的數(shù)量變化時择示，只需要把一部分?jǐn)?shù)據(jù)從舊節(jié)點移動到新節(jié)點，不需要做其他的移動晒旅。
我們根據(jù)這個單調(diào)性可以推算出一些性質(zhì)來栅盲。
這里先令f(key, n)為一致性哈希算法，輸出的為[0,n)之間的數(shù)字废恋，代表數(shù)據(jù)在對應(yīng)的節(jié)點上谈秫。
n=1時扒寄，對于任意的key，輸出應(yīng)該都是0拟烫。n=2時该编，為了保持均勻，應(yīng)該有1/2的結(jié)果保持為0硕淑，1/2的結(jié)果輸出為1课竣。n=3時，應(yīng)該有1/3的結(jié)果保持為0置媳，1/3的結(jié)果保持為1于樟，1/3的結(jié)果保持為2。依次遞推拇囊，節(jié)點數(shù)由
n變?yōu)?code>n+1時迂曲，f(key, n)里面應(yīng)該有n/(n+1)的結(jié)果不變，有1/(n+1)的結(jié)果變?yōu)?code>n寥袭。
這個使用概率公式來表示路捧，就是這樣的代碼。
關(guān)于這個算法直接看可能還是看不懂传黄。
所以需要使用實際數(shù)據(jù)模擬一下鬓长，見下圖。
關(guān)鍵在于n=2到n=3的過程尝江，每個數(shù)字的概率從1/2轉(zhuǎn)化到了1/3涉波。
之后，我們可以得出一個規(guī)律：增加一個節(jié)點炭序，數(shù)據(jù)不發(fā)生變化的概率是n/(n+1) 再乘以之前每個數(shù)字的概率1/n啤覆，就可以得出每個數(shù)字最新的概率1/(n+1)
由此，可以輕松計算出n=4各數(shù)字的概率為1/4惭聂。自此窗声，我們可以確定這個算法確實是有效的。
這個算法唯一的缺點是復(fù)雜度太高辜纲，是O(n)的笨觅。
所以需要進(jìn)行優(yōu)化。
四耕腾、算法優(yōu)化
在上一小節(jié)中见剩，我們了解到f(key, n)算法的正確性。
除了復(fù)雜度是O(n)外扫俺，我們還可以確定苍苞，循環(huán)越往后，結(jié)果改變的概率會越來越低。
結(jié)果改變指的是羹呵，增加一個節(jié)點后骂际，一個固定的key輸出的結(jié)果發(fā)生了改變。
如果我們能夠快速計算出這個固定的key在哪些節(jié)點下發(fā)生了改變冈欢，就可以快速計算出最終答案歉铝。
假設(shè)某一次結(jié)果是b，經(jīng)過若干次概率測試凑耻，下一次改變?yōu)?code>a太示，則從b到a-1這中間，不管節(jié)點如何變化拳话，這個key的結(jié)果都是不會變化的先匪。
根據(jù)上一小節(jié)的到的概率變化公式种吸，新增一個節(jié)點數(shù)字不變化的概率是n/(n+1)弃衍。
那從b到i不變化的概率就是b/i（中間的抵消了）。
如果我們有一個均勻的隨機(jī)函數(shù)r坚俗，當(dāng)r<b/i時镜盯，f(i)=f(b)。
那么i的上界就是(b+1)/r猖败。
這個上限也是下一次key發(fā)生變化的節(jié)點數(shù)量速缆，由此可以得出下面的代碼。
由于r是均勻的恩闻，所以期望是1/2艺糜。
這樣，代碼中j就是按照指數(shù)級增長的幢尚，平均復(fù)雜度就是O(log(n))了破停。
回頭看看第一個代碼，就可以看懂代碼了尉剩。
第一個key=key*x+1算是一個偽隨機(jī)生成器真慢。
而j=(b+1)*x/y則是上面的求上界的公式，其中y/x通過浮點數(shù)運(yùn)算來產(chǎn)生(0,1)內(nèi)的一個隨機(jī)數(shù)理茎。
自此黑界，這個代碼就可以看懂了。
五皂林、最后
谷歌能夠創(chuàng)造這樣一個算法確實了不起朗鸠，但是從實際應(yīng)用上來，這個算法也沒有想象中的好础倍。
如果你用過一致性哈希的話童社，會發(fā)現(xiàn)有很多問題。
因為我們實際使用時著隆，節(jié)點往往是有權(quán)重的扰楼。
這里只有一個節(jié)點的最大值呀癣，那意味著，節(jié)點的擴(kuò)散需要在外層實現(xiàn)弦赖。
也就是需要在外層來儲存擴(kuò)散后的節(jié)點列表项栏。
既然外面儲存了節(jié)點列表，按照 hash 值排序蹬竖，就可以二分查找出符合要求的節(jié)點了沼沈。
如果使用 map 儲存，也可以在 log 級別找到對應(yīng)的節(jié)點币厕。
由此列另，可以發(fā)現(xiàn) 谷歌的這個算法自身不需要內(nèi)存了，但是內(nèi)存需要業(yè)務(wù)自己維護(hù)旦装，實際上還是需要的页衙。
當(dāng)然，如果你沒使用過一致性哈希的話阴绢，你不知道我在說什么店乐。
或者你可以看看之前我記錄的一致性 HASH 文章，然后再回頭看看這個小節(jié)呻袭。
-EOF-
上篇文章：《公有云眨八、私有云爹凹、專有云的區(qū)別》
相關(guān)推薦：《一致性hash基礎(chǔ)知識(二)》
本文公眾號：天空的代碼世界
個人微信號：tiankonguse
QQ算法群：165531769（不止算法）
知識星球：不止算法
