RackSched: A Microsecond-Scale Scheduler for Rack-Scale Computers

§1 TL;DR #

RackSched 将 ToR 可编程交换机用作 rack 级微秒调度器，通过 power-of-k-choices 做服务器间负载均衡 + 各服务器内集中调度消除队头阻塞，实现近线性吞吐扩展并保持单服务器水平的尾延迟。

§2 Q1 / Q2 / Q3 #

Q1 — 痛点 #

微秒级在线服务（KV-store、事务数据库、微服务）的严格 SLO 要求数据面操作系统以极低开销调度请求。Shinjuku 等单服务器方案只能扩展到约 11 核，无法覆盖一个 rack 中数百至数千核的规模。简单地将请求随机分发到多台服务器会导致 服务器间负载不均 和 队头阻塞，尾延迟急剧恶化。现有方案要么调度延迟在毫秒级（软件集中调度如 Sparrow、Firmament），要么只做五元组哈希的静态负载均衡（SilkRoad、Duet），无法在微秒粒度做动态请求级调度。

Q2 — 方法 #

网络-系统协同设计的两层调度框架：

关键组件：

• LoadTable：交换机片上寄存器，存各服务器队列长度；通过 reply 包 INT piggyback 更新
• ReqTable：多级哈希表（数据面 insert/read/remove），保证同一请求所有包到达同一服务器
• Tree-based parallel min：流水线并行计算 k 个采样中的最小负载，$O(\log k)$ 级数

核心技术壁垒：将"per-request 粒度的动态负载感知调度"完全实现在交换机数据面（P4 → Tofino ASIC），做到线速、on-path、零额外跳数。这要求同时解决三个约束——(1) 有限 stage 数下的最小值计算，(2) 无控制面介入的状态表操作（64K slot 多级哈希），(3) 基于 piggyback INT 的亚微秒反馈环路以避免 herding。任一环节用软件或控制面解决都会退化到毫秒级。

Q3 — 结果 #

• 12 台服务器 testbed（Barefoot Tofino + 8 台 Shinjuku worker），吞吐最高提升 1.44×
• 近线性吞吐扩展：增加服务器数量，总吞吐线性增长
• 保持单服务器级尾延迟直到系统饱和
• RocksDB 实测：RackSched 维持低尾延迟至 500 KRPS vs Shinjuku 300 KRPS
• 资源开销：13.12% SRAM、9.96% Match Crossbar、12.5% Hash Unit、25% Stateful ALU

§3 架构 / 方法图 #

数据路径：

1. 客户端发送请求（anycast IP），首包 REQF 到达 ToR 交换机
2. 交换机从 LoadTable 采样 k 台服务器，tree-based 并行选最小队列，写入 ReqTable
3. 后续包 REQR 查 ReqTable 获取目标服务器（request affinity）
4. 目标服务器的 intra-server scheduler 入队并调度给 worker
5. Reply 包携带当前队列长度（INT piggyback），交换机更新 LoadTable 并删除 ReqTable 条目

包格式：ETH | IP | TCP/UDP | TYPE | REQ_ID | LOAD | Payload

• TYPE: REQF（首包）/ REQR（后续包）/ REP（回复）
• LOAD: 仅 REP 包携带，值为服务器当前队列长度

---

§4 作者证明 #

形式化基础 #

论文基于排队论 A/S/K/JSQ/P 模型体系论证两层框架的近优性。核心论断：JSQ（Join-the-Shortest-Queue）在任意服务时间分布下提供近最优负载均衡，power-of-k-choices 是 JSQ 的实际可实现近似。详细证明在技术报告 [74] 中。

关键公式 / 模型 #

符号	含义
$N$	rack 内服务器数
$C$	每台服务器核数
$k$	采样服务器数（默认 $k=2$）
$\mu$	单核服务速率
$\lambda$	到达速率
$\rho = \lambda / (N \cdot C \cdot \mu)$	系统负载

尾延迟模型：对于 Exp($1/\mu$) 服务时间，cFCFS 下 p99 延迟在 $\rho \to 1$ 时发散为 $O(1/(1-\rho))$。两层框架通过消除服务器间负载不均，使每台服务器的有效负载接近 $\rho$（全局均匀），而非出现 $\rho + \epsilon$ 的热点服务器。

