Table of Contents

• Introduction
• Write Path and Storage Layout
  • Without Key-Value Separation
  • BadgerDB
  • TerarkDB
  • Titan and BlobDB
  • Comparison of Write Paths
• Garbage Collection
  • Garbage Collection in BadgerDB
  • Compaction and Garbage Collection in TerarkDB
  • Garbage Collection in Titan
  • Garbage Collection in BlobDB
  • Comparison of Garbage Collection Strategies
• Read Path of Large Values
  • BadgerDB
  • TerarkDB
  • Titan and BlobDB
  • Comparison of Read Paths
• Alternative Implementation — Neon Page Server
• Summary
  • References

Introduction

General-purpose LSM storage engines, such as LevelDB and RocksDB, store user-written keys and values together in ordered SSTs (Sorted String Tables). During compaction, the engine merges SSTs from one level with overlapping SSTs in another level to produce new files. This process rewrites both keys and values, resulting in significant write amplification. If values are much larger than keys, rewriting them can introduce substantial overhead.

In WiscKey (FAST ’16), the authors proposed an SSD-friendly LSM-tree design that reduces write amplification by separating keys from values. Large values are stored elsewhere, while the LSM tree stores a value pointer (vptr) to each value’s location. WiscKey calls this separate storage the value log (vLog). LSM-tree compaction can then reorganize key indexes without rewriting the values themselves, reducing write amplification and SSD wear.

The idea sounds straightforward, but a practical implementation must answer several questions:

• How should the vLog be organized and compressed?
• After a user deletes a value, how should the engine reclaim the resulting garbage?
• When reclaiming garbage, how should the engine update vptrs in the LSM tree?
• How should the engine manage the effect of key-value separation on range scans?

Several key-value-separated LSM storage engines have emerged since WiscKey. In this article, I will introduce four open-source implementations and compare their design tradeoffs. These differences can help readers choose an engine for workloads with large values.

• BadgerDB is the closest of these engines to the key-value separation described in the WiscKey paper. It is written in Go and was developed for the Dgraph graph database.
• TerarkDB was developed by Terark, which ByteDance acquired, and is based on RocksDB.
• Titan is a RocksDB plugin used by TiKV.
• BlobDB is integrated into RocksDB and stores large values in separate blob files.

Write Path and Storage Layout

In this article, unless otherwise stated, we assume that the storage engine has enabled Write-Ahead Logging (WAL) and uses leveled compaction for LSM trees.

Without Key-Value Separation

First, let’s look at how a conventional LSM storage engine handles writes. When the engine receives a write, it records the key-value pair in both the memtable and the WAL (Write-Ahead Log). The memtable often uses a skip list. The WAL makes the memtable’s contents recoverable after a server failure; once the required WAL record is durable, the engine can acknowledge the write as persisted.

The engine performs two main kinds of background work: flushing memtables to disk and compacting the LSM tree. It may have one mutable memtable and several immutable memtables waiting to flush. When a memtable reaches its size limit, the engine writes it as an SST; its WAL can be removed after no live memtable depends on it. An SST stores ordered key-value pairs in blocks, which may be compressed, with indexes and often Bloom filters to speed up reads.

Level 0 of the LSM tree consists of multiple SST files whose key ranges may overlap. In a leveled design, files within each level from level 1 onward have non-overlapping key ranges. If a level exceeds its size limit, the storage engine compacts selected files with overlapping files in the next level. As a result, data generally moves toward lower levels over time.

Moving data through every level while an LSM tree is still small would introduce unnecessary write amplification. Many engines therefore choose a dynamic base level (Lbase), allowing early data to move there directly from level 0.

BadgerDB

BadgerDB writes large values directly to its value log (vLog), as shown below.

When a user writes a key-value pair to Badger, values below a configurable threshold stay inline in the LSM tree. For a value at or above the threshold, the write path is as follows:

