Redis Cluster

Redis Cluster是Redis官方在Redis 3.0版本正式推出的高可用以及分布式的解決方案。

Redis Cluster由多個Redis實例組成的整體卦洽，數(shù)據(jù)按照槽(slot)存儲分布在多個Redis實例上，通過Gossip協(xié)議來進行節(jié)點之間通信。

Redis Cluster

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標(biāo)準(zhǔn)痢法，即G(x)為：x16+?x12+?x5+ 1。)

Redis Cluster中的每個分片只需要維護自己的槽以及槽所映射的鍵值數(shù)據(jù)杜顺。

Redis Cluster 分片實現(xiàn)

Hash標(biāo)簽

哈希標(biāo)簽(hash tags)财搁，在Redis集群分片中，可以通過哈希標(biāo)簽來實現(xiàn)指定兩個及以上的Key在同一個slot中躬络。只要Key包含“{…}”這種模式尖奔，Redis就會根據(jù)第一次出現(xiàn)的’{’和第一次出現(xiàn)的’}’之間的字符串進行哈希計算以獲取相對應(yīng)的slot數(shù)。如上Redis源碼實現(xiàn)穷当。

所以如果要指定某些Key存儲到同一個slot中越锈，只需要在命令Key的之后指定相同的“{…}”命名模式即可。

Redis 分片源碼

集群節(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?）

槽與分片節(jié)點

1當(dāng)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ù)，默認(rèn)關(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用于標(biāo)識集群中的每個節(jié)點俊扭，包括指定Replication Master勾徽。只要節(jié)點ID不改變，哪怕節(jié)點的IP和端口發(fā)生了改變统扳，Redis Cluster可以自動識別出IP和端口的變化，并將變更的信息通過Gossip協(xié)議廣播給其他節(jié)點畅姊。

ClusterNode

ClusterNode 數(shù)據(jù)結(jié)構(gòu)

Master 節(jié)點維護這一個16384/8字節(jié)的位序列咒钟，Master節(jié)點用bit來標(biāo)識對于某個槽自己是否擁有。(判斷索引是不是為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）

示例1

即在Redis Cluster中Master節(jié)點使用bit(0)和bit(1)來標(biāo)識對某個槽是否擁有供屉，而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é)點吃衅。

數(shù)據(jù)結(jié)構(gòu) ClusterState

示例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é)處理趣效。

示例2

數(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)报账。當(dāng)節(jié)點出故障研底、新節(jié)點加入、主從角色變化透罢、槽信息變更等事件發(fā)生時榜晦，通過不斷的ping/pong消息通信，經(jīng)過一段時間后所有的節(jié)點都會知道整個集群全部節(jié)點的最新狀態(tài)羽圃，從而達到集群狀態(tài)同步的目的乾胶。

Gossip消息

Gossip協(xié)議的主要職責(zé)就是信息交換，信息交換的載體就是節(jié)點彼此發(fā)送的Gossip消息朽寞，常用的Gossip消息可分為：

? meet消息：用于通知新節(jié)點加入识窿。消息發(fā)送者通知接收者加入到當(dāng)前集群，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消息：當(dāng)接收到ping、meet消息時炼幔，作為響應(yīng)消息回復(fù)給發(fā)送方確認(rèn)消息正常通信秋茫。pong消息內(nèi)部封裝了自身狀態(tài)數(shù)據(jù)。節(jié)點也可以向集群內(nèi)廣播自身的pong消息來通知整個集群對自身狀態(tài)進行更新乃秀。

? fail消息：當(dāng)節(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é)點標(biāo)識(主從角色耀态，是否下線)等轮傍。

消息頭源碼定義

消息格式數(shù)據(jù)結(jié)構(gòu)

消息體：

定義發(fā)送消息的數(shù)據(jù)。

消息體在Redis內(nèi)部采用clusterMsgData結(jié)構(gòu)聲明：

消息體源碼定義

通信消息處理流程

當(dāng)接收到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消息會攜帶當(dāng)前節(jié)點和部分其他節(jié)點的狀態(tài)數(shù)據(jù)疼约，勢必會加重帶寬和計算的負擔(dān)。

? 通信節(jié)點選擇過多可以讓信息及時交換蝙泼，但是成本過高程剥；

? 通信節(jié)點選擇過少會降低集群內(nèi)所有節(jié)點彼此信息交換頻率，從而影響故障判定汤踏、新節(jié)點發(fā)現(xiàn)等需求的速度织鲸。

Redis Cluster 通信規(guī)則

節(jié)點選擇

消息交換的成本主要體現(xiàn)在單位時間選擇發(fā)送消息的節(jié)點數(shù)量和每個消息攜帶的數(shù)據(jù)量舔腾。

(1)選擇發(fā)送消息的節(jié)點數(shù)量

集群內(nèi)每個節(jié)點維護定時任務(wù)默認(rèn)每秒執(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ù)量影響非常大丘损。當(dāng)我們的帶寬資源緊張時普办，可以適當(dāng)調(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é)點信息远寸。

Gossip 通信攜帶其他節(jié)點數(shù)量判斷源碼

通信開銷

節(jié)點狀態(tài)信息：clusterMsgDataGossip，ping屠凶、meet驰后、pong采用clusterMsgDataGossip數(shù)組作為消息體。

節(jié)點狀態(tài)信息定義

所以每個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的分配問題搞隐，將大集群打散到小集群的物理機上，可以平衡和更高效的利用資源远搪。