一致性 Hash 在負載均衡中的應用

簡介

一致性 Hash 是一種特殊的 Hash 算法，由於其均衡性、持久性的映射特點，被廣泛的應用於負載均衡領域，如 nginx 和 memcached 都採用了一致性 Hash 來作爲集羣負載均衡的方案。

本文將介紹一致性 Hash 的基本思路，並討論其在分佈式緩存集羣負載均衡中的應用。同時也會進行相應的代碼測試來驗證其算法特性，並給出和其他負載均衡方案的一些對比。

一致性 Hash 算法簡介

在瞭解一致性 Hash 算法之前，先來討論一下 Hash 本身的特點。普通的 Hash 函數最大的作用是散列，或者說是將一系列在形式上具有相似性質的數據，打散成隨機的、均勻分佈的數據。

比如，對字符串 abc 和 abcd 分別進行 md5 計算，得到的結果如下：

可以看到，兩個在形式上非常相近的數據經過 md5 散列後，變成了完全隨機的字符串。負載均衡正是利用這一特性，對於大量隨機的請求或調用，通過一定形式的 Hash 將他們均勻的散列，從而實現壓力的平均化。（當然，並不是只要使用了 Hash 就一定能夠獲得均勻的散列，後面會分析這一點。）

舉個例子，如果我們給每個請求生成一個 Key，只要使用一個非常簡單的 Hash 算法 Group = Key % N 來實現請求的負載均衡，如下：

（如果將 Key 作爲緩存的 Key，對應的 Group 儲存該 Key 的 Value，就可以實現一個分佈式的緩存系統，後文的具體例子都將基於這個場景）

不難發現，這樣的 Hash 只要集羣的數量 N 發生變化，之前的所有 Hash 映射就會全部失效。如果集羣中的每個機器提供的服務沒有差別，倒不會產生什麼影響，但對於分佈式緩存這樣的系統而言，映射全部失效就意味着之前的緩存全部失效，後果將會是災難性的。

一致性 Hash 通過構建環狀的 Hash 空間代替線性 Hash 空間的方法解決了這個問題，如下圖：

整個 Hash 空間被構建成一個首尾相接的環，使用一致性 Hash 時需要進行兩次映射。

第一次，給每個節點（集羣）計算 Hash，然後記錄它們的 Hash 值，這就是它們在環上的位置。

第二次，給每個 Key 計算 Hash，然後沿着順時針的方向找到環上的第一個節點，就是該 Key 儲存對應的集羣。

分析一下節點增加和刪除時對負載均衡的影響，如下圖：

可以看到，當節點被刪除時，其餘節點在環上的映射不會發生改變，只是原來打在對應節點上的 Key 現在會轉移到順時針方向的下一個節點上去。增加一個節點也是同樣的，最終都只有少部分的 Key 發生了失效。不過發生節點變動後，整體系統的壓力已經不是均衡的了，下文中提到的方法將會解決這個問題。

問題與優化

最基本的一致性 Hash 算法直接應用於負載均衡系統，效果仍然是不理想的，存在諸多問題，下面就對這些問題進行逐個分析並尋求更好的解決方案。

數據傾斜

如果節點的數量很少，而 hash 環空間很大（一般是 0 ~ 2^32），直接進行一致性 hash 上去，大部分情況下節點在環上的位置會很不均勻，擠在某個很小的區域。最終對分佈式緩存造成的影響就是，集羣的每個實例上儲存的緩存數據量不一致，會發生嚴重的數據傾斜。

緩存雪崩

如果每個節點在環上只有一個節點，那麼可以想象，當某一集羣從環中消失時，它原本所負責的任務將全部交由順時針方向的下一個集羣處理。例如，當 group0 退出時，它原本所負責的緩存將全部交給 group1 處理。這就意味着 group1 的訪問壓力會瞬間增大。

設想一下，如果 group1 因爲壓力過大而崩潰，那麼更大的壓力又會向 group2 壓過去，最終服務壓力就像滾雪球一樣越滾越大，最終導致雪崩。

引入虛擬節點

解決上述兩個問題最好的辦法就是擴展整個環上的節點數量，因此我們引入了虛擬節點的概念。一個實際節點將會映射多個虛擬節點，這樣 Hash 環上的空間分割就會變得均勻。

同時，引入虛擬節點還會使得節點在 Hash 環上的順序隨機化，這意味着當一個真實節點失效退出後，它原來所承載的壓力將會均勻地分散到其他節點上去。

如下圖：

代碼測試

現在我們嘗試編寫一些測試代碼，來看看一致性 hash 的實際效果是否符合我們預期。

首先我們需要一個能夠對輸入進行均勻散列的 Hash 算法，可供選擇的有很多，memcached 官方使用了基於 md5 的 KETAMA 算法，但這裏處於計算效率的考慮，使用了 FNV1_32_HASH 算法，如下：

