前言

大家好，我是田螺。

有位伙伴面試了字節(jié)，說有道題，他當(dāng)時(shí)答不上，大家一起來看看：redis的cluster集群原理，客戶端是怎樣知道該訪問哪個(gè)分片的。

我們應(yīng)該怎樣更好回答呢？可以分這幾個(gè)維度

• 為什么需要Redis Cluster？哨兵模式不香嗎？
• 客戶端是怎樣知道該訪問哪個(gè)分片的? (哈希槽)
• redis實(shí)例上并沒有相應(yīng)的數(shù)據(jù)，會怎么樣？(MOVED重定向和ASK重定向)
• 各個(gè)節(jié)點(diǎn)之間是怎么通信的呢(Gossip協(xié)議)
• 集群內(nèi)節(jié)點(diǎn)出現(xiàn)故障怎么辦（故障轉(zhuǎn)移）
• 加餐：Redis Cluster的Hash Slot 為什么是16384？

1. 為什么需要Redis Cluster？

哨兵模式基于主從模式，實(shí)現(xiàn)讀寫分離，它還可以自動切換，系統(tǒng)可用性更高。但是它每個(gè)節(jié)點(diǎn)存儲的數(shù)據(jù)是一樣的，浪費(fèi)內(nèi)存，并且不好在線擴(kuò)容。

因此，Reids Cluster集群（切片集群的實(shí)現(xiàn)方案）應(yīng)運(yùn)而生，它在Redis3.0加入的，實(shí)現(xiàn)了Redis的分布式存儲。對數(shù)據(jù)進(jìn)行分片，也就是說每臺Redis節(jié)點(diǎn)上存儲不同的內(nèi)容，來解決在線擴(kuò)容的問題。并且，它可以保存大量數(shù)據(jù)，即分散數(shù)據(jù)到各個(gè)Redis實(shí)例，還提供復(fù)制和故障轉(zhuǎn)移的功能。

比如你一個(gè)Redis實(shí)例保存15G甚至更大的數(shù)據(jù)，響應(yīng)就會很慢，這是因?yàn)镽edis RDB 持久化機(jī)制導(dǎo)致的，Redis會fork子進(jìn)程完成 RDB 持久化操作，fork執(zhí)行的耗時(shí)與 Redis 數(shù)據(jù)量成正相關(guān)。

這時(shí)候你很容易想到，把15G數(shù)據(jù)分散來存儲就好了嘛。這就是Redis切片集群的初衷。切片集群是啥呢？來看個(gè)例子，如果你要用Redis保存15G的數(shù)據(jù)，可以用單實(shí)例Redis，或者3臺Redis實(shí)例組成切片集群，對比如下：

切片集群和Redis Cluster的區(qū)別：Redis Cluster是從Redis3.0版本開始，官方提供的一種實(shí)現(xiàn)切片集群的方案。

圖片

既然數(shù)據(jù)是分片分布到不同Redis實(shí)例的，那客戶端到底是怎么確定想要訪問的數(shù)據(jù)在哪個(gè)實(shí)例上呢？我們一起來看下Reids Cluster是怎么做的哈。

2. 客戶端是怎樣知道該訪問哪個(gè)分片的?哈希槽

Redis Cluster方案采用哈希槽（Hash Slot），來處理數(shù)據(jù)和實(shí)例之間的映射關(guān)系。

一個(gè)切片集群被分為16384個(gè)slot（槽），每個(gè)進(jìn)入Redis的鍵值對，根據(jù)key進(jìn)行散列，分配到這16384插槽中的一個(gè)。使用的哈希映射也比較簡單，用CRC16算法計(jì)算出一個(gè)16bit的值，再對16384取模。數(shù)據(jù)庫中的每個(gè)鍵都屬于這16384個(gè)槽的其中一個(gè)，集群中的每個(gè)節(jié)點(diǎn)都可以處理這16384個(gè)槽。

集群中的每個(gè)節(jié)點(diǎn)負(fù)責(zé)一部分的哈希槽，假設(shè)當(dāng)前集群有A、B、C3個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)上負(fù)責(zé)的哈希槽數(shù) =16384/3，那么可能存在的一種分配：

• 節(jié)點(diǎn)A負(fù)責(zé)0~5460號哈希槽
• 節(jié)點(diǎn)B負(fù)責(zé)5461~10922號哈希槽
• 節(jié)點(diǎn)C負(fù)責(zé)10923~16383號哈希槽

