Evolution of Development Priorities in Key-value Stores Serving Large-scale Applications: The RocksDB Experience

In one breath — the whole paper, compressed

RocksDB is an embedded LSM-tree key-value library that Facebook forked from LevelDB in 2012 and now runs under more than 30 internal applications holding hundreds of petabytes. This paper is not a new algorithm but an eight-year field report on which resource actually hurts: the team began by minimizing write amplification to protect flash erase cycles, found from fleet measurement that most deployments were bounded by disk space instead and built Dynamic Leveled Compaction to hold space overhead near 13 percent, and only later turned to CPU and DRAM, not because SSDs outran software but because CPU and memory grew expensive relative to flash. Running one RocksDB instance per shard, with tens or hundreds of instances per host, forced host-wide resource controllers, thread pools, configurable WAL modes and rate-limited file deletion; monthly releases rolled out and rolled back host by host forced both backward and forward on-disk format compatibility. Production also showed that block checksums are not enough: corruption is introduced at the RocksDB level roughly once every three months per 100PB, and 40 percent of the time it has already reached other replicas, which pushed integrity checking up into the MemTable and block cache and down into a handoff checksum given to the storage layer. The paper closes by conceding that three of its own founding beliefs were wrong: that customizability is always good for users, that RocksDB may be blind to CPU bitflips, and that panicking on any I/O error is acceptable.

Before this paper — the world it landed in

Before RocksDB, an application that wanted local persistent storage on a server either embedded something like LevelDB or BerkeleyDB, or pushed its data to a remote storage service. Flash SSDs had just made the second option unattractive: a device serving hundreds of thousands of IOPS moved the bottleneck off storage and onto the network, so keeping data on locally attached flash and embedding the engine inside the application became the natural design. But LevelDB was written for one modest workload; it had a single compaction strategy, options baked directly into code, and no story at all for running dozens of instances on one host. Meanwhile the community consensus around 2011, exemplified by work like SILT, was that write amplification was the number to minimize, since flash program/erase cycles are finite and B-tree engines like InnoDB rewrite an entire 4KB to 16KB page for a change of under 100 bytes. RocksDB started from that consensus, and much of this paper is the story of discovering it was not the right first-order target for most of Facebook's fleet.

The problem — what was actually breaking

Flash SSDs deliver hundreds of thousands of IOPS but tolerate only a limited number of program/erase cycles, so a storage engine that rewrites whole pages for small updates burns through the device's endurance budget.
Letting every application build its own storage layer is wasteful and dangerous, because even a simple one must checksum against media corruption, stay consistent across crashes, issue durability syscalls in the correct order, and correctly handle every error the file system returns.
A single engine has to serve workloads with contradictory priorities: databases want balanced reads and writes plus transactions, stream processing and logging are write-heavy, index services are read-heavy with bulk loading, and SSD caches are allowed to simply drop data.
A distributed service partitions data into shards and gives each shard its own RocksDB instance, so one host ends up running tens or hundreds of instances contending for memory, compaction threads, I/O bandwidth, disk space and file-deletion rate with no global arbiter.
Continuous deployment ships a new RocksDB release every month and rolls it out and back host by host, so data written by one binary must be readable by both older and newer binaries, including when SSTable files are copied between instances running different versions.
Checksums that cover only data at rest or data on the wire miss corruption introduced above the file I/O layer, in the MemTable or block cache, where a flush or compaction can make a bitflip permanent and replication can spread it to healthy replicas.

Core ideas — the contributions, and why they work

LSM-tree as the flash-native structure

RocksDB committed to the Log-Structured Merge tree from day one because flash has asymmetric read/write performance and finite erase cycles. Writes are absorbed in memory and turned into large sequential file writes, so the engine never issues the small random in-place page overwrites a B-tree does, which is exactly where InnoDB's write amplification comes from. The same layout is also compact: SSTables are written once, fully packed and immutable, so there is none of the internal page fragmentation B-trees carry, and that non-fragmented layout is what later let the team pivot cleanly to space as the target. The authors keep re-asking whether LSM is still the right structure and keep answering yes, because SSD prices have not fallen enough to make trading flash away for CPU or DRAM worthwhile for most use cases.

Compaction style as the workload dial

