徐术挺-漫思录

23-调度与排队

28分钟阅读

23 调度与排队：优先级、公平性、排队论

开篇提问

先给你一个场景：

你运维一个服务，突然流量涨了 3 倍，机器扛不住了。有两类请求：

  • A 类：普通用户查询，占 90% 流量，每个耗时 10ms
  • B 类：付费用户的导出请求，占 10% 流量，每个耗时 5 秒

现在系统饱和了，你必须丢弃一部分请求。请问：你该丢 A 还是丢 B？

直觉会说”丢 B，因为 B 慢、占资源”。

但请先想清楚一个反直觉的事实：一个 B 类请求占的资源，相当于 500 个 A 类请求。 丢一个 B，能腾出资源服务 500 个 A 用户。但丢 500 个 A，才能腾出资源服务 1 个付费用户。

先别急着下结论。我给你三个更深的问题，你把它们想清楚，答案会变得复杂得多：

  1. 你说的”资源”是什么？如果 A 和 B 占的是同一种资源（比如 CPU），那”丢一个 B 换 500 个 A”当然划算。但如果 B 占的是磁盘 IO、A 占的是 CPU呢？还能简单换算吗？
  2. “丢”是什么意思？你丢的到底是”拒绝新请求”，还是”杀掉正在跑的请求”？这两者对用户体验的影响天差地别。
  3. 那 10% 的付费用户，是不是比 90% 的普通用户更值钱？如果付费用户流失一个，损失顶得上普通用户流失一百个呢？

这三个问题问完，你会发现”丢 A 还是丢 B”这个问题，根本没有简单答案。因为”公平”和”效率”往往矛盾，“先来后到”和”重要优先”往往矛盾，“短期资源最优”和”长期商业价值”往往矛盾。

这一章讲清这个张力，以及真实的系统是怎么解它的。

子主题一：排队是必然的——为什么系统需要队列

先建立一个认知：只要”到达速率”存在波动、“服务速率”有限，排队就不可避免。

为什么？因为：

  • 请求的到达是随机的（不是均匀间隔到达）
  • 服务的处理时间是有波动的
  • 服务能力是有限的

即使平均到达速率远低于服务能力，排队的形成依然是必然的——因为到达有突发性。

想象一下：平均每秒来 5 个请求、系统每秒能处理 10 个，看起来”能力绰绰有余”。但某一秒突然来了 20 个，那一秒就排了 10 个的队。

一个帮助你理解”排队不可避免”的类比：银行柜台

银行有 3 个柜台，平均每分钟来 2 个客户、每个客户办 1 分钟。看起来”能力是需求的 1.5 倍”，绰绰有余。

但客户不是”每分钟精确来 2 个”——他们是随机地、扎堆地来的。可能 10 分钟没人，也可能 2 分钟内涌进 8 个人。一旦出现”扎堆”，队伍就排起来了，而且队伍一旦形成，需要很长一段时间才能消化掉（因为后面还在持续来人）。

这就是排队论最根本的洞见：你无法靠”平均能力大于平均需求”来避免排队，因为排队的元凶是”波动”，不是”平均”。

这就是排队论的核心洞察：系统利用率越高，排队延迟增长得越快，而且是非线性的。

子主题二：排队论的关键结论——利用率的非线性陷阱

排队论有个著名的公式（M/M/1 模型）：

平均排队延迟 ≈ (利用率 / (1 - 利用率)) × 服务时间

看几个数字感受一下这个非线性：

利用率平均延迟（相对服务时间）
50%1×
70%2.3×
80%4×
90%9×
95%19×
99%99×

注意 90% → 95% 这一段：利用率只涨了 5 个百分点，延迟却翻了一倍多。

这个非线性有个极其重要的工程含义

系统的”安全容量”远低于它的”理论容量”。

如果你的服务每秒能处理 1000 个请求，把它跑到 900 QPS（90% 利用率），延迟已经是空闲时的 9 倍。而跑满（100%）意味着延迟无穷大——系统彻底崩溃。

