一致性Hash是一種特殊的Hash算法，由于其均衡性萤彩、持久性的映射特點(diǎn)粪滤，被廣泛的應(yīng)用于負(fù)載均衡領(lǐng)域，如nginx和memcached都采用了一致性Hash來作為集群負(fù)載均衡的方案雀扶。

本文將介紹一致性Hash的基本思路杖小，并討論其在分布式緩存集群負(fù)載均衡中的應(yīng)用。同時(shí)也會進(jìn)行相應(yīng)的代碼測試來驗(yàn)證其算法特性愚墓，并給出和其他負(fù)載均衡方案的一些對比予权。

在了解一致性Hash算法之前，先來討論一下Hash本身的特點(diǎn)浪册。普通的Hash函數(shù)最大的作用是散列扫腺，或者說是將一系列在形式上具有相似性質(zhì)的數(shù)據(jù)，打散成隨機(jī)的村象、均勻分布的數(shù)據(jù)笆环。比如，對字符串a(chǎn)bc和abcd分別進(jìn)行md5計(jì)算厚者，得到的結(jié)果如下：

image

可以看到躁劣，兩個(gè)在形式上非常相近的數(shù)據(jù)經(jīng)過md5散列后，變成了完全隨機(jī)的字符串库菲。負(fù)載均衡正是利用這一特性账忘，對于大量隨機(jī)的請求或調(diào)用，通過一定形式的Hash將他們均勻的散列蝙昙，從而實(shí)現(xiàn)壓力的平均化闪萄。（當(dāng)然，并不是只要使用了Hash就一定能夠獲得均勻的散列奇颠，后面會分析這一點(diǎn)败去。）

舉個(gè)例子，如果我們給每個(gè)請求生成一個(gè)Key烈拒，只要使用一個(gè)非常簡單的Hash算法Group = Key % N來實(shí)現(xiàn)請求的負(fù)載均衡圆裕，如下：

image

（如果將Key作為緩存的Key广鳍，對應(yīng)的Group儲存該Key的Value，就可以實(shí)現(xiàn)一個(gè)分布式的緩存系統(tǒng)吓妆，后文的具體例子都將基于這個(gè)場景） 不難發(fā)現(xiàn)赊时，這樣的Hash只要集群的數(shù)量N發(fā)生變化，之前的所有Hash映射就會全部失效行拢。

如果集群中的每個(gè)機(jī)器提供的服務(wù)沒有差別祖秒，倒不會產(chǎn)生什么影響，但對于分布式緩存這樣的系統(tǒng)而言舟奠，映射全部失效就意味著之前的緩存全部失效竭缝，后果將會是災(zāi)難性的。

一致性Hash通過構(gòu)建環(huán)狀的Hash空間代替線性Hash空間的方法解決了這個(gè)問題沼瘫，如下圖：

image

整個(gè)Hash空間被構(gòu)建成一個(gè)首尾相接的環(huán)抬纸，使用一致性Hash時(shí)需要進(jìn)行兩次映射。

第一次耿戚，給每個(gè)節(jié)點(diǎn)（集群）計(jì)算Hash湿故，然后記錄它們的Hash值，這就是它們在環(huán)上的位置膜蛔。

第二次坛猪，給每個(gè)Key計(jì)算Hash，然后沿著順時(shí)針的方向找到環(huán)上的第一個(gè)節(jié)點(diǎn)飞几，就是該Key儲存對應(yīng)的集群砚哆。分析一下節(jié)點(diǎn)增加和刪除時(shí)對負(fù)載均衡的影響独撇，如下圖：

image

可以看到屑墨，當(dāng)節(jié)點(diǎn)被刪除時(shí)，其余節(jié)點(diǎn)在環(huán)上的映射不會發(fā)生改變纷铣，只是原來打在對應(yīng)節(jié)點(diǎn)上的Key現(xiàn)在會轉(zhuǎn)移到順時(shí)針方向的下一個(gè)節(jié)點(diǎn)上去卵史。增加一個(gè)節(jié)點(diǎn)也是同樣的，最終都只有少部分的Key發(fā)生了失效搜立。不過發(fā)生節(jié)點(diǎn)變動后以躯，整體系統(tǒng)的壓力已經(jīng)不是均衡的了，下文中提到的方法將會解決這個(gè)問題啄踊。

