第37章负载均衡算法推导与韧性状态机

学习目标

推导主流 LB 算法的"为什么"：P2C 为何吊打 least-conn、一致性哈希环、Maglev 查表
掌握熔断器三态状态机与重试预算，理解它们如何保护后端
理解亚稳态失败——为什么系统过载后即使触发消失也不自愈
把"选后端（LB）+ 保后端（韧性）"串成代理在故障下的完整行为

前置知识

第09章 LB 算法（列名）、第10章重试/幂等、第31章重试放大

原理 · A 部分：负载均衡算法推导

第09章列了算法名，这里补上"为什么这样设计"。

从轮询的问题说起

纯轮询/随机假设"后端同质、请求同质"，现实往往不是：后端配置不一、请求耗时差异大 → 负载倾斜。改进方向是"看负载选"——但怎么看、看的代价多大，是关键。

least-conn 的隐藏代价

"选当前连接数最少的"听起来最优，但有两个问题：

需要全局状态：得知道每个后端此刻的连接数。单机 LB 还好，分布式/多副本 LB 之间难实时同步——你以为最少的，别的 LB 也在往那打。
连接数 ≠ 负载：一个连接可能在跑重活，另一个在 idle。

P2C：用 O(1) 状态逼近最优

Power of Two Choices（两选一） 是个漂亮的结果：

  随机挑 2 个后端 → 比较它们的负载（连接数 / EWMA 延迟）→ 发给较优的那个

为什么它吊打纯随机？理论结果：

纯随机分配，n 个后端最大负载约 Θ(log n / log log n)
只要随机挑 d=2 个取较优，最大负载骤降到 Θ(log log n)——指数级改善，而再增加 d（挑 3 个、4 个）收益急剧递减

关键是：P2C 只需 O(1) 状态、无需全局协调（每次随机两个、本地比一下），却拿到接近全局 least-conn 的效果。所以 Envoy 默认 LB 就是 P2C（叫 "weighted least request"）。这是"少量随机 + 局部比较"打败"全局最优但昂贵"的经典案例。

一致性哈希：让后端增减只扰动 1/N

当你需要同一个 key 总落到同一个后端（缓存亲和、会话保持、sharding），就要哈希。但朴素的 hash(key) % N 有致命问题：

  N 从 4 变 5：几乎【所有】key 的 % 结果都变了 → 缓存全部失效、会话全乱

一致性哈希用一个环解决：

  把后端和 key 都 hash 到一个环（0 ~ 2³²）上
  key 顺时针找到的第一个后端 = 它的归属

         后端A
        /      \
   key3         后端B
      |          |
   后端D        key1
        \      /
         后端C ← key2 顺时针归 D

  加/删一个后端，只影响【环上相邻的一段】key → 只重映射约 1/N

但有个陷阱：后端少时，它们在环上分布不均，可能某个后端占了大半个环 → 负载倾斜。解法是虚拟节点（vnode）：每个物理后端在环上放多个点（如 100~200 个），把分布抹匀。

Maglev：把一致性哈希做成 O(1) 查表

一致性哈希环的查找是 O(log n)（二分找下一个点），vnode 还占内存。Google 的 Maglev 改进：

  预计算一张固定大小的查找表（大小 M 取大质数，如 65537）
  每个后端按一个 permutation 填表，直到填满
  查找：table[hash(key) % M] → O(1)，且分布极均匀
  后端增减：重算表，但扰动很小（接近一致性哈希的最小重映射）

Maglev = 一致性哈希的最小扰动 + O(1) 查表 + 更均匀。用于 Google Maglev 负载均衡器和 Cilium 的 XDP/eBPF L4 LB（第11章/第12章），无状态、线速。

小结：算法选型的"为什么"

算法	状态成本	适合	代表
轮询/随机	O(1)	同质后端	简单场景
P2C	O(1)	通用、并发高	Envoy 默认
一致性哈希	O(log n)	缓存亲和/会话/sharding	缓存层
Maglev	O(1) 查表	大规模 L4 LB	Google/Cilium

原理 · B 部分：韧性状态机

LB 决定"发给谁"，韧性机制决定"出故障时怎么办"——二者共同决定代理在故障下的行为。

重试预算：替代"固定重试次数"

第31章讲过重试放大。固定"重试 3 次"的问题是：后端越挂、重试越多，正好在它最虚弱时加倍捶它。更好的是重试预算（retry budget）：

  限制【重试请求】占【总请求】的比例（如 ≤ 20%）
  后端健康时：失败少，预算够，正常重试
  后端挂时：失败多，预算很快耗尽，停止重试 → 不再雪上加霜

Envoy 用比例预算替代固定次数，本质是让重试在系统健康时帮忙、在系统垂危时自动让路。配合指数退避 + 抖动（jitter），避免重试同步成尖峰。

熔断器：三态状态机

熔断器（circuit breaker）是保护后端的核心状态机：

            错误率 > 阈值
   ┌────────────────────────────▶┐