客戶端給一個(gè)Redis實(shí)例發(fā)送數(shù)據(jù)讀寫操作時(shí)，如果這個(gè)實(shí)例上并沒有相應(yīng)的數(shù)據(jù)，會怎么樣呢？MOVED重定向和ASK重定向了解一下哈

3. 實(shí)例上并沒有相應(yīng)的數(shù)據(jù)，會怎么樣？(MOVED重定向和ASK重定向)

在Redis cluster模式下，節(jié)點(diǎn)對請求的處理過程如下：

• 通過哈希槽映射，檢查當(dāng)前Redis key是否存在當(dāng)前節(jié)點(diǎn)
• 若哈希槽不是由自身節(jié)點(diǎn)負(fù)責(zé)，就返回MOVED重定向
• 若哈希槽確實(shí)由自身負(fù)責(zé)，且key在slot中，則返回該key對應(yīng)結(jié)果
• 若Redis key不存在此哈希槽中，檢查該哈希槽是否正在遷出（MIGRATING）？
• 若Redis key正在遷出，返回ASK錯(cuò)誤重定向客戶端到遷移的目的服務(wù)器上
• 若哈希槽未遷出，檢查哈希槽是否導(dǎo)入中？
• 若哈希槽導(dǎo)入中且有ASKING標(biāo)記，則直接操作，否則返回MOVED重定向

3.1 Moved 重定向

客戶端給一個(gè)Redis實(shí)例發(fā)送數(shù)據(jù)讀寫操作時(shí)，如果計(jì)算出來的槽不是在該節(jié)點(diǎn)上，這時(shí)候它會返回MOVED重定向錯(cuò)誤，MOVED重定向錯(cuò)誤中，會將哈希槽所在的新實(shí)例的IP和port端口帶回去。這就是Redis Cluster的MOVED重定向機(jī)制。流程圖如下：

圖片

3.2 ASK 重定向

Ask重定向一般發(fā)生于集群伸縮的時(shí)候。集群伸縮會導(dǎo)致槽遷移，當(dāng)我們?nèi)ピ垂?jié)點(diǎn)訪問時(shí)，此時(shí)數(shù)據(jù)已經(jīng)可能已經(jīng)遷移到了目標(biāo)節(jié)點(diǎn)，使用Ask重定向可以解決此種情況。

圖片

4. 各個(gè)節(jié)點(diǎn)之間是怎么通信的呢(Gossip)

一個(gè)Redis集群由多個(gè)節(jié)點(diǎn)組成，各個(gè)節(jié)點(diǎn)之間是怎么通信的呢？通過Gossip協(xié)議！Gossip是一種謠言傳播協(xié)議，每個(gè)節(jié)點(diǎn)周期性地從節(jié)點(diǎn)列表中選擇 k 個(gè)節(jié)點(diǎn)，將本節(jié)點(diǎn)存儲的信息傳播出去，直到所有節(jié)點(diǎn)信息一致，即算法收斂了。

Gossip協(xié)議基本思想：一個(gè)節(jié)點(diǎn)想要分享一些信息給網(wǎng)絡(luò)中的其他的一些節(jié)點(diǎn)。于是，它周期性的隨機(jī)選擇一些節(jié)點(diǎn)，并把信息傳遞給這些節(jié)點(diǎn)。這些收到信息的節(jié)點(diǎn)接下來會做同樣的事情，即把這些信息傳遞給其他一些隨機(jī)選擇的節(jié)點(diǎn)。一般而言，信息會周期性的傳遞給N個(gè)目標(biāo)節(jié)點(diǎn)，而不只是一個(gè)。這個(gè)N被稱為fanout

Redis Cluster集群通過Gossip協(xié)議進(jìn)行通信，節(jié)點(diǎn)之前不斷交換信息，交換的信息內(nèi)容包括節(jié)點(diǎn)出現(xiàn)故障、新節(jié)點(diǎn)加入、主從節(jié)點(diǎn)變更信息、slot信息等等。gossip協(xié)議包含多種消息類型，包括ping，pong，meet，fail等等

圖片

