How the engine works

TessariKV is a log-structured merge tree. It never overwrites data in place. A write is appended to a log, kept in a sorted in-memory table, and later written out as an immutable sorted file. Background compaction merges those files level by level.

The write path

1. The batch takes a sequence number. Sequence numbers order every write in the database. A snapshot is a sequence number: it sees every batch at or below it.
2. Its log record is written with the durability the write asked for (see Writes and durability). Writers that arrive together share one log write and one sync.
3. Its entries go into the keyspace's in-memory table, a lock-free skiplist. From then on every new snapshot sees the batch.

Concurrent writers take their places in the commit order without queueing behind a mutex: claiming sequence numbers is one wait-free atomic add. What readers may see is a prefix: the largest sequence below which every batch is complete. So a reader never sees a later write without an earlier one.

Flushes and the manifest

When an in-memory table reaches memtable_bytes it is frozen: it stops taking writes and a fresh one takes its place. A background task flushes the frozen table into a sorted table file in level 0.

The manifest is the log of changes to the set of table files. A flushed file becomes part of the database only once the manifest naming it is synced. Only then may the log segments it covers be removed. A crash between the two loses nothing: opening replays the log above the last recorded flush.

DbOptions::total_memtable_bytes caps the newest in-memory tables of every keyspace together. When they reach it, they are flushed as if one of them were full.

The table format

A table file holds sorted key-value pairs:

• Data blocks of about block_bytes (4 KiB by default), compressed with the keyspace's codec. A block is stored compressed only when that saves at least an eighth of it.
• Prefix compression inside each block: a key stores only the bytes that differ from the key before it. Every block_restart_interval keys (16 by default) a key is stored whole, so a seek can binary-search the block.
• An index naming the block each key range lives in.
• A bloom filter over the keys, 10 bits per key by default, so a read of an absent key skips the file without touching a data block.
• A checksum on every block, verified on every read from storage.
• Range-delete blocks for the range deletes the table carries.

The read path

A read takes a snapshot and asks the newest data first, stopping at the first answer:

1. the active in-memory table, then the frozen ones — each has a whole-key filter, so a read of a key it does not hold skips it;
2. the table files of level 0, newest first;
3. then one table per level below, the one whose key range covers the key.

For each table the bloom filter decides whether to look at all. If it may hold the key, its index names one block. The block cache answers if it holds that block. Otherwise the block is read from storage, its checksum verified, and it enters the cache.

Range deletes are applied on the way: a version older than a range delete that covers it is invisible.

The block cache

The block cache is a lock-free CLOCK cache shared by every keyspace, sized by DbOptions::block_cache_bytes (512 MiB by default; zero disables it). CLOCK keeps a reference bit per entry instead of a list in access order, so a cache hit writes no shared list and takes no lock.

DbOptions::max_open_files bounds how many table files stay open. Each table's index and filter stay in memory either way.

What lock-free means here

Every shared structure on a read or write path is lock-free or wait-free wherever a non-blocking form exists:

• the in-memory table is a lock-free skiplist;
• the block cache is a lock-free CLOCK;
• the commit order is claimed without a mutex;
• every statistic is one wait-free add on a per-thread stripe.

A writer never waits for a lock to apply its batch. One window remains by design: because visibility is a prefix, a writer stalled between claiming its sequence numbers and completing its batch holds back the visibility of every later batch until it completes. These building blocks live in the tessarikv-sync crate. Each is documented with its specification, its linearization points and the argument for every memory ordering it uses, and each is model-checked under loom.

Background work — flushes, compactions, log writes — runs as tokio tasks, with CPU-heavy and blocking parts on blocking threads. The library never creates a runtime of its own.

Versions and garbage

Old versions of a key stay in the tables until compaction can prove that no open snapshot can read them. See Compaction and backpressure.