> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/specific-work/seminar-and-talk/fall-21-reading-list/bpf-for-storage-an-exokernel-inspired-approach.md).

# BPF for Storage: An Exokernel-Inspired Approach

* Trend: faster storage devices 
  * HDD, SSD, Intel Optane Gen 1 / 2 
  * Software overhead of I/O requests become more significant 
* Reduce kernel overhead 
  * Kernel bypass: allow applications to directly talk with the device, without going through the kernel storage stack
    * Problem: lack of fine-grained isolation, wastes CPU cycles due to polling 
    * ![](/files/QZXe6huSlHMr8oKaS3LX)
  * Near-storage processing 
    * Download application logic into the storage device, but it requires specialized hardware
    * ![](/files/OGxGcqlCIie5ux3VSgX3)
*  Reduce kernel overhead 
  * Goal: a standard **OS-supported** mechanism in Linux that can reduce the software overhead 
  * Exokernel file system supports user-defined kernel extensions, which give the kernel user-defined understanding of file system metadata 
  * By downloading application logic into the Linux kernel, we can potentially eliminate most of the software overhead 
  * Question: how to run untrusted application logic with the Linux kernel? 
    * Networking community has been using Linux eBPF for efficient packet processing, filtering, security, and tracing 
      * eBPF: extended Berkeley Packet Filter (interchangeable with BPF) 
    * BPF allows user to run untrusted function in the kernel safely using JIT compiler 
    * BPF could be used to chain dependent I/Os, eliminating traversals of the kernel storage stack and transitions to/from user space 
      * e.g., B tree index lookup 
* On-Disk B-Tree Lookup with reads 
  * ![](/files/X5PsUjITmo3Rox2ZqsRe)
  * ![](/files/ZsqQPl92LQ4mIjNcMPsj)
    * After the request is completed, an interrupt will be generated, and the interrupt handler of the NVMe driver will be invoked to handle the completion 
    * Here, already have the data. Binary search --> not in the user space 
      * ![](/files/XyQ6vuYEJuVhlDWDtjar)
* Only generate 1 read() request and (d-1) BPF lookups that bypass the kernel, where d is the depth of the tree 
* Dispatch paths for an I/O Chain 
  * ![](/files/ImSdERUptcVvNhYxeAD7)
  * NVMe driver is lack of file system and block layer semantics 
* Potential benefit of BPF
  * Breakdown average 512B read() latency using Intel Optane SSD gen 2 
  * ![](/files/tdsh2xPnimM5KFc14lYc)
* Simulate B-tree lookups with different levels 
  * Max speedup: 1.25x 
  * Dispatch from NVMe Driver: max speedup - 2.5x 
  * Dispatch from different layers: syscall layer (13%), NVMe driver (49%) 
    * Calling BPF as early in the storage I/O completion path as possible to maximize performance gain 
* Can BPF help io\_uring?
  * io\_uring is a new syscall that allows applications to submit batches of async I/O requests in a zero-copy way, and to collect batches of I/O completions 
  * However, requests sent with io\_uring still passes through all the kernel layers 
  * Dispatch from NVMe Driver (batch size) 
    * Maximal speedup: 2.7x 
    * 3-level: 1.3-1.9x 
    * BPF is complementary to io\_uring 
* Future work: design for storage BPF
  * Build a library that provides a higher level interface than BPF, and new BPF hooks in the NVMe driver completion path 
  * BPF functions would be triggered in the NVMe driver interrupt handler on each I/O completion 
    * These BPF functions could extract file offsets from blocks fetched from storage and immediately reissue an I/O to those offsets, or 
    * Filter, project, and aggregate block data by building up buffers that are later return to the application 
* Challenges 
  * Translation & Security: NVMe driver lacks file-system semantics such as extent translation and access control
  * I/O Granularity Mismatch: A single I/O request might requires multiple NVMe commands to finish
  * Caching: NVMe driver bypasses page cache, which requires the application to implement its own caching
  * Concurrency: synchronizing read and write might require locking, which is prohibitive in the interrupt handler 
  * Fairness: NVMe driver does not provide fas or QoS guarantees 
* Summary
  * Linux kernel storage stack accounts for \~50% of the access latency for fast storage devices 
  * We can bypass most of the software layers by pushing application logics into Linux kernel to issue a chain of dependent I/O requests
  * Linux eBPF allows user to download simple untrusted function into the kernel safely 
  * By dispatching the next request in the NVMe driver, we can improve the IOPS of read() syscall by 2.5x, and improve the IOPS of io\_uring by 2.7x
  * Challenges arise in terms of translation, security, caching, concurrency, and fairness