首先，從使用hash取模數(shù)據(jù)分片開始說起

無論是哈希槽，還是一致性hash，都屬于hash取模數(shù)據(jù)分片。

先從經(jīng)典的hash取模數(shù)據(jù)分片說起

假如 Redis集群的節(jié)點數(shù)為3個，使用經(jīng)典的hash取模算法進(jìn)行數(shù)據(jù)分片，實際上就是一個節(jié)點一個數(shù)據(jù)分片，分為3片而已。

每次請求使用 hash(key) % 3 的方式計算對應(yīng)的節(jié)點，或者進(jìn)行 分片的路由。

經(jīng)典哈希取模分片的問題和對策：

哈希取模分片有一個核心問題：對擴(kuò)容不友好，擴(kuò)容的時候數(shù)據(jù)遷移規(guī)模太大。

比如，把節(jié)點從3個擴(kuò)展到4個， 具體如下：

原來的分片路由算法是：hash(key) % 3

現(xiàn)在的分片路由算法是：hash(key) % 4

分片路由算法調(diào)整之后，那么，大量的key需要進(jìn)行節(jié)點的遷移。

換句話，即當(dāng)增加或減少節(jié)點時，原來節(jié)點中的80%以上的數(shù)據(jù)，可能會進(jìn)行遷移操作，對所有數(shù)據(jù)重新進(jìn)行分布。

如何應(yīng)對呢？

規(guī)避的措施之一：如果一定要采用哈希取模分片，建議使用多倍擴(kuò)容的方式，這樣只需要適移50%的數(shù)據(jù)。例如以前用3個節(jié)點保存數(shù)據(jù)，擴(kuò)容為比以前多一倍的節(jié)點即6個節(jié)點來保存數(shù)據(jù)，這樣移動50%的數(shù)據(jù)即可。

規(guī)避的措施之一：采用一致性hash分片方法。

哈希取模分片優(yōu)點：

• 配置簡單：對數(shù)據(jù)進(jìn)行哈希，然后取余

哈希取模分片缺點：

• 數(shù)據(jù)節(jié)點伸縮時，導(dǎo)致大量數(shù)據(jù)遷移

• 遷移數(shù)量和添加節(jié)點數(shù)據(jù)有關(guān)，建議翻倍擴(kuò)容

一致性hash算法

如果redis使用一致性hash算法進(jìn)行數(shù)據(jù)分片，那么核心會涉及到的兩個階段：

• 第一階段，需要完成key到slot槽位之間的映射。

• 第二階段，需要完成slot槽位到 redis node節(jié)點之間的映射。

首先看第一階段。

第一階段，需要完成key到slot槽位之間的映射

第一階段，使用了哈希取模的方式，不同的是: ?對 2^32 這個固定的值進(jìn)行取模運算。

注意，這里的取模的除數(shù)，是 2^32 ， 相當(dāng)于 ?2^32個槽位， 英文是 slot 。

通過這個槽位的計算，可以確定 key => slot 之間的映射關(guān)系。

第二階段，需要完成slot槽位到 redis node節(jié)點之間的映射。

第二階段，需要完成slot槽位到 redis node節(jié)點之間的映射。

如何完成 slot ?槽位到node 節(jié)點之間的映射呢？

這里，需要 采用一種特殊的結(jié)構(gòu)：Hash槽位環(huán)。

Hash槽位環(huán)

把一致哈希算法是對 2^32 ?slot 槽位虛擬成一個圓環(huán)，環(huán)上的對應(yīng) 0~2^32 刻度，

如何完成 slot ?槽位到node 節(jié)點之間的映射呢？

假設(shè)有4個redis 節(jié)點， 可以把 2^32 ?slot 槽位環(huán)分成4段， 每一個redis 節(jié)點負(fù)責(zé)存儲一個slot分段

如何對每一個key進(jìn)行node 路由呢？

第一步?進(jìn)行slot槽位計算：每一個key進(jìn)行hash運算，被哈希后的結(jié)果 2^32 ?取模，獲得slot 槽位、

第二步?在hash槽位環(huán)上，按順時針去找最近的redis節(jié)點，這個key將會被保存在這個節(jié)點上。

一致性哈希原理：

將所有的數(shù)據(jù)用hash取模， 映射到 2^32個槽位。

把2^32個槽位 當(dāng)做一個環(huán)，把N個redis 節(jié)點瞬時間放置在槽位環(huán)上，從而把槽位環(huán)分成N段，每redis 節(jié)點負(fù)責(zé)一個分段。

當(dāng)key在槽位環(huán)上路由的時候，按順時針去找最近的redis節(jié)點，這個key將會被保存在這個節(jié)點上。

來看一致性哈希 三個經(jīng)典場景：

經(jīng)典場景1：Key入環(huán)

下圖我們四個key（Key1/Key2/Key3）經(jīng)過哈希計算，放入下面環(huán)中，第一步是進(jìn)行hash計算，取模后得到slot槽位。

找到了slot槽位，相當(dāng)于已經(jīng)成功映射到哈希環(huán)上，

然后將槽位按順時針方向，找到離自己最近的redis節(jié)點上，將value存儲到那個節(jié)點上。

經(jīng)典場景2：新增redis節(jié)點

現(xiàn)在，需要對redis 節(jié)點進(jìn)行擴(kuò)容， 在redis1 和 redis2之間，新增加點redis 5。

具體的操作是：在hash槽位環(huán)上，把redis 5節(jié)點放置進(jìn)去

添加了新節(jié)點之后，對所有的redis 2上的數(shù)據(jù)，進(jìn)行重新的檢查。

如果redis 2上的數(shù)據(jù)，順時針方式最近的新節(jié)點不是redis 2而是 redis 5的話，需要進(jìn)行遷移，遷移到redis 5。

比如，上圖的key2，需要從redis 2遷移 redis 5。

而其他節(jié)點上的數(shù)據(jù)，不受影響。比如redis1、redis3、redis4上的數(shù)據(jù)不受影響。上圖中，key1和key3不受影響