这就是为什么生产系统的容量规划通常只跑到 50-70% 利用率：不是浪费，而是给突发流量留出缓冲。越接近饱和，延迟增长得越离谱，而且一旦超过 100%，排队会无限增长，系统会进入”排队爆炸”状态并难以恢复。

为什么是 1/(1-利用率) 这个形状？

你可以直观地理解这个”越接近 1 越陡”的曲线：

  • 利用率 50% 时，你有一半时间空闲，空闲期能把排队的债还上。
  • 利用率 90% 时，你只有 10% 时间空闲，一旦来一波突发，队伍涨上去就很难降下来。
  • 利用率 99% 时，你几乎没有空闲，任何一点波动都会让队伍只增不减——队伍一旦涨起来，就再也回不去了。

这就是”非线性”的物理直觉：越忙，你越没有余力去消化波动，波动就越容易滚雪球。

另一个重要推论：长尾延迟会转化成排队

一个慢请求（耗时是正常请求的 100 倍）会占着资源 100 倍的时间，把后面的请求全堵住。

这就是为什么”消除长尾”比”降低平均延迟”更重要——一个慢请求的影响远不止它自己的延迟，它造成的排队会波及所有后续请求。

一个慢请求，等于”在队伍最前面的人突然不走了”。 后面所有人，不管多快，都被他堵住。所以真正致命的往往不是”平均慢”，而是”偶尔出现的、占着资源很久的慢请求”。

子主题三：调度策略——先来后到 vs 优先级

系统资源有限时，谁先用？这就是调度策略。

策略一：FIFO / FCFS（先来先服务）

  • 公平、简单、无饥饿
  • 问题：队头阻塞（Head-of-Line Blocking）——一个耗时长的任务堵在队头，后面所有短任务都得等它
  • 这就是开篇那个场景的默认行为：一个 5 秒的导出请求，堵住后面 500 个 10ms 的查询

策略二：优先级调度（Priority）

  • 重要的先做
  • 问题：饥饿（Starvation）——低优先级的任务可能永远排不上
  • 解法：老化（Aging）——等待时间越长，优先级自动提升

策略三：最短作业优先（SJF, Shortest Job First）

  • 理论上平均等待时间最优（这是排队论的数学结论）
  • 问题一：需要预知任务耗时（通常做不到，只能用历史估计）
  • 问题二：长作业饥饿

策略四：轮转（Round Robin / 时间片）

  • 每个任务轮流执行一小片时间，保证公平、保证响应性
  • 适合交互式系统（操作系统的进程调度）
  • 问题：上下文切换开销；且对”长任务”不友好（被切成很多片）

策略五：加权公平队列（WFQ）/ 公平调度

  • 按权重分配资源份额，既保证优先级，又保证每个队列都有份
  • 这是网络设备、容器编排（Kubernetes 的 requests/limits）常用的策略

真实系统的选择：几乎都是”混合策略”

  • 操作系统：优先级 + 时间片轮转 + 老化（多级反馈队列）
  • 数据库：优先级 + 资源组（Resource Group）隔离
  • Kubernetes：requests/limits（保证份额）+ QoS 等级（决定驱逐顺序）

一个帮助你记住这些策略的框架

这些策略，本质是在三个目标之间做权衡：

  1. 效率（让整体吞吐/平均等待最优）→ SJF 是赢家
  2. 公平（每个任务都有份，不饿死）→ 轮转、WFQ 是赢家
  3. 优先级（重要的先做）→ 优先级调度是赢家

没有任何一个策略能同时把三者都做到最好——SJF 效率最优但饿死长任务，优先级调度响应重要请求但饿死低优先级，轮转公平但效率不如 SJF。

所以真实系统永远是”混合”，而且是”带参数的混合”：多级反馈队列就是”优先级 + 轮转 + 老化”的组合，通过调参数在三者之间找平衡点。这和全书反复出现的”权衡”主题完全一致：没有最优解，只有”在你的约束下的最优解”。

