📊 statistics

Experimentation for Different Scheduling Policies on Queues: Mixed Differences-in-Q Estimators Based on Little's Law

本文提出了一种基于利特尔定律的混合差异 - 量（Differences-in-Q）估计量，旨在缓解数据中心调度策略 A/B 测试中的马尔可夫干扰，并通过大量仿真证明，与标准方法相比，该方法能显著降低偏差和方差。

原作者： Nanshan Jia, Ramesh Johari, Nian Si, Zeyu Zheng

发布于 2026-05-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Nanshan Jia, Ramesh Johari, Nian Si, Zeyu Zheng

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一家拥有数千个收银通道（服务器）的大型高科技超市，每秒都有源源不断的顾客（任务）涌入。店经理的目标是让队伍尽可能快速地流动。为此，他们使用一种“调度策略”——一套决定哪位顾客前往哪个通道的规则。

有时，经理希望尝试新规则（例如“将顾客派往人数最少的通道”），以验证其是否优于旧规则。为了测试这一点，他们会进行A/B 测试：随机将部分顾客分配到“新规则”通道，其余顾客分配到“旧规则”通道，然后比较平均等待时间。

问题：“涟漪效应”

该论文指出，由于存在所谓的马尔可夫干扰，简单的 A/B 测试在这些繁忙系统中往往失效。

可以这样理解：如果你将一位顾客派往特定通道，就会改变该通道的长度。这种改变不仅影响该位顾客，还会改变整个系统的状态，进而影响下一位顾客，以及再下一位顾客。

如果“新规则”使某条通道变短，下一位顾客可能更快得到服务，但这并非因为该规则本身更优，而是因为该通道暂时被清空了。
反之，如果“旧规则”导致某条通道拥堵，就会扰乱所有后续顾客的时序。

由于两组（新规则组与旧规则组）不断相互影响彼此的环境，简单比较等待时间会得出有偏的结果。这就像试图在两名跑步者互相绊倒对方脚的情况下判断他们的速度。

旧方案：“长记忆”方法

先前的研究者（Farias 等人）尝试通过一种称为Q 值差分（DQ）的方法来解决这一问题。
想象你要评估一名跑步者的表现，但你不是仅记录其当前一圈的时间，而是观察其表现对接下来 100 圈的影响。你将单次决策所引发的所有未来“奖励”（或惩罚）加总起来。

好消息：该方法能有效消除偏差，因为它考虑了涟漪效应。
坏消息：它极其嘈杂（高方差）。由于你加总了如此多的未来事件，单个随机波动就可能扰乱整个计算。这就像试图通过观察每一朵云来预测未来一年的天气：你获得了大量数据，但信号却被噪声淹没。

新方案：结合“利特尔定律”

本文作者提出了一种巧妙的创新方法，将两者的优势结合起来。他们运用了排队论中一个著名的原理——利特尔定律。

类比：
利特尔定律就像一架天平。它指出，在一个稳定系统中，以下三者紧密关联：

店内有多少人（队列长度）。
顾客到达的速度（到达率）。
他们停留的时间（响应时间）。

如果你知道其中两个，就能推算出第三个。作者意识到，“队列长度”和“响应时间”是同一枚硬币的两面，它们高度相关。

创新点：“混合”估计量
他们不再仅仅关注响应时间的“长记忆”（这很嘈杂），也不仅仅关注队列长度的“长记忆”（这也同样嘈杂），而是将两者混合起来。

想象一位厨师在品尝汤品：

仅品尝盐分（响应时间）可能会因为一粒随机的盐粒而显得过咸或过淡。
仅品尝胡椒（队列长度）可能会显得过辣。
但如果将两者按完美比例混合品尝，随机误差就会相互抵消，从而得到完美的风味。

作者通过数学计算得出混合这两种测量的“完美比例”（一个称为 $\alpha$ 的权重）。由此构建出一种混合 Q 值差分估计量。

结果

该论文在多种混乱条件下运行了数千次计算机模拟，以测试这一构想：

繁忙时段：当超市人满为患（高到达率）时。
慢速工人：当某些服务器比其他服务器更慢时（异构速率）。
混乱延迟：当信息在经理与服务器之间传输需要时间时（通信延迟）。
不可预测的顾客：当服务时间不平稳且不可预测时（非指数分布时间）。

结论：
在所有场景中，他们的新混合估计量均胜出。

低偏差：它准确识别了新策略的真实价值，忽略了那些误导简单测试的“涟漪效应”。
低方差：它比之前的“长记忆”方法更加稳定和可靠，不会在一次测试到下一次测试之间剧烈波动。

总结

该论文解决了在测试繁忙计算机系统中的新规则时遇到的棘手问题。通过认识到“队伍有多长”与“你等待多久”在数学上是相互关联的，他们创造了一种新的统计工具，将这两种视角混合起来。这一工具能够更清晰、更准确地判断新的调度策略是否真正有效，而不会被系统本身的混乱噪声所迷惑。

技术摘要：队列中不同调度策略的实验研究

问题陈述

在现代数据中心中，调度算法对于在服务器网络中分配工作负载以平衡响应时间和计算成本至关重要。在部署新的调度策略时，从业者通常依赖 A/B 测试来评估其实际影响。然而，排队系统中的标准 A/B 测试容易受到马尔可夫干扰（也称为跨期干扰）的影响。

在标准的随机化 A/B 测试中，任务被分配到处理组和对照组，系统状态（例如队列长度）会动态演变。应用于某一组的调度策略会影响服务器负载，进而影响另一组任务的响应时间和队列状态。这种干扰会导致“朴素”估计量（即简单比较组间平均结果的估计量）产生系统性偏差。具体而言，朴素估计量会低估处理效应，因为对照组中存在更高效的策略会人为地缩短处理组的队列，反之亦然。

