Random LoadBalance
随机算法，顾名思义，当有大量请求时，根据概率学可以知道每一台服务器分配的流量基本会均等。
广义版本是加权随机算法，需要思考的问题是，如何让请求根据权重随机分配到多个服务器上？
当不考虑权重的时候，如果有n个服务器，可以用randomInt(n)的方式生成随机数，随机数即对应相应server的ID。
当需要考虑权重的时候，可以按将权重的和当成虚拟服务器的数量，比如有三个服务器a，b，c，权重分别为(1,2,3)。可以认为有6台虚拟服务器在提供服务，分别是(a,b1,b2,c1,c2,c3),然后生成随机数randomInt(6),并按此数字选择服务器。选到虚拟服务器c1,c2,c3时实际上都会将请求分配到c服务器。
Dubbo实现的是加权随机算法，并将这种算法设置为默认采取的负载均衡策略。
RoundRobin LoadBalance
轮转法，服务器排成一个圈，顺着往下一个个点，点到谁谁服务。一圈转完再来一圈，稳定的公平分配。
轮转法也有加权版本，加权的目的是将请求按权重分配到每个服务器中，比如我们有服务器对应的权重a(1), b(2), c(3);那么总权重是6，我们可以简单的生成序列(a,b,b,c,c,c)(a,b,b,c,c,c)...，这样每有6个请求就会1个请求到a，2个请求到b，三个请求到c，从而实现了请求按权重分配。
这个序列的缺陷在于有连续的请求压在一台服务器，我们更希望序列是类似(c,a,b,c,b,c)这样交叉的序列。6个请求中仍然有一个到a，两个到b，三个到c，但分布更为均匀。
如何实现这样更为均匀的序列呢？如果暴力解这个问题，可以将序列(a,b,b,c,c,c)人工随机打乱后存储在调度服务器中，这样服务器就会按指定的序列调度。这种方式的问题在于需要调度服务器存储一个可能是非常巨大的序列。
暴力解通常采取数学的方式来优化。RoundRobin也需要需要寻找一种数学运算，它能够生成一个均匀的序列，并且不需要调度服务器维护过多的状态。
这里介绍一种轮转序列生成的方式，背后的数学原理和验证不做深究。
smooth weighted round-robin balancing
平滑加权轮转均衡，nginx中使用的算法。我们用peer表示负载服务器，调度服务器需要为每个peer维护三个变量:权重，有效权重及当前权重
peer(weight, effective_weight, current_weight)
weight及配置中指定的服务器权重，effective_weight初始值是weight，为了实现动态调整，effective_weight会由于出现调用错误时减小，调用成功时增加，从而可以实现权重动态调整。当前权重初始值0，此值用于实现我们需要生成的序列。
具体算法如下
public class LoadBalanceTest {
public static class Peer {
String name;
int weight;
int effectiveWeight;
int currentWeight;
Peer(String name, int weight) {
this.name = name;
this.weight = weight;
this.effectiveWeight = weight;
this.currentWeight = 0;
}
@Override
public String toString() {
return "[" + this.weight + "," + this.effectiveWeight + ","
+ this.currentWeight + "]";
}
}
@Test
public void testRoundRobin() {
List<Peer> peers = new ArrayList<>();
peers.add(new Peer("a", 1));
peers.add(new Peer("b", 2));
peers.add(new Peer("c", 3));
int n_REQUESTS = 12;
for (int i = 0; i < n_REQUESTS; i++) {
int total = 0;
int max = -1;
int index = 0;
for (int j = 0; j < peers.size(); j++) {
Peer peer = peers.get(j);
peer.currentWeight += peer.effectiveWeight;
total += peer.effectiveWeight;
if (peer.currentWeight > max) {
max = peer.currentWeight;
index = j;
}
}
peers.get(index).currentWeight -= total;
System.out.print("select: " + peers.get(index).name + " ");
System.out.println("state: " + peers);
}
}
}
输出结果为：
select: c state: [1,1,1] [2,2,2] [3,3,-3]
select: b state: [1,1,2] [2,2,-2] [3,3,0]
select: a state: [1,1,-3] [2,2,0] [3,3,3]
select: c state: [1,1,-2] [2,2,2] [3,3,0]
select: b state: [1,1,-1] [2,2,-2] [3,3,3]
select: c state: [1,1,0] [2,2,0] [3,3,0]
-----------------------------------------------
select: c state: [1,1,1] [2,2,2] [3,3,-3]
select: b state: [1,1,2] [2,2,-2] [3,3,0]
select: a state: [1,1,-3] [2,2,0] [3,3,3]
select: c state: [1,1,-2] [2,2,2] [3,3,0]
select: b state: [1,1,-1] [2,2,-2] [3,3,3]
select: c state: [1,1,0] [2,2,0] [3,3,0]
LeastActive LoadBalance
前面两种负载均衡算法只为服务器分配了固定了权重，而没有考虑服务器当前的处理状态。比如当一个服务器收到一个耗时的请求导致服务器处于高负载状态，而之前的两种负载均衡算法对此并无感知。我们希望提供一种算法能考虑到服务器当前的状态来分配请求。
LeastActive LoadBalance根据服务器的活跃数来分配请求，使得慢的服务提供者收到更少的请求。从而让请求能根据服务器的当前状态来动态分配。
活跃数可以理解成服务器当前正在处理的请求的个数。比如我们有a,b两台服务器，a正在处理3个请求，b正在处理2个请求。那么a的活跃数是3，b的活跃数是2。如果再来一个请求，我们需要选择的服务器是b。
这里仍然可以加入考虑服务器a，b的权重。当有多个服务器的活跃数相同时，这几个服务器中的负载均衡可以退化成使用加权随机算法。
ConsistentHash LoadBalance
最后谈到鼎鼎大名的一致性哈希算法。
前面提到的三种算法都只考虑了服务器的状态和特性(权重)，而没有考虑到请求本身的特性。比如有一个根据ID加载数据的服务，服务提供者会在请求时将相应数据在服务器上缓存一段时间。在这种应用场景中，我们希望将相同ID的请求分配到同一台服务器，从而实现服务加速。前面的三种均衡算法都无法满足这种需求。
要将请求根据ID定向到某台服务器，自然就需要应用到哈希。一个简单的思路是按哈希值取模，比如我们有3台服务器，那么按hash(ID)%3的方式，就能将请求分配到三台服务器。从而按请求ID来分发到服务器。
这样简单的哈希算法有什么问题呢？我们需要考虑到现实环境是残酷的，计算机运行环境会因为网络分区无法访问，服务也有可能会crash。使用这种简单的算法，如果三台服务器中如果有一台服务器crash掉，所有对应的ID的请求都无法获得服务，这显然不是我们希望的结果。为了实现服务的可用性，我们希望在一台服务器crash掉的时候，自动的将对应的ID的请求分配到其他的可用服务器上。
在hash(ID)%3这种分发方式中，我们采用了模除的方法决定了哈希值是如何对应到服务器上的。我们可以采用其他的对应方式。哈希值的区间是0~90,我们可以给定如下的对应关系
0~30 -> a
31~60 ->b
61~90 -> c
这种对应方式就可以完成我们采用hash(ID)%3实现的分发功能，需要增加的代价是每台服务器需要存储两个值对应其hash空间，这种代价是可以接受的。
在这种分发模式下，如何应对某台服务器不可用呢？一个简单的方案是如果一个服务器cash，将对应于它的请求转移到下一台服务器中。比如当a服务器crash掉时，分发的对应关系转变成
0~60 -> b
61~90 -> c
如果是c服务器crash，分发的对应关系转变成
61~90, 0~30 -> a
31~60 -> b
即我们将a，b，c看成了一个环形的关系，每当一个服务器crash时，将对应其的请求转移到下一台服务器中，从而实现服务的可用性。
这里有一个显然的违反直觉的缺陷，如果a服务器crash掉,我们更希望采取的方式是将原来对应于a的请求平均分派到b，c上，而不是将全部压力转移到b服务器。
如何实现呢？回到Random balance算法中，我们采用了虚拟服务器的思路，将一台服务器可以看成多台服务器。在这里，是不是可以采用同样的思路呢，我们采取如下的分派策略
0~15 -> a1
15~30 - a2
31~60 ->b
61~90 -> c
此时如果a服务器crash请求仍然会全部转移到b服务器。但如果调整一下顺序
0~15 -> a1
16~45 -> b
46~60 -> a2
61~90 -> c
这中分派模式下，如果a服务器crash压力就会平均转移到b，c上，从而满足了我们的需求。
这就是一致性哈希算法。