子主题四：队头阻塞——一个反复出现的幽灵

队头阻塞（Head-of-Line Blocking）值得单独讲，因为它是”排队”带来的最隐蔽、最常复发的坑。

它的模式是：一个”慢的东西”堵住了后面的”快的”，导致整体性能崩塌。

它在计算机领域反复出现，每次换个皮：

形态一：单队列的任务调度（开篇那个场景）

一个 5 秒的导出任务堵住 500 个 10ms 的查询。

形态二：HTTP/1.1 的连接复用

HTTP/1.1 允许在一个 TCP 连接上发多个请求，但必须按顺序返回。第一个请求慢了，后面的全堵住。 → HTTP/2 的解法：多路复用（Multiplexing），把请求拆成独立的流，互不阻塞。

形态三：TCP 的队头阻塞（更底层）

TCP 保证字节流严格有序。如果第 3 个包丢了，即使第 4、5、6 个包都到了，应用层也读不到它们——必须等第 3 个包重传成功。 → QUIC（HTTP/3 的底层）的解法：在 UDP 上实现多路复用，每个流独立，丢包只影响它自己那条流。

形态四：数据库的锁等待

一个长事务持锁，后面所有需要这把锁的事务全排队。

形态五：消息队列的单分区

一个消费慢的消息堵住同一分区后面的所有消息。

识别队头阻塞的价值

当你发现系统”明明资源没跑满，但延迟很高”时，第一件事就是找队头阻塞——是不是有个慢的把整条队列堵住了？

解法三板斧

  1. 拆分队列（按类型/优先级分成多个队列，互不影响）
  2. 多路复用（让独立的流互不阻塞）
  3. 超时 + 丢弃（不让慢的无限期占着位置）

一个贯穿全书的”识别模式”

队头阻塞的本质，其实是第 6 章 Amdahl 定律的一个特例：一个”串行的环节”卡住了整体。 无论你后面的部分并行度多高、多快，只要前面有一个必须串行、而且慢的环节，整体就被它卡死。

这提醒你一个通用的排查思维：当你发现系统”资源没跑满但就是慢”，别只盯着那些”跑满”的部分，去看看是不是有个”串行的、被堵住的”环节在拖后腿。 队头阻塞、锁竞争、全局锁、单点协调，全都是”串行环节卡整体”这个模式的不同面孔。

子主题五：拥塞控制——排队在网络的形态

排队问题在网络里有个专门的名字和一套专门的解法：拥塞控制（Congestion Control）。

问题背景

网络中间的路由器/交换机也有队列。如果发送方发得太快，中间设备的队列会满，然后丢包——而丢包导致重传，重传又加剧拥塞，最终网络”拥塞崩溃”（congestion collapse）：吞吐量反而降到接近零。

这是 1986 年互联网真实发生过的灾难（吞吐量从 32 Kbps 掉到 40 bps，掉了一千倍）。

TCP 的解法：拥塞控制算法

核心思想极其优雅：

把网络当成一个”黑盒”，通过”探测”来推断它有多拥挤。

TCP 的两个核心机制：

1. 慢启动（Slow Start）

  • 刚建立连接时，拥塞窗口（cwnd）很小，每收到一个 ACK 就翻倍
  • 指数增长，快速探测可用带宽
  • 一旦丢包（或超过阈值），转入拥塞避免

2. 拥塞避免（Congestion Avoidance）

  • 窗口改为线性增长（每个 RTT 加 1），小心翼翼地逼近极限

3. 丢包时：窗口减半（乘法减小）

  • 经典的 AIMD（Additive Increase, Multiplicative Decrease，加性增、乘性减）

AIMD 的精妙之处

它让所有 TCP 连接在没有中心协调的情况下，自发地收敛到”公平分享带宽”的状态。这是分布式系统里”自组织”最优雅的例子之一——没有任何中央调度器，靠简单的局部规则达成全局的公平和效率。

