Towards Optimal Rack-scale µs-level CPU Scheduling through In-Network Workload Shaping

找到研究场景，确定研究问题，然后在环境里做减法，减到每个机制都是必要的，且动机可查——这是要费大力气去想的。

ATC25：Towards Optimal Rack-scale µs-level CPU Scheduling through In-Network Workload Shaping

论文检索来自gemini

总览

随着云端微服务和高频实时应用的普及，微秒级服务对系统调度延迟和资源利用提出了极高要求。论文提出了一种新型机架级调度系统——Pallas，用于高效调度微秒级请求。该系统创新性地引入“网络内工作负载整形（in-network workload shaping）”的理念，利用可编程交换机主动将混合请求划分为同质请求组，并在交换机中完成分组调度，从而在根本上避免服务器侧的请求堵塞问题（Head-of-line Blocking）。随后，Pallas对这些同质请求执行组内负载均衡，并在服务器端采用简单的集中式FCFS调度，实现近乎最优的尾延迟。为了适应动态负载变化和突发流量，Pallas还设计了请求回弹（request bouncing）机制以平滑策略切换过程中的性能波动，并提出无悔（no-regret）的请求克隆策略，在局部过载时将请求复制至低负载组，从而屏蔽瞬时尖峰带来的尾延迟膨胀。

背景

机架级调度（rack-scale scheduling）典型代表是 RackSched（本文重点比较对象），它通过可编程交换机进行跨服务器负载均衡，并在服务器内使用如 Shinjuku 等数据平面操作系统进行调度。

  • RackSched 存在两个关键问题
    1. 负载不均衡：其基于最短队列（JSQ）的负载均衡方法不感知请求的具体执行时间，导致服务器间负载不均。
    2. 队头阻塞（HoL blocking）：由于请求类型混杂（长短请求混合），服务器内部即使使用高级调度算法也难以避免队头阻塞，导致尾延迟显著增加。
  • Pallas关键架构（三层调度）
    1. 工作负载整形（ToR 交换机）：根据请求类型及其历史执行时间，将请求划分到不同分组，确保组内请求的 CPU 需求高度一致。
    2. 组内负载均衡（ToR 交换机）：采用加权轮询（WRR）将请求均匀分发到组内服务器。
    3. 服务器内调度（服务器端）：对同质化请求使用简单的集中式 FCFS（cFCFS），对于少数混合服务器使用 DARC 调度。

论文观察到：同质化的工作负载在单服务器上易于调度

Pallas 的核心机制是在交换机上主动把请求分流到不同的服务器组，这要求请求在服务器之间可以灵活调度，不受数据所在位置的限制

本文限定场景

可以看到限定非常之细。

往往新人总是喜欢 “大一统、all in one、异构容错全加上”，反正要是搁我亲和性绝对放进去的（Pallas说没放亲和性是因为RackSched已经做了，迁移就好），不就是个字段吗，但Pallas没有

  • 范围
    • 单机架：仅一个ToR交换机，不涉及ToR交换机之间的交互
  • 调度何种任务
    • CPU 密集型任务，没有异构的事情。在 §7 Discussion 提到当前的“同构整形”只考虑了 CPU，未考虑内存、I/O 等资源。如果要在异构环境下达到更高吞吐量，需要将 多维资源特征 纳入分组依据。
    • 实时性 要求极高的任务，而不是离线任务。请求混合长短执行时间。依赖请求类型与执行时间的强相关性，不适用于执行时间高度不可预测的工作负载。
    • 任务必须是 无状态 的，例如只读查询。Pallas不能根据包解析数据位置。论文在 §7 Discussion 中简短提及了扩展方向，即添加一个跟type类似的字段，交换机根据这个字段做“亲和性转发”。
  • 任务封装
    • 单包请求：任务的代码是预先部署在每台服务器的 CPU 上的，不携带大量代码
    • 类型用一个8位的type字段不多：实验包括 RocksDB（2 种请求）、TPC-C（5 种）、合成负载（2-3 种），因此 8-bit Type 绰绰有余
    • 任务发起者填type字段

  • 存在微秒级突发

Q & A

  • 论文是机架级、服务器间的范围设计的，与服务器内调度器是如何协同的
    • 理解 Pallas 的协同，最好的参照是 RackSched 的失败经验：
维度 RackSched Pallas
协同信息 服务器将实时队列长度上报给交换机（有延迟） 控制平面下发静态策略（Type→Group 和调度算法）
交换机决策 基于过时的队列长度做 JSQ 负载均衡 基于预配置的权重表做 WRR 负载均衡
服务器责任 使用复杂算法（如 Shinjuku/DARC）处理混合负载 大部分服务器用 cFCFS 处理同质化负载
协同性质 反馈式：依赖实时的、可能过时的状态 前馈式：依赖预先规划的策略和请求类型
  • 如何生成有效的调度策略？
    • 使用改进的 k-means 聚类生成候选分组策略，再通过离线微基准测试选择最优策略，平衡组内同质性与系统利用率。
  • 请求回弹机制是什么
    • 在策略切换时优先处理短请求，避免队头阻塞。
  • 请求克隆机制是什么
    • 处理突发。当某个服务组（Group）在极短时间内收到的请求数量超过其处理能力时，交换机主动将部分请求复制一份，转发到其他负载较低的服务组去处理，以分摊压力、降低尾延迟。并过滤冗余响应，保证“无悔”性能。
  • 为什么Pallas没做资源感知
    • 在 §4.2 解释了原因
    • 延迟太大：如果交换机要实时感知服务器负载，需要服务器每 10μs 上报一次状态。网络延迟（RTT）远大于微秒级服务本身的执行时间，等交换机收到“忙”的信号时，服务器可能早就空闲了。
    • 避免决策错误：RackSched 因为依赖这种过时的实时负载信息导致了严重的负载不均（ Figure 2a）。Pallas 索性放弃实时感知，转向确定性更强的静态权重分配。
  • 为什么做“在网”整形，上控制面不行吗？
    • 当任务只有几微秒时，任何基于“询问-答复”的调度方案在物理逻辑上都失效了。
    • 交换机基于的是服务器 2微秒之前的状态做决策。在微秒级高并发环境下，这段时间里服务器可能早就被别的包塞满了。
    • 因此pallas 不再依赖反馈。在交换机这就把流量按类型“整形”好，前馈（Feed-forward）地发出去。在信息还没“凉”之前就把动作做完。
↑