基于eBPF和ghOSt，在用户态实现用户自定义的数据包调度算法。核心思想是map work to execution resources。用户定义自己需要的数据包调度算法，并在应用中调用API实现部署和交互。

调度器的共同特点：map work to execution resources。调度策略与workload的适配很重要。然而，实现自己的调度算法的成本/门槛太高，要么就是kernel hacking，要么就是building specialized full-stack system。

syrup认为，应用开发者应该能够express their preferred scheduling policies to the underlying systems。 syrup将调度视为一个matching problem。给三个后端提供hooks：eBPF软件，eBPF硬件和ghOSt。其中eBPF软件用于在内核协议栈中部署matching function。 eBPF硬件允许syrup利用可编程网络设备。 ghOSt负责offload线程调度。

Motivation

User-defined Scheduling Matters

为了展示调度的重要性，论文以一个非常简单的工作负载场景为例：一个6线程的RocksDB服务器，处理同质的GET请求，服务时间为10-12us。所有线程都有一个绑定到相同UDP端口的套接字。让Linux将传入的数据报分配给套接字。

Linux的vanilla scheduling使用5元组的哈希值将数据报分配给套接字。然而，图2显示它的效果不是很好，因为基于哈希的调度方案在5元组（50）和套接字（6）数量较少的情况下会导致不平衡，而比预期更多的5元组被随机分配到同一个套接字，使其过载。

需要注意的是，虽然round robin策略对这个工作负载来说比较好，但它不是万能的。对于其他工作负载类型，locality可能更重要。如果没有基于哈希的调度，像Linux的RFS这样的、将网络处理放在与接收应用程序相同的核心上的优化，是不可能的实现的。一个使用RFS的netperf TCP_RR测试已经被证明比没有RFS的测试要高出200%的吞吐量。因此，调度的灵活性和可定制性是现代操作系统的一个必要特征。

大多数现有的系统并没有提供调度的灵活性。上游的Linux内核基本上只支持六种调度策略（CFS, BATCH, IDLE, FIFO, RR, DEAD-LINE），即使在定制的内核中增加一个新的策略也需要大量的开发工作。因此，应用程序开发人员经常为他们想要以不同方式调度的每个应用程序类别建立一个新的定制框架或数据平面系统。这种方法有很大的缺点：

即使是对新的调度策略进行原型化，也需要相当大的开发努力。
这些数据平面通常使用特殊的API，与建立在现有系统（如Linux）之上的常用应用程序不兼容。
随着周围基础设施的变化，维护这种专门的每一个应用系统是非常耗时和昂贵的。

Scheduling Requirements

Expressibility
Cross-layer deployment
Low overhead
Multi-tenancy and Isolation

Syrup Design

Workflow Overview

首先，想要使用Syrup的应用程序的开发者或管理员通过在一个单独的文件中实现一个简单的C接口来指定想要的调度策略。
应用程序代码然后调用syr_deploy_policy 函数，它需要两个参数：一个描述所需调度策略的文件和一个或多个策略的目标部署钩子。这个函数与全系统的Syrup守护程序syrupd沟通，后者为策略部署做所有繁重的工作。
守护进程根据目标调度钩子，将策略文件编译成二进制文件或object文件
守护进程在用户指定的钩子中跨栈部署。
用户空间应用程序和部署在不同钩子上的Syrup策略可以选择性地交流信息，如负载、延迟统计、或预期完成时间。该交流时通过类似键值存储的map抽象实现的。map是在策略文件中定义的，并在部署时由syrupd设置。应用程序在运行过程中可以随时更新或部署新的策略。如果没有部署Syrup策略，应用程序会使用底层运行时和操作系统的默认调度策略运行。

Scheduling as a Matching Problem

Syrup通过将调度视为一个有趣的在线匹配问题来实现这一目标。调度策略被表示为输入和处理输入的执行者之间的匹配函数。输入可以是任何支持的工作单位，执行者可以是任何系统处理组件。

Syrup目前支持网络数据包、连接和线程作为输入，支持网卡队列、内核和网络套接字作为执行者。每当有新的输入可供处理时，Syrup策略就会运行，例如，一个数据包到达或一个线程可运行，或一个执行器可使用。

Syrup的匹配抽象提供了通用性，因为它可以用于各种粒度的决策。小到将数据包放置到网络协议栈处理的核心，大到将作业放置到数据中心的机器。此外，在线匹配将调度分解为一系列的小决策，提高了复杂策略的可组合性和可理解性。例如，在Linux中优化数据包的处理，首先是将数据包分配给网卡队列，然后是分配给网络堆栈处理的核心，最后是分配给应用级套接字。 Syrup用户可以为这些决策中的每一项定义和部署不同的独立调度策略。

将调度作为每个应用的在线匹配来实现，还具有可靠性和隔离性的优势。 Syrup确保每个策略只处理属于部署它的应用程序的输入。一个性能不好或有错误的策略将只影响部署它的应用程序，从而导致比单一的系统范围的策略更可靠。恶意应用程序只能通过占用一些执行器来影响整个系统的性能，这种行为可以通过资源管理器快速检测和处理。

