Now Reading
How RocksDB works – Artem Krylysov

How RocksDB works – Artem Krylysov

2023-04-19 18:39:41

How RocksDB works


Over the previous years, the adoption of RocksDB elevated dramatically. It turned an ordinary for embeddable key-value shops.

At this time RocksDB runs in manufacturing at Meta, Microsoft, Netflix, Uber. At Meta RocksDB serves as a storage engine for the MySQL deployment powering the distributed graph database known as TAO.

Huge tech corporations will not be the one RocksDB customers. A number of startups have been constructed round RocksDB – CockroachDB, Yugabyte, PingCAP, Rockset.

I spent the previous 4 years at Datadog constructing and working companies on prime of RocksDB in manufacturing. On this publish, I am going to give a high-level overview of how RocksDB works.

What’s RocksDB

RocksDB is an embeddable persistent key-value retailer. It is a sort of database designed to retailer giant quantities of distinctive keys related to values. The straightforward key-value information mannequin can be utilized to construct search indexes, document-oriented databases, SQL databases, caching programs and message brokers.

RocksDB was forked off Google’s LevelDB in 2012 and optimized to run on servers with SSD drives.
At the moment, RocksDB is developed and maintained by Meta.

RocksDB is written in C++, so moreover to C and C++, the С bindings enable embedding the library into purposes written in different languages reminiscent of Rust, Go or Java.

For those who ever used SQLite, you then already know what an embeddable database is! Within the context of databases, and notably within the context of RocksDB, “embeddable” means:

  • The database would not have a standalone course of, it is as an alternative linked along with your utility.

  • It would not include a built-in server that may be accessed over the community.

  • It isn’t distributed, which means it doesn’t present fault tolerance, replication, or sharding mechanisms.

It’s as much as the appliance to implement these options if vital.

RocksDB shops information as a set of key-value pairs. Each keys and values will not be typed, they’re simply arbitrary byte arrays. The database gives a low-level interface with a number of capabilities for modifying the state of the gathering:

  • put(key, worth): shops a brand new key-value pair or updates an current one

  • merge(key, worth): combines the brand new worth with the prevailing worth for a given key

  • delete(key): removes a key-value pair from the gathering

Values could be retrieved with level lookups:

An iterator permits “vary scans” – in search of to a selected key and accessing subsequent key-value pairs so as:

Log-structured merge-tree

The core information construction behind RocksDB is named the Log-structured merge-tree (LSM-Tree). It is a tree-like construction organized into a number of ranges, with information on every degree ordered by key. The LSM-tree was primarily designed for write-heavy workloads and was launched in 1996 in a paper underneath the identical title.

The highest degree of the LSM-Tree is stored in reminiscence and comprises probably the most lately inserted information. The decrease ranges are saved on disk and are numbered from 0 to N. Degree 0 (L0) shops information moved from reminiscence to disk, Degree 1 and under retailer older information. When a degree turns into too giant, it is merged with the subsequent degree, which is often an order of magnitude bigger than the earlier one.

Be aware

I will be speaking particularly about RocksDB, however many of the ideas lined apply to many databases that makes use of LSM-trees underneath the hood (e.g. Bigtable, HBase, Cassandra, ScyllaDB, LevelDB, MongoDB WiredTiger).

To raised perceive how LSM-trees work, let’s take a more in-depth have a look at the write and skim paths.

Write path


The highest degree of the LSM-tree is named the MemTable. It is an in-memory buffer that holds keys and values earlier than they’re written to disk. All inserts and updates all the time undergo the memtable. That is additionally true for deletes – fairly than modifying key-value pairs in-place, RocksDB marks deleted keys by inserting a tombstone file.

The memtable is configured to have a selected dimension in bytes. When the memtable turns into full, it’s swapped with a brand new memtable, the outdated memtable turns into immutable.

Be aware

The default dimension of the memtable is 64MB.

Let’s begin by including a number of keys to the database:

db.put("chipmunk", "1")
db.put("cat", "2")
db.put("raccoon", "3")
db.put("canine", "4")

As you’ll be able to see, the key-value pairs within the memtable are ordered by their key. Though chipmunk was inserted first, it comes after cat within the memtable because of the sorted order. The ordering is a requirement for supporting vary scans and it makes some operations, which I’ll cowl later extra environment friendly.

Write-ahead log

Within the occasion of a course of crash or a deliberate utility restart, information saved within the course of reminiscence is misplaced. To stop information loss and be certain that database updates are sturdy, RocksDB writes all updates to the Write-ahead log (WAL) on disk, along with the memtable. This manner the database can replay the log and restore the unique state of the memtable on startup.

The WAL is an append-only file, consisting of a sequence of data. Every file comprises a checksum, a key-value pair, and a file sort (Put/Merge/Delete). Not like within the memtable, data within the WAL will not be ordered by key. As an alternative, they’re appended within the order wherein they arrive.


