读论文

问题

阅读系统论文时，先找出旧方法无法满足的约束，再检查新机制改善了哪些指标，以及代价落在哪里。

机制

第一遍可以只读 Title、Abstract、Introduction、Conclusion 和小节标题，回答 five C’s：Category、Context、Correctness、Contributions、Clarity，先判断论文解决的问题和主要贡献。

第二遍梳理 problem、motivation、design、evaluation、limitation，并沿架构图追踪请求流：请求从哪里进入、在哪个队列等待、调度器如何决策、瓶颈出现在哪里。

第三遍是假装自己要复现系统：沿着论文假设重新推导设计选择，挑战 workload、硬件和 SLO 变化后的结论，并整理“创新点 + 失败边界”。

ZygOS

问题

KV store、内存数据库和 leaf service 中，RPC 服务时间可到微秒级。系统目标不是单纯提高平均吞吐，而是在激进的 99th tail-latency SLO 下承受更高 load。fan-out/fan-in 会把单个 leaf 的尾延迟放大成整体请求的 tail-at-scale 问题。

机制

传统 single queue 理论上更 work-conserving：只要系统还有请求、还有空闲 worker，空闲 worker 就能拿到活，瞬时负载不均衡小。但 centralized queue 需要共享队列，同步开销高，放到微秒级 RPC 里会直接吃掉延迟预算。

dataplane 系统路径短、同步少、cache/coherence 开销低，但通常采用每核队列，可能 not work-conserving。某个 worker 的队列已经很忙时，另一个 worker 仍可能空闲。

ZygOS 的折中是保留 dataplane 风格的 share-nothing 网络处理，同时通过 work stealing 让空闲核从繁忙核偷 ready connection，逼近 single queue 行为。它的结构可以分成三层：

取舍

ZygOS 保留 dataplane 的低开销路径，再用 work stealing 补足 per-core queue 的 work conservation。Silo TPC-C 实验中，相比 Linux，吞吐约提升 1.63x，99 分位延迟约降低 3.68x。

Shinjuku

问题

Shinjuku 的背景是微秒级低延迟服务中，请求分布可能非常偏：绝大多数请求很短，少数请求很长。run-to-completion 或 FCFS 一旦让短请求排在长请求后面，p99 / p99.9 latency 就会被少量长请求显著拖高。

机制

Shinjuku 把 RR / processor sharing 的细粒度抢占放进微秒级服务。它使用 single address-space OS、dedicated scheduling core、硬件虚拟化辅助抢占和用户态快速上下文切换，避免传统内核路径耗尽延迟预算。

取舍

Shinjuku 与 ZygOS 的差别是：ZygOS 主要解决队列组织和 work conservation，Shinjuku 主要解决长请求压住短请求。普通 Linux 式抢占的路径和调度粒度太重，所以它必须围绕微秒级 workload 重新设计调度环境。

Tiresias

问题

深度学习训练任务大量增长后，GPU 集群调度的目标是降低平均 JCT，同时保持 GPU 利用率。难点有两个：训练时长难以准确预测；过度 consolidation 会造成资源碎片、排队时延和网络热点。

机制

Tiresias 先把调度和放置拆开。调度决定队列中谁先跑，放置决定 job 真正落到哪些 GPU 或机器上：

二维 age 定义为：

1

age = #GPUs * executed time

无完整先验时，2D-LAS 优先服务已获得服务少的 job，从而保护短 job，获得接近 SRTF 的收益；离散化后行为像 MLFQ，可以减少频繁 job switches。有部分分布信息时，可切换到 2D-Gittins 风格。

取舍

把一个 job 尽量放在同一台机器可以减少跨机通信，但所有 job 都过度集中会制造碎片和排队。Tiresias 的 model profile-based placement 用 tensor size 等模型特征判断是否值得 consolidation。60-GPU 测试床中，它相对 YARN-CS 将平均 JCT 改善约 5.5x；2000-GPU trace 仿真中，相对 Gandiva 改善约 2x。

DRF

问题

单资源 max-min fairness 很直观：每个用户获得公平份额。但数据中心作业的需求往往是向量化的，例如 CPU、内存、磁盘和 I/O。只看一个资源时，CPU-intensive 和 memory-intensive 用户之间到底谁更“占便宜”会变得模糊。

机制

DRF 的做法是先把每个用户最紧张的资源找出来，再围绕这个瓶颈资源比较公平性。它定义两个核心概念：

DRF 对所有用户的 dominant share 做 max-min fairness。计算例子流程是：先算每个用户在每种资源上的占比，再取最大占比作为 dominant share，分配时优先照顾 dominant share 最小的用户，直到某些用户被拉齐或资源耗尽。

例子

设总资源为 <9 CPU, 18 GB>。用户 1 的任务需求是 <1 CPU, 4 GB>，主导资源是内存；用户 2 的任务需求是 <3 CPU, 1 GB>，主导资源是 CPU。DRF 不把资源份额简单相加，而是让二者在各自瓶颈资源上的 dominant share 达到同层公平。

取舍

Asset fairness 只保证资源总量相等，可能让某个用户在瓶颈资源上吃亏。DRF 还提供 share guarantee 和 strategy-proofness；CEEI 等市场方案则可能换取更高利用率。

FairRide

问题

传统 LRU/LFU 优化全局命中率，可能让某些用户拿到很小缓存份额，也容易被 spurious access 等策略性行为利用。FairRide 关注的是共享缓存中的三目标冲突：isolation/share guarantee、strategy-proofness、Pareto efficiency。

机制

Isolation/share guarantee、strategy-proofness 和 Pareto efficiency 无法同时完全满足。FairRide 从 max-min fairness 出发，先给每个用户 share guarantee，再分摊共享文件的访问成本。用户未承担相应成本时，系统通过 blocking 或 delaying 限制其访问。

概率阻断公式是：

1

p(n_j) = 1 / (n_j + 1)

其中 n_j 是共享该文件的其他用户数。例如 p(1)=50%，p(4)=20%。

取舍

deterministic blocking 的直觉是让 cheating always gives worst performance，从而降低策略性访问收益；probabilistic blocking 可以减少无谓阻塞，但阻塞太少又不能防作弊。FairRide 的定位是 near-optimal：在 fairness / strategy-proofness 和效率之间做折中。

经典策略的现代实现

现代系统并没有抛弃经典算法，而是把它们放进新的约束里重写：

这些系统保留了经典策略的目标，但把实现位置移到了 dataplane、GPU 集群调度、多资源分配和共享缓存之中。