• meet消息：通知新節(jié)點(diǎn)加入。消息發(fā)送者通知接收者加入到當(dāng)前集群，meet消息通信正常完成后，接收節(jié)點(diǎn)會加入到集群中并進(jìn)行周期性的ping、pong消息交換。
• ping消息：節(jié)點(diǎn)每秒會向集群中其他節(jié)點(diǎn)發(fā)送 ping 消息，消息中帶有自己已知的兩個(gè)節(jié)點(diǎn)的地址、槽、狀態(tài)信息、最后一次通信時(shí)間等
• pong消息：當(dāng)接收到ping、meet消息時(shí)，作為響應(yīng)消息回復(fù)給發(fā)送方確認(rèn)消息正常通信。消息中同樣帶有自己已知的兩個(gè)節(jié)點(diǎn)信息。
• fail消息：當(dāng)節(jié)點(diǎn)判定集群內(nèi)另一個(gè)節(jié)點(diǎn)下線時(shí)，會向集群內(nèi)廣播一個(gè)fail消息，其他節(jié)點(diǎn)接收到fail消息之后把對應(yīng)節(jié)點(diǎn)更新為下線狀態(tài)。

特別的，每個(gè)節(jié)點(diǎn)是通過集群總線(cluster bus) 與其他的節(jié)點(diǎn)進(jìn)行通信的。通訊時(shí)，使用特殊的端口號，即對外服務(wù)端口號加10000。例如如果某個(gè)node的端口號是6379，那么它與其它nodes通信的端口號是 16379。nodes 之間的通信采用特殊的二進(jìn)制協(xié)議。

5. 集群內(nèi)節(jié)點(diǎn)出現(xiàn)故障怎么辦（故障轉(zhuǎn)移）

Redis集群實(shí)現(xiàn)了高可用，當(dāng)集群內(nèi)節(jié)點(diǎn)出現(xiàn)故障時(shí)，通過故障轉(zhuǎn)移，以保證集群正常對外提供服務(wù)。

redis集群通過ping/pong消息，實(shí)現(xiàn)故障發(fā)現(xiàn)。這個(gè)環(huán)境包括主觀下線和客觀下線。

• 主觀下線：某個(gè)節(jié)點(diǎn)認(rèn)為另一個(gè)節(jié)點(diǎn)不可用，即下線狀態(tài)，這個(gè)狀態(tài)并不是最終的故障判定，只能代表一個(gè)節(jié)點(diǎn)的意見，可能存在誤判情況。

圖片

• 客觀下線：指標(biāo)記一個(gè)節(jié)點(diǎn)真正的下線，集群內(nèi)多個(gè)節(jié)點(diǎn)都認(rèn)為該節(jié)點(diǎn)不可用，從而達(dá)成共識的結(jié)果。如果是持有槽的主節(jié)點(diǎn)故障，需要為該節(jié)點(diǎn)進(jìn)行故障轉(zhuǎn)移。
• 假如節(jié)點(diǎn)A標(biāo)記節(jié)點(diǎn)B為主觀下線，一段時(shí)間后，節(jié)點(diǎn)A通過消息把節(jié)點(diǎn)B的狀態(tài)發(fā)到其它節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)C接受到消息并解析出消息體時(shí)，如果發(fā)現(xiàn)節(jié)點(diǎn)B的pfail狀態(tài)時(shí)，會觸發(fā)客觀下線流程；
• 當(dāng)下線為主節(jié)點(diǎn)時(shí)，此時(shí)Redis Cluster集群為統(tǒng)計(jì)持有槽的主節(jié)點(diǎn)投票，看投票數(shù)是否達(dá)到一半，當(dāng)下線報(bào)告統(tǒng)計(jì)數(shù)大于一半時(shí)，被標(biāo)記為客觀下線狀態(tài)。

 流程如下：

圖片

• 故障恢復(fù)：故障發(fā)現(xiàn)后，如果下線節(jié)點(diǎn)的是主節(jié)點(diǎn)，則需要在它的從節(jié)點(diǎn)中選一個(gè)替換它，以保證集群的高可用。流程如下：

圖片

• 資格檢查：檢查從節(jié)點(diǎn)是否具備替換故障主節(jié)點(diǎn)的條件。
• 準(zhǔn)備選舉時(shí)間：資格檢查通過后，更新觸發(fā)故障選舉時(shí)間。
• 發(fā)起選舉：到了故障選舉時(shí)間，進(jìn)行選舉。
• 選舉投票：只有持有槽的主節(jié)點(diǎn)才有票，從節(jié)點(diǎn)收集到足夠的選票（大于一半），觸發(fā)替換主節(jié)點(diǎn)操

