46. 排队论与容量估算：利特尔法则与尾延迟

1. 平均延迟骗人

监控大盘上「平均响应时间 20 ms」看起来很健康，但用户仍抱怨卡顿。原因在于延迟分布是长尾的：均值被大量快速请求拉低，而真正影响体验的是 P95、P99 甚至 P999。一个服务可能有 20 ms 的中位数，却有 2 秒的 P99——对一次要扇出 100 个下游调用的聚合请求来说，几乎每次都会撞上某个下游的尾部。

尾延迟（Tail Latency） 的工程含义是：用分位数而非均值来定义 SLO。常见目标：

2. 利特尔法则

2.1 公式

利特尔法则（Little’s Law） 是排队论里最稳健的结论，对任意到达分布、任意服务分布、任意调度策略都成立：

L = λ · W

L = 系统中平均请求数（并发数 / 在途数）
λ = 平均到达率（吞吐，请求/秒）
W = 平均逗留时间（延迟，秒）

它把「并发、吞吐、延迟」三者锁死成守恒关系：知道任意两个，第三个就被确定。

2.2 三种用法

1. 已知吞吐与延迟，求需要的并发数：
   L = λ · W = 1000 req/s × 0.05 s = 50

2. 已知线程池大小与延迟，求最大吞吐：
   λ = L / W = 200 / 0.02 = 10000 req/s

3. 已知并发与吞吐，估算延迟：
   W = L / λ = 64 / 3200 = 0.02 s = 20 ms

2.3 工程直觉

• 线程池大小本质就是 L：池子太小 → 请求排队；池子太大 → 上下文切换与内存开销。
• 连接池同理：L = 峰值 QPS × 平均占用时长。
• 利特尔法则不假设任何分布，因此是压测与容量估算里最可靠的锚点。唯一前提是系统处于稳态（到达率 ≈ 完成率）。

3. 排队模型

3.1 Kendall 记号

排队系统用 A/S/c/K/N/D 描述，通常只写前三项：

M/M/1 表示泊松到达、指数服务时间、单服务台。

3.2 M/M/1

设到达率 λ、服务率 μ（单台每秒处理数），定义利用率 ρ = λ / μ（要求 ρ < 1 才稳定）：

系统内平均请求数：  L  = ρ / (1 - ρ)
平均逗留时间：      W  = 1 / (μ - λ)
平均排队时间：      Wq = ρ / (μ - λ)

关键洞察：当 ρ → 1 时，L 与 W 非线性爆炸：

核心结论：利用率从 50% 提到 90%，系统内请求数翻了 9 倍。这就是「别把 CPU 跑到 90%」的数学依据——不是浪费，而是给突发流量留缓冲。

3.3 M/M/c 与 Erlang C

多服务台（如 8 线程池）的等待概率由 Erlang C 公式给出：

a = λ / μ                （到达强度，Erlang）
ρ = a / c                （每个服务台的利用率）

P(排队) = [ a^c / (c!(1-ρ)) ] / [ Σ_{k=0}^{c-1} a^k/k! + a^c/(c!(1-ρ)) ]
Wq = P(排队) / (cμ - λ)

它说明：服务台越多，在相同利用率下排队概率越低。8 个利用率 80% 的线程，比 1 个利用率 80% 的线程，排队延迟小得多——这是「池化」的理论收益。

3.4 用 Python 算一算

import math

def mm1(lam, mu):
    rho = lam / mu
    if rho >= 1:
        return None  # 不稳定，队列无限增长
    return {
        "rho": rho,
        "L":  rho / (1 - rho),
        "W":  1 / (mu - lam),
        "Wq": rho / (mu - lam),
    }

print(mm1(lam=90, mu=100))   # ρ=0.9, W≈0.1s, Wq≈0.09s

def erlang_c(lam, mu, c):
    a = lam / mu
    rho = a / c
    if rho >= 1:
        return None
    s = sum(a**k / math.factorial(k) for k in range(c))
    last = a**c / (math.factorial(c) * (1 - rho))
    p_wait = last / (s + last)
    wq = p_wait / (c * mu - lam)
    return {"rho": rho, "P_wait": p_wait, "Wq": wq}

print(erlang_c(lam=90, mu=12, c=8))  # 8 台，利用率≈0.94

3.5 服务时间分布的影响

M/M/1 假设服务时间服从指数分布，其变异系数 Cv = 标准差 / 均值 = 1。真实系统的服务时间往往更集中（Cv < 1）或更离散（Cv > 1）。用 Pollaczek-Khinchine（P-K）公式可推广到一般服务分布：

Wq = (ρ / (1 - ρ)) × ((1 + Cv²) / 2) × (1 / μ)

代入 Cv = 0（确定性服务，如固定大小任务）可得 Wq = ρ / (2(1-ρ)μ)，排队延迟减半；代入 Cv = 1 则退化回 M/M/1。工程含义：

• 让服务时间更均匀（限请求大小、拆大任务）能直接缩短排队延迟。
• 若服务时间重尾（Cv ≫ 1，如大查询拖尾），排队延迟会被显著放大，必须靠超时与隔离（舱壁模式）兜底。

4. 利用率曲线与拐点

把上面的表画成曲线，会发现一个拐点：利用率低于约 70% 时延迟几乎平坦，超过后迅速上翘。

延迟
 │                              ╭─── 急剧上翘
 │                          ╭───╯
 │                    ╭─────╯
 │        ────────────╯            ← 拐点约在 ρ≈0.7~0.8
 └────────────────────────────────▶ 利用率 ρ
   0.5      0.7     0.8   0.9  0.95  1.0

工程含义：

