Quincy — 把"派活给机器"变成一道最小费用流题

是什么

Quincy 是一套集群任务调度算法，第一次把”该把这个任务派给哪台机器”建模成一个最小费用流问题。日常类比：你在排座位——既要让客人坐他熟人旁边（数据本地性），又要保证每桌人数差不多（公平），同时不让等位的人等太久。Quincy 的做法是画一张图，把所有约束写成边的权重，然后让图论算法替你算出最优座位表。

它出自 Microsoft Research 2009 年 SOSP，作者里 Andrew Goldberg 是最小费用流领域的大佬，论文用的就是他自己写的求解器。

为什么重要

不理解 Quincy，下面这些事都没法解释：

为什么 YARN / Hadoop 的 Capacity Scheduler / Fair Scheduler 写了一堆贪心规则，但算不出最优解——因为它们是 heuristic，Quincy 是数学最优
为什么 2016 年 OSDI 又出了一篇 Firmament，号称”亚秒级调度 12500 台机器”——它就是 Quincy 的工业化重写
为什么 Kubernetes 的 scheduler-plugins 框架敢说”多目标加权”是合理的——背后思想可追溯到 Quincy
一切”在 N 个候选位置里挑最优”的问题，都能试试这条建图思路

核心要点

Quincy 的三步走：

画图：每个待调度的任务是一个源节点，每台机器、每个机架、整个集群各是一个中转节点，最后汇到汇点。
标边权：每条边代表一个选项，边的”代价”同时编码三件事——数据离机器多远（本地性）、任务等了多久（饥饿）、要不要踢掉别人才能跑（抢占代价）。
解流：跑一次最小费用流算法，得出的”流量分配”就是”哪个任务派给哪台机器”。

这一步不是贪心，它是全局最优——只要图建对，结果就是数学上代价最小的方案。

类比：导航 App 的”全局最优路线”。Quincy 不是边走边挑下一个路口，它是摊开整张地图一次性算完。

实践案例

案例 1：图长什么样

简化的 Quincy 图（只画一个任务的视角）：

任务 T → 它的数据在 m1 上 → m1（机器节点，代价 0）
任务 T → 数据在 m1 同机架 m2 → m2（代价 1，跨机器但不跨机架）
任务 T → 跨机架 m3 → m3（代价 2，跨机架）
任务 T → 集群聚合点 X → 任意机器（代价 3，最差选项）

每条边的代价数字代表”如果走这条边，付出多少额外开销”。求解器算出来的最小费用流，会自动倾向把任务推到代价低的机器，但当低代价机器被占满时，它会智能地选次优。

为什么是费用流而不是普通最大流？ 普通最大流只问”最多能塞多少任务”，不管塞到哪。Quincy 想问的是”最多能塞多少 + 总代价最小”，这就需要给每条边加一个”单位流量代价”，然后让算法在多种”塞法”里挑总代价最小那种。这正是最小费用流的定义。

案例 2：公平性怎么编码

Quincy 不是用”轮询”做公平，而是给每个用户一条”配额边”——这条边的容量就是他能用的机器数上限。

用户 A 的所有任务 → A 的配额节点（容量 = 50 台机器） → 集群
用户 B 的所有任务 → B 的配额节点（容量 = 30 台机器） → 集群

容量上限由图论算法强制，不是 if-else 检查。这就是为什么 Quincy 能给”公平”一个数学保证而不是一句”我们会努力”。

案例 3：和 YARN Capacity Scheduler 的差距

维度	YARN Capacity	Quincy
决策方式	一台机器一台机器贪心匹配	整张图一次性求最优
公平	队列容量上限（硬规则）	边容量约束（数学保证）
本地性	三级 fallback（节点/机架/任意）但贪心	编码成边权，全局优化
速度	毫秒级	秒级（Quincy 的痛点）

YARN 选了”够快但不一定优”，Quincy 选了”最优但慢”。Firmament 后来证明两者可兼得——但思想还是 Quincy 的。

案例 4：抢占代价怎么算

Quincy 不会无脑抢占。它在图里给”已经在 m1 上跑的任务 T1”加一条特殊边——回到自己当前机器的代价是 0，但被替换需要重启的代价是 P（P 取决于已经跑了多久）。

