一致性雜湊

普通的雜湊分片會遇到什麼問題？

Sharding

#

上次談到對資料庫進行水平擴展時，其中一種做法是 分片 (sharding)，將一個大資料庫切成多個較小的資料庫 (shard)，目標是將大量資料與請求，有效率且均勻的分配到多台機器上，避免產生熱點。那麼在實作分片時，如何決定哪些資料該儲存在哪些節點上？

機器是指作為 storage node 的 server，讓 shard 在上面運行著。shard 和 server 不需要是一對一關係，一台 server 上可以跑多個 shard。

Shard Key

#

可以先觀察應用程式的 query 模式，再來決定適合的分片策略，並選擇 shard key。好的 shard key 通常具備幾個特性，包括不會隨時間變動 (immutable)、擁有大量不重複的值 (高基數, high cardinality)、能夠均勻分散數據與負載、以及符合主要的查詢模式，讓大多數請求能在單個分片上完成。反之，盡量避免使用基數低、或會頻繁變動的屬性作為 shard key。

Sharding Strategy

#

分片策略有很多種，可以按 key 的範圍來分，也就是 範圍分片 (range sharding)，類似百科全書 A-C 放一個 shard、D-F 放另一個；或是按月份將 Jan 明細放一個 shard、Feb 明細放另一個。另一種作法是按 key 的 hash 值來分，也就是 雜湊分片 (hash sharding)，對 key 計算雜湊值後，依分片數量取餘數，來決定要放在哪台機器。

不同策略有它適用的場景，從資料特性來思考，單調遞增類型的資料，比如訂單編號或 timestamp，就不適合純範圍分片，因為新的資料一定會往數值最大的那端跑，造成尾端熱點 (hot tail / write hotspot)，使得最新的分片被寫入流量壓垮，舊分片卻在閒置。這時候就可以考慮雜湊分片，把連續的數值打散，隨機分佈到不同節點，來達到寫入均衡。而某些具備地理或分類屬性的資料，比如用戶所在地區，就不適合純雜湊分片，因為雜湊會把同一個地區的資料，噴到全球各處，當需要查詢「台北市的銷售報告」時，就必須跨節點訪問每一台機器，讀取的效率很差。因此當需要頻繁做範圍查詢時，用範圍分片會比較適合。有些系統則會用複合式分片策略，先按地區做範圍分片，再對地區內的資料做雜湊分片，來兼顧查詢效率與寫入均衡。

Hash Sharding

#

接續前面提到的雜湊 (hash)，hash 運算就是將某個任意長度的值，丟進一個 hash 函數 (也就是 雜湊演算法，例如 MD5、SHA-256、MurmurHash) 做計算，無論輸入的值有多長，hash 函數都會輸出一個固定長度、看似亂碼的數字，稱為 雜湊值 (hash value)。雜湊值具有 不可逆 的單向性，我們無法從雜湊值反推出原本的 input 是什麼；而相同的 input 丟進去，出來的雜湊值一定相同。另一方面，當輸入兩個不同的 input，卻計算出一樣的雜湊值，這種衝突現象稱為雜湊碰撞 (hash collision)，即使雜湊碰撞無法完全避免，但一個好的雜湊演算法，能夠讓碰撞的機率降到極低。

Hash Table

• 雜湊表 (hash table) 是一種資料結構，核心概念是根據 key 來決定資料存放在哪個記憶體位置。運作方式是利用雜湊函數，將 key 轉換成一個整數 index，再將 value 存入 array 中對應的那個 index 位置，進而建立雜湊表，而後也能透過同樣的雜湊函數，來找出資料存放在表格的位置。底層 array 中，用來存放資料的具體空間，叫做 bucket / slot (桶 / 槽)，也就是儲存資料的格子。在電腦的記憶體中，array 是一塊連續的空間，它有一個特性是，只要知道 index，電腦就能在固定的時間內跳到那個位置。