經(jīng)典場景3：刪除redis節(jié)點

假設(shè)，刪除hash環(huán)上的節(jié)點redis 2

那么存儲在redis 2節(jié)點上的key2，將會重新映射找到離它最近的節(jié)點redis3，如下圖

另外，key1、key3不受影響。

經(jīng)典哈希取模與一致性hash的對比：

前面講到，假設(shè)Redis 集群使用經(jīng)典哈希取模分片， 缺點是在數(shù)據(jù)節(jié)點伸縮時，導(dǎo)致大量數(shù)據(jù)遷移：

• 最少50%的數(shù)據(jù)要遷移，這個是在翻倍擴(kuò)容場景

• 一般有80%以上的數(shù)據(jù)要遷移。

假設(shè)Redis 集群使用一致性哈希取模分片， 通過上面的一致性哈希取模新增節(jié)點、一致性哈希取模刪除節(jié)點的分析之后， 可以得到：

• 一致性hash在伸縮的時候， 需要遷移的數(shù)據(jù)不到25%（假設(shè)4個節(jié)點）。

• 和普通hash取模分片相比， 一致性哈希取模分片需要 遷移的數(shù)據(jù)規(guī)?？s小2倍以上。

一致性hash的數(shù)據(jù)不平衡（數(shù)據(jù)傾斜）問題

標(biāo)準(zhǔn)的一致性hash，存在一個大的問題：數(shù)據(jù)不平衡（數(shù)據(jù)傾斜）問題。

回顧一下，一致性hash算法的兩個階段：

• 第一階段，需要完成key到slot槽位之間的映射。

• 第二階段，需要完成slot槽位到 redis node節(jié)點之間的映射。

在這個兩階段中，數(shù)據(jù)不平衡（數(shù)據(jù)傾斜）問題的來源在第二階段：

• 第一個階段，hash算法是均勻的。

• 第二個階段，如果某個節(jié)點宕機(jī)，那么就會出現(xiàn)節(jié)點的不平衡。

遷移之后，發(fā)生了 嚴(yán)重的數(shù)據(jù)傾斜，或者不平衡。Redis 3上4個key，而redis 1、redis 4上只有1個key。

這樣，redis2 上的數(shù)量很多，此時會導(dǎo)致節(jié)點壓力陡增。

旱澇不均。

那如何解決這個旱澇不均問題呢？答案是通過?虛擬節(jié)點。

什么是 虛擬節(jié)點？

虛擬節(jié)點?可以理解為邏輯節(jié)點，不是物理節(jié)點。?假設(shè)在hash環(huán)上，引入 32 個虛擬 reids節(jié)點。

如何找到物理節(jié)點呢？?辦法是增加一次映射：虛擬節(jié)點到物理節(jié)點的映射。

假設(shè)加上一層 ?32 個虛擬 redis節(jié)點到 4個 ?redis 物理節(jié)點映射。一種非常簡單的map參考映射方案

假設(shè)物理節(jié)點 redis 3被移除，那么，把redis 3負(fù)責(zé)的邏輯節(jié)點，二次分配到其他三個物理節(jié)點就行了

無論如何，通過虛擬節(jié)點，就會大大減少了 一致性hash 算法的數(shù)據(jù)傾斜/數(shù)據(jù)不平衡。

一致性hash的簡易實現(xiàn)

可以使用TreeMap 來實現(xiàn)一致性hash，原因有二：

• TreeMap的key是有序，

• 使用TreeMap的ceilingEntry(K k) 方法，可以返回大于或等于給定參數(shù)K的鍵， 這就是映射到的節(jié)點。

TreeMap是一個小頂堆，默認(rèn)是根據(jù)key的自然排序來組織（比如integer的大小，String的字典排序）。底層是根據(jù)紅黑樹的數(shù)據(jù)結(jié)構(gòu)構(gòu)建的。

這里使用TreeMap的ceilingEntry(K key) 方法，該方法用來返回與該鍵至少大于或等于給定鍵，如果不存在這樣的鍵的鍵 - 值映射，則返回null相關(guān)聯(lián)。

一致性hash的簡易實現(xiàn)，參考代碼如下：

package?com.th.treemap;

import?java.util.HashMap;
import?java.util.Iterator;
import?java.util.Map;
import?java.util.TreeMap;