Rather than pick one point on the read, write and space triangle, RocksDB exposes the compaction algorithm itself as a configuration choice. Leveled Compaction, inherited and improved from LevelDB, gives exponentially growing levels holding one sorted run each, so reads touch roughly one file per level and space overhead stays small, but write amplification usually lands between 10 and 30. Tiered Compaction, called Universal in RocksDB and similar to what Cassandra and HBase do, merges sorted runs lazily and cuts write amplification to the 4 to 10 range at the cost of many more sorted runs to search on every read. FIFO Compaction simply discards the oldest files once the database hits a size limit, which is nonsense for a database but exactly right for an in-memory cache spilling to SSD that is permitted to lose data. Because the tuning knob is the algorithm and not merely its parameters, one library covers write-heavy logging, balanced databases and cache workloads alike.

The moving optimization target

The central narrative is that the resource worth optimizing changed twice, and each change was driven by fleet measurement rather than by theory. Write amplification came first, following community consensus about protecting erase cycles, and leveled compaction beat B-trees decisively, issuing only 5 percent as many writes per transaction as InnoDB under LinkBench. Measurement then showed that IOPS and flash endurance were mostly idle while disk space was the binding constraint, so space amplification became the target and Dynamic Leveled Compaction was built for it. Only after the easy space wins were harvested did CPU and DRAM matter, and even then the authors reject the popular claim that SSDs have outrun software; their argument is economic, since CPU and memory prices rose relative to SSDs, making CPU reduction a cost lever that enables cheaper hardware configurations rather than a throughput fix.

Dynamic Leveled Compaction

Classic leveled compaction assigns each level a static size target, which means the last level, where nearly all the data lives, can sit far below its configured target while the upper levels accumulate dead data waiting to be merged down. Dynamic Leveled Compaction inverts the calculation: it measures the actual size of the last level and derives every other level's target from it, so the tree always maintains the intended exponential ratio against real data instead of against a configured constant. The effect is that the fraction of the database that is deleted or overwritten data is bounded much more tightly and, crucially, stays stable rather than drifting as the database grows. In a random-write benchmark it holds space overhead near 13 percent where LevelDB-style leveling drifts past 25 percent, and the paper notes leveled worst-case overhead can reach 90 percent while dynamic leveling stays stable.

Resource management across instances

Because a shard is the unit of load balancing and replication and must be copied between nodes atomically, its size is bounded, so a host runs tens or hundreds of RocksDB instances rather than one large one. That turns local tuning into a global problem: write buffers, block cache, compaction threads, compaction I/O bandwidth, total disk usage and file-deletion rate must be capped both per instance and per host, potentially on a per-I/O-device basis. RocksDB's answer is explicit resource controller objects created by the application and passed into several DB objects so multiple instances draw from one shared budget, plus prioritization so the instance that needs a resource most receives it. When instances live in separate processes the problem is much harder because each sees only local information, and the paper offers only two imperfect strategies: configure each instance conservatively and underuse the host, or have instances exchange usage information and adapt.

Corruption detection at every layer

The block checksum inherited from LevelDB only proves that what came back from the file system matches what was handed to it, which leaves everything above the file I/O layer unprotected. Production data shows this matters: corruption originates inside RocksDB roughly once per 100PB per three months, and 40 percent of the time it has already been replicated before anyone notices, at which point discarding the bad replica no longer helps because there may be no correct one left. RocksDB therefore layers four checks: per-key-value checksums that travel with the record through MemTable and block cache, block checksums verified on every read, whole-file checksums recorded in metadata and verified whenever an SSTable is copied for replica building or backup, and handoff checksums passed down so the storage layer verifies at write time. The governing principle is the classic end-to-end argument applied per layer: each layer should catch its own errors as early as possible, because the cost of a corruption grows with how far it travels before detection.

User-defined timestamps in the KV interface

RocksDB already keeps 56-bit internal sequence numbers per key version, but the application cannot set them, cannot ask for a snapshot of a past instant it did not register in advance, and cannot correlate sequence numbers across instances, so cross-shard consistent reads are essentially impossible. Applications work around this by encoding a timestamp into the key, which destroys point lookups because the exact key is no longer known, or into the value, which makes out-of-order writes to the same key and reads of old versions expensive. The proposed fix is to make the timestamp a first-class field attached to the key-value pair, chosen by the application but understood by RocksDB. Keeping it outside the user key means Bloom filters still work on the key and point lookups replace iterators, and each SSTable can record the timestamp range it covers so files that could only contain stale values are excluded before being opened.

How it works — the mechanism, concretely

