[[380706]]

 本文轉載自微信公眾號「全棧修仙之路」，作者阿寶哥   。轉載本文請聯系全棧修仙之路公眾號。

要了解一致性哈希，首先我們必須了解傳統的哈希及其在大規模分布式系統中的局限性。簡單地說，哈希就是一個鍵值對存儲，在給定鍵的情況下，可以非常高效地找到所關聯的值。假設我們要根據其郵政編碼查找城市中的街道名稱。一種最簡單的實現方式是將此信息以哈希字典的形式進行存儲 。

當數據太大而無法存儲在一個節點或機器上時，問題變得更加有趣，系統中需要多個這樣的節點或機器來存儲它。比如，使用多個 Web 緩存中間件的系統。那如何確定哪個 key 存儲在哪個節點上?針對該問題，最簡單的解決方案是使用哈希取模來確定。 給定一個 key，先對 key 進行哈希運算，將其除以系統中的節點數，然后將該 key 放入該節點。同樣，在獲取 key 時，對 key 進行哈希運算，再除以節點數，然后轉到該節點并獲取值。上述過程對應的哈希算法定義如下：

node_number = hash(key) % N # 其中 N 為節點數。 

下圖描繪了多節點系統中的傳統的哈希取模算法，基于該算法可以實現簡單的負載均衡。

一、傳統哈希取模算法的局限性

下面我們來分析一下傳統的哈希及其在大規模分布式系統中的局限性。這里我們直接使用我之前所寫文章 布隆過濾器你值得擁有的開發利器 中定義的 SimpleHash 類，然后分別對 semlinker、kakuqo 和 test 3 個鍵進行哈希運算并取余，具體代碼如下：

public class SimpleHash { 
    private int cap; 
    private int seed; 
 
    public SimpleHash(int cap, int seed) { 
        this.cap = cap; 
        this.seed = seed; 
    } 
 
    public int hash(String value) { 
        int result = 0; 
        int len = value.length(); 
        for (int i = 0; i < len; i++) { 
            result = seed * result + value.charAt(i); 
        } 
        return (cap - 1) & result; 
    } 
 
    public static void main(String[] args) { 
        SimpleHash simpleHash = new SimpleHash(2 << 12, 8); 
        System.out.println("node_number=hash(\"semlinker\") % 3 -> " +  
          simpleHash.hash("semlinker") % 3); 
        System.out.println("node_number=hash(\"kakuqo\") % 3 -> " +  
          simpleHash.hash("kakuqo") % 3); 
        System.out.println("node_number=hash(\"test\") % 3 -> " +  
          simpleHash.hash("test") % 3); 
    } 
} 

以上代碼成功運行后，在控制臺會輸出以下結果：

node_number=hash("semlinker") % 3 -> 1 
node_number=hash("kakuqo") % 3 -> 2 
node_number=hash("test") % 3 -> 0 

基于以上的輸出結果，我們可以創建以下表格：

1.1 節點減少的場景

在分布式多節點系統中，出現故障很常見。任何節點都可能在沒有任何事先通知的情況下掛掉，針對這種情況我們期望系統只是出現性能降低，正常的功能不會受到影響。 對于原始示例，當節點出現故障時會發生什么?原始示例中有的 3 個節點，假設其中 1 個節點出現故障，這時節點數發生了變化，節點個數從 3 減少為 2，此時表格的狀態發生了變化：

很明顯節點的減少會導致鍵與節點的映射關系發生變化，這個變化對于新的鍵來說并不會產生任何影響，但對于已有的鍵來說，將導致節點映射錯誤，以 “semlinker” 為例，變化前系統有 3 個節點，該鍵對應的節點編號為 1，當出現故障時，節點數減少為 2 個，此時該鍵對應的節點編號為 0。

1.2 節點增加的場景

在分布式多節點系統中，對于某些場景比如節日大促，就需要對服務節點進行擴容，以應對突發的流量。 對于原始示例，當增加節點會發生什么?原始示例中有的 3 個節點，假設進行擴容臨時增加了 1 個節點，這時節點數發生了變化，節點個數從 3 增加為 4 個，此時表格的狀態發生了變化：

很明顯節點的增加也會導致鍵與節點的映射關系發生變化，這個變化對于新的鍵來說并不會產生任何影響，但對于已有的鍵來說，將導致節點映射錯誤，同樣以 “semlinker” 為例，變化前系統有 3 個節點，該鍵對應的節點編號為 1，當增加節點時，節點數增加為 4 個，此時該鍵對應的節點編號為 2。