一个帮助你理解 AIMD 的类比：一条共享的窄路

想象一条小路，很多人同时往里挤。每个人都想快点过：

  • 加性增：每个人一点一点地加快脚步（谨慎地试探路况）。
  • 乘性减：一旦撞车（丢包/拥堵），每个人立刻把速度砍半（快速退让）。

结果是什么？ 不需要任何人指挥，大家会自动收敛到”都能以相近速度通过”的状态——因为跑太快的会被”撞车”逼着减速，跑太慢的会一点点追上来。这就是”加性增、乘性减”在宏观上涌现出的公平。

现代演进：BBR

  • BBR（Google）：不再以”丢包”为拥塞信号（因为现代网络有深缓冲区，丢包发生得太晚），而是主动测量 RTT 和带宽，建立网络模型。这是从”事后反应”到”主动建模”的思路转变。

拥塞控制给我们的通用启示

  1. “探测 + 反馈”是应对未知容量的通用手段（对应第 13 章的自适应限流）
  2. 在资源未知时，“指数增长探测 + 快速退让”是最优策略
  3. 把”崩溃”作为反馈信号太晚了——应该主动建模（BBR 的思路）

一个深刻的”突破口”复盘（第 28 章会展开）

TCP 拥塞控制是本书最精彩的”突破口”案例之一。当时的难题是：发送方不知道网络有多拥挤，而”必须知道容量才能控制发送速率”。

Van Jacobson 的突破在于重新定义了问题：他把”如何在不知道容量的情况下控制速率”——答案不是”去知道”，而是”去探测”。

这个”用探测替代预知”的思想，后来成了整个分布式系统领域的基本功：限流、弹性伸缩、负载均衡、熔断，全都是”不知道真实容量，那就探测 + 反馈”。这也是第 13 章、第 24 章反复出现的主题。

演进脉络

把调度与排队的演进串起来，你会看到一条”从简单到多维，再到自适应”的主线。

  • 1909：Erlang 创立排队论（最初用于电话交换机的容量设计）。这是”排队”第一次被数学化——在此之前，“要多少条电话线”靠拍脑袋。
  • 1950s-60s：排队论在运筹学和计算机领域发展；操作系统调度算法（多级反馈队列）成熟。
  • 1986：互联网发生第一次拥塞崩溃。这次事故暴露了”排队在网络里”的致命性——所有人都发得很快，结果谁的数据都过不去。
  • 1988：Van Jacobson 提出 TCP 的慢启动和拥塞避免，拯救了互联网。
  • 1990s-2000s：公平队列（WFQ）、加权调度在 QoS 领域成熟。
  • 2010s：BBR 拥塞控制算法（Google, 2016）；HTTP/2 多路复用解决应用层队头阻塞。
  • 现代：QUIC/HTTP/3 解决传输层队头阻塞；Kubernetes 的资源调度（requests/limits + QoS）；自适应并发控制（根据延迟反馈动态调整并发数）。

主线：调度与排队的演进，是从”简单的先来后到”走向”多维度权衡”（优先级、公平性、效率），再走向”自适应”（根据实时反馈动态调整）。

而贯穿始终的核心认知是那条非线性曲线：系统利用率越高，排队延迟增长越快——所以”留有余量”不是浪费，而是对非线性世界的必要敬畏。

一个值得记住的”统一视角”

这一章讲了看似不同的四件事：操作系统调度、HTTP 队头阻塞、TCP 拥塞控制、Kubernetes 资源调度。但它们的底层是同一个问题：

当”想要资源的人”比”资源”多时，谁先来？怎么排？排多久？

无论是进程抢 CPU、请求抢连接、数据包抢带宽、Pod 抢节点，本质都是”稀缺资源的分配”。而”分配稀缺资源”这个问题的解法，永远是那三个目标的权衡：效率、公平、优先级。 认清这一点，你就不会被”调度”、“排队”、“拥塞控制”这些不同的名词吓住——它们是同一个问题的不同面孔。

