本文属于《后端系统工程：从接口契约到故障恢复》系列。文中提到的演练工程、测试与实验证据位于博客源码仓库的 batch-4/ 目录（examples/、evidence/ 等子目录）；业务数据均为合成数据。

多租户共享一组工作者时，“公平”常常被说成一个直觉：大租户不能把小租户挤死。要比较方案，就得把直觉换成可以计算的指标：每个租户应得多少，实际得到多少，偏离多少算不公平，小租户的延迟是否受大租户突发的影响，空闲容量会不会因为限额而白白浪费。

本篇先给出这些指标的定义，再在同一份不均匀的合成租户流量上比较四种准入与调度方案：全局先进先出、每租户令牌桶配额、赤字轮询（DRR），以及 DRR 加配额。仿真只用于比较调度算法，不代表任何真实服务的容量。

1. 场景与规模假设

项 值
工作者 8 个，任务服务时间服从均值 10 毫秒的指数分布，理论容量约 800 个/秒
heavy 租户 平时 400 个/秒；20–40 秒突发为 5 倍，即 2000 个/秒
mid0–mid3 各 60 个/秒
small00–small19 各 5 个/秒
运行时长 60 秒，统计窗口为突发期 20–40 秒
随机种子 1、2、3

平时总需求约 740 个/秒，略低于容量；突发期总需求约 2340 个/秒，约为容量的 3 倍。24 个中小租户的需求合计 340 个/秒，在任何公平划分下都应当被完全满足。

需要成立的性质写成可检查的形式：

  • F1 需求不超过公平份额的租户，完成速率不低于需求的 97%（留出抽样波动）。
  • F2 这些租户在突发窗口内的 p99 排队时间低于 50 毫秒，并且没有任务因队列满被拒绝。
  • F3 过载产生的拒绝只落在超出公平份额的租户上。
  • F4 只有一个租户活跃时，它能使用全部容量（工作保持）。
  • F5 租户维度的指标基数有上界，不随租户数增长。

F1 与 F2 的阈值是教学设定，表达的是“份额内的租户感觉不到别人的突发”；它们对应 test_drr_isolates_under_share_tenants 中的断言，同一组断言在 fifo 上必然失败，在 test_fifo_lets_heavy_starve_small 中作为负向对照固定下来。

2. 指标定义

公平份额： 突发窗口内，租户 i 的需求 d_i 为到达任务数除以窗口长度，容量 C 按窗口内实测的平均服务时间折算。公平份额 f_i 取加权 max-min 公平分配（注水法）：需求不超过均分份额的租户拿到全部需求，剩余容量在其余租户之间按权重继续均分，直到分完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def max_min_fair(demands, capacity, weights=None):
    weights = weights or {k: 1.0 for k in demands}
    alloc = {k: 0.0 for k in demands}
    left, cap = dict(demands), capacity
    while left and cap > 1e-12:
        wsum = sum(weights[k] for k in left)
        share = {k: cap * weights[k] / wsum for k in left}
        sat = [k for k in left if left[k] <= share[k]]
        if not sat:
            for k in left:
                alloc[k] += share[k]
            break
        for k in sat:
            alloc[k] += left[k]; cap -= left[k]; del left[k]
    return alloc

本场景中，中小租户的公平份额等于各自需求，heavy 的公平份额是剩余的约 460 个/秒，而不是它要求的 2000 个/秒。

归一化吞吐与 Jain 指数： x_i = 实际完成速率 / f_i。Jain、Chiu、Hawe 在 1984 年的报告中提出的公平指数 J = (Σx_i)² / (n·Σx_i²)，论文摘要说明它总是落在 0 与 1 之间；按公式，所有 x_i 相等时取 1，只有一个租户得到资源时取 1/n。这里对窗口内有需求的 25 个租户计算。

最小归一化份额： min x_i，表示最吃亏的租户拿到了自己份额的多少。Jain 指数对单个租户的严重受损不敏感，所以两个指标同时报告。

份额内租户的 p99 排队时间： 需求被公平份额完全覆盖的租户（本场景的 24 个中小租户），在突发窗口内的 p99 排队时间。这些租户没有超额，理应不受影响，这个指标直接衡量隔离程度。