[Closed 正常]                  [Open 熔断]
   ▲   请求通过，统计错误率        │   直接快速失败，不打后端
   │                              │   （给后端喘息）
   │  探测成功                     │ 熔断超时后
   │                              ▼
   └──────────[Half-Open 半开]◀──┘
              放少量探测请求：
              成功 → 回 Closed
              失败 → 退回 Open

Closed：正常放行，统计错误率/超时率
Open：错误率超阈值，打开——后续请求直接快速失败（fail fast），不再打后端，给它恢复时间
Half-Open：熔断一段时间后，放少量探测请求试水；成功就恢复 Closed，失败就退回 Open

Envoy 还有异常剔除（outlier detection）：自动把连续失败的后端临时摘除一段时间（被动健康检查，第09章/第10章），是熔断在"后端集合"粒度的版本。

亚稳态失败：为什么过载后不自愈

这是分布式系统最阴险的故障模式，也是韧性设计的终极理由：

亚稳态失败（metastable failure）：系统在正常负载下稳定；一个触发（流量尖峰、GC、慢依赖）把它推过某个拐点后，系统靠自身的重试/排队维持崩溃状态，即使原始触发消失也回不来。

经典正反馈循环：

  后端变慢 → 客户端超时 → 重试 → 负载加倍 → 后端更慢 → 更多超时重试 → ...
            ↑__________________ 自我维持的死亡螺旋 _______________↓
  原始尖峰早就过去了，但【重试流量】自己把系统摁在崩溃态

打破亚稳态的手段，正是上面这套：重试预算（砍掉放大）、熔断（断开正反馈）、退避抖动（去同步）、负载脱落（主动减载）。

负载脱落（load shedding）

过载时，主动拒绝一部分请求（快速返回 503）比"所有请求都慢/超时"更好——保住一部分请求的 SLA，而不是同归于尽。这是"优雅降级"的底线，也是打破亚稳态的减载手段。

️ 实现 / 命令

实验一：Envoy 配 P2C / 一致性哈希

clusters:
- name: backend
  lb_policy: LEAST_REQUEST          # P2C（weighted least request，Envoy 默认其一）
# 或缓存亲和场景：
- name: cache
  lb_policy: RING_HASH              # 一致性哈希环
  # 或 MAGLEV                       # Maglev 查表
  ring_hash_lb_config: { minimum_ring_size: 1024 }   # 环大小≈vnode 数

实验二：配熔断 + 重试预算 + 异常剔除

clusters:
- name: backend
  circuit_breakers:
    thresholds:
    - max_connections: 1000
      max_pending_requests: 100
      max_retries: 3
  outlier_detection:                 # 异常剔除（被动健康检查）
    consecutive_5xx: 5               # 连续 5 个 5xx → 临时摘除
    base_ejection_time: 30s
    max_ejection_percent: 50
# 路由侧重试预算（VirtualService/route）
retry_policy:
  retry_on: "5xx,reset"
  num_retries: 2
  retry_budget: { budget_percent: { value: 20 } }   # 重试 ≤ 20% 总流量

实验三：观察熔断三态切换

# 打挂后端（让其返回 5xx），观察熔断打开 → 快速失败
# Envoy admin 指标
curl -s localhost:15000/stats | grep -E "outlier|circuit|upstream_rq_pending"
# upstream_rq_pending_overflow ↑ = 熔断触发，请求被快速拒绝（不再打后端）
# 后端恢复后，half-open 探测成功 → 指标回落

排错

现象	根因	解决
后端负载倾斜	用了纯轮询/随机，后端异质	改 P2C（least request）
扩缩容后缓存命中率暴跌	用了 `hash%N`（非一致性）	改一致性哈希 / Maglev + vnode
少数后端过热	vnode 太少，环分布不均	调大 `minimum_ring_size`
重试把后端彻底打死	固定重试次数放大	重试预算 + 退避抖动
后端恢复了流量还打不进	熔断 half-open 探测失败/阈值太严	调熔断阈值与恢复探测
尖峰过去系统仍崩溃	亚稳态（重试自维持）	熔断 + 重试预算 + 负载脱落破环

本章小结

P2C（两选一）用 O(1) 状态逼近全局最优，指数级压低最大负载，是 Envoy 默认——少量随机+局部比较胜过昂贵的全局 least-conn。
一致性哈希（环 + vnode）让后端增减只扰动 1/N；Maglev 进一步做成 O(1) 查表、更均匀，用于大规模 L4 LB。
韧性靠状态机：熔断三态（Closed/Open/Half-Open）保护后端，重试预算让重试在系统垂危时让路。
亚稳态失败——重试/排队的正反馈让系统过载后不自愈；靠熔断+重试预算+退避抖动+负载脱落打破。

下一章第38章 capstone，把这套机制（背压/状态机/连接池/超时/韧性）整合，将前面的玩具代理改造成一个"生产级骨架"——底层机制篇与全书的收官。