本文主要講解了一致性哈希算法的原理以及其存在的數據傾斜的問題，然后引出解決數據傾斜問題的方法，最后分析一致性哈希算法在 Dubbo 中的使用。通過這篇文章，可以了解到一致性哈希算法的原理以及這種算法存在的問題和解決方案。

一、負載均衡

在這里引用 dubbo 官網的一段話 ——

LoadBalance 中文意思為負載均衡，它的職責是將網絡請求，或者其他形式的負載 “均攤” 到不同的機器上。避免集群中部分服務器壓力過大，而另一些服務器比較空閑的情況。通過負載均衡，可以讓每臺服務器獲取到適合自己處理能力的負載。在為高負載服務器分流的同時，還可以避免資源浪費，一舉兩得。負載均衡可分為軟件負載均衡和硬件負載均衡。在我們日常開發中，一般很難接觸到硬件負載均衡。但軟件負載均衡還是可以接觸到的，比如 Nginx。在 Dubbo 中，也有負載均衡的概念和相應的實現。

Dubbo 需要對服務消費者的調用請求進行分配，避免少數服務提供者負載過大。服務提供者負載過大，會導致部分請求超時。因此將負載均衡到每個服務提供者上，是非常必要的。Dubbo 提供了 4 種負載均衡實現，分別是基于權重隨機算法的 RandomLoadBalance、基于最少活躍調用數算法的 LeastActiveLoadBalance、基于 hash 一致性的 ConsistentHashLoadBalance，以及基于加權輪詢算法的 RoundRobinLoadBalance。這幾個負載均衡算法代碼不是很長，但是想看懂也不是很容易，需要對這幾個算法的原理有一定了解才行。

二、哈希算法

圖 1 無哈希算法請求

如上所示，假設 0,1,2 號服務器都存儲的有用戶信息，那么當我們需要獲取某用戶信息時，因為我們不知道該用戶信息存放在哪一臺服務器中，所以需要分別查詢 0,1,2 號服務器。這樣獲取數據的效率是極低的。

對于這樣的場景，我們可以引入哈希算法。

圖 2 引入哈希算法后的請求

還是上面的場景，但前提是每一臺服務器存放用戶信息時是根據某一種哈希算法存放的。所以取用戶信息的時候，也按照同樣的哈希算法取即可。

假設我們要查詢用戶號為 100 的用戶信息，經過某個哈希算法，比如這里的 userId mod n，即 100 mod 3 結果為 1。所以用戶號 100 的這個請求最終會被 1 號服務器接收并處理。

這樣就解決了無效查詢的問題。

但是這樣的方案會帶來什么問題呢？

擴容或者縮容時，會導致大量的數據遷移。最少也會影響 50% 的數據。

圖 3 增加一臺服務器

為了說明問題，加入一臺服務器 3。服務器的數量 n 就從 3 變成了 4。還是查詢用戶號為 100 的用戶信息時，100 mod 4 結果為 0。這時，請求就被 0 號服務器接收了。

• 當服務器數量為 3 時，用戶號為 100 的請求會被 1 號服務器處理。
• 當服務器數量為 4 時，用戶號為 100 的請求會被 0 號服務器處理。

所以，當服務器數量增加或者減少時，一定會涉及到大量數據遷移的問題。

對于上述哈希算法其優點是簡單易用，大多數分庫分表規則就采取的這種方式。一般是提前根據數據量，預先估算好分區數。

其缺點是由于擴容或收縮節點導致節點數量變化時，節點的映射關系需要重新計算，會導致數據進行遷移。所以擴容時通常采用翻倍擴容，避免數據映射全部被打亂，導致全量遷移的情況，這樣只會發生 50% 的數據遷移。

三、一致性哈希算法

** 一致性 hash 算法由麻省理工學院的 Karger 及其合作者于 1997 年提出的，算法提出之初是用于大規模緩存系統的負載均衡。** 它的工作過程是這樣的，首先根據 ip 或者其他的信息為緩存節點生成一個 hash，并將這個 hash 投射到 [0, 232 - 1] 的圓環上。當有查詢或寫入請求時，則為緩存項的 key 生成一個 hash 值。然后查找第一個大于或等于該 hash 值的緩存節點，并到這個節點中查詢或寫入緩存項。如果當前節點掛了，則在下一次查詢或寫入緩存時，為緩存項查找另一個大于其 hash 值的緩存節點即可。大致效果如下圖所示，每個緩存節點在圓環上占據一個位置。如果緩存項的 key 的 hash 值小于緩存節點 hash 值，則到該緩存節點中存儲或讀取緩存項。比如下面綠色點對應的緩存項將會被存儲到 cache-2 節點中。由于 cache-3 掛了，原本應該存到該節點中的緩存項最終會存儲到 cache-4 節點中。

圖 4 一致性哈希算法

在一致性哈希算法中，不管是增加節點，還是宕機節點，受影響的區間僅僅是增加或者宕機服務器在哈希環空間中，逆時針方向遇到的第一臺服務器之間的區間，其它區間不會受到影響。

