尼恩說在前面

在40歲老架構(gòu)師 尼恩的讀者交流群(50+)中，最近有小伙伴拿到了一線互聯(lián)網(wǎng)企業(yè)如得物、阿里、滴滴、極兔、有贊、希音、百度、網(wǎng)易、美團(tuán)的面試資格，遇到很多很重要的面試題：

Redis為何用哈希槽而不用一致性哈希？

最近有小伙伴在面試網(wǎng)易，又遇到了相關(guān)的面試題。小伙伴懵了，因?yàn)闆]有遇到過，所以支支吾吾的說了幾句，面試官不滿意，面試掛了。

所以，尼恩給大家做一下系統(tǒng)化、體系化的梳理，使得大家內(nèi)力猛增，可以充分展示一下大家雄厚的 “技術(shù)肌肉”，讓面試官愛到 “不能自已、口水直流”，然后實(shí)現(xiàn)”offer直提”。

當(dāng)然，這道面試題，以及參考答案，也會(huì)收入咱們的 《尼恩Java面試寶典PDF》V170版本，供后面的小伙伴參考，提升大家的 3高 架構(gòu)、設(shè)計(jì)、開發(fā)水平。

《尼恩 架構(gòu)筆記》《尼恩高并發(fā)三部曲》《尼恩Java面試寶典》的PDF，請(qǐng)到文末公號(hào)【技術(shù)自由圈】取

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

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

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

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

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

從上面可以看到，經(jīng)典哈希取模分片，是非常簡單的一種分片方式

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

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

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

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

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

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

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

如何應(yīng)對(duì)呢？

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

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

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

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

哈希取模分片缺點(diǎn)：

• 數(shù)據(jù)節(jié)點(diǎn)伸縮時(shí)，導(dǎo)致大量數(shù)據(jù)遷移
• 遷移數(shù)量和添加節(jié)點(diǎn)數(shù)據(jù)有關(guān)，建議翻倍擴(kuò)容

一致性hash算法

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

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

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

首先看第一階段。

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

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

具體如下圖所示：

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

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

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

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

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

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

Hash槽位環(huán)

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

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

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

如下圖所示：

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

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

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

一致性哈希原理：

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

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

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

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

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

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

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

然后將槽位按順時(shí)針方向，找到離自己最近的redis節(jié)點(diǎn)上，將value存儲(chǔ)到那個(gè)節(jié)點(diǎn)上。

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

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

具體的操作是：在hash槽位環(huán)上，把redis 5節(jié)點(diǎn)放置進(jìn)去，大致如下圖所示。

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

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

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

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

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

假設(shè)，刪除hash環(huán)上的節(jié)點(diǎn)redis 2，如下圖：

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

另外，key1、key3不受影響。

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

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

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

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

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

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

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

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

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

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

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

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

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

• 第一個(gè)階段，hash算法是均勻的。

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

比如，下面一個(gè)例子，6個(gè)key 分布在四個(gè)節(jié)點(diǎn)：

如果，上圖的節(jié)點(diǎn)redis2 宕機(jī)了， 那么，key2和key3會(huì)遷移到節(jié)點(diǎn)redis 3。

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

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

旱澇不均。

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

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

虛擬節(jié)點(diǎn) 可以理解為邏輯節(jié)點(diǎn)，不是物理節(jié)點(diǎn)。 假設(shè)在hash環(huán)上，引入 32 個(gè)虛擬 reids節(jié)點(diǎn)。如下圖所示：

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

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

假設(shè)物理節(jié)點(diǎn) redis 3被移除，那么，把redis 3負(fù)責(zé)的邏輯節(jié)點(diǎn)，二次分配到其他三個(gè)物理節(jié)點(diǎn)就行了，大致的思路如下：

當(dāng)然，上圖例子中只簡單列舉了一種虛擬節(jié)點(diǎn)的簡單映射方案，實(shí)際代碼中會(huì)有更多的、更為復(fù)雜的方案。

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

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

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

• TreeMap的key是有序，

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

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

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

一致性hash的簡易實(shí)現(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個(gè)節(jié)點(diǎn)(可以是ip, 就理解為ip吧);
     * 把 1024個(gè)虛擬節(jié)點(diǎn)跟 8個(gè)資源節(jié)點(diǎn)相對(duì)應(yīng)
     */
    public static Map<Integer, String> nodeMap = new HashMap<>();
    public static int V_redisS = 1024; // 假設(shè)我們的環(huán)上有1024個(gè)虛擬節(jié)點(diǎn)
    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++) {
            // 每個(gè)虛擬節(jié)點(diǎn)跟其取模的余數(shù)的 redisMap 中的key相對(duì)應(yīng);
            // 下面刪除虛擬節(jié)點(diǎn)的時(shí)候, 就可以根據(jù)取模規(guī)則來刪除 TreeMap中的節(jié)點(diǎn)了;
            virtualHashRingMap.put(i, nodeMap.get(i % REAL_redis_COUNT));
        }
    }

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

