鲁班 - 系统设计大全

12.5 公平调度算法 (MMF / DRF)

一句话

公平不是 “平均分”，而是 “每个用户的主导航资源份额尽量相等”：MMF 按最稀缺的那一维分配，DRF 把多维资源压成 “主导份额（dominant share）”再比较——这样 “只要 1 核但吃 8G 内存” 与 “要 8 核但只吃 1G” 的任务才可比。

三种分配策略

策略 规则 问题
FIFO 先到先得，整块满足 大任务堵住后来者，短任务饿死
均分（Equal share） 每个用户 1/N 忽略 “任务形状不同”，形状不匹配时浪费严重
MMF（最大最小公平） 先满足最小需求，再逐步抬高 单资源维度公平，多维需扩展
DRF（主导资源公平） 按 max(cpu份额, mem份额) 排序，份额小者优先 需要知道每个用户的总份额

DRF 是 MMF 在多维资源上的推广：把 “用户 u 已占用的资源向量” 归一化成 “主导份额” d(u)=max(r_i/cap_i)，每次把资源给 d(u) 最小的用户。

实测：FIFO 与 DRF 在同一负载下的差别

双资源（16 核 / 16G），4 个用户形状不同的任务（A:1核4G、B:4核1G、C/D:1核1G），连续提交 400 个：

策略 成功服务任务数 主导份额（A/B/C/D）
FIFO 10 0.50 / 0.50 / 0.19 / 0.19
DRF 13 0.25 / 0.25 / 0.38 / 0.31

两个结论：① DRF 在同一资源池里多服务了 30% 的任务（13 vs 10）；② 它把 A、B 的份额从 0.5 压到 0.25，让 C、D 也有机会——这就是 “按主导份额排序” 的直接效果。

# DRF 选择：主导份额最小的用户优先
cand = [(max((used[u][0]+c)/CAP[0], (used[u][1]+m)/CAP[1]), u)
        for u, (c, m) in shapes.items() if fits(u, c, m)]
u = min(cand)[1]          # 份额最小者获得本次资源

反模式

反模式 后果
用 “平均分 CPU” 做多租户公平 内存型任务把节点 OOM，CPU 却空闲
只按提交顺序排队 大任务堵住队列，小任务延迟爆炸
不设 “最大份额上限” 单一用户可占满全池，公平失效
配额按 “团队” 而不是 “队列” 团队内部互相抢，外部看不到
忽略资源形状（只算总量） 碎片化：总量够但放不下
公平性不做监控 无法证明 “谁被饿死”

三条铁律

🔑 公平要按 “主导份额” 比，不按单维资源比。

🔑 公平与利用率是对偶的：越公平，装箱越碎、利用率可能越低。

🔑 配额必须有上限与借用规则，否则 “公平” 只是口号。

自检

Q1 DRF 的 “主导份额” 为什么能解决 “形状不同不可比” 的问题？

▸ 答案：因为它把 “绝对用量” 换成 “占全局容量的比例”：A 用 1 核 4G 在 16/16 的池子里主导份额是 0.25（内存），B 用 4 核 1G 也是 0.25（CPU）。两者虽然用量不同，但 “主导份额” 相等，就可以比较 “谁更该拿下一份资源”。

Q2 实测中 FIFO 只服务了 10 个任务，为什么这么少？

▸ 答案：因为 FIFO 按 “任务到达顺序 + 整块满足” 分配：A（1核4G）先来，连续占满内存维度后，B（4核1G）虽然 CPU 还够，但整块申请被 “内存不足” 挡住，于是后续任务全部排队。FIFO 的浪费来自 “不考虑形状”，不是容量不够。

Q3 DRF 会不会让 “小任务” 一直占优势？

▸ 答案：不会，因为份额是累计的：小任务拿得越多，主导份额越高，后续就越排在后面。DRF 保证的是 “长期份额趋近相等”，不是 “小任务优先”。但如果小任务数量极多，份额增长慢，仍可能出现 “大任务等待较久”——这需要 “最大等待时间/老化” 机制补充。

Q4 公平调度与 “优先级” 能共存吗？

▸ 答案：能，常见做法是 “先按优先级分层，层内按 DRF 公平”：高优先级队列先拿资源，层内再公平分配。代价是低优先级可能长期拿不到——所以要有 “配额保证/最小份额” 兜底，否则公平只是高优先级内部的公平。

Q5 为什么 “公平” 有时会降低利用率？

▸ 答案：因为公平要求 “每个用户都能拿到一份”，即使某些用户的任务形状会留下碎片；而 “贪心装箱” 可以把碎片填满。所以公平与利用率是一对权衡：单租户追求利用率，多租户追求公平 + 可预测。

Q6 多资源里 “归一化” 的基准该用总容量还是可用容量？

▸ 答案：用总容量（集群可分配总量）更稳定：可用容量随其他任务波动，会让 “份额” 抖动，导致调度决策反复。代价是 “集群扩容后份额需要重算”，这通常由配置中心/调度器周期刷新解决。

Q7 怎么验证 “公平真的生效了”？

▸ 答案：看三条曲线：每个用户的主导份额（应收敛）、最大与最小份额的比值（应接近 1）、每用户等待时间分布（不应有长期饥饿）。只看 “平均利用率” 看不出公平问题——平均可以很漂亮，而某个用户一直排不上。

关联