RocksDB runs a devoted background thread that persists immutable memtables to disk. As quickly because the flush course of is full, the immutable memtable and the corresponding WAL are discarded. RocksDB begins writing to a brand new WAL and a brand new memtable. Every flush produces a single SST file on L0. The produced information are immutable – they’re by no means modified as soon as written to disk.

The default memtable implementation in RocksDB relies on a skip list. The information construction is a linked listing with further layers of hyperlinks that enable quick search and insertion in sorted order. The ordering makes the flush course of environment friendly, permitting the memtable content material to be written to disk sequentially by iterating the key-value pairs. Turning random inserts into sequential writes is without doubt one of the key concepts behind the LSM-tree design.

Be aware

RocksDB is very configurable. Like many different parts, the memtable implementation could be swapped with an alternate. It isn’t unusual to see self-balancing binary search timber used to implement memtables in different LSM-based databases.


SST stands for Static Sorted Desk (or Sorted String Desk in another databases). It is a block-based file format that organizes information into fixed-size blocks (4KB by default). Particular person blocks could be compressed with numerous compression algorithms supported by RocksDB, reminiscent of Zlib, BZ2, Snappy, LZ4, or ZSTD. Much like data within the WAL, blocks include checksums to detect information corruptions. RocksDB verifies these checksums each time it reads from the disk.

Blocks in an SST file are divided into sections. The primary part, the information part, comprises an ordered sequence of key-value pairs. This ordering permits delta-encoding of keys, which means that as an alternative of storing full keys, we are able to retailer solely the distinction between adjoining keys.

To discover a particular key, we may use binary search on the SST file blocks. RocksDB optimizes lookups by including an index, which is saved in a separate part proper after the info part. The index maps the final key in every information block to its corresponding offset on disk. Once more, the keys within the index are ordered, permitting us to discover a key shortly by performing a binary search. For instance, if we’re looking for lynx, the index tells us the important thing could be within the block 2 as a result of lynx comes after chipmunk, however earlier than raccoon.

In actuality, there is no such thing as a lynx within the SST file above, however we needed to learn the block from disk and search it. RocksDB helps enabling a bloom filter – a space-efficient probabilistic information construction used to check whether or not a component is in a set. It is saved in an non-compulsory bloom filter part and makes looking for keys that do not exist sooner.

Moreover, there are a number of different much less attention-grabbing sections, just like the metadata part.


What I described thus far is already a practical key-value retailer. However there are a number of challenges that may forestall utilizing it in a manufacturing system: house and skim amplification. Area amplification measures the ratio of space for storing to the dimensions of the logical information saved. As an instance, if a database wants 2MB of disk house to retailer key-value pairs that take 1MB, the house amplification is 2. Equally, learn amplification measures the variety of IO operations to carry out a logical learn operation. I am going to let you determine what write amplification is as a bit train.

Now, let’s add extra keys to the database and take away a number of:

db.put("cat", "5")
db.put("raccoon", "6")
db.put("zebra", "7")
// Flush triggers
db.put("cat", "8")
db.put("zebra", "9")
db.put("duck", "10")

As we preserve writing, the memtables get flushed and the variety of SST information on L0 retains rising:

  • The house taken by deleted or up to date keys isn’t reclaimed. For instance, the cat key has three copies, chipmunk and raccoon nonetheless take up house on the disk though they’re not wanted.

  • Reads get slower as their price grows with the variety of SST information on L0. Every key lookup requires inspecting each SST file to seek out the wanted key.

A background course of known as compaction helps to scale back house and skim amplification in trade for elevated write amplification. Compaction selects SST information on one degree and merges them with SST information on a degree under, discarding deleted and overwritten keys.

Leveled Compaction is the default compaction technique in RocksDB. With Leveled Compaction, key ranges of SST information on L0 overlap. Ranges 1 and under are organized to include a single sorted key vary partitioned into a number of SST information, guaranteeing that there is no such thing as a overlap in key ranges inside a degree. Compaction picks information on a degree and merges them with the overlapping vary of information on the extent under. For instance, throughout an L0 to L1 compaction, if the enter information on L0 span the whole key vary, the compaction has to choose all information from L0 and all information from L1.

For this L1 to L2 compaction under, the enter file on L1 overlaps with two information on L2, so the compaction is restricted solely to a subset of information.

Compaction is triggered when the variety of SST information on L0 reaches a sure threshold (4 by default). For L1 and under, compaction is triggered when the dimensions of the whole degree exceeds the configured goal dimension. When this occurs, it might set off an L1 to L2 compaction. This manner, an L0 to L1 compaction could cascade all the best way to the bottommost degree. After the compaction ends, RocksDB updates its metadata and removes compacted information from disk.

Be aware

See Also

RocksDB gives different compaction methods providing completely different tradeoffs between house, learn and write amplification.

Do not forget that keys in SST information are ordered? The ordering assure permits merging a number of SST information incrementally with the assistance of the k-way merge algorithm. Ok-way merge is a generalized model of the two-way merge that works equally to the merge part of the merge sort.

Learn path

With immutable SST information continued on disk, the learn path is much less refined than the write path. A key lookup traverses the LSM-tree from the highest to the underside. It begins with the energetic memtable, descends to L0, and continues to decrease ranges till it finds the important thing or runs out of SST information to test.

Listed here are the lookup steps:

  1. Search the energetic memtable.

  2. Search immutable memtables.

  3. Search all SST information on L0 ranging from probably the most lately flushed.

  4. For L1 and under, discover a single SST file that will include the important thing and search the file.

Looking out an SST file includes:

  1. (non-compulsory) Probe the bloom filter.

  2. Search the index to seek out the block the important thing could belong to.

  3. Learn the block and attempt to discover the important thing there.

That is it!

Take into account this LSM-tree:

Relying on the important thing, a lookup could finish early at any step. For instance, wanting up cat or chipmunk ends after looking the energetic memtable. Trying to find raccoon, which exists solely on Degree 1 or manul, which does not exist within the LSM-tree in any respect requires looking the whole tree.


RocksDB gives one other characteristic that touches each learn and write paths: the Merge operation. Think about you retailer an inventory of integers in a database. Sometimes it’s essential lengthen the listing. To change the listing, you learn the prevailing worth from the database, replace it in reminiscence after which write again the up to date worth. That is known as “Learn-Modify-Write” loop:

db = open_db(path)

// Learn
old_val = db.get(key) // RocksDB shops keys and values as byte arrays. We have to deserialize the worth to show it into an inventory.
old_list = deserialize_list(old_val) // old_list: [1, 2, 3]

// Modify
new_list = old_list.lengthen([4, 5, 6]) // new_list: [1, 2, 3, 4, 5, 6]
new_val = serialize_list(new_list)

// Write
db.put(key, new_val)

db.get(key) // deserialized worth: [1, 2, 3, 4, 5, 6]

The strategy works, however has some flaws:

  • It isn’t thread-safe – two completely different threads could attempt to replace the identical key overwriting one another’s updates.

  • Write amplification – the price of the replace will increase as the worth will get bigger. E.g., appending a single integer to an inventory of 100 requires studying 100 and writing again 101 integers.

Along with the Put and Delete write operations, RocksDB helps a 3rd write operation, Merge, which goals to resolve these issues. The Merge operation requires offering a Merge Operator – a user-defined operate answerable for combining incremental updates right into a single worth:

func merge_operator(existing_val, updates) {
        combined_list = deserialize_list(existing_val)
        for op in updates {
        return serialize_list(combined_list)

db = open_db(path, {merge_operator: merge_operator})
// key's worth is [1, 2, 3]

list_update = serialize_list([4, 5, 6])
db.merge(key, list_update)

db.get(key) // deserialized worth: [1, 2, 3, 4, 5, 6]

The merge operator above combines incremental updates handed to the Merge calls right into a single worth. When Merge is named, RocksDB inserts solely incremental updates into the memtable and the WAL. Later, throughout flush and compaction, RocksDB calls the merge operator operate to mix the updates right into a single giant replace or a single worth each time it is potential. On a Get name or an iteration, if there are any pending not-compacted updates, the identical operate is named to return a single mixed worth to the caller.

Merge is an efficient match for write-heavy streaming purposes that continuously must make small updates to the prevailing values. So, the place is the catch? Reads grow to be dearer – the work completed on reads is just not saved. Repetitive queries fetching the identical keys need to do the identical work time and again till a flush and compaction are triggered. Like virtually every part else in RocksDB, the conduct could be tuned by limiting the variety of merge operands within the memtable or by decreasing the variety of SST information in L0.


If the efficiency is vital on your utility, probably the most difficult facet of utilizing RocksDB is configuring it appropriately for a selected workload. RocksDB gives quite a few configuration choices, and tuning them typically requires understanding the database internals and diving deep into the RocksDB supply code:

“Sadly, configuring RocksDB optimally is just not trivial. Even we as RocksDB builders do not totally perceive the impact of every configuration change. If you wish to totally optimize RocksDB on your workload, we advocate experiments and benchmarking, whereas maintaining a tally of the three amplification components.”

Official RocksDB Tuning Guide

Remaining ideas

Writing a production-grade key-value retailer from scratch is tough:

RocksDB solves this permitting you to deal with the enterprise logic as an alternative. This makes RocksDB a wonderful constructing block for databases.

Source Link

What's Your Reaction?
In Love
Not Sure
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top