但是一致性哈希也是存在問題的：

圖 5 數據傾斜

當節點很少的時候可能會出現這樣的分布情況，A 服務會承擔大部分請求。這種情況就叫做數據傾斜。

那如何解決數據傾斜的問題呢？

加入虛擬節點。

首先一個服務器根據需要可以有多個虛擬節點。假設一臺服務器有 n 個虛擬節點。那么哈希計算時，可以使用 IP + 端口 + 編號的形式進行哈希值計算。其中的編號就是 0 到 n 的數字。由于 IP + 端口是一樣的，所以這 n 個節點都是指向的同一臺機器。

圖 6 引入虛擬節點

在沒有加入虛擬節點之前，A 服務器承擔了絕大多數的請求。但是假設每個服務器有一個虛擬節點（A-1，B-1，C-1），經過哈希計算后落在了如上圖所示的位置。那么 A 服務器的承擔的請求就在一定程度上（圖中標注了五角星的部分）分攤給了 B-1、C-1 虛擬節點，實際上就是分攤給了 B、C 服務器。

一致性哈希算法中，加入虛擬節點，可以解決數據傾斜問題。

四、一致性哈希在 DUBBO 中的應用

圖 7 Dubbo 中一致性哈希環

這里相同顏色的節點均屬于同一個服務提供者，比如 Invoker1-1，Invoker1-2，……, Invoker1-160。這樣做的目的是通過引入虛擬節點，讓 Invoker 在圓環上分散開來，避免數據傾斜問題。所謂數據傾斜是指，由于節點不夠分散，導致大量請求落到了同一個節點上，而其他節點只會接收到了少量請求的情況。比如：

圖 8 數據傾斜問題

如上，由于 Invoker-1 和 Invoker-2 在圓環上分布不均，導致系統中 75% 的請求都會落到 Invoker-1 上，只有 25% 的請求會落到 Invoker-2 上。解決這個問題辦法是引入虛擬節點，通過虛擬節點均衡各個節點的請求量。

到這里背景知識就普及完了，接下來開始分析源碼。我們先從 ConsistentHashLoadBalance 的 doSelect 方法開始看起，如下：

public class ConsistentHashLoadBalance extends AbstractLoadBalance {


    private final ConcurrentMap<String, ConsistentHashSelector<?>> selectors = 
        new ConcurrentHashMap<String, ConsistentHashSelector<?>>();


    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        String methodName = RpcUtils.getMethodName(invocation);
        String key = invokers.get(0).getUrl().getServiceKey() + "." + methodName;


        // 獲取 invokers 原始的 hashcode
        int identityHashCode = System.identityHashCode(invokers);
        ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
        // 如果 invokers 是一個新的 List 對象，意味著服務提供者數量發生了變化，可能新增也可能減少了。
        // 此時 selector.identityHashCode != identityHashCode 條件成立
        if (selector == null || selector.identityHashCode != identityHashCode) {
            // 創建新的 ConsistentHashSelector
            selectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));
            selector = (ConsistentHashSelector<T>) selectors.get(key);
        }


        // 調用 ConsistentHashSelector 的 select 方法選擇 Invoker
        return selector.select(invocation);
    }
    
    private static final class ConsistentHashSelector<T> {...}
}

如上，doSelect 方法主要做了一些前置工作，比如檢測 invokers 列表是不是變動過，以及創建 ConsistentHashSelector。這些工作做完后，接下來開始調用 ConsistentHashSelector 的 select 方法執行負載均衡邏輯。在分析 select 方法之前，我們先來看一下一致性 hash 選擇器 ConsistentHashSelector 的初始化過程，如下：

private static final class ConsistentHashSelector<T> {


    // 使用 TreeMap 存儲 Invoker 虛擬節點
    private final TreeMap<Long, Invoker<T>> virtualInvokers;


    private final int replicaNumber;


    private final int identityHashCode;


    private final int[] argumentIndex;


    ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
        this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
        this.identityHashCode = identityHashCode;
        URL url = invokers.get(0).getUrl();
        // 獲取虛擬節點數，默認為160
        this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
        // 獲取參與 hash 計算的參數下標值，默認對第一個參數進行 hash 運算
        String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0"));
        argumentIndex = new int[index.length];
        for (int i = 0; i < index.length; i++) {
            argumentIndex[i] = Integer.parseInt(index[i]);
        }
        for (Invoker<T> invoker : invokers) {
            String address = invoker.getUrl().getAddress();
            for (int i = 0; i < replicaNumber / 4; i++) {
                // 對 address + i 進行 md5 運算，得到一個長度為16的字節數組
                byte[] digest = md5(address + i);
                // 對 digest 部分字節進行4次 hash 運算，得到四個不同的 long 型正整數
                for (int h = 0; h < 4; h++) {
                    // h = 0 時，取 digest 中下標為 0 ~ 3 的4個字節進行位運算
                    // h = 1 時，取 digest 中下標為 4 ~ 7 的4個字節進行位運算
                    // h = 2, h = 3 時過程同上
                    long m = hash(digest, h);
                    // 將 hash 到 invoker 的映射關系存儲到 virtualInvokers 中，
                    // virtualInvokers 需要提供高效的查詢操作，因此選用 TreeMap 作為存儲結構
                    virtualInvokers.put(m, invoker);
                }
            }
        }
    }
}

