Day 14 / 共 20 天 · 第 3 周 xDS 与上游

负载均衡

集群里有多个后端，一个请求该发给哪个？这就是负载均衡（LB）。今天看 LoadBalancer::chooseHost 接口，以及轮询、最少请求（P2C）、一致性哈希几种经典算法的实现。

📍 你在整门课的位置 · 第 3 周「xDS 与上游」（D13 选到了"哪组窗口"Cluster → 今天讲从这组里挑哪个具体窗口）

D11 xDS 总览→ D12 配置订阅→ D13 集群管理→ D14 负载均衡→ D15 健康检查/发现

L01

LoadBalancer 接口

// envoy/upstream/load_balancer.h:191
class LoadBalancer {
  virtual HostSelectionResponse chooseHost(LoadBalancerContext* context) PURE;   // :222 核心！
  virtual HostConstSharedPtr peekAnotherHost(LoadBalancerContext* context) PURE; // :230 预测下一个（预连接）
};

LB = "从一堆后端里挑一个" chooseHost 就是负载均衡的全部：给它一个请求上下文，它按某种算法返回"这个请求该发给哪台后端"。不同算法有不同取舍：轮询最公平简单、最少请求更能避开慢节点、一致性哈希保证同一用户总去同一后端（会话粘性）。Router（Day 09）转发前就调它选后端。peekAnotherHost 用于"预连接"（提前和下一个可能用到的后端建连，降延迟）。

L02

现有 LB 类型

每种算法一个目录（source/extensions/load_balancing_policies/）：

算法	特点
round_robin	轮询，依次分配（最公平）
least_request	最少请求，避开繁忙节点（默认）
ring_hash / maglev	一致性哈希，会话粘性
random	随机
subset	子集（按元数据筛选后再 LB）

读法：多数加权算法继承 EdfLoadBalancerBase（EDF = Earliest Deadline First 加权公平调度，L05）。算法都作为扩展存在（Day 16 讲扩展机制）——想加新算法，写个扩展注册即可。

L03

轮询 Round Robin

// source/extensions/load_balancing_policies/round_robin/round_robin_lb.h:28
class RoundRobinLoadBalancer : public EdfLoadBalancerBase {
  HostConstSharedPtr unweightedHostPick(const HostVector& hosts_to_use, const HostsSource& source) override {
    return hosts_to_use[rr_indexes_[source]++ % hosts_to_use.size()];   // :78 取模递增
  }
  absl::flat_hash_map<HostsSource, uint64_t, HostsSourceHash> rr_indexes_;  // :82
};

读法：等权重时轮询就是最朴素的"取模递增"：一个自增索引对后端数取模，1→2→3→1→2→3… 依次分配。每个 HostsSource（优先级+本地性组合）有独立索引。权重不等时走 EDF 基类（L05）。

🤔 痛点："扫描所有窗口、选最闲的"听着最优，其实会翻车延续餐厅比喻：大堂经理想把新顾客派给"当前最空的窗口"。直觉做法是扫一遍所有窗口选最闲的——但两个问题：①窗口多时扫描慢（O(N)）；②"羊群效应"——所有服务员同一瞬间都把顾客往那个"最闲窗口"塞，一下把它挤爆。

💡 本质：P2C = 随机瞄两个窗口，挑人少的那个 Power of Two Choices：随机挑 2 个后端，选活跃请求更少的那个。只看 2 个（O(1) 超快），却能很好地近似"全局最少"；而且因为有随机性，不会所有人挤同一个——羊群效应消失。这是负载均衡领域著名的理论结果，Envoy 默认就用它。

📝 举个例子：5 个后端的活跃请求数 [3,1,4,1,5] 全局最少：所有 worker 同时都选到 index=1（值 1）→ 瞬间被打爆。
P2C：worker A 随机抽到 [4,1]→选 1；worker B 随机抽到 [3,5]→选 3；worker C 抽到 [4,1(第4个)]→选第4个。负载被摊开，没人扎堆。

左：全局选最少 → 所有请求扎堆同一个"最闲"节点（羊群效应）。右：P2C 随机二选一 → O(1) 且负载分散。

L04

最少请求 P2C

least_request_lb.h:25 的 LeastRequestLoadBalancer，默认用 P2C（Power of Two Choices，二选一）（unweightedHostPickNChoices，:71）：随机取 2 个后端，选其中活跃请求数更少的那个。