• 容量规划应把稳态利用率控制在 60%~70%，为突发留出 30%~40% 余量。
• 自动扩缩容的触发阈值应设在拐点之前，否则扩缩容本身会被排队拖慢。
• 突发流量会把瞬时 ρ 推过拐点，这就是需要**过载保护（限流、熔断）**的原因。

5. 尾延迟的来源

5.1 尾延迟放大

当一个请求需要扇出到多个下游（如搜索聚合、广告竞价），整体延迟是各下游延迟的最大值：

单下游 P99 = 1% 概率慢 → 扇出 100 个下游
至少一个慢的概率 = 1 - 0.99^100 ≈ 63%

即使每个下游的 P99 只有 1%，扇出 100 后整体「变慢」的概率高达 63%。扇出越多，尾部越被放大。缓解手段：

• 对冲请求（Hedged Request）：超过 P95 时向第二个副本重发，取先返回者。
• 微分区（Micro-partitioning）：让同一请求的所有下游落在同一台，减少放大。
• 少扇出：合并下游调用，用批处理换取更少的独立性。

5.2 协调遗漏

协调遗漏（Coordinated Omission） 是压测中最隐蔽的陷阱：压测工具按固定速率发请求，一旦被测系统变慢、响应堆积，工具就「停发等待」，从而漏掉了最慢的那批请求，把 P99 报得虚低。

错误做法：每发一个请求，等它返回再发下一个
  → 系统卡顿时自动降速，测出的延迟偏乐观

正确做法：按固定速率（如 1000 req/s）独立发送，
          记录「应发时刻」与实际完成时刻的差值

wrk2、k6、gatling 等工具支持「按速率发送 + 修正延迟」，能还原真实的尾部。

5.3 队头阻塞与排队不公

• 队头阻塞（HOL Blocking）：FCFS 队列里一个慢请求挡住后面所有快请求。
• 缓解：多队列 + 优先级、按请求大小分级（SJF 近似）、随机化（Power of Two Choices）。

6. 容量估算实操

6.1 线程池/连接池定容

步骤：
1. 压测得到单请求平均服务时间 W0（如 20 ms）
2. 估算目标峰值 QPS λ（如 5000）
3. 由利特尔法则算最小并发：L = λ × W0 = 5000 × 0.02 = 100
4. 按目标利用率反推容量：c = L / 目标利用率 = 100 / 0.7 ≈ 143
5. 取整并留冗余：线程池 ≈ 150

6.2 数据库连接池

数据库连接是稀缺资源，过大会引发上下文切换与锁竞争。经验公式：

连接数 ≈ ((核心数 × 2) + 有效磁盘数)

例如 8 核 + SSD：8 × 2 + 1 = 17，取 20 左右

这个公式来自 PostgreSQL 社区实践，背后正是排队论：连接太多会让 ρ 冲过拐点，反而降低吞吐。

6.3 压测方案

# wrk2：按固定速率压测，避免协调遗漏，输出正确分位数
wrk -t4 -c200 -d60s -R5000 --latency http://localhost:8080/api

# 输出关注 P50/P90/P99/P99.9 与「非 2xx 比例」

压测时至少覆盖三个维度：

6.4 过载保护

排队论给出的负反馈手段：

• 限流（Rate Limiting）：令牌桶/漏桶把 λ 钳制在 μ 以下。
• 并发限制（Concurrency Limit）：直接用信号量限制在途数 L，超出的快速失败。
• 熔断（Circuit Breaker）：下游连续失败时直接短路，避免请求堆积把 ρ 推向 1。
• 背压（Backpressure）：无缓冲队列让上游感知拥塞，而非无限堆积。

这些手段与https://plumephp.com/cs-network-model/的分层模型、https://plumephp.com/cs-transport-layer-tcp/的拥塞控制一脉相承：TCP 的慢启动、AIMD 本质上也是用排队论思想调节发送速率，避免网络队列过载。

7. 模型假设与适用边界

排队论模型好用，但依赖几条容易被忽视的假设，误用会得出错误结论。

7.1 泊松到达是否成立

M/M/1 假设到达是泊松过程（到达间隔指数分布、无记忆性）。现实中：

• 大量独立用户的聚合流量近似泊松，成立。
• 同步批量任务（如整点定时、客户端重试风暴）是**突发（bursty）**的，泊松假设失效，实际排队远重于模型预测。
• 重试放大：下游超时触发上游重试，会把一次请求放大成多次，λ 瞬间翻倍。

检验方法：抓取到达时间间隔，看其分布是否接近指数；或比较实测方差与均值（泊松的方差 = 均值）。

7.2 队列纪律

FCFS 下所有请求都变慢，而 PS 下小请求几乎不受大请求影响。这也是为什么「按请求大小分级队列」能显著改善 P99。

7.3 稳态与瞬态

所有公式都建立在稳态假设上：到达率长期不超过服务率。当系统过载（λ > μ）时，队列无限增长，任何「平均延迟」都无意义——此时唯一正确的动作是丢请求（限流），而不是算延迟。

稳态：λ < μ  → 队列长度有界，公式可用
过载：λ ≥ μ  → 队列发散，必须限流/降级

8. 小结

容量估算的三块基石是：利特尔法则（L = λW 守恒）给出并发/吞吐/延迟的换算；M/M/1 与 Erlang C 量化了「利用率过拐点后延迟爆炸」；尾延迟与协调遗漏提醒我们分位数才是 SLO 的正确度量。工程上，把稳态利用率控制在 60%~70%、用固定速率压测还原尾部、并用限流/并发限制/熔断守住过载边界，比事后调参有效得多。

参考文章

• IO 模型与多路复用：https://plumephp.com/cs-io-models/
• 网络基础专题：网络基础