前文回顧
建議前面文章沒看過的同學先看下前面的文章：
「老司機帶你玩轉(zhuǎn)面試（1）：緩存中間件 Redis 基礎(chǔ)知識以及數(shù)據(jù)持久化」
「老司機帶你玩轉(zhuǎn)面試（2）：Redis 過期策略以及緩存雪崩庭呜、擊穿、穿透」
「老司機帶你玩轉(zhuǎn)面試（3）：Redis 高可用之主從模式」
「老司機帶你玩轉(zhuǎn)面試（4）：Redis 高可用之哨兵模式」
簡介
之前介紹的 Redis 的高可用方案：主從模式或者說哨兵模式峡迷，都只是在解決高可用的問題装诡，比如說主從模式解決了讀高可用润脸，哨兵模式解決了寫高可用怔球。
如果我們需要緩存的數(shù)據(jù)量比較少，幾個 G 足夠用了驼抹，那么這兩種方案的高可用模式完全可以滿足需求桑孩，一個 master 對多個 salve ，需要幾個 salve 跟讀的吞吐量相關(guān)框冀，然后再搞一個 sentinel 集群去保證 Redis 主從模式的高可用流椒。
但是如果我們有大量的數(shù)據(jù)需要進緩存，單機的存儲容量無法滿足的時候明也，怎么辦宣虾？
這時，需要用到分布式緩存温数，就在幾年前绣硝，想用分布式緩存還得借助中間件來實現(xiàn)，比如當時風靡一時的 codis 撑刺，或者說還有 twemproxy 鹉胖。在使用上，我們對 Redis 中間件進行讀寫操作够傍， Redis 中間件負責將我們的數(shù)據(jù)分布式的存儲在多臺機器上的 Redis 實例中甫菠。
而 Redis 也是不斷在發(fā)展的，終于在 3.0 的版本中（其實對現(xiàn)在來講也是比較早的版本了冕屯，現(xiàn)在的版本都 6.0 了）寂诱，原生支持了集群模式。
可以做到在多臺機器上安聘，部署多個 Redis 實例痰洒，每個實例存儲一部分的數(shù)據(jù)，同時每個 Redis 主實例可以掛載 Redis 從實例搞挣，實現(xiàn)了 Redis 主實例掛了带迟，會自動切換到 Redis 從實例上來。
除了實現(xiàn)了分布式存儲以外囱桨，還順便實現(xiàn)了高可用仓犬。
分布式尋址算法
Redis Cluster 的數(shù)據(jù)是分布式存儲的，這就必然會引發(fā)一個問題舍肠，假如我有 3 個節(jié)點搀继，我如何知道一個 key 是存在這 3 個節(jié)點的哪一個節(jié)點上，取數(shù)的時候如何準確的找到對應(yīng)的節(jié)點將數(shù)據(jù)取出來翠语？這就要用到分布式尋址算法了叽躯。
常見的分布式尋址算法有兩種：
- hash 算法
- 一致性 hash 算法
hash 算法
hash 算法是對 key 進行 hash 運算后取值，然后對節(jié)點的數(shù)量取模肌括。
接著將 key 存入對應(yīng)的節(jié)點点骑，但是，一旦其中某個節(jié)點宕機，所有的請求過來黑滴，都會基于最新的存活的節(jié)點數(shù)量進行取模運算憨募，這就會導(dǎo)致大多數(shù)的請求無法拿到緩存數(shù)據(jù)。
舉個例子袁辈，一開始我有 3 個節(jié)點菜谣，這時大家正常的取模運算將數(shù)據(jù)基本均勻的存在了 3 個節(jié)點上，突然宕機了一臺晚缩，現(xiàn)在只剩下 2 個有效的節(jié)點了尾膊，這時所有的運算都會基于最新的 2 個節(jié)點進行取模運算，原來的 key 對 2 進行取模運算后荞彼，顯然和對 3 進行取模運算得到的結(jié)果是不一樣的冈敛。
結(jié)果是大量的數(shù)據(jù)請求會直接打在 DB 上，這是不可容忍的卿泽。
一致性 hash 算法
一致性 hash 算法將整個 hash 值空間組織成一個虛擬的圓環(huán)莺债，整個空間按順時針方向組織，下一步將各個 master 節(jié)點（使用服務(wù)器的 ip 或主機名）進行 hash签夭。這樣就能確定每個節(jié)點在其哈希環(huán)上的位置。
來看一個經(jīng)典的一致性 hash 算法的環(huán)狀示意圖：
來了一個 key椎侠，首先計算 hash 值第租，并確定此數(shù)據(jù)在環(huán)上的位置，從此位置沿環(huán)順時針「行走」我纪，遇到的第一個 master 節(jié)點就是 key 所在位置慎宾。
在一致性哈希算法中，如果一個節(jié)點掛了浅悉，受影響的數(shù)據(jù)僅僅是此節(jié)點到環(huán)空間前一個節(jié)點（沿著逆時針方向行走遇到的第一個節(jié)點）之間的數(shù)據(jù)趟据，其它不受影響。增加一個節(jié)點也同理术健。
一致性哈希算法在節(jié)點太少時汹碱，容易因為節(jié)點分布不均勻而造成緩存熱點的問題。為了解決這種熱點問題荞估，一致性 hash 算法引入了虛擬節(jié)點機制咳促，即對每一個節(jié)點計算多個 hash，每個計算結(jié)果位置都放置一個虛擬節(jié)點勘伺。這樣就實現(xiàn)了數(shù)據(jù)的均勻分布跪腹，負載均衡。
Redis Cluster 的 hash slot 算法
Redis Cluster 的實現(xiàn)方案十分的聰明飞醉，它的分區(qū)方式采用了虛擬槽分區(qū)冲茸。
Redis Cluster 首先會預(yù)設(shè)虛擬槽，每個槽就相當于一個數(shù)字，有一定范圍轴术，每個槽映射一個數(shù)據(jù)子集蹲盘。
Redis Cluster中預(yù)設(shè)虛擬槽的范圍為 0 到 16383
- Redis Cluster 會把 16384 個槽按照節(jié)點數(shù)量進行平均分配，由節(jié)點進行管理膳音。
- 當一個 key 過來的時候召衔，會對這個 key 按照 CRC16 規(guī)則進行 hash 運算。
- 把 hash 結(jié)果對 16383 進行取余祭陷。
- 把余數(shù)發(fā)送給 Redis 節(jié)點苍凛。
- 節(jié)點接收到數(shù)據(jù)，驗證是否在自己管理的槽編號的范圍：
- 如果在自己管理的槽編號范圍內(nèi)兵志，則把數(shù)據(jù)保存到數(shù)據(jù)槽中醇蝴，然后返回執(zhí)行結(jié)果。
- 如果在自己管理的槽編號范圍外想罕，則會把數(shù)據(jù)發(fā)送給正確的節(jié)點悠栓，由正確的節(jié)點來把數(shù)據(jù)保存在對應(yīng)的槽中。
注意：Redis Cluster 的節(jié)點之間會共享消息按价，每個節(jié)點都會知道是哪個節(jié)點負責哪個范圍內(nèi)的數(shù)據(jù)槽
虛擬槽分布方式中惭适，由于每個節(jié)點管理一部分數(shù)據(jù)槽，數(shù)據(jù)保存到數(shù)據(jù)槽中楼镐。當節(jié)點擴容或者縮容時癞志，對數(shù)據(jù)槽進行重新分配遷移即可，數(shù)據(jù)不會丟失框产。
節(jié)點內(nèi)部通信機制
在分布式的存儲方式中凄杯，還有另外一個點需要我們關(guān)注，那就是集群之間的內(nèi)部通信方式秉宿，畢竟整個集群是需要知道當前集群中有多少有效的節(jié)點戒突，這些節(jié)點分配的 ip 以及一些其他的數(shù)據(jù)，這些數(shù)據(jù)我們可以稱之為元數(shù)據(jù)描睦。
集群元數(shù)據(jù)的維護有兩種方式：集中式膊存、 Gossip 協(xié)議。而 Redis Cluster 節(jié)點間采用 Gossip 協(xié)議進行通信酌摇。
集中式是將集群元數(shù)據(jù)（節(jié)點信息膝舅、故障等等）幾種存儲在某個節(jié)點上。集中式元數(shù)據(jù)集中存儲的一個典型代表窑多，就是大數(shù)據(jù)領(lǐng)域的 storm 仍稀。它是分布式的大數(shù)據(jù)實時計算引擎，是集中式的元數(shù)據(jù)存儲的結(jié)構(gòu)埂息，底層基于 zookeeper （分布式協(xié)調(diào)的中間件）對所有元數(shù)據(jù)進行存儲維護技潘。
Redis 維護集群元數(shù)據(jù)采用另一個方式遥巴， Gossip 協(xié)議，所有節(jié)點都持有一份元數(shù)據(jù)享幽，不同的節(jié)點如果出現(xiàn)了元數(shù)據(jù)的變更铲掐，就不斷將元數(shù)據(jù)發(fā)送給其它的節(jié)點，讓其它節(jié)點也進行元數(shù)據(jù)的變更值桩。
Gossip 協(xié)議
Gossip 協(xié)議是一種非常有意思的協(xié)議摆霉，它的過程是由一個種子節(jié)點發(fā)起，它會隨機的選擇周圍幾個節(jié)點散播消息奔坟，收到消息的節(jié)點也會重復(fù)該過程携栋，直至最終網(wǎng)絡(luò)中所有的節(jié)點都收到了消息。
這個過程可能需要一定的時間咳秉，由于不能保證某個時刻所有節(jié)點都收到消息婉支，但是理論上最終所有節(jié)點都會收到消息，因此它是一個最終一致性協(xié)議澜建。
Gossip 協(xié)議的一些特性：
- 擴展性：網(wǎng)絡(luò)可以允許節(jié)點的任意增加和減少向挖，新增加的節(jié)點的狀態(tài)最終會與其他節(jié)點一致。
- 容錯：網(wǎng)絡(luò)中任何節(jié)點的宕機和重啟都不會影響 Gossip 消息的傳播炕舵，Gossip 協(xié)議具有天然的分布式系統(tǒng)容錯特性何之。
- 去中心化： Gossip 協(xié)議不要求任何中心節(jié)點，所有節(jié)點都可以是對等的幕侠，任何一個節(jié)點無需知道整個網(wǎng)絡(luò)狀況帝美，只要網(wǎng)絡(luò)是連通的，任意一個節(jié)點就可以把消息散播到全網(wǎng)晤硕。
- 一致性收斂： Gossip 協(xié)議中的消息會以一傳十、十傳百一樣的指數(shù)級速度在網(wǎng)絡(luò)中快速傳播庇忌，因此系統(tǒng)狀態(tài)的不一致可以在很快的時間內(nèi)收斂到一致舞箍。消息傳播速度達到了 logN。
- 消息的延遲：由于 Gossip 協(xié)議中皆疹，節(jié)點只會隨機向少數(shù)幾個節(jié)點發(fā)送消息疏橄，消息最終是通過多個輪次的散播而到達全網(wǎng)的，因此使用 Gossip 協(xié)議會造成不可避免的消息延遲略就。不適合用在對實時性要求較高的場景下捎迫。
- 消息冗余： Gossip 協(xié)議規(guī)定，節(jié)點會定期隨機選擇周圍節(jié)點發(fā)送消息表牢，而收到消息的節(jié)點也會重復(fù)該步驟窄绒，因此就不可避免的存在消息重復(fù)發(fā)送給同一節(jié)點的情況，造成了消息的冗余崔兴，同時也增加了收到消息的節(jié)點的處理壓力彰导。而且蛔翅，由于是定期發(fā)送，因此位谋，即使收到了消息的節(jié)點還會反復(fù)收到重復(fù)消息山析，加重了消息的冗余。
Gossip 協(xié)議包含多種消息掏父，包含 ping , pong , meet , fail 等等笋轨。
- meet：某個節(jié)點發(fā)送 meet 給新加入的節(jié)點，讓新節(jié)點加入集群中赊淑，然后新節(jié)點就會開始與其它節(jié)點進行通信爵政。
- ping：每個節(jié)點都會頻繁給其它節(jié)點發(fā)送 ping，其中包含自己的狀態(tài)還有自己維護的集群元數(shù)據(jù)膏燃，互相通過 ping 交換元數(shù)據(jù)茂卦。
- pong：返回 ping 和 meeet，包含自己的狀態(tài)和其它信息组哩，也用于信息廣播和更新等龙。
- fail：某個節(jié)點判斷另一個節(jié)點 fail 之后，就發(fā)送 fail 給其它節(jié)點伶贰，通知其它節(jié)點說蛛砰，某個節(jié)點宕機啦。
由于 Redis Cluster 節(jié)點之間會定期交換 Gossip 消息黍衙，以及做一些心跳檢測泥畅，對網(wǎng)絡(luò)帶寬的壓力還有比較大的，包括官方都直接建議 Redis Cluster 節(jié)點數(shù)量不要超過 1000 個琅翻，當集群中節(jié)點數(shù)量過多的時候位仁，會產(chǎn)生不容忽視的帶寬消耗。
高可用和主備切換
一說到集群就不得不提高可用和主備切換方椎，而Redis cluster 的高可用的原理聂抢，幾乎跟哨兵是類似的。
判斷宕機
首先第一步當然是判斷宕機棠众，這和哨兵模式非常的像琳疏，同樣是分成兩種類型，一種是主觀宕機 pfail 闸拿，另一種的客觀宕機 fail 空盼。
- 主觀宕機：一個節(jié)點認為另外一個節(jié)點宕機，這是一種「偏見」新荤，并不代表整個集群的認知揽趾。
- 節(jié)點 1 定期發(fā)送 ping 消息給節(jié)點 2 。
- 如果發(fā)送成功迟隅，代表節(jié)點 2 正常運行但骨，節(jié)點 2 會響應(yīng) PONG 消息給節(jié)點 1 励七，節(jié)點 1 更新與節(jié)點 2 的最后通信時間
- 如果發(fā)送失敗，則節(jié)點 1 與節(jié)點 2 之間的通信異常判斷連接奔缠，在下一個定時任務(wù)周期時掠抬，仍然會與節(jié)點 2 發(fā)送 ping 消息
- 如果節(jié)點 1 發(fā)現(xiàn)與節(jié)點 2 最后通信時間超過
cluster-node-timeout，則把節(jié)點 2 標識為 pfail 狀態(tài)校哎。
- 客觀宕機：當半數(shù)以上持有槽的主節(jié)點都標記某節(jié)點主觀下線两波。
- 當節(jié)點 1 認為節(jié)點 2 宕機后，那么會在 Gossip ping 消息中闷哆， ping 給其他節(jié)點腰奋。
- 當其他節(jié)點會重新嘗試之前節(jié)點 1 主觀宕機的過程。
- 如果有超過半數(shù)的節(jié)點都認為
pfail了抱怔，那么這個節(jié)點 2 就會變成真的fail劣坊。
注意：集群模式下，只有主節(jié)點( master )才有讀寫權(quán)限和集群槽的維護權(quán)限屈留，從節(jié)點( slave )只有復(fù)制的權(quán)限局冰。
從節(jié)點選舉
- 先檢查資格，檢查所有的 salve 與 master 斷開連接的時間灌危，如果超過了
cluster-node-timeout * cluster-slave-validity-factor康二，那么久沒有資格成為 master 。 - 每個從節(jié)點勇蝙，都根據(jù)自己對 master 復(fù)制數(shù)據(jù)的 offset沫勿，來設(shè)置一個選舉時間，offset 越大（復(fù)制數(shù)據(jù)越多）的從節(jié)點味混，選舉時間越靠前产雹，優(yōu)先進行選舉。
- 所有的 master 開始選舉投票翁锡，如果大部分 master 節(jié)點 （N/2 + 1） 都投票給了某個從節(jié)點洽故，那么選舉通過，那個從節(jié)點可以切換成 master 盗誊。
- 從節(jié)點執(zhí)行主備切換，從節(jié)點切換為主節(jié)點隘弊。
參考
https://www.cnblogs.com/williamjie/p/11132211.html
https://github.com/doocs/advanced-java/blob/master/docs/high-concurrency/redis-cluster.md