• Java 的 HashMap、Python 的 Dictionary，都是雜湊表在程式語言中的具體實作。以 Dictionary 為例：

  • d[“Ally”] = 100 (key = “Ally”, value = 100)。
  • hashing：python 對 key 進行雜湊運算，“Ally” → 34567。
  • mapping key to index：運算結果決定資料要存在 array 的哪個位置。例如：將雜湊值對 array 大小取餘數，來決定存放位置：34567 % 8 = 7，將 value 存入 array[7]，array[7] = 100。
  • O(1) 查找：呼叫 d[“Ally”] 時，python 做同樣的計算，並跳轉到目標位置，直接存取 array[7] 取出 100。

• 雜湊表以計算取代搜尋，不需要掃描整張表，因此可以達到平均 O(1) 的存取效率 (也就是常數時間複雜度，不管資料量多大，查詢所需要的時間幾乎都是一樣的)，這也是 hash sharding 的優勢所在，當有了 shard key，就能很快找到對應的 shard。

Example

#

一般雜湊分片做法是這樣： server index = hash(shard key) % n，其中 n 是 server 或 shard 的總數量。

假設現在有 4 台 server，每個 key 的分配情況如下 (圖1)：

如果 server 數量是固定的，而且資料的分佈很均勻，這種做法就有很好的效果。但如果 server 數量有變動，我們就會面臨「重新計算雜湊值」的問題。假設現在覺得負載太重，想增加第 5 台機器，一樣採用取餘數的方法，就會變成「雜湊值 % 5」。由於大多數的運算結果都會改變，使得大部分的 key 都被重新分配到不同機器如下 (圖 2)，而且現在 server 3 的負擔還更重了。

Consistent Hashing

#

當系統需要擴展時，如果增加或刪減一台機器，就導致大量資料需要重新搬移，那麼在搬移期間，就很容易使系統過載甚至癱瘓。這個問題在設計快取系統時也很明顯，當快取命中率在重新分片的瞬間大幅下降，導致大量請求直接打到 DB，就會造成快取雪崩 (cache avalanche)。面對這樣的情況，具有一致性的雜湊作法 (consistent hashing) 就能用來緩解機器數量變化時，需要大規模遷移資料的問題。現實中像是 Cassandra、DynamoDB、Discord 等系統，都有運用這個技術。它是一種特殊的雜湊演算法，基本步驟是這樣：

• 使用一種均勻分佈的雜湊函式，把 server 和各個 key 對應到圓環上。
• 如果要找出某個 key 對應到哪台 server，就從 key 的位置開始順時針方向移動，直到遇到圓環上的第一台 server，就是它存放的地方。

接著來看看它是如何運作：

Hash Space & Hash Ring

#

• 假設用 SHA-1 作為雜湊函式，函式的輸出範圍是 x0, x1, …, xn (雜湊值)。
• 在密碼學中，SHA-1 的雜湊空間 (hash space) 是從 0 到 2^260-1。
• 表示 x0 對應到 0，xn 對應到 2^260-1，而中間所有其他的雜湊值，都介於 0 到 2^260-1 之間。
• 把 x0、xn 兩端接起來，就可以得到一個雜湊環 (hash ring) (圖 3)。

Hashing Servers

#

用相同的雜湊函式，對 server 的 IP 或名稱做 hash 運算，讓每台 server 落在圓環上對應的位置 (圖 4)。

Hashing Keys

#

用相同的雜湊函式，對 key 做 hash 運算，讓 key 也落在圓環上對應的位置 (圖 5)。要注意的是，這裡用的雜湊函式和前面提到的不同，並沒有進行「取餘數」的運算。

Looking Up a Server

#

從各個 key 在環上的位置開始，沿著順時針方向找到一台 server，來決定每個 key 應該存放在哪一台 server。如圖 6 所示，key 0 保存在 server 0；key 1 保存在 server 1；key 2 保存在server 2；key 3 保存在 server 3。

Adding a Server

#

