Redis Cluster
Redis Cluster是Redis官方在Redis 3.0版本正式推出的高可用以及分布式的解決方案。
Redis Cluster由多個Redis實例組成的整體，數(shù)據(jù)按照槽(slot)存儲分布在多個Redis實例上，通過Gossip協(xié)議來進行節(jié)點之間通信。
Redis Cluster實現(xiàn)的功能：
? 將數(shù)據(jù)分片到多個實例(按照slot存儲)；
? 集群節(jié)點宕掉會自動failover；
? 提供相對平滑擴容(縮容)節(jié)點。
Redis Cluster暫未有的：
? 實時同步
? 強一致性
Redis Cluster分片實現(xiàn)
一般分片（Sharding）實現(xiàn)的方式有l(wèi)ist、range和hash(或者基于上述的組合方式)等方式。而Redis的實現(xiàn)方式是基于hash的分片方式，具體是虛擬槽分區(qū)。
虛擬槽分區(qū)
槽(slot):使用分散度良好的hash函數(shù)把所有數(shù)據(jù)映射到一個固定范圍的整數(shù)集合中，這個整數(shù)集合就是槽。
Redis Cluster槽: Redis Cluster槽的范圍是0 ~ 16383。槽是集群內(nèi)數(shù)據(jù)管理和遷移的基本單位。
分片的具體算法
Redis Cluster使用slot ?= CRC16(key) %16384來計算鍵key屬于哪個slot。（Redis先對key使用CRC16算法計算出一個結(jié)果，然后再把結(jié)果對16384求余，得到結(jié)果即跟Redis Cluster的slot對應(yīng)，也就是對應(yīng)數(shù)據(jù)存儲的槽數(shù)。）
(注: CRC16算法——循環(huán)冗余校驗(Cyclic Redundancy Check/Code),Redis使用的是CRC-16-CCITT標準，即G(x)為：x16+?x12+?x5+ 1。)
Redis Cluster中的每個分片只需要維護自己的槽以及槽所映射的鍵值數(shù)據(jù)。
Hash標簽
哈希標簽(hash tags)，在Redis集群分片中，可以通過哈希標簽來實現(xiàn)指定兩個及以上的Key在同一個slot中。只要Key包含“{…}”這種模式，Redis就會根據(jù)第一次出現(xiàn)的’{’和第一次出現(xiàn)的’}’之間的字符串進行哈希計算以獲取相對應(yīng)的slot數(shù)。如上Redis源碼實現(xiàn)。
所以如果要指定某些Key存儲到同一個slot中，只需要在命令Key的之后指定相同的“{…}”命名模式即可。
集群節(jié)點和槽
我們現(xiàn)在已經(jīng)知道，Redis Cluster中的keys被分割為16384個槽(slot)，如果一個槽一個節(jié)點的話，那Redis Cluster最大的節(jié)點數(shù)量也就是16384個。官方推薦最大節(jié)點數(shù)量為1000個左右。
（關(guān)于Redis為什么使用16384個槽，原作者有回答：why redis-cluster use 16384 slots?）
1當Redis Cluster中的16384個槽都有節(jié)點在處理時，集群處于上線狀態(tài)(ok)；
如果Redis Cluster中有任何一個槽沒有得到處理(或者某一分片的最后一個節(jié)點掛了)，那么集群處于下線狀態(tài)(fail)。（info cluster中的：cluster_state狀態(tài)）。那整個集群就不能對外提供服務(wù)。
Redis-3.0.0.rc1加入cluster-require-full-coverage參數(shù)，默認關(guān)閉，打開集群容忍部分失敗。
但是如果集群超過半數(shù)以上master掛掉，無論是否有slave集群進入fail狀態(tài)。
節(jié)點ID
Redis Cluster每個節(jié)點在集群中都有唯一的ID，該ID是由40位的16進制字符組成，具體是節(jié)點第一次啟動由linux的/dev/urandom生成。具體信息會保存在node.cnf配置文件中(該文件有Redis Cluster自動維護，可以通過參數(shù)cluster-config-file來指定路徑和名稱)，如果該文件被刪除，節(jié)點ID將會重新生成。（刪除以后所有的cluster和replication信息都沒有了）或者通過Cluster Reset強制請求硬重置。
節(jié)點ID用于標識集群中的每個節(jié)點，包括指定Replication Master。只要節(jié)點ID不改變，哪怕節(jié)點的IP和端口發(fā)生了改變，Redis Cluster可以自動識別出IP和端口的變化，并將變更的信息通過Gossip協(xié)議廣播給其他節(jié)點。
ClusterNode
Master 節(jié)點維護這一個16384/8字節(jié)的位序列，Master節(jié)點用bit來標識對于某個槽自己是否擁有。(判斷索引是不是為1即可)
slots屬性是一個二進制位數(shù)組(bit arry)，這個數(shù)組的長度為16384/8 = 2048個字節(jié)，共包含16384個二進制。
Redis Cluster對slots數(shù)組中的16384個二進制位進行編號：從0為起始索引，16383為終止索引。
根據(jù)索引i上的二進制位的值來判斷節(jié)點是否負責(zé)處理槽i：
?slots數(shù)組在索引i上的二進制位的值為1，即表示該節(jié)點負責(zé)處理槽i；
?slots數(shù)組在索引i上的二進制位的值為0，即表示該節(jié)點不負責(zé)處理槽i；
示例1：（如下節(jié)點負責(zé)處理slot0-slot7）
即在Redis Cluster中Master節(jié)點使用bit(0)和bit(1)來標識對某個槽是否擁有，而Master只要判斷序列第二位的值是不是1即可，時間復(fù)雜度為O(1)。
numslots屬性記錄節(jié)點負責(zé)處理的槽的數(shù)量，也就是slots數(shù)組中值為1的二進制位的數(shù)量。上圖中節(jié)點處理的槽數(shù)量為8個。
ClusterState
集群中所有槽的分配信息都保存在ClusterState數(shù)據(jù)結(jié)構(gòu)的slots數(shù)組中，程序要檢查槽i是否已經(jīng)被分配或者找出處理槽i的節(jié)點，只需要訪問clusterState.slots[i]的值即可，時間復(fù)雜度為O(1)。
slots數(shù)組包含16384個項，每個數(shù)組項都是一個指向clusterNode結(jié)構(gòu)的指針：
?如果slots[i]指針指向null，那么表示槽i尚未指派給任何節(jié)點；
?如果slots[i]指針指向一個clusterNode結(jié)構(gòu)，那么表示槽i已經(jīng)指派給了clusterNode結(jié)構(gòu)所代表的節(jié)點。
示例2：
1. ?slots[0]至slots[4999]的指針都指向端口為6381的節(jié)點，即槽0到4999都由節(jié)點6381負責(zé)處理；
2. ?slots[5000]至slots[9999]的指針都指向端口為6382的節(jié)點，即槽5000到9999都由節(jié)點6382負責(zé)處理；
3.?slots[10000]至slots[16383]的指針都指向端口為6383的節(jié)點，即槽10000到16384都由節(jié)點6383負責(zé)處理。
數(shù)組 clusterNode.slots和clusterState.slots：
? clusterNode.slots數(shù)組記錄了clusterNode結(jié)構(gòu)所代表的節(jié)點的槽指派信息（每個節(jié)點負責(zé)哪些槽）。
? clusterState.slots數(shù)組記錄了集群中所有槽的指派信息。
? 如果需要查看某個節(jié)點的槽指派信息，只需要將相應(yīng)節(jié)點的clusterNode.slots數(shù)組整個發(fā)送出去即可。
? 但是如果需要查看槽i是否被分配或者分配給了哪個節(jié)點，就需要遍歷clusterState.nodes字典中所有clusterNode結(jié)構(gòu)，檢查這些結(jié)構(gòu)的slots數(shù)組，直到遍歷到負責(zé)處理槽i的節(jié)點為止，這個過程的時間復(fù)雜度為O(N)，N是clusterState.nodes字典保存的clusterNode結(jié)構(gòu)的數(shù)量。
? 引入clusterState.slots ,將所有槽的指派信息保存在clusterState.slots數(shù)組里面，程序要檢查槽i是否已經(jīng)被指派，或者查看負責(zé)處理槽i的節(jié)點，只需要訪問clusterState.slots[i]的值即可，這個操作的時間復(fù)雜度為O(1)。
? 如果只使用clusterState.slots數(shù)組(不引入clusterNode.slots)，如果要將節(jié)點A的槽指派信息傳播給其他節(jié)點時，必須先遍歷整個clusterState.slots數(shù)組，記錄節(jié)點A負責(zé)處理哪些槽，然后再發(fā)送給其他節(jié)點。比直接發(fā)送clusterNode.slots數(shù)組要低效的多。
Redis Cluster節(jié)點通信
Redis Cluster采用P2P的Gossip協(xié)議，Gossip協(xié)議的原理就是每個節(jié)點與其他節(jié)點間不斷通信交換信息，一段時間后節(jié)點信息一致，每個節(jié)點都知道集群的完整信息。
Redis Cluster通信過程：
(1)集群中的每個節(jié)點都會單獨開辟一個TCP通道，用于節(jié)點之間彼此通信，通信端口號在基礎(chǔ)端口上加10000；
(2)每個節(jié)點在固定周期內(nèi)通過特定規(guī)則選擇幾個節(jié)點發(fā)送ping消息；
(3)接收到ping消息的節(jié)點用pong消息作為響應(yīng)。
集群中每個節(jié)點通過一定規(guī)則挑選要通信的節(jié)點，每個節(jié)點可能知道全部節(jié)點，也可能僅知道部分節(jié)點，
只要這些節(jié)點彼此可以正常通信，最終它們會達到一致的狀態(tài)。當節(jié)點出故障、新節(jié)點加入、主從角色變化、槽信息變更等事件發(fā)生時，通過不斷的ping/pong消息通信，經(jīng)過一段時間后所有的節(jié)點都會知道整個集群全部節(jié)點的最新狀態(tài)，從而達到集群狀態(tài)同步的目的。
Gossip消息
Gossip協(xié)議的主要職責(zé)就是信息交換，信息交換的載體就是節(jié)點彼此發(fā)送的Gossip消息，常用的Gossip消息可分為：
? meet消息：用于通知新節(jié)點加入。消息發(fā)送者通知接收者加入到當前集群，meet消息通信正常完成后，接收節(jié)點會加入到集群中并進行周期性的ping、pong消息交換；
? ping消息：集群內(nèi)交換最頻繁的消息，集群內(nèi)每個節(jié)點每秒向多個其他節(jié)點發(fā)送ping消息，用于檢測節(jié)點是否在線和交換彼此狀態(tài)信息。ping消息發(fā)送封裝了自身節(jié)點和部分其他節(jié)點的狀態(tài)數(shù)據(jù)。
? pong消息：當接收到ping、meet消息時，作為響應(yīng)消息回復(fù)給發(fā)送方確認消息正常通信。pong消息內(nèi)部封裝了自身狀態(tài)數(shù)據(jù)。節(jié)點也可以向集群內(nèi)廣播自身的pong消息來通知整個集群對自身狀態(tài)進行更新。
? fail消息：當節(jié)點判定集群內(nèi)另一個節(jié)點下線時，會向集群內(nèi)廣播一個fail消息，其他節(jié)點接收到fail消息之后把對應(yīng)節(jié)點更新為下線狀態(tài)。
消息格式：
所有的消息格式劃分為：消息頭和消息體。
消息頭包含發(fā)送節(jié)點自身狀態(tài)數(shù)據(jù)，接收節(jié)點根據(jù)消息頭就可以獲取到發(fā)送節(jié)點的相關(guān)數(shù)據(jù)。
消息格式數(shù)據(jù)結(jié)構(gòu)
消息頭：包含自身的狀態(tài)數(shù)據(jù)，發(fā)送節(jié)點關(guān)鍵信息，如節(jié)點id、槽映等節(jié)點標識(主從角色，是否下線)等。
消息格式數(shù)據(jù)結(jié)構(gòu)
消息體：
定義發(fā)送消息的數(shù)據(jù)。
消息體在Redis內(nèi)部采用clusterMsgData結(jié)構(gòu)聲明：
通信消息處理流程
當接收到ping、meet消息時，接收節(jié)點會解析消息內(nèi)容并根據(jù)自身的識別情況做出相應(yīng)處理：
接收節(jié)點收到ping/meet消息時，執(zhí)行解析消息頭和
消息體流程：
? 解析消息頭過程：消息頭包含了發(fā)送節(jié)點的信息，如果發(fā)送節(jié)點是新節(jié)點且消息是meet類型，則加入到本地節(jié)點列表；如果是已知節(jié)點，則嘗試更新發(fā)送節(jié)點的狀態(tài)，如槽映射關(guān)系、主從角色等狀態(tài)。
? 解析消息體過程：如果消息體的clusterMsgDataGossip數(shù)組包含的節(jié)點是新節(jié)點，則嘗試發(fā)起與新節(jié)點的meet握手流程；如果是已知節(jié)點，則根據(jù)clusterMsgDataGossip中的flags字段判斷該節(jié)點是否下線，用于故障轉(zhuǎn)移。
消息處理完后回復(fù)pong消息，內(nèi)容同樣包含消息頭和消息體，發(fā)送節(jié)點接收到回復(fù)的pong消息后，采用類似的流程解析處理消息并更新與接收節(jié)點最后信息時間，完成一次消息通信。
通信規(guī)則
Redis集群內(nèi)節(jié)點通信采用固定頻率(定時任務(wù)每秒執(zhí)行10次)。由于內(nèi)部需要頻繁地進行節(jié)點信息交換，而ping/pong消息會攜帶當前節(jié)點和部分其他節(jié)點的狀態(tài)數(shù)據(jù)，勢必會加重帶寬和計算的負擔(dān)。
? 通信節(jié)點選擇過多可以讓信息及時交換，但是成本過高；
? 通信節(jié)點選擇過少會降低集群內(nèi)所有節(jié)點彼此信息交換頻率，從而影響故障判定、新節(jié)點發(fā)現(xiàn)等需求的速度。
節(jié)點選擇
消息交換的成本主要體現(xiàn)在單位時間選擇發(fā)送消息的節(jié)點數(shù)量和每個消息攜帶的數(shù)據(jù)量。
(1)選擇發(fā)送消息的節(jié)點數(shù)量
集群內(nèi)每個節(jié)點維護定時任務(wù)默認每秒執(zhí)行10次，每秒會隨機選擇5個節(jié)點找出最久沒有通信的節(jié)點發(fā)送ping消息，用于Gossip信息交換的隨機性。每100毫秒都會掃描本地節(jié)點列表，如果發(fā)現(xiàn)節(jié)點最后一次接受pong消息的時間大于cluster_node_timeout/2，則立刻發(fā)送ping消息,防止該節(jié)點信息太長時間未更新。根據(jù)以上規(guī)則得出每個節(jié)點每秒需要發(fā)送ping消息的數(shù)量=1+10*num(node.pong_received> cluster_node_timeout/2)，因此cluster_node_timeout參數(shù)對消息發(fā)送的節(jié)點數(shù)量影響非常大。當我們的帶寬資源緊張時，可以適當調(diào)大此參數(shù)。但是如果cluster_node_timeout過大會影響消息交換的頻率從而影響故障轉(zhuǎn)移、槽信息更新、新節(jié)點發(fā)現(xiàn)的速度。因此需要根據(jù)業(yè)務(wù)容忍度和資源消耗進行平衡。同時整個集群消息總交換量也跟節(jié)點數(shù)成正比。
(2)消息數(shù)據(jù)量
每個ping消息的數(shù)據(jù)量體現(xiàn)在消息頭和消息體中，其中消息頭主要占用空間的字段是myslots[CLUSTER_SLOTS/8]，占用2KB，這塊空間占用相對固定。消息體會攜帶一定數(shù)量的其他節(jié)點信息用于信息交換。而消息體攜帶數(shù)據(jù)量跟集群的節(jié)點數(shù)量相關(guān)，集群越大每次消息通信的成本也就更高。
通信開銷
Redis Cluster內(nèi)節(jié)點通信自身開銷：
(1)節(jié)點自身信息，主要是自己負責(zé)的slots信息：slots[CLUSTER_SLOTS/8]，占用2KB;
(2)攜帶總節(jié)點1/10的其他節(jié)點的狀態(tài)信息（1個節(jié)點的狀態(tài)數(shù)據(jù)約為104byte）
注：并不是所有的都是攜帶十分之一的節(jié)點信息的。
如果total_nodes/10小于3，那就至少攜帶3個節(jié)點信息；
如果total_nodes/10大于total_nodes-2，最多攜帶total_nodes-2個節(jié)點信息；
Else就total_nodes/10個節(jié)點信息。
通信開銷
節(jié)點狀態(tài)信息：clusterMsgDataGossip，ping、meet、pong采用clusterMsgDataGossip數(shù)組作為消息體。
所以每個Gossip消息大小為2KB+total_nodes/10*104b
Redis Cluster帶寬消耗主要為：業(yè)務(wù)操作(讀寫)消耗+Gossip消息消耗。
我們現(xiàn)在假設(shè)節(jié)點數(shù)為64*2=128，floor(122)=12：
每個Gossip消息的大小約為：2KB+12*104b ≈ 3KB。
根據(jù)之前的每個節(jié)點每秒需要發(fā)送ping消息的數(shù)量=1+10*num(node.pong_received> cluster_node_timeout/2)
假設(shè)：cluster_node_timeout為15秒時，num=20，即開銷=3KB*(1+10*20)*2*20=25MB/s；
cluster_node_timeout為30秒時，num=5，即開銷=3KB*(1+10*5)*2*20=6MB/s。
可以看出影響Gossip開銷的主要兩點：Cluster Redis的節(jié)點數(shù)和cluster_node_timeout設(shè)置的閾值：
那如果節(jié)點越多，Gossip消息就越大，最近接收pong消息時間間隔大于cluster_node_timeout/2秒的節(jié)點也會越多，那么帶寬的開銷越大。
所以得出如下結(jié)論：
(1)盡量避免大集群，針對大集群就拆分出去；
(2)如果某些場景必須使用大集群，那就可以通過增大cluster_node_timeout來降低帶寬的消耗，但是會影響failover的時效，這個可以根據(jù)業(yè)務(wù)場景和集群具體狀態(tài)評估；
(3）docker的分配問題，將大集群打散到小集群的物理機上，可以平衡和更高效的利用資源。