Write path: MemTable, WAL, flush

A write goes into an in-memory MemTable, implemented as a skiplist so keys stay ordered with O(log n) insert and search, and also into an on-disk write-ahead log. When the MemTable reaches its configured size the engine makes both the MemTable and the WAL immutable, allocates a fresh pair for subsequent writes, flushes the frozen MemTable into a Sorted String Table file on disk, then discards the frozen MemTable and its associated WAL. Each SSTable stores data in sorted order divided into uniformly sized blocks, plus an index block with one entry per block so a lookup inside the file is a binary search. The WAL is not mandatory, which matters because the distributed systems above RocksDB usually maintain their own replication log, for example a Paxos log, and do not need a second one.

Leveled compaction and level targets

Freshly flushed SSTables land in Level-0, where files may have overlapping key ranges because each file is a complete sorted run in its own right. Every level above Level-0 contains exactly one sorted run partitioned across files, so within such a level a given key can live in at most one file. Levels are assigned exponentially increasing size targets; when level L exceeds its target, RocksDB selects some of its SSTables and merges them with the overlapping SSTables in level L+1, dropping deleted and overwritten versions in the process and rewriting the output optimized for reads and space. Compaction I/O consists of bulk sequential reads and writes of entire files and can be parallelized, which is why it suits SSDs; under dynamic leveling the size targets themselves are recomputed from the observed size of the last level rather than fixed.

Read path and Bloom filters

A Get searches all MemTables first, then all Level-0 SSTables since their ranges overlap, then each successively higher level, stopping as soon as the key is found or the last level is exhausted. Within a level a binary search over the index block locates the candidate block, and a per-SSTable Bloom filter eliminates most files that cannot contain the key before any data block is read. Measured under RocksDB 5.9, leveled compaction needs about 0.99 I/Os per Get with Bloom filters and 1.7 without, while tiered needs 3.39 without filters because there are 12 sorted runs to visit. Scans are the weak case: an iterator must position itself in every level and cannot use Bloom filters at all, which is why FIFO compaction shows 967 I/Os per iterator seek against 1.84 for leveled.

WAL modes and rate-limited file deletion

Because replicated systems often already log durably elsewhere, RocksDB offers three WAL behaviours: synchronous writes on every operation, buffered writes that a low-priority background thread periodically pushes to disk so foreground latency is untouched, and no WAL at all. A separate operational hazard is file deletion: on a flash-aware file system such as XFS with realtime discard, deleting a file issues a TRIM, and TRIM makes the SSD firmware update its address mapping, journal that change into the FTL log in flash, and possibly trigger internal garbage collection with considerable data movement. Since a single compaction deletes several input files at once, the resulting TRIM burst surfaces as a foreground I/O latency spike. RocksDB therefore rate-limits file deletion so files are removed gradually instead of simultaneously, keeping the endurance benefit of TRIM without the latency spikes.

Resource controllers and thread pools

Applications create resource controller objects, one or more per resource type, as C++ objects passed into several DB objects so those instances draw from a shared budget; per-instance controllers additionally cap any single instance's appetite, and priorities decide who wins under contention. The controlled resources the paper names are write-buffer and block-cache memory, compaction I/O bandwidth, compaction threads, total disk usage and file-deletion rate, and it notes these limits may need to be maintained per I/O device. A second hard-won rule is never to liberally spawn unpooled long-lived threads: too many threads cause excessive context switching, I/O spikes and extremely difficult debugging, so any work that may sleep or wait on a condition belongs in a thread pool whose size and resource usage can be capped. Cross-process coordination remains unsolved, since a process running one shard has only local information.

The four-checksum stack

Block checksums cover each SSTable block and each WAL fragment, are generated when the data is created, and are verified on every read because their scope is small, so anything corrupted at or below the file system is caught before it reaches the client. File checksums, added in 2020, cover a whole SSTable, are recorded in the database metadata's file entry, and are re-validated whenever the file travels for replica building or backup, catching corruption introduced by the transfer path itself. Handoff checksums are computed on data about to be written and passed down with it so the layer below verifies at write time; local file systems rarely support such a write API, though specialized stacks like Oracle ASM do and a remote storage service can hook it into its internal ECC, and RocksDB can combine existing WAL fragment checksums to compute the handoff value cheaply. Per-key-value checksums, still being implemented when the paper was written, travel with each record through MemTable and block cache and are checked at flush and compaction, closing the gap above the file I/O layer.

