Priority Level

在上一篇文章中我提到

Priority

，一個叢集可以包含多個

Priority

，每一個

Priority

下可以有很多主機，預設的

Priority

是0，也是最高的優先級，如果一個叢集同時存在多個

Priority

，Envoy是如何來進行處理呢? Envoy預設隻從

Priority

為0的的主機中進行負載均衡，直到

Priority

為0的主機其健康的比例低于某個閥值才會按照一定的比例将流量發往下一個優先級。那麼問題來了? 如何界定主機是否健康?，這個閥值是多少?，發到下一個優先級的流量的比例是如何計算的? 接下來針對這些問題我們從代碼中找尋答案。

// 一個Host的ymal表示
{
  "endpoint": "{...}",
  "endpoint_name": "...",
  "health_status": "...",
  "metadata": "{...}",
  "load_balancing_weight": "{...}"
}

每一個主機都會有個

health_status

，這個标志預設是

UNKNOWN

，Envoy認為帶有這個标志的機器，其健康狀态是

Healthy

的，相關的代碼如下:

/**
 * Implementation of Upstream::Host.
 */
class HostImpl : public HostDescriptionImpl,
                 public Host,
                 public std::enable_shared_from_this<HostImpl> {
public:
  HostImpl(ClusterInfoConstSharedPtr cluster, const std::string& hostname,
           Network::Address::InstanceConstSharedPtr address,
           const envoy::api::v2::core::Metadata& metadata, uint32_t initial_weight,
           const envoy::api::v2::core::Locality& locality,
           const envoy::api::v2::endpoint::Endpoint::HealthCheckConfig& health_check_config,
           uint32_t priority, const envoy::api::v2::core::HealthStatus health_status)
      : HostDescriptionImpl(cluster, hostname, address, metadata, locality, health_check_config,
                            priority),
        used_(true) {
    // 初始化的時候設定根據health_status來設定health_flag
    setEdsHealthFlag(health_status);
    weight(initial_weight);
  }
    .......
  // 查詢主機的健康狀況
  Host::Health health() const override {
    // If any of the unhealthy flags are set, host is unhealthy.
    if (healthFlagGet(HealthFlag::FAILED_ACTIVE_HC) ||
        healthFlagGet(HealthFlag::FAILED_OUTLIER_CHECK) ||
        healthFlagGet(HealthFlag::FAILED_EDS_HEALTH)) {
      return Host::Health::Unhealthy;
    }

    // If any of the degraded flags are set, host is degraded.
    if (healthFlagGet(HealthFlag::DEGRADED_ACTIVE_HC) ||
        healthFlagGet(HealthFlag::DEGRADED_EDS_HEALTH)) {
      return Host::Health::Degraded;
    }
        // health_status的值為UNKNOW的時候，health_flags_為0，是以被認為是Healthy的
    // The host must have no flags or be pending removal.
    ASSERT(health_flags_ == 0 || healthFlagGet(HealthFlag::PENDING_DYNAMIC_REMOVAL));
    return Host::Health::Healthy;
  }

private:
    ......
  std::atomic<uint64_t> health_flags_{};
};
// health_status預設值是UNKNOW，是以health_flags_沒有被設定，是預設值0。
void HostImpl::setEdsHealthFlag(envoy::api::v2::core::HealthStatus health_status) {
  switch (health_status) {
  case envoy::api::v2::core::HealthStatus::UNHEALTHY:
    FALLTHRU;
  case envoy::api::v2::core::HealthStatus::DRAINING:
    FALLTHRU;
  case envoy::api::v2::core::HealthStatus::TIMEOUT:
    healthFlagSet(Host::HealthFlag::FAILED_EDS_HEALTH);
    break;
  case envoy::api::v2::core::HealthStatus::DEGRADED:
    healthFlagSet(Host::HealthFlag::DEGRADED_EDS_HEALTH);
    break;
  default:;
    break;
    // No health flags should be set.
  }
}

在Envoy的運作過程中，這個狀态可能會因為健康檢查機制使其變成

UNHEALTHY

，也可以是控制面通過xDS下發EDS的時候，主動設定一個

UNHEALTHY

的status。接着我們來看下這個健康的閥值是多少?

100% == Overprovisioning Factor / 100.0 * 健康主機的比例

Envoy并沒有選擇直接使用健康主機的比例來确定閥值，而是通過設定Overprovisioning Factor(預設值140，可以通過xDS動态來改變)，然後通過上面公式乘以健康主機的比例。并根據計算的結果是否小于100%來确定是否要将流量發往其他優先級。也就是說預設情況下，健康主機的比例低于72%就會導緻結果小于100%，也就會将流量發往下一個優先級。那到底要發多少比例的流量呢?

P=0 healthy endpoints	Traffic to P=0	Traffic to P=1
100%		0%
72%
71%	99%	1%
50%	70%	30%
25%	35%	65%

轉發多少比例其實就是看上面公式的計算結果，結果是70%，那麼就轉發30%的流量到下一個優先級。如果我們發往下一個優先級的流量超過下一個優先級可能承載的比例這該怎麼辦?例如下面這張圖(P表示優先級)

	P=1 healthy endpoints