工作保持： 只有 heavy 一个租户、需求约 1000 个/秒时，它能拿到多少吞吐。空闲容量能被唯一的活跃租户用掉，调度就是工作保持的；被限额挡住而闲置，就不是。

3. 四种方案

方案 准入 排队 参数
fifo 全局队列满即拒绝 全局先进先出 队列上限 2000
quota 每租户令牌桶，超额拒绝 全局先进先出 heavy 450/秒、mid 120/秒、small 20/秒，各自带突发额度
drr 每租户队列满即拒绝 赤字轮询，按任务成本计费 每租户队列 200，量子 10 毫秒，权重相同
drr_quota 令牌桶 + 每租户队列 赤字轮询 同上两者

DRR 由 Shreedhar 与 Varghese 提出，论文摘要称它在吞吐上接近完全公平，处理每个包只需 O(1) 的工作量，而此前的近似完全公平方案需要 O(log n)。机制是：每一轮给每个活跃队列一个量子的额度，上一轮没用完的余额累加到下一轮；队首任务的成本不超过额度时出队并扣减。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def take(self):
    while self.active:
        name = self.active[0]
        q = self.qs[name]
        if self._fresh:
            self.deficit[name] += self.quantum * self.w.get(name, 1.0)
            self._fresh = False
        if q and q[0].cost <= self.deficit[name]:
            t = q.popleft()
            self.deficit[name] -= t.cost
            if not q:
                self.active.popleft(); self.deficit[name] = 0.0; self._fresh = True
            return t
        self.active.rotate(-1)          # 额度不足：移到队尾，额度保留到下一轮
        self._fresh = True
    return None

“按成本计费”在这里意味着任务的服务时间在出队前已知。仿真在任务到达时抽样服务时间，等于假设调度器拿到了准确的成本估计。真实系统通常只能估计，或者在任务完成后再结算。

---
title: 图 E06-1 drr_quota 方案中一个任务的准入与调度路径
---
flowchart LR
    A[任务到达: 租户 t] --> B{租户 t 的令牌桶有令牌?}
    B -- 否 --> R1[拒绝: quota]
    B -- 是 --> C{租户 t 的队列 < 200?}
    C -- 否 --> R2[拒绝: queue]
    C -- 是 --> Q[进入租户 t 的队列]
    Q --> D[赤字轮询: 每轮 +量子×权重]
    D --> W[空闲工作者执行]

4. 实验结果

运行入口 examples/e06_fairness/：python3 -m unittest test_fairness -v，9 个用例通过；python3 report.py 生成三个种子的结果（evidence/E06/results.md）。种子 1 的结果：

方案 Jain 指数 最小归一化份额 份额内租户 p99 排队 heavy 吞吐（个/秒） 全程利用率
fifo 0.757 0.264 2601.6 毫秒 684.5 0.990
quota 1.000 0.972 138.4 毫秒 453.7 0.944
drr 1.000 0.989 19.5 毫秒 468.1 0.953
drr_quota 1.000 0.971 18.6 毫秒 452.7 0.944

三个种子的区间：fifo 的 Jain 指数 0.736–0.757，份额内 p99 排队 2602–2669 毫秒；quota 的份额内 p99 排队 138–286 毫秒；drr 为 19–22 毫秒。

单租户工作保持对照（只有 heavy，需求约 1001 个/秒）：

方案 heavy 吞吐 全程利用率
fifo 790.5 0.704
quota 454.6 0.522
drr 792.4 0.667

4.1 FIFO：大租户把队列占满

突发期间 heavy 的到达是其余租户总和的 6 倍，全局队列很快被它的任务填满。小租户的任务要么排在约 2.6 秒的队尾，要么在队列满时被拒绝：最吃亏的小租户只拿到需求的 26%。fifo 的全程利用率最高（0.99），说明它没有浪费容量，但容量几乎都给了超额的那个租户。利用率高不代表分配合理。

4.2 配额：保护了小租户，代价有两处