Versions: sequence numbers, snapshots, timestamps

Internally every client write increments a 56-bit sequence number, so multiple versions of the same key coexist in the LSM tree distinguished by that number, and compaction is what eventually removes versions nobody can observe. An application may take a Snapshot, after which RocksDB guarantees every key-value pair existing at that moment persists until the snapshot is explicitly released, but snapshots must be taken in advance, there is no API to name a past point in time, and they are scoped to a single instance, so nothing coordinates versions across shards. The user-defined timestamp extension adds an application-chosen timestamp as metadata attached to the pair rather than concatenated into the key or buried in the value. Because the user key stays intact, a point lookup with a Bloom filter still works instead of an iterator, and SSTable properties can record the timestamp range covered so files that could only contain stale values are excluded from the read.

What the paper showed — measurements and proofs

Under RocksDB 5.9 with direct I/O and a block cache sized at 10 percent of the fully compacted database, leveled compaction shows write amplification 16.07 with 9.5 percent average space overhead, tiered with 12 sorted runs shows 4.8 with 45.5 percent average overhead, and FIFO shows 2.14 but needs 528 I/Os per Get without a filter (Table 3).
In a random-write micro-benchmark at a constant 2MB/s write rate, Dynamic Leveled Compaction holds space overhead between 11.8 and 12.7 percent from 200 million to 1 billion keys, while LevelDB-style leveling ranges from 12.2 up to 25.6 percent; the text adds that leveled worst-case overhead can reach 90 percent (Table 4).
Replacing InnoDB with RocksDB reduced the space footprint of UDB, one of Facebook's main databases, to 50 percent, and under LinkBench on MySQL RocksDB issues only 5 percent as many writes per transaction as InnoDB.
A survey of 42 production ZippyDB and MyRocks deployments measured over one month found most workloads space-constrained rather than CPU- or endurance-constrained: the representative cache workload runs at 78 percent space utilization and 74 percent flash endurance but only 3 percent CPU, while stream processing runs at 48 percent space and 11 percent CPU (Table 2, Fig. 3).
Comparing primary against secondary indexes in MyRocks tables shows corruption is introduced at the RocksDB level about once every three months per 100PB of data, and in 40 percent of those cases it had already propagated to other replicas; separately, one storage-system bug in network failure handling produced roughly 17 checksum mismatches per petabyte of physical data transferred.
The user-defined timestamp API beats the baseline of encoding the timestamp inside the key by 1.2x on fill_seq plus read_random and by 2.0x on fill_random plus read_while_writing in DB_bench (Table 6), while 39 sampled ZippyDB deployments used over 25 distinct configurations, 14 of them differing in compaction settings alone (Table 5).

Limits and trade-offs — conceded and discovered

The paper concedes that its early bet on maximal customizability backfired: there are now far too many options, their effects are too difficult to understand, the optimal setting depends on the workload above the embedding system and not just the system itself, and third parties shipping MySQL or ZippyDB have neither the knowledge nor the appetite to tune RocksDB.
The authors explicitly retract two safety assumptions they once held, that RocksDB could be blind to CPU and memory bitflips and that panicking on any I/O error was acceptable; per-key-value checksums and retriable-error recovery were both retrofits, and by their own admission WAL files still lack whole-file checksums while local file systems still cannot accept handoff checksums.
The paper concedes that pursuing automatic adaptivity while retaining full explicit configurability, and holding both backward and at least one year of forward on-disk compatibility, imposes significant and permanent code-maintenance overhead, which they accept as the price of one consolidated engine.
The proposed user-defined timestamp is admitted to be a mixed blessing: the API is more complicated and perhaps prone to misuse, the database consumes more disk space than storing no timestamp, and the data becomes less portable to other key-value systems.
Because RocksDB is deliberately a single-node library, replication, backup, consistent update ordering and cross-shard versions are all pushed onto the application, and the authors report users still demanding lower write amplification than RocksDB can provide; their answer, key-value separation in the style of WiscKey, was only being added as BlobDB at publication, and later forks such as CockroachDB's Pebble and Speedb suggest not everyone was satisfied with the trade-offs as shipped.

What it became — the systems that inherited it

