nanoDB

An LSM-tree based key-value storage engine written in Python.

Brief Architecture

The whole engine logic consists out of the four main components:

• WAL: for crash recovery
• Memtable: in-memory storage for ensuring fast reads
• SSTable: sorted, immutable persistent storage. Nothing is altered or deleted. Deletion is marking with a thombstone.
• Compaction Janitor: background process for compacting SSTables.

See docs/ for a deeper, code-traced walkthrough of each layer, including the on-disk SSTable format and the Bloom filter.

Toolkit

• struct: binary serialization for SSTable records
• bisect: binary search over sorted index entries
• sortedcontainers.SortedDict: memtable backing structure
• heapq.merge: k-way merge during compaction
• zlib.crc32 or hashlib: checksums for WAL integrity
• mmap: optional, for faster SSTable reads once everything works
• pytest + hypothesis: testing, simulating random sequences of actions and sudden crashes.
• time.perf_counter (stdlib only): benchmark timing, no extra benchmarking dependency.

Project Layout

src/           engine, wal, memtable, sstable, compaction, format modules
tests/         pytest + hypothesis test suite (one file per module, plus
               integration and property tests for the full engine)
benchmarks/    throughput benchmarks (put/get/delete/compaction)
data/          default on-disk location for a store's WAL + SSTable files
               (generated contents are gitignored; the folder itself is kept)

Setup

python3 -m venv venv
source venv/bin/activate
pip install -r requirements-dev.txt   # runtime + test/dev dependencies

Use requirements.txt alone if you only need the runtime dependency (sortedcontainers), e.g. when embedding nanoDB in another project.

Usage

import sys
sys.path.insert(0, "src")  # modules import each other as top-level, e.g. `from wal import WAL`

from pathlib import Path
from engine import LSMStore

with LSMStore(Path("data")) as store:
    store.put(b"key", b"value")
    store.get(b"key")      # b"value"
    store.delete(b"key")
    store.get(b"key")      # None

LSMStore takes the on-disk directory plus two optional tuning parameters: memtable_max_bytes (flush threshold) and compaction_threshold (how many SSTables accumulate before they're merged).

Running Tests

pytest

pytest.ini points pythonpath at src/ so tests can import the engine modules directly. The suite includes unit tests per module and an integration/property-based suite (tests/test_engine_properties.py) that runs Hypothesis-generated random sequences of puts/deletes/reopens against a plain-dict model to catch crash-recovery and merge-ordering bugs.

Running Benchmarks

python benchmarks/bench_engine.py [--ops N] [--value-size N]

Reports throughput for sequential/random puts, memtable-hot vs. sstable-heavy gets, deletes, and puts that trigger flush + compaction.