quota 在突发期间把 heavy 限制在 450 个/秒附近，中小租户的需求基本被满足，Jain 指数接近 1。但它仍然有两个问题。第一，份额内租户的 p99 排队仍有 138–286 毫秒，是 DRR 的 7 到 13 倍：配额只限制了速率，所有租户仍在同一个 FIFO 队列里，heavy 在配额之内的任务依然排在小租户前面。第二，单租户对照中，heavy 只拿到 454.6 个/秒，而容量约 800 个/秒，近一半的容量在没有任何其他租户需要时被闲置。

quota 的 Jain 指数和 drr 一样接近 1。Jain 指数衡量的是给定容量下各租户的相对份额，它既看不到排队延迟，也看不到浪费的容量。只报告一个公平指数会把 quota 和 drr 判为等价，而它们对小租户延迟和资源利用的影响相差很大。

4.3 DRR：隔离且工作保持

drr 的份额内租户 p99 排队约 20 毫秒，24 个中小租户的完成速率都不低于需求的 98.9%（三个种子中的最低值为 97.9%），没有一个小租户的任务被拒绝；被拒绝的全部是 heavy 的超额任务（它自己的队列满了）。单租户对照中 heavy 拿到 792.4 个/秒，与 FIFO 相当，说明空闲容量没有被浪费。过载的代价只落在超额的租户身上：heavy 自己的 p99 排队约 0.5 秒，它的超额请求被拒绝。

4.4 DRR 加配额

drr_quota 与 drr 的隔离效果相同，区别在于 heavy 的超额任务在令牌桶处就被拒绝，而不是进入它的队列后再因队列满被拒绝。配额在这里的作用不再是保护其他租户，而是表达合同上的上限：某个租户即使在系统空闲时也不应超过某个速率，例如按套餐计费。它与公平调度解决的是两个不同的问题，应当分开配置、分开解释拒绝原因。

5. 参数怎样选择

DRR 有三个参数：每租户队列上限、量子和权重。

  • 量子不应小于单个任务的典型成本。量子小于任务成本时，一个租户要累积几轮额度才能出队一个任务，轮询会空转。每个租户每轮至少能出队一个任务，是轮询开销保持常数的前提。本实验的量子取 10 毫秒，等于平均服务时间；指数分布的长尾任务需要两到三轮额度，这部分空转在实验中没有单独测量。
  • 每租户队列上限决定超额租户自己的排队时间。heavy 的队列为 200，它在窗口内分到约 460 个/秒，满队列的等待约 0.43 秒，与实测 p99 约 0.52–0.57 秒同一量级。队列越长，超额租户的成功率越高、延迟越长；队列上限乘以单任务成本，再除以该租户的公平份额，应当小于调用方的截止时间（与第 37 篇的约束相同）。
  • 权重来自合同或优先级，而不是来自流量大小。按流量设定权重等于把 FIFO 的行为重新引入：流量越大，权重越大，份额也越大。

令牌桶配额的速率与突发额度应当按套餐或合同设定，并在系统扩容时保持不变，否则配额就成了容量的另一种表达，每次扩容都要同步修改。

6. 租户维度的观测

公平性问题的诊断需要按租户拆分的指标：到达数、准入数、按原因分开的拒绝数（配额、队列满）、队列深度、排队时间分位数。租户数量一大，“每个租户一组时间序列”会让指标基数随租户数线性增长。

TenantMetrics 每个周期只为请求量最大的 K 个租户保留独立标签，其余并入 __other__；被并入的租户如果发生拒绝，把租户名记入一个有界的样例列表，便于排查。测试中 1000 个租户、K=10 时，输出不超过 11 条序列，样例不超过 5 个，聚合前后的请求总数相等。

这个做法的盲点是：一个请求量不大、但被拒绝比例很高的小租户，会被埋进 __other__。样例列表只能保证“有人注意到”，不能给出它的历史曲线。需要逐租户审计时，应当把按租户的计数写入日志或明细存储，而不是放进时序指标。

