RESYSTANCE: Unleashing Hidden Performance of Compaction in LSM-trees via eBPF

RESYSTANCE is a system that leverages eBPF and io_uring to offload LSM-tree compaction I/O operations directly into the kernel, eliminating nearly all system call overhead and achieving up to 75% throughput improvement and 40% latency reduction in write-intensive workloads without modifying existing database structures.

The Gist

Here is an explanation of the paper RESYSTANCE, broken down into simple concepts with creative analogies.

The Big Problem: The "Paperwork" Bottleneck

Imagine you own a super-fast delivery truck (your NVMe SSD). This truck can drive at 200 mph. However, every time the driver wants to pick up or drop off a package, they have to stop at a government office, fill out three different forms, get a stamp, wait in line, and then drive back to the truck.

Even though the truck is fast, the paperwork (the System Calls) is so slow and annoying that the truck spends 90% of its time waiting in line and only 10% actually driving.

In the world of databases (like RocksDB), this is exactly what happens. The hardware is incredibly fast, but the software (the operating system) forces the database to stop and "talk" to the kernel (the OS manager) for every single piece of data it reads or writes. This slows everything down.

The Specific Culprit: The "Cleanup Crew"

In these databases, data is constantly being organized. Imagine a library where books are thrown onto a shelf randomly. Every so often, a Cleanup Crew (called Compaction) comes in to sort the books, remove duplicates, and organize them neatly.

The problem? The Cleanup Crew is doing its job terribly inefficiently.

• Instead of grabbing a whole box of books at once, they pick up one book, run to the office to fill out a form, run back, pick up the next book, run to the office again... and so on.
• Because they have to do this for thousands of books, the "Cleanup Crew" becomes the biggest bottleneck in the entire system.

The Solution: RESYSTANCE

The researchers created a tool called RESYSTANCE. Think of it as a Magic Clipboard and a Direct Highway that lets the Cleanup Crew work without ever leaving the warehouse.

Here is how it works, using two main technologies:

1. The Magic Clipboard (eBPF)

eBPF is like a safe, programmable robot that lives inside the government office (the Kernel).

• Before: The Cleanup Crew (User Space) had to leave the warehouse, go to the office, ask for permission to read a book, come back, read it, go back to the office, ask to write it, etc.
• With RESYSTANCE: The researchers give the Cleanup Crew a "Magic Clipboard" (an eBPF program). This clipboard allows the crew to read the books, sort them, and organize them right inside the office, without ever having to leave the building or fill out the standard forms.
• Safety: The government (Kernel Verifier) checks the clipboard first to make sure the robot won't accidentally burn down the building or steal the books. It's safe, but super fast.

2. The Direct Highway (io_uring)

io_uring is like a High-Speed Conveyor Belt that connects the warehouse directly to the trucks.

• Before: The crew had to shout a request, wait for a reply, shout another request, wait for a reply.
• With RESYSTANCE: The crew puts a whole list of 100 books onto the conveyor belt at once. The belt whisks them all to the truck instantly. The crew doesn't have to wait for a reply for each book; they just keep working while the belt does the heavy lifting.

The Result: A Supercharged Library

By combining the Magic Clipboard (doing the work inside the office) and the High-Speed Conveyor Belt (sending many requests at once), RESYSTANCE changes the game:

• 99% Less Paperwork: The database stops filling out forms for almost every single book.
• 50% Faster Cleanup: The "Cleanup Crew" finishes its job in half the time.
• 75% More Throughput: The library can process way more customers (writes) because the shelves are being organized so efficiently.
• No Rebuilding: The best part? They didn't have to rebuild the library or buy new trucks. They just gave the existing crew better tools.

Summary in One Sentence

RESYSTANCE is a clever software upgrade that lets database "cleanup crews" sort and organize data directly inside the operating system's brain, skipping the slow, boring paperwork that usually slows everything down, making the database run as fast as the hardware actually allows.

Technical Summary

Here is a detailed technical summary of the paper "RESYSTANCE: Unleashing Hidden Performance of Compaction in LSM-trees via eBPF".

1. Problem Statement

With the advent of ultra-fast storage devices like NVMe SSDs, the primary I/O bottleneck in modern database systems has shifted from hardware limitations to software overhead, specifically system call invocations and context switches between user space and the kernel.

• LSM-tree Vulnerability: Log-Structured Merge-tree (LSM-tree) based NoSQL databases (e.g., RocksDB, LevelDB) rely heavily on background compaction processes to merge and sort data.
• The Bottleneck: Compaction involves reading thousands of SSTable blocks and merging them. This process generates a massive volume of pread() system calls.
  • Profiling shows compaction accounts for the vast majority of system calls in LSM engines (e.g., ~67,000 syscalls per compaction operation in RocksDB).
  • Table I in the paper indicates that for a standard pread() on NVMe, the software stack (File System, Block Layer, Driver) accounts for 68.5% of the total latency, while the hardware device accounts for only 31.5%.
