lsmkv

I wanted to know what happens inside a database when you write a row. LevelDB and RocksDB are built on the same idea, the LSM tree, so I wrote a small one myself. It is a learning project and nothing runs on it.

A write goes to a log file first and then to a hash map in memory. When the map reaches 4 MB, it is sorted and written to disk as a table. A delete writes a marker instead of removing anything, because the old value might still be in a table on disk.

A read checks memory first, then the tables from newest to oldest. Each table has a bloom filter, so most tables are skipped without touching the disk. When the filter says the key might be there, an index points to the one 4 KB block to read.

Over time the tables are merged into levels, with the same sizes LevelDB uses. A merge keeps the newest version of each key and drops deleted keys once nothing older is left below them. There are no background threads. Merging runs in small steps inside each write.

Every record, block and index is checksummed. On startup a half-written record at the end of the log fails its checksum and is cut off, and table files left behind by a crashed merge are deleted.

Most of the tests fake a crash by truncating or corrupting files, then reopen the store and check nothing was lost. Another test runs 100,000 random writes, deletes and reads against a std::map and reopens the store along the way.