11 min readAug 13, 2021

初識 Redis Cluster Ep 2 : Key-Based Sharding — 乾坤大挪移之術

前言：

Ep1 Redis 架構簡介介紹了 Redis Cluster 的用途，節點怎麼分配資料，以及節點之間如何溝通，Ep2 主要著重討論資料分配上的相關議題。

Redis Cluster 系列文章：

Ep 1. Redis Cluster 架構

Ep 2. Key-Based Sharding

Ep 3. Cluster Message Protocol

Ep 4. Cluster Management

Ep 5. 手把手用 Docker-Compose 架一個 Redis Cluster

內文 — Key-Based Sharding

在介紹 Key-Based Sharding 之前，讓我先提一個概念「data sharding」

data sharding 是在分散式 DB 架構中，透過水平擴展將資料分散到不同 DB 的技術

採用 data sharding 主要有以下原因：

垂直擴展最終會遇到瓶頸 (e.g CPU, Disk, Power etc)
單一 DB 塞太多資料會降低效能跟提高風險 (e.g 容易當機)

data sharding 中主要三種分散資料的方式：

Key Based Sharding：將資料中的特定欄位 (e.g Primary Key) 丟到 Hash Function 算出一個值，並用這個值來找出對應的 DB，由於這個分散方式會用到 Hash，所有又稱為 Hash Based Sharding。
Range Based Sharding : 將資料中的特定欄位 (e.g Timestamp ) 依照大小分成不同 Range 來分配到不同 DB，例如 1~3 月的資料給 DB_1，4~6 月的資料給 DB_2。
Directory Based Sharding : 在 Sharding 之前先準備好一個 Key-Value Table，Key 為資料中某個特定欄位，Value 為 DB 的編號，直接透過該 Table 做資料分配。

透過 Ep1 (還沒看的拜託去看)，知道了 Redis Cluster 的方式是用 Key Based Sharding (aka Hash Based Sharding)，因此針對 Key Based Sharding，我們來探討以下幾個問題：

一個好的 Key Based Sharding 要符合哪些條件？
誰是大名鼎鼎的 Consistent Hashing？
為何 Redis 不用大名鼎鼎的 Consistent Hashing？
資料被分散了，我的 Transaction 怎麼辦？

問題一：一個好的 Key Based Sharding 要符合哪些條件？

首先勒，一個好的 Key Based Sharding 要符合兩個條件：

均衡性：資料要盡可能的平均分散在不同的 DB 上。
單調性：當 Cluster 成員有變動時，要確保原有的 Key 盡可能地不會被重新分配。

一個不符合以上條件的 Key-Based Sharding 方式就是 HASH(key) MOD N (N 代表 DB 的數量)。

首先均衡性，我們沒辦法控制 Hash 的結果，因此就無法保證均衡性，而單調性的話，想像如果今天 N 的數量改變，原有的 Key 原本對應的 DB 編號可能會發生改變，這樣大部分的資料都要重新分配，想到就覺得很麻煩對吧。

看到這裡不知有沒有想到 Ep1 中的

HASH_SLOT = CRC16(key) mod 16384

是不是跟 HASH(key) MOD N 有點像，難道 Redis 用了一個很爛的 sharding 方式嗎？

別急，先讓我來介紹符合以上條件的 sharding 方式。

問題二：誰是大名鼎鼎的 Consistent Hashing？

提到 Key-Based Sharding 就會提到大名鼎鼎的 Consistent Hashing，它透過一個環來符合上面兩個條件。

首先我們以 CRC32 這個 Hashing Function 為例，他所產生出來的值一定是 32-bit 的數字，因此不管什麼 input 經過 CRC32，最後的 output range 一定介於 0 ~ 2³²-1 之間，之後我們將 0 ~ 2³²-1 的數字視為一個環 (下圖)，可以想像成一個時鐘，但有 2³²-1 格。

隨後經過以下兩個步驟就能完成 sharding：

step 1 : 我們將 DB 的唯一識別符 (e.g IP, ID etc) 經過 CRC32 產生出來的數字，放在環上

step 2 : 將資料的 Key 丟到 CRC32，並將產出來的數字也放到環上，隨後順時針往前走，第一個遇到的 DB 就是該資料的歸屬。

這樣的環遇到 DB 增加會發生什麼事勒？

上圖中，我們新增了 DB_4，在剛剛的分配步驟，Data_A 順時針前進後，第一個遇到的 DB 從 DB_3 變成 DB_4，因此在上面的案例中，要重新分配的資料只有 DB_1 到 DB_4 這個區段的資料，也就是 Data_A，相較於之前的HASH(key) MOD N 的方式，Consistent Hashing 盡可能降低了資料重分配的可能性，默默地就符合了單調性。

而均衡性，就採用一個簡單粗暴的方式 — Virtual Node，就是讓一個 DB 產生多個 Hash Value 並放在環上。

如上圖，DB_1–1 & DB_1–2 兩個節點都是 DB_1 的 Virtual Node，透過這種方式能縮短 DB 之間的 Range，就算有很多 Key 經過 CRC32 都落在很接近的 Range 中，該 Range 有比較有機會包含多個不同的 DB。

既然 Consistent Hashing 那麼神，Redis 大大為何不採用 Consistent Hashing？Hash Slot 跟 Consistent Hashing 又有啥區別？

問題三：為何 Redis 不用大名鼎鼎的 Consistent Hashing？

根據 Redis 官方說法，在設計 Redis Cluster 主要有三個目標：

高讀寫效能以及線性地水平擴展
寫入操作在一定的程度上是安全地，也就是寫入操作會盡可能地送到 Cluster 中穩定的節點，不會送到已經跟大部分節點失聯的節點上。
高可用性，當 Cluster 中某個節點掛點，會由 Slave 快速補上，不需要暫停整個 Cluster 做資料的搬移。

