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%的正确率。这使得整个集群能够在遇到极特殊情况的时候能够从困境中恢复。

通用运营后台

火山和抖音都有搜索彩蛋的需求就是搜索某个特定词的时候出一些彩蛋，配合广告售卖或者活动
大家接到需求的想法就是写个运营后台，数据存入mysql，然后再起个脚本，定时把数据按照格式dump到redis，在线服务读redis判断
或者说单独抽象一个服务，运营后台负责写入，在线业务负责读取

搜索结果过滤条件

客户端配置，广告、图片链接配置，客户端Toast提示文本内容。
你可以设置用户满足什么地域、UID在哪个灰度的情况下，更换某一项内容。

Envoy中的 LB 算法