Syrup: User-Defined Scheduling Across the Stack

原文地址：doi/10.1145/3477132.3483548

背景

  1. 应用性能受到多种调度机制的影响，比如 OS 、网络协议栈和应用自身的任务分配
  2. 这些调度机制和策略往往与系统自身深度捆绑，例如 Linux 的 CFS 和网卡的流一致哈希 RSS，想要修改调度策略工作量大且通用性差
  3. 希望能允许应用跨层定义自己的调度策略，在网卡、协议栈、内核调度器等多个地方执行

用户定义的调度框架需要满足以下需求：

  1. 表达力：能够实现多种调度策略
  2. 跨层部署：在执行和数据路径上的各个层面生效
  3. 低开销
  4. 用户隔离

设计

Syrup 由以下组件和工作流构成：

  1. 调度策略文件，文件内需要实现一个简化的 C 的接口
  2. 应用程序通过 syr_deploy_policy 调用指定调度策略和 hook
  3. 这个函数和守护进程 syrupd 通信，后者编译调度策略成可执行代码
  4. 将可执行代码部署到调度钩子位置
  5. 不同部署点位的调度策略可以通过 Map 接口通信

Syrup 将调度抽象为一个在线匹配问题，能够支持网络包、连接、线程作为输入，网卡队列、处理器核和网络 socket 作为执行器。

实现

Syrup 利用 eBPF 和 ghOSt 分别作为网络协议栈和内核线程调度的后端，二者均提供了低开销、安全的内核 hook 机制。

性能评估

RocksDB 和 MICA ，看 BE 和 LS 负载的吞吐和尾延迟

评价

Syrup 在 Linux 内核中不同 hook 机制之上构造了一套统一的跨层调度框架，并且允许不同层和点位的调度执行单元互相通信，应用能够根据自己的情况更好地设计调度策略，并且相对轻松地部署。匹配-执行的抽象在软件定义网络的包调度中应用较广，现在用于 OS 内调度框架应该也很合适。

Enzian: An Open, General, CPU/FPGA Platform for Systems Software Research

原文地址： doi/10.1145/3503222.3507742

背景

  • 过去的系统研究主要基于商用成品服务器，而随着越来越多的新型特化、异构的硬件架构在各类平台上部署，成品服务器无法满足探索新架构的需求。
  • 现有的 CPU-FPGA 系统主要可分为以下几类：
    • 基于 PCIe 的加速器：FPGA 和 CPU 之间用大吞吐量的 PCIe 总线连接，但不适合细粒度的负载。编程接口通常类似 GPU。CCIX 和 CXL 等协议强化了内存和缓存一致性方面的能力。
    • 完全缓存一致协议：FPGA 和 CPU 直接通过缓存一致协议互联，FPGA 能够访问连接到 CPU 的内存，但自身几乎没有直连内存。适合细粒度的工作负载。
    • 智能网卡：主要用于处理网络包。用途相对单一。
    • 单芯片混合平台 MPSoC ：在 FPGA 内集成 CPU 核，FPGA 可以和 CPU 通过片内总线互联，嵌入 CPU 的内存子系统，但内嵌的 CPU 核通常性能较弱，难以运行真实负载。

设计

面向研究的平台需要满足两个重要的标准：

  1. 高覆盖率：能够模拟替换更多的特化系统，还能覆盖尽可能多的未来潜在的设计
  2. 性能充足：与现有的特化的系统的性能相当，便于对比。

Enzian 主要遵循以下设计原则：

  • 不要过度担心每台单元的成本
  • 不确定的时候就过度设计
  • 倾向于大带宽而不是容量
  • 避免被现有标准限制
  • 暴露更多的底层控制和测量接口
  • 不只考虑单个单元，而要考虑多台互联组成更大的系统

Enzian 硬件上主要架构是双槽 NUMA 系统，CPU 是 Marvell Cavium ThunderX-1 ARMv8, FPGA 是 Xilinx XCVU9P ，二者通过原生的一致性互联协议连接，此外还有丰富的内存、网络、存储等接口。在 FPGA 一侧采用了自行设计的 ECI 一致性接口，能够与 CPU 的 CCPI 协议互相操作。

基板管理器 (BMC) 部分硬件采用了基于 Zynq 7000 的设计，软件采用 OpenBMC ，能够精细灵活地调控基板上大量的电源轨配置、上电时序、时钟分布等内容。Enzian 中有 25 个电压调节芯片，提供 30 个电源轨，其中大部分可以通过 PMBus 协议控制和监测，可以用于研究供电异常等场景下的系统行为。

评估