當集群中節點的數量發生變化時，之前的映射規則就可能發生變化。如果集群中每個機器提供的服務沒有差別，這不會有什么影響。但對于分布式緩存這種的系統而言，映射規則失效就意味著之前緩存的失效，若同一時刻出現大量的緩存失效，則可能會出現 “緩存雪崩”，這將會造成災難性的后果。

要解決此問題，我們必須在其余節點上重新分配所有現有鍵，這可能是非常昂貴的操作，并且可能對正在運行的系統產生不利影響。當然除了重新分配所有現有鍵的方案之外，還有另一種更好的方案即使用一致性哈希算法。

二、一致性哈希算法

一致性哈希算法在 1997 年由麻省理工學院提出，是一種特殊的哈希算法，在移除或者添加一個服務器時，能夠盡可能小地改變已存在的服務請求與處理請求服務器之間的映射關系。一致性哈希解決了簡單哈希算法在分布式哈希表(Distributed Hash Table，DHT)中存在的動態伸縮等問題 。

2.1 一致性哈希算法優點

• 可擴展性。一致性哈希算法保證了增加或減少服務器時，數據存儲的改變最少，相比傳統哈希算法大大節省了數據移動的開銷 。
• 更好地適應數據的快速增長。采用一致性哈希算法分布數據，當數據不斷增長時，部分虛擬節點中可能包含很多數據、造成數據在虛擬節點上分布不均衡，此時可以將包含數據多的虛擬節點分裂，這種分裂僅僅是將原有的虛擬節點一分為二、不需要對全部的數據進行重新哈希和劃分。

虛擬節點分裂后，如果物理服務器的負載仍然不均衡，只需在服務器之間調整部分虛擬節點的存儲分布。這樣可以隨數據的增長而動態的擴展物理服務器的數量，且代價遠比傳統哈希算法重新分布所有數據要小很多。

2.2 一致性哈希算法與哈希算法的關系

一致性哈希算法是在哈希算法基礎上提出的，在動態變化的分布式環境中，哈希算法應該滿足的幾個條件：平衡性、單調性和分散性。

• 平衡性：是指 hash 的結果應該平均分配到各個節點，這樣從算法上解決了負載均衡問題。
• 單調性：是指在新增或者刪減節點時，不影響系統正常運行。
• 分散性：是指數據應該分散地存放在分布式集群中的各個節點(節點自己可以有備份)，不必每個節點都存儲所有的數據。

三、一致性哈希算法原理

一致性哈希算法通過一個叫作一致性哈希環的數據結構實現。這個環的起點是 0，終點是 2^32 - 1，并且起點與終點連接，故這個環的整數分布范圍是 [0, 2^32-1]，如下圖所示：

3.1 將對象放置到哈希環

假設我們有 "semlinker"、"kakuqo"、"lolo"、"fer" 四個對象，分別簡寫為 o1、o2、o3 和 o4，然后使用哈希函數計算這個對象的 hash 值，值的范圍是 [0, 2^32-1]：

圖中對象的映射關系如下：

hash(o1) = k1; hash(o2) = k2; 
hash(o3) = k3; hash(o4) = k4; 

3.2 將服務器放置到哈希環

接著使用同樣的哈希函數，我們將服務器也放置到哈希環上，可以選擇服務器的 IP 或主機名作為鍵進行哈希，這樣每臺服務器就能確定其在哈希環上的位置。這里假設我們有 3 臺緩存服務器，分別為 cs1、cs2 和 cs3：

圖中服務器的映射關系如下：

hash(cs1) = t1; hash(cs2) = t2; hash(cs3) = t3; # Cache Server 

3.3 為對象選擇服務器

將對象和服務器都放置到同一個哈希環后，在哈希環上順時針查找距離這個對象的 hash 值最近的機器，即是這個對象所屬的機器。 以 o2 對象為例，順序針找到最近的機器是 cs2，故服務器 cs2 會緩存 o2 對象。而服務器 cs1 則緩存 o1，o3 對象，服務器 cs3 則緩存 o4 對象。

3.4 服務器增加的情況

假設由于業務需要，我們需要增加一臺服務器 cs4，經過同樣的 hash 運算，該服務器最終落于 t1 和 t2 服務器之間，具體如下圖所示：

圖片

對于上述的情況，只有 t1 和 t2 服務器之間的對象需要重新分配。在以上示例中只有 o3 對象需要重新分配，即它被重新到 cs4 服務器。在前面我們已經分析過，如果使用簡單的取模方法，當新添加服務器時可能會導致大部分緩存失效，而使用一致性哈希算法后，這種情況得到了較大的改善，因為只有少部分對象需要重新分配。

3.5 服務器減少的情況