最基本的一致性Hash算法直接應(yīng)用于負(fù)載均衡系統(tǒng)忧设，效果仍然是不理想的，存在諸多問題颠通，下面就對這些問題進(jìn)行逐個(gè)分析并尋求更好的解決方案址晕。

如果節(jié)點(diǎn)的數(shù)量很少，而hash環(huán)空間很大（一般是 0 ~ 2^32）顿锰，直接進(jìn)行一致性hash上去谨垃，大部分情況下節(jié)點(diǎn)在環(huán)上的位置會很不均勻启搂，擠在某個(gè)很小的區(qū)域。最終對分布式緩存造成的影響就是刘陶，集群的每個(gè)實(shí)例上儲存的緩存數(shù)據(jù)量不一致胳赌，會發(fā)生嚴(yán)重的數(shù)據(jù)傾斜。

如果每個(gè)節(jié)點(diǎn)在環(huán)上只有一個(gè)節(jié)點(diǎn)匙隔，那么可以想象疑苫，當(dāng)某一集群從環(huán)中消失時(shí)，它原本所負(fù)責(zé)的任務(wù)將全部交由順時(shí)針方向的下一個(gè)集群處理纷责。例如缀匕，當(dāng)group0退出時(shí)，它原本所負(fù)責(zé)的緩存將全部交給group1處理碰逸。這就意味著group1的訪問壓力會瞬間增大乡小。

設(shè)想一下，如果group1因?yàn)閴毫^大而崩潰饵史，那么更大的壓力又會向group2壓過去满钟，最終服務(wù)壓力就像滾雪球一樣越滾越大，最終導(dǎo)致雪崩胳喷。

解決上述兩個(gè)問題最好的辦法就是擴(kuò)展整個(gè)環(huán)上的節(jié)點(diǎn)數(shù)量湃番，因此我們引入了虛擬節(jié)點(diǎn)的概念。一個(gè)實(shí)際節(jié)點(diǎn)將會映射多個(gè)虛擬節(jié)點(diǎn)吭露，這樣Hash環(huán)上的空間分割就會變得均勻吠撮。同時(shí)，引入虛擬節(jié)點(diǎn)還會使得節(jié)點(diǎn)在Hash環(huán)上的順序隨機(jī)化讲竿，這意味著當(dāng)一個(gè)真實(shí)節(jié)點(diǎn)失效退出后泥兰，它原來所承載的壓力將會均勻地分散到其他節(jié)點(diǎn)上去。如下圖：

image

現(xiàn)在我們嘗試編寫一些測試代碼题禀，來看看一致性hash的實(shí)際效果是否符合我們預(yù)期鞋诗。首先我們需要一個(gè)能夠?qū)斎脒M(jìn)行均勻散列的Hash算法，可供選擇的有很多迈嘹，memcached官方使用了基于md5的KETAMA算法削彬，但這里處于計(jì)算效率的考慮，使用了FNV1_32_HASH算法秀仲，如下：

public class HashUtil {  
    /**  
     * 計(jì)算Hash值, 使用FNV1_32_HASH算法  
     * @param str  
     * @return  
     */  
    public static int getHash(String str) {  
        final int p = 16777619;  
        int hash = (int)2166136261L;  
        for (int i = 0; i < str.length(); i++) {  
            hash =( hash ^ str.charAt(i) ) * p;  
        }  
        hash += hash << 13;  
        hash ^= hash >> 7;  
        hash += hash << 3;  
        hash ^= hash >> 17;  
        hash += hash << 5;  
  
        if (hash < 0) {  
            hash = Math.abs(hash);  
        }  
        return hash;  
    }  
}  