主要评估了以下场景：缓存一致互联、网络、PCIe 加速器应用、定制内存控制器、功耗监测。

评价

很多研究致力于解决现实应用中遇到的问题，但是解决研究过程本身遇到的问题的工作相对较少。尽管 Enzian 的设计原则很大程度上与工业产品的实践相悖，但最终呈现的系统的完成度却相当高，不像某些只能作为实验室里的小玩具。

Towards Fast, Adaptive, and Hardware-Assisted User-Space Scheduling

原文地址： arXiv:2308.02896

背景动机

  1. 云应用的微服务需要满足尾延迟约束，而双模、重尾分布的任务在协作式调度下尾延迟表现不佳，需要抢占式调度；
  2. 内核只能提供毫秒级的线程抢占调度，开销大，无法满足微秒级的尾延迟要求；
  3. Shinjuku 利用虚拟化的 IPI 通知实现了微秒级时间片调度，但在共享云场景下可能无法访问 APIC。

方法/贡献

基于 x86 用户态中断扩展 (UINTR) ，提供可微秒级抢占调度的用户态线程库，快速精准的用户态计时器，允许应用提供灵活的调度策略，为用户态中断提供新的软件抽象层。

设计和实现

  1. LibPreemptible: 函数线程，请求上下文，DDL
  2. LibUtimer: 轮询 TSC, 用 UMWAIT 降低功耗或让出超线程
  3. 调度器: 全局就绪队列，动态调整调度周期

评估

性能对比

负载类型：重尾（双模态）、轻尾（指数）、动态（前半段重尾，后半段轻尾）

相同尾延迟约束下，吞吐量比 Shinjuku 高 10% ~ 50%

LibPreemptible

微测试：uintrFd 即使在阻塞 (blocked) 状态下性能也比其他 IPC 好很多，大约是非阻塞的 uintr 的 1/2 ~ 1/3

LibUtimer 的精确性和扩展性都优于内核定时器；内核定时器做不到 20us 级别，基本上下限是 60us 。

真实负载

MICA KVS 作为延迟敏感应用， zlib 压缩作为尽力调度 (best-effort) 应用

调度策略： FCFS+抢占，固定抢占周期；FCFS+抢占，动态周期

固定比例混合请求，稳定请求量和突发请求量

相关工作

  • 数据平面 OS: IX, ZygOS, Shinjuku
  • 用户态线程: Go, uThreads, C++ 协程; Libturquoise 首次通过定时器实现抢占调度用户态线程
  • 调度策略: FCFS, RSS, 工作窃取，抢占和完全无抢占，定制硬件

评论

基本上是用户态中断版的 Shinjuku ，再加上一些动态调度策略，背景和测试负载与 Shinjuku 一脉相承。测试设计和相关工作的整理比较丰富。

微测试条件和 Intel 的内核邮件里的基本相同， signal 和 pipe 表现也接近，但 eventfd 的延迟几乎相差两倍，比较奇怪。

RISC-V (至少 Rocket) 缺少 UMWAIT 这种类似于用户态 wfi 或者 wfe 的指令，也没有超线程，轮询用户态中断可能就比较浪费 CPU 了。

主要作者来自康奈尔， MIT 和 Intel ，另外 Shinjuku 的作者也在其中。虽然本文目前在预印本网站上，但从作者之一的主页推测可能在投 SOSP '23 。

Achieving Microsecond-Scale Tail Latency Efficiently with Approximate Optimal Scheduling

原文地址：doi/10.1145/3600006.3613136

代码仓库：dslab-epfl/concord

背景动机

  1. 尾延迟约束
  2. 针对尾延迟优化的系统往往牺牲吞吐、可部署性和通用性

方法/贡献

Concord 通过近似模拟单队列调度和（基于中断的）精确抢占的行为，能够大幅提升吞吐率，同时又几乎不影响尾延迟，不牺牲可部署性和通用性，以此在吞吐和尾延迟上取得更好的平衡。

设计和实现

  1. 编译器插入调度点，工作线程和调度器之间通过缓存异步通信，近似精确抢占
  2. JBSQ 调度器，近似单队列，减少缓存一致性带来的阻塞
  3. 任务调度器也参与处理请求

评估

评论

看了下代码，比想象中还要简单，似乎并没有特殊的针对缓存优化的操作，直接放了个全局变量去查的。另外既然是在 LLVM 上加了一个 pass ，那应该对应用的语言要求不高， Rust 这种编译到 LLVM IR 的也能用。

核心的部分包括 在循环中插代码 ， 在函数中插代码 （不过这一部分好像没有调用）。在 IR 层面主要加了这些操作：

  1. 查找或创建全局变量 concord_preempt_now
  2. 加载该全局变量的值，判断是否为 1
  3. 若为 1 ，跳转到切换函数 concord_func