假設 cs3 服務器出現故障導致服務下線，這時原本存儲于 cs3 服務器的對象 o4，需要被重新分配至 cs2 服務器，其它對象仍存儲在原有的機器上。

3.6 虛擬節點

到這里一致性哈希的基本原理已經介紹完了，但對于新增服務器的情況還存在一些問題。新增的服務器 cs4 只分擔了 cs1 服務器的負載，服務器 cs2 和 cs3 并沒有因為 cs4 服務器的加入而減少負載壓力。如果 cs4 服務器的性能與原有服務器的性能一致甚至可能更高，那么這種結果并不是我們所期望的。

針對這個問題，我們可以通過引入虛擬節點來解決負載不均衡的問題。即將每臺物理服務器虛擬為一組虛擬服務器，將虛擬服務器放置到哈希環上，如果要確定對象的服務器，需先確定對象的虛擬服務器，再由虛擬服務器確定物理服務器。

圖中 o1 和 o2 表示對象，v1 ~ v6 表示虛擬服務器，s1 ~ s3 表示物理服務器。

四、一致性哈希算法實現

這里我們只介紹不帶虛擬節點的一致性哈希算法實現：

import java.util.SortedMap; 
import java.util.TreeMap; 
 
public class ConsistentHashingWithoutVirtualNode { 
    //待添加入Hash環的服務器列表 
    private static String[] servers = {"192.168.0.1:8888", "192.168.0.2:8888",  
      "192.168.0.3:8888"}; 
 
    //key表示服務器的hash值，value表示服務器 
    private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>(); 
 
    //程序初始化，將所有的服務器放入sortedMap中 
    static { 
        for (int i = 0; i < servers.length; i++) { 
            int hash = getHash(servers[i]); 
            System.out.println("[" + servers[i] + "]加入集合中, 其Hash值為" + hash); 
            sortedMap.put(hash, servers[i]); 
        } 
    } 
 
    //得到應當路由到的結點 
    private static String getServer(String key) { 
        //得到該key的hash值 
        int hash = getHash(key); 
        //得到大于該Hash值的所有Map 
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash); 
        if (subMap.isEmpty()) { 
            //如果沒有比該key的hash值大的，則從第一個node開始 
            Integer i = sortedMap.firstKey(); 
            //返回對應的服務器 
            return sortedMap.get(i); 
        } else { 
            //第一個Key就是順時針過去離node最近的那個結點 
            Integer i = subMap.firstKey(); 
            //返回對應的服務器 
            return subMap.get(i); 
        } 
    } 
 
    //使用FNV1_32_HASH算法計算服務器的Hash值 
    private 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; 
    } 
 
    public static void main(String[] args) { 
        String[] keys = {"semlinker", "kakuqo", "fer"}; 
        for (int i = 0; i < keys.length; i++) 
            System.out.println("[" + keys[i] + "]的hash值為" + getHash(keys[i]) 
                    + ", 被路由到結點[" + getServer(keys[i]) + "]"); 
    } 
 
} 

以上代碼成功運行后，在控制臺會輸出以下結果：

[192.168.0.1:8888]加入集合中, 其Hash值為1326271016 
[192.168.0.2:8888]加入集合中, 其Hash值為1132535844 
[192.168.0.3:8888]加入集合中, 其Hash值為115798597 
 
[semlinker]的hash值為1549041406, 被路由到結點[192.168.0.3:8888] 
[kakuqo]的hash值為463104755, 被路由到結點[192.168.0.2:8888] 
[fer]的hash值為1677150790, 被路由到結點[192.168.0.3:8888] 

上面我們只介紹了不帶虛擬節點的一致性哈希算法實現，如果有的小伙伴對帶虛擬節點的一致性哈希算法感興趣，可以參考 一致性Hash(Consistent Hashing)原理剖析及Java實現 這篇文章。

五、總結

本文通過示例介紹了傳統的哈希取模算法在分布式系統中的局限性，進而在針對該問題的解決方案中引出了一致性哈希算法。一致性哈希算法在 1997 年由麻省理工學院提出，是一種特殊的哈希算法，在移除或者添加一個服務器時，能夠盡可能小地改變已存在的服務請求與處理請求服務器之間的映射關系。在介紹完一致性哈希算法的作用和優點等相關知識后，我們以圖解的形式生動介紹了一致性哈希算法的原理，最后給出了不帶虛擬節點的一致性哈希算法的 Java 實現。

六、參考資源

百度百科 - 一致性哈希

知乎 - 面試必備：什么是一致性 Hash 算法

Leo - 一致性Hash-Consistent-Hashing 原理剖析

CSDN - 一致性Hash(Consistent Hashing)原理剖析及Java實現

Codeproject - consistent-hashing