實(shí)際使用時(shí)可以根據(jù)需求調(diào)整融痛。接著需要使用一種數(shù)據(jù)結(jié)構(gòu)來保存hash環(huán)，可以采用的方案有很多種神僵，最簡單的是采用數(shù)組或鏈表雁刷。但這樣查找的時(shí)候需要進(jìn)行排序，如果節(jié)點(diǎn)數(shù)量多挑豌，速度就可能變得很慢安券。

針對集群負(fù)載均衡狀態(tài)讀多寫少的狀態(tài)墩崩，很容易聯(lián)想到使用二叉平衡樹的結(jié)構(gòu)去儲存，實(shí)際上可以使用TreeMap（內(nèi)部實(shí)現(xiàn)是紅黑樹）來作為Hash環(huán)的儲存結(jié)構(gòu)侯勉。先編寫一個(gè)最簡單的鹦筹，無虛擬節(jié)點(diǎn)的Hash環(huán)測試：

public class ConsistentHashingWithoutVirtualNode {  
  
      
    private static String[] groups = {  
        "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",  
        "192.168.0.3:111", "192.168.0.4:111"  
    };  
  
      
    private static SortedMap<Integer, String> sortedMap = new TreeMap<>();  
  
      
    static {  
        
        for (String group : groups) {  
            int hash = HashUtil.getHash(group);  
            System.out.println("[" + group + "] launched @ " + hash);  
            sortedMap.put(hash, group);  
        }  
    }  
  
      
    private static String getServer(String widgetKey) {  
        int hash = HashUtil.getHash(widgetKey);  
        
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);  
        if (subMap == null || subMap.isEmpty()) {  
            
            return sortedMap.get(sortedMap.firstKey());  
        }  
        return subMap.get(subMap.firstKey());  
    }  
  
    public static void main(String[] args) {  
        
        Map<String, Integer> resMap = new HashMap<>();  
  
        for (int i = 0; i < 100000; i++) {  
            Integer widgetId = (int)(Math.random() * 10000);  
            String server = getServer(widgetId.toString());  
            if (resMap.containsKey(server)) {  
                resMap.put(server, resMap.get(server) + 1);  
            } else {  
                resMap.put(server, 1);  
            }  
        }  
  
        resMap.forEach(  
            (k, v) -> {  
                System.out.println("group " + k + ": " + v + "(" + v/1000.0D +"%)");  
            }  
        );  
    }  
}  

生成10000個(gè)隨機(jī)數(shù)字進(jìn)行測試，最終得到的壓力分布情況如下：

[192.168.0.1:111] launched @ 8518713  
[192.168.0.2:111] launched @ 1361847097  
[192.168.0.3:111] launched @ 1171828661  
[192.168.0.4:111] launched @ 1764547046  
group 192.168.0.2:111: 8572(8.572%)  
group 192.168.0.1:111: 18693(18.693%)  
group 192.168.0.4:111: 17764(17.764%)  
group 192.168.0.3:111: 27870(27.87%)  
group 192.168.0.0:111: 27101(27.101%) 

可以看到壓力還是比較不平均的址貌，所以我們繼續(xù)铐拐，引入虛擬節(jié)點(diǎn)：

public class ConsistentHashingWithVirtualNode {  
      
    private static String[] groups = {  
        "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",  
        "192.168.0.3:111", "192.168.0.4:111"  
    };  
  
      
    private static List<String> realGroups = new LinkedList<>();  
  
      
    private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();  
  
    private static final int VIRTUAL_NODE_NUM = 1000;  
  
    static {  
        
        realGroups.addAll(Arrays.asList(groups));  
  
        
        for (String realGroup: realGroups) {  
            for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {  
                String virtualNodeName = getVirtualNodeName(realGroup, i);  
                int hash = HashUtil.getHash(virtualNodeName);  
                System.out.println("[" + virtualNodeName + "] launched @ " + hash);  
                virtualNodes.put(hash, virtualNodeName);  
            }  
        }  
    }  
  
    private static String getVirtualNodeName(String realName, int num) {  
        return realName + "&&VN" + String.valueOf(num);  
    }  
  