在调度器代码 中，基本上的做法就是轮询 rdtsc ，如果时间到了，就把 concord_preempt_now 全局变量置为 1 。除了这个变量放在 TLS 外，目前没有看到其他针对缓存的优化，推测是轮询频率较高所以这个变量能常驻在缓存中。

TreeSLS: A Whole-system Persistent Microkernel with Tree-structured State Checkpoint on NVM

原文地址：10.1145/3600006.3613160

背景动机

  1. 基于 NVM 的单层存储 SLS
  2. 现有的 SLS 大部分还是基于 DRAM + 闪存的两层结构，靠软件检查点提供单层的抽象，性能开销大，检查点频率低
  3. 全系统持久化一方面希望对应用透明，另一方面还要对外部同步
  4. 微内核的 Capability Tree 结构简单，其他系统服务状态可以直接按照用户程序内存数据来持久化

方法和贡献

  1. 基于 NVM 和微内核 Capability Tree 结构和检查点的全系统持久化 SLS
  2. 透明外部同步性

设计

  1. 定期停机，让所有处理器核进入内核态等待，其中一个核负责将系统的 Capability Tree 做检查点持久化
  2. 检查点管理器使用日志系统维护自身的持久化，避免自举问题
  3. 内存页分冷热处理，热页在停机的时候持久化，冷页先标记成只读，等应用尝试修改的时候触发页错误，再持久化

Achelous: Enabling Programmability, Elasticity, and Reliability in Hyperscale Cloud Networks

原文地址 doi/10.1145/3603269.3604859

背景与问题

Achelous是阿里云的网络虚拟化平台。随着云计算业务的发展，单个虚拟私有云（VPC）中的实例节点数量达到了百万量级，而现有的研究往往关注单一具体的问题，无法支持大规模的云网络架构。在现代云环境中主要面临以下三个挑战：

  1. 百万并发实例下的亚秒级重配置。大规模云网络有两个关键特征：高部署密度和高频实例创建和销毁。流量高峰期，用户可能同时创建数万个生命周期仅有几分钟的实例，单个VPC中总实例数量可达百万级，这会产生大量的路由表项变动，对网络收敛速度提出了很高的要求。
  2. 为重流量的中间盒部署提供高弹性网络。传统网络中间盒（如负载均衡器、NAT网关、防火墙等）通常部署在专用的物理硬件上，而为了提高灵活性，降低成本，云服务商逐渐将这些功能迁移到云上的虚拟机中，此时CPU、内存等资源的竞争可能影响中间盒的性能。此外，传统的中心化负载均衡和ECMP路由机制横向扩展性不佳，难以应对百万级数量的虚拟机产生的流量。
  3. 云服务的高可靠性。云上的虚拟网络变动频繁，不存在一个稳定的拓扑结构，传统的故障探测手段或者只能处理物理网络，或者缺乏实时探测能力，无法确保云网络的可靠性。此外，大多数热迁移手段没有考虑有状态流的流量持续性，进而导致租户服务中断。

解决方案与设计

为了应对上述三个挑战，Achelous 2.1将控制平面和数据平面协同设计，带来以下三项关键提升：

  1. 大规模网络可编程性。Achelous采用主动学习机制，由vSwitch定期向网关学习路由信息，自己只需要维护转发缓存，而控制器只需要对网关编程，不需要调整每个vSwitch的配置，vSwitch也不需要存储完整的转发信息，降低了内存开销，提升了网络收敛速度。
  2. 弹性网络。Achelous对一个主机上的所有虚拟机采用弹性信用点策略，既能确保性能隔离，又可以在资源空闲时吸收突发流量负载。Achelous还在vSwitch上实现了分布式ECMP机制，消除了中心节点带来的瓶颈。
  3. 网络风险感知和热迁移。Achelous采用多种主动网络健康探测手段，为网络故障提供早期预警。vSwitch会定期向虚拟机发送健康检查包，也会向控制器报告性能统计信息。检测到故障风险时，vSwitch会根据控制器的指导，热迁移相关的虚拟机，迁移过程中采取流量重定向、会话复位和会话同步等技术降低服务中断时间。

实现细节

大规模网络可编程性