尼恩提示，一致性hash是面試重點(diǎn)，這段代碼，大家一定要跑一下。

回顧下一致性 Hash 算法

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

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

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

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

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

回到正題，很多小伙伴問尼恩，既然一致性hash那么完美，兩大優(yōu)點(diǎn)：

• 既很少的數(shù)據(jù)遷移，
• 又很少數(shù)據(jù)傾斜。

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

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

• 去中心化
• 方便伸縮 （自動(dòng)伸縮、手動(dòng)伸縮都可以）

Redis Cluster集群核心特點(diǎn)一：去中心化

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

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

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

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

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

尼恩這里重點(diǎn)討論的是數(shù)據(jù)分片，而不是高可用和故障轉(zhuǎn)移， 有關(guān)高可用和故障轉(zhuǎn)移的內(nèi)容，請(qǐng)參見尼恩視頻《視頻第21章：6個(gè)面試必備 Redis cluster的核心實(shí)操》

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

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

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

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

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

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

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

在客戶端看來，先從協(xié)調(diào)節(jié)點(diǎn)獲取元數(shù)據(jù)，然后再負(fù)載均衡到某個(gè)服務(wù)節(jié)點(diǎn)，大致如下圖所示：

kafka在2.8版本之前，強(qiáng)依賴zookeeper這個(gè)分布式服務(wù)協(xié)調(diào)管理工具的進(jìn)行元數(shù)據(jù)管理。

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

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

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

尼恩備注：raft是工程上使用較為廣泛的強(qiáng)一致性、去中心化、高可用的分布式協(xié)議。

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

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

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

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

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

扯太遠(yuǎn)了，尼恩就像一個(gè)喜歡講歷史故事的老人， 喜歡無止境的發(fā)散。

抱歉了，伙計(jì)們，咱們得回到正題。

當(dāng)然，如果能和面試官扯到這里， 面試也會(huì)很驚奇的。

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

使用去中心化的方式，讓每個(gè)redis節(jié)點(diǎn)、甚至客戶端都維護(hù)一份元數(shù)據(jù)信息，大概是這樣：

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

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

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

redis client客戶端請(qǐng)求直連集群任意節(jié)點(diǎn)，

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

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

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

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

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

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

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

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

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

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

redis cluster 哈希槽

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

 slot = Hash(key) % 16484 

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

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

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

所不同的是：

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

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

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

一致性hash的映射規(guī)則是，每個(gè)槽按照順時(shí)針方向找到最近的一個(gè)節(jié)點(diǎn)便是對(duì)應(yīng)所屬的存儲(chǔ)服務(wù)器，簡稱為順時(shí)針映射，如下圖：

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

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

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

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

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

增加節(jié)點(diǎn)

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

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

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

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

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

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

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

減少節(jié)點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

客戶端如何感知槽位？

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

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

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

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

   具體的計(jì)算步驟為：

• step1 hash 槽位： 通過CRC16（key）/ 16384計(jì)算出slot

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

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

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

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

具體如下圖：

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

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

smart客戶端

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

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

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

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

我們看下圖：

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

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

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

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

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

1）MOVED：

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

MOVED 錯(cuò)誤的格式為：

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

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

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

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

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

2）ASK：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

尼恩提示：給面試官嘚啵嘚、嘚啵嘚 講到這里，已經(jīng)10多分鐘過去了。

面試已經(jīng)了解到了你的強(qiáng)大的技術(shù)實(shí)力， 基本已經(jīng)佛了。

估計(jì)已經(jīng)被你的超強(qiáng)內(nèi)功，迷得神魂顛倒了。

接下來，我們?cè)倏偨Y(jié)一下，為什么Redis是使用哈希槽而不是一致性哈希呢？

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

• 第一階段是：hash 取模
• 第二階段是： node 映射

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

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

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

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

第二階段是： node 映射。

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

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

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

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

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

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

• 同時(shí)，redis cluster 哈希槽靜態(tài)映射還有一個(gè)優(yōu)點(diǎn)，手動(dòng)遷移。

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

附錄1：Raft 協(xié)議

