Dubbo負載平衡策略之 一致性哈希

本文主要講解了一致性雜湊演算法的原理以及其存在的資料傾斜的問題，然後引出解決資料傾斜問題的方法，最後分析一致性雜湊演算法在 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除以4的餘數為0。這時，請求就被 0 號伺服器接收了。

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

所以，當伺服器數量增加或減少時，一定會涉及大量資料遷移的問題。

這種雜湊演算法的優點在於其簡單易用性，因此大多數分庫分錶規則都採用了它。一般是提前根據資料量，預先估算好分區數。

此技術的不足在於，一旦網路中節點數量發生擴增或收縮，就需要重新計算節點的映射關係，導致資料需要被遷移。所以擴容時通常會採用翻倍擴容，避免資料映射全部被打亂，導致全量遷移的情況，這樣只會發生 50% 的資料遷移。

三、一致性雜湊演算法

** 一致性hash 演算法由麻省理工學院的Karger 及其合作者於1997 年提出的，演算法提出之初是用於大規模快取系統的負載平衡。 ** 它的工作過程是這樣的，首先根據 ip 或其他的資訊為快取節點產生一個 hash，並將這個 hash 投射到 [0, 232 - 1] 的圓環上。每當有查詢或寫入請求時，就會為快取項目的鍵產生一個雜湊值。接著，需要尋找快取節點中第一個hash值大於或等於給定值的節點，並在該節點中進行快取查詢或寫入操作。噹噹前節點失效時，下次快取查詢或寫入時，可以找另一個哈希值大於目前快取項目的快取節點。大致效果如下圖所示，每個快取節點在圓環上佔據一個位置。當快取項目的 key 的雜湊值小於快取節點的雜湊值時，會將快取項目儲存或從快取節點讀取。下面這個綠色標記所對應的快取項目將會儲存至節點 cache-2。快取項目原本應該儲存到 cache-3 節點中，但由於該節點宕機，最終儲存到了 cache-4 節點中。

圖4 一致性雜湊演算法

在一致性雜湊演算法中，不管是增加節點，或是宕機節點，受影響的區間只是增加或當機伺服器在哈希環空間中，逆時針方向遇到的第一台伺服器之間的區間，其它區間不會受到影響。

但是一致性雜湊也是有問題的：

圖5 資料傾斜

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

那要如何解決資料傾斜的問題呢？

加入虛擬節點。

首先一個伺服器根據需要可以有多個虛擬節點。假設一台伺服器有 n 個虛擬節點。在雜湊計算中，可以採用 IP 位址、連接埠號碼和編號的組合來計算雜湊值。其中的編號就是 0 到 n 的數字。這 n 個節點都指向同一台機器，因為它們共用相同的 IP 位址和連接埠號碼。

圖 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<?>>();@Overrideprotected <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 原始的 hashcodeint identityHashCode = System.identityHashCode(invokers);ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);// 如果 invokers 是一个新的 List 对象，意味着服务提供者数量发生了变化，可能新增也可能减少了。// 此时 selector.identityHashCode != identityHashCode 条件成立if (selector == null || selector.identityHashCode != identityHashCode) {// 创建新的 ConsistentHashSelectorselectors.put(key, new ConsistentHashSelector<T>(invokers, methodName, identityHashCode));selector = (ConsistentHashSelector<T>) selectors.get(key);}// 调用 ConsistentHashSelector 的 select 方法选择 Invokerreturn 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();// 获取虚拟节点数，默认为160this.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) {// 将参数转为 keyString key = toKey(invocation.getArguments());// 对参数 key 进行 md5 运算byte[] digest = md5(key);// 取 digest 数组的前四个字节进行 hash 运算，再将 hash 值传给 selectForKey 方法，// 寻找合适的 Invokerreturn selectForKey(hash(digest, 0));}private Invoker<T> selectForKey(long hash) {// 到 TreeMap 中查找第一个节点值大于或等于当前 hash 的 InvokerMap.Entry<Long, Invoker<T>> entry = virtualInvokers.tailMap(hash, true).firstEntry();// 如果 hash 大于 Invoker 在圆环上最大的位置，此时 entry = null，// 需要将 TreeMap 的头节点赋值给 entryif (entry == null) {entry = virtualInvokers.firstEntry();}// 返回 Invokerreturn entry.getValue();}

如上，选择的过程相对比较简单了。首先，需要对参数进行 md5 和 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 上的连接请求以反向代理的方式动态地转发给内部网络上的多台服务器进行处理，从而达到负载均衡的目的。
• 混合型负载均衡在有些大型网络，由于多个服务器群内硬件设备、各自的规模、提供的服务等的差异，可以考虑给每个服务器群采用最合适的负载均衡方式，然后又在这多个服务器群间再一次负载均衡或群集起来以一个整体向外界提供服务（即把这多个服务器群当做一个新的服务器群），从而达到最佳的性能。将这种方式称之为混合型负载均衡。此种方式有时也用于单台均衡设备的性能不能满足大量连接请求的情况下。

作者：京东物流 乔杰

来源：京东云开发者社区

以上是Dubbo負載平衡策略之 一致性哈希的詳細內容。更多資訊請關注PHP中文網其他相關文章！