LSM Key Store

A small Log-Structured Merge-tree (LSM) key-value store written in C++20.

You can put, get, and delete string keys, scan a key range, and compact on-disk SSTables. Writes go to a write-ahead log (WAL) and an in-memory memtable first; when the memtable fills, data is flushed to sorted SSTable files on disk. Reads check the memtable, then SSTables newest-first. Compaction merges SSTables so shadowed and deleted keys are dropped from disk.

---

Directories

Path	Purpose
include/	Public headers (Store, WAL, SSTable, iterators, compactor)
src/	Implementations of those components
tests/	Unit / integration tests for each milestone
bench/	Performance harness (lsm_bench)
examples/	Simple demo program showing the public API
Makefile	Build tests, demo, and benchmarks

On-disk data for runs lives under ../data relative to the process working directory (same path the tests use). Prefer running binaries from the repository root.

---

Build & run

Requires a C++20 compiler and zlib (-lz, used for WAL checksums).

# Demo — try the API
make demo
./lsm_demo

# Unit tests (examples)
make test_scan
make test_compaction

# Benchmarks
make bench
./lsm_bench all --n 5000
./lsm_bench all --n 10000

---

Demo (examples/main.cpp)

make demo builds ./lsm_demo, which:

1. Inserts a few keys (put)
2. Reads one back (get)
3. Updates and deletes
4. Prints a range scan
5. Calls compact()

---

Benchmarks

Harness: ./lsm_bench (see also bench/README.md).

Environment

Machine	MacBook (arm64)
OS	macOS 15.7.4
Compiler	Apple Clang 17 / g++ -std=c++20 -O2
Value size	64 bytes (writes / gets / scans)
Key counts	--n 5000 and --n 10000

Times vary slightly from run to run (disk/OS scheduling), but repeated runs stay in the same range. The tables below are one representative pass; expect similar—not identical—numbers if you re-run.

Results — n = 5000

Workload	n	Time (ms)	Throughput	µs/op
Sequential writes	5000	3156.64	1583.96 ops/s	631.33
Random writes	5000	3427.93	1458.61 ops/s	685.59
Point gets	5000	835.00	5988.01 ops/s	167.00
Full scan	5000	16.52	302720.70 keys/s	3.30
Bounded scan	1250	11.12	112374.70 keys/s	8.90
Gets before compact	1250	175.38	7127.37 ops/s	140.30
Scans before compact	1500	16.49	90941.47 keys/s	11.00
compact()	—	21.52	—	—
Gets after compact	1250	160.98	7765.16 ops/s	128.78
Scans after compact	1500	5.82	257792.86 keys/s	3.88

Compaction disk: 4 → 1 SST file, 719000 → 171250 bytes (76.18% smaller).

Results — n = 10000

Workload	n	Time (ms)	Throughput	µs/op
Sequential writes	10000	17362.58	575.95 ops/s	1736.26
Random writes	10000	27068.71	369.43 ops/s	2706.87
Point gets	10000	2461.26	4062.96 ops/s	246.13
Full scan	10000	37.14	269236.98 keys/s	3.71
Bounded scan	2500	33.15	75423.03 keys/s	13.26
Gets before compact	2500	413.02	6052.95 ops/s	165.21
Scans before compact	3000	32.66	91853.60 keys/s	10.89
compact()	—	42.82	—	—
Gets after compact	2500	336.78	7423.25 ops/s	134.71
Scans after compact	3000	11.63	257878.73 keys/s	3.88

Compaction disk: 4 → 1 SST file, 1438250 → 342750 bytes (76.17% smaller).

Takeaways

• Writes are dominated by WAL durability (fsync); sequential and random puts are in the same ballpark.
• Point gets are much faster than writes; range scans are cheapest per key when streaming.
• Compaction cuts on-disk size sharply (~76% here) and improves get/scan times when multiple SSTables were being merged at read time.

---

License

See LICENSE.