    private static String getRealNodeName(String virtualName) {  
        return virtualName.split("&&")[0];  
    }  
  
    private static String getServer(String widgetKey) {  
        int hash = HashUtil.getHash(widgetKey);  
        
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);  
        String virtualNodeName;  
        if (subMap == null || subMap.isEmpty()) {  
            
            virtualNodeName = virtualNodes.get(virtualNodes.firstKey());  
        }else {  
            virtualNodeName = subMap.get(subMap.firstKey());  
        }  
        return getRealNodeName(virtualNodeName);  
    }  
  
    public static void main(String[] args) {  
        
        Map<String, Integer> resMap = new HashMap<>();  
  
        for (int i = 0; i < 100000; i++) {  
            Integer widgetId = i;  
            String group = getServer(widgetId.toString());  
            if (resMap.containsKey(group)) {  
                resMap.put(group, resMap.get(group) + 1);  
            } else {  
                resMap.put(group, 1);  
            }  
        }  
  
        resMap.forEach(  
            (k, v) -> {  
                System.out.println("group " + k + ": " + v + "(" + v/100000.0D +"%)");  
            }  
        );  
    }  
} 

這里真實(shí)節(jié)點(diǎn)和虛擬節(jié)點(diǎn)的映射采用了字符串拼接的方式，這種方式雖然簡單但很有效练对，memcached官方也是這么實(shí)現(xiàn)的遍蟋。將虛擬節(jié)點(diǎn)的數(shù)量設(shè)置為1000，重新測試壓力分布情況螟凭，結(jié)果如下：

group 192.168.0.2:111: 18354(18.354%)  
group 192.168.0.1:111: 20062(20.062%)  
group 192.168.0.4:111: 20749(20.749%)  
group 192.168.0.3:111: 20116(20.116%)  
group 192.168.0.0:111: 20719(20.719%)  

可以看到基本已經(jīng)達(dá)到平均分布了虚青，接著繼續(xù)測試刪除和增加節(jié)點(diǎn)給整個(gè)服務(wù)帶來的影響，相關(guān)測試代碼如下：

private static void refreshHashCircle() {  
    
  virtualNodes.clear();  
    for (String realGroup: realGroups) {  
      for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {  
           String virtualNodeName = getVirtualNodeName(realGroup, i);  
            int hash = HashUtil.getHash(virtualNodeName);  
            System.out.println("[" + virtualNodeName + "] launched @ " + hash);  
            virtualNodes.put(hash, virtualNodeName);  
        }  
    }  
}  
private static void addGroup(String identifier) {  
  realGroups.add(identifier);  
    refreshHashCircle();  
}  
  
private static void removeGroup(String identifier) {  
    int i = 0;  
    for (String group:realGroups) {  
      if (group.equals(identifier)) {  
          realGroups.remove(i);  
        }  
        i++;  
    }  
    refreshHashCircle();  
}  

測試刪除一個(gè)集群前后的壓力分布如下：

running the normal test.  
group 192.168.0.2:111: 19144(19.144%)  
group 192.168.0.1:111: 20244(20.244%)  
group 192.168.0.4:111: 20923(20.923%)  
group 192.168.0.3:111: 19811(19.811%)  
group 192.168.0.0:111: 19878(19.878%)  
removed a group, run test again.  
group 192.168.0.2:111: 23409(23.409%)  
group 192.168.0.1:111: 25628(25.628%)  
group 192.168.0.4:111: 25583(25.583%)  
group 192.168.0.0:111: 25380(25.38%)  

同時(shí)計(jì)算一下消失的集群上的Key最終如何轉(zhuǎn)移到其他集群上：

[192.168.0.1:111-192.168.0.4:111] :5255  
[192.168.0.1:111-192.168.0.3:111] :5090  
[192.168.0.1:111-192.168.0.2:111] :5069  
[192.168.0.1:111-192.168.0.0:111] :4938  

可見螺男，刪除集群后棒厘，該集群上的壓力均勻地分散給了其他集群，最終整個(gè)集群仍處于負(fù)載均衡狀態(tài)下隧，符合我們的預(yù)期奢人，最后看一下添加集群的情況。壓力分布：