public class HashUtil {
    /**
     * 計算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;
    }
}

實際使用時可以根據需求調整。

接着需要使用一種數據結構來保存 hash 環，可以採用的方案有很多種，最簡單的是採用數組或鏈表。但這樣查找的時候需要進行排序，如果節點數量多，速度就可能變得很慢。

針對集羣負載均衡狀態讀多寫少的狀態，很容易聯想到使用二叉平衡樹的結構去儲存，實際上可以使用 TreeMap（內部實現是紅黑樹）來作爲 Hash 環的儲存結構。

先編寫一個最簡單的，無虛擬節點的 Hash 環測試：

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"
    };

    /**
     * 用於保存Hash環上的節點
     */
    private static SortedMap<Integer, String> sortedMap = new TreeMap<>();

    /**
     * 初始化，將所有的服務器加入Hash環中
     */
    static {
        // 使用紅黑樹實現，插入效率比較差，但是查找效率極高
        for (String group : groups) {
            int hash = HashUtil.getHash(group);
            System.out.println("[" + group + "] launched @ " + hash);
            sortedMap.put(hash, group);
        }
    }

    /**
     * 計算對應的widget加載在哪個group上
     *
     * @param widgetKey
     * @return
     */
    private static String getServer(String widgetKey) {
        int hash = HashUtil.getHash(widgetKey);
        // 只取出所有大於該hash值的部分而不必遍歷整個Tree
        SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
        if (subMap == null || subMap.isEmpty()) {
            // hash值在最尾部，應該映射到第一個group上
            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 個隨機數字進行測試，最終得到的壓力分佈情況如下：

[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%)

可以看到壓力還是比較不平均的，所以我們繼續，引入虛擬節點：

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));

        // 將虛擬節點映射到Hash環上
        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);
        // 只取出所有大於該hash值的部分而不必遍歷整個Tree
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        String virtualNodeName;
        if (subMap == null || subMap.isEmpty()) {
            // hash值在最尾部，應該映射到第一個group上
            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 +"%)");
            }
        );
    }
}

這裏真實節點和虛擬節點的映射採用了字符串拼接的方式，這種方式雖然簡單但很有效，memcached 官方也是這麼實現的。將虛擬節點的數量設置爲 1000，重新測試壓力分佈情況，結果如下：

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%)

可以看到基本已經達到平均分佈了，接着繼續測試刪除和增加節點給整個服務帶來的影響，相關測試代碼如下：

private static void refreshHashCircle() {
    // 當集羣變動時，刷新hash環，其餘的集羣在hash環上的位置不會發生變動
  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();
}

測試刪除一個集羣前後的壓力分佈如下：

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%)

同時計算一下消失的集羣上的 Key 最終如何轉移到其他集羣上：

[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

可見，刪除集羣后，該集羣上的壓力均勻地分散給了其他集羣，最終整個集羣仍處於負載均衡狀態，符合我們的預期，最後看一下添加集羣的情況。

壓力分佈：

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%)

壓力轉移：

