> 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 https\://sigops.org/s/conferences/hotos/2021/papers/hotos21-s07-zhong.pdf * 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 * ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2FzkM2qCnzZwLapKXEfPz3%2Fimage.png?alt=media\&token=19110154-0936-400a-b88b-34d84fdb43b2) * Near-storage processing * Download application logic into the storage device, but it requires specialized hardware * ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2F9aHHcJjd2DYkN1m20DQu%2Fimage.png?alt=media\&token=4aeca405-e202-4b57-b300-a19429e9b4fa) * 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 * ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2F1OGv0FoWdTssG7DYhKns%2Fimage.png?alt=media\&token=03017edd-25be-4e82-99f9-4397aad5d89c) * ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2FvY2Egmkn9EA1187HHy6T%2Fimage.png?alt=media\&token=12a5ec9e-7b1a-4856-a6f6-4c7cfc1bbebc) * 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 * ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2Fxiwr3CkKIGOP0yAxP6iz%2Fimage.png?alt=media\&token=cce0e3cd-41c4-4a9c-8b92-254c5e50b665) * 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 * ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2FPXj0V8jZy74DsOtrrvOp%2Fimage.png?alt=media\&token=c5e3e346-adf6-44c7-912d-00cc3d8a5150) * 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 * ![](https://2097630930-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVORxAomcgtzVVUqmws%2Fuploads%2FgSL9MlKR6SXdnainU8d6%2Fimage.png?alt=media\&token=7c3768b8-267f-444f-8d12-748716200633) * 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