Power-of-k-choices 的理论依据：经典结果 [18] 证明，从 $N$ 台服务器中随机采样 $k$ 台并选最短队列，最大队列长度从 $O(\log N)$ 降至 $O(\log \log N / \log k)$。

6 项检查 #

#	检查项	结果
1	假设显式声明	✓ — 假设微秒级请求、rack 内直连（单跳 RTT）、服务无状态或已复制
2	公式量纲一致性	✓ — 队列长度无量纲；延迟单位 µs；吞吐单位 KRPS
3	极限行为检查	✓ — $N=1$ 时退化为单服务器调度（Figure 12 验证）；$\rho \to 0$ 时所有策略等价
4	与实验数据一致性	✓ — 仿真（Figure 2）与实验（Figure 10–14）趋势一致
5	参数敏感度	✓ — $k=2$ vs $k=4$ 差异极小（Figure 15）；INT 机制对比（Figure 16）
6	未证明/推迟证明的 claim	Tech report [74] 包含完整排队论分析；论文本体以仿真+实验为主要证据

Cluster-specific 检查 #

• 尾延迟模型：Figure 2 仿真验证 JSQ-cFCFS / JSQ-PS 逼近 global-cFCFS / global-PS 的 p99。8 servers × 8 workers，Exp(50µs) 和 Trimodal 分布。仿真参数完全可复现。
• Scaling formula：吞吐 $T(N) \approx N \cdot T(1)$（近线性），尾延迟 $p99(N) \approx p99(1)$ 直到饱和。Figure 12 验证 1/2/4/8 servers。
• 反馈延迟：ToR 与服务器直连（单跳），dataplane bypass 传统协议栈，feedback loop 延迟为亚微秒级，远小于请求处理时间（50–5000 µs），因此 INT piggyback 足够实时。

---

§5 实验与数据 #

实验配置 #

项	值
交换机	Barefoot Tofino, 6.5 Tbps
Worker 服务器	8 台, Intel Xeon E5-2620 (8 core, 2.1 GHz), 64 GB, 40G NIC (Intel XL710)
客户端	4 台, open-loop, DPDK 16.11.1
P4 实现	P4 Studio → Tofino ASIC
服务器软件	Shinjuku + RackSched extension, 抢占阈值 250 µs
ReqTable	64K slots → 支持 1.28 BRPS
调度策略	默认 power-of-2-choices

关键结果 #

Exp(50) — 低离散 (Figure 10a)：RackSched 维持低 p99 直到约 950 KRPS，Shinjuku 在 800 KRPS 处急剧退化。吞吐提升 ~1.19×。

Bimodal(90%-50, 10%-500) (Figure 10b)：RackSched 650 KRPS vs Shinjuku 500 KRPS。吞吐提升 ~1.30×。

Trimodal(33.3%-50/500/5000) (Figure 10d)：多队列策略下 RackSched 优势更大，因请求类型越多样，inter-server 调度增益越显著。

RocksDB 实测 (Figure 13a)：90% GET / 10% SCAN，RackSched 维持低尾延迟至 500 KRPS vs Shinjuku 300 KRPS。吞吐提升 ~1.67×（最大场景）。50/50 混合下 GET 和 SCAN 两种请求的尾延迟均改善。

近线性扩展 (Figure 12)：1→2→4→8 servers，总吞吐近线性增长。8 台时 RackSched(8) 比 Shinjuku(8) 多支撑 150 KRPS (650 vs 500)，且随服务器数增加优势扩大。

对比 R2P2 (Figure 14)：R2P2 无抢占式 intra-server 调度，在高离散负载下尾延迟显著劣于 RackSched。在低离散负载下差距更大（R2P2 的 JBSQ 策略导致队头阻塞）。

对比 Client-based (Figure 14)：Client(100) 性能几乎等同于随机分发（Shinjuku），因为微秒级负载下 probing 开销抵消了调度收益。

消融分析 #

