内容简介:LB是现代高并发应用必然的需求,下面介绍一下Envoy中使用的LB算法。fromROUND_ROBIN是使用最为广泛的LB算法,轮询。
LB是现代高并发应用必然的需求,下面介绍一下Envoy中使用的LB算法。
from https://github.com/envoyproxy/envoy/blob/stable/v1.7.1/api/envoy/api/v2/cds.proto#L119
enum LbPolicy { ROUND_ROBIN = 0; LEAST_REQUEST = 1; RING_HASH = 2; RANDOM = 3; ORIGINAL_DST_LB = 4; MAGLEV = 5; }
ROUND_ROBIN
ROUND_ROBIN是使用最为广泛的LB算法,轮询。
举个例子:
1,2,3,4,5,6,六个请求依次访问有两个后端的LB,那么依ROUND_ROBIN算法,
服务器A服务1,3,5
服务器B服务2,4,6
Envoy的ROUND_ROBIN实际上是加权的。
由于服务后端的处理能力不同。假如服务器A能力比较强,我们分配了Weight=2;B的服务能力一般,我们分配了Weight=1,那么依照Weighted Round-Robin
服务器A服务1,2,4,5
服务器B服务3,6
LEAST_REQUEST
LEAST_REQUEST的意思是把请求送给当前活跃请求最少的服务器。
因为不同的请求需要耗费的资源实际上也是不一样的,我们假设2,4,6请求都特别耗费资源,1,3,5请求都很简单,那么把2,4,6都分配给服务器B就不甚合理。
1,2两个请求来了
服务器A服务1
服务器B服务2
1很快结束了,2还卡单
请求3来了,由于B现在有1个active req,A没有,所以分配给A
请求3也很快处理完
请求4来了,由于B现在有1个active req,A没有,所以分配给A
两个都在卡单。
请求5和6来了,分别分配给A,B。
最终,所有请求解决。
综上
服务器A服务1,3,4,5
服务器B服务2,6
RING_HASH
环形哈希是最基本的一致性哈希算法
需要设置hash key
来了一个新的请求,需要得到下游的时候,需要对Lookup Table进行二分查找。
当Lookup Table的大小为N的时候,需要Log(N)的查找时间复杂度。
N太大,每次查找时间太长;
N太小,环形哈希的均匀性又不够。
这个地方需要Trade-off,或者可以选用Maglev算法。
RANDOM
纯随机
一般效果还不错。
ORIGINAL_DST_LB
原始目的地负载均衡
upstream的主机基于downstream的连接元数据。这个是envoy特定的,不详细讲了。
MAGLEV
一种特殊的一致性哈希算法,效率比环形哈希要高一些,增删节点的影响一般更小。
需要设置hash key
首先对每一个后端节点产生一个permutation;
然后用一种特殊的walk算法,得到一个Lookup Table。
新的请求到来的时候,只需要直接查表即可,时间复杂度为O(1)。
walk算法保证哈希的概率是基本均匀的。
Extra: healthy_panic_threshold
Envoy中有一个监控恐慌阈值的设置,这个设置很有意思,所以在这里额外讲一下。
负载均衡一般是根据集群中主机的健康情况灵活变动的。当某台主机跪了,LB算法将会把它从候选列表中踢出去,这也是很合理的。
但是我们假设这么一种情况,某一时间,所有服务主机的负载情况是最大负载的80%,(负载800;最大处理能力1000)
因为某种原因,导致20.0%的机器彻底崩溃。(负载800;最大处理能力800)
LB策略忽略20%的机器,导致剩下的80%的机器都在最大处理负载上运行;
又来了一个网络波动,造成所有的服务器一个接一个崩溃,整个集群雪崩。
每拉起一台新的机器,LB策略立刻把所有的流量打到这么一台机器上,导致它再次崩溃。
如果有一个恐慌阈值,譬如50%,那么LB会在50%机器崩溃的时候,禁用淘汰策略,把所有机器都当做健康的,在整体集群上执行普通的Round-Robin策略。
多数机器恢复,整个集群的处理能力恢复80%的正确率。这使得整个集群能够在遇到极特殊情况的时候能够从困境中恢复。
以上所述就是小编给大家介绍的《Envoy中的 LB 算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 通俗易懂--决策树算法、随机森林算法讲解(算法+案例)
- 限流算法之漏桶算法、令牌桶算法
- 什么是Paxos算法?Paxos算法是区块链核心算法之一
- 一文读懂对称加密算法、非对称加密算法和Hash算法
- 算法(六):图解贪婪算法
- 算法篇03:排序算法
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。