public?class?ConsistentHash?{
????/**
?????*?假設(shè)我們一共初始化有8個節(jié)點(可以是ip,?就理解為ip吧);
?????*?把?1024個虛擬節(jié)點跟?8個資源節(jié)點相對應(yīng)
?????*/
????public?static?Map<Integer,?String>?nodeMap?=?new?HashMap<>();
????public?static?int?V_redisS?=?1024;?//?假設(shè)我們的環(huán)上有1024個虛擬節(jié)點
????static?TreeMap<Integer,?String>?virtualHashRingMap?=?new?TreeMap<>();
????private?static?final?Integer?REAL_redis_COUNT?=?8;
????static?{
????????nodeMap.put(0,?"redis_0");
????????nodeMap.put(1,?"redis_1");
????????nodeMap.put(2,?"redis_2");
????????nodeMap.put(3,?"redis_3");
????????nodeMap.put(4,?"redis_4");
????????nodeMap.put(5,?"redis_5");
????????nodeMap.put(6,?"redis_6");
????????nodeMap.put(7,?"redis_7");
?
?
????????for?(Integer?i?=?0;?i?<?V_redisS;?i++)?{
????????????//?每個虛擬節(jié)點跟其取模的余數(shù)的?redisMap?中的key相對應(yīng);
????????????//?下面刪除虛擬節(jié)點的時候,?就可以根據(jù)取模規(guī)則來刪除?TreeMap中的節(jié)點了;
????????????virtualHashRingMap.put(i,?nodeMap.get(i?%?REAL_redis_COUNT));
????????}
????}

????/**
?????*?輸入一個id
?????*
?????*?@param?value
?????*?@return
?????*/
????public?static?String?getRealServerredis(String?value)?{
????????//?1.?傳遞來一個字符串,?得到它的hash值
????????Integer?vredis?=?value.hashCode()?%?1024;
????????//?2.找到對應(yīng)節(jié)點最近的key的節(jié)點值
????????String?realredis?=?virtualHashRingMap.ceilingEntry(vredis).getValue();
?
?
????????return?realredis;
????}
?
????/**
?????*?模擬刪掉一個物理可用資源節(jié)點,?其他資源可以返回其他節(jié)點
?????*/
????public?static?void?dropBadredis(String?redisName)?{
????????int?redisk?=?-1;
????????//?1.?遍歷?redisMap?找到故障節(jié)點?redisName對應(yīng)的key;
????????for?(Map.Entry<Integer,?String>?entry?:?nodeMap.entrySet())?{
????????????if?(redisName.equalsIgnoreCase(entry.getValue()))?{
????????????????redisk?=?entry.getKey();
????????????????break;
????????????}
????????}
????????if?(redisk?==?-1)?{
????????????System.err.println(redisName?+?"在真實資源節(jié)點中無法找到,?放棄刪除虛擬節(jié)點!");
????????????return;
????????}
?
????????//?2.?根據(jù)故障節(jié)點的?key,?對應(yīng)刪除所有?chMap中的虛擬節(jié)點
????????Iterator<Map.Entry<Integer,?String>>?iter?=?virtualHashRingMap.entrySet().iterator();
????????while?(iter.hasNext())?{
????????????Map.Entry<Integer,?String>?entry?=?iter.next();
????????????int?key?=?entry.getKey();
????????????String?value?=?entry.getValue();
????????????if?(key?%?REAL_redis_COUNT?==?redisk)?{
????????????????System.out.println("刪除物理節(jié)點對應(yīng)的虛擬節(jié)點:?["?+?value?+?"?=?"?+?key?+?"]");
????????????????iter.remove();
????????????}
????????}
????}
?
????public?static?void?main(String[]?args)?{
????????//?1.?一個字符串請求(比如請求字符串存儲到8個節(jié)點中的某個實際節(jié)點);
????????String?requestValue?=?"技術(shù)自由圈";
????????//?2.?打印虛擬節(jié)點和真實節(jié)點的對應(yīng)關(guān)系;
????????System.out.println(virtualHashRingMap);
????????//?3.?核心:?傳入請求信息,?返回實際調(diào)用的節(jié)點信息
????????System.out.println(getRealServerredis(requestValue));
????????//?4.?刪除某個虛擬節(jié)點后
????????dropBadredis("redis_2");
????????System.out.println("==========刪除?redis_2?之后:?================");
????????System.out.println(getRealServerredis(requestValue));
????}
}

回顧下一致性 Hash 算法

接下來，簡單回顧下一致性 Hash 算法：

為了避免出現(xiàn)數(shù)據(jù)傾斜問題，一致性 Hash 算法引入了虛擬節(jié)點的機(jī)制。

虛擬節(jié)點和物理節(jié)點解耦，引入虛擬節(jié)點到物理節(jié)點之間的映射，最終每個物理節(jié)點在哈希環(huán)上會有多個虛擬節(jié)點存在，引入了虛擬節(jié)點的機(jī)制之后，數(shù)據(jù)定位算法不變，只是多了一步虛擬節(jié)點到實際節(jié)點的映射，例如定位到“redis-1-1”、“redis-1-2”、“redis-1-3”三個虛擬節(jié)點，都能映射到 ?redis-1 上。

引入虛擬節(jié)點，可以大大削弱甚至避免數(shù)據(jù)傾斜問題。在實際應(yīng)用中，通常將虛擬節(jié)點數(shù)設(shè)置為32甚至更大。

Redis為什么使用哈希槽而不用一致性哈希

回到正題，既然一致性hash那么完美，兩大優(yōu)點：

• 既很少的數(shù)據(jù)遷移，

• 又很少數(shù)據(jù)傾斜。

Redis為什么使用哈希槽而不用一致性哈希呢？

這個和redis 集群的架構(gòu)特點有關(guān)系， redis 集群的架構(gòu)特點，主要有兩點:

• 去中心化

• 方便伸縮 ?（自動伸縮、手動伸縮都可以）

Redis Cluster集群核心特點一：去中心化

關(guān)于分布式集群的設(shè)計，一般要考慮以下幾個方面：

• 元數(shù)據(jù)存儲，包括 數(shù)據(jù)分片與存儲節(jié)點的映射關(guān)系等

• 節(jié)點間通信，包括信息互通、健康狀態(tài)等

• 擴(kuò)縮容，比如 考慮數(shù)據(jù)遷移情況

• 高可用，當(dāng)節(jié)點出現(xiàn)故障時，能及時自動的進(jìn)行故障轉(zhuǎn)移

先看分布式集群的設(shè)計中的核心：元數(shù)據(jù)存儲 ?設(shè)計。

有兩種架構(gòu)模式：

• 中心化的存儲架構(gòu)

• 去中心化的存儲架構(gòu)

中心化的 元數(shù)據(jù)存儲架構(gòu)

首先，看中心化的 元數(shù)據(jù)存儲架構(gòu)

常見的中間組件來存儲元數(shù)據(jù)，比如 zk、etcd、nacos 等等；

在客戶端看來，先從協(xié)調(diào)節(jié)點獲取元數(shù)據(jù)，然后再負(fù)載均衡到某個服務(wù)節(jié)點

在kafka2.8版本開始嘗試從服務(wù)架構(gòu)中去掉zookeeper，到了3.0版本這個工作基本上完成，這是kafka的一個非常重要的里程碑。2.8.0版本將是第一個不需要ZooKeeper就可以運行Kafka的版本，而這也被稱為Kafka Raft Metadata mode（Kafka Raft 元數(shù)據(jù)模式），或許就是一個會被后人銘記的版本。