running the normal test.  
group 192.168.0.2:111: 18890(18.89%)  
group 192.168.0.1:111: 20293(20.293%)  
group 192.168.0.4:111: 21000(21.0%)  
group 192.168.0.3:111: 19816(19.816%)  
group 192.168.0.0:111: 20001(20.001%)  
add a group, run test again.  
group 192.168.0.2:111: 15524(15.524%)  
group 192.168.0.7:111: 16928(16.928%)  
group 192.168.0.1:111: 16888(16.888%)  
group 192.168.0.4:111: 16965(16.965%)  
group 192.168.0.3:111: 16768(16.768%)  
group 192.168.0.0:111: 16927(16.927%) 

壓力轉(zhuǎn)移：

[192.168.0.0:111-192.168.0.7:111] :3102  
[192.168.0.4:111-192.168.0.7:111] :4060  
[192.168.0.2:111-192.168.0.7:111] :3313  
[192.168.0.1:111-192.168.0.7:111] :3292  
[192.168.0.3:111-192.168.0.7:111] :3261 

綜上可以得出結(jié)論淆院，在引入足夠多的虛擬節(jié)點(diǎn)后何乎，一致性hash還是能夠比較完美地滿足負(fù)載均衡需要的。

緩存服務(wù)器對于性能有著較高的要求土辩，因此我們希望在擴(kuò)容時(shí)新的集群能夠較快的填充好數(shù)據(jù)并工作支救。但是從一個(gè)集群啟動，到真正加入并可以提供服務(wù)之間還存在著不小的時(shí)間延遲脯燃，要實(shí)現(xiàn)更優(yōu)雅的擴(kuò)容搂妻，我們可以從兩個(gè)方面出發(fā)：

1.高頻Key預(yù)熱

負(fù)載均衡器作為路由層蒙保，是可以收集并統(tǒng)計(jì)每個(gè)緩存Key的訪問頻率的辕棚，如果能夠維護(hù)一份高頻訪問Key的列表，新的集群在啟動時(shí)根據(jù)這個(gè)列表提前拉取對應(yīng)Key的緩存值進(jìn)行預(yù)熱邓厕，便可以大大減少因?yàn)樾略黾憾鴮?dǎo)致的Key失效逝嚎。

具體的設(shè)計(jì)可以通過緩存來實(shí)現(xiàn)，如下：

``

不過這個(gè)方案在實(shí)際使用時(shí)有一個(gè)很大的限制详恼，那就是高頻Key本身的緩存失效時(shí)間可能很短补君，預(yù)熱時(shí)儲存的Value在實(shí)際被訪問到時(shí)可能已經(jīng)被更新或者失效，處理不當(dāng)會導(dǎo)致出現(xiàn)臟數(shù)據(jù)昧互，因此實(shí)現(xiàn)難度還是有一些大的挽铁。

2.歷史Hash環(huán)保留

回顧一致性Hash的擴(kuò)容伟桅，不難發(fā)現(xiàn)新增節(jié)點(diǎn)后，它所對應(yīng)的Key在原來的節(jié)點(diǎn)還會保留一段時(shí)間叽掘。因此在擴(kuò)容的延遲時(shí)間段楣铁，如果對應(yīng)的Key緩存在新節(jié)點(diǎn)上還沒有被加載，可以去原有的節(jié)點(diǎn)上嘗試讀取更扁。

舉例盖腕，假設(shè)我們原有3個(gè)集群，現(xiàn)在要擴(kuò)展到6個(gè)集群浓镜，這就意味著原有50%的Key都會失效（被轉(zhuǎn)移到新節(jié)點(diǎn)上）溃列，如果我們維護(hù)擴(kuò)容前和擴(kuò)容后的兩個(gè)Hash環(huán)，在擴(kuò)容后的Hash環(huán)上找不到Key的儲存時(shí)膛薛，先轉(zhuǎn)向擴(kuò)容前的Hash環(huán)尋找一波听隐，如果能夠找到就返回對應(yīng)的值并將該緩存寫入新的節(jié)點(diǎn)上，找不到時(shí)再透過緩存哄啄，如下圖：

