LSM Tree

Component 3 of 3 in Storage & Persistence of the strata-database-engine ecosystem. Repo: github.com/juanmmm21/lsm-tree-engine

A Log-Structured Merge Tree storage engine, written from scratch in Python: writes land in an in-memory skip list backed by a crash-safe write-ahead log, get sealed into immutable, checksummed SSTables once the skip list grows past a configurable threshold, and a hybrid size-tiered/leveled compaction fuses SSTables in the background — keeping key ranges disjoint from L1 down — to bound how many files a read has to check. It is one of the two interchangeable storage backends of the ecosystem (the other being bplus-tree-storage-engine), and its own internal WAL follows the same durability discipline as write-ahead-log-recovery.

What it is and what problem it solves

A B+Tree updates its data in place: every insert eventually touches a handful of pages scattered across the file, each of which needs its own disk seek. That is fine for read-heavy workloads, but it caps write throughput at however fast the disk can do small random writes. The Log-Structured Merge Tree, the engine behind RocksDB, Cassandra and LevelDB, takes the opposite trade: never touch old data in place. Every write only ever appends — to a log, then to a new sorted file — and the cost of merging old and new data is paid later, in the background, by compaction. The result is write throughput close to the disk's sequential write speed, at the cost of a read sometimes having to check more than one file before it can answer "not found".

This project implements that structure from first principles: a skip list memtable, a binary SSTable format with an embedded bloom filter and sparse index, a hybrid size-tiered/leveled compaction with a correctness proof for when a tombstone is safe to drop, and property-based tests that compare the engine against a plain Python dict under thousands of randomized operations, before and after compaction, and across simulated crashes.

Role in strata-database-engine

                    write-ahead-log-recovery
                     (durability discipline)
                              │
                              ▼
                 ┌─────────────────────────────┐
                 │      lsm-tree-engine         │   (this repo)
                 │  skip list · WAL · SSTables   │
                 │  bloom filter · compaction     │
                 └───────────────┬───────────────┘
                                 │ pluggable storage backend
                                 ▼
                    mvcc-transaction-manager /
                    lock-manager-deadlock-detector
                                 │
                                 ▼
                              nanosql

This repo does not import or depend on any other subproject — including write-ahead-log-recovery, whose durability discipline it follows without sharing a line of code with it, and bplus-tree-storage-engine, the sibling backend it is meant to be compared against. It exposes a versioned binary SSTable format and a plain Python API (LsmTree.put / get / delete / scan) as its integration surface. nanosql is where a real engine would pick this backend or the B+Tree one at configuration time; that composition is deliberately out of scope here.

Goal / skills demonstrated

• A skip list built from scratch (no sortedcontainers or any third-party ordered structure) as the memtable, with the level-promotion randomness injected via random.Random so tests can fix a seed and get a fully reproducible structure.
• A bloom filter built from scratch: a raw bit array plus the Kirsch–Mitzenmacher double-hashing scheme (derive k hash positions from a single 16-byte blake2b digest instead of k independent hash functions), deliberately avoiding Python's built-in hash() because it is salted per-process and would make two runs of the same program produce different — and non-portable — filters.
• A binary SSTable format with a fixed-size footer, a CRC32 checksum per data block (not one checksum for the whole file) recorded in the sparse index itself, so a point lookup only has to verify the one block it actually reads, not the whole SSTable.
• Hybrid size-tiered / leveled compaction, with an explicit, tested correctness argument for tombstone deletion: a tombstone is only ever dropped when the target level and everything deeper than it are empty at the moment of the merge — otherwise an older, shadowed value could resurface once nothing is left to shadow it. From L1 down, every promotion also absorbs (via transitive range-overlap detection) any SSTable already living in the target level that shares part of its key range, so a level never ends up holding two SSTables that overlap — the same invariant LevelDB/RocksDB's leveled compaction maintains, kept here without also requiring per-level size targets or picking individual files to compact.
• Crash safety at every persisted boundary: the internal WAL is fsynced on every put/delete, the manifest is written atomically (temp file → fsync → os.replace), and flush/compaction always durably persist new data before discarding what made it redundant — so a crash at any point leaves, at worst, harmless redundant work to redo, never lost data.
• A bounded, LRU-evicted cache of open SSTable readers, added after profiling showed that reopening and re-verifying a SSTable's footer, index and bloom filter on every single get dominated read latency — the same "acotado con política de reemplazo explícita" requirement bplus-tree-storage-engine's buffer pool follows, applied here to file handles and parsed metadata instead of pages.
• Property-based tests with fixed-seed random put/delete workloads (multiple seeds, thousands of operations each) verified against a reference dict, both with compaction disabled and with it actively cascading across levels, plus a dedicated test that kills and reopens the engine mid-workload to exercise real crash recovery.

