rs-lsmtree

A simplified but correct Log-Structured Merge tree (LSM-tree) key-value store for Rust, built entirely on the standard library — zero external dependencies.

LSM-trees are the write-optimized data structure behind real systems like LevelDB, RocksDB, Cassandra, and HBase: writes are cheap (append to an in-memory table, occasionally flush it sequentially to disk) at the cost of reads sometimes having to check multiple files. This crate implements the core of that idea — memtable, immutable sorted SSTable files, tombstone deletes, and compaction — in a small, readable package, so you can actually see how the write path, read path, and compaction of a real LSM-tree work without wading through a production storage engine's codebase.

It is intentionally scoped down from a production engine: no write-ahead log (a crash before a flush loses unflushed writes), no bloom filters or sparse indexes to skip SSTable files or seek within them (reads do a linear scan of a file when they miss the memtable), no leveled/tiered compaction strategy (compact() merges everything into one table), and no concurrency control (see below). What it does implement, it implements correctly: the memtable/SSTable read-precedence order and tombstone semantics are exercised by real tests against real on-disk files, not just "it compiles."

Usage

use rs_lsmtree::LsmTree;

fn main() -> std::io::Result<()> {
    // A real directory on disk. `flush_threshold` is the approximate number
    // of bytes of key+value data the memtable may hold before it is
    // automatically flushed to a new SSTable file.
    let dir = std::env::temp_dir().join("rs-lsmtree-example");
    let mut db = LsmTree::open(&dir, 64 * 1024)?;

    db.put(b"user:1".to_vec(), b"kayra".to_vec())?;
    db.put(b"user:2".to_vec(), b"berilis".to_vec())?;
    assert_eq!(db.get(b"user:1")?, Some(b"kayra".to_vec()));

    db.delete(b"user:2".to_vec())?;
    assert_eq!(db.get(b"user:2")?, None); // tombstoned

    // Force everything currently in memory out to disk...
    db.flush()?;
    // ...then merge every SSTable file into one, permanently dropping
    // tombstoned keys and keeping only the newest version of the rest.
    db.compact()?;

    Ok(())
}

How it works

Memtable

Writes (put/delete) go into an in-memory BTreeMap<Vec<u8>, Option<Vec<u8>>>. A value of None is a tombstone: it doesn't mean "no entry," it means "this key was explicitly deleted," which is why it has to be stored rather than just removed from the map — an older SSTable on disk might still have a real value for that key, and the tombstone has to be able to shadow it.

BTreeMap keeps its keys in sorted order for free, which matters below.

Flushing to SSTables

Once the approximate byte size of the memtable's keys and values reaches flush_threshold, the memtable is flushed: its entire sorted contents are written out as one new SSTable ("Sorted String Table") file, and the memtable is cleared. SSTable files are immutable once written — nothing ever edits one in place — and are named sstable-XXXXXXXXXX.dat, where the zero-padded number is a monotonically increasing ID. A higher ID means a more recently flushed (newer) table; LsmTree::open scans the store directory for existing files matching this pattern on startup, so data survives a process restart and new IDs never collide with old files.

On-disk format. Each SSTable file is a flat sequence of entries, in ascending key order (guaranteed by writing straight from the BTreeMap's iterator), with no header:

repeated for each entry:
  key_len:   u32, little-endian
  key:       `key_len` bytes
  tombstone: u8            (0 = a value follows, 1 = this key is deleted)
  value_len: u32, little-endian   -- only present when tombstone == 0
  value:     `value_len` bytes    -- only present when tombstone == 0

The file ends wherever the last entry ends; there's no length prefix or footer. See src/sstable.rs for the exact reader/writer.

Reads

get(key) checks the memtable first. If key isn't there, it scans SSTable files from newest to oldest (highest ID to lowest), stopping at the first file that contains key at all. Whatever that first hit is — a real value or a tombstone — wins. That order is the whole reason tombstones behave correctly: if a key was written, then flushed, then later deleted, then flushed again, the delete lives in a newer SSTable than the value. Reading newest-first (and stopping immediately on the first hit) means the tombstone is found before the older value ever gets a chance to be returned. Because each SSTable file is sorted, a lookup that misses can stop scanning as soon as it passes the point in the file where the key would have been, rather than reading the whole file.

Compaction

Over time, flushing produces many small SSTable files, some of which contain now-superseded values or tombstones that are permanently obsolete (nothing older will ever need to see them again once every input table is part of the merge). compact() merges every SSTable file into one: it reads each file oldest-to-newest into a single sorted map (so a later file's entry for a key naturally overwrites an earlier file's), drops every key whose resulting value is a tombstone, and writes what's left as one new SSTable file. The old files are only deleted after the merged file has been written successfully, so a failure partway through writing loses no data (a failure partway through deleting old files can leave old files and the new merged file coexisting on disk momentarily; re-running compact cleans this up, since it's idempotent given the same input state).

What's deliberately out of scope

• No write-ahead log. Memtable contents that haven't been flushed yet are lost if the process crashes or is killed; only flushed data is durable.
• No indexing within an SSTable file. A lookup that isn't in the memtable does a sequential scan of each candidate SSTable (with an early exit once the sorted file passes the target key), rather than using a sparse index or bloom filter to jump straight to (or skip) the right block. Fine for a teaching-scale implementation; a real engine would add this to avoid O(number of files) disk reads per miss.
• No leveled/tiered compaction. compact() is a full merge of every table into one; there's no background scheduling or size-tiered strategy.
• No concurrency control. LsmTree does no file locking, so two processes (or two LsmTree instances) must not open the same directory at once, and the type is not internally thread-safe — wrap it in a Mutex to share it across threads.

Testing

cargo test

This runs unit tests (including SSTable format round-trip tests) and the runnable doctest examples embedded in the API documentation. The core correctness tests use real, unique temporary directories on disk (under std::env::temp_dir()) and clean them up afterward. They specifically prove:

• That writing enough keys to cross the flush threshold produces a real SSTable file on disk, and that get is correct both for a key that ended up flushed to that file and for a key that is still only in memory.
• That deleting a key and flushing produces a tombstone that correctly shadows an older, already-flushed value for the same key — verified after fully reopening the store from disk, so it isn't just in-process bookkeeping.
• That compacting two SSTables with overlapping keys keeps only the newest value for keys that were updated, drops keys whose newest version is a tombstone, and leaves untouched keys alone — checked both through get and by reading the merged file's actual on-disk contents directly.

License

MIT. See LICENSE.