轉(zhuǎn)載 http://dubbo.apache.org/zh-cn/docs/source_code_guide/loadbalance.html
簡介
Dubbo 提供了4種負載均衡實現(xiàn)拣度，分別是基于權(quán)重隨機算法的 RandomLoadBalance、基于最少活躍調(diào)用數(shù)算法的LeastActiveLoadBalance扼倘、基于 hash 一致性的ConsistentHashLoadBalance，以及基于加權(quán)輪詢算法的 RoundRobinLoadBalance
源碼
在 Dubbo 中谭企，所有負載均衡實現(xiàn)類均繼承自 org.apache.dubbo.rpc.cluster.loadbalance.AbstractLoadBalance淹办，該類實現(xiàn)了 LoadBalance 接口，并封裝了一些公共的邏輯
核心的select方法
@Override
public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) {
if (CollectionUtils.isEmpty(invokers)) {
return null;
}
if (invokers.size() == 1) {
return invokers.get(0);
}
return doSelect(invokers, url, invocation);
}
protected abstract <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation);
具體的doSelect方法則由子類完成焚志。
在AbstractLoadBalance 中映凳，另一個核心的方法就是getWeight
/**
* Get the weight of the invoker's invocation which takes warmup time into account
* if the uptime is within the warmup time, the weight will be reduce proportionally
*
* @param invoker the invoker
* @param invocation the invocation of this invoker
* @return weight
*/
protected int getWeight(Invoker<?> invoker, Invocation invocation) {
int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), WEIGHT_KEY, DEFAULT_WEIGHT);
if (weight > 0) {
long timestamp = invoker.getUrl().getParameter(REMOTE_TIMESTAMP_KEY, 0L);
if (timestamp > 0L) {
int uptime = (int) (System.currentTimeMillis() - timestamp);
int warmup = invoker.getUrl().getParameter(WARMUP_KEY, DEFAULT_WARMUP);
if (uptime > 0 && uptime < warmup) {
weight = calculateWarmupWeight(uptime, warmup, weight);
}
}
}
return weight >= 0 ? weight : 0;
}
/**
* Calculate the weight according to the uptime proportion of warmup time
* the new weight will be within 1(inclusive) to weight(inclusive)
*
* @param uptime the uptime in milliseconds
* @param warmup the warmup time in milliseconds
* @param weight the weight of an invoker
* @return weight which takes warmup into account
*/
static int calculateWarmupWeight(int uptime, int warmup, int weight) {
int ww = (int) ((float) uptime / ((float) warmup / (float) weight));
return ww < 1 ? 1 : (ww > weight ? weight : ww);
}
RandomLoadBalance
RandomLoadBalance 是加權(quán)隨機算法的具體實現(xiàn)胆筒，它的算法思想很簡單。假設(shè)我們有一組服務(wù)器 servers = [A, B, C]，他們對應(yīng)的權(quán)重為 weights = [5, 3, 2]仆救，權(quán)重總和為10∈愫停現(xiàn)在把這些權(quán)重值平鋪在一維坐標值上，[0, 5) 區(qū)間屬于服務(wù)器 A彤蔽，[5, 8) 區(qū)間屬于服務(wù)器 B摧莽，[8, 10) 區(qū)間屬于服務(wù)器 C。接下來通過隨機數(shù)生成器生成一個范圍在 [0, 10) 之間的隨機數(shù)顿痪，然后計算這個隨機數(shù)會落到哪個區(qū)間上镊辕。比如數(shù)字3會落到服務(wù)器 A 對應(yīng)的區(qū)間上，此時返回服務(wù)器 A 即可蚁袭。權(quán)重越大的機器征懈，在坐標軸上對應(yīng)的區(qū)間范圍就越大，因此隨機數(shù)生成器生成的數(shù)字就會有更大的概率落到此區(qū)間內(nèi)揩悄。只要隨機數(shù)生成器產(chǎn)生的隨機數(shù)分布性很好卖哎，在經(jīng)過多次選擇后，每個服務(wù)器被選中的次數(shù)比例接近其權(quán)重比例虏束。比如棉饶，經(jīng)過一萬次選擇后厦章，服務(wù)器 A 被選中的次數(shù)大約為5000次镇匀，服務(wù)器 B 被選中的次數(shù)約為3000次，服務(wù)器 C 被選中的次數(shù)約為2000次袜啃。
LeastActiveLoadBalance
LeastActiveLoadBalance 翻譯過來是最小活躍數(shù)負載均衡汗侵。活躍調(diào)用數(shù)越小群发，表明該服務(wù)提供者效率越高晰韵，單位時間內(nèi)可處理更多的請求。此時應(yīng)優(yōu)先將請求分配給該服務(wù)提供者熟妓。在具體實現(xiàn)中雪猪，每個服務(wù)提供者對應(yīng)一個活躍數(shù) active。初始情況下起愈，所有服務(wù)提供者活躍數(shù)均為0只恨。每收到一個請求，活躍數(shù)加1抬虽，完成請求后則將活躍數(shù)減1官觅。在服務(wù)運行一段時間后，性能好的服務(wù)提供者處理請求的速度更快阐污，因此活躍數(shù)下降的也越快休涤，此時這樣的服務(wù)提供者能夠優(yōu)先獲取到新的服務(wù)請求、這就是最小活躍數(shù)負載均衡算法的基本思想笛辟。除了最小活躍數(shù)功氨，LeastActiveLoadBalance 在實現(xiàn)上還引入了權(quán)重值序苏。所以準確的來說，LeastActiveLoadBalance 是基于加權(quán)最小活躍數(shù)算法實現(xiàn)的疑故。舉個例子說明一下杠览，在一個服務(wù)提供者集群中，有兩個性能優(yōu)異的服務(wù)提供者纵势。某一時刻它們的活躍數(shù)相同踱阿，此時 Dubbo 會根據(jù)它們的權(quán)重去分配請求，權(quán)重越大钦铁，獲取到新請求的概率就越大软舌。如果兩個服務(wù)提供者權(quán)重相同，此時隨機選擇一個即可
ConsistentHashLoadBalance
一致性 hash 算法由麻省理工學院的 Karger 及其合作者于1997年提出的牛曹，算法提出之初是用于大規(guī)模緩存系統(tǒng)的負載均衡佛点。它的工作過程是這樣的，首先根據(jù) ip 或者其他的信息為緩存節(jié)點生成一個 hash黎比，并將這個 hash 投射到 [0, 232 - 1] 的圓環(huán)上超营。當有查詢或?qū)懭胝埱髸r，則為緩存項的 key 生成一個 hash 值阅虫。然后查找第一個大于或等于該 hash 值的緩存節(jié)點演闭，并到這個節(jié)點中查詢或?qū)懭刖彺骓棥Ｈ绻斍肮?jié)點掛了颓帝，則在下一次查詢或?qū)懭刖彺鏁r米碰，為緩存項查找另一個大于其 hash 值的緩存節(jié)點即可。大致效果如下圖所示购城，每個緩存節(jié)點在圓環(huán)上占據(jù)一個位置吕座。如果緩存項的 key 的 hash 值小于緩存節(jié)點 hash 值，則到該緩存節(jié)點中存儲或讀取緩存項瘪板。比如下面綠色點對應(yīng)的緩存項將會被存儲到 cache-2 節(jié)點中吴趴。由于 cache-3 掛了，原本應(yīng)該存到該節(jié)點中的緩存項最終會存儲到 cache-4 節(jié)點中侮攀。
下面來看看一致性 hash 在 Dubbo 中的應(yīng)用锣枝。我們把上圖的緩存節(jié)點替換成 Dubbo 的服務(wù)提供者，于是得到了下圖：
這里相同顏色的節(jié)點均屬于同一個服務(wù)提供者魏身，比如 Invoker1-1惊橱，Invoker1-2，……, Invoker1-160箭昵。這樣做的目的是通過引入虛擬節(jié)點税朴，讓 Invoker 在圓環(huán)上分散開來，避免數(shù)據(jù)傾斜問題。所謂數(shù)據(jù)傾斜是指正林，由于節(jié)點不夠分散泡一，導致大量請求落到了同一個節(jié)點上，而其他節(jié)點只會接收到了少量請求的情況觅廓。比如：
如上质礼，由于 Invoker-1 和 Invoker-2 在圓環(huán)上分布不均膳帕，導致系統(tǒng)中75%的請求都會落到 Invoker-1 上履腋，只有 25% 的請求會落到 Invoker-2 上企软。解決這個問題辦法是引入虛擬節(jié)點，通過虛擬節(jié)點均衡各個節(jié)點的請求量瞳脓。
ConsistentHashSelector 的構(gòu)造方法執(zhí)行了一系列的初始化邏輯塑娇，比如從配置中獲取虛擬節(jié)點數(shù)以及參與 hash 計算的參數(shù)下標，默認情況下只使用第一個參數(shù)進行 hash劫侧。需要特別說明的是埋酬，ConsistentHashLoadBalance 的負載均衡邏輯只受參數(shù)值影響，具有相同參數(shù)值的請求將會被分配給同一個服務(wù)提供者烧栋。ConsistentHashLoadBalance 不 關(guān)系權(quán)重写妥，因此使用時需要注意一下。
在獲取虛擬節(jié)點數(shù)和參數(shù)下標配置后审姓，接下來要做的事情是計算虛擬節(jié)點 hash 值珍特，并將虛擬節(jié)點存儲到 TreeMap 中。到此邑跪，ConsistentHashSelector 初始化工作就完成了
選擇的過程相對比較簡單了次坡。首先是對參數(shù)進行 md5 以及 hash 運算呼猪，得到一個 hash 值画畅。然后再拿這個值到 TreeMap 中查找目標 Invoker 即可。
RoundRobinLoadBalance
RoundRobinLoadBalance宋距。在詳細分析源碼前轴踱，我們先來了解一下什么是加權(quán)輪詢。這里從最簡單的輪詢開始講起谚赎，所謂輪詢是指將請求輪流分配給每臺服務(wù)器淫僻。舉個例子，我們有三臺服務(wù)器 A壶唤、B雳灵、C。我們將第一個請求分配給服務(wù)器 A闸盔，第二個請求分配給服務(wù)器 B悯辙，第三個請求分配給服務(wù)器 C，第四個請求再次分配給服務(wù)器 A。這個過程就叫做輪詢躲撰。輪詢是一種無狀態(tài)負載均衡算法针贬，實現(xiàn)簡單，適用于每臺服務(wù)器性能相近的場景下拢蛋。但現(xiàn)實情況下桦他，我們并不能保證每臺服務(wù)器性能均相近。如果我們將等量的請求分配給性能較差的服務(wù)器谆棱，這顯然是不合理的快压。因此，這個時候我們需要對輪詢過程進行加權(quán)垃瞧，以調(diào)控每臺服務(wù)器的負載嗓节。經(jīng)過加權(quán)后，每臺服務(wù)器能夠得到的請求數(shù)比例皆警，接近或等于他們的權(quán)重比拦宣。比如服務(wù)器 A、B信姓、C 權(quán)重比為 5:2:1鸵隧。那么在8次請求中，服務(wù)器 A 將收到其中的5次請求意推，服務(wù)器 B 會收到其中的2次請求豆瘫，服務(wù)器 C 則收到其中的1次請求。
參考
http://dubbo.apache.org/zh-cn/docs/source_code_guide/loadbalance.html