How it works

Memtable: a skip list

New writes go into an in-memory skip list (SkipList in pipeline.py), Pugh's classic structure: each node is promoted to an extra level with probability SKIP_LIST_P = 0.25, up to SKIP_LIST_MAX_LEVEL = 16, giving expected O(log n) search and insert without the rebalancing logic a tree would need. A delete is not a separate operation — it inserts a Record with value=None (a tombstone) at the same key, exactly the representation SSTables use, so the memtable and every SSTable share one uniform notion of "this key was deleted here".

Durability: an internal write-ahead log

Every put/delete is appended to a binary WAL (WAL_MAGIC = b"LWL1", one record per operation: sequence number, type, key, value, CRC32 checksum) and fsynced before the call returns. On LsmTree.open, the WAL is replayed to rebuild whatever memtable content never made it into a SSTable before the last crash. Replay stops — without raising — at the first truncated or checksum-mismatched record, because past that point the following bytes cannot be trusted to mark a real record boundary; that tail is treated as never-confirmed and discarded, the same principle write-ahead-log-recovery applies to its own log. Once a flush durably persists the memtable's content as a SSTable, the WAL is reset — its content is redundant from that point on.

SSTable format

An SSTable is an immutable, once-written file: a data block of entries sorted by key, a sparse index, an embedded bloom filter, and a fixed-size footer at the end (so it can always be located by reading the last SSTABLE_FOOTER_SIZE bytes, regardless of anything else in the file):

