Nacos12# 隨機(jī)權(quán)重負(fù)載均衡算法
引言
Nacos在Client選擇節(jié)點(diǎn)時(shí)提供了一種基于權(quán)重的隨機(jī)算法，通過(guò)源碼分析掌握其實(shí)現(xiàn)原理，方便實(shí)戰(zhàn)中加以運(yùn)用。
下面以圖示的方式貫穿下隨機(jī)權(quán)重負(fù)載均衡算法的流程：
節(jié)點(diǎn)列表
假設(shè)注冊(cè)了5個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的權(quán)重如下。
組織遞增數(shù)組
目的在于形成weights數(shù)組，該數(shù)組元素取值[0~1]范圍，元素逐個(gè)遞增，計(jì)算過(guò)程如下圖示。另外注意非健康節(jié)點(diǎn)或者權(quán)重小于等于0的不會(huì)被選擇。
隨機(jī)算法
通過(guò)生成[0~1]范圍的隨機(jī)數(shù)，通過(guò)二分法查找遞增數(shù)組weights[]接近的index，再?gòu)淖?cè)節(jié)點(diǎn)列表中返回節(jié)點(diǎn)。
隨機(jī)權(quán)重負(fù)載均衡算法是在NacosNamingService#selectOneHealthyInstance提供，一起走查下。
@Override
public Instance selectOneHealthyInstance(String serviceName, String groupName, boolean subscribe)
throws NacosException {
return selectOneHealthyInstance(serviceName, groupName, new ArrayList<String>(), subscribe);
}
@Override
public Instance selectOneHealthyInstance(String serviceName, String groupName, List<String> clusters,
boolean subscribe) throws NacosException {
String clusterString = StringUtils.join(clusters, ",");
// 注解@1
if (subscribe) {
ServiceInfo serviceInfo = serviceInfoHolder.getServiceInfo(serviceName, groupName, clusterString);
if (null == serviceInfo) {
serviceInfo = clientProxy.subscribe(serviceName, groupName, clusterString);
}
return Balancer.RandomByWeight.selectHost(serviceInfo);
} else {
// 注解@2
ServiceInfo serviceInfo = clientProxy
.queryInstancesOfService(serviceName, groupName, clusterString, 0, false);
return Balancer.RandomByWeight.selectHost(serviceInfo);
}
}
注解@1 已訂閱「從緩存獲取注冊(cè)節(jié)點(diǎn)列表」，默認(rèn)subscribe為true。
注解@2 從 「從服務(wù)器獲取注冊(cè)節(jié)點(diǎn)列表」
protected static Instance getHostByRandomWeight(List<Instance> hosts) {
NAMING_LOGGER.debug("entry randomWithWeight");
if (hosts == null || hosts.size() == 0) {
NAMING_LOGGER.debug("hosts == null || hosts.size() == 0");
return null;
}
NAMING_LOGGER.debug("new Chooser");
List<Pair<Instance>> hostsWithWeight = new ArrayList<Pair<Instance>>();
for (Instance host : hosts) {
if (host.isHealthy()) { // 注解@3
hostsWithWeight.add(new Pair<Instance>(host, host.getWeight()));
}
}
NAMING_LOGGER.debug("for (Host host : hosts)");
Chooser<String, Instance> vipChooser = new Chooser<String, Instance>("www.taobao.com");
// 注解@4
vipChooser.refresh(hostsWithWeight);
NAMING_LOGGER.debug("vipChooser.refresh");
// 注解@5
return vipChooser.randomWithWeight();
}
注解@3 非健康節(jié)點(diǎn)不會(huì)被選中，組裝Pair的列表，包含健康節(jié)點(diǎn)的權(quán)重和Host信息
注解@4 刷新需要的數(shù)據(jù)，具體包括三部分：所有健康節(jié)點(diǎn)權(quán)重求和、計(jì)算每個(gè)健康節(jié)點(diǎn)權(quán)重占比、組織遞增數(shù)組。
public void refresh() {
Double originWeightSum = (double) 0;
// 注解@4.1
for (Pair<T> item : itemsWithWeight) {
double weight = item.weight();
// ignore item which weight is zero.see test_randomWithWeight_weight0 in ChooserTest
// weight小于等于 0的將會(huì)剔除
if (weight <= 0) {
continue;
}
items.add(item.item());
// 值如果無(wú)窮大
if (Double.isInfinite(weight)) {
weight = 10000.0D;
}
// 值如果為非數(shù)字值
if (Double.isNaN(weight)) {
weight = 1.0D;
}
// 累加權(quán)重總和
originWeightSum += weight;
}
// 注解@4.2
double[] exactWeights = new double[items.size()];
int index = 0;
for (Pair<T> item : itemsWithWeight) {
double singleWeight = item.weight();
//ignore item which weight is zero.see test_randomWithWeight_weight0 in ChooserTest
if (singleWeight <= 0) {
continue;
}
// 每個(gè)節(jié)點(diǎn)權(quán)重的占比
exactWeights[index++] = singleWeight / originWeightSum;
}
// 注解@4.3
weights = new double[items.size()];
double randomRange = 0D;
for (int i = 0; i < index; i++) {
weights[i] = randomRange + exactWeights[i];
randomRange += exactWeights[i];
}
double doublePrecisionDelta = 0.0001;
if (index == 0 || (Math.abs(weights[index - 1] - 1) < doublePrecisionDelta)) {
return;
}
throw new IllegalStateException(
"Cumulative Weight caculate wrong , the sum of probabilities does not equals 1.");
}
注解@4.1 所有健康節(jié)點(diǎn)權(quán)重求和originWeightSum
注解@4.2 計(jì)算每個(gè)健康節(jié)點(diǎn)權(quán)重占比exactWeights數(shù)組
注解@4.3 組織遞增數(shù)組weights，每個(gè)元素值為數(shù)組前面元素之和
以一個(gè)例子來(lái)表示這個(gè)過(guò)程，假設(shè)有5個(gè)節(jié)點(diǎn)：
1.2.3.4 100
1.2.3.5 100
1.2.3.6 100
1.2.3.7 80
1.2.3.8 60
步驟一 計(jì)算節(jié)點(diǎn)權(quán)重求和
originWeightSum = 100 + 100 + 100 + 80 + 60 = 440
步驟二 計(jì)算每個(gè)節(jié)點(diǎn)權(quán)重占比
exactWeights[0] = 0.2272
exactWeights[1] = 0.2272
exactWeights[2] = 0.2272
exactWeights[3] = 0.1818
exactWeights[4] = 0.1363
步驟三 組織遞增數(shù)組weights
weights[0] = 0.2272
weights[1] = 0.4544
weights[2] = 0.6816
weights[3] = 0.8634
weights[4] = 1
注解@5 隨機(jī)選取一個(gè)，邏輯如下：
public T randomWithWeight() {
Ref<T> ref = this.ref;
// 注解@5.1
double random = ThreadLocalRandom.current().nextDouble(0, 1);
// 注解@5.2
int index = Arrays.binarySearch(ref.weights, random);
// 注解@5.3
if (index < 0) {
index = -index - 1;
} else {
// 注解@5.4
return ref.items.get(index);
}
// 返回選中的元素
if (index >= 0 && index < ref.weights.length) {
if (random < ref.weights[index]) {
return ref.items.get(index);
}
}
/* This should never happen, but it ensures we will return a correct
* object in case there is some floating point inequality problem
* wrt the cumulative probabilities. */
return ref.items.get(ref.items.size() - 1);
}
注解@5.1 產(chǎn)生0到1區(qū)間的隨機(jī)數(shù)
注解@5.2 二分法查找數(shù)組中接近的值
注解@5.3 沒有命中返回插入數(shù)組理想索引值
注解@5.4 命中直接返回選中節(jié)點(diǎn)
小結(jié)： 一種基于權(quán)重的隨機(jī)算法的實(shí)現(xiàn)過(guò)程，扒開看也不復(fù)雜。