尼恩的宗旨是， 寫的文章一定要方便大家好懂。 對(duì)于Raft 協(xié)議，尼恩也在這加點(diǎn)附錄。

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

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

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

• 它贏得選舉；
• 另一個(gè)節(jié)點(diǎn)成為Leader；
• 一段時(shí)間沒有節(jié)點(diǎn)成為Leader。

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

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

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

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

附錄2：Gossip 協(xié)議

尼恩的宗旨是， 寫的文章一定要方便大家好懂。 對(duì)于Gossip 協(xié)議，尼恩也在這加點(diǎn)附錄。

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

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

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

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

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

Gossip 整體過程描述如下。

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

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

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

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

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

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

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

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

• 擴(kuò)展性

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

• 容錯(cuò)

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

• 健壯性

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

• 最終一致性

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

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

Gossip 協(xié)議缺點(diǎn)

• 消息延遲

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

• 消息冗余

節(jié)點(diǎn)會(huì)定期隨機(jī)選擇周圍節(jié)點(diǎn)發(fā)送消息，而收到消息的節(jié)點(diǎn)也會(huì)重復(fù)該步驟，因此就不可避免的存在消息重復(fù)發(fā)送給同一節(jié)點(diǎn)的情況，造成了消息的冗余，同時(shí)也增加了收到消息的節(jié)點(diǎn)的處理壓力。

說在最后：有問題找老架構(gòu)取經(jīng)

以上的內(nèi)容，如果大家能對(duì)答如流，如數(shù)家珍，基本上 面試官會(huì)被你 震驚到、吸引到。

最終，讓面試官愛到 “不能自已、口水直流”。offer， 也就來了。

在面試之前，建議大家系統(tǒng)化的刷一波 5000頁《尼恩Java面試寶典PDF》，里邊有大量的大廠真題、面試難題、架構(gòu)難題。很多小伙伴刷完后， 吊打面試官， 大廠橫著走。

在刷題過程中，如果有啥問題，大家可以來 找 40歲老架構(gòu)師尼恩交流。

另外，如果沒有面試機(jī)會(huì)，可以找尼恩來改簡歷、做幫扶。

遇到職業(yè)難題，找老架構(gòu)取經(jīng)， 可以省去太多的折騰，省去太多的彎路。

尼恩指導(dǎo)了大量的小伙伴上岸，前段時(shí)間，剛指導(dǎo)一個(gè)40歲+被裁小伙伴，拿到了一個(gè)年薪100W的offer。

狠狠卷，實(shí)現(xiàn) “offer自由” 很容易的， 前段時(shí)間一個(gè)武漢的跟著尼恩卷了2年的小伙伴， 在極度嚴(yán)寒/痛苦被裁的環(huán)境下， offer拿到手軟， 實(shí)現(xiàn)真正的 “offer自由” 。

尼恩技術(shù)圣經(jīng)系列PDF

• 《NIO圣經(jīng)：一次穿透NIO、Selector、Epoll底層原理》
• 《Docker圣經(jīng)：大白話說Docker底層原理，6W字實(shí)現(xiàn)Docker自由》
• 《K8S學(xué)習(xí)圣經(jīng)：大白話說K8S底層原理，14W字實(shí)現(xiàn)K8S自由》
• 《SpringCloud Alibaba 學(xué)習(xí)圣經(jīng)，10萬字實(shí)現(xiàn)SpringCloud 自由》
• 《大數(shù)據(jù)HBase學(xué)習(xí)圣經(jīng)：一本書實(shí)現(xiàn)HBase學(xué)習(xí)自由》
• 《大數(shù)據(jù)Flink學(xué)習(xí)圣經(jīng)：一本書實(shí)現(xiàn)大數(shù)據(jù)Flink自由》
• 《響應(yīng)式圣經(jīng)：10W字，實(shí)現(xiàn)Spring響應(yīng)式編程自由》
• 《Go學(xué)習(xí)圣經(jīng)：Go語言實(shí)現(xiàn)高并發(fā)CRUD業(yè)務(wù)開發(fā)》

……完整版尼恩技術(shù)圣經(jīng)PDF集群，請(qǐng)找尼恩領(lǐng)取

《尼恩 架構(gòu)筆記》《尼恩高并發(fā)三部曲》《尼恩Java面試寶典》PDF，請(qǐng)到下面公號(hào)【技術(shù)自由圈】取↓↓↓文章來源地址http://www.zghlxwxcb.cn/news/detail-833402.html

到了這里，關(guān)于得物面試：Redis用哈希槽，而不是一致性哈希，為什么？的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！