什么是Load balancing?

Load balancing is a way of distributing traffic between multiple hosts within a single upstream cluster in order to effectively make use of available resources. There are many different ways of accomplishing this, so Envoy provides several different load balancing strategies. At a high level, we can break these strategies into two categories: global load balancing and distributed load balancing.

上面是Envoy官方文档对于Load balancing的一个解释，说通俗点就是一种将流量分布到一个upstream集群中的多台机器上的方法。而实现的方式有很多种，Envoy提供了几种Load balancing的策略，主要是分为global load balancing和 distributed load balancing两类。前者是通过一个中心的控制节点来决策流量到底分布到哪些机器，比如通过控制节点来调节权重、优先级、区域等，而后者则是Envoy自己根据自定义的规则来决定流量到底分布到哪些机器上，比如根据区域来决策、或者根据自己使用的负载均衡算法、又或者是根据机器的健康状况来决策，Envoy是同时支持这两种策略的。

Envoy中Load balancer的类型

上面这张图是Envoy中的Load balancer的实现类图，蓝色部分是各个Load balancer实现所依赖的基类，每一种颜色代表一种Load balancer实现。根据它们所实现的基类可以知道这些Load balancer的类型。在Envoy中大致可以分为五类。

1. 带有权重支持的Load balancer(EdfLoadBalancerBase)
2. 带有区域感知支持的Load balancer(ZoneAwareLoadBalancerBase)
3. 每一个worker线程包含一个Load balancer实例(LoadBalancerBase)
4. 所有线程共享同一个Load balancer实例(ThreadAwareLoadBalancerBase)
5. 自定义的Load balancer(LoadBalancer)

根据Load balancer所继承的基类就可以知道这个Load balancer所属于的类别，接下来我具体分析下这五个基类。EdfLoadBalancerBase这是借助EDF算法(后面的文章会介绍这个算法)实现对权重的支持，这个类继承自ZoneAwareLoadBalancerBase，所以说支持权重的同时也支持区域感知，区域感知简单来说就是可以将流量分布到和Envoy运行所在区域相同的机器上。LoadBalancerBase继承这个基类的Load balancer是每一个worker线程一个实例，在进行load balancing的时候每一个线程从各自的实例中进行获取，这么做的好处就是避免了锁，但是带来的问题就是存在冷启动的问题，因为load balancer的算法的结果是固定的，所以每一个实例在启动的时候都是会选择相同的机器，如果线程数很多的话会导致启动的时候流量都达到相同的机器上。但是如果是所有的线程共享同一个实例就不会有这个问题，这类load balancer需要继承ThreadAwareLoadBalancerBase，最后一类是继承LoadBalancer，这类load balancer有自己的一整套算法，目前Envoy中主要是subset load balancer，它会根据机器中携带的元信息进行选择。

Envoy中支持的Load balancer

1. 基于权重的RR
2. 基于权重的最小连接数
3. Ring Hash
4. Maglev
5. 随机
6. subset

基于权重的RR和最小连接数是支持区域感知路由的，而且是每一个线程一个load balancer实例，而Ring Hash和Maglev则是全局一个实例并且不支持区域感知，随机则不支持权重，但是支持区域感知。subset则是安全一套自己的算法。

Envoy中关于Load balancing的基本概念

在正式开始分析Envoy中的Load balancing的时候，我们需要介绍下Envoy关于这个部分的一些基本概念，Envoy首先会根据指定的路由规则选取集群，而Load balancing的对象就是集群下面的机器列表。Envoy中有很多概念是为了加强Load balancing机制的，下面我们来一个个介绍下。首先是Priority，一个集群下面可以配置多个Priority，每一个Priority会存在一些机器，是用来表示一组机器的优先级的，默认从0开始，优先级最高。下一个概念就是Locality，用来表示机器所在的位置，主要的用途就是用来实现区域感知路由。最后通过一张图来表示下Cluster、Priority、Locality、Host这几个的关系。