求解器在算最小费用流时，会自然地比较”踢掉 T1 来跑 T2 的本地性收益”和”T1 重启的浪费”。如果踢的代价 > 收益，算法不会动 T1。这就是全局视角的妙处——贪心调度器很难做到这种”想三步看四步”。

踩过的坑

图越大解越慢：1000 台机器以上 Quincy 就开始卡。论文里 240 机器还行，工业级要等 Firmament 用增量求解器才修好。
代价函数是手工调的：边权（“跨机架代价 = 2”）凭直觉拍脑袋，没有原则性推导方法。换工作负载就要重调。
全局最优 ≠ 在线最优：每来一个新任务就重新解一次图，可能导致已经在跑的任务被抢占重排。抖动比贪心调度器大。
公平 ≠ max-min fair：Quincy 的”公平”是”容量上限 + 优先级”，不是 DRF（Dominant Resource Fairness）那种多维资源公平。GPU 场景需要扩展。
求解器是黑盒：你能看到结果，但很难解释”为什么这个任务被派到了 m17 而不是 m9”。运维排障时这点很折磨。

适用 vs 不适用场景

适用：

中小规模集群离线批处理（< 1000 机器，秒级调度延迟可接受）
Dryad / MapReduce / Spark shuffle 这种数据本地性强的负载
多目标加权资源分配的建模思路（不限于任务调度，也可建模成”派单”）

不适用：

毫秒级在线服务调度 → 用 Borg / Omega 这类工业方案
GPU 训练（需要 gang scheduling 一起起多卡）→ Quincy 没原生支持
强 SLA 场景 → 抢占抖动太大，要加入”切换代价” 才能稳

历史小故事（可跳过）

2009 年：Microsoft Research 在 Dryad 引擎里发现，已有的”FIFO + 贪心”调度器在多用户环境下既不公平也不本地。Isard 等人想：能不能给这个问题一个数学定义？
想到最小费用流：Andrew Goldberg 是 push-relabel 算法的发明者之一，团队里有这块专家。把调度建成图这个跳跃，是 Quincy 最大的贡献。
2016 年 OSDI：剑桥的 Ionel Gog 团队发表 Firmament，号称把 Quincy 的求解器升级到亚秒级，能跑 12500 机器。Quincy 的思想终于变成工业可用。

学到什么

多目标问题别急着写规则——先想能不能建模成图论 / 优化问题，让数学帮你算
代价函数 = 你对世界的表态——你愿意为本地性付多少？为公平付多少？写成数字就吵不起来
全局最优 vs 增量响应有内在张力——Quincy 选了前者，Firmament 用增量求解兼顾
理论 → 工程还是要等 7 年（2009 → 2016）。第一篇论文很少能直接落地，但思想会传承
图论是程序员的瑞士军刀：很多看起来不像图的问题（任务派单、座位排布、广告投放）建图后都能用流 / 匹配 / 最短路解掉

给零基础读者的复习路径

如果你想真的看懂 Quincy 的图算法部分，建议这个顺序：

先理解最大流（max-flow）：用一根水管子的比喻，从源头到终点最多能流多少水
再加上容量和割（min-cut）：知道最大流 = 最小割定理
然后看最小费用流：每条边除了容量还有”单位流量代价”，问总代价最小的最大流
最后看 Quincy 怎么把”调度”翻译成这张图——重点不在算法，在建模翻译那一层

关联

borg —— 工业级调度对照组，Borg 走的是 heuristic + 优先级路线
borg-omega-kube-2016 —— 把 Borg / Omega / K8s 调度演进串起来，Quincy 是其理论分支
mapreduce —— Quincy 在 Dryad 上验证，Dryad 是 MapReduce 的同代表亲

一句话记住

Quincy 的核心不是”用了什么图算法”，而是先把问题翻译成图这件事——只要你能把”做选择”翻译成”在图里找最优流”，几十年的图论积累就立刻为你打工。

这种建模能力比记住任何具体算法都更长久。下次你看到”在 N 个候选里挑最优”的问题（派单、排课、广告竞价、推荐召回），不妨先问自己一句：能不能画成一张图？

反向链接

borg —— Borg — Google 把一万台机器假装成一台
mapreduce —— MapReduce — 用户只写两个函数，框架替你扛千节点
omega-2013 —— Omega 2013 — 让多个调度器同时改一份 cluster 状态