为什么"随机二选一"比"全局选最少"更好？直觉上应该扫描所有后端、选活跃请求最少的那个（全局最优）。但那样有两个问题：①后端多时扫描慢（O(N)）；②"羊群效应"——所有 worker 线程同时都把请求发给那个"当前最闲"的后端，瞬间把它打爆。P2C 的巧妙：随机挑 2 个，选较闲的那个。O(1) 代价，却能很好地近似全局最少请求，且因为有随机性不会所有人挤同一个。这是负载均衡领域著名的理论结果（"两个选择的力量"）。Envoy 默认用它。

L05

EDF 加权公平

权重不等时（比如后端 A 权重 3、B 权重 1，希望 A 收 3 倍流量），走 EdfLoadBalancerBase（基于 edf_scheduler.h）：用权重的倒数作 deadline，实现按权重平滑分配。

EDF = "谁最该被选就选谁" EDF（Earliest Deadline First，最早截止优先）本是操作系统调度算法。这里用它做加权：权重高的后端"deadline 来得快"（倒数小），所以被选得更频繁，但又是平滑交错的（A B A A B A A A…而非 AAA...BBB...）。好处：既满足权重比例，又避免"连续把请求全给高权重节点"的突刺。慢启动（slow-start）因子也叠加在这里——新上线的节点权重逐渐爬升，避免冷启动被打爆。

L06

一致性哈希

ring_hash / maglev 提供会话粘性：按请求的某个 key（如用户 ID、cookie）哈希到固定后端——同一用户总去同一后端。

为什么需要"粘性"？有些场景需要"同一用户的请求总落到同一后端"——比如后端在本地缓存了该用户的会话数据。一致性哈希（ring_hash/maglev）把后端排在一个哈希环上，请求按 key 哈希落到环上最近的后端。关键优点：某个后端挂了，只有它负责的那一小段 key 需要重新分配，其他用户不受影响（普通哈希取模会导致后端数变化时几乎所有 key 重新分配）。maglev 是 Google 的改进版，分布更均匀。这是"有状态服务"负载均衡的标准解法。

🧭 到底选哪个 LB？一张对照表帮你决策：

算法	什么时候用	一句话
round_robin	后端等价、无状态、想最简单公平	轮流发牌
least_request(P2C)	后端处理慢快不一（默认）	随机二选一挑闲的
ring_hash/maglev	要会话粘性（后端缓存了用户态）	老顾客总去熟悉的窗口
random	极简、量大、不在乎精细	随手一指
subset	先按元数据筛一批再 LB	先分区再挑

⚠️ 常见误解：以为"轮询最公平所以最好"。其实轮询只在每个请求耗时都差不多时才公平；一旦有慢节点，轮询照样把请求塞给它 → 越塞越堵。least_request(P2C) 才会避开繁忙节点，所以 Envoy 默认用它。

口诀：等价轮询、快慢用 P2C、粘性用哈希权重不等时，以上算法都会走 EdfLoadBalancerBase（EDF 加权平滑，L05），保证"权重 3 的收 3 倍流量，却是 A B A A B 交错、不是 AAA…BBB"。

L07

LB 是扩展

所有 LB 算法都在 source/extensions/load_balancing_policies/，作为扩展注册（Day 16）。集群配置里指定用哪个策略，ClusterManager 为集群创建对应 LB。

读法：LB 可插拔——这体现了 Envoy"核心稳定 + 扩展丰富"的架构。每个 Worker 的 ClusterEntry（Day 13）持有该集群的 LB 实例，本线程独享（无锁）。选后端发生在 Router 转发时，从当前线程的 LB 调 chooseHost。

L08

今日小结 + 动手

                🧠 今天你应该能回答
                chooseHost 干什么？LB 的核心问题是什么？
轮询等权重时怎么实现？
P2C 为什么比"全局选最少"好？（羊群效应 + O(1)）
EDF 怎么做加权平滑分配？
一致性哈希解决什么问题？后端挂了影响多少 key？

            

✋ 动手

cd /Users/bitmart/work/codes/github/higress-group/envoy
sed -n '191,235p' envoy/upstream/load_balancer.h
sed -n '28,85p' source/extensions/load_balancing_policies/round_robin/round_robin_lb.h
ls source/extensions/load_balancing_policies/

明天预告 · Day 15（第3周收官）：健康检查 + 服务发现——主动健康检查（定时探测）vs 被动异常点检测（看真实请求结果剔除坏节点），以及 static/strict_dns/logical_dns/eds 四种端点来源，最后串讲 LDS→RDS→CDS→EDS 全链路。

← Day 13 Cluster Mgr Day 15 · 健康检查 + 服务发现 →