Build a log-structured store

Why append to a log instead of updating a record in place?

Because an append is the cheapest write a disk offers and the safest one. Every write goes to the end of one file, so the disk never has to seek to the middle, and a crash can only damage the record being written at the end. An update in place has to find the old record first, and if the power goes halfway through it, the record that was good before the write is now neither the old value nor the new one. The price is that old values stay in the file until something compacts it.

What does the index in memory hold, and what happens to it on a restart?

One entry per key: the byte offset where that key's newest record starts. It never holds a value, so a read is one dict lookup and one read at a known offset. The index is lost when the process stops, and that is fine, because the log holds everything the index was built from. On a restart the store reads the log from the first byte to the last, and each record points its key at itself, so the last record for a key wins. A delete is a record too, a tombstone, and replaying it removes the key.

What if the process crashed in the middle of an append?

Then the log ends with part of a record. Each record carries its lengths at the front and a CRC-32 checksum at the end, so recovery can tell a whole record from a torn one: it stops at the first record that is short or fails its checksum, keeps everything before it, and cuts the file back to that point. The cut matters. Without it the next append would land after the torn bytes, and the restart after that would stop at the torn record and lose the new one.

When is it safe for compaction to drop a tombstone?

Only when no segment older than the ones being merged is left behind. A tombstone exists to hide older values of its key. If the merge includes the oldest segment, every older value is being rewritten in the same pass and the tombstone has nothing left to hide, so both can go. If an older segment survives the merge, it may still hold a value for that key, and dropping the tombstone brings that value back. The build proves this with a recorded run in which a deleted key returns.

How is this different from an LSM tree?

This store keeps a hash index of every key in memory and writes each segment in the order the writes arrived. An LSM tree keeps the newest writes in a sorted table in memory, flushes it to disk as a sorted segment, and merges sorted segments in the background. Sorting buys two things a hash index cannot give: a range scan over neighbouring keys, and an index that does not have to fit in memory, because a sparse index with one key per block is enough to find the right block of a sorted segment.