ZooKeeper是一個獨立的軟件，但是ZooKeeper使得Kafka整個系統(tǒng)變得復(fù)雜，因此官方?jīng)Q定使用內(nèi)部仲裁控制器來取代ZooKeeper。過去Kafka因為帶著ZooKeeper，因此被認(rèn)為擁有沉重的基礎(chǔ)設(shè)施，而在移除ZooKeeper之后，Kafka更輕巧更適用于小規(guī)模工作負(fù)載，輕量級單體程序適合用于邊緣以及輕量級硬件解決方案。

KRaft

2.8.0版本之后的Kafka集群，元數(shù)據(jù)管理，本質(zhì)上從中心化演進(jìn)到了去中心化，通過raft協(xié)議保證元數(shù)據(jù)寫入的數(shù)據(jù)一致性。

2.8版本之前zookeeper-based Kafka集群，集群有唯一的Controller，這個Controller是從所有的broker中選出，負(fù)責(zé)Watch Zookeeper、partition的replica的集群分配，以及l(fā)eader切換選舉等流程。

2.8.0版本之后with quorum kafka集群將其引入的共識協(xié)議稱為Event-driven consensus，quorum controller不是單個節(jié)點，而是一個小的集群，每個 controller 節(jié)點內(nèi)部維護(hù)RSM（replicated state machine），不像之前的zookeeper-based，controller 節(jié)點不需要首先訪問zookeeper獲取狀態(tài)信息。Kafka的元數(shù)據(jù)會通過raft一致性協(xié)議寫入quorum，并且系統(tǒng)會定期做snapshot。

KRaft中Controller可以被指定為奇數(shù)個節(jié)點（一般情況下3或5）組成raft quorum。controller節(jié)點中有一個active（選為leader），其他的hot standby。這個active controller集群負(fù)責(zé)管理Kafka集群的元數(shù)據(jù)，通過raft協(xié)議達(dá)成共識。因此，每個controller都擁有幾乎update-to-date的Metadata，所以controller集群重新選主時恢復(fù)時間很短。

event-drive

集群的其他節(jié)點通過配置選項controller.quorum.voters獲取controller。zookeeper-based Kafka集群中，controller發(fā)送Metadata給其他的broker。現(xiàn)在broker需要主動向active controller拉取Metadata。一旦broker收到Metadata，它會將其持久化。這個broker持久化Metadata的優(yōu)化意味著一般情況下active controller不需要向broker發(fā)送完整的Metadata，只需要從某個特定的offset發(fā)送即可。但如果遇到一個新上線的broker，Controller可以發(fā)送snapshot給broker（類似raft的InstallSnapshot RPC）。

去中心化的 元數(shù)據(jù)存儲架構(gòu)

使用去中心化的方式，讓每個redis節(jié)點、甚至客戶端都維護(hù)一份元數(shù)據(jù)信息

集群間的redis 采用特定的一些通信協(xié)議（如raft協(xié)議、gossip協(xié)議）進(jìn)行信息交換，以保證集群數(shù)據(jù)整體一致性。

有關(guān)Raft 協(xié)議的內(nèi)容，請參見后面的 《附錄1：Raft 協(xié)議》

有關(guān)gossip協(xié)議的內(nèi)容，請參見后面的 《附錄2：gossip 協(xié)議》

redis ?client客戶端請求直連集群任意節(jié)點，

當(dāng)redis client訪問任意一個節(jié)點，該節(jié)點總能定向到正確的節(jié)點去處理（即使該請求不歸屬于它處理，但它知道誰能處理）。

去中心化場景如何保證元數(shù)據(jù)一致?

如果每個redis節(jié)點都要存儲一份元數(shù)據(jù)信息（分片與節(jié)點的映射關(guān)系），那么問題來了？

在數(shù)據(jù)更新時，必然可能存在一定的數(shù)據(jù)一致性的延遲，這就要求更高的節(jié)點間通信效率。如何保證呢？

問題1：redis 如何進(jìn)行數(shù)據(jù)分片的？

redis 集群的元數(shù)據(jù)信息，核心就是數(shù)據(jù)分片shard與節(jié)點的映射關(guān)系。

redis 如何進(jìn)行數(shù)據(jù)分片的？redis 本質(zhì)上也是 hash 之后取模分片。

第一步：hash。hash算法的功效，核心就是保證數(shù)據(jù)不傾斜，或者說保證分布均勻。那么，redis cluster 的hash算法，采用的是 crc16 哈希算法。

第二步：取模。就是槽位的數(shù)量， redis 集群的把數(shù)據(jù)分為16484 個細(xì)粒度分片，或者說 16484 個slot槽位。

redis cluster 采用 crc16 哈希算法，并使用固定長度的模 16384，其中，這 16484 個哈希分片也稱之為 哈希槽，然后將這些哈希槽盡可能均勻的分配給不同的服務(wù)節(jié)點。

redis cluster 哈希槽

redis cluster 還是采用hash取模分片，數(shù)據(jù)落在哪個分片（這里對應(yīng)到槽位）的算法為

?slot?=?Hash(key)?%?16484?

這里，使用固定長度的模 16384（2^14），這 16484 個哈希分片也稱之為 哈希槽，然后將這些哈希槽盡可能均勻的分配給不同的服務(wù)節(jié)點。具體如下圖：

集群將數(shù)據(jù)劃分為 16384 個槽位（哈希槽），每個Redis服務(wù)節(jié)點分配了一部分槽位。

從hash取模這個角度來說，redis hash 分片和一致性哈希是一樣的。

所不同的是：

• 第一：槽位規(guī)模不同。redis 集群將數(shù)據(jù)劃分為 16384 （2^14）個槽位（哈希槽），一致性hash有 ?2^32個槽位。

• 第二：hash slot和node 節(jié)點的映射關(guān)系不同。一致性hash是哈希環(huán)順時針映射， redis 哈希槽是靜態(tài)映射。

大家回顧一下，一致性hash 怎么 進(jìn)行hash slot和node 節(jié)點 映射的呢？

一致性hash的映射規(guī)則是，每個槽按照順時針方向找到最近的一個節(jié)點便是對應(yīng)所屬的存儲服務(wù)器，簡稱為順時針映射