如果增加一台新的 server 4，按照上述的邏輯，只有 key 0 需要重新分配。在圖 7 中，key 0 原本放在 server 0，現在會被重新存放到 server 4；而 key 1、key 2、key 3 都不會變，會繼續存放在原有的 server。運用這樣具有一致性的雜湊算法，可以讓大部分的 key 都不需要重新分配。

Removing a Server

#

同樣的邏輯，如果移除了 server 1，就只有 key 1 需要被重新分配到 server 2，其餘的 key 都不受影響 (圖 8)。

Identifying Affected Keys

#

既然新增或移除機器時，會有一部分資料需要重新分配，那麼要如何找出受影響的範圍？用前面兩個例子來說，當增加了 server 4 (圖 7)，受影響的範圍就是從 新節點 (s4) 開始，逆時針 方向移動，直到遇到另一台 server 為止 (s3)，位於 s4 與 s3 之間的 key 都要重新分給 s4。而當移除了 server 1 (圖 8)，受影響的範圍就是從 已刪除的節點 (s1) 開始，逆時針 方向移動，直到遇到另一台 server 為止 (s0)，位於 s1 與 s0 之間的 key 都要重新分配給 s2。

Virtual Nodes

#

以上說明的基本做法，其實會遇到以下兩個問題：

1. server 在圓環上可能分佈不均，由於可以增減機器，相鄰 server 之間的雜湊空間 (可以稱作分區 (partition)) 可能會變很大、或變很小。如圖 9 (左) 所示，當移除了 s1，s0 和 s2 之間的空間 (p2)，就會變成其他人的兩倍大。

2. key 在圓環上也可能分布不均，使得大多數的 key 被存在同一個 server，而其他 server 卻空空的。如圖 9 (右) 所示，大部分的 key 都存放在 s2，而 s1 和 s3 卻沒有任何資料。

上面這兩個問題，可以利用 虛擬節點 的技術來解決：

• 每個虛擬節點都會指向一個真實節點。
• 在圖 10 (左) 中，假設 server 0 有三個虛擬節點 (s0_0、s0_1、s0_2)，server 1 也有三個虛擬節點 (s1_0、s1_1、s1_2)。實務上，虛擬節點的數量會大很多，也許有一、兩百個。
• 由於有很多虛擬節點，讓每個分區 (相鄰機器之間的雜湊空間) 都有對應到的 server 來負責。
• 如圖 10 (右) 所示，標籤為 s0 的黃色分區，全都由 server 0 負責管理；標籤為 s1 的藍色分區，則都由 server 1 負責管理。

• 要查出某個 key 存放在哪台 server，也是以順時鐘方向移動，直到遇到第一個虛擬節點。在圖 11 中，key 0 會找到虛擬節點 s1_1，代表的就是 server 1。
• 虛擬節點的數量越多，資料的分佈也就越均勻。不過，增加越多的虛擬節點，就需要越多空間來儲存虛擬節點的資料，這也是一個需要取捨的問題。我們可以自行調整數量，以符合我們的系統要求。

Revisiting the Example

#

回到一開始的例子 (圖 1、圖 2)，現在使用一致性雜湊，假設圓環數值空間是 0~100000；有 4 台 server，A、B、C、D；分別對應到的位置是 A: 20000、B: 40000、C: 60000、D: 80000，資料的分佈情況就會如下 (圖 12)：

現在增加了第 5 台 server E，對應的位置是 50000，只有一個 key (ORD-003) 需要重新分配到 server E，如下 (圖 13)：

總結來說，具有一致性的雜湊作法，有以下幾個優點：

• 新增、移除 server 時，讓需要重新分配的 key 的數量最小化。
• 由於資料分佈更均勻，很容易進行水平擴展。
• 更均勻的分散資料，可以緩解其中某些 key 特別熱門的問題。例如：不會把 Justin Bieber 和 Lady Gaga 的資料全放在同一個分片，造成特定分片遇到過多存取導致 server 超載。