image

這樣做的缺點(diǎn)是增加了緩存讀取的時(shí)間遵绰，但相比于直接擊穿緩存而言還是要好很多的。優(yōu)點(diǎn)則是可以隨意擴(kuò)容多臺機(jī)器增淹，而不會產(chǎn)生大面積的緩存失效椿访。談完了擴(kuò)容，再談?wù)効s容虑润。

1.熔斷機(jī)制

縮容后成玫，剩余各個(gè)節(jié)點(diǎn)上的訪問壓力都會有所增加，此時(shí)如果某個(gè)節(jié)點(diǎn)因?yàn)閴毫^大而宕機(jī)拳喻，就可能會引發(fā)連鎖反應(yīng)哭当。因此作為兜底方案，應(yīng)當(dāng)給每個(gè)集群設(shè)立對應(yīng)熔斷機(jī)制來保護(hù)服務(wù)的穩(wěn)定性冗澈。

2.多集群LB的更新延遲

這個(gè)問題在縮容時(shí)比較嚴(yán)重钦勘，如果你使用一個(gè)集群來作為負(fù)載均衡，并使用一個(gè)配置服務(wù)器比如ConfigServer來推送集群狀態(tài)以構(gòu)建Hash環(huán)亚亲，那么在某個(gè)集群退出時(shí)這個(gè)狀態(tài)并不一定會被立刻同步到所有的LB上彻采，這就可能會導(dǎo)致一個(gè)暫時(shí)的調(diào)度不一致，如下圖：

image

如果某臺LB錯(cuò)誤地將請求打到了已經(jīng)退出的集群上捌归，就會導(dǎo)致緩存擊穿肛响。解決這個(gè)問題主要有以下幾種思路：

• 緩慢縮容，等到Hash環(huán)完全同步后再操作惜索√厮瘢可以通過監(jiān)聽退出集群的訪問QPS來實(shí)現(xiàn)這一點(diǎn)，等到該集群幾乎沒有QPS時(shí)再將其撤下巾兆。

• 手動刪除猎物，如果Hash環(huán)上對應(yīng)的節(jié)點(diǎn)找不到了虎囚，就手動將其從Hash環(huán)上刪除，然后重新進(jìn)行調(diào)度蔫磨，這個(gè)方式有一定的風(fēng)險(xiǎn)溜宽，對于網(wǎng)絡(luò)抖動等異常情況兼容的不是很好。

• 主動拉取和重試质帅，當(dāng)Hash環(huán)上節(jié)點(diǎn)失效時(shí)适揉，主動從ZK上重新拉取集群狀態(tài)來構(gòu)建新Hash環(huán)，在一定次數(shù)內(nèi)可以進(jìn)行多次重試煤惩。

了解了一致性Hash算法的特點(diǎn)后嫉嘀，我們也不難發(fā)現(xiàn)一些不盡人意的地方：

• 整個(gè)分布式緩存需要一個(gè)路由服務(wù)來做負(fù)載均衡，存在單點(diǎn)問題（如果路由服務(wù)掛了魄揉，整個(gè)緩存也就涼了）

• Hash環(huán)上的節(jié)點(diǎn)非常多或者更新頻繁時(shí)剪侮，查找性能會比較低下

針對這些問題，Redis在實(shí)現(xiàn)自己的分布式集群方案時(shí)洛退，設(shè)計(jì)了全新的思路：基于P2P結(jié)構(gòu)的HashSlot算法瓣俯，下面簡單介紹一下：

1.使用HashSlot

類似于Hash環(huán)，Redis Cluster采用HashSlot來實(shí)現(xiàn)Key值的均勻分布和實(shí)例的增刪管理兵怯。

