Redis Cluster 數據分片
介紹 Redis Cluster
Redis 集群是 Redis 提供的分散式資料庫方案， 集群通過分片（sharding） 來進行數據共享， 並提供複製和故障轉移功能。
節點
一個 Redis 集群通常由多個節點（node） 組成， 在剛開始的時候，每個節點都是相互獨立的，它們都處於一個只包含自己的集群當中， 要組建一個真正可工作的集群， 我們必須將各個獨立的節點連接起來，構成一個包含多個節點的集群。
連接各個節點的工作可以使用 cluster meet 命令來完成， 該命令的格式如下：cluster meet < ip > < port >。節點通過握手來將其他節點添加到自己所處的集群當中。向一個 node 節點發送 cluster meet 命令， 可以讓 node 節點與 ip 和 port 所指定的節點進行握手（handshake），當握手成功時， node 節點就會將 ip 和 port 所指定的節點添加到 node 節點當前所在的集群中。
一個節點就是一個運行在集群模式下的 Redis 伺服器，Redis 伺服器在啟動時會根據 cluster-enabled 配置選項是否為 yes 來決定是否開啟伺服器的集群模式。啟動伺服器時，伺服器判斷是否開啟集群模式：
- 如果 cluster-enabled 選項的值為 yes，則開啟伺服器的集群模式，成為一個節點；
- 如果 cluster-enabled 選項的值不為 yes，則開啟伺服器的單機（stand alone）模式，成為一個普通的 Redis 伺服器。
節點會繼續使用 redisServer 結構來保存伺服器的狀態， 使用 redisClient 結構來保存客戶端的狀態，至於那些只有在集群模式下才會用到的數據，節點將它們保存到了cluster.h/clusterNode 結構、 cluster.h/clusterLink 結構，以及 cluster.h/clusterState 結構裡面。
槽指派
Redis 集群通過分片的方式來保存資料庫中的鍵值對：集群的整個資料庫被分為 16384 個槽（slot），資料庫中的每個鍵都屬於這 16384 個槽的其中一個，集群中的每個節點可以處理 0 個或最多 16384 個槽。
通過向節點發送 cluster addslots 命令，我們可以將一個或多個槽指派（assign）給節點負責：cluster addslots < slot > [slot …]。
在 cluster addslots 命令執行完畢之後，節點會通過發送消息告知集群中的其他節點，自己目前正在負責處理哪些槽。也就是說，每個節點都會記錄哪些槽指派給了自己，而哪些槽又被指派給了其他節點。
集群的在線狀態：
- 上線狀態：當資料庫中的 16384 個槽都有節點在處理時，集群處於上線狀態（ok）；
- 下線狀態：相反地，如果資料庫中有任何一個槽沒有得到處理，那麼集群處於下線狀態（fail）。
節點保存槽指派資訊
Redis 集群的每個節點都會記錄自己負責處理哪些槽。
clusterNode 結構的 slots 屬性和 numslot 屬性記錄了節點負責處理哪些槽：
struct clusterNode {
// ...
unsigned char slots[16384/8];
int numslots;
// ...
};
slots 屬性是一個二進位位數組，這個數組的長度為 16384 / 8 = 2048 個位元組，共包含 16384 個二進位位。Redis 以 0 為起始索引，16383 為終止索引，對 slots 數組中的 16384 個二進位位進行編號，並根據索引 i 上的二進位位的值來判斷節點是否負責處理槽 i：
- 如果 slots 數組在索引 i 上的二進位位的值為 1，那麼表示節點負責處理槽 i。
- 如果 slots 數組在索引 i 上的二進位位的值為 0，那麼表示節點不負責處理槽 i。
numslots 屬性則記錄節點負責處理的槽的數量，也即是 slots 數組中值為 1 的二進位位的數量。
節點之間傳播槽指派資訊
一個節點除了會將自己負責處理的槽記錄在 clusterNode 結構的 slots 屬性和 numslots 屬性之外，它還會將自己的 slots 數組通過消息發送給集群中的其他節點，以此來告知其他節點自己目前負責處理哪些槽。
當節點 A 通過消息從節點 B 那裡接收到節點 B 的 slots 數組時， 節點 A 會在自己的 clusterState.nodes 字典中查找節點 B 對應的 clusterNode 結構，並對結構中的 slots 數組進行保存或者更新。
因為集群中的每個節點都會將自己的 slots 數組通過消息發送給集群中的其他節點， 並且每個接收到 slots 數組的節點都會將數組保存到相應節點的 clusterNode 結構裡面， 因此， 集群中的每個節點都會知道資料庫中的 16384 個槽分別被指派給了集群中的哪些節點。
記錄集群所有槽的指派資訊
Redis 集群的每個節點都會記錄集群所有槽的指派資訊
clusterState 結構中的 slots 數組記錄了集群中所有 16384 個槽的指派資訊：
typedef struct clusterState {
// ...
clusterNode *slots[16384];
// ...
} clusterState;
slots 數組包含 16384 個項，每個數組項都是一個指向 clusterNode 結構的指針：
- 如果 slots[i] 指針指向 NULL，那麼表示槽 i 尚未指派給任何節點。
- 如果 slots[i] 指針指向一個 clusterNode 結構，那麼表示槽 i 已經指派給了 clusterNode 結構所代表的節點。
如果只將槽指派資訊保存在各個節點的 clusterNode.slots 數組裡，會出現一些無法高效地解決的問題，而 clusterState.slots 數組的存在解決了這些問題：
- 如果節點只使用 clusterNode.slots 數組來記錄槽的指派資訊，那麼為了知道槽 i 是否已經被指派，或者槽 i 被指派給了哪個節點，程式需要遍歷 clusterState.nodes 字典中的所有 clusterNode 結構，檢查這些結構的 slots 數組，直到找到負責處理槽 i 的節點為止，這個過程的複雜度為 O(N)，其中 N 為 clusterState.nodes 字典保存的 clusterNode 結構的數量。
- 而通過將所有槽的指派資訊保存在 clusterState.slots 數組裡面，程式要檢查槽 i 是否已經被指派，又或者取得負責處理槽 i 的節點，只需要訪問 clusterState.slots[i] 的值即可，這個操作的複雜度僅為 O(1)。
clusterState.slots 數組記錄了集群中所有槽的指派資訊，而 clusterNode.slots 數組只記錄了 clusterNode 結構所代表的節點的槽指派資訊，這是兩個 slots 數組的關鍵區別所在。
客戶端向集群的節點發送命令
在對資料庫中的 16384 個槽都進行了指派之後，集群就會進入上線狀態，這時客戶端就可以向集群中的節點發送數據命令了。
當客戶端向節點發送與資料庫鍵有關的命令時，接收命令的節點會計算出命令要處理的資料庫鍵屬於哪個槽，並檢查這個槽是否指派給了自己：
- 如果鍵所在的槽正好就指派給了當前節點，那麼節點直接執行這個命令。
- 如果鍵所在的槽並沒有指派給當前節點，那麼節點會向客戶端返回一個 moved 錯誤，指引客戶端轉向（redirect）至正確的節點，並再次發送之前想要執行的命令。
1、計算鍵屬於哪個槽
節點使用以下演算法來計算給定鍵 key 屬於哪個槽：
def slot_number(key):
return CRC16(key) & 16383
其中 CRC16 (key) 語句用於計算鍵 key 的 CRC-16 校驗和，而 &16383 語句則用於計算出一個介於 0 至 16383 之間的整數作為鍵 key 的槽號。
使用 cluster keyslot < key > 命令可以查看一個給定鍵屬於哪個槽，這個命令就是通過調用上面給出的槽分配演算法來實現的。
2、判斷槽是否由當前節點負責處理
當節點計算出鍵所屬的槽 i 之後，節點就會檢查 clusterState.slots 數組中的項 i，判斷鍵所在的槽是否由自己負責：
- 如果 clusterState.slots[i] 等於 clusterState.myself，那麼說明槽 i 由當前節點負責，節點可以執行客戶端發送的命令。
- 如果 clusterState.slots[i] 不等於 clusterState.myself，那麼說明槽 i 並非由當前節點負責，節點會根據 clusterState.slots[i] 指向的 clusterNode 結構所記錄的節點 IP 和埠號，向客戶端返回 moved 錯誤，指引客戶端轉向至負責處理槽 i 的節點。
3、moved 錯誤的實現方法
當節點發現鍵所在的槽並非由自己負責處理的時候，節點就會向客戶端返回一個 moved 錯誤，指引客戶端轉向至負責處理槽的節點。
moved 錯誤的格式為：moved < slot > < ip > : < port >。其中 slot 為鍵所在的槽，而 ip 和 port 則是負責處理槽 slot 的節點的 IP 地址和埠號。
當客戶端接收到節點返回的 moved 錯誤時，客戶端會根據 moved 錯誤中提供的 IP 地址和埠號，轉向至負責處理槽 slot 的節點，並向該節點重新發送之前想要執行的命令。
一個集群客戶端通常會與集群中的多個節點創建套接字連接，而所謂的節點轉向實際上就是換一個套接字來發送命令。 如果客戶端尚未與想要轉向的節點創建套接字連接，那麼客戶端會先根據 moved 錯誤提供的 IP 地址和埠號來連接節點，然後再進行轉向。
被隱藏的 moved 錯誤：集群模式的 redis-cli 客戶端在接收到 moved 錯誤時，並不會列印出 moved 錯誤，而是根據 moved 錯誤自動進行節點轉向，並列印出轉向資訊，所以我們是看不見節點返回的 moved 錯誤的。但是，如果我們使用單機（stand alone）模式的 redis-cli 客戶端，moved 錯誤就會被客戶端列印出來。這是因為單機模式的 redis-cli 客戶端不清楚 moved 錯誤的作用， 所以它只會直接將 moved 錯誤直接列印出來，而不會進行自動轉向。
節點資料庫的實現
集群節點保存鍵值對以及鍵值對過期時間的方式，與單機 Redis 伺服器保存鍵值對以及鍵值對過期時間的方式完全相同。節點和單機伺服器在資料庫方面的一個區別是，節點只能使用 0 號資料庫，而單機 Redis 伺服器則沒有這一限制。
除了將鍵值對保存在資料庫裡面之外，節點還會用 clusterState 結構中的 slots_to_keys 跳躍表來保存槽和鍵之間的關係：
typedef struct clusterState {
// ...
zskiplist *slots_to_keys;
// ...
} clusterState;
slots_to_keys 跳躍表每個節點的分值（score）都是一個槽號，而每個節點的成員（member）都是一個資料庫鍵：
- 每當節點往資料庫中添加一個新的鍵值對時，節點就會將這個鍵以及鍵的槽號關聯到 slots_to_keys 跳躍表。
- 當節點刪除資料庫中的某個鍵值對時，節點就會在 slots_to_keys 跳躍表解除被刪除鍵與槽號的關聯。
通過在 slots_to_keys 跳躍表中記錄各個資料庫鍵所屬的槽，節點可以很方便地對屬於某個或某些槽的所有資料庫鍵進行批量操作，例如命令 cluster getkeysinslots < slot > < count > 命令可以返回最多 count 個屬於槽 slot 的資料庫鍵，而這個命令就是通過遍歷 slots_to_keys 跳躍表來實現的。
重新分片
介紹重新分片
Redis 集群的重新分片操作可以將任意數量已經指派給某個節點 （源節點）的槽改為指派給另一個節點（目標節點），並且相關槽所屬的鍵值對也會從源節點被移動到目標節點。
重新分片操作可以在線（online）進行，在重新分片的過程中，集群不需要下線，並且源節點和目標節點都可以繼續處理命令請求。
重新分片的實現原理
Redis 集群的重新分片操作是由 Redis 的集群管理軟體 redis-trib 負責執行的，Redis 提供了進行重新分片所需的所有命令，而 redis-trib 則通過向源節點和目標節點發送命令來進行重新分片操作。
redis-trib 對集群的單個槽 slot 進行重新分片的步驟如下：
- 目標節點準備導入槽 slot 的鍵值對：redis-trib 對目標節點發送 cluster setslot < slot > importing <source_id> 命令，讓目標節點準備好從源節點導入（import）屬於槽 slot 的鍵值對。
- 源節點準備遷移槽 slot 的鍵值對：redis-trib 對源節點發送 cluster setslot < slot > migrating <target_id> 命令，讓源節點準備好將屬於槽 slot 的鍵值對遷移（migrate）至目標節點。
- redis-trib 向源節點發送 cluster getkeysinslot < slot > < count > 命令，獲得最多 count 個屬於槽 slot 的鍵值對的鍵名（key name）。
- 對於步驟 3 獲得的每個鍵名，redis-trib 都向源節點發送一個 migrate <target_ip> <target_port> <key_name> 0 < timeout > 命令，將被選中的鍵原子地從源節點遷移至目標節點。
- 將屬於槽 slot 的鍵全部遷移至目標節點：重複執行步驟 3 和步驟 4，直到源節點保存的所有屬於槽 slot 的鍵值對都被遷移至目標節點為止。
- 將槽 slot 指派給目標節點：redis-trib 向集群中的任意一個節點發送 cluster setslot < slot > node <target_id> 命令，將槽 slot 指派給目標節點，這一指派資訊會通過消息發送至整個集群，最終集群中的所有節點都會知道槽 slot 已經指派給了目標節點。
- 如果重新分片涉及多個槽，那麼 redis-trib 將對每個給定的槽分別執行上面給出的步驟。
ask 錯誤
在進行重新分片期間，源節點向目標節點遷移一個槽的過程中，可能會出現這樣一種情況：屬於被遷移槽的一部分鍵值對保存在源節點裡面，而另一部分鍵值對則保存在目標節點裡面。
當客戶端向源節點發送一個與資料庫鍵有關的命令，並且命令要處理的資料庫鍵恰好就屬於正在被遷移的槽時：
- 源節點會先在自己的資料庫裡面查找指定的鍵，如果找到的話，就直接執行客戶端發送的命令。
- 相反地，如果源節點沒能在自己的資料庫裡面找到指定的鍵，那麼這個鍵有可能已經被遷移到了目標節點，源節點將向客戶端返回一個 ask 錯誤，指引客戶端轉向正在導入槽的目標節點，並再次發送之前想要執行的命令。
如果節點 A 正在遷移槽 i 至節點 B，那麼當節點 A 沒能在自己的資料庫中找到命令指定的資料庫鍵時，節點 A 會向客戶端返回一個 ask 錯誤，指引客戶端到節點 B 繼續查找指定的資料庫鍵。
源節點判斷是否需要向客戶端發送 ask 錯誤的整個過程。
被隱藏的 ask 錯誤：和接到 moved 錯誤時的情況類似，集群模式的 redis-cli 在接到 ask 錯誤時也不會列印錯誤，而是自動根據 ask 錯誤提供的 IP 地址和埠進行轉向動作。
ask 錯誤
如果節點收到一個關於鍵 key 的命令請求，並且鍵 key 所屬的槽 i 正好就指派給了這個節點，那麼節點會嘗試在自己的資料庫里查找鍵 key：
- 如果找到了的話，節點就直接執行客戶端發送的命令。
- 與此相反，如果節點沒有在自己的資料庫里找到鍵 key，那麼節點會檢查自己的 clusterState.migrating_slots_to[i]，看鍵 key 所屬的槽 i 是否正在進行遷移，如果槽 i 的確在進行遷移的話，那麼節點會向客戶端發送一個 ask 錯誤，引導客戶端到正在導入槽 i 的節點去查找鍵 key。
接到 ask 錯誤的客戶端會根據錯誤提供的 IP 地址和埠號，轉向至正在導入槽的目標節點，然後首先向目標節點發送一個 asking 命令， 之後再重新發送原本想要執行的命令。
asking 錯誤
當客戶端接收到 ask 錯誤並轉向至正在導入槽的節點時，客戶端會先向節點發送一個 asking 命令，然後才重新發送想要執行的命令，這是因為如果客戶端不發送 asking 命令，而直接發送想要執行的命令的話，那麼客戶端發送的命令將被節點拒絕執行，並返回 moved 錯誤。
asking 命令唯一要做的就是打開發送該命令的客戶端對應的實例結構的 REDIS_ASKING 標識，以下是該命令的偽程式碼實現：
def ASKING():
# 打開標識
client.flags |= REDIS_ASKING
# 向客戶端返回OK 回復
reply("OK")
在一般情況下，如果客戶端向節點發送一個關於槽 i 的命令，而槽 i 又沒有指派給這個節點的話，那麼節點將向客戶端返回一個 moved 錯誤；但是，如果節點的 clusterState.importing_slots_from[i] 顯示節點正在導入槽 i，並且發送命令的客戶端帶有 REDIS_ASKING 標識，那麼節點將破例執行這個關於槽 i 的命令一次。
需要注意的是，客戶端的 REDIS_ASKING 標識是一個一次性標識，當節點執行了一個帶有 REDIS_ASKING 標識的客戶端發送的命令之後，客戶端的 REDIS_ASKING 標識就會被移除。
節點判斷是否執行客戶端命令的過程
ask 錯誤和 moved 錯誤都會導致客戶端轉向，它們的區別在於：
- moved 錯誤代表槽的負責權已經從一個節點轉移到了另一個節點：在客戶端收到關於槽 i 的 moved 錯誤之後，客戶端每次遇到關於槽 i 的命令請求時，都可以直接將命令請求發送至 moved 錯誤所指向的節點，因為該節點就是目前負責槽 i 的節點。
- 與此相反，ask 錯誤只是兩個節點在遷移槽的過程中使用的一種臨時措施：在客戶端收到關於槽 i 的 ask 錯誤之後，客戶端只會在接下來的一次命令請求中將關於槽 i 的命令請求發送至 ask 錯誤所指示的節點， 但這種轉向不會對客戶端今後發送關於槽 i 的命令請求產生任何影響， 客戶端仍然會將關於槽 i 的命令請求發送至目前負責處理槽 i 的節點，除非 ask 錯誤再次出現。
參考資料
《Redis 設計與實現》書籍
