SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores

Alexander Conway, Abhishek Gupta, Vijay Chidambaram, Martin Farach-Colton, Richard P. Spillane, Amy Tai, Rob JohnsonUSENIX ATC 2020 · OpenReview

TL;DR

Modern NVMe SSDs are incredibly fast, but existing key-value stores struggle to keep up. SplinterDB introduces a novel STB-tree data structure and a "flush-then-compact" policy to achieve significantly higher insertion and query throughput, while also reducing write amplification, making full use of NVMe capabilities.

What Problem Does This Paper Address?

Key-value stores are fundamental building blocks for many applications. With the advent of high-performance NVMe solid-state drives (SSDs), which offer much higher bandwidth and lower latency than previous storage technologies, there's a growing mismatch. Existing key-value stores, like Google's LevelDB and Facebook's RocksDB, are often CPU-bound when trying to utilize NVMe speeds, especially with small key-value pairs. This bottleneck arises from inefficiencies like repeated data reads during compaction, cache misses, and thread contention. The paper aims to bridge this gap by designing a key-value store that can fully exploit NVMe bandwidth.

Methods

SplinterDB's core innovation is the STB-tree, a new data structure that blends ideas from log-structured merge trees (LSM trees) and B-trees. It aims to reduce write amplification and CPU costs while maintaining query performance. Key aspects include:

  • STB-tree Structure: A "tree-of-trees" design with a "trunk tree" and multiple "branch trees." Branches store the actual data, and trunk nodes manage metadata and pointers.
  • Flush-then-Compact Policy: This policy decouples the flushing of data from its compaction. Flushes are performed quickly, and compactions happen asynchronously in the background. This allows for more concurrency and better handling of workloads with locality.
  • Concurrent Memtable and Cache: A highly concurrent memtable and a user-level cache are designed to minimize cache misses and avoid contention, further boosting performance.
  • Quotient Filters: Instead of Bloom filters, SplinterDB uses quotient filters, which offer similar space efficiency but faster insert and query operations.
  • Distributed Reader-Writer Locks: These are used to manage access to the cache, allowing for high read concurrency without significant contention.

Datasets

The paper evaluates SplinterDB using the Yahoo Cloud Services Benchmark (YCSB). They use traces derived from YCSB workloads (A-F) with 24-byte keys and 100-byte values, as well as 1KiB values. They also compare against existing key-value stores like RocksDB and PebblesDB.

Key Insights and Ideas

  • CPU is the New Bottleneck: For NVMe SSDs, the performance bottleneck has shifted from the storage device itself to the CPU, due to inefficiencies in existing data structures and algorithms.
  • STB-tree's Hybrid Approach: Combining the strengths of LSM trees (write amplification reduction) and B-trees (query performance) in the STB-tree is a promising direction for high-performance storage.
  • Decoupling Flush and Compact: The "flush-then-compact" strategy is crucial for unlocking concurrency and adapting to workloads with varying degrees of locality. It allows compactions to be more efficient by skipping data that's already been flushed.
  • Locality Exploitation: SplinterDB's design naturally adapts to workloads with locality, leading to significantly better performance on sequential insertions compared to systems that rely on more general-purpose compaction strategies.
  • Low-Memory Resilience: The design prioritizes efficient operation even in low-memory environments, a critical factor for many real-world deployments.

Key Results

  • Insertion Throughput: SplinterDB outperforms RocksDB by 6-10x on insertions.
  • Query Throughput: SplinterDB is 1.5-3x faster than RocksDB and PebblesDB on point queries.
  • Write Amplification: SplinterDB reduces write amplification by 2x compared to RocksDB.
  • NVMe Bandwidth Utilization: SplinterDB can fully utilize NVMe SSD bandwidth, especially for small key-value pairs, achieving throughput close to the device's advertised capabilities.
  • Sequential Insertions: SplinterDB shows a 76% speedup on purely sequential insertions compared to random ones, with write amplification approaching 1. RocksDB shows a much smaller speedup (35%).
  • Concurrency Scaling: SplinterDB exhibits nearly linear read concurrency scaling up to 24 threads, reaching 88-95% of the device's random read capability. Insertion concurrency also scales well.

Limitations and Future Work

  • Small Range Queries: Like other size-tiered systems, SplinterDB sacrifices some performance on small range queries, though it aims to minimize this impact.
  • Space Usage: Size-tiering can temporarily increase space usage until compactions occur.
  • Memory Constraints: While SplinterDB is designed for low-memory scenarios, its performance is still influenced by available RAM. The paper notes that for very large key-value pairs, other systems might be competitive if memory is plentiful.
  • Future Work: The paper suggests that the STB-tree and flush-then-compact policy are orthogonal to other optimizations like hardware acceleration (flash translation layers, vector interfaces) and can be combined with them.

Summary updated

BibTeX
@inproceedings{conway2020splinterdb,
  author = {Alexander Conway and Abhishek Gupta and Vijay Chidambaram and Martin Farach-Colton and Richard P. Spillane and Amy Tai and Rob Johnson},
  title = {{SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores}},
  booktitle = {USENIX ATC},
  year = {2020},
  url = {https://openreview.net/forum?id=XhMETZyRBw},
}
Figure