小编点评

正文

https://www.cnblogs.com/charlieroro/p/14666082.html

译自：BPF for storage: an exokernel-inspired approach

BPF主要用于报文处理，通过绕过网络栈提高报文的处理速度。本文则用于通过绕过存储栈(文件系统、BIO等层)来提高存储的读写效率，但在实现过程中也遇到了相应的挑战，如文件和块的映射关系，多进程共享存储块以及进程间的QoS等。

概要

内核存储路径开销占新式NVMe存储设备访问延迟的一半。本文中我们将探究使用BPF在内核的I/O处理栈中注入用户定自定义函数来降低这种开销。当发起一系列独立的I/O请求时，这种方式可以(通过绕过内核层以及避免跨内核边界)增加2.5倍的IPOS，并降低一半延迟。但在绕过文件系统和块设备层的同时时应该避免丢失重要的属性，如文件系统的安全性和物理块地址和文件偏移之间的转换。我们从90年代后期的外核文件系统中汲取灵感，为这些问题提供了可能的解决方案。

简介

历史上，存储设备在实现高带宽和低延迟的目标上要远低于网络设备，现在很多网卡(NICs)都可以支持100 Gb/s的带宽，而物理层的存储设备仅支持2-7GB/s的带宽，以及4-5us的延迟[8, 13, 19, 20]。当使用这些存储设备时，软件栈会在每个存储请求上花费大量开销，在我们的实验中占存储请求占了一半的I/O操作延迟，且可能对吞吐量造成更大的影响。

内核旁路(kernel -bypass)框架(如SPDK[44])以及靠近存储的处理方式可以降低内核开销。但两者同样都有明显的缺点，例如通常需要定制，需要对应用程序进行更改[40，41]，缺乏隔离性，在I/O使用率不高时会浪费大量等待时间，以及在计算存储中需要定制的硬件[10, 16, 42]。因此，我们期望使用一个支持标准OS的机制来降低高速存储设备的软件开销。

为此，我们参考了很早就支持高速带宽设备的网络通信。Linux的eBPF[6]为应用提供了一种直接在内核中嵌入简单函数的接口。当用于拦截I/O时，可以在应用中使用这些函数进行处理，以此来避免内核和用户空间的上下文切换和数据拷贝。Linux eBPF通常用于报文处理和过滤[5,30]、安全[9]和追踪[29]。

BPF在内核中普遍存在，并被广泛用于在网络栈外针对特定应用进行内核侧扩展。BPF可以用于链式依赖的I/Os，消除内核存储栈传输以及与用户空间的数据转换造成的开销。例如，它可以遍历一个基于磁盘的数据结构(B树，该数据结构中一个块会引用另一个块)。通过在内核中嵌入这些BPF函数，就可以像内核旁路一样消除发起I/Os造成的开销，但与内核旁路不同的是，它不需要轮询以及浪费CPU时间。

为了了解BPF可以获得的性能，我们确立了四个与存储使用有关的开放研究。首先，为了便于采纳研究结果，在架构上必须支持标准的Linux文件系统，并尽量减少对应用的修改，同时应该兼具灵活性，且能够高效运行并绕过大量软件层；其次，存储使BPF超出了当前的简单报文处理的范畴，由于报文是自描述的，这使得BPF对它们的处理在大部分场景下是相互隔离的。而硬盘上的数据结构的传输通常是有状态的，且经常需要查询外部状态。存储BPF需要了解应用的磁盘格式，并访问外部的应用状态或内核状态。例如，为了并发访问或访问内存的结构的元数据；再者，我们需要保证BPF存储函数在允许应用间共享磁盘容量时不会违背文件系统的安全性。存储块本身通常不会记录块的所有者或访问控制属性，与网络报文相比，报文的首部指定了该报文所属的流。因此我们需要一种有效的方案来实施访问控制，且不会在内核文件系统和块层引入开销。最后，我们需要保证并发性。应用程序需要通过细粒度同步(如锁耦合[28])来支持并发访问，以此避免读写对高吞吐量的影响，因此BPF函数可能需要同步功能。

