负载均衡算法

常见的负载均衡算法

1. 轮询法
   1. 将请求按顺序轮流地分配到后端服务器上，它均衡地对待后端的每一台服务器，而不关心服务器实际的连接数和当前的系统负载。
2. 加权轮询法
   1. 不同的后端服务器可能机器的配置和当前系统的负载并不相同，因此它们的抗压能力也不相同，给高配置的及其配置更高的权重，低配置的降低权重，达到一个均衡。
3. 随机法
   1. 根据后端服务器列表大小值来随机选取其中的一台服务器进行访问。随着客户端访问的次数越来越多，实际效果也越来越接近于平均分配调用量到后端的每一台服务器。
4. 加权随机法
   1. 加权随机法也跟及后端及其的配置，系统的负载分配不同的权重。不同的是，它是按照权重随机请求后端服务器，而非顺序。
5. 源地址哈希法
   1. 源地址哈希的思想是根据获取客户端的IP地址，通过哈希函数计算得到的一个述职
6. 最小连接数法
   1. 最小连接数算法比较灵活和只能，由于后端服务器的配置不尽相同，对于请求的处理有快又慢，它是根据后端服务器当前的连接情况，动态的选取其中当前积压连接数最少的一台服务器来处理当前的请求，尽可能地提高后端服务地利用率，将负责合理地分流到每一台服务器。

Nginx的5种负载均衡算法

1. 轮询法(Round robin)(默认)

每个请求按时间顺序逐一分配到不同的后端服务器，如果后端服务器down掉，能自动剔除

2. 加权轮询法

指定轮询几率，weight和访问比率称正比，用于后端服务器性能不均的情况

例如:

upstream bakend {  
  server 192.168.0.14 weight=8;  
  server 192.168.0.15 weight=10;//权值越高被分配到的比例越大
 }

3.源地址哈希法

每个请求按访问ip 的hash结果分配，这样每个方可固定访问一个后端服务器，可以解决session 的问题

upstream bakend {  
  ip_hash; 
  server 192.168.0.14:88;  
  server 192.168.0.15:80;  
}

4. fair(第三方)

按后端服务器的响应时间来分配请求，响应时间短的优先分配

upstream backend {  
  server server1;  
  server server2;  
  fair;  
}

5. url_hash

按访问url的hash结果来分配请求，使每个url定向走到同一个后端服务器。后端服务器为缓存时比较有效

upstream backend {  
  server squid1:3128;  
  server squid2:3128;  
  hash $request_uri;  
  hash_method crc32;
}
tips:
upstream bakend{#定义负载均衡设备的Ip及设备状态  
  ip_hash;  
  server 127.0.0.1:9090 down;  
  server 127.0.0.1:8080 weight=2;  
  server 127.0.0.1:6060;  
  server 127.0.0.1:7070 backup;  
}

• 表示当前单位的server不参与
• weight默认为1，weight越大，负载的权重就越大
• max_fails 允许请求失败的次数，默认为1，当超过最大次数返回proxy_next_upstream模块定义的错误
• fail_timeout:max_fails 次失败后，暂停 的时间
• backup:其他所有的非backup 机器down或者忙的时候，请求backup机器。所以这台机器压力会最轻。

nginx支持同时设置多组的非负载均衡，用来给不用的server来使用

• client_body_in_file_only 设置为on ，可以将client post过来的数据记录到文件用来debug
• client_body_temp_path：设置记录文件的目录，可以设置最多3层记录
• location：对URL进行匹配，可以进行重定向或者进行新的代理，负载均衡。

Dubbo的负载均衡策略

Dubbo提供了4种负载均衡的实现，分别是基于权重随机算法的RandomLoadBalance、基于最少活跃调用算法的LeastActiveLoadBalance、基于hash一致性的ConsistenHashLoadBalance，以及基于加权轮询算法的RoundRobinLoadBalance。

1. RadndomLoadBalance