在大规模云网络中，虚拟机路由表（VRT）和虚拟机-主机映射表（VHT）变动较频繁，需要针对性优化，而ACL、QoS等配置则相对固定，且占用体积小，可以保留在vSwitch上。Achelous在vSwitch上部署了轻量级转发缓存（FC），其中只保存目标IP→下一跳的映射，相比基于五元组等流表的设计，FC可以大幅降低计算和内存开销，也消除了针对元组空间的DoS攻击风险。

  • 快速路径：Achelous 2.1的快速路径与2.0相同，基于五元组的流和双向流组成的会话进行精确匹配，后续进入处理流水线。
  • 慢速路径：查询FC（而非2.0中查询VRT和VHT），若命中则从vSwitch直接发送到目标vSwitch，同时生成会话匹配项注入快速路径；未命中时，由网关转发，同时vSwitch会从网关学习记录对应的FC条目。 vSwitch定期（50ms）遍历所有的FC项，如果发现某项的存留时间超过阈值（如100ms），则通过路由同步协议（RSP）向网关查询，如果对应FC项有变动，则重新从网关学习更新，否则保持FC项不变。

弹性网络

Achelous采用信用点策略，在每台主机上为每个虚拟机设定带宽和处理器资源限制。当虚拟机实际使用的带宽和处理器低于限制时，累积信用点；当出现突发流量，资源使用超出限制时，消耗信用点；当信用点全部消耗完后，虚拟机资源会被削减到预设的限制值上。

网络风险感知

vSwitch定期向虚拟机发送ARP包检测虚拟机的网络健康状况。对于vSwitch之间的链路，控制器会预先配置一个检查清单，vSwitch会向检查单中的地址定期发送健康探测包，健康监测器分析这些包的延迟，向控制器报告可能的网络风险，如虚拟机失效或链路阻塞。此外，Achelous还会检测虚拟网络设备的健康状况，如CPU负载、内存占用和网卡丢包率，如果发现异常则通知控制器介入，启动故障恢复机制。

评价

Achelous是阿里云整体的网络虚拟化平台，vSwitch是其中的边缘节点和重要组成部分。在vSwitch的转发加速上，Achelous的快速路径与OVS的microflow相似，均是基于五元组做精确匹配；而OVS的megaflow仍然基于元组空间搜索，Achelous则采用更类似传统路由表的“目标IP→下一跳”的转发缓存。由于面对的VPC规模大，变动频繁，Achelous更进一步强调控制平面的更新性能，采取了更短的轮询更新间隔。

Flor: An Open High Performance RDMA Framework Over Heterogeneous RNICs

原文链接：osdi23-flor

背景

  • 不同厂商、甚至同一厂商的不同代的 RDMA 网卡 (RNIC) 之间没有统一的控制平面接口
  • 这些网卡部署在同一集群中时，并不能很好地配合，互相通信时性能存在损失且不均衡

设计

Flor 采用数据平面与控制平面分离的思路，从异构的RNIC中抽象出一组通用的控制功能，构造出通用的高性能RDMA框架，优化了异构RNIC的互操作性，且能够适应轻度有损耗的数据中心网络。

Flor 主要由五个模块构成：连接管理，分块、拥塞控制、可靠性、RTT测量。数据平面采用RDMA WRITE和SEND操作，控制平面则上移到软件处理。

  1. 连接管理模块：负责建立和释放连接，并管理备份QP，当主QP断链时切换到备份QP，以实现快速恢复；此外在使用软件可靠性模块时还有ACK QP。
  2. 分块模组：将大的消息分解成小的RDMA请求，而选择性重传和拥塞控制算法以块为基本单元，而非网络包。
  3. RTT测量模块：负责收集网卡的硬件时间戳并与软件同步，更新RTT；在Flor中RTT是网络拥塞、重传和链路故障检测的信号。
  4. 可靠性模组：负责存储传输层信息并维护丢包检测和RTT计算的状态，实现基于软件的选择性重传。
  5. 拥塞控制模块：根据拥塞信息和丢包事件，通过拥塞控制算法计算出拥塞窗口和发送速率；Flor默认的拥塞控制算法是基于RTT的。

评估

主要与 XRDMA 对比。

  • 将控制策略上移到软件带来的额外 CPU 开销并不显著，同时可以获得与XRDMA相近的吞吐量。
  • 在从1/16384到1/256的不同的高低丢包率场景下，Flor的吞吐量均超过了Mellanox CX-5有损/无损配置+XRDMA的组合。
  • 基于软件的拥塞控制能够更好适应有损网络，摆脱了对PFC的依赖，也能够大幅消减异构RNIC之间的性能差异，在跨Pod通信和异构部署的场景下能够获得稳定且均衡的性能表现。

评价

RNIC 层面的“软件定义网络”，将控制和数据平面分开，控制平面交给软件。风格和 Achelous 有类似之处，主要面向大规模部署下暴露出的问题，针对性解决。