我们的灵感来源于外核文件系统。用户定义的内核扩展是XN的基石(用于Xok 外核)，它通过从用户进程下载到内核[32]的代码来支持互不信任的"libfs"es。在XN中，这些不可信的功能被解释为让内核按照用户定义的方式来理解文件系统元数据。这种方式不会影响应用和内核设计，且满足了文件系统布局的灵活性目标。虽然我们需要一个类似的机制来允许用户让内核理解他们的数据布局，但实现的目标是不同的：我们希望在设计上允许应用使用自定义的兼容BPF的数据结构以及传输和过滤磁盘数据的功能，且能够与Linux现有的接口和文件系统一起运作，通过大幅削减每个I/O执行所需要的内核代码量来驱动百万级的IOPS。

软件是存储的瓶颈

在过去的几年中，使用NVMe连接到高带宽PCIe的SSD中出现了新的内存技术，这使得存储设备在性能上可以与高速网络设备[1]相媲美，具有毫秒级的访问延迟以及每秒GB级别的带宽[8, 13, 19, 20]。现在内核存储栈成为了这些新式设备的瓶颈。

图1展示了这种情况，可以看到硬件的I/O的延迟比例降低了，由于设备硬件和系统软件的增长，使得存储设备的速度越来越快。从下图中可以看到，在第一代NVMe设备中已经可以观测到软件带来的开销(10-15%延迟开销)。在新一代设备中，软件开销则占到了几乎一半的读I/O延迟。

图1：使用512B随机读下的内核延迟开销。HDD为Seagate Exos X16, NAND为 Intel Optane 750 TLC NAND, NVM-1是第一代Intel Optane SSD (900P), NVM-2是第二代Intel Optane SSD (P5800X)

开销源。为了降低软件开销，我们需要通过发起随机512B read()调用(设置O_DIRECT选项)来测量不同软件层的平均延迟，测试环境为Intel Optane SSD Gen 2 prototype (P5800X)，6核i5-8500 3GHz，16GB内存，系统为Ubuntu20.04，内核Linux 5.8.0。本文使用的都是该配置。我们仅用了处理器的C-states和睿频加速技术，并使用最大性能调节器。表1展示了耗时最多的为文件系统层(此处为ext4)，随后是用户空间和内核空间之间的转换。

表1：使用第二代Intel Optane SSD测试512B随机read()调用的平均延迟

内核旁路允许应用直接将请求提交到设备，有效消除了除给NVMe提交请求以及设备本身造成的延时[22, 33, 44, 45]之外的开销。但消除这些层的代价也比较高昂。内核只能将任务委派给整个设备进行处理，此时必须在裸设备[40, 41]上实现应用自己的文件系统。但即使这么做，也无法保证不可信进程之间的文件和容量共享的安全性。最终，由于缺少有效的应用层中断派发，意味着应用必须采用轮询来保证高负载，最终导致无法有效地在多个进程间共享核，而在频繁轮询时也会造成I/O浪费。

最近采用了一种称为io_uring[7]的系统调用来优化I/O提交造成的开销。它使用批量和异步I/O submission/completion路径(参见图2)来分摊跨内核造成的开销，并且避免使用调度器交互来阻塞内核线程。但每个提交的I/O仍然会经过所有的内核层(如表1所示)，因此，在访问高速存储设备时，每个I/O仍然会造成大量软件开销(见下文)。

BPF是解药？

随着高速网络的崛起，为Berkeley Packet Filter(BPF)带来了新的机会，由于不需要将报文拷贝到用户空间，因此可以高效地处理报文，同时应用也可以安全地在内核中对报文进行操作。一般的网络场景包括报文过滤[4,5,21,30]，网络跟踪[2,3,29]，负载均衡[4,12]，报文引导[27]以及网络安全检查[9]等。 BPF也被用作一种在访问分类存储时避免多网络交叉的方法[35]。可以使用解释器或JIT编译器来运行用户定义的函数。

