负载均衡算法--Dubbo、Nginx
概述
比较经典的5种负载均衡算法：随机法、轮询法、最少连接数法、最快响应法、Hash化散列法（包括IP-Hash和参数值Hash一致性算法），另外还可以整合权重（配置权重值和JVM预热启动加权）
- 随机法：实现比较简单，也不需要记住状态位，每次随机选举，实现负载均衡的同时又避免了在选取节点时候的复杂运算
- 轮询法：实现更公平的负载均摊，但是是基于所有访问的服务器处理响应时间差不多的业务场景
- 最少连接数法：实现了更贴合实际场景的负载均摊，真正实现了根据服务器的实际处理能力来分摊请求，避免了慢堆积
- 通过统计每个Server的平均响应时间，然后选取最快的server，可以实现动态的调整负载的均摊。
- Hash化散列法：IP哈希可以解决集群的Session共享问题，Hash一致性解决的是在非常复杂的集群模式下，频繁发生节点的新增和删除的时候，如何实现影响最小的请求均摊。
- 权重值的引入，非常有意义的一个干预参数，因为实际的业务场景，每台服务器的物理环境所导致的服务性能各不相同。可以和随机法、轮训法、最少连接数法结合起来用，在和轮询法结合起来用时，又有平滑的负载均摊和不是很平滑的负载均摊。
总体来看，Dubbo提供的负载均衡的方法最多，但是负载的实现问题也多，性能也有待优化。Nginx次之，但是功能也很丰富、性能都较好。
Dubbo负载均衡算法 2.6.2版本
Dubbo提供了功能丰富（bug也多）的4种负载均衡算法，解决Consumer如何从Provider集群间选择哪个Provider提供服务的问题。
另外Dubbo在负载均衡时引入了自定义权重配置、JVM预热时间加权的规则进来。
四种算法：
-
Random LoadBalance：按照权重随机分配Provider，比如随机且权重Node1:Node2= 2:1，那么运行30次，大约有20次在Node1上，10次在Node2上。
-
RoundRobin LoadBalance：按照权重轮询分配。比如权重Node1:Node2= 20:10，那么运行30次：前20次里面轮询Node1和Node2大家各10次，第20次到30次，全部选择Node1。因为Dubbo默认是不会做公约数的处理，只有完成一个完整的20+10次运算，才能保证负载均衡的权重比例准确，如果Consumer只调用了20次，那么这里配置的权重的结果就是1:1了，该算法很不平滑。
-
LeastActive LoadBalance：节点处理越快分配更多，避免慢节点堆积，每次筛选Provider的时候，都只取Active值最小的节点，如果最小Active值的节点有多个，则按照权重随机选取。Provider每获取到一个任务Active值++，每结束一个任务Active值--
-
ConsistentHash LoadBalance：唯一忽略权重配置和JVM预热的算法。先把所有Provider都分配160个虚拟节点，通过Hash算法，全部分散到Hash圆上。每次Consumer调用时，会根据参数值做Hash换算，最后映射到Hash圆上，找到邻近的虚拟节点，最终获取到提供服务的Provider。但是Dubbo在实现的时候违背了Hash一致性的原则，每次Porvider发生改变的时候（新增或者剔除)，都会重新创建一个Hash圆，而不是在之前的Hash圆上新增或者剔除不合格的Porvider
AbstractLoadBalance抽象类
这个类提供了计算权重的方法，该方法里面会根据JVM启动时间做加权，并且直接处理了只有1个Provider或者没有Provider的情况，通过doSelect抽象方法，让4种负载均衡实现类去实现各自的规则。
- 获取服务节点的时候，首先调用的是AbstractLoadBalance的select()方法，该方法对一些只有1个Provider或者没有Provider做了处理，如果可用Porvider不止1个，配置的算法才有意义
public <T> Invoker<T> select(List<Invoker<T>> invokers, URL url, Invocation invocation) {
if (invokers == null || invokers.size() == 0)
return null;
if (invokers.size() == 1)
return invokers.get(0);
return doSelect(invokers, url, invocation);
}
- 因为jvm重启后有一段预热过程，要运行一段时间，它的性能才能达到最佳，所以Dubbo在做负载均衡计算Provider的权重时，引入了warmupTime的加权的算法。
在AbstractLoadBalance里面getWeight方法里面：weight= weight * （启动时间/逾期预热时间），warmup默认10分钟，Provider的权重会随着启动时间的增长，取的权重值增加，到了10分钟后，才是真正的配置的权重值
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);
}
- 备注：2.5.3版本代码里面有bug，在求当前Provider的运行时间参数的时候，实际上取的是当前Consumer的jvm启动时间，不过后来修复了
正确的取值参数为：REMOTE_TIMESTAMP_KEY。2.5.3版本的参数为 TIMESTAMP_KEY
long timestamp = invoker.getUrl().getParameter(Constants.REMOTE_TIMESTAMP_KEY, 0L);
RandomLoadBalance源码分析：
- 先求总权重，如果权重有不相等的，就根据总权重为上限生成随机值，然后看该随机值落在哪个Node上
- 如果权重未配置或者所有节点权重相同，就按照节点数做随机取值
public class RandomLoadBalance extends AbstractLoadBalance {
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
int length = invokers.size(); // 总个数
int totalWeight = 0; // 总权重
boolean sameWeight = true; // 权重是否都一样
for (int i = 0; i < length; i++) {
int weight = getWeight(invokers.get(i), invocation);
totalWeight += weight; // 累计总权重
if (sameWeight && i > 0 && weight != getWeight(invokers.get(i - 1), invocation)) {
sameWeight = false; // 计算所有权重是否一样
}
}
if (totalWeight > 0 && ! sameWeight) {
int offset = random.nextInt(totalWeight);
for (int i = 0; i < length; i++) {
offset -= getWeight(invokers.get(i), invocation);
if (offset < 0) {
return invokers.get(i);
}
}
}
return invokers.get(random.nextInt(length));
}
}
RoundRobinLoadBalance源码分析
核心思想
核心思想是先均摊，小权重的节点权重使用完后被淘汰，大权重节点之间均摊，逐个淘汰，最后是最大的一个节点独占。
比如Node1、Node2、Node3 ：1:5:10的权重，那么16次调用的结果就是
（Node1，Node2，Node3)
（Node2，Node3，Node2，Node3，Node2，Node3，Node2，Node3）
（node3，node3，node3，node3，node3)
缺点1：不够平滑，如果只调用了10次，那么权重类似于1:5:4
缺点2：没有类似公约数的处理，节点1:节点2设置1:10和 100万:1000万权重的耗时相差极大
缺点3：大权重值时循环次数太多，第1000万次的调用的时候，会循环1000*2次才能判断出哪个节点来处理请求，节点数越多，权重值设置越大越严重。
改进方案：
- 引入公约数，或者按照1-100进行折算
- 借鉴Nginx的平滑的权重加权轮询的算法
代码分析
- 通过一个全局的sequences根据key来存储调用的值。每个方法对应一个key，value来标记该方法是第几次被调用。
- 通过预热加权后的权重，计算出所有Provider的最大权重、最小权重、累计权重
- 2层for循环自减，第一层for循环的上线时maxWeight，第二层循环的次数是list<invokers>.size
private final ConcurrentMap<String, AtomicPositiveInteger> sequences = new ConcurrentHashMap<String, AtomicPositiveInteger>();
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
int length = invokers.size(); // Number of invokers
int maxWeight = 0; // The maximum weight
int minWeight = Integer.MAX_VALUE; // The minimum weight
final LinkedHashMap<Invoker<T>, IntegerWrapper> invokerToWeightMap = new LinkedHashMap<Invoker<T>, IntegerWrapper>();
int weightSum = 0;
for (int i = 0; i < length; i++) {
int weight = getWeight(invokers.get(i), invocation);
maxWeight = Math.max(maxWeight, weight); // Choose the maximum weight
minWeight = Math.min(minWeight, weight); // Choose the minimum weight
if (weight > 0) {
invokerToWeightMap.put(invokers.get(i), new IntegerWrapper(weight));
weightSum += weight;
}
}
AtomicPositiveInteger sequence = sequences.get(key);
if (sequence == null) {
sequences.putIfAbsent(key, new AtomicPositiveInteger());
sequence = sequences.get(key);
}
//计算当前方法是第几次发起的调用
int currentSequence = sequence.getAndIncrement();
//如果Providers之间的权重不相同，会按照权重来进行轮询Provider
if (maxWeight > 0 && minWeight < maxWeight) {
//关键的两层循环，调用次数会按照weightSum的余数来循环计算
int mod = currentSequence % weightSum;
//这里的上限是maxWeight，因为 里面会有invokerList.size()次的判断，maxWeight*size >sumWeight
for (int i = 0; i < maxWeight; i++) {
//不管该invoker的权重是否自减完了，仍然要取值判断
for (Map.Entry<Invoker<T>, IntegerWrapper> each : invokerToWeightMap.entrySet()) {
final Invoker<T> k = each.getKey();
final IntegerWrapper v = each.getValue();
if (mod == 0 && v.getValue() > 0) {
return k;
}
//只有当value<0的时候，该节点已经被淘汰，没有资格自减mod
if (v.getValue() > 0) {
v.decrement();
mod--;
}
}
}
}
// Round robin
return invokers.get(currentSequence % length);
}
LeastActiveLoadBalance
- 配置：需要设置Consumer的filter="activelimit"
<dubbo:reference id="demoService" interface="..." loadbalance="leastactive" filter="activelimit"/>
- 算法逻辑
每个Provider对象里面有active值，抽选节点的时候优先判断Active是否是最小的，再根据权重值最随机抽选节点，这样避免让调用堆积在速度相应慢的节点上面
- 如果最小active值的Provider只有1个，那么就调用这个Provider
- 如果最小active值的Provider有多个，则用一个数组存起来，在这个数组中的Provider按照权重值做随机抽选
- 如果大家的Active值都一样，且权重也都一样，就随机抽选
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
...
//遍历所有节点，获取几个指标
//用int[] leastIndexs 保存所有活跃值都最小且相同的Providers的下标
//totalWeight 只获取该数组的Providers的totalWeight,不是最小的Provider不统计
// boolean sameWeight 判断该数组中的Providers的权重是否都相同
for (int i = 0; i < length; i++) {
...
if (leastActive == -1 || active < leastActive) { // 发现更小的活跃数，重新开始
leastActive = active; // 记录最小活跃数
leastCount = 1; // 重新统计相同最小活跃数的个数
leastIndexs[0] = i; // 重新记录最小活跃数下标
totalWeight = weight; // 重新累计总权重
firstWeight = weight; // 记录第一个权重
sameWeight = true; // 还原权重相同标识
} else if (active == leastActive) { // 累计相同最小的活跃数
leastIndexs[leastCount ++] = i; // 累计相同最小活跃数下标
totalWeight += weight; // 累计总权重
// 判断所有权重是否一样
if (sameWeight && i > 0 && weight != firstWeight) {
sameWeight = false;
}
}
}
...
//如果最小活跃值数组不止一个且大家权重不相同
//然后按照权重做随机选取
if (! sameWeight && totalWeight > 0) {
// 如果权重不相同且权重大于0则按总权重数随机
int offsetWeight = random.nextInt(totalWeight);
// 并确定随机值落在哪个片断上
for (int i = 0; i < leastCount; i++) {
int leastIndex = leastIndexs[i];
offsetWeight -= getWeight(invokers.get(leastIndex), invocation);
if (offsetWeight <= 0)
return invokers.get(leastIndex);
}
}
// 权重相同或权重为0则均等随机
return invokers.get(leastIndexs[random.nextInt(leastCount)]);
}
- 活跃数统计ActiveLimitFilter
配置了Filter时，在开始调用方法时会beginCount，active++，方法调用结束时会active--
public Result invoke(Invoker<?> invoker, Invocation invocation) throws RpcException {
RpcStatus count = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName());
int active = count.getActive();
RpcStatus.beginCount(url, methodName);
Result result = invoker.invoke(invocation);
RpcStatus.endCount(url, methodName, System.currentTimeMillis() - begin, true);
return result;
}
private static void beginCount(RpcStatus status) {
status.active.incrementAndGet();
}
ConsistentHashLoadBalance
- 算法分析：
- 根据设置的参数和参数值的拼接，来通过Hash一致性算法，获取在圆上对应的Provider节点，默认配置160个虚拟节点，只取第一个参数的参数值进行散列
- 实现的效果是：类似优化粒度的随机取值，而且随机的好坏和散列的算法关联度很高。目前的API并没有支持动态的扩容和缩容，只是简单的初始化和选取节点。
- 该算法不参考权重值
- 配置
<dubbo:reference id="demoService" interface="com.mor.server.dubbo.service.DemoServer">
<dubbo:method name="sayHello" loadbalance="consistenthash"/>
</dubbo:reference>
- 源码分析
protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
String key = invokers.get(0).getUrl().getServiceKey() + "." + invocation.getMethodName();
ConsistentHashSelector<T> selector = (ConsistentHashSelector<T>) selectors.get(key);
return selector.select(invocation);
}
ConsistentHashSelector(List<Invoker<T>> invokers, String methodName, int identityHashCode) {
this.virtualInvokers = new TreeMap<Long, Invoker<T>>();
...
this.replicaNumber = url.getMethodParameter(methodName, "hash.nodes", 160);
String[] index = Constants.COMMA_SPLIT_PATTERN.split(url.getMethodParameter(methodName, "hash.arguments", "0"));
argumentIndex = new int[index.length];
//构建一个160份镜像的散列的invoker
for (Invoker<T> invoker : invokers) {
String address = invoker.getUrl().getAddress();
for (int i = 0; i < replicaNumber / 4; i++) {
byte[] digest = md5(address + i);
for (int h = 0; h < 4; h++) {
long m = hash(digest, h);
virtualInvokers.put(m, invoker);
}
}
}
哈希一致性算法
假如有2000张图片，图片名/图片路径 组成，有4台机器来存储，会进行图片进行CRUD操作。
- 如果采取随机法存储，那么每次get一张图片，最差需要遍历所有数据才能获取到对应的图片
- 哈希取余法，根据图片名称 散列成一个hashcode值，然后和4取余数，这样就可以大致均摊到4台服务器，而且每次get的时候，都只需要查找1个节点即可
- 哈希取余法的缺点：伸缩性不好，如果新增加一台机器，那么get图片就会出错，需要2000万条数据，全部重新排序，分配到5台节点。如果考虑缩减一个节点，也需要全部重新2000万数据重排列
- 哈希一致性算法：把各个节点按照serverId进行散列，让其尽可能的均匀的散布在一个最大值为 2的32次方的圆上，这样，这个圆上就有4个server节点，存储图片的时候，需要按照相同的算法，然后，分配到比自己值大的最近的一个节点。
- 哈希一致性的优点：新增和缩容的时候，只会影响到下一个节点，而不是全部节点要调整
-
新增一个节点的时候，比如之前节点在圆上的散落顺序是顺序散落，4台server求出来的hash值分别是 1、100、200、300，新增一台机器的E节点hash值是250，那么只需要把落在它的上一个节点，也就是D节点的所有数据（数据的key的区间是201-300）重新进行排列，然后该圆就仍然有效，不会影响到 A、B、C节点的数据。
image
- 如果要缩容，去除掉D节点，只需要取出300节点的所有数据，全部分配给A节点即可。
- 哈希一致性算法引入虚拟节点：可以降低分散的不均匀性，但是会提升容量调整时的复杂性。
- 加入虚拟数为2，之前的排列是 A B C D，现在是 A1 B1 A2 C1 C2 D1 B2 D2，如果新增或者删除A节点，那么也只会影响到 *虚拟数的节点，也就是 B1 和C1节点，而不会影响其他 B2 C2 D1 D2节点
- 虚拟数越大，容量变化时需要调整的数据就越多，但是虚拟数越大，数据分布的就越均匀
Nginx的负载均衡算法
结合第三方插件，可以实现高可用，剔除掉出问题的节点
Nginx目前有5种负载均衡配置：
-
round_robin，加权轮询，是默认的HTTP负载均衡算法，适用于知道机器的性能，且默认所有的请求对于服务器而言，处理的时间相差不大。比如我Server1 比Server2的配置要高一倍，我设置为2:1的权重，可以实现比较科学的负载。算法实现上，简单的轮询很简单，给每个Server依次编号，然后只要记录一个调用index，既可以实现轮询。
-
ip_hash，IP哈希，可保持会话
-
least_conn; 避免了慢堆积，会取连接数最小的server提供服务，可以避免有些请求耗时长，有些耗时端的情况。根据实际的连接数选择服务器。
-
fair，需要插件扩展该功能，根据后端服务器的响应时间来分配请求，响应时间短的优先分配，避免慢堆积。
-
权重配置：而且采用的是平滑的负载均衡算法，比如node1:node2:node3=1:2:5 --> node3，node3，node2，node3，node1，node3，node2，node3
平滑的轮询负载均衡算法（Smooth Weighted Round Robin)
例如server-a:server-b:server-c=4：2:1。选取7次的话，选取的结果 server-a,server-b,server-a,server-c,server-a,server-b,server-a。
每次都筛选当前权重值最大的节点，然后对该节点权重值-totalWeight，然后所有的节点都grow一下，都用当前权重+init权重
初始化的时候大家的权重（4,2,1），Server-a的权重最大，选他干活，干完之后，a节点的权重-最大权重，a的当前权重为-3，然后所有节点的权重，都按照自己的初始权重自增一次（-3+4,2+2,1+1），也就是（1,4,2），开始第二轮选取
image
java代码实现
class Server{
int initWeigth;
int printCount=0;
int weigth;
String name;
}
public List<Server> init(){
Server server1=new Server(4,4,"server-a");
totalWeight+=4;
Server server2=new Server(2,2,"server-b");
totalWeight+=2;
Server server3=new Server(1,1,"server-c");
totalWeight+=1;
List<Server> list=new ArrayList();
list.add(server1);
list.add(server2);
list.add(server3);
return list;
}
public Server chooseServer(List<Server> list){
Server choosenServer=list.get(0);
for(int i=1;i<list.size();i++){
Server server=list.get(i);
if(choosenServer.getWeigth()<server.getWeigth()){
choosenServer=server;
}
}
choosenServer.setWeigth(choosenServer.getWeigth()-totalWeight);
return choosenServer;
}
public void grow(List<Server> list){
for(int i=0;i<list.size();i++){
Server server=list.get(i);
server.setWeigth(server.getWeigth()+server.getInitWeigth());
}
}
public static void main(String[] args) {
Test smooth=new Test();
List<Server> list=smooth.init();
for(int i=0;i<7;i++){
Server server= smooth.chooseServer(list);
System.out.println("server-"+server.getName()+" is working");
server.setPrintCount(server.getPrintCount()+1);
smooth.grow(list);
}
System.out.println("--------------------");
for(int i=0;i<list.size();i++){
Server server=list.get(i);
System.out.println(server.getName()+" initWeight-"+server.getInitWeigth()+" totalPrint-"+server.getPrintCount()+"times");
}
}
参考资料
https://blog.csdn.net/revivedsun/article/category/6435629
github中文官网
https://dubbo.gitbooks.io/dubbo-user-book/content/preface/background.html
哈希一致性算法
https://www.cnblogs.com/lpfuture/p/5796398.html
https://blog.csdn.net/bntX2jSQfEHy7/article/details/79549368