本章思考题

【思考题】

  1. 排队论里”利用率 vs 延迟”的非线性关系说明了什么？为什么生产系统通常只跑到 50-70% 利用率？

  2. 为什么说”消除长尾”比”降低平均延迟”更重要？请用排队的视角解释。

  3. 什么是队头阻塞？请举出至少三个它在不同层次的表现形态，以及对应的解法。队头阻塞的本质是什么？

  4. 调度策略里，“最短作业优先”理论上平均等待时间最优，但有什么问题？优先级调度又有什么问题，怎么缓解？这些策略本质是在哪三个目标之间权衡？

  5. TCP 的 AIMD（加性增、乘性减）为什么精妙？BBR 相比传统拥塞控制的思路转变是什么？

【参考答案】

  1. 延迟 ≈ (利用率/(1-利用率)) × 服务时间，利用率越高延迟非线性暴涨：50%→1×，90%→9×，95%→19×，99%→99×。物理直觉：越忙越没有余力消化波动，波动越容易滚雪球。含义：系统的”安全容量”远低于”理论容量”，跑满(100%)意味着延迟无穷大、排队无限增长且难以恢复。所以生产只跑 50-70%，不是浪费，而是给突发流量留缓冲。另外排队的元凶是”波动”而非”平均”，平均能力大于平均需求并不能避免排队。

  2. 因为一个慢请求（耗时是正常的 100 倍）会占着资源 100 倍时间，把后面的请求全堵住——等于”队伍最前面的人突然不走”，后面所有人不管多快都被堵住。它造成的排队会波及所有后续请求，所以”偶尔出现的、占资源很久的慢请求”远比”平均慢”致命。这也是队头阻塞和 Amdahl 定律的共同点：一个串行的慢环节卡住整体。

  3. 队头阻塞：一个慢的堵住后面所有快的，导致整体性能崩塌。形态一：单队列任务调度（5 秒导出堵住 500 个 10ms 查询，解法：按类型分多队列）。形态二：HTTP/1.1 连接复用（请求必须按序返回，解法：HTTP/2 多路复用）。形态三：TCP 字节流严格有序（第 3 个包丢了后面到了也读不到，解法：QUIC 在 UDP 上做每流独立多路复用）。形态四：数据库锁等待（长事务堵住后续）。形态五：消息队列单分区（慢消息堵住同分区）。本质：第 6 章 Amdahl 定律的特例——一个”串行环节”卡住整体，无论后面并行度多高多快。通用解法：拆分队列、多路复用、超时+丢弃。排查思维：资源没跑满但慢时，去找”串行的、被堵住的”环节。

  4. 最短作业优先(SJF)理论平均等待时间最优，但问题：需要预知任务耗时（只能靠历史估计）、长作业会饥饿。优先级调度问题：低优先级任务可能永远排不上（饥饿），解法是”老化(Aging)“——等待时间越长优先级自动提升。本质权衡：效率（SJF 最优）、公平（轮转/WFQ 最优）、优先级（优先级调度最优）——三者无法同时最优，所以真实系统用”混合策略”（如操作系统的多级反馈队列 = 优先级+轮转+老化），通过调参在三者间找平衡。

  5. AIMD 精妙在：所有 TCP 连接在没有中央协调的情况下，靠”加性增（线性试探）、乘性减（丢包时窗口减半）“这一简单局部规则，自发收敛到”公平分享带宽”的全局状态——是分布式自组织最优雅的例子（类比共享窄路：跑太快的被撞车逼着减速，跑慢的一点点追上来）。BBR 的思路转变：传统算法以”丢包”为拥塞信号（事后反应，而现代网络有深缓冲区，丢包发生得太晚，缓冲已排满），BBR 改为主动测量 RTT 和带宽、建立网络模型（主动建模），从”事后反应”转向”主动预测”。通用启示：“探测+反馈”是应对未知容量的通用手段；“崩溃”作为反馈太晚，应主动建模。

反向链接