• Badger first appends the key and value to the active vLog. When that file reaches its configured size, the engine creates a new one. Each vLog therefore contains records in write order.
• Badger then stores a pointer containing the vLog file id, the value’s byte length, and its offset (<fid, len, offset>) in the LSM entry. The pointer lets a read address the value directly; Badger does not search the vLog by key.

TerarkDB

Because TerarkDB is based on RocksDB, its foreground write path follows RocksDB: key-value pairs enter the memtable and WAL, and the memtable is later flushed to disk. Compared with Badger’s direct vLog path, a large value is written once to the WAL and again to the v-SST (Value SST) during the flush, adding one full-value write.

During a background flush, TerarkDB separates entries according to value size. Small values remain with their keys in an SST. Large values and their keys are written to a v-SST. Because the v-SST has index blocks, a query can locate a value by key. For a separated value, the LSM tree stores the key and the v-SST file number, <key, fileno>, without an offset.

Because a v-SST uses SST format, its large values are sorted by key and can use RocksDB’s block-level compression.

The pinned TerarkDB source defaults to a 512 B separation threshold. Its key-sorted, indexed v-SSTs can use block compression, which helps explain why separating smaller values is a reasonable design choice here. This is not a universal optimum: lowering the threshold moves more values out of the LSM tree, changing compaction work, compression opportunity, cache behavior, and read and scan I/O.

Titan and BlobDB

Titan is a RocksDB plugin, so its foreground path follows RocksDB. Its background path resembles TerarkDB’s, but it stores large values in blob files. A blob file contains key-value records in key order and can compress each record. For a separated value, Titan stores <key, <fileno, offset, size>> in the LSM tree.

BlobDB has a similar write path and also stores ordered values with per-record compression when enabled. Its LSM blob index contains the record type, file number, offset, size, and compression metadata.

Comparison of Write Paths

Garbage Collection

After users update or delete keys, a conventional LSM engine can discard obsolete records during compaction, as shown below. It can drop an old version or tombstone once no snapshot or lower-level data still needs it.

Once large values live outside the LSM tree, the engine needs a separate way to reclaim obsolete records and control space amplification.

Garbage Collection in BadgerDB

Badger estimates reclaimable space when LSM compaction drops an obsolete entry whose value is stored in the vLog. At that point, it adds the referenced value’s byte length to the discard statistic for that vLog file. Badger persists these statistics in the DISCARD file.

As shown in the above figure, applications start collection explicitly. Badger uses the discard statistics to select a vLog file, then checks each record against the LSM tree. It skips a record if its key is gone or the current LSM entry no longer points to it. Badger copies the remaining live values into a new file and writes their updated pointers back to the LSM tree.

Because those replacement pointers use the normal LSM write path, GC adds write traffic and must not overwrite a concurrent update or deletion.

As shown in the above figure, a deletion at version 10 can coexist with a GC rewrite of the older value at version 9. Unlike an ordinary LSM lookup that can return after the first matching key in the newest SSTs, Badger searches the memtables and LSM levels for the highest visible version. The version-10 deletion therefore remains visible over the rewritten version-9 entry. While the rewrite is active, Badger also prevents compaction from discarding a newer tombstone.

Compaction and Garbage Collection in TerarkDB

As shown in the above figure, TerarkDB uses each v-SST’s garbage estimate to choose files for collection. It checks each record against the LSM tree, writes the live values into new v-SSTs, and records dependencies from the old files to their replacements. A read that still points to an old v-SST follows the dependency to the latest file, so GC does not have to write every replacement file number through the foreground path.

As shown in the above figure, TerarkDB first selects the levels and files for an LSM-tree compaction. While merging those SSTs, it checks each separated value’s v-SST file number. If the referenced v-SST has been replaced, TerarkDB follows the dependency relationship and writes the new file number into the compaction output before adding the new SSTs to the LSM tree.

Over time, lower LSM levels may depend on many v-SSTs, and one v-SST may be referenced by many SSTs. TerarkDB performs a special rebuild compaction to bound and shorten these dependency chains.