下一優先級的機器可以承載多少流量也是通過上面的公式計算出來的，如果發往下一個優先級的流量小于它可以承載的流量就全部發過去，否則就按照兩個優先級通過上面公式計算出來的結果按比例來均攤。上圖中的最後一組資料中，兩個優先級的健康主機比例都是25%，根據公示計算出來的結果應該是(1.4 * 25 = 35)，也就是承載35%的流量，然後将剩下的65%流量轉發到P1，但是P1的健康主機的比例也是25%，沒辦法承受65%的流量，這個時候需要按照兩者的所能承受的流量按比例來劃分。

Degraded endpoints

讨論完優先級後，接下來我們來聊一下Envoy支援的另外一個特性，host降級，這類降級的host能夠接收流量，但隻有在沒有足夠的健康主機可用時才會接收流量。那麼到底接收多少流量呢? 計算的方式和上面讨論的優先級一樣。

P=0 healthy/degraded/unhealthy	Traffic to P=0 healthy hosts	Traffic to P=0 degraded hosts
100%/0%/0%
71%/0%/29%
71%/29%/0%
25%/65%/10%
5%/0%/95%

簡單來說就是健康的主機先接收流量，處理不了的，交給降級的host來處理，仍然處理不了的，就交給下一個優先級來處理。那如何才能稱為降級的host呢?，有兩種方式，第一種就是通過控制面下發EDS的時候，将host的

health_status

字段設定為DEGRADED，另外一種就是配置健康檢查，upstream的機器在收到健康檢查的請求時，在response中帶上

x-envoy-degraded

的header就表明這個主機被降級了。

Locality weighted load balancing

Envoy的Load balancer子產品是很強大的，它支援區域相關的路由，比如區域感覺路由、還有接下來要說的區域權重負載均衡。Envoy中的host都是帶有

Locality

的，也就是有區域的屬性。每一個

Locality

都會帶有一個權重。當開啟

Locality weighted load balancing

的時候，會按照權重比例将流量發到每一個

Locality

Locality

根據指定的負載均衡算法來挑選主機。如果某個

Locality

中的主機無法承載那麼多流量(根據 Overprovisioning Factor / 100.0 * 健康主機的比例這個公式計算出來，如果小于100%就無法承載)，就會按照下列算法進行流量的配置設定。

// Setp1: 計算一個Locality X可以承載的流量
availability(L_X) = 140 * available_X_upstreams / total_X_upstreams

// Setp2: 計算Loocality X的有效權重等于實際權重乘以可以承載的流量比例 
effective_weight(L_X) = locality_weight_X * min(100, availability(L_X))

// Setp3: 計算接收的流量比例，locality X的有效權重除以所有的locality的有效權重之和
load to L_X = effective_weight(L_X) / Σ_c(effective_weight(L_c))

下面是一個

Locality weighted load balancing

的流量配置設定的例子，有兩個

Locality

X和Y，前者的權重是1，後者的權重是2。Y可以100%承載主機流量。

L=X healthy endpoints	Percent of traffic to L=X	Percent of traffic to L=Y
	33%	67%

69%	32%	68%
	26%	74%
	15%	85%

比如上面這張圖中，當Locality X的健康主機比例是25%的時候，根據公式計算出來可以承受35%的流量，Locality X的權重是1，是以最後的有效權重是35%，locality Y可以承受100%的流量，其有效權重為100% * 2 = 200%，最後Locality X可以接收的流量比例等于35% / (200% + 35%) ~ 15%。到此為止Locality weighted load balancing就講解完畢了。

Panic threshold

最後來講一下Envoy中的

Panic mode

的概念，正常模式下，我們認為配置的叢集是有能力承載目前的流量，但是随着部分upstream因為健康檢查等原因從可用的機器清單中移除時，會導緻我們的可用的upstream數量減少。但是要承載的總的流量大小并沒有改變，也就是說我們需要使用更少的機器來承載相同的流量，一旦可用的upstream低于某個閥值Envoy就認為達到了

Panic mode

，就會将流量發到所有的機器，無論是否可用。這個閥值就稱為

Panic threshold

。

總結

在前面的文章中談到的負載均衡算法，以及本文中提到的

Locality weighted load balancing

、`Priority Level，這幾者之間的關系到底是啥? 誰先誰後? 總的來說Envoy會根據下面這個步驟來進行負載均衡。

根據 Priority Level 選擇合适的優先級
找到優先級後對這個優先級下的所有 Locality 執行 Locality weighted load balancing 确定發往這些 Locality 的流量比例。
對一個 Locality 包含的host使用指定的負載均衡算法擷取要發送的host

參考文獻

Load Balancing

Envoy源碼分析之Load balancing PriorityPriority LevelLocality weighted load balancing總結參考文獻Next

Priority Level

Degraded endpoints

Locality weighted load balancing

Panic threshold

總結

參考文獻

Next

繼續閱讀

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

nginx location中斜線的位置的重要性

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希