Dubbo——常見負載均衡算法分析

最近看Dubbo源碼時，看到了 LoadBanlance 相關算法，以此為問題出發點，總結下這方面相關的常見算法。（ 本文和Dubbo源碼並沒有太大的關係，只是屬於這個系列中遇到的知識總結 ）

負載均衡的目的是什麼？

討論負載均衡，那麼歸根結底其要解決的問題是什麼？當一臺服務器的承受能力達到上限時，那麼就需要多臺服務器來組成集群，提升應用整體的吞吐量，那麼這個時候就涉及到如何合理分配客戶端請求到集群中不同的機器，這個過程就叫做負載均衡，當然這也是負載均衡要解決的問題。

由於服務器之間的處理能力差異，因此每臺服務器需要有自己的權重比例，為了更好的描述後面所涉及到的算法，因此抽象出一個 Server 類，代表集群中的服務器。 LoadBalance 接口代表負載均衡算法。

public class Server { /** * 服務器地址 */ private String address; /** * 服務器權重 */ private Integer weight;}public interface LoadBalance { /** * 根據負載均衡算法選擇最合適的一個Server * @param servers 客戶端集合 * @return result */ Server select(List servers);}

權重隨機算法

單純的隨機算法通過偽隨機數來保證請求均勻的分佈到對應的Server上，但是其忽略了每一個服務器處理能力的差異，這樣就導致處理能力差的服務可能因為這種絕對的均衡策略而崩掉，改進策略就是根據權重佔比隨機。算法很簡單，就是一根數軸。然後利用偽隨機數產生點，看點落在了哪個區域從而選擇對應的 Server 。