而redis hash 分片，屬于靜態(tài)映射類型。直接把slot槽位靜態(tài)分配到redis 節(jié)點，當(dāng)然，靜態(tài)分配的時候需要盡可能保證均勻。

假定我們有三個服務(wù)節(jié)點，盡可能均勻分配之后，分配關(guān)系如下：

• 節(jié)點 A 包含哈希槽從 0 到 5460.

• 節(jié)點 B 包含哈希槽從 ?5461 到 10923.

• 節(jié)點 C 包含哈希槽從 10924 到 16383.

增加節(jié)點

還記得我們搞集群的目的是啥？單機(jī)容量不足，需要擴(kuò)容成多機(jī)組成的集群，然后將數(shù)據(jù)盡可能的均分到各個節(jié)點。

redis cluster ，我們可以很容易的增加或者刪除節(jié)點，

新增一個節(jié)點4，redis cluster的這種做法是從各個節(jié)點的前面各拿取一部分slot(槽)到4上。

當(dāng)我們新增一個節(jié)點4 時，節(jié)點1、2、3的數(shù)據(jù)會遷移一部分到節(jié)點 4；實現(xiàn)4個節(jié)點 數(shù)據(jù)均勻：

此時服務(wù)1、2、3、4通過分配各自有了對應(yīng)的哈希槽，新增節(jié)點后集群會自動進(jìn)行哈希槽的重新平均分配，比如上圖中四個節(jié)點中每個節(jié)點的槽位數(shù)是：18384 / 4 = 4096。

當(dāng)然，還可以適當(dāng)調(diào)整，或者手動進(jìn)行分配。

具體來說，可以使用命令 【cluster addslots】為每個節(jié)點自定義分配槽的數(shù)量，手動調(diào)整的場景是：比如有些節(jié)點的機(jī)器性能好，內(nèi)存有128G，那就可以配置更多槽位。

減少節(jié)點

如果減少一個節(jié)點4，redis cluster同樣會自動進(jìn)行槽數(shù)量的重新計算。

當(dāng)我們刪除節(jié)點 4 時，節(jié)點4的slot數(shù)據(jù)會均勻的遷移到節(jié)點 1、節(jié)點 2、節(jié)點3。

刪除節(jié)點C之后，此時服務(wù)A、B節(jié)點中每個節(jié)點的槽位數(shù)是：18384 / 3 = 6128

和一致性哈希不同的是，redis cluster 集群節(jié)點全員參與，目標(biāo)是達(dá)到集群節(jié)點間數(shù)據(jù)盡可能均勻的效果。

對比之前，得到一個結(jié)論：

• 一致性哈希 優(yōu)先考慮的是：如何實現(xiàn) 最少的數(shù)據(jù)遷移。

• redis cluster ?哈希槽分片 優(yōu)先考慮的是：?如何 實現(xiàn)數(shù)據(jù)的均勻。

值得注意，redis 集群數(shù)據(jù)遷移是以哈希槽位單位，也就是說，同一個槽的數(shù)據(jù)只會遷移到一個目的節(jié)點。

問題2：redis 如何管理元數(shù)據(jù)的一致性

redis 采用?流言蜚語?協(xié)議，顧名思義，就像流言、八卦一樣，一傳十、十傳百這樣傳遞下去，直到所有節(jié)點的元數(shù)據(jù)信息達(dá)成一致。

有關(guān)gossip協(xié)議的內(nèi)容，請參見后面的 《附錄2：gossip 協(xié)議》

有關(guān)Raft 協(xié)議的內(nèi)容，請參見后面的 《附錄1：Raft 協(xié)議》

redis cluster 如何實現(xiàn) Gossip 協(xié)議的？

我們知道，每個集群節(jié)點都維護(hù)了集群其他節(jié)點的信息，其通信名單就是根據(jù)該列表來的。

首先，這個工作也是由周期性的時間事件來負(fù)責(zé)處理，每次從通信名單中隨機(jī)選擇 5 個節(jié)點，然后從這批名單中選擇最久未通信的節(jié)點。然后構(gòu)造?PING 請求，嘗試與其進(jìn)行通信，請求報文中會攜帶自己負(fù)責(zé)的那些哈希槽以及部分掌握的其他節(jié)點負(fù)責(zé)的哈希槽信息。

最后是接收?PONG?響應(yīng)報文，該報文和 PING 請求報文基本一致，包含的信息是對方節(jié)點處理的哈希槽以及掌握的部分其他節(jié)點信息，至于要發(fā)送多少其他節(jié)點的信息，這個可以通過一些參數(shù)來控制。

這樣一來一回，雙方的信息算是打通了，順便還打通了雙方掌握的集群其他節(jié)點的信息。

然后多幾個這樣的來回，集群信息就基本一致了。

總體來說，Gossip 協(xié)議 包括兩個部分：

• 第一個部分是通訊報文：槽（slots）數(shù)據(jù)結(jié)構(gòu)實際上是一個二進(jìn)制數(shù)組，數(shù)組長度為 2048 個字節(jié)，16384 個二進(jìn)制位，也就是 2k 大小。這里不包括其他的基礎(chǔ)報文數(shù)據(jù)。

• 第二個部分是報文類型：集群節(jié)點通過 PING，PONG 方式（類似心跳報文）來傳遞集群的元數(shù)據(jù)信息，PING、PONG 都采用相同的數(shù)據(jù)結(jié)構(gòu)攜帶信息，一來一回便知曉了雙方的元數(shù)據(jù)信息，多個來回，整個集群元數(shù)據(jù)信息就一致了，這便是?Gossip 協(xié)議。

你也注意到了，上面的通信節(jié)點是隨機(jī)選擇的，如果某個節(jié)點一直未進(jìn)行通信，節(jié)點就無法打通？

沒錯，redis cluster 也是考慮了這種情況，所以會定期的選擇那些長時間沒有通信的節(jié)點，然后進(jìn)行上面的流程進(jìn)行通信。

客戶端如何感知槽位？