[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

綜上可以得出結論，在引入足夠多的虛擬節點後，一致性 hash 還是能夠比較完美地滿足負載均衡需要的。

優雅縮擴容

緩存服務器對於性能有着較高的要求，因此我們希望在擴容時新的集羣能夠較快的填充好數據並工作。但是從一個集羣啓動，到真正加入並可以提供服務之間還存在着不小的時間延遲，要實現更優雅的擴容，我們可以從兩個方面出發：

1. 高頻 Key 預熱

負載均衡器作爲路由層，是可以收集並統計每個緩存 Key 的訪問頻率的，如果能夠維護一份高頻訪問 Key 的列表，新的集羣在啓動時根據這個列表提前拉取對應 Key 的緩存值進行預熱，便可以大大減少因爲新增集羣而導致的 Key 失效。

具體的設計可以通過緩存來實現，如下：

不過這個方案在實際使用時有一個很大的限制，那就是高頻 Key 本身的緩存失效時間可能很短，預熱時儲存的 Value 在實際被訪問到時可能已經被更新或者失效，處理不當會導致出現髒數據，因此實現難度還是有一些大的。

2. 歷史 Hash 環保留

回顧一致性 Hash 的擴容，不難發現新增節點後，它所對應的 Key 在原來的節點還會保留一段時間。因此在擴容的延遲時間段，如果對應的 Key 緩存在新節點上還沒有被加載，可以去原有的節點上嘗試讀取。

舉例，假設我們原有 3 個集羣，現在要擴展到 6 個集羣，這就意味着原有 50% 的 Key 都會失效（被轉移到新節點上），如果我們維護擴容前和擴容後的兩個 Hash 環，在擴容後的 Hash 環上找不到 Key 的儲存時，先轉向擴容前的 Hash 環尋找一波，如果能夠找到就返回對應的值並將該緩存寫入新的節點上，找不到時再透過緩存，如下圖：

這樣做的缺點是增加了緩存讀取的時間，但相比於直接擊穿緩存而言還是要好很多的。優點則是可以隨意擴容多臺機器，而不會產生大面積的緩存失效。

談完了擴容，再談談縮容。

1. 熔斷機制

縮容後，剩餘各個節點上的訪問壓力都會有所增加，此時如果某個節點因爲壓力過大而宕機，就可能會引發連鎖反應。因此作爲兜底方案，應當給每個集羣設立對應熔斷機制來保護服務的穩定性。

2. 多集羣 LB 的更新延遲

這個問題在縮容時比較嚴重，如果你使用一個集羣來作爲負載均衡，並使用一個配置服務器比如 ConfigServer 來推送集羣狀態以構建 Hash 環，那麼在某個集羣退出時這個狀態並不一定會被立刻同步到所有的 LB 上，這就可能會導致一個暫時的調度不一致，如下圖：

如果某臺 LB 錯誤地將請求打到了已經退出的集羣上，就會導致緩存擊穿。解決這個問題主要有以下幾種思路：

緩慢縮容，等到 Hash 環完全同步後再操作。可以通過監聽退出集羣的訪問 QPS 來實現這一點，等到該集羣幾乎沒有 QPS 時再將其撤下。
手動刪除，如果 Hash 環上對應的節點找不到了，就手動將其從 Hash 環上刪除，然後重新進行調度，這個方式有一定的風險，對於網絡抖動等異常情況兼容的不是很好。
主動拉取和重試，當 Hash 環上節點失效時，主動從 ZK 上重新拉取集羣狀態來構建新 Hash 環，在一定次數內可以進行多次重試。

對比：HashSlot

瞭解了一致性 Hash 算法的特點後，我們也不難發現一些不盡人意的地方：

整個分佈式緩存需要一個路由服務來做負載均衡，存在單點問題（如果路由服務掛了，整個緩存也就涼了）
Hash 環上的節點非常多或者更新頻繁時，查找性能會比較低下

針對這些問題，Redis 在實現自己的分佈式集羣方案時，設計了全新的思路：基於 P2P 結構的 HashSlot 算法，下面簡單介紹一下：

1. 使用 HashSlot

類似於 Hash 環，Redis Cluster 採用 HashSlot 來實現 Key 值的均勻分佈和實例的增刪管理。

首先默認分配了 16384 個 Slot（這個大小正好可以使用 2kb 的空間保存），每個 Slot 相當於一致性 Hash 環上的一個節點。接入集羣的所有實例將均勻地佔有這些 Slot，而最終當我們 Set 一個 Key 時，使用 CRC16(Key) % 16384 來計算出這個 Key 屬於哪個 Slot，並最終映射到對應的實例上去。

那麼當增刪實例時，Slot 和實例間的對應要如何進行對應的改動呢？

舉個例子，原本有 3 個節點 A,B,C，那麼一開始創建集羣時 Slot 的覆蓋情況是：

節點A  0－5460
 節點B  5461－10922
 節點C  10923－16383

現在假設要增加一個節點 D，RedisCluster 的做法是將之前每臺機器上的一部分 Slot 移動到 D 上（注意這個過程也意味着要對節點 D 寫入的 KV 儲存），成功接入後 Slot 的覆蓋情況將變爲如下情況：

節點A  1365-5460
 節點B  6827-10922
 節點C  12288-16383
 節點D  0-1364,5461-6826,10923-1228

同理刪除一個節點，就是將其原來佔有的 Slot 以及對應的 KV 儲存均勻地歸還給其他節點。

2.P2P 節點尋找

現在我們考慮如何實現去中心化的訪問，也就是說無論訪問集羣中的哪個節點，你都能夠拿到想要的數據。其實這有點類似於路由器的路由表，具體說來就是：

每個節點都保存有完整的 HashSlot - 節點映射表，也就是說，每個節點都知道自己擁有哪些 Slot，以及某個確定的 Slot 究竟對應着哪個節點。
無論向哪個節點發出尋找 Key 的請求，該節點都會通過 CRC(Key) % 16384 計算該 Key 究竟存在於哪個 Slot，並將請求轉發至該 Slot 所在的節點。

總結一下就是兩個要點：映射表和內部轉發，這是通過著名的 **Gossip 協議 ** 來實現的。

最後我們可以給出 Redis Cluster 的系統結構圖，和一致性 Hash 環還是有着很明顯的區別的：

對比一下，HashSlot + P2P 的方案解決了去中心化的問題，同時也提供了更好的動態擴展性。但相比於一致性 Hash 而言，其結構更加複雜，實現上也更加困難。

而在之前的分析中我們也能看出，一致性 Hash 方案整體上還是有着不錯的表現的，因此在實際的系統應用中，可以根據開發成本和性能要求合理地選擇最適合的方案。總之，兩者都非常優秀，至於用哪個、怎麼用，就是仁者見仁智者見智的問題了。

作者：木士易

來源：blog.csdn.net/yangxueyangxue/article/details/105274629

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/j4JeEv2H7jyeGJMDdgfoNg

問題與優化

數據傾斜

緩存雪崩

引入虛擬節點

代碼測試

猜你喜歡