虽然 Farias 等人 [2022] 提出的Q 值差分（DQ）估计量旨在通过累加未来奖励来估计 Q 值以减轻这种偏差，但这些估计量由于在长视界上累积噪声，往往遭受高方差的困扰。

方法论

1. 系统模型

作者将数据中心建模为具有 $N$ 台服务器的并行服务器排队网络（“超级市场模型”）。任务以泊松流形式到达，并根据负载均衡策略（例如 Power-of- $d$ ）路由到服务器。系统状态由队列长度向量定义。作者定义了两个主要性能指标：

响应时间（ $C_w$ ）： 任务在系统中花费的时间（等待 + 服务）。
队列长度（ $C_q$ ）： 系统中的平均任务数量。

目标是估计全局处理效应（GTE），定义为处理策略（例如 Power-of- $d_2$ ）与控制策略（例如 Power-of- $d_1$ ）之间长期平均性能的差异。

2. 理论基础：利特尔定律

核心理论贡献是将利特尔定律应用于估计框架。利特尔定律指出，在稳定系统中，长期平均队列长度等于到达率乘以平均响应时间。
作者证明，通过响应时间定义的 GTE（ $GTE_w$ ）等价于通过队列长度定义的 GTE（ $GTE_q$ ）乘以到达率 $\lambda$ 的缩放：
$GTE_w = GTE_q = \frac{C_{1,q}(\lambda) - C_{0,q}(\lambda)}{\lambda}$
这种等价性使得作者可以将队列长度和响应时间视为处理效应的可互换代理，前提是考虑了到达率。

3. 混合 Q 值差分估计量

为了解决标准 DQ 估计量的高方差问题，作者提出了一种混合 Q 值差分估计量。

标准 DQ： 通过在截断视界 $L$ 内对所有处理分配后跟随的未来任务的成本（响应时间或队列长度）差异求和来估计 GTE。
混合方法： 认识到基于队列长度的 Q 函数和基于响应时间的 Q 函数具有强相关性，作者采用控制变量技术。他们构建了一个混合 Q 函数：
$\hat{Q}^{\alpha, L}_{mix} = \alpha \hat{Q}^L_w + (1-\alpha) \frac{\hat{Q}^L_q}{\lambda}$
其中 $\alpha$ 是用于最小化混合估计量方差的最优权重。最优 $\alpha^*$ 基于各个估计量的方差和协方差解析推导得出。

该方法利用排队系统的结构特性（特别是利特尔定律）来降低方差，同时不牺牲原始 DQ 方法的偏差减少特性。

主要贡献

数据中心 A/B 测试框架： 本文在超级市场模型中建立了一个严格的 A/B 测试框架，明确捕捉了随机实验下替代调度策略的性能影响。
混合 Q 值差分估计量： 作者提出了一种新颖的估计量，推广了 Farias 等人 [2022] 的 DQ 估计量。通过利特尔定律结合队列长度和响应时间的 Q 函数，该方法在保持低偏差的同时实现了显著更低的方差。
广泛的模拟验证： 该研究在多样且具有挑战性的场景中验证了所提出的方法，包括：
- 异构服务率。
- 非平稳到达率（循环模式）。
- 调度器与服务器之间的通信延迟。
- 非指数服务时间（包括常数和重尾帕累托分布）。
- 与往返实验设计的比较。

结果

数值实验（在 $N=20$ 台服务器和不同到达率下进行）表明如下结果：

偏差减少： 由于干扰，朴素估计量表现出显著偏差（低估处理效应）。标准 DQ 估计量（基于队列长度和响应时间）以及混合 DQ 估计量均成功减少了这种偏差。
方差减少： 虽然标准 DQ 估计量减少了偏差，但它们通常表现出比朴素估计量大 50 至 500 倍的标准差。混合 DQ 估计量显著缓解了这一问题。在均匀设置中，与标准 DQ 估计量相比，它将标准差降低了 2 到 5 倍。
均方误差（MSE）： 在所有测试场景（均匀、异构、非平稳、延迟和非指数服务时间）中，混合 DQ 估计量在所有比较的估计量（朴素、分组、qDQ、wDQ 和往返）中始终实现最低的 MSE。
鲁棒性： 该方法即使在重尾服务时间和通信延迟下仍然有效。在非平稳设置中，即使到达率是周期性的（理论上有利于往返设计的设置），混合 DQ 估计量也优于往返设计。
截断敏感性： 关于截断长度 $L$ 的消融研究揭示了偏差 - 方差的权衡。作者发现 $L = 30N\lambda$ 提供了稳健的平衡，且即使 $L$ 较小，混合 DQ 估计量也比其对应方法收敛得更快。

意义与主张

本文主张，这项工作的主要意义在于证明融入领域知识——特别是排队系统的结构特性（如利特尔定律）——可以显著提高 A/B 测试中性能评估的可靠性。

作者认为，仅依赖严格假设下的理论分析不足以应对工业实践。相反，他们提出的混合 DQ 估计量提供了一种实用且易于实施的解决方案，在存在马尔可夫干扰的情况下显著降低了偏差和方差。这使得数据中心运营商能够在全面部署之前更准确地评估新调度算法的实际影响。

本文结论较为谦逊，指出虽然该方法是在超级市场模型上展示的，但它广泛适用于一般排队网络环境。未来的工作被确定为严格开发该估计量的推断程序，并将该框架扩展到复杂场景，如大型语言模型（LLM）推理。