Specifying a policy in Syrup

为了define a scheduling policy，用户需要实现一个schedule函数，指定input和output。（此处的input和output是之前提到的意思）调度决策的实际执行，例如，当使用SO_REUSEPORT时，将数据包分配给一个特定的网络套接字，是hook-specific的，由Syrup框架专门处理。

schedule函数应该返回一个uint32_t，这个值是一个application-specific并且hook-specific的一个map的key。比如connection scheduling的场景里，这个map里的存的就是network sockets。还有两个特别的返回值类型，PASS和DROP。PASS让系统用default策略，DROP就会把这个input丢了。

这里给了个例子，还比较直观。

Cross-layer communication

主要是通过提供key-value store API的map实现的。除了作为executor containers（这个是什么意思呢？）的maps之外，应用程序还可以声明和填充自定义的maps。用户定义的Maps在策略文件中声明，并由syrupd pin to sysfs，以便同一用户的不同程序可以访问它们。我们可以用文件系统的权限来控制对map的访问。

Syrupd for multi-tenancy and isolation

Syrupd提供了跨应用的隔离，在将策略加载到scheduling hook之前，它安装检查以确保每个策略只处理属于该策略应用的输入。

Syrup Implementation

eBPF & ghOSt

这两段主要是介绍eBPF和ghOSt的能力的。之所以需要ghOSt，是因为内核调度器子系统中的eBPF钩子非常少，而且大多数钩子都与可观察性有关，而不是决策。因此，syrup选择使用ghOSt将线程调度卸载到用户空间。

The coarser granularity of thread scheduling allows us to do so, while, e.g., offloading per-packet scheduling decisions to userspace would add too much context-switch overhead. 上面这句话没特别理解，但是总之最后的调度好像是线程级别的？

Supported Hooks

Thread scheduler hook，允许用户使用ghOSt定义线程调度策略
Socket Select hook，在同一个端口上监听的、使用SO_REUSEPORT选项的TCP或者UDP网络套接字中选择一个
CPU Redirect hook，允许用户steer packets to specific cores for kernel network stack processing
XDP_DRV和XDP_SKB hooks允许Syrup在包进入协议栈之前就处理具体的数据包，一个可能的做法是将这些包重定向到userspace的AF_XDP network sockets上，以实现kernel-bypass-like的性能
XDP Offload hook允许用户在smartNICs上运行策略，以编程方式steer packets to the NIC RX queues

Cross-application Isolation

Syrup允许为不同的应用程序同时部署多个用户定义的策略，并提供以下保证：

由一个应用程序加载的策略只能访问属于该应用程序的输入。
一个应用程序加载的策略代码不能对属于其他应用程序或内核的内存进行未经授权的访问。

第一点通过守护进程syrupd实现。调用syrup_deploy_policy()函数的应用程序向该守护进程发送请求，而不是将eBPF程序加载到内核本身。第二点主要是eBPF verifier实现的。

ghOSt隔离就不用说了。

Specifying Inputs and Executors

Syrupd和Syrup用户必须指定每个策略处理的输入和策略可以使用的执行器（executor）。

指定执行器是很简单的。对于网络协议栈上层的hook，执行者是network socket，在同一端口上监听数据包/连接。用户使用套接字和程序的文件描述符向Syrup注册他们创建的第一个套接字，然后将此套接字和后续套接字添加到策略部署时创建的相关executor map中。应用程序控制每个套接字所使用的map index，让schedule函数能够仅仅通过返回该map的索引来做出调度决定。

对于其余的调度hook，executor是服务器的硬件资源，即CPU或网卡队列。 Syrupd目前为每个应用程序静态地分配了一些这样的资源，并使用内核或队列ID将它们添加到每个策略map中。与套接字的情况类似，策略通过返回相关map的索引来做出调度决定。

对于输入，eBPF和ghOSt后端之间存在着差异。

对于网络协议栈的上层，每个Syrup程序都与一组套接字相关。操作系统确保每个Syrup程序处理数据报（对于UDP来说）或建立连接的SYN包（对于TCP来说）作为输入指向该套接字。对于网络堆栈的下层，Syrupd做了繁重的工作，过滤输入到正确的策略程序。在这两种情况下，策略程序都会收到一组指向数据包及其元数据的指针，它可以对其进行处理以做出调度决定。

对于ghOSt部署的策略，用户需要通过函数调用向策略注册线程，并将其添加到map中。然后，线程ID和发生的线程状态变化类型被作为输入传给调度程序。

网络协议栈和线程调度之间存在着显著的区别。它们的选择方向是反的。在线程调度中，当一个执行器/内核变得可用时，策略会选择其中一个线程/输入。而网络协议栈策略在输入变得可用时选择一个执行器。

Evaluation

主要是以下四点

syrup是否能够express并implement不同的scheduling policies
syrup能否跨层调度
syrup的调度策略在不同的hook之间是否是可移植的
syrup的性能开销