ConsistentHashSelector 的構造方法執行了一系列的初始化邏輯，比如從配置中獲取虛擬節點數以及參與 hash 計算的參數下標，默認情況下只使用第一個參數進行 hash。需要特別說明的是，ConsistentHashLoadBalance 的負載均衡邏輯只受參數值影響，具有相同參數值的請求將會被分配給同一個服務提供者。ConsistentHashLoadBalance 不 關系權重，因此使用時需要注意一下。

在獲取虛擬節點數和參數下標配置后，接下來要做的事情是計算虛擬節點 hash 值，并將虛擬節點存儲到 TreeMap 中。到此，ConsistentHashSelector 初始化工作就完成了。接下來，我們來看看 select 方法的邏輯。

public Invoker<T> select(Invocation invocation) {
    // 將參數轉為 key
    String key = toKey(invocation.getArguments());
    // 對參數 key 進行 md5 運算
    byte[] digest = md5(key);
    // 取 digest 數組的前四個字節進行 hash 運算，再將 hash 值傳給 selectForKey 方法，
    // 尋找合適的 Invoker
    return selectForKey(hash(digest, 0));
}


private Invoker<T> selectForKey(long hash) {
    // 到 TreeMap 中查找第一個節點值大于或等于當前 hash 的 Invoker
    Map.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();
    // 如果 hash 大于 Invoker 在圓環上最大的位置，此時 entry = null，
    // 需要將 TreeMap 的頭節點賦值給 entry
    if (entry == null) {
        entry = virtualInvokers.firstEntry();
    }


    // 返回 Invoker
    return entry.getValue();
}

如上，選擇的過程相對比較簡單了。首先是對參數進行 md5 以及 hash 運算，得到一個 hash 值。然后再拿這個值到 TreeMap 中查找目標 Invoker 即可。

到此關于 ConsistentHashLoadBalance 就分析完了。

在閱讀 ConsistentHashLoadBalance 源碼之前，建議讀者先補充背景知識，不然看懂代碼邏輯會有很大難度。

五、應用場景

• DNS 負載均衡最早的負載均衡技術是通過 DNS 來實現的，在 DNS 中為多個地址配置同一個名字，因而查詢這個名字的客戶機將得到其中一個地址，從而使得不同的客戶訪問不同的服務器，達到負載均衡的目的。DNS 負載均衡是一種簡單而有效的方法，但是它不能區分服務器的差異，也不能反映服務器的當前運行狀態。
• 代理服務器負載均衡使用代理服務器，可以將請求轉發給內部的服務器，使用這種加速模式顯然可以提升靜態網頁的訪問速度。然而，也可以考慮這樣一種技術，使用代理服務器將請求均勻轉發給多臺服務器，從而達到負載均衡的目的。
• 地址轉換網關負載均衡支持負載均衡的地址轉換網關，可以將一個外部 IP 地址映射為多個內部 IP 地址，對每次 TCP 連接請求動態使用其中一個內部地址，達到負載均衡的目的。
• 協議內部支持負載均衡除了這三種負載均衡方式之外，有的協議內部支持與負載均衡相關的功能，例如 HTTP 協議中的重定向能力等，HTTP 運行于 TCP 連接的最高層。
• NAT 負載均衡 NAT（Network Address Translation 網絡地址轉換）簡單地說就是將一個 IP 地址轉換為另一個 IP 地址，一般用于未經注冊的內部地址與合法的、已獲注冊的 Internet IP 地址間進行轉換。適用于解決 Internet IP 地址緊張、不想讓網絡外部知道內部網絡結構等的場合下。
• 反向代理負載均衡普通代理方式是代理內部網絡用戶訪問 internet 上服務器的連接請求，客戶端必須指定代理服務器，并將本來要直接發送到 internet 上服務器的連接請求發送給代理服務器處理。反向代理（Reverse Proxy）方式是指以代理服務器來接受 internet 上的連接請求，然后將請求轉發給內部網絡上的服務器，并將從服務器上得到的結果返回給 internet 上請求連接的客戶端，此時代理服務器對外就表現為一個服務器。反向代理負載均衡技術是把將來自 internet 上的連接請求以反向代理的方式動態地轉發給內部網絡上的多臺服務器進行處理，從而達到負載均衡的目的。
• 混合型負載均衡在有些大型網絡，由于多個服務器群內硬件設備、各自的規模、提供的服務等的差異，可以考慮給每個服務器群采用最合適的負載均衡方式，然后又在這多個服務器群間再一次負載均衡或群集起來以一個整體向外界提供服務（即把這多個服務器群當做一個新的服務器群），從而達到最佳的性能。將這種方式稱之為混合型負載均衡。此種方式有時也用于單臺均衡設備的性能不能滿足大量連接請求的情況下。

作者：京東物流 喬杰

來源：京東云開發者社區