调度策略 (Figure 15)：Shortest（贪心最优）因 herding 反而劣于 Sampling-2/4；RR 因忽略服务时间差异在高负载退化。Sampling-2 ≈ Sampling-4，边际收益递减极快。

负载跟踪机制 (Figure 16)：INT1（per-server outstanding requests）最佳；Proactive（switch 计数器增减）因丢包误差最差；INT2（仅跟踪最小值）因 herding 次之。

---

§6 论证链 #

步骤	命题	论据类型	证据位置
1	µs 级请求 + Moore 定律终结 → 必须从单服务器扩展到 rack 级（数百/数千核）	趋势论证 + 文献引证	§1 para 1-3; [12, 31]
2	集中调度（单核管理整个 rack）不可行：Shinjuku 仅扩展到 11 核；100M RPS 需每 10ns 处理一请求	算力瓶颈分析	§2 para 3, 5
3	两层框架（ToR inter-server + per-server intra-server）逼近集中调度性能	排队论 + 仿真	§2 para 4-6; Figure 2
4	JSQ 近最优但实际不可行（stale info → herding）；power-of-k-choices 是可实现的近似	理论 [18] + 实验	§2 para 7; Figure 15
5	ToR 可编程交换机是 inter-server scheduler 的唯一合适位置：on-path、线速、全局视野	架构论证 + client-based 反例	§2 para 5, 8; Figure 14
6	数据面三组件（LoadTable/ReqTable/Tree-min）可在 Tofino 有限资源内实现	工程验证	§3.3-3.5; §4.1 资源消耗
7	端到端：近线性吞吐扩展 + 单服务器级尾延迟直到饱和	实验验证	§4.2-4.4; Figure 10-13

---

§7 实现 cross-reference #

开源代码：https://github.com/netx-repo/RackSched

核心技术壁垒实现 #

在交换机数据面实现 per-request 动态调度的三个关键难点：

1. Tree-based parallel min computation（§3.3）：利用 Tofino 多 stage pipeline 的并行性，将 $k$ 个采样服务器的 LoadTable 值以二叉树方式归约。每 stage 执行 $m$ 次独立比较，$\log k$ 个 stage 完成最小值选取。P4 实现需精确控制寄存器读写在 stage 间的依赖关系。
1. Multi-stage hash table for ReqTable（§3.4, Algorithm 2）：借鉴 Cuckoo hashing 思路，$n$ 个 stage 各有 $m$ 个 slot，通过不同哈希函数索引。INSERT/READ/REMOVE 全在数据面完成，避免控制面介入（控制面仅 ~10K updates/s，远不够）。溢出时 fallback 到哈希随机分发。
1. INT piggyback + power-of-k-choices 的 herding 消除（§3.5）：reply 包在 LOAD 字段携带服务器当前队列长度。直连拓扑 + dataplane bypass 确保反馈延迟亚微秒。采样的随机性天然避免"多个连续请求扎堆到同一台最低负载服务器"的 herding 效应。

关键实现细节 #

1. ReqTable 容量规划：64K slots × 8 bytes = 256 KB。以 50 µs 平均请求延迟计，每 slot 支撑 20 KRPS，总计支撑 1.28 BRPS — 远超 rack 内实际吞吐。溢出概率极低，但论文仍提供 fallback 路径。
1. 抢占时间片 250 µs：Shinjuku 工人超过此阈值即被抢占。此值需根据服务时间分布调优 — 太小增加 context switch 开销，太大则长请求阻塞短请求时间过长。论文未做该参数的敏感度分析。

Software → Hardware reverse implication #

RackSched 隐含对交换机硬件的以下需求：

• 数据面可编程性：match-action pipeline 可执行自定义逻辑（P4 → Tofino/Trident 等）
• 片上 Stateful ALU：支持 register read-modify-write（本文消耗 25% — 最紧约束资源）
• 足够 stage 数：tree-based min 需 $\log k$ + 采样 + affinity 查表，总计消耗 10+ stages
• 足够片上 SRAM：ReqTable 256KB + LoadTable <1KB，对现代交换芯片（数十 MB SRAM）不构成瓶颈

---