存储使用BPF。可以预见，在发起独立的存储请求时，可以使用BPF来移除内核存储栈以及内核空间和用户空间之间的数据交互。很多存储应用包含很多"辅助"I/O请求，如索引查询。这些请求最主要的一个特点是它们会占用I/O带宽以及CPU时间来获取永远不会返回给用户的数据。例如，对一个B树索引的查找其实是一系列指针查找，用来生成对用户数据页的最终I/O请求。每个查找都会经应用到内核存储栈，仅仅是为了在应用简单处理之后丢弃数据。其他类似的场景包括数据库迭代器，它会顺序扫描表，直到某个属性满足条件[15]，或图数据库执行深度优先查找[24]。

好处。我们设计了一个在使用B+树(索引数据库的常用数据结构)的磁盘上执行查找的性能测试。为了简化，实验会假设索引的叶子包含用户数据(而非指针[36])。我们假设B树的每个节点都位于独立的磁盘页，意味着对于一颗深度为d的B树，需要从磁盘读取d个页。B树查找的核心操作是通过解析当前页来找出下一个磁盘页的偏移量，并对下一页发起读操作，即"指针查找"。传统上，一个B树查找需要在用户空间连续执行d个指针查找。为了提高基准，我们从内核堆栈中的两个钩子之一重新发出连续的指针查找：系统调用派发层(主要消除跨内核开销)或completion路径上的NVMe驱动中断处理器。图2显示了两个钩子的派发路径以及正常的用户空间派发路径。这两个钩子用来代理eBPF钩子，我们最终将使用它们来完成用户定义的功能。

图2：应用的派发路径和两个内核钩子

图3a和图3b展示了两个与基准应用遍历有关的钩子的吞吐量增量。图3c展示了B树的深度对两个钩子的延迟的影响。当从系统调用派发层发起查找时，最大可以提升1.25倍。由于每次查找仍然会存在文件系统和块层的开销，因此提升并不明显。提升完全来自于消除跨内核带来的开销。存储设备的延迟接近1us，我们希望从派发钩子上获得更大的提升。另一方面，通过绕过几乎整个软件栈，从NVMe驱动程序重新发出的命令可大大减少后续I/O请求的计算量，这种方式可以提升2.5倍速度，并减少49%的延迟。但当添加更多的线程时，反而降低了相对吞吐量的提升，这是因为在达到CPU饱和之前(线程数为6)，基准应用也会从中(增加线程)受益。一旦基准达到CPU饱和之后，由重新分配驱动程序而节省的计算量会变得更加明显。由于树的每一级都包含了可以廉价发起的请求，因此吞吐量的提高将随着树的深度而不断扩大。

图3：从不同的内核层发起查找时，B树深度和吞吐量的关系

图3a：使用read系统调用查找，使用系统调用层钩子(可以看到线程对性能的提升并不大)

图3b：使用read系统调用查找，使用NVMe驱动层钩子(由于绕过了BIO和文件系统层，因此性能提升明显)

图3c：使用read系统调用单线程查找，使用系统调用层和NVMe驱动层钩子

图3d：使用io_uring系统调用单线程查找，使用NVMe驱动钩子(B树深度越深，可节省的I/O计算就越多)

io_uring怎么样？前面实验中使用了Linux标准的同步read系统调用。这里我们使用更高效、批量化的io_uring submission路径来重复这些测试场景，使用单线程来驱动B树查找。像之前一样，我们在NVMe驱动中重新发起查询请求，使用未修改的io_uring调用执行批量I/O，并绘制吞吐量提升图。图3d展示了在驱动中发起查找后的(相对于应用基准的)吞吐量提升。

如预期的一样，增加批处理调用的数目(在每个io_uring调用中的系统调用的数目)会提升吞吐量，这是因为更高的批处理会增加驱动发起的请求的数目。例如，可以廉价地发起只有一个请求(B树的每一层)的批处理，而对于大小为8的批处理，B树的每一层会节省8个并发请求。因此将钩子靠近设备有利于标准的同步read调用，并使得io_uring调用更加高效。使用深度树时，BPF与io_uring结合使用可将吞吐量提高2.5倍以上； 且三个相关的查找也可以实现1.3–1.5倍的提升。

