圖解一緻性雜湊演算法

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

<Zip Code，Street Name>

。

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

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

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

下面我們來分析一下傳統的哈希及其在大規模分布式系統中的局限性。這裡我們直接使用我之前所寫文章 布隆過濾器你值得擁有的開發利器 中定義的 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 實作。