• Limitations of Existing Solutions:
  • Kernel Bypass (e.g., SPDK): While effective at removing syscalls, it requires abandoning the OS file system, redesigning the entire I/O subsystem, and introduces high implementation complexity and maintenance costs.
  • Standard Optimization: Merely using io_uring without kernel integration still incurs user-kernel transitions for logic execution.

2. Methodology: RESYSTANCE

The authors propose RESYSTANCE, a framework that leverages eBPF (extended Berkeley Packet Filter) and io_uring to migrate the core I/O and merge logic of compaction directly into the kernel, eliminating unnecessary system calls without modifying the LSM-tree structure or requiring hardware changes.

Core Architecture

RESYSTANCE consists of three main components:

1. Controller: A user-space component that manages the compaction flow. It constructs an SST-Map (metadata containing SSTable indices, offsets, and sizes) and passes it to the kernel.
2. io_uring: Used to issue asynchronous, batched read requests for multiple data blocks simultaneously, maximizing NVMe parallelism.
3. eBPF Program: Hooked into the kernel, this program:
   • Receives the read data blocks.
   • Performs the merge-sort logic (comparing keys and selecting the next KV pair).
   • Writes the merged results to a kernel-side buffer.

Key Design Decisions

• Partial Offloading: Only the merge phase is offloaded to eBPF.
  • Reads: Handled via io_uring to reduce syscall counts.
  • Writes: Retained in user space using the conventional path. The authors argue that writes occur in large, infrequent batches where syscall overhead is negligible compared to I/O latency, and moving them to eBPF would increase verifier complexity and risk.
• SST-Map: Since eBPF cannot inherently access user-space metadata, RESYSTANCE builds an SST-Map in shared memory. This allows the kernel to know exactly which blocks to read without complex lookups.
• Merge Algorithms: To handle eBPF's strict instruction limits and verifier constraints, RESYSTANCE dynamically selects between two algorithms based on the number of input files:
  • Linear Search: Used for small file counts (≤6).
  • Min-Heap: Used for larger file counts (>6) to maintain $O(K \log N)$ efficiency.
• Kernel Stability: The authors modified the eBPF verifier to relax instruction count limits (from 1M to higher) specifically for compaction logic and restricted memory access to a predefined safe region to prevent kernel panics.

3. Key Contributions

1. Identification of the Bottleneck: Quantitatively demonstrated that compaction is the dominant source of system call overhead in LSM-tree databases, primarily driven by pread().
2. RESYSTANCE Framework: The first system to eliminate software stack overhead for compaction purely through software optimization (eBPF + io_uring) without altering the LSM-tree architecture or requiring kernel bypass.
3. Dynamic Algorithm Selection: A mechanism to switch between linear and heap-based merge strategies within eBPF to balance performance and verifier constraints.
4. Non-Intrusive Optimization: Achieves performance gains without modifying the LSM-tree engine's core structure or requiring new hardware accelerators.

4. Experimental Results

The system was evaluated using RocksDB v10.1.3 on a server with an AMD Ryzen 9 7950X and Samsung 990 PRO NVMe SSD, using db_bench, YCSB, and Sysbench OLTP workloads.

• System Call Reduction: Reduced the average number of system calls during compaction by 99%.
• Compaction Latency: Shortened compaction time by 50%.
• Throughput Improvements:
  • Write-Intensive (FillRandom): Improved throughput by up to 75% compared to baseline RocksDB.
  • OLTP Workloads: Achieved 22% higher throughput in mixed read-write scenarios.
  • YCSB Load: Up to 85% higher throughput in the Load phase (due to Zipfian distribution amplifying the benefits of in-kernel processing).
• Latency Reduction: Reduced p99 write latency by 40% in write-intensive workloads.
• Comparison with Alternatives:
  • Outperformed SPDK (Kernel Bypass) in compaction throughput because SPDK's reliance on a user-space cache (BlobFS) introduced overhead, whereas RESYSTANCE leveraged the kernel's native I/O scheduling and parallelism.
  • Outperformed standard io_uring implementations by removing the user-kernel transition for the merge logic.

5. Significance and Impact

• Software-Defined Performance: RESYSTANCE proves that even with ultra-fast hardware, software overhead (syscalls) remains a critical bottleneck. It demonstrates that optimizing the OS-DBMS boundary can yield massive gains without hardware upgrades.
• Practicality: Unlike kernel bypass solutions (SPDK), RESYSTANCE is non-intrusive. It works with existing file systems, standard LSM-tree engines, and requires no architectural redesign of the database.
• Scalability: The solution scales effectively with I/O parallelism; as the number of I/O threads increases, the performance gap between RESYSTANCE and baseline widens.
• Future of Kernel Optimization: The paper highlights the potential of eBPF not just for observability or networking, but for accelerating core storage I/O paths, provided that verifier constraints and kernel stability are carefully managed.

In conclusion, RESYSTANCE effectively "liberates" LSM-tree compaction from the tyranny of system calls, unlocking hidden performance potential in modern high-speed storage environments through intelligent kernel offloading.