把第 2 节的指标搬到线上时，计算方式要做两处调整。第一，公平份额依赖每个租户的需求，而线上能直接观测的是“到达”，被客户端限流或因为排队太久主动放弃的请求不会出现在到达里，需求会被低估；拒绝之后的重试又会让需求被高估。线上的需求估计应当同时记录到达、拒绝与重试标记。第二，Jain 指数与最小归一化份额都应当按固定窗口（例如一分钟）滚动计算，并只对窗口内有需求的租户计算，否则长期空闲的租户会把指数拉向 1，掩盖窗口内的不公平。份额内租户的 p99 排队时间最适合作为告警指标：它直接对应“小租户被大租户拖慢”这一用户可感知的问题，阈值也能从服务目标推出。

7. 方案比较与其他做法

方案 隔离（份额内延迟） 工作保持 过载代价落在谁身上 额外成本
全局 FIFO 差 是 所有租户 无
每租户配额 + FIFO 部分 否 超额租户，但份额内租户仍排在其后 配额要随容量调整
每租户队列 + DRR 好 是 超额租户 每租户一个队列；需要成本估计
DRR + 配额 好 否（被配额限制的部分） 超额租户 两套参数

两个相关的设计没有实现，但值得对照：

  • Kubernetes 的 API Priority and Fairness 把请求按 FlowSchema 与“流区分符”（请求用户、目标命名空间或不区分）划分为流，用洗牌分片把流分配到队列。文档说明洗牌分片能以较少的队列把低强度流与高强度流隔离开；handSize 越大，两个流完全撞在一起的可能越小，但少数流占据服务器的可能越大。它用“席位”作为并发单位，大的 LIST 请求占多个席位，这与本文的“按成本计费”是同一类考虑。租户数达到数万时，每租户一个队列的开销会变大，洗牌分片就是为这种情况设计的。
  • Dominant Resource Fairness（Ghodsi 等，NSDI 2011）处理多种资源：用户的主导份额是它在各类资源中占比最大的那一项，DRF 最大化最小的主导份额；只有一种资源时，DRF 退化为 max-min 公平。本文只有“工作者时间”一种资源，所以 max-min 就够了；任务同时消耗 CPU、内存和下游配额时，需要 DRF 这样的定义。

8. 限制

  • 任务成本在到达时已知且准确；真实系统中的成本估计误差会削弱 DRR 的公平性，本实验没有测量这种影响。
  • 只有一种资源、权重全部相等；加权公平只做了单元测试（2:1 权重下的服务比例为 2.0±0.02）。
  • 没有模拟租户的客户端重试。被拒绝的超额任务在现实中会被重试，形成额外的到达（参见第 37 篇）。
  • 公平份额按突发窗口内的平均需求计算，没有考虑窗口内需求的时间变化；一个只在窗口前 2 秒集中到达的租户，按平均值看是份额内租户，实际上在那 2 秒里是超额租户。更细的时间窗口会改变“份额内”的划分，从而改变 F1、F2 的统计对象。
  • 拒绝是瞬时的，没有 Retry-After，也没有把拒绝原因反馈给租户。
  • Demers、Keshav、Shenker 1989 年的公平队列论文只核对了书目信息，正文中没有引用其具体论断。

9. 来源

核对日期 2026-10-18。

  • Jain, Chiu, Hawe，A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems，DEC TR-301（1984），arXiv cs/9809099：摘要称公平指数总在 0 与 1 之间。公式从扫描版无法逐字核对，正文按通行定义给出。
  • Shreedhar, Varghese，Efficient Fair Queuing using Deficit Round Robin，SIGCOMM '95，DOI 10.1145/217382.217453：O(1) 每包工作量、余额结转到下一轮、计数器初始化为 0。
  • Demers, Keshav, Shenker，Analysis and Simulation of a Fair Queueing Algorithm，SIGCOMM '89，DOI 10.1145/75246.75248（仅书目）。
  • Kubernetes 文档 API Priority and Fairness（v1.29 起稳定）：流区分符、洗牌分片、席位、handSize 的取舍。https://kubernetes.io/docs/concepts/cluster-administration/flow-control/
  • Ghodsi 等，Dominant Resource Fairness，NSDI 2011：主导份额定义；单资源时退化为 max-min 公平。

本批导航