6. 加餐：為什么Redis Cluster的Hash Slot 是16384？

對于客戶端請求過來的鍵值key，哈希槽=CRC16(key) % 16384，CRC16算法產(chǎn)生的哈希值是16bit的，按道理該算法是可以產(chǎn)生2^16=65536個(gè)值，為什么不用65536，用的是16384（2^14）呢？

大家可以看下作者的原始回答：

圖片

Redis 每個(gè)實(shí)例節(jié)點(diǎn)上都保存對應(yīng)有哪些slots，它是一個(gè)unsigned char slots[REDIS_CLUSTER_SLOTS/8]類型

圖片

• 在redis節(jié)點(diǎn)發(fā)送心跳包時(shí)需要把所有的槽放到這個(gè)心跳包里，如果slots數(shù)量是65536，占空間= 65536 / 8(一個(gè)字節(jié)8bit) / 1024(1024個(gè)字節(jié)1kB) =8kB，如果使用slots數(shù)量是16384，所占空間 =16384 / 8(每個(gè)字節(jié)8bit) / 1024(1024個(gè)字節(jié)1kB) = 2kB，可見16384個(gè)slots比 65536省 6kB內(nèi)存左右，假如一個(gè)集群有100個(gè)節(jié)點(diǎn),那每個(gè)實(shí)例里就省了600kB啦
• 一般情況下Redis cluster集群主節(jié)點(diǎn)數(shù)量基本不可能超過1000個(gè)，超過1000會導(dǎo)致網(wǎng)絡(luò)擁堵。對于節(jié)點(diǎn)數(shù)在1000以內(nèi)的Redis cluster集群，16384個(gè)槽位其實(shí)夠用了。

既然為了節(jié)省內(nèi)存網(wǎng)絡(luò)開銷，為什么 slots不選擇用8192（即16384/2）呢?

8192 / 8(每個(gè)字節(jié)8bit) / 1024(1024個(gè)字節(jié)1kB) = 1kB,只需要1KB！可以先看下Redis 把 Key 換算成所屬 slots 的方法

unsignedintkeyHashSlot(char*key,intkeylen){
ints,e;/*start-endindexesof{and}*/

for(s=0;s<keylen;s++)
if(key[s]=='{')break;

/*No'{'?Hashthewholekey.Thisisthebasecase.*/
if(s==keylen)returncrc16(key,keylen)&0x3FFF;

/*'{'found?Checkifwehavethecorresponding'}'.*/
for(e=s+1;e<keylen;e++)
if(key[e]=='}')break;

/*No'}'ornothingbetweeen{}?Hashthewholekey.*/
if(e==keylen||e==s+1)returncrc16(key,keylen)&0x3FFF;

/*Ifweareherethereisbotha{anda}onitsright.Hash
*whatisinthemiddlebetween{and}.*/
returncrc16(key+s+1,e-s-1)&0x3FFF;
}

Redis 將key換算成slots 的方法：其實(shí)就是是將crc16(key) 之后再和slots的數(shù)量進(jìn)行與計(jì)算

這里為什么用0x3FFF(16383)來計(jì)算,而不是16384呢？因?yàn)樵诓划a(chǎn)生溢出的情況下x % (2^n)等價(jià)于x & (2^n - 1)即x % 16384 == x & 16383

那到底為什么不用8192呢？

crc16 出來結(jié)果,理論上出現(xiàn)重復(fù)的概率為 1?65536,但實(shí)際結(jié)果重復(fù)概率可能比這個(gè)大不少,就像crc32 結(jié)果 理論上 1/40億 分之一,但實(shí)際有人測下來10萬碰撞的概率就比較大了。假如 slots 設(shè)置成 8192, 200個(gè)實(shí)例的節(jié)點(diǎn)情況下,理論值是 每40個(gè)不同key請求,命中就會失效一次,假如節(jié)點(diǎn)數(shù)增加到400,那就是20個(gè)請求。并且1kb 并不會比 2k 省太多,性價(jià)比不是特別高,所以可能 選16384會更為通用一點(diǎn)