什麼是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這幾個的關係。