RandomLoadBalance 是加权随机算法的具体实现，它的算法思想很简单。假设我们有一组服务器 servers = [A, B, C]，他们对应的权重为 weights = [5, 3, 2]，权重总和为10。现在把这些权重值平铺在一维坐标值上，[0, 5) 区间属于服务器 A，[5, 8) 区间属于服务器 B，[8, 10) 区间属于服务器 C。接下来通过随机数生成器生成一个范围在 [0, 10) 之间的随机数，然后计算这个随机数会落到哪个区间上。比如数字3会落到服务器 A 对应的区间上，此时返回服务器 A 即可。权重越大的机器，在坐标轴上对应的区间范围就越大，因此随机数生成器生成的数字就会有更大的概率落到此区间内。只要随机数生成器产生的随机数分布性很好，在经过多次选择后，每个服务器被选中的次数比例接近其权重比例。比如，经过一万次选择后，服务器 A 被选中的次数大约为5000次，服务器 B 被选中的次数约为3000次，服务器 C 被选中的次数约为2000次。

2. LeastActiveLoadBalance

LeastActiveLoadBalance 翻译过来是最小活跃数负载均衡。活跃调用数越小，表明该服务提供者效率越高，单位时间内可处理更多的请求。此时应优先将请求分配给该服务提供者。在具体实现中，每个服务提供者对应一个活跃数 active。初始情况下，所有服务提供者活跃数均为0。每收到一个请求，活跃数加1，完成请求后则将活跃数减1。在服务运行一段时间后，性能好的服务提供者处理请求的速度更快，因此活跃数下降的也越快，此时这样的服务提供者能够优先获取到新的服务请求、这就是最小活跃数负载均衡算法的基本思想。除了最小活跃数，LeastActiveLoadBalance 在实现上还引入了权重值。所以准确的来说，LeastActiveLoadBalance 是基于加权最小活跃数算法实现的。举个例子说明一下，在一个服务提供者集群中，有两个性能优异的服务提供者。某一时刻它们的活跃数相同，此时 Dubbo 会根据它们的权重去分配请求，权重越大，获取到新请求的概率就越大。如果两个服务提供者权重相同，此时随机选择一个即可。

3. ConsistentHashLoadBalance

一致性 hash 算法由麻省理工学院的 Karger 及其合作者于1997年提出的，算法提出之初是用于大规模缓存系统的负载均衡。它的工作过程是这样的，首先根据 ip 或者其他的信息为缓存节点生成一个 hash，并将这个 hash 投射到 [0, 232 - 1] 的圆环上。当有查询或写入请求时，则为缓存项的 key 生成一个 hash 值。然后查找第一个大于或等于该 hash 值的缓存节点，并到这个节点中查询或写入缓存项。如果当前节点挂了，则在下一次查询或写入缓存时，为缓存项查找另一个大于其 hash 值的缓存节点即可。大致效果如下图所示，每个缓存节点在圆环上占据一个位置。如果缓存项的 key 的 hash 值小于缓存节点 hash 值，则到该缓存节点中存储或读取缓存项。比如下面绿色点对应的缓存项将会被存储到 cache-2 节点中。由于 cache-3 挂了，原本应该存到该节点中的缓存项最终会存储到 cache-4 节点中。

4. RoundRobinLoadBalance

我们来看一下 Dubbo 中加权轮询负载均衡的实现 RoundRobinLoadBalance。在详细分析源码前，我们先来了解一下什么是加权轮询。这里从最简单的轮询开始讲起，所谓轮询是指将请求轮流分配给每台服务器。举个例子，我们有三台服务器 A、B、C。我们将第一个请求分配给服务器 A，第二个请求分配给服务器 B，第三个请求分配给服务器 C，第四个请求再次分配给服务器 A。这个过程就叫做轮询。轮询是一种无状态负载均衡算法，实现简单，适用于每台服务器性能相近的场景下。但现实情况下，我们并不能保证每台服务器性能均相近。如果我们将等量的请求分配给性能较差的服务器，这显然是不合理的。因此，这个时候我们需要对轮询过程进行加权，以调控每台服务器的负载。经过加权后，每台服务器能够得到的请求数比例，接近或等于他们的权重比。比如服务器 A、B、C 权重比为 5:2:1。那么在8次请求中，服务器 A 将收到其中的5次请求，服务器 B 会收到其中的2次请求，服务器 C 则收到其中的1次请求。