概覽
什麼是一致性雜湊（Consistent Hashing）？ 在了解這個概念之前，首先可以將 hashing（雜湊）理解為「切碎並混合」。Hash Map 是一種將數據映射到索引的資料結構。作為時間複雜度為 O(1) 的結構，可以說是最有效率的。通常是以鍵值對（key-value pair）的形式進行儲存。
關於雜湊就先談到這裡，接下來讓我們來聊聊分散式雜湊。
分散式雜湊
想像一下有以下的雜湊表（Hash Table）。現在我們要把這些數據儲存到分散式的數據存儲空間中。
| KEY | HASH | HASH mod 3 |
|---|---|---|
| “john” | 1633428562 | 2 |
| “bill” | 7594634739 | 0 |
| “jane” | 5000799124 | 1 |
| “steve” | 9787173343 | 0 |
| “kate” | 3421657995 | 2 |
如果分配到三台伺服器儲存，整理如下。 索引分別為 A:0, B:1, C:2。
| A | B | C |
|---|---|---|
| “bill” | “jane” | “john” |
| “steve” | “kate” |
在運作良好的情況下，假設突然有一台設備故障了。如果伺服器 C 宕機，雜湊表和伺服器上的數據分配將會變成如下所示：
| KEY | HASH | HASH mod 2 |
|---|---|---|
| “john” | 1633428562 | 0 |
| “bill” | 7594634739 | 1 |
| “jane” | 5000799124 | 0 |
| “steve” | 9787173343 | 1 |
| “kate” | 3421657995 | 1 |
現在數據將會儲存在 A:0, B:1 兩台存儲空間中，如下所示：
| A | B |
|---|---|
| “john” | “bill” |
| “jane” | “steve” |
| “kate” |
這樣一來，原本存在於 C 的所有鍵位置都會發生變動。此時需要從原始數據進行 re-hashing（重新雜湊）作業，這會給原始伺服器帶來負載。而且在此過程中，客戶端請求的數據將會遺失。
為了解決這個問題而提出的雜湊技術就是一致性雜湊 (Consistent Hashing)。
一致性雜湊 (Consistent Hashing)
上圖就是本次要說明的核心。 讓我們根據上圖的邏輯來進行雜湊。
| KEY | HASH | ANGLE (DEG) |
|---|---|---|
| “john” | 1633428562 | 58.7 |
| “C” | 2269549488 | 81.7 |
| “kate” | 3421657995 | 123.1 |
| “jane” | 5000799124 | 180 |
| “A” | 5572014557 | 200.5 |
| “bill” | 7594634739 | 273.4 |
| “B” | 8077113361 | 290.7 |
| “steve” | 787173343 | 352.3 |
伺服器也會一起配置在雜湊環中。
在這裡，尋找各個鍵所屬伺服器的規則只有一個：
逆時針方向旋轉時，最接近的伺服器就是該鍵所在的存儲空間。
根據上述基準整理鍵所在的存儲空間如下：
| KEY | HASH | ANGLE (DEG) | LABEL | SERVER |
|---|---|---|---|---|
| “john” | 1632929716 | 58.7 | “C” | C |
| “kate” | 3421831276 | 123.1 | “A” | A |
| “jane” | 5000648311 | 180 | “A” | A |
| “bill” | 7594873884 | 273.4 | “B” | B |
| “steve” | 9786437450 | 352.3 | “C” | C |
那麼，這項技術的優點到底是什麼呢？
現在請想像一下，假設 C 設備被移除了。在傳統技術中，所有的鍵都必須重新雜湊（rehashing）。
而透過這種技術，我們可以看到只需要對原本分配給 C 設備的鍵進行 rehashing。
因為指向 A、B 伺服器的鍵已經指向了最近的 A、B 位置。即使 C 消失了，那些鍵也不會有任何變動。只有原本分配給 C 伺服器的鍵需要進行 rehashing。
相反地，即使增加設備，也只需要進行 K/N（鍵的數量 / 設備數量）比例的 rehashing，而不需要對所有鍵進行 rehashing。
例如，當原本有 3 個鍵和 2 台設備時，如果中間增加了一台設備。假設設計成鍵能均勻分佈，那麼大約只需要對 3/3 = 1 個鍵進行 rehashing，最終可以達到每台設備儲存一個鍵的均衡狀態。
不過，一致性雜湊也有一個問題，就是「鍵傾斜」（資料分佈不均）。該如何緩解這個問題呢？
Ketama 一致性雜湊 (Ketama Consistent Hashing)
最簡單的方法是將伺服器拆分成多個權杖（虛擬節點），並配置在一致性雜湊環（Consistent Hashing Circle）中。 這就是 Ketama 一致性雜湊技術。將 A 伺服器分散為 A0 到 A10，使鍵的配置盡可能均勻。
思考
- 最終，rehashing 是無法完全避免的問題。設計並構建一個能讓 rehashing 發生率降至最低的系統，我認為這是分散式處理的核心需求。