@Overridepublic Server select(List servers) { ThreadLocalRandom localRandom = ThreadLocalRandom.current(); // 計算總比重 int totalWeight = 0; for (Server server : servers) { totalWeight += server.getWeight(); } // 按照權重選擇 int randomWeight = localRandom.nextInt(totalWeight); for (Server server : servers) { randomWeight -= server.getWeight(); if (randomWeight < 0) { return server; } } // default int length = servers.size(); return servers.get(localRandom.nextInt(length));}

權重輪詢算法

輪詢算法是指依次訪問可用服務器列表，其和隨機本質是一樣的處理，在無權重因素下，輪詢只是在選數軸上的點時採取自增對長度取餘方式。有權重因素下依然自增取餘，再看選取的點落在了哪個區域。這裡就不在過多描述。

對於 {a:5, b:1, c:1) 這三個服務實例，權重輪詢會得到 { a a a a a b c } 這樣的訪問順序，那麼當權重差過大時，對於服務器 a 來說依然存在集中訪問，為了解決這個問題，Nginx實現了一種平滑的輪詢算法，對於上述權重實例，Nginx的算法得出的訪問順序為 { a, a, b, a, c, a, a } ，這樣的分佈顯然比直接輪詢合理的多。

算法流程如下：

private static final ConcurrentMap ServerMap = new ConcurrentHashMap<>();@Overridepublic Server select(List servers) { Server best = null; int totalWeight = 0; for (Server server : servers) { AtomicInteger weightServer = ServerMap.get(server); if (null == weightServer) { weightServer = new AtomicInteger(0); ServerMap.putIfAbsent(server, weightServer); } int weight = server.getWeight(); // 加權 weightServer.addAndGet(weight); totalWeight += weight; // 根據權選擇 if (null == best || weightServer.get() > ServerMap.get(best).get()) { best = server; } } if (null == best) { throw new IllegalStateException("can't select client"); } // 降權 AtomicInteger bestWeightServer = ServerMap.get(best); bestWeightServer.set(totalWeight - bestWeightServer.get()); printSorts(servers); return best;}

整個實現非常巧妙，大概思想是每一個 Server 的權重都是動態可改變的，在遍歷過程中對每一個 Server 的權重做累加，然後選出權重最高的作為best，選中後再對best做降權，以此達到平滑。

以 {a:5, b:1, c:1) 作為輸入，選擇10次，其輸出結果為 { a a c a b a c a b a } ，下面是部分詳情，幫助理解加權與降權的流程。

server name: a weight: 5 current: 5server name: b weight: 2 current: 2server name: c weight: 3 current: 3Server(address=a, weight=5) // 第一次選擇server name: a weight: 5 current: 0server name: b weight: 2 current: 4server name: c weight: 3 current: 6Server(address=a, weight=5) // 第二次選擇server name: a weight: 5 current: 5server name: b weight: 2 current: 6server name: c weight: 3 current: 1Server(address=c, weight=3) // 第三次選擇server name: a weight: 5 current: 0server name: b weight: 2 current: 8server name: c weight: 3 current: 4Server(address=a, weight=5) // 第四次選擇server name: a weight: 5 current: 5server name: b weight: 2 current: 0server name: c weight: 3 current: 7Server(address=b, weight=2) // 第五次選擇

一致性Hash負載均衡算法

無論是隨機還是輪詢算法，對於一個客戶端的多次請求，每次落到的 Server 很大可能是不同的，如果這是一臺緩存服務器，那麼這就對緩存同步帶來了很大的挑戰，當系統繁忙時，主從延遲帶來的同步緩慢，可能就造成了同一客戶端兩次訪問得到不同的結果。解決方案是利用hash算法定位到對應的服務器。

1. 普通的Hash ：當客戶端請求到達是則使用 hash(client) % N,其中N是服務器數量，利用這個表達式計算出該客戶端對應的Server處理，因為客戶端總是同一個那麼對應的Server也總是同一個。該算法致命的問題是增減服務器，也就是 N +/- 1 ,該操作會導致取餘的結果變化，重新分配所有的Client，為了解決這個問題，一致性Hash算法誕生了。
2. 一致性Hash
   ：一致性Hash是把服務器分佈變成一個環形，每一個hash(clinet)的結果會在該環上順時針尋找第一個與其鄰的 Server 節點，具體可以參考 負載均衡–一致性hash算法 ，裡面的幾幅圖描述的很形象。

在 不考慮權重 的條件下，對於 {a:5, b:1, c:1) 三個Server，其組成的數軸首尾相連組成一個環。對於這個環，其規則如下：

hash(client)hash(client)hash(client)

因為對於 Client 來說其hash結果是固定的，因此能保證每一個Client總是能落到唯一確定的一個 Server 上。考慮到特殊情況，當 N +/- 1 ,也就是服務器增加或者減少，比如服務器 b 宕機了，那麼整個環只剩 a 和 c ，那麼原本落在 a , c 上的client依然會落到其上，只有原本落在b 節點上的client才會重新選擇Server。反之增加節點也是如此，儘可能的降低重新hash分配的client數量。

考慮權重的話，所期望的圖應該是按照一定比例設置。

a 因為權重是5所以其佔了圓的一半，這裡一種做法就是利用虛擬節點（給 a 創建5個hash值不同的副本），思路是把圓分成等分為10分（a，b，c權重之和為10），然後分配5個 a ，2個 b，3個 c ，這樣增大了hash到 a 區域的幾率，也就實現了權重。

在Java中，得益於 NavigableMap 數據結構的強大，其中 tailMap 方法可以直接得到某一個key之後的元素，對應於環中操作就是很容易獲取到某一點的相鄰點。

/** * 表示一致性Hash算法中的環 */ private static final ConcurrentSkipListMap ServerMap = new ConcurrentSkipListMap<>(); public Server select(List servers, String clientIdentify) { // 放入環中 for (Server server : servers) { Long hash = hash(server.getAddress()); if (!ServerMap.containsKey(hash)) { addServer(hash,server); } } // 計算client Long hash = hash(clientIdentify); // 定位到其後面的元素 ConcurrentNavigableMap tailMap = ServerMap.tailMap(hash); if (null == tailMap.firstEntry()) { tailMap = ServerMap.headMap(hash); } // 獲取到鄰近的Server return tailMap.firstEntry().getValue(); }

最小連接數加權算法

即每次選擇連接數最小的 Server ，當最小的 Server 有多個時則使用加權輪詢選擇其中一個，原理比較簡單，就算法就不過多的敘述了。

閱讀更多 菜根譚 的文章

關鍵字: Nginx 技術 常見