這個算法零記憶體、分布均勻、計算快速，全是優點了。但是。。。
一、背景
三年前在《一緻性hash基礎知識》文章中，曾提到 google 有一個算法簡單的計算就做到了一緻性哈希需要做到的事情。
上個月在《一緻性HASH技術的困境》文章的留言中，也有小夥伴提到，有一個 Jump consistent hash 算法可以做到一緻性哈希的事情。
其實這兩個說的是一個事情，那就是 google 有一個 Jump consistent hash 算法，可以通過數學運算做到和一緻性哈希效果一樣好的平衡性。
那今天就來看看這個算法吧。
二、看代碼
先看代碼，下面就是全部的代碼。
是不是感覺不可思議，這個代碼的文法全部都懂，但是合在一起我們就看不懂了。
我第一眼看到這個代碼的時候，也是一臉懵逼的。
這個算法是 Google 的 John Lamping 和 Eric Veach 創造的。
他們為這個算法寫了一篇論文：《A Fast, Minimal Memory, Consistent Hash Algorithm》。
看了論文後，我才恍然大悟，原來是這樣，果然是合理的。
如果你要閱讀原文論文，可以公衆号背景回複“谷歌算法”擷取論文。
三、算法原理
一緻性雜湊演算法有兩個目标：
- 平衡性。即把資料平均的分布在所有節點中。
- 單調性。即節點的數量變化時，隻需要把一部分資料從舊節點移動到新節點，不需要做其他的移動。
我們根據這個單調性可以推算出一些性質來。
這裡先令
f(key, n)
為一緻性雜湊演算法，輸出的為
[0,n)
之間的數字，代表資料在對應的節點上。
-
n=1
key
-
n=2
1/2
1/2
1
-
n=3
1/3
1/3
1
1/3
2
- 依次遞推，節點數由
n
n+1
f(key, n)
n/(n+1)
1/(n+1)
n
這個使用機率公式來表示，就是這樣的代碼。
關于這個算法直接看可能還是看不懂。
是以需要使用實際資料模拟一下，見下圖。
關鍵在于
n=2
到
n=3
的過程，每個數字的機率從
1/2
轉化到了
1/3
。
之後，我們可以得出一個規律：增加一個節點，資料不發生變化的機率是
n/(n+1)
再乘以之前每個數字的機率
1/n
，就可以得出每個數字最新的機率
1/(n+1)
由此，可以輕松計算出
n=4
各數字的機率為
1/4
。自此，我們可以确定這個算法确實是有效的。
這個算法唯一的缺點是複雜度太高，是
O(n)
的。
是以需要進行優化。
四、算法優化
在上一小節中，我們了解到
f(key, n)
算法的正确性。
除了複雜度是
O(n)
外，我們還可以确定，循環越往後，結果改變的機率會越來越低。
結果改變指的是，增加一個節點後，一個固定的
key
輸出的結果發生了改變。
如果我們能夠快速計算出這個固定的
key
在哪些節點下發生了改變，就可以快速計算出最終答案。
假設某一次結果是
b
，經過若幹次機率測試，下一次改變為
a
，則從
b
到
a-1
這中間，不管節點如何變化，這個
key
的結果都是不會變化的。
根據上一小節的到的機率變化公式，新增一個節點數字不變化的機率是
n/(n+1)
。
那從
b
到
i
不變化的機率就是
b/i
（中間的抵消了）。
如果我們有一個均勻的随機函數
r
，當
r<b/i
時，
f(i)=f(b)
。
那麼
i
的上界就是
(b+1)/r
。
這個上限也是下一次
key
發生變化的節點數量，由此可以得出下面的代碼。
由于
r
是均勻的，是以期望是
1/2
。
這樣，代碼中
j
就是按照指數級增長的，平均複雜度就是
O(log(n))
了。
回頭看看第一個代碼，就可以看懂代碼了。
第一個
key=key*x+1
算是一個僞随機生成器。
而
j=(b+1)*x/y
則是上面的求上界的公式，其中
y/x
通過浮點數運算來産生
(0,1)
内的一個随機數。
自此，這個代碼就可以看懂了。
五、最後
谷歌能夠創造這樣一個算法确實了不起，但是從實際應用上來，這個算法也沒有想象中的好。
如果你用過一緻性哈希的話，會發現有很多問題。
因為我們實際使用時，節點往往是有權重的。
這裡隻有一個節點的最大值，那意味着，節點的擴散需要在外層實作。
也就是需要在外層來儲存擴散後的節點清單。
既然外面儲存了節點清單，按照 hash 值排序，就可以二分查找出符合要求的節點了。
如果使用 map 儲存，也可以在
log
級别找到對應的節點。
由此，可以發現 谷歌的這個算法自身不需要記憶體了，但是記憶體需要業務自己維護，實際上還是需要的。
當然，如果你沒使用過一緻性哈希的話，你不知道我在說什麼。
或者你可以看看之前我記錄的一緻性 HASH 文章，然後再回頭看看這個小節。
-EOF-
上篇文章：《公有雲、私有雲、專有雲的差別》
相關推薦：《一緻性hash基礎知識(二)》
本文公衆号：天空的代碼世界
個人微信号：tiankonguse
QQ算法群：165531769（不止算法）
知識星球：不止算法