首先，Consistent Hashing 在 Cluster 有節點數量變動時，採用的方式是依照環上的順序重新分配資料到不同的節點，雖然重新分配的資料量可能不多，但這個重分配的過程，可能會影響系統的可用性以及一致性：

可用性：為了確保可用性，Cluster 在重新分配的時候，也要讓 Client 對資料做存取，但如果部分 Client 還不知道 Cluster 節點有變動，它就可能對錯誤節點進行讀寫，因此喪失一致性以及寫入安全。
一致性：若要確保 Client 讀寫的時候都在正確的節點，那麼 Cluster 在重新分配的時候，就不能接收 Client 的請求，降低了可用性。

有點類似 CAP 理論， C 跟Ａ只能選一個，但 Redis 說，小孩才做選擇，我全都要！

Redis 採用的 Hash Slot 雖然在 Cluster 初始化時就分配好，且不會隨著 Cluster 成員變更自動調整資料分布，但因為這個穩定的特性，結合上 Master-Slave 的架構，讓 Redis 盡可能達到 C & A 之間的平衡。

當 Cluster 有節點掛掉時：

因為 Slave 會補上，而這個補上的時間理論上也比資料分配來的快速，因此不會影響可用性，雖然會在一段很短的時間內不符合一致性，但 Redis 說：「Usually there are small windows where acknowledged writes can be lost」，不管你信不信，反正我是信了。

其實 Redis 有一些 configuration 的參數可用來管理 Master-Slave 機制 (e.g 怎樣的Slave可以成為Master，Master最少要幾個Slave)，透過正確的 configuration，就能盡可能在 Fail-Over 的時候維持 C & A。

當 Cluster 新增節點時：

Cluster 水平擴展時，Redis 並不會自動分配 Slots，而是要由開發人員自行透過指令決定要搬移哪些 Slots，而在搬移的過程中，Cluster 可以繼續 Client 的請求，如果 Client 讀寫到舊的 Node 且那筆資料已經搬走了，舊的 Node 就會跟 Client 別問我，問他，Client 就能把請求送到正確的 Node，維持可用性的時候，寫又能安全，這樣是不是有維持 C & A 特性？帥吧。

Hash Slot v.s Consistent Hashing：

Hash Slot 與 Consistent Hashing 最大差別就在於 Fail-Over 的處理方式，一個是 Slave 補上，一個是透過環重分配資料，而就是這個差別讓 Redis Cluster 在 Fail-Over 的過程中比 Consistent Hashing 穩定。

你說那 Consistent Hashing 也可以結合 Master-Slave 啊，你說的沒錯，但這樣 Consistent Hashing 透過環重分配資料的特性就只有在 Scale Up 時才能體現，而我的認知是，在使用 Cluster 時，比較常發生的是某台 Server 突然掛點，在這個前提下，Consistent Hashing 結合 Master-Slave ，環上資料會重分配的次數就很少，那這樣跟直接用 Hash Slot 也沒啥區別。

問題四：資料被分散了，我的 Transaction 怎麼辦？

Redis 提供 MULTI EXEC 的指令，確保 Redis 在執行多個指令時，能維持 Atomicity 的特性，要馬全部成功，要馬全部失敗，要死一起死的概念，但如果多個指令存取了不同 Key 怎麼辦，難道 Redis Cluster 實現了分散式 Transaction？Two-Phase Commit？

沒有喔，Redis 提供另一個更簡單的方式就是 Hash Tag，在 Redis 的 Key 中加上 {} 符號，這樣 Redis 在算 Hash Value 時只會用括號內的字串，也就是說 {key}_abc ＆ {key}_cba 這兩個 Key 一定會在同一個 Slot ，也就是同一台 Server，這樣就算一個 Transaction 讀寫多個 Key 只要確保這些 Key 都有相同的 Hash Tag 就沒問題了，是不是很棒～。

這時候我就在想，我也想把我們公司 Redis Server 換成 Cluster，雖然資料還沒有多到要做 Sharding，但有 Master-Slave 機制也能讓我多一些安全感，但如果直接用 Redis Cluster，我不就要把所有 Transaction 跟 Lua Script 裡面用到的 Key 都加上 Hash Tag 嗎？哇賽當我很閒？

好在 Redis 提供了另一套 Cluster 架構 — Sentinel，Sentinel 就有點像一個 Center Proxy 了，他不提供 Sharding 功能，但可以幫你管理背後的 Master-Slave，去 Monitor Redis 的狀態並處理 Fail-Over。

總結

Data Sharding 是資料庫將資料分散在不同 DB 的技術，主要 Sharding 的方式有 Key-Based，Range-Based 以及 Directory-Based。
Consistent Hashing 是能達到平衡性以及單調性的 Key-Based Sharding，使用環型結構去分配資料到不同節點。
Hash Slot 與 Consistent Hashing 最大差別就在於 Fail-Over 的處理方式，一個是 Master-Slave 輔助讓 Slave 補上，一個是透過環重新分配資料。
Redis 使用 Hash Tag 讓不同 Key 的資料也可以存在相同的 Slot 已此來解決 Transaction 問題。

下集預告

這篇文章講了 Redis 為何選擇 Hash Slot，以及用 Hash Tag 來輔助 Transaction，但我想大家更想知道 Redis 在 Cluster 中實際上是怎麼互相合作對吧？雖然 Ep1 有提到 Gossip，但是並沒有說實際交換了哪些訊息，下集就來講講 Redis 之間在講哪些八卦吧。

前言：