Garbage Collection in Titan

Titan’s regular garbage collection resembles Badger’s: statistics identify candidate blob files, Titan rewrites their live records, and it writes new vptrs back to the LSM tree. The process is shown below.

Regular GC synchronizes pointer updates with foreground writes so it cannot overwrite later values. This can affect write throughput.

Titan also offers Level Merge, which is off by default. When enabled, compaction into the last two LSM levels can rewrite blob records and place updated blob indexes directly in the compaction output, avoiding a separate regular-GC pointer write-back.

Garbage Collection in BlobDB

BlobDB integrates garbage collection with LSM compaction. An age cutoff selects older blob files that may be rewritten, while a separate force threshold can trigger targeted compaction when enough space can be reclaimed.

Blob files are not compacted independently. Live blobs move only when LSM compaction processes their referencing SST entries.

Comparison of Garbage Collection Strategies

Read Path of Large Values

For a point lookup, an LSM engine may inspect memtables, overlapping level-0 files, and one candidate file in each lower level. Bloom filters, caches, and indexes help it skip work and find the newest visible value.

With key-value separation, the read path gains an out-of-line value lookup.

BadgerDB

Badger checks candidates through the memtables and LSM levels for the highest visible version. It then decodes the vptr and reads the value directly from the vLog.

Reading a separated value always adds one extra indirection. Badger’s scan-specific drawback is different: values are appended in write order, so nearby keys can point to distant locations in the vLog, weakening spatial locality. Badger mitigates this with configurable value prefetch, which defaults to 100 values; scan performance still depends on the workload and write order.

TerarkDB

TerarkDB first finds the v-SST file number in the LSM tree. It follows any dependency relationship to the latest v-SST, uses that file’s index to locate the key, and then reads the value.

Titan and BlobDB

Titan and BlobDB find the vptr in the LSM tree and then read the corresponding record from a blob file.

Comparison of Read Paths

Alternative Implementation — Neon Page Server

A specialized engine can apply the same broad idea to one workload without implementing a general-purpose key-value separation scheme.

Neon’s page server, the underlying storage engine of Neon’s serverless Postgres service, uses an LSM-like structure for Postgres page-version history. Redo information is generally smaller than a materialized 8 KiB page. Managing incremental history and page images as different layer types can reduce write amplification compared with eagerly materializing every page version in a general-purpose LSM-tree layout.

Neon streams WAL to the page server, which builds page-version history in memory and flushes it to delta layers. The page server can also materialize image layers containing complete page snapshots at a chosen point in the log. Keeping history and snapshots separate lets Neon compact them on different schedules.

Summary

Key-value separation can reduce LSM-tree write amplification, but it introduces other costs: more complex garbage collection and read paths, an extra out-of-line lookup, possible foreground-write interference, different compression behavior, and potentially weaker range-scan locality. Each design makes different tradeoffs, so developers should choose an engine according to their workload rather than treating separation as a universal improvement.

References

• WiscKey: Separating Keys from Values in SSD-conscious Storage
• BadgerDB source, including v2.2007.3 options, v2.2007.3 value-log encoding, v4.9.6 options, and v4.9.6 value-log encoding
• Badger value-pointer layout, discard accounting, and value-log GC API
• Badger iterator and prefetch implementation
• TerarkDB source, options, and v-SST table builder
• Titan: a RocksDB plugin for key-value separation
• Titan blob-index format, blob-record encoding, and threshold, compression, and Level Merge options
• Design and Implementation of Titan
• RocksDB BlobDB index format, options, blob-record builder, and integrated BlobDB design
• Neon page-server storage and compaction

This blog post was originally published in Simplified Chinese on August 7, 2021. The English version was translated with ChatGPT and adds material on RocksDB’s BlobDB and Neon’s page server.

Feel free to comment and share your thoughts on the corresponding GitHub Discussion for this blog post.