设计存储BPF

上述实验已经告诉我们使用BPF优化高速存储设备操作速度的原因。但为了达到这些目标，需要尽早执行I/O重提交，理想情况是在内核的NVMe中断处理器内部提交I/O。但这也为使用BPF查找如键-值存储这样的实用系统带来巨大挑战。

我们设想构建一个可以提供比BPF更高层的接口库，以及新的BPF钩子，且尽可能早于存储I/O completion路径(类似XDP)[21]。该库可能包含用于加速访问和操作特定数据结构的BPF函数，如B树和日志结构合并树(LSM)。

在内核中，在每个块I/O结束后，NVMe驱动中断处理器可能会触发这些BPF函数。通过给予这些函数访问块数据原始缓冲的功能，可以从存储的块中抽取文件偏移，并立即使用这些偏移发起I/O。它们还可以通过后续返回给应用的缓冲来过滤、投影和汇总块数据。通过将应用定义的数据结构推送到内核，这些函数可以在应用有限参与的情况下遍历持久化数据结构。与XN不同，XN目的是实现完整的系统，而这些存储BPF函数主要是为了定义构成应用数据结构的存储块布局。

我们概括了初步设计中需要关注的主要考量点和挑战，我们相信通过这种方式可以实现目标，而无需对Linux内核进行实质性的重构。

安装&执行。为了加速相关访问，我们的库使用一个特殊的ioctl安装了一个BPF函数。安装后，会对应用发起I/O时使用的文件描述符"打标签"(tagged)，传递到NVMe层时也会携带该标签，后续会在触发NVMe设备中断处理器的内核I/O completion路径上检查该标签。对于每个打标签的submission/completion请求，我们的NVMe中断处理器钩子会将读存储块传递到BPF函数中。

当触发钩子时，BPF函数可以执行一部分工作。例如，它可以从块中抽取文件偏移，可以通过调用辅助函数来"回收"NVMe提交描述符和I/O缓冲，将描述符重新定位到新的偏移并将其重新发布到NVMe设备提交队列。因此，一个I/O completion可以决定下一个可以提交的I/O，而无需分配额外的CPU或延时。这类函数可以在没有应用层参与的情况下快速遍历结构。

这些函数也可以将块缓冲中的数据拷贝或聚合到本地缓冲中，使得函数可以通过执行选择、投影或聚合来生成返回到应用程序的结果。当函数结束时，它可以指定返回给应用的缓冲。如果函数启动了一个新的I/O，且还没有将结果返回给应用时(例如还没有找到正确的块)，则无需返回任何缓冲，这样可以防止将I/O完成上升到应用层。

转换&安全。在Linux中，NVMe驱动无法访问文件系统元数据。如果在一个文件的o1偏移处完成了一个I/O，BPF函数可能会使用偏移量o2来发起下一个I/O。由于NVMe无法判断该偏移量对应哪个物理块，因此o2毫无意义。块可以嵌入物理块地址来避免查询扩展区，但由于没有对这些地址进行限制，BPF函数可以访问设备上的任意块。因此，一个重要的挑战是向NVMe层提供足够的信息，有效安全地将文件偏移映射到文件对应的相应物理块偏移，而不会限制文件系统重映射(选择的)块的能力。

为了简化设计和保证安全性，每个函数仅会使用附加的ioctl用到的文件的偏移量。通过这种方式保证函数不会访问不属于该文件的数据。为了在实现该目的的同时不会减缓文件系统层的调用，且不会限制文件系统层的块分配策略，我们打算在在文件的extents(与ext4文件系统有关)不变时触发该块的回收。我们观察到，很多数据中心应用并不会原地修改块存储上的持久化结构。例如，一旦一个LSM树将SSTable文件写入磁盘，则这些文件就不会变且extents是稳定的[26]。在运行TokuDB的MariaDB上进行24小时的YCSB [25]（读取40％，更新40％，插入20％，Zip为0.7）实验，发现索引文件的extents平均每159秒才会进行一次变更，而24小时内只有5个extents的变更没有映射任何块。注意，在这些索引的实现中，每个索引保存在一个文件中，且不会跨多个文件，这种存储方式可以简化我们的设计。