Redis cluster的主節(jié)點各自負(fù)責(zé)一部分slot，那么客戶端的請求的key是如何客戶端如何感知槽位？

如何定位到具體的節(jié)點，然后返回對應(yīng)的數(shù)據(jù)的。

首先，Redis-Cli客戶端的會連接到集群中的任何一個節(jié)點，比如redis 2節(jié)點，如下圖：

1. redis 2節(jié)點 收到命令，首先檢查當(dāng)前key是否存在集群中的節(jié)點

   具體的計算步驟為：

• step1?? hash 槽位：通過CRC16（key）/ 16384計算出slot

• step2??檢查slot：?檢查該slot負(fù)責(zé)的節(jié)點是否本地存儲

• step3??如果slot在本地，就直接就直接返回key對應(yīng)的結(jié)果

• step4?? 如果slot不在本地，那么會 MOVED重定向（包含槽位和目標(biāo)地址 比如redis 3）給客戶端

• step5??客戶端轉(zhuǎn)向至正確的節(jié)點(比如redis 3)，并再次發(fā)送之前執(zhí)行的命令

問題：每執(zhí)行命令前都可能現(xiàn)在Redis節(jié)點上進(jìn)行MOVED重定向才能找到要執(zhí)行命令的節(jié)點，額外增加了IO開銷。

怎么提升性能呢？使用加了本地緩存的 smart客戶端。

smart客戶端

不過大多數(shù)開發(fā)語言的Redis客戶端都采用 Smart客戶端 支持集群協(xié)議，讓整個訪問就更高效。

smart客戶端，加了 元數(shù)據(jù)的本地緩存。

smart客戶端的主要特點：Redis客戶端在內(nèi)部維護(hù)哈希槽--節(jié)點的映射關(guān)系，這樣就可以在Smart客戶端實現(xiàn)鍵到節(jié)點的查找，避免了再進(jìn)行MOVED重定向。

本地緩存何時初始化呢？最開始的時候，redis會選擇一個運行節(jié)點，初始化槽和節(jié)點映射關(guān)系。

smart客戶端仍然需要MOVED和ASK命令

不過smart客戶端仍然需要MOVED和ASK命令配合，為啥呢？

通常在smart客戶端也需要緩存元數(shù)據(jù)信息（哈希槽與節(jié)點的對應(yīng)關(guān)系），實現(xiàn)更加高效的精準(zhǔn)定位具體的節(jié)點，然而，也很容易發(fā)生客戶端本地緩存更新不及時的情，仍然需要MOVED和ASK命令。

所以，為了保證客戶端不受此類元數(shù)據(jù)變更帶來的影響，cluster 提供了對應(yīng)的一些指令來處理，比如 MOVED、ASK 等指令。

當(dāng)客戶端收到這些指令后，會做出比如重定向、更新客戶端緩存等操作，我們具體來看看：

1）MOVED：

當(dāng)節(jié)點發(fā)現(xiàn)鍵所在的槽并非由自己負(fù)責(zé)處理的時候，節(jié)點就會向客戶端返回一個 MOVED 錯誤，指引客戶端轉(zhuǎn)向至正在負(fù)責(zé)槽的節(jié)點。

MOVED 錯誤的格式為：

MOVED?<slot>?<ip>:<port>1.

其中 slot 為鍵所在的槽，而 ip 和 port 則是負(fù)責(zé)處理槽 slot 的節(jié)點的 IP 地址和端口號。

當(dāng)客戶端接收到節(jié)點返回的 MOVED 錯誤時，客戶端會根據(jù) MOVED 錯誤中提供的 IP 地址和端口號，轉(zhuǎn)向至負(fù)責(zé)處理槽 slot 的節(jié)點，并向該節(jié)點重新發(fā)送之前想要執(zhí)行的命令。

一個集群客戶端通常會與集群中的多個節(jié)點創(chuàng)建套接字連接，而所謂的節(jié)點轉(zhuǎn)向?qū)嶋H上就是換一個套接字來發(fā)送命令。

如果客戶端尚未與想要轉(zhuǎn)向的節(jié)點創(chuàng)建套接字連接，那么客戶端會先根據(jù) MOVED 錯誤提供的 IP 地址和端口號來連接節(jié)點，然后再進(jìn)行轉(zhuǎn)向。

2）ASK：

在進(jìn)行重新分片期間，源節(jié)點向目標(biāo)節(jié)點遷移一個槽的過程中，可能會出現(xiàn)這樣一種特殊情況：被遷槽的一部分key還在源節(jié)點，而另一部分key則遷移到目標(biāo)節(jié)點。

當(dāng)客戶端向源節(jié)點發(fā)送一個與數(shù)據(jù)庫鍵有關(guān)的命令，并且命令要處理的數(shù)據(jù)庫鍵恰好就屬于正在被遷移的槽時：

• 源節(jié)點會先在本地查找指定的鍵，如果找到的話，就直接執(zhí)行客戶端發(fā)送的命令。

• 如果源節(jié)點本地沒找到，那么這個鍵已經(jīng)被遷移到了目標(biāo)節(jié)點，源節(jié)點將向客戶端返回一個 ASK 響應(yīng)，指引客戶端轉(zhuǎn)向正在導(dǎo)入槽的目標(biāo)節(jié)點，

• 客戶端收到ASK響應(yīng)，再次發(fā)送之前想要執(zhí)行的命令。

客戶端將收到如下ASK 響應(yīng)：

ASK?<slot>?<ip>:<port>1.

ASK 和 MOVED 都會導(dǎo)致客戶端轉(zhuǎn)向，它們有哪些區(qū)別？

• MOVED 代表槽的負(fù)責(zé)權(quán)已經(jīng)完成從一個節(jié)點轉(zhuǎn)移到了另一個節(jié)點，在客戶端收到關(guān)于槽 i 的MOVED 之后，客戶端槽位映射關(guān)系緩存關(guān)系也會刷新，客戶端本地的槽位映射關(guān)系刷新之后，后面節(jié)點關(guān)于槽 i 的請求可以直接發(fā)往 MOVED 所指向的節(jié)點。