首先默認(rèn)分配了16384個(gè)Slot（這個(gè)大小正好可以使用2kb的空間保存）彩匕，每個(gè)Slot相當(dāng)于一致性Hash環(huán)上的一個(gè)節(jié)點(diǎn)。接入集群的所有實(shí)例將均勻地占有這些Slot媒区，而最終當(dāng)我們Set一個(gè)Key時(shí)驼仪，使用CRC16(Key) % 16384來計(jì)算出這個(gè)Key屬于哪個(gè)Slot，并最終映射到對應(yīng)的實(shí)例上去袜漩。

那么當(dāng)增刪實(shí)例時(shí)绪爸，Slot和實(shí)例間的對應(yīng)要如何進(jìn)行對應(yīng)的改動呢？

舉個(gè)例子宙攻，原本有3個(gè)節(jié)點(diǎn)A,B,C奠货，那么一開始創(chuàng)建集群時(shí)Slot的覆蓋情況是：

節(jié)點(diǎn)A  0－5460  
節(jié)點(diǎn)B  5461－10922  
節(jié)點(diǎn)C  10923－16383 

現(xiàn)在假設(shè)要增加一個(gè)節(jié)點(diǎn)D，RedisCluster的做法是將之前每臺機(jī)器上的一部分Slot移動到D上（注意這個(gè)過程也意味著要對節(jié)點(diǎn)D寫入的KV儲存）座掘，成功接入后Slot的覆蓋情況將變?yōu)槿缦虑闆r：

節(jié)點(diǎn)A  1365-5460  
節(jié)點(diǎn)B  6827-10922  
節(jié)點(diǎn)C  12288-16383  
節(jié)點(diǎn)D  0-1364,5461-6826,10923-1228 

同理刪除一個(gè)節(jié)點(diǎn)递惋，就是將其原來占有的Slot以及對應(yīng)的KV儲存均勻地歸還給其他節(jié)點(diǎn)。

2.P2P節(jié)點(diǎn)尋找

現(xiàn)在我們考慮如何實(shí)現(xiàn)去中心化的訪問雹顺，也就是說無論訪問集群中的哪個(gè)節(jié)點(diǎn)丹墨，你都能夠拿到想要的數(shù)據(jù)。其實(shí)這有點(diǎn)類似于路由器的路由表嬉愧，具體說來就是：

每個(gè)節(jié)點(diǎn)都保存有完整的HashSlot - 節(jié)點(diǎn)映射表，也就是說喉前，每個(gè)節(jié)點(diǎn)都知道自己擁有哪些Slot没酣，以及某個(gè)確定的Slot究竟對應(yīng)著哪個(gè)節(jié)點(diǎn)王财。

無論向哪個(gè)節(jié)點(diǎn)發(fā)出尋找Key的請求，該節(jié)點(diǎn)都會通過CRC(Key) % 16384計(jì)算該Key究竟存在于哪個(gè)Slot裕便，并將請求轉(zhuǎn)發(fā)至該Slot所在的節(jié)點(diǎn)绒净。

總結(jié)一下就是兩個(gè)要點(diǎn)：映射表和內(nèi)部轉(zhuǎn)發(fā)，這是通過著名的 Gossip協(xié)議 來實(shí)現(xiàn)的偿衰。

最后我們可以給出Redis Cluster的系統(tǒng)結(jié)構(gòu)圖挂疆，和一致性Hash環(huán)還是有著很明顯的區(qū)別的：

image

對比一下，HashSlot + P2P的方案解決了去中心化的問題下翎，同時(shí)也提供了更好的動態(tài)擴(kuò)展性缤言。但相比于一致性Hash而言，其結(jié)構(gòu)更加復(fù)雜视事，實(shí)現(xiàn)上也更加困難胆萧。

而在之前的分析中我們也能看出，一致性Hash方案整體上還是有著不錯(cuò)的表現(xiàn)的俐东，因此在實(shí)際的系統(tǒng)應(yīng)用中跌穗，可以根據(jù)開發(fā)成本和性能要求合理地選擇最適合的方案÷脖瑁總之蚌吸，兩者都非常優(yōu)秀，至于用哪個(gè)砌庄、怎么用套利，就是仁者見仁智者見智的問題了。