我们通过NVMe层extents的软状态缓存来获得文件extents的相对稳定性。当ioctl首次在存储数据结构的文件上安装功能时，文件的extents会传递到NVMe层。如果存在没有映射到块的文件extents，则文件系统中的新钩子会向NVMe层触发一个无效调用，丢弃正在回收的I/O，并向应用层返回一个错误，必须重新运行ioctl才能重置NVMe层extents，然后才能重新发出带标签的I/O。这是一种笨拙但简单的方法，几乎完全将文件系统和NVMe层进行了解耦，且没有对文件系统块分配策略施加任何限制。当然，为了有效利用缓存，必须减少这类无效调用。

I/O粒度不匹配。当BIO层"分割"一个I/O时(如跨两个不连续的扩展)，会在不同的时间产生多个NVMe操作。我们期望尽量减少这类情况，这样就可以像一个普通BIO那样执行I/O，并将缓冲和completion返回给应用。这里，它可以执行BPF函数，并在内核开始下一次"hop"时重启I/O链，这样可以避免额外的内核复杂性。类似地，如果应用需要生成更多的I/O来响应一个I/O completion，我们可以将该completion传播到BIO层，在该层可以分配并将多个I/O提交到NVMe层，以此来避免返回给应用层。

Cache。由于索引的缓存通常由应用程序来管理[14, 23, 26]，我们假设BPF遍历时不会直接与缓冲区缓存进行交互，应用管理缓存并与遍历保持同步。缓存驱逐和管理越来越多地以具有应用程序意义的对象粒度(如，单个数据记录)为单位而非以整个分页为单位进行处理。我们的方案会符合这些模型，BPF可以将特定的对象返回给应用(而不是分页)，这样应用就可以采纳自己的缓存策略。

并发性和公平性。从文件系统发起的写可能只会反应在缓冲区缓存中，BPF遍历不可见。可以通过锁定来解决这个问题，但从NVMe驱动程序内部来管理应用程序级别的锁定可能会很昂贵。因此，需要精心设计需要细粒度锁定的数据结构(例如B +树中的锁定耦合[28])。

为了避免读/写冲突，一开始我们计划使用不可变的数据结构(至少是一段时间不可变)。幸运的是，很多数据结构都具有这种特性，包括LSM SSTable文件(不可变[26,39])，以及磁盘B树，它们不会原地动态更新，而是会分批处理[14]。此外，由于锁的复杂性，我们计划一开始只支持只读的BPF遍历。

BPF发起的请求不会经过文件系统或块层，因此不容易在进程间保证公平性或QoS，但由于NVMe设备默认的Linux块层调度器是noop，且NVMe规范支持在需要公平性时，在硬件队列使用命令仲裁[11]。另一个挑战是，NVMe层可能会无限发起I/O请求。eBPF校验器会阻止无界循环[38]，但我们也需要阻止NVMe钩子上的无界I/O循环。

为了实现公平性，并防止无界遍历，我们计划在NVMe层为每个进行实现一个计数器，跟踪I/O调用链提交的数目，并在计数器上设置一个边界。计数器的值会周期性地传递给BIO层，统计请求数目。

总结

BPF有提升高速存储设备的相关查找速度的潜力。但同时也产生了相应的挑战，特别是由于丢失上下文，对操作内核底层存储栈增加了难度。本论文中，我们主要关注索引遍历。即便如此，对于现在的高速NVMe设备，通过使用BPF将少量请求串接起来也可以获得显著的收益。我们可以预想到，BPF存储库可以为开发者在其他标准内核存储操作中提供便利，如压缩(compaction，compression)，重复数据删除和扫描。我们也相信BPF与缓存和调度器策略的交互也会创造令人兴奋的研究机会。