RocksDB became the default answer to the question of where a distributed system keeps its bytes on a single node. MySQL got MyRocks, whose halving of UDB's footprint is the paper's headline space result; Facebook's ZippyDB, LogDevice, Dragon and Rockset were built on top of it; CockroachDB, TiDB's TiKV, MongoDB and Rocksandra adopted it as a pluggable engine; and Apache Flink, Kafka Streams and Samza all use it as their local state backend, which is why an LSM-tree now sits underneath most stream-processing checkpoints. The compaction vocabulary this paper codifies, leveled versus tiered versus FIFO plus dynamic level sizing, became the frame in which later LSM research argues, and RocksDB is the baseline that PebblesDB, SlimDB, Monkey, WiscKey and their successors measure themselves against. Not everyone kept the original: CockroachDB replaced RocksDB with Pebble, a Go engine that keeps the file format and much of the design but sheds the configuration surface this paper complains about, and Speedb forked RocksDB outright, both of which are the configuration-sprawl limitation playing out in public. The failure-handling section has aged into standard practice, with per-record and whole-file checksums now expected of any engine whose files get shipped between replicas. Most influentially, the empirical finding that space, not IOPS or flash endurance, binds the majority of SSD deployments redirected a research community that had spent a decade minimizing write amplification, and it helped legitimize the industrial experience report as a first-class FAST and OSDI contribution.

In the paper’s words — verbatim

“We describe how and why RocksDB's resource optimization target migrated from write amplification, to space amplification, to CPU utilization.”

Abstract

“Second, we find that any server with a high-end CPU has more than enough compute power to saturate one high-end SSD. RocksDB has never had an issue making full use of SSD performance in our environment.”

§3 CPU utilization

“Based on our measurements, corruptions are introduced at the RocksDB level roughly once every three months for each 100PB of data. Worse, in 40% of those cases, the corruption had already propagated to other replicas.”

§5 Frequency of silent corruptions

Vocabulary — as this paper uses it

LSM-tree (Log-Structured Merge tree): The layered structure RocksDB uses: an in-memory buffer plus a sequence of levels of immutable sorted files, where new data enters at the top and migrates downward by merging. It converts random updates into large sequential file writes at the cost of consulting several levels per lookup.
MemTable: The in-memory write buffer, implemented as a skiplist so keys stay ordered with O(log n) insert and search. When it reaches its configured size it is made immutable, flushed to an SSTable, and discarded together with its write-ahead log.
SSTable (Sorted String Table): An immutable on-disk file holding keys in sorted order, divided into uniformly sized blocks, with an index block carrying one entry per data block and usually a Bloom filter. Every level of the LSM-tree is built out of these files.
Write amplification: In this paper, total SSTable file writes divided by the number of MemTable bytes flushed, with WAL writes excluded. It matters because flash tolerates only a limited number of program/erase cycles, and the SSD itself adds a further 1.1x to 3x on top of whatever the software generates.
Space amplification: The extra space a database occupies beyond what its live data would need if fully compacted, reported here as a space overhead percentage. It became RocksDB's main optimization target once fleet measurement showed disk space, not IOPS or endurance, was the binding constraint.
Leveled, Tiered and FIFO compaction: The three compaction styles RocksDB offers: leveled keeps one sorted run per level with exponentially growing size targets, tiered (called Universal here, as in Cassandra and HBase) merges sorted runs lazily to cut write amplification, and FIFO simply drops the oldest files at a size limit for cache workloads.
Dynamic Leveled Compaction: A variant of leveled compaction in which each level's size target is derived from the measured actual size of the last level instead of being set statically by configuration. It keeps space overhead near 13 percent and, more importantly, keeps it stable as the database grows.
Handoff checksum: A checksum computed on data about to be written and passed down along with the data, so the layer below verifies it at write time rather than waiting until read time. RocksDB wants this for WAL appends, but local file systems rarely offer such a write API.
User-defined timestamp: An application-chosen version tag stored as metadata attached to a key-value pair, distinct from RocksDB's internal 56-bit sequence number and kept outside both key and value. It preserves point lookups and Bloom filter usefulness while enabling point-in-time reads and cross-shard consistent versions.

On the timeline — where this sits in the story

Year2012–2013

MilestoneRocksDB

Problem solvedDistributed applications needed an embeddable high-performance key-value engine optimized for SSDs and large write-heavy workloads.

How it solved itRocksDB industrialized LSM-tree storage with production tuning, compaction control, and SSD-oriented performance.

Why it matteredBecame a storage-engine substrate for many databases, stream processors, and distributed systems.

DDIACh. 4: Storage & Retrieval

View on the timeline