当一个查找需要一连串的前置查询的时候，可能会产生一系列最后并没有用到的数据，这些查询可以被BPF加速。 实现resubmission logic来增强NVMe驱动中的interrupt handler，包括一个BPF hook、一个file translation step、the construction and resubmission of the next NVMe request at the new physical offset。
开源 https://github.com/xrp-project/XRP
Background and Motivation
Software is Now the Storage Bottleneck
现在的NVMe存储设备能够达到7GB/s，延迟能够低至3us。
Where is the time going？
最耗时的是file system (ext4)，然后是block layer (bio)和kernel crossing。 软件开销占了48.6%。
Why not just bypass the kernel?
- kernel bypass权限全开
- 必须要自己重写file system
- 没有可靠的isolation
- user space没有有效的中断机制，所以必须poll，导致资源被浪费
- 一个processor有多个polling thread，CPU竞争和sync的缺失会导致性能下降
The Potential Benefit of BPF
当一个查找需要一连串的前置查询的时候，可能会产生一系列最后并没有用到的数据，这些查询可以被BPF加速。（就是减少数据传输）
What about io_uring? io_uring是一个新的Linux系统调用框架，它允许进程提交成批的异步I/O请求，这就摊薄了用户-内核的crossing开销。 不过io_uring仍然需要穿过整个层。
Design Challenges and Principles
Challenge 1: address translation and security
NVMe驱动程序不能访问文件系统元数据。
Challenge 2: concurrency and caching
A write issued from the file system will only be reflected in the page cache, which is not visible to XRP. In addition, any writes that modify the layout of the data structure (e.g., modify the pointers to the next block) that are issued concurrently to read requests could lead XRP to accidentally fetch the wrong data. Both of these could be addressed by locking, but accessing locks from within the NVMe interrupt handler may be expensive.
Observation
The files of many storage engines remain relatively stable. Accessing these immutable on-disk storage structures requires less synchronization effort.
Design Principle
- One file at a time. 将XRP的chained resubmission限制在一个文件内。这样简化了address translation和access control，还减少了需要push到NVMe driver的metadata
- Stable data structures. XRP针对结构（比如指针）不怎么变化的数据结构。
- User-managed caches. XRP不和page cache对接。如果blocks在内核页面缓存中被cached，XRP函数不能安全地并发运行。
- Slow path fallback. XRP是best effort的，如果traversal失败了，就回退到用户态的实现方式。
XRP Design and Implementation
Resubmission Logic
当一个NVMe请求完成后，设备会产生一个中断，导致内核上下文切换到中断处理程序中。 对于每个在中断上下文中完成的NVMe请求，XRP调用其相关的BPF函数（图4中的bpf_func_0），其指针存储在kernel I/O request struct（即struct bio）的一个字段中。 调用BPF函数后，XRP调用metadata digest，这通常是一个文件系统状态的digest，使XRP能够翻译下一次重新提交的逻辑地址。 最后，XRP通过设置NVMe请求中的相应字段来准备下一次NVMe命令的重新提交，它将请求附加到该核心的NVMe提交队列（SQ）。
BPF Hook
定义了一种新的BPF类型 - BPF_PROG_TYPE_XRP。
主要讲了一下几个字段的用处。
scratch可能比较重要。 scratch是一个4KB的缓冲区，用来从user到BPF传递参数、在I/O之间存储intermediate data、向user返回data。
下面文章的这句话其实没理解： Letting the user supply a scratch buffer (instead of using BPF map) avoids the overhead of processes and functions having to call bpf_map_lookup_elem to access the scratch buffer.
BPF Verifier
上面定义的数据结构里面，data和scratch是PTR_TO_MEM格式的，其余都是SCALAR_TYPE。
本文还改了BPF verifier，允许BPF_PROG_TYPE_XRP的is_valid_access()回调将data或scratch的大小传递给验证器，以便它能够执行边界检查。
The Metadata Digest
在传统的存储栈中，磁盘数据结构中的逻辑块偏移量由文件系统进行转换，以确定要读取的下一个物理块。 这个转换步骤也执行了访问控制和安全，防止在没有映射到开放文件的区域中进行读取。
在XRP中，查找的下一个逻辑地址是由BPF调用后的next_addr字段给出。 然而，将这个逻辑地址翻译成物理地址是一个挑战，因为中断处理程序没有文件的概念，也不执行物理地址翻译。 为了解决这个问题，本文实现了metadata digest，这是文件系统和中断处理程序之间的一个thin interface，让文件系统与中断处理程序共享其逻辑到物理块的映射。
主要是由update_mapping和lookup_mapping组成。 update函数is called within the file system，实现logical-to-physical的更新。此外update函数还通过防止BPF函数请求打开文件以外的block的resubmission来执行访问控制。 lookup函数is called within the interrupt handler，返回一个给定的offset和length的mapping。
后面讲了一些数据结构可能竞争的处理。总体来说是无锁的。
Resubmitting NVMe Requests
Resubmission包括了复用数据结构以节省kmalloc开销和fanout两个设计点。
Synchronization Limitations
不管是eBPF自带的自旋锁还是自己实现的spinlock，都存在一些限制。
Interaction with Linux Schedulers
当多进程共享一个核的时候，像Optane SSD这种微秒级的存储设备会interferes with Linux的CFS。 比如当I/O-heavy进程和compute-heavy进程在同一个核上运行的时候，I/O-heavy进程产生的中断会在compute-heavy的时间片内被处理。 不过文章没有解决，只是把这个问题提出来了。
Case Studies
主要是两个函数：bpf_prog_load（libbpf里面的函数）；read_xrp像是pread的扩展，主要加了bpf_prog_load返回的文件描述符和对scratch的指针。
分别实现了
- BPF-KV，一个kv store
- WiredTiger，MongoDB的后端
Evaluation
主要回答四个问题
- overhead
- XRP如何scale to multiple threads
- XRP能够支持什么样的操作
- 这个其实只是做了range query的实验，在figure 8
- XRP对real-world kv store的加速效果