How a key travels: in through the log, down through the levels.

The write path

A batch, a log record, a skiplist node.

A write is a batch: puts, deletes and range deletes, possibly in several keyspaces. It takes a sequence number, its log record is written with the durability the write asked for, and its entries go into the keyspace's in-memory table, a lock-free skiplist. From then on every new snapshot sees it.

When an in-memory table is full it is frozen and a background task flushes it into a sorted table file. The file is named by a manifest that is synced before the log above it may be dropped, so a crash between the two loses nothing.

Concurrency

Many writers, no lock between them.

Every shared structure on a read or write path is lock-free or wait-free wherever a non-blocking form exists: the skiplist, the block cache, the statistics. Concurrent writers take their place in the commit order without queueing behind a lock, and readers never block them.

The building blocks live in their own crate, each documented with its specification, linearization points and memory-ordering argument, and each model-checked under loom.

The read path

Newest first, and skip what cannot hold the key.

A read takes a snapshot and asks the newest data first: the active in-memory table, the frozen ones, then the table files level by level. A whole-key filter lets an absent key skip an in-memory table, and each table's bloom filter lets it skip a file without touching a block.

When a table may hold the key, its index names one block; the lock-free block cache answers it if it can, otherwise the block is read from storage and its checksum verified.

Compaction

Merge the overlap, drop what nobody can read.

Flushed tables land in level 0, where they may overlap. Compaction merges them into the levels below, where each level holds non-overlapping key ranges and is ten times the size of the one above by default, and drops versions no open snapshot can still read. Universal and FIFO compaction trade differently between write cost, read cost and space.

Several compactions run at once, each split into parallel parts, and their output is rate-limited so a merge does not starve the foreground. When compaction falls behind, writes slow down before they stop.

Transactions

First committer wins, decided without a lock.

A transaction reads at its own snapshot and keeps its writes private. At commit it checks whether anything it writes, or under serializable isolation anything it read, was written after it began; if so it is refused with Conflict and writes nothing. The check waits only for commits that claimed earlier sequence numbers to publish their keys.

At rest

Sealed before it touches the disk.

With encryption on, tables, the log, the manifest and the options record are each encrypted and authenticated under a key of their own, derived from the root key your KeyProvider supplies. Opening with a wrong or missing key is refused before a single file is read.

The crates

Five crates, each with one job.