这是我在SOSP上写的最后几篇论文之一——我正在尝试一些新的东西，并在这里发布我计划阅读的论文队列。这些论文评论可以每周发送到你的收件箱，也可以订阅Atom订阅源。一如既往，请随时在Twitter上发表反馈或建议！
这篇ghOSt论文描述了一个实现Linux调度的系统。这篇论文是关于CPU调度的，而不是数据中心调度的（就像我在之前的论文回顾中提到的）。用户空间中的策略查看用户空间和内核空间之间的区别。对于数据中心工作负载来说，操作系统调度更为复杂，因为在决定要运行什么时候以及何时（例如，确保用户查询的低延迟）时需要考虑其他因素。以前的研究旨在在做出调度决策时考虑应用程序的更高级别上下文。一个示例调度器新宿（Shinjuku）旨在减少尾部延迟。通过实施定制的调度策略，该方法能够实现高达6.6倍的吞吐量和88%的尾部延迟，取得了显著的积极成果。
不幸的是，定制调度器可能很难实现、部署和维护。新宿就是一个例子。论文还引用了一系列以沙丘为主题的项目，比如卡拉丹和雪南戈，作为该领域遇到耦合问题的前期工作。一个定制调度器面临这些问题的例子——它旨在减少数据中心应用程序的尾部延迟，但需要应用程序和调度器之间的紧密耦合。这种紧密耦合意味着对内核的更改也可能会无意中影响使用这种方法的应用程序，可能会导致脆弱的实现和高昂的持续维护成本。
ghOSt旨在解决定制调度器及其实现者所面临的问题，同时促进特定于工作负载的调度器所允许的显著性能和可伸缩性提升。其方法的关键是分离调度逻辑和与内核交互的组件。被称为策略的自定义调度程序被移动到用户空间中。
相比之下，直接与Linux内核交互的相对稳定的代码仍保留在内核空间中，并为用户空间调度器提供了一个与之交互的API。这种拆分方法意味着定制调度器的运行与任何其他应用程序一样——因此，它们可以用多种语言实现，使用现有基础设施进行测试，并以更快的速度部署到更广泛的工作负载中。
本文的主要贡献有三个：设计和实现一个允许自定义调度逻辑在用户空间中运行的系统，使用该系统实现多个自定义调度程序，以及评估体系结构（包括在生产环境中）。
由于对内核代码的限制，实现调度器很困难，比如对语言的限制，在内核中支持生锈是一项正在进行的工作。调试工具见前面关于HN上内核调试困难的讨论。
部署调度程序更加困难，因为升级内核需要技术支持，而不是所有对内核的更改都需要重新启动。转移工作负载和重新启动机器的耗时多步骤过程。内核升级可能会导致性能下降，这使得这个过程更加困难。
自定义调度程序必须调度内核级线程，而不是用户级线程。请参阅用户级线程和内核支持线程之间的区别？-在内核级线程之上调度用户级线程并不能保证相关的内核级线程实际运行。本文指出了两种允许开发人员克服用户级线程限制的方法：“（1）将CPU专用于运行用户线程的本机线程，从而保证隐式控制。然而，此选项在低工作负载利用率下浪费资源，因为专用CPU无法与其他应用程序共享（请参见§4.2），并且需要围绕扩展容量进行广泛协调。或者，开发人员可以（2）任由本机线程调度器摆布，允许共享CPU，但最终会失去对响应时间的控制，而这正是他们转向用户级运行时的原因。" .
为特定工作负载定制的定制调度器也带来了挑战，因为它们不能很好地适应不同的用例（更不用说它们的内部结构很复杂，可能无法在多个调度器之间共享）。
现有的定制调度技术是不够的，尤其是伯克利数据包过滤器（BPF）Julia Evans在BPF上发表了一篇很好的文章，它最初设计用于捕获和过滤内核内部的数据包。最近，eBPF将这个想法扩展到了内核的其他部分——有关BPF/eBPF如何工作的更多细节，请参阅eBPF的全面介绍。围绕eBPF工具还有一个令人兴奋的生态系统建设，比如该工具背后的公司Cilium and Isopalent最近从Andreessen Horowitz那里筹集了资金。虽然BPF程序非常酷，但它们同步运行并阻塞CPU——从性能角度来看，这并不理想。值得注意的是，本文确实提到使用BPF实现快速路径。
自定义调度逻辑应该易于实现和测试：将调度逻辑与内核分离可以简化开发和测试。
应该可以轻松地为许多不同的用例创建调度逻辑：与以前内置在内核中的专用调度程序不同，ghOSt旨在成为一个通用平台，可以在其上构建调度程序。
调度应该能够跨多个CPU运行：现有的Linux调度程序会做出每个CPU的调度决策，并且很难在一组CPU上执行调度决策以优化其他属性，像tail latency一样，本文引用了许多以前的系统（比如Shenango：为延迟敏感的数据中心工作负载实现高CPU效率），这些系统通过跨多个CPU进行调度来实现其目标。
无中断更新和故障隔离：应该很容易部署调度逻辑，就像在机器上运行其他任务一样，允许在不需要重新启动的情况下进行更新。此外，调度策略中的故障或倒退不应使整个机器崩溃。
为了实现系统的目标，ghOSt引入了策略（自定义调度逻辑）。策略在用户空间中执行，相关的调度决策被传送到内核。
策略（及其调度决策）在运行于内核和用户空间的三个主要组件上传播：
这里的ghOSt调度类是一篇关于调度类和Linux的完全公平调度程序的伟大文章。还有一个关于相关sched系统调用的手册页。在Linux内核内部运行，并提供一个系统调用接口，其他组件使用该接口来传达调度决策。
代理在用户空间中运行策略（自定义调度逻辑），并做出调度决策，并与内核空间中运行的ghOSt调度类通信。
飞地是一群特工。每个飞地都有一个主要代理，负责制定调度决策。将多个代理分配给一个enclave可以在主代理失败的情况下提供冗余。
在内核或用户空间中运行的ghOSt组件需要一种相互提供信息和反馈的方式。本文讨论了两种主要的通信流：内核到代理和代理到内核。
在内核到代理的流程中，内核使用消息和消息队列与代理进行通信。此处定义了消息。当内核中发生可能影响调度决策的事件时，内核会在队列上发送消息。每个CPU都有一个关联的队列，每个队列都与一个enclave关联。并非每个代理都有一个消息队列，因为在某些配置中，enclave只有一个主代理从内核接收信息——请参考上面的enclave图，以获得此想法的可视化表示。虽然有几种现有的队列方法（包括io__-uring或BPF环形缓冲区），但并不是所有的内核版本都支持它们——作者认为这使得ghOSt的队列抽象成为必要。
在代理到内核的方向上，代理通过进行系统调用进行通信，以传达调度决策，并对共享队列执行管理操作。为了发送调度决策，代理创建并提交事务（比如TXN_CREATE（）和TXNS_COMMIT（））。事务非常重要，因为它们允许策略跨一系列CPU做出调度决策，确保所有或所有事务都能成功，批处理调度信息——批处理非常关键，因为它限制了影响待调度CPU的中断数量（因为ghOSt的核心组件需要响应代理事务）。
最后，内核到代理和代理到内核的通信都面临一个挑战：跟上系统的状态。内核需要确保它不会执行过时的调度决策，代理需要确保它不会根据旧的世界状态做出调度决策。用于跟踪状态的关键信息是存在于每个代理的序列号。
在内核到代理的通信中，内核在每条消息和共享内存区域中为代理提供序列号。每当内核发布新消息时，共享内存中的序列号就会被更新。当从队列中读取消息时，代理会使用共享内存中的序列号，并将该值与共享内存中的序列号进行比较。当已使用消息的序列号与共享内存中的值匹配时，代理知道它已读取最新状态。
在代理到内核的通信中，代理在向内核发送调度决策（通过事务）时包含序列号。内核将代理事务中的序列号与内核知道的最新序列号进行比较。如果事务的序列号太旧，内核就不会执行调度决策。
为了评估ghOSt，本文考虑了与系统相关的开销，将ghOSt与以前的定制调度器实现进行了比较，并评估了生产中的系统。
为了评估系统的开销，本文包括了微基准，显示了在调度系统的不同部分花费的时间，表明它具有竞争力。
本文还确定了使用ghOSt实现的全局调度器（对系统上的所有核心进行调度）的性能——之前的研究表明，随着调度器对系统有更全面的了解，这种方法的潜在优势。评估表明，ghOSt能够扩展到数百万个事务，即使它负责许多CPU。
接下来，这篇论文将鬼魂与新宿进行了比较。参见新宿论文，这是一个定制的调度系统的例子，可以减少尾部延迟。此评估的目标是查看ghOSt的性能是否与定制调度器类似（理论上，通过使用定制的优化技术，定制调度器可以实现更高的性能）。新宿与ghOSt有很多不同之处——它使用专用资源（占用全部CPU或一组CPU的旋转线程），受限于一组物理内核，并利用虚拟化功能来提高性能（如发布中断）。作者还移植了新宿调度策略本身，以便与ghOSt兼容。
这两个系统运行生成的工作负载，“其中每个请求都包括对内存中RocksDB键值存储的GET查询，并执行少量处理”。
鬼魂与新宿竞争𝜇s规模的尾部工作负载，尽管其新宿策略的代码行比定制的新宿数据平面系统少82%。ghOSt在高负载下的尾部延迟略高于新宿，在新宿饱和吞吐量的5%以内。
最后，本文针对ghOSt运行了一个生产工作负载，并将结果与使用完全公平调度程序（CFS）的机器执行的相同工作负载进行了比较。关于完全公平调度程序的更多信息，请参阅此处的“较旧”部分，但它似乎是最近更新的。
工作负载包含三种查询类型（CPU和内存绑定、IO和内存绑定以及CPU绑定）-ghOSt能够减少前两种请求的尾部延迟，但是对第三个没有太大的影响。论文确实指出，通过使用类似于Linux的CFS包含的nice值的逻辑来扩展ghOSt策略，可以影响计算绑定的任务。
在我看来，这一部分最突出的是ghOSt对开发人员生产力的影响：
在开发内核调度器时，写测试写周期包括（a）编译内核（最多15分钟），（b）部署内核（10-20分钟），以及（c）运行测试（由于重启后数据库初始化，需要1小时）。因此，这位热心的内核开发人员每天都要用5种变体进行实验。有了ghOSt，新代理的编译、部署和启动可以轻松地在一分钟内完成。
ghOSt论文建立在之前的一系列研究的基础上，这些研究证明了调度对数据中心工作负载的可伸缩性和性能有多么重要。调度还远远不是一个解决的问题，尤其是因为“杀手微秒的崛起”和新的设备类型——我期待着在ghOSt开源项目的未来工作中继续跟进！