[ data block: entries sorted by key ascending, grouped into blocks of   ]
[ SSTABLE_INDEX_INTERVAL = 16 entries each                              ]
[ sparse index: one (key, offset, block_checksum) triple per block      ]
[ bloom filter: raw bit array, sized for the SSTable's entry count      ]
[ footer (fixed size): magic, version, entry_count, section offsets/    ]
[ sizes/checksums for the index and the bloom filter, footer checksum   ]

Opening a SSTable (SSTableReader.__init__) reads and verifies the footer, the whole index and the whole bloom filter — all three bounded in size, proportional to entry_count / 16 and to the bloom filter's bit budget, never to the file size. A point lookup then does a binary search over the in-memory index to find the one block that could hold the key, reads only that block from disk, verifies its own CRC32 (stored right in its index entry), and scans its handful of entries. Corruption or truncation anywhere — the footer, the index, the bloom filter, or a single data block — raises a typed exception instead of returning wrong data or crashing the process.

Compaction: hybrid size-tiered / leveled, with a tombstone-safety proof

Compactor merges SSTables level by level: once a level accumulates CompactionConfig.level_trigger files, all of them are fused (a k-way merge keyed on the globally unique sequence number — never a coin-flip when two sources disagree, the highest seq always wins) into one new SSTable. L0 is left as-is otherwise: its files can and do overlap in key range, because each one comes from an independent memtable flush and there is no way around that without buffering multiple memtables before ever writing one to disk.

From L1 down, promoting a merge result is not a blind append: _split_by_overlap first finds every SSTable already in the target level whose key range intersects the union of what is being promoted, expanding that union transitively (absorbing one overlapping file can extend the range far enough to now also overlap a second one, and so on) until the set of overlapping files stops growing. Those get folded into the same merge; everything else in the target level is left untouched. The result: every level from L1 on is always a set of SSTables with mutually disjoint key ranges — a get only ever has to open, at most, one SSTable per level from L1 down (L0 is the exception, bounded by level_trigger - 1 overlapping files at any time), instead of every SSTable a naive size-tiered design would leave scattered across it. If the target level now also crosses the trigger, the cascade continues in the same pass — see tests/test_compaction.py::test_no_two_sstables_overlap_within_a_level_after_hot_range_workload for a property-style check of this invariant under a few thousand random operations concentrated on a small, frequently-overwritten key range.

This is deliberately not full leveled compaction: a production engine also targets a maximum total size per level and picks individual files to compact against it, instead of sweeping an entire level once it crosses a file-count trigger. That refinement changes how the compaction work is scheduled, not whether the result is correct or whether ranges stay disjoint, so it was left out — it would not demonstrate anything this design does not already cover.

A tombstone is only dropped from the output when is_bottommost holds: every level deeper than the target is empty before this merge writes anything. If they were not, an older value could be sitting in a file this merge never touched, and erasing the tombstone that hides it would let it resurface on the next read — a class of bug covered explicitly by tests/test_compaction.py.

Architecture

src/lsm_tree_engine/
├── __init__.py     # re-exported public API
├── models.py       # binary format constants, Record/WalRecord/SSTableMeta/ManifestState, config, exceptions
├── protocols.py     # WriteAheadLog: the one pluggable seam
├── pipeline.py       # skip list, bloom filter, WAL, SSTable codec, manifest, compaction, LsmTree
└── __main__.py       # demonstration CLI

• models.py — immutable data types (dataclass(frozen=True, slots=True)) and the exception hierarchy (LsmError → StorageIOError / LogCorruptionError → WalTruncatedRecordError / WalChecksumMismatchError / WalInvalidRecordError, and symmetrically SSTableCorruptionError → SSTableTruncatedError / SSTableChecksumMismatchError / SSTableInvalidError, plus ManifestCorruptionError and CompactionInvariantError).
• protocols.py — WriteAheadLog, the durability contract; FileWriteAheadLog and InMemoryWriteAheadLog (for fast, deterministic tests) both implement it.
• pipeline.py — everything else: SkipList, BloomFilter, the WAL codec, SSTableWriter/SSTableReader, the manifest codec (read_manifest/write_manifest), Compactor, SSTableReaderCache, and LsmTree (put, get, delete, scan, flush, compact).
• __main__.py — a demonstration CLI (put, get, delete, scan, info, compact, benchmark).

Concurrency: every class in this module assumes a single thread of control — there is no internal locking because there is nothing to race against in this scope. A caller needing concurrent access (nanosql, for instance) must serialize it in its own layer before calling into this engine.

Requirements and installation

• Python >=3.11

git clone https://github.com/juanmmm21/lsm-tree-engine.git
cd lsm-tree-engine
python3 -m venv .venv && source .venv/bin/activate
pip install -e ".[dev]"  # or: pip install -e . pytest mypy ruff

Usage

CLI

python -m lsm_tree_engine put --path /tmp/demo.db --key alice --value 30
python -m lsm_tree_engine put --path /tmp/demo.db --key bob --value 25
python -m lsm_tree_engine put --path /tmp/demo.db --key carol --value 35

python -m lsm_tree_engine get --path /tmp/demo.db --key alice
# 30

python -m lsm_tree_engine scan --path /tmp/demo.db
# alice	30
# bob	25
# carol	35

python -m lsm_tree_engine scan --path /tmp/demo.db --start bob --end carol
# bob	25

python -m lsm_tree_engine delete --path /tmp/demo.db --key bob
python -m lsm_tree_engine info --path /tmp/demo.db
# memtable_entries=3
# memtable_size_bytes=65

# --memtable-size forces a flush per put below, to get two separate SSTables in L0
python -m lsm_tree_engine put --path /tmp/demo.db --key dave --value 40 --memtable-size 1
python -m lsm_tree_engine put --path /tmp/demo.db --key erin --value 45 --memtable-size 1
python -m lsm_tree_engine info --path /tmp/demo.db
# memtable_entries=0
# memtable_size_bytes=0
# level=0 sstables=2 entries=5

python -m lsm_tree_engine compact --path /tmp/demo.db --level-trigger 2
# level=1 sstables=1 entries=4
# (bob's tombstone was dropped here: L1 and everything deeper were empty,
#  so nothing could still be shadowing the old value it deleted)

Programmatic usage

from lsm_tree_engine import LsmTree, MemtableConfig, CompactionConfig

with LsmTree.open(
    "demo.db",
    memtable_config=MemtableConfig(max_size_bytes=4 * 1024 * 1024),
    compaction_config=CompactionConfig(level_trigger=4),
) as tree:
    tree.put(b"alice", b"30")
    tree.put(b"bob", b"25")
    tree.put(b"carol", b"35")

    assert tree.get(b"alice") == b"30"
    assert list(tree.scan(start=b"bob", end=b"carol")) == [(b"bob", b"25")]

    tree.delete(b"bob")
    assert tree.get(b"bob") is None

LsmTree.open recovers automatically: if the process is killed with unflushed writes still only in the WAL, the next open replays them back into the memtable before returning.

Data format / interface exposed to nanosql

The binary SSTable format (SSTABLE_MAGIC = b"LSS1", versioned) and the manifest format (MANIFEST_MAGIC = b"LMF1") are the on-disk contract. Programmatically, nanosql (or any consumer) drives the engine through LsmTree's plain methods — put, get, delete, scan, flush, compact — over a data directory it owns. WriteAheadLog is a Protocol specifically so nanosql can plug in a different durability backend without touching this repo's internals, the same seam PageDevice provides in bplus-tree-storage-engine.

Development

pytest
ruff check .
ruff format --check .
mypy --strict src/

The test suite covers: skip list ordering and determinism under a fixed seed; bloom filter false-positive rate and serialization; WAL codec round-trips and crash-safe replay under truncated or checksum-corrupted tails; SSTable codec round-trips, rejection of out-of-order/duplicate writes, and per-block corruption detection; atomic manifest persistence and its own corruption/truncation handling; compaction correctness (deduplication by sequence number, tombstone dropping only when bottommost, multi-level cascades); the full LsmTree engine (CRUD, automatic flush, forced compaction, crash recovery, orphaned-SSTable cleanup); every CLI subcommand; and property-based tests running thousands of randomized put/delete operations across several fixed seeds, compared against a reference dict, with and without active compaction, and with the engine killed and reopened mid-workload.

Benchmarks

Illustrative numbers from a single machine (pure Python, no C extensions, single-threaded — treat as a rough order of magnitude, not a guarantee), all with count=100000 keys of the form bench-{i:08d}, compared against bplus-tree-storage-engine's benchmark subcommand run with the same count and a 64-page buffer pool:

$ python -m bplus_tree_storage_engine benchmark --path /tmp/bplus.db --count 100000 --capacity 64
writes: 100000 en 13.495s (7410 ops/s)
reads:  100000 en 19.494s (5130 ops/s)

$ python -m lsm_tree_engine benchmark --path /tmp/lsm.db --count 100000
writes: 100000 en 2.687s (37220 ops/s)
reads:  100000 en 0.686s (145774 ops/s)

Writes are ~5x faster, which is the whole point of this design: a put is an fsynced WAL append plus an in-memory skip-list insert, never a page read-modify-write, so throughput stays close to the disk's sequential write speed regardless of how the key space is distributed.

The read numbers need an honest caveat, though: they are not simply "LSM beats B+Tree at reads too". With the default 4 MiB memtable and 100,000 small keys, this workload never accumulates more than one or two SSTables, and SSTableReaderCache's default capacity (64 open readers) keeps every SSTable's footer, index and bloom filter fully resident in memory after the first access — so a get degrades to little more than a bloom-filter check plus one small block read. That is a fair result (a production LSM engine caches exactly this metadata too), but it is not representative of read amplification under memory pressure. Forcing more SSTables to coexist (--level-trigger 20) and starving the reader cache (--reader-cache-capacity 2) makes that cost reappear directly:

memtable_size=64KiB, level_trigger=20 → 16 SSTables across 2 levels, 100000 random-order reads
  reader-cache-capacity=64 (warm):  100257 ops/s
  reader-cache-capacity=2  (cold):    5242 ops/s

With a cache too small to hold every SSTable's metadata, a random-order read pattern thrashes it — every get on a "cold" key re-reads and re-verifies a SSTable's footer, index and bloom filter from disk — and read throughput collapses to roughly what bplus-tree-storage-engine sustains unconditionally, since a B+Tree's read cost is a near-constant number of page reads regardless of history. That collapse is the trade-off this comparison exists to demonstrate: an LSM-Tree buys write throughput by deferring and batching the cost of keeping data merged, and a read pays that deferred cost whenever the metadata needed to avoid it does not fit in memory.

This particular benchmark uses monotonically increasing keys, so every SSTable's range is already naturally disjoint from every other one — the cache-thrashing cost above comes purely from how many distinct SSTables a random read pattern touches, not from any one get having to check more than one SSTable per level. A workload that instead concentrates repeated writes on a small, hot key range (exactly what tests/test_property_invariants.py and test_no_two_sstables_overlap_within_a_level_after_hot_range_workload exercise) is where the leveled half of the compaction design earns its keep: without the transitive overlap-absorption in Compactor, every level from L1 down could accumulate several SSTables that all cover roughly the same range, and a single get would have to check all of them; with it, a level past L0 never holds more than one SSTable whose range could contain any given key.

Troubleshooting

• WalChecksumMismatchError / SSTableChecksumMismatchError on open or read: real corruption of bytes already written (not a truncation). For the WAL, replay simply stops at that point and everything before it is still recovered; for a SSTable, only the specific block being read is affected — every other block's checksum is independent.
• WalTruncatedRecordError / SSTableTruncatedError: the file is shorter than a record/section declares — typically a process killed mid-write. Handled the same way as a checksum mismatch: recovery stops there instead of crashing or trusting partial data.
• ManifestCorruptionError on open: should not happen in normal operation, since the manifest is only ever replaced atomically (temp file → fsync → os.replace) — a crash mid-write leaves the previous, still-valid manifest in place. If it does happen, it points at corruption of already-durable bytes (disk-level bit rot), not a partial write.
• CompactionInvariantError from SSTableWriter.add: entries were added out of order or with a duplicate key — a bug in whatever produced them (the memtable iterator or Compactor's merge), not something a caller of the public LsmTree API can trigger directly.
• Reads are much slower than expected: check --reader-cache-capacity (or ReaderCacheConfig.capacity programmatically) against how many SSTables actually exist (info / levels_summary()); see Benchmarks above for why a cache too small for the working set turns every read into a fresh disk scan of a SSTable's metadata.

License

MIT — see LICENSE.