• ASK 只是兩個節(jié)點在遷移槽的過程中使用的一種臨時措施：在客戶端收到關(guān)于槽 i 的 ASK 之后，客戶端只會在接下來的一次命令請求中，將命令請求發(fā)送至 ASK 所指示的節(jié)點；客戶端槽位映射關(guān)系緩存關(guān)系不會刷新，因此，流程上還是會走「原節(jié)點 -> ASK 重定向目標(biāo)節(jié)點」這一流程。

問題3：為什么Redis Cluster哈希槽數(shù)量是16384 (16K)？

前面講到 redis 哈希與一致性hash所不同的是：

• 第一：槽位規(guī)模不同。

  redis 集群將數(shù)據(jù)劃分為 16384 個槽位（哈希槽），一致性hash有 ?2^32 個槽位。

• 第二：hash slot和node 節(jié)點的映射關(guān)系不同。

  一致性hash是哈希環(huán)順時針映射， redis 哈希槽是靜態(tài)映射。

問題是：一致性哈希算法是對2的32次方取模，而哈希槽是對2的14次方取模。為啥Redis 不設(shè)置 2的32次方 個槽位呢？

為啥 16384 (16K) 個槽位， redis 給出的主要原因是：

• 1：網(wǎng)絡(luò)帶寬的因素：

  Redis節(jié)點間通信時，心跳包會攜帶節(jié)點的所有槽信息，通過這些槽位元數(shù)據(jù)來更新配置。

  所以，槽位數(shù)量不能太多，如果太多，那么通訊的報文就太大了。reids 采用 16384 個插槽，一個槽位占用一個二進(jìn)制為，16384 ?(16384/8=2048）占通訊報文空間 2KB; ?反過來，如果采用 65536 個插槽，占空間 8KB (65536/8)。

• 2：當(dāng)集群擴(kuò)展到1000個節(jié)點時，也能確保每個master節(jié)點有足夠的插槽，每個節(jié)點16384 /1024=16個槽位，也足夠了

• 3：Redis Cluster 不太可能擴(kuò)展到超過 1000 個主節(jié)點，太多可能導(dǎo)致網(wǎng)絡(luò)擁堵。

  在實際應(yīng)用中，一個redis cluster集群不超過200個節(jié)點，超過200個節(jié)點就會有大量的gossip 協(xié)議的報文， 很容易出現(xiàn)網(wǎng)絡(luò)擁塞。

關(guān)于這個問題，Redis作者的回答在這里：why redis-cluster use 16384 slots? · Issue #2576 · redis/redis

為什么Redis是使用哈希槽而不是一致性哈希呢？

接下來，我們再總結(jié)一下，為什么Redis是使用哈希槽而不是一致性哈希呢？

首先， Redis哈希槽和一致性哈希，總體的流程都是差不多的，都是兩個階段：

• 第一階段是：hash 取模

• 第二階段是：node 映射

第一階段都是 hash 之后取模分片。分為兩步：

• 第一步：hash。hash算法的功效，核心就是保證數(shù)據(jù)不傾斜，或者說保證分布均勻。redis cluster 的hash算法，采用的是 crc16 哈希算法。

• 第二步：取模。就是槽位的數(shù)量， redis 集群的把數(shù)據(jù)分為16484 （16K）個slot槽位。一致性哈希是 2的32次方個槽位。

為啥redis cluster 不設(shè)置 2的32次方個槽位呢？主要是考慮節(jié)點數(shù)在1000的規(guī)模一下，而是使用gossip 去中心一致性協(xié)議，數(shù)據(jù)包不能太大，16K 個二進(jìn)制位 2K字節(jié)已經(jīng)很大了。

第二階段是：node 映射。

• 一致性hash是哈希環(huán)順時針映射，

• redis 哈希槽是靜態(tài)映射。

通過前面的對比，得到一個結(jié)論：

• 一致性hash 哈希環(huán)順時針映射 優(yōu)先考慮的是：如何實現(xiàn) 最少的節(jié)點數(shù)據(jù)發(fā)生數(shù)據(jù)遷移。

  一致性hash 哈希環(huán)上面，只有被干掉的節(jié)點順時針方向最近的那一個節(jié)點涉及到數(shù)據(jù)遷移；其他間隔較遠(yuǎn)的節(jié)點，不涉及到數(shù)據(jù)遷移。

• redis cluster ?哈希槽靜態(tài)映射 優(yōu)先考慮的是：?如何 實現(xiàn)數(shù)據(jù)的均勻。

  redis cluster 各個節(jié)點都會參與數(shù)據(jù)遷移，優(yōu)先保證各個redis節(jié)點承擔(dān)同樣的訪問壓力。

• 同時，redis cluster ?哈希槽靜態(tài)映射還有一個優(yōu)點，手動遷移。

  redis cluster ?可以自動分配，也可以根據(jù)節(jié)點的性能（比如Memory大?。?手動的調(diào)整slot的分配。

附錄1：Raft 協(xié)議

Raft協(xié)議對標(biāo)Paxos，容錯性和性能都是一致的，但是Raft比Paxos更易理解和實施。系統(tǒng)分為幾種角色：Leader（發(fā)出提案）、Follower（參與決策）、Candidate（Leader選舉中的臨時角色）。

剛開始所有節(jié)點都是Follower狀態(tài)，然后進(jìn)行Leader選舉。成功后Leader接受所有客戶端的請求，然后把日志entry發(fā)送給所有Follower，當(dāng)收到過半的節(jié)點的回復(fù)（而不是全部節(jié)點）時就給客戶端返回成功并把commitIndex設(shè)置為該entry的index，所以是滿足最終一致性的。

Leader同時還會周期性地發(fā)送心跳給所有的Follower（會通過心跳同步提交的序號commitIndex），F(xiàn)ollower收到后就保持Follower狀態(tài)（并應(yīng)用commitIndex及其之前對應(yīng)的日志entry），如果Follower等待心跳超時了，則開始新的Leader選舉：首先把當(dāng)前term計數(shù)加1，自己成為Candidate，然后給自己投票并向其它結(jié)點發(fā)投票請求。直到以下三種情況：

• 它贏得選舉；

• 另一個節(jié)點成為Leader；

• 一段時間沒有節(jié)點成為Leader。

在選舉期間，Candidate可能收到來自其它自稱為Leader的寫請求，如果該Leader的term不小于Candidate的當(dāng)前term，那么Candidate承認(rèn)它是一個合法的Leader并回到Follower狀態(tài)，否則拒絕請求。

如果出現(xiàn)兩個Candidate得票一樣多，則它們都無法獲取超過半數(shù)投票，這種情況會持續(xù)到超時，然后進(jìn)行新一輪的選舉，這時同時的概率就很低了，那么首先發(fā)出投票請求的的Candidate就會得到大多數(shù)同意，成為Leader。

在Raft協(xié)議出來之前，Paxos是分布式領(lǐng)域的事實標(biāo)準(zhǔn)，但是Raft的出現(xiàn)打破了這一個現(xiàn)狀（raft作者也是這么想的，請看論文），Raft協(xié)議把Leader選舉、日志復(fù)制、安全性等功能分離并模塊化，使其更易理解和工程實現(xiàn)，將來發(fā)展怎樣我們拭目以待（挺看好）。

Raft協(xié)議目前被用于 cockrouchDB，TiKV等項目中，據(jù)我聽的一些報告來看，一些大廠自己造的分布式數(shù)據(jù)庫也在使用Raft協(xié)議。

附錄2：Gossip 協(xié)議

Gossip協(xié)議與raft協(xié)議最大的區(qū)別就是它是徹底的去中心化的，

Gossip 協(xié)議也叫 Epidemic Protocol（流行病協(xié)議），主要用于消息傳播，是一種一致性算法。

協(xié)議也非常好理解，正如協(xié)議的名稱，如流行病一樣靠“感染”節(jié)點進(jìn)行持續(xù)傳播。

使用 Gossip 協(xié)議的有：Redis Cluster、Consul、Apache Cassandra等。

Gossip協(xié)議基本思想就是：一個節(jié)點想要分享一些信息給網(wǎng)絡(luò)中的其他的節(jié)點，于是隨機(jī)選擇一些節(jié)點進(jìn)行信息傳遞。這些收到信息的節(jié)點接下來把這些信息傳遞給其他一些隨機(jī)選擇的節(jié)點。

Gossip 整體過程描述如下。

1. Gossip 是周期性的散播消息

2. 被感染節(jié)點隨機(jī)選擇 k 個鄰接節(jié)點（fan-out）散播消息，假設(shè)把 fan-out 設(shè)置為2，每次最多往2個節(jié)點散播

3. 每次散播消息都選擇尚未發(fā)送過的節(jié)點進(jìn)行散播

4. 收到消息的節(jié)點不再往發(fā)送節(jié)點散播，比如 A -> B，那么 B 進(jìn)行散播的時候，不再發(fā)給 A

前面的raft協(xié)議雖然去中心化，但是還是要選出一個類似于Leader的角色來統(tǒng)籌安排事務(wù)的響應(yīng)、提交與中斷，

但是Gossip協(xié)議中就沒有Leader，也不選舉leader每個節(jié)點都是平等的。

?

Gossip 協(xié)議 每個節(jié)點存放了一個key,value,version構(gòu)成的列表，每隔一定的時間，節(jié)點都會主動挑選一個在線節(jié)點進(jìn)行上圖的過程（不在線的也會挑一個嘗試），兩個節(jié)點各自修改自己較為落后的數(shù)據(jù)，最終數(shù)據(jù)達(dá)成一致并且都較新。節(jié)點加入或退出都很容易。

Gossip 協(xié)議優(yōu)點

• 擴(kuò)展性

Gossip 協(xié)議的可擴(kuò)展性極好，一般只需要 O(LogN) 輪就可以將信息傳播到所有的節(jié)點，其中 N 代表節(jié)點的個數(shù)。即使集群節(jié)點的數(shù)量增加，每個節(jié)點的負(fù)載也不會增加很多，幾乎是恒定的。這就允許集群管理的節(jié)點規(guī)模能橫向擴(kuò)展到幾千幾萬個，集群內(nèi)的消息通信成本卻不會增加很多。

• 容錯

網(wǎng)絡(luò)中任何節(jié)點的宕機(jī)和重啟都不會影響 Gossip 消息的傳播，Gossip 協(xié)議具有天然的分布式系統(tǒng)容錯特性。

• 健壯性

Gossip 協(xié)議是去中心化的協(xié)議，所以集群中的所有節(jié)點都是對等的，任何節(jié)點出現(xiàn)問題都不會阻止其他節(jié)點繼續(xù)發(fā)送消息。任何節(jié)點都可以隨時加入或離開，而不會影響系統(tǒng)的整體服務(wù)質(zhì)量。

• 最終一致性

消息傳播是指數(shù)級的快速傳播，因此當(dāng)有新信息傳播時，消息可以快速地發(fā)送到全局節(jié)點。

系統(tǒng)狀態(tài)的不一致可以在很快的時間內(nèi)收斂到一致。

Gossip 協(xié)議缺點

• 消息延遲

節(jié)點隨機(jī)向少數(shù)幾個節(jié)點發(fā)送消息，消息最終是通過多個輪次的傳播而到達(dá)全網(wǎng)，不可避免的造成消息延遲。不適合于對實時性要求較高的場景。

• 消息冗余

節(jié)點會定期隨機(jī)選擇周圍節(jié)點發(fā)送消息，而收到消息的節(jié)點也會重復(fù)該步驟，因此就不可避免的存在消息重復(fù)發(fā)送給同一節(jié)點的情況，造成了消息的冗余，同時也增加了收到消息的節(jié)點的處理壓力。文章來源地址http://www.zghlxwxcb.cn/news/detail-853668.html

到了這里，關(guān)于JAVA面試題分享五百六十五：為啥Redis用哈希槽，不用一致性哈希？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！