RocksDB

RocksDB consists of three core components: a memtable, a log file, and a sorted strings table.

The memtable is an in-memory data structure that temporarily holds incoming write operations.

RocksDB uses a skip-list, a sorted set data structure, as its default implementation.

Alternative implementations exist, such as a red-black tree.

A memtable can be viewed as a self-balancing binary tree structure.

The write-ahead log is an append-only file stored on disk.

For every write request, the database appends key-value records to this file.

The primary purpose of the WAL is to allow recovery of the memtable after a crash.

The sorted strings table is a file containing key-value pairs sorted by key.

The question arises: if the WAL captures writes, does this mean data is stored twice?

We will address this shortly.

When a write request arrives, the database stores data in two places:

• In memory, within the memtable
• In the write-ahead log file on disk

As the memtable fills, it reaches capacity.

When full, the memtable is written to disk as an SS-table file.

This process is efficient because the memtable is a binary search tree, with keys already sorted.

An in-order traversal of the tree enables quick, sorted output to disk.

Upon writing, the memtable becomes immutable and read-only.

A background thread continuously flushes memtable content to disk.

A new active memtable is allocated, and all writes are directed to it.

When this new memtable fills, it too becomes read-only and enters a flush pipeline.

The background thread continues flushing all read-only memtables in the pipeline.

At any moment, the system may have multiple memtables in memory:

• One active memtable accepting all writes
• Several read-only memtables being flushed to disk

Each memtable has a corresponding log file.

A new write-ahead log is created when a new memtable is initialized.

When a memtable is written to an SS-table, all data in its associated log file has been persisted.

The log file is then archived.

Archived logs are eventually purged after a defined retention period.

When a read request arrives, the database follows this sequence:

• First, it checks the active memtable
• If the key is not found, it scans all read-only memtables
• If the key is not found in memory, it searches SS-table files, starting from the most recent

Log files are not used during read operations.

Sorting keys enables efficient search.

This is analogous to hash indexes, where keys are stored in a hash table with file offsets.

To retrieve a record, the system first looks up the offset in the hash table, then seeks to that position in the file.

A major drawback of this approach is that it requires a large file seek, which is slow.

Sorting keys allows binary search, which drastically reduces search time.

This is why keys are stored in sorted order in SS-tables.

The sorted order enables fast, logarithmic-time lookups during reads.

When keys are sorted, not all keys need to be stored in memory. Instead, only a subset of keys—along with their file offsets—is kept in memory.

This works because any key in the database must lie between two known keys. Thus, the system only needs to track a few representative keys and their positions.

To find a key like F:

1. Use binary search on the hash table index to locate the range where F falls.
2. Determine that F lies between keys D and G.
3. Retrieve the offset for key D.
4. Seek to the start of the corresponding record in the ss table.
5. Scan records sequentially until key F is found.

Keys in memory index point to the start of a block.

• Blocks group multiple key-value pairs into a few kilobytes.
• The entire block is read from disk in a single disk scan.
• Blocks can be compressed to save disk space and reduce I/O.

If a key does not exist:

• The database scans all memtables and all ss table files.
• This process can be slow due to extensive disk and memory traversal.

Bloom filters are memory-efficient data structures that quickly determine if a key is absent.

• If a bloom filter indicates the key is not in the ss table, no binary search is needed.
• In ROG-CDB, bloom filters can be configured for both ss tables and memtables.
• For large memtables, bloom filters reduce CPU usage.

Periodically, the database runs compaction to remove duplicates and deleted keys.

• Multiple ss table files are merged into one large ss table.
• Keys are sorted, enabling efficient merging.
• A background thread iterates over sorted files, selecting the smallest key at each step.
• This process mirrors the merge sort algorithm.