參考
這個東西是這樣的，他其實跟 Concurrency 一點關係都沒有，但因為我在思考究竟 Hash Table 可不可以做成 Concurrency 的形式，而之前提到的 kfifo 有使用到環狀結構，Concurrent Therad Pool 有使用到 Load Balance ，綜合以上種種關鍵字，忽然想到有這個演算法存在，那就是 Consistent Hashing
而 Consistent Hashing 也有使用到環狀結構，Match 一堆關鍵字讓我整個興趣都來了，就開始花一堆時間研究～～
因為大家已經做了非常多的介紹，基本上我就只是抄他的或者用我的話再說一次，所以這是目前最水的文章，但是又覺得這兩個演算法很棒，可以介紹一下
原本只打算看 Consistent Hashing，但是又 Google 到 Jump Consistent Hashing，感覺很厲害，就一併閱讀了
至於 Hash Table 能否做成 Concurrency 的形式嗎？我覺得可以，就只是 Concurrent Linked List 的一個變形，但因為碰撞機率本來就很低，如果又發生問題，我認為會直接卡死在 Linked List 中，幾乎是永遠出不來，所以好像也不要這麼作會比較好＝＝ 或者要再設計個定時的機制，卡太久幫他換一個 Hash Value？？？
Hash Table
location = hash(key) % size
這是建立在我們已知以下兩點的情況
DHT
如果現在有多個節點共同維護同一個 Hash Table，但是這些節點是動態新增/減少，沒有相對應的機制，繼續使用原先 Hash Table 的機制，那麼只要節點數有變，就代表我們的記憶體大小改變了，所有的索引值都需要作更新，非常的沒有效率
// 多一台 Server
location = hash(key) % (size+1)
// 少一台 Server
location = hash(key) % (size-1)
這邊使用的 DHT 機制是使用 Consistent Hashing ，因為他最簡單，而他採取環形空間的方式進行儲存，頭尾相連
假設一個情況，有三個節點 node1 node2 node3 以及四份資料 data1 data2 data3 data4
第一個部份沒有問題，就是幫資料找到自己的索引值
location_for_data1 = hash(data1)
location_for_data2 = hash(data2)
location_for_data3 = hash(data3)
location_for_data4 = hash(data4)
但我們現在還不知道，該儲存在哪一個節點上，「我們幫節點也作一次 Hash」，節點所代表的數值，通常是使用 IP 位置或者節點名稱
location_for_node1 = hash(node1) // 40
location_for_node2 = hash(node2) // 5000000
location_for_node3 = hash(node3) // 100000000
那我們知道了這幾個節點位置，接下來要存取在哪裡呢！？假設節點的索引值如我們上述所說，那麼我們一開始知道他是一個環狀架構，如果這段記憶體大小是 2^32 - 1 那這個環狀架構就會根據節點的索引值，被切成三個部份
存取在哪一個節點的規則是「以順時針走訪，儲存在遇到的第一個節點」
node1 (100000000 ~ 2147483648, 0 ~ 40)
node2 (40 ~ 5000000)
node3 (5000000 ~ 100000000)
然後如果有節點掛掉了，那就把該節點的資料，轉移到下一個節點，比如說 node2 掛掉了，那就把 node2 的資料，轉移到 node3，如此只需要轉移部份資料
請注意
這並不是拿來儲存資料的技巧，而是一個 Cache 相關的服務，所以資料不見了也不會怎樣，我原本一直很疑惑，資料不見了還轉移什麼＝＝
找到該節點之後，要怎麼儲存是你家的事，可以用 Hash 也可以改用其他資料結構
我們可以知道 Consistent Hashing 算是一種 Load Balance 的方法，所以公平性是非常重要的，但如果只是使用單個 IP 位置來作 Hash ，公平性其實存在一定的問題
所以，實作上可以使用虛擬節點來解決這個問題，因為我們很難保證他會均勻的切割儲存空間
可以使用這種加後綴的方式來作虛擬節點的新增，如此能使得分佈更加均勻
location_for_node1_0 = hash(node1#0)
location_for_node1_1 = hash(node1#1)
location_for_node1_2 = hash(node1#2)
....
Google 天殺的在 2014 年的時候提出了另外一個演算法，叫做 Jump Consistent Hashing A Fast, Minimal Memory, Consistent Hash Algorithm
他使用起來嘛，我覺得跟 Consistent Hashing 真的是一點狗屁關係都沒有，我猜是因為從 Consistent Hashing 開始發想的，所以沿用了這個名字
那麼他想要改善的問題是，在新增/刪除節點的時候，要移動很多資料，而這個動作很浪費效能，因為你要一直在那邊決定，到底要把資料搬到哪裡好呢，其實要花不少時間跟空間，在只有數十個節點的時候，可能還無感，但資料中心動輒幾百幾千個節點，這樣造成的效能影響是可觀的
假設現在有 N 個節點
Consistent Hashing
| 項目 | Big(O) |
|---|
時間複雜度 | O(log N)
空間複雜度 | O(N)
時間複雜度的部份，有點像 Binary Search，一直分邊找，所以複雜度是 O(log N)
空間複雜度的部份，因為我們需要儲存全部節點的索引
Jump Consistent Hashing
| 項目 | Big(O) |
|---|
時間複雜度 | O(log N)
空間複雜度 | O(1)
居然可以常數化空間複雜度！！！
key Hash Valuenum_buckets 節點總數，其實在 Consistent Hashing 中，他們很喜歡使用 bucket 來表示節點，像是在論文中還會看到 shard 來表示節點，反正就是節點的意思b 節點索引值，表示最終要到哪個節點j Jump 的意思int ch(int key, int num_buckets) {
random.seed(key);
int b = 0; // This will track ch(key, j+1).
for (int j = 1; j < num_buckets; j++) {
if (random.next() < 1.0 / (j + 1))
b = j;
}
return b;
}
可以發現現在 ch 的時間複雜度是 O(N) 而空間複雜度是 O(1)，ch 的運算邏輯是隨著 j 的增加，跳躍的可能性越來越低，越來越不可能執行 b = j 這一行程式
PS：會回傳一個節點索引值，所以他不能亂設名字，只能設編號
我們透過一些範例來了解，程式的運行
ch(key, 1)
只有一個 bucket，所以 b 會等於 0
ch(key, 2)b 有 1/2 的機率從 0 變成 1
b 等於 1 的機率是 1/2b 等於 0 的機率是 1/2
ch(key, 3)b 有 1/2 的機率從 0 變成 1b 有 1/3 的機率從 1 變成 2
b 等於 2 的機率是 (1/2) * (1/3) = 1/6b 等於 1 的機率是 1/2b 等於 0 的機率是 2/6
ch(key, N)b 有 1/2 的機率從 0 變成 1b 有 1/3 的機率從 1 變成 2b 有 1/4 的機率從 3 變成 4
....b 有 1/n+1 的機率從 n 變成 n+1
現在我們把目光放在 b 如何隨著 j 去作變化，每一次變化都只有 1/n+1 的部份會作調整，有 n/n+1 的部份保持原樣
如果使用完全隨機的方式去產生機率，會非常的不準，所以有一種東西叫做 偽隨機性，設計出屬於我們的隨機涵式，根據 (key, j) 去作變化，讓他在每個 key 在每個 j 底下都可以均勻分佈
那要怎麼使用偽隨機性呢？？其實就是直接使用 Random 函數就可以了，重點在於把每一個不同的 Hash Value 作為種子丟進去，這樣仍然可以保有 Hash 的特質，就是他的唯一性，而我們又可以根據不同的 Hash Value 得到不同的機率值
想像的是很美好，那該如何設計？？？這終究是個機率問題，讓我們使用機率來幫問題作定義
b 代表上一次的結果，上一個迴圈中選擇哪個節點
j 代表 Jump
P(j >= i) = P(ch(key, b+1) == ch(key, i))
這行數學式表示「下一次結果跳到 i 的機率是多少」，也就是從 b+1 到 i 的這段過程，b 都沒有改變的機率是多少，可以理解為「連續多次不變」
現在還不明白 P(j >= i) 的機率要怎麼算，但可以透過了解「單次不變」，再延伸到「連續多次不變」
單次不變的機率 i/(i+1)P(ch(key, i)==ch(key, i+1)) 代表的意義就是單次不變
b+1 代表下一次結果，我們之前已經推導過了，每次都會有 n/n+1 的機率不變，把 n 替換成 i 就是長這樣
連續多次不變的機率 (b+1)/i
連續多次不變 = P(ch(key, b+1)==ch(k, b+2)) * P(ch(key, b+2)==ch(key, b+3)) * ... * P(ch(key, i-1)==ch(key, i))
= (b+1)/(b+2) * (b+2)/(b+3) * ... * (i-1)/i
= (b+1)/i
那我們可以寫出一段新的程式碼，老實說看完上面的推導，我還是不知道可以像下面這樣寫程式，而這甚至還不是最終版本
int ch(int key, int num_buckets) {
random.seed(key);
int b = -1;
int j = 0;
while (j < num_buckets) { // j 必須要連續不變，
b = j; // 每次都更新 b
double r = random.next(); // 取得這一次的隨機結果， 0~1 之間的小數
// 到底是怎麼把 (b+1)/i 轉化為 floor((b+1) / r) ？？？
// P(j >= i) = (b+1)/i
// 因為我們現在沒有 i ，所以要先把他假設出來
//
// 假設 P(j >= i) 若且唯若 r <= (b+1)/i
// r 是指隨機結果，0~1 之間的小數
// 這邊可能覺得有點奇怪，為什麼是「小於等於」而不是「等於」
// 但是他的邏輯是這樣，等於的時候一定對，但是小於的機率更小，所以更對
// 反正更不可能發生，所以他變得多小都不重要，他就只是個界線，這邊所求的就是一個機率而已
//
// 接下來對不等式進行操作，我們現在得到 i <= (b+1)/r
// 那麼回到原本的式子 P(j >= i) ，可以發現 j = (b+1)/r
//
// 可以簡單理解為把連續分佈轉換為離散分佈
// 那為什麼不用 ceil？？
// 因為如果是 ceil 的話，會把不夠小的 r 一併映射到較大的 j，這樣是不符合 r <= (b+1)/i
//
//
// 單純從程式碼來看：
// 因為 r 是一個小數，所以 b+1 一定會大於 r ，那麼就會完全變成一個機率問題，j 可以往後跳多少
// 隨著 j 變大，下一輪的時候 b+1 也會變得更大，所以往後跳轉的區間會越來越大
// 這也代表著一個區間中，每個節點被選到的機率，不斷在下降
j = floor((b + 1) / r);
}
return b;
}
只看上面還是不知道怎麼計算時間複雜度，因為是均勻分佈，所以假設每次 r 的期望值是 0.5
假設現在有 N 個節點，j = floor((b+1)/r)
第一次跳躍 j = 2 跳了 2 個節點
第二次跳躍 j = 6 跳了 4 個節點
第三次跳躍 j = 14 跳了 8 個節點
...
第 Log N 次跳躍，一定可以結束
而這段程式碼，可以再做優化，避免調用 random 涵式，最終是使用 線性同餘方法(LCG) 這個偽隨機函數進行實作，我沒有查看系統中的偽函數一般是怎麼實作，但論文中只有提到他希望盡可能的快速，所以...就只是想找一個夠快的偽函數演算法
int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
int64_t b = -1, j = 0;
while (j < num_buckets) {
b = j;
key = key * 2862933555777941757ULL + 1;
j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
}
return b;
}
如果在網路上查資料，可以發現更多結果，因為上面講的也都只是理論，但實作 Load Balance 其實有很多要注意的點
但我沒有相關經驗，也沒有機器可以實驗，所以這部份我真的是不想作實驗啦@@
iThome鐵人賽
看影片追技術