Yet Another Bitcask — My ravings

I have to confess at not having spent much time hands on with storage technology. It is as interesting as it is foundational, but all my research into it have been theoretical: understanding query engines, BTrees, Indexing, but I felt that actual, manly man storage was to get hands on. Besides, what is the point, when you have MySQL and PostgreSQL and sqlite, etc. out there… I have nothing to add. Yet I remain fascinated by storage technology.

For a while things seem to be pretty stale; the NoSQL movement was surrounded by groupies who seemed, as a class, to be missing the point in the most depraved sort of way, and its products seemed supplementary and derivative: the symptom of a problem space that was settled. I was wrong, and I am glad.

I played around with Calcite for a while; I even got to use products built with it. Poked at the Volcano query engine, but it all looked very removed from my day to day concerns. In the meantime there was a quiet revolution happening in the space with things like Parquet becoming a new standard for storage. The advent of the rust language added a piece to the milieu: a safe, performance systems language. I cut my teeth on C, and it’ll always have a place in my heart, but it always felt like the bastard child of double entry accounting and the feeling you get when you are driving a car while you are building it. In comparison to higher level languages, it was always a drag for things other than toys. The D language is awesome, but wasn’t quite it for me.

Rust came along and reminded me how much I love systems programming. Then I spent a couple hours figuring out how to use the datafusion crate to solve the billion line challenge, and I was blown away.

Fast forward to present time, and while searching to scratch an indetermined itch, I came across the Bitcask paper. yabiir — Yet Another Bitcask Implementation, is the result. I also discovered a new joy; well, not discover, or new, but I could finally put my finger on an otherwise nebulous feeling. Coding with the help of an AI agent was fun (so much fun), but this exercise helped me understand why: being able to noodle the details of a design back and forth is a blast.

The whole bitcask design rests on a simple idea: never overwrite anything. Ever. Every operation is append-only — all of it is just bytes appended to the end of a file. No moving file pointers, no in-place updates, no B-trees to rebalance, no page splits, no complicated logic for this guy to get wrong. The genius of the design is entirely in what is built on top of that constraint to make reads fast and reclaim space later.

For completeness, let’s specify what this thing does:

You can put(key, value), which stores the value on disk associated with key.
A subsequent get(key) will return the latest value stored alongside that key, or tell you it did not find one, if none was stored.
delete(key) does the obvious.

Let’s look at what bytes end up being put on disk.

The entry format

Every write — a put, an overwrite, even a delete — becomes one of these, appended to whatever the currently-active file (more on that later) is:

offset  size  field
0       4     crc          (u32, CRC32 of everything after this field)
4       4     tstamp       (u32, unix seconds)
8       4     ksz_and_flags (u32; bit 31 = tombstone; bits 0..30 = key length)
12      4     value_sz     (u32; 0 for tombstones)
16      ksz   key
16+ksz  value_sz  value

That ksz_and_flags field is my addition to the pile of cleverness. In true expert fashion, the paper leaves some details unspecified because, yawn, who has time to, yawn, explain the obvious way to do tombstones in this design. The paper describes ksz as being a 32 bit key length, but the paper elsewhere reveals that deletes are actually handled via tombstoning, marking the data as deleted instead of actually deleting the data. A key length needs 32 bits about as much as I need a bigger yacht — no real key, in my mind of minds, is anywhere near 2 GiB — so the top bit gets stolen and repurposed as a tombstone flag. This obviates the need for a separate flags byte, and avoids having to reinterpreting, or overload one of the other fields to mark a tombstoned entry. You could, e.g. designate a CRC of 0000 as such, but it turns out that is a valid CRC; perhaps you use a tstamp of zero for the purpose, or a sentinel value (but right now we are in the business of storing data, and you are messing with that, which is bad karma)

I wrote a tiny throwaway program against the real crate (Engine::open, a few puts, a delete, max_file_size cranked down to 1 byte so it rotates to a new file after every single entry — the real default is 64 MiB) just to get real files to point a hexdump at. Here’s the literal file for put("lang", "rust"):

$ xxd 00000000000000000000.bitcask.data
00000000: d5cb 411e 0019 b56a 0400 0000 0400 0000  ..A....j........
00000010: 6c61 6e67 7275 7374                      langrust

Twenty-four bytes: d5cb411e is the CRC32, 0019b56a is the timestamp, 04000000 is ksz_and_flags — 4, no tombstone bit — 04000000 is value_sz, then langrust is literally the key and value concatenated with nothing in between them, because the header already told you exactly where one ends and the other begins. No delimiters needed when the lengths are right there.

Now the interesting one — delete("year"), after year had already been written earlier:

$ xxd 00000000000000000004.bitcask.data
00000000: 2d2d 94b9 0019 b56a 0400 0080 0000 0000  --.....j........
00000010: 7965 6172                                year

ksz_and_flags is 04000080 this time — read that last byte as 80, and in bit terms that’s 1000 0000, the top bit set. Mask it off and you’re left with 4, the length of “year”; keep only that top bit and you’ve got your tombstone. value_sz is zero, because a tombstone carries no payload — there’s nothing after the key at all. Twenty bytes instead of twenty-four: header plus key.

Rotation, and why there’s more than one file lying around

For the example below I have set max_file_size to 1 byte, which forces a new file after literally every entry. Five operations (put lang, put paper, put year, overwrite lang, delete year) leave five files behind instead of one, but it’s easy to follow.

00000000000000000000.bitcask.data   24 bytes   lang = rust
00000000000000000001.bitcask.data   28 bytes   paper = bitcask
00000000000000000002.bitcask.data   24 bytes   year = 2010
00000000000000000003.bitcask.data   30 bytes   lang = rust-again  (overwrite)
00000000000000000004.bitcask.data   20 bytes   year tombstone
00000000000000000005.bitcask.data    0 bytes   fresh active file, nothing written yet

Every file except the last one is now immutable — the paper’s model is that once a file stops being the active one, nothing ever writes to it again. That makes the rest of the design tractable: recovery, merge, and concurrent readers all get to assume “closed files never change out from under you,” which is a very nice way to live your life.

Notice lang now has two live-looking entries on disk (file 0 and file 3) and year has two as well (file 2’s real value and file 4’s tombstone). Nothing has cleaned either of those up yet. That’s on purpose — see Merge, below.

The keydir: why reads don’t have to scan anything

None of this would be fast if get had to search through every file for the newest matching entry. Instead there’s an in-memory HashMap<Box<[u8]>, KeydirEntry> — the keydir — mapping every live key straight to (file_id, value_pos, value_size, tstamp). A get is one hashmap lookup plus one positioned read at a known offset in a known file. No scanning, no tree traversal, no locks on whatever’s currently being written to (writes flush before returning, so a fresh read handle always sees consistent bytes without needing to coordinate with the writer at all). The code (impl Engine) is complex and hard to follow, but here it is:

fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>> {
    match self.keydir.get(key) {
        Some(entry) => Ok(Some(self.read_value(entry)?)),
        None => Ok(None),
    }
}

fn put(&self, key: &[u8], value: &[u8], timestamp: u32) -> Result<()> {
    let encoded = format::encode_entry(key, value, false, timestamp);
    let (file_id, value_pos) = self.append(&encoded)?;
    self.keydir
        .insert(key, KeydirEntry { file_id, value_pos, value_size: value.len() as u32, timestamp });
    Ok(())
}

put is genuinely that small: encode the entry (into the bytes we saw at the beginning), append it, point the keydir at where it landed. delete is the mirror image — append a tombstone, then remove the key from the keydir. The keydir is the entire database, functionally; the files on disk are just its durable backing store. Also, that’s the reason you do not really want a 2Gb key: keys live in memory!.

There is one subtle point with the hash: the keydir’s HashMap uses ahash instead of the stdlib default (SipHash, slow-but-DoS-resistant) or the more common FxHash/rustc-hash speed pick. FxHash has a known weakness on exactly the kind of keys real systems generate constantly — user-0000042, zero-padded counters, timestamps — where its multiply-and-rotate can collapse a whole family of structured keys into the same few buckets, turning your faast O(1) hashmap into a sloow O(n) linked list. ahash doesn’t have that specific failure mode and isn’t meaningfully slower for this workload (Claude checked, ‘cause ain’t nobody got time for that.). Small is a small thing, but one of the things I learned looking at redis (I told you I have a thing), is that the worst case matters as much as the average case. antirez (The author of redis, and to my surprise of dump1090), went out of his way to make redis performance predictable, which it turns out is nice if you carry a pager.

Recovery: replaying the log back into memory

The keydir is just a cache — nothing on disk depends on it existing. So on open(), it gets rebuilt from scratch by walking every data file, oldest to newest, and replaying each entry into the keydir: a normal entry inserts, a tombstone removes. Because files are visited in ascending id order and entries within a file in ascending offset order, “last write wins” just happens — sans special-casing, no timestamp comparisons needed. The physical order of the log is the order of truth.

Each entry’s CRC is there so that this scan can tell “clean end of file” apart from “we crashed mid-write” or “this specific entry bit-rotted.” A truncated tail (the last entry cut off mid-write, exactly what you’d see after an unclean shutdown) stops the scan there and keeps everything recovered up to that point — the datastore still opens, it just starts a fresh active file above whatever was torn, rather than trying to surgically resume writing into a possibly-damaged file. A CRC mismatch in the middle of a file (actual bit rot, not a torn write) skips just that one entry and keeps scanning — one corrupt record doesn’t take the rest of the file down with it.

Scanning every data file byte-by-byte on every restart would be slow once there’s real data behind it, though, which is what hint files are for.

Hint files: recovery without touching a single value byte

A hint file is the keydir persisted on-disk, written once at the end of a merge pass — same key, same metadata, but it points at the value instead of carrying it:

offset  size  field
0       4     tstamp
4       4     ksz_and_flags
8       4     value_sz
12      8     value_pos    (u64 — where the VALUE starts in the data file)
20      ksz   key

No CRC or actual value; it just points to the data. If it’s missing or damaged, recovery just falls back to scanning the data file it belongs to. After merging the demo directory above, paper’s hint file looks like this:

$ xxd 00000000000000000007.bitcask.hint
00000000: 0019 b56a 0500 0000 0700 0000 1500 0000  ...j............
00000010: 0000 0000 7061 7065 72                   ....paper

value_pos is 1500000000000000 in little-endian — 0x15, decimal 21. And 21 is exactly HEADER_SIZE (16) + ksz (5), the length of “paper”: the offset of the value within that same file, not the entry. When this line is read by the recovery process, it would know where bitcask lives without opening the data file at all. Multiply that by however many million keys are in a real dataset, and you can see how that improves startup time.

The astute reader might notice an apparent problem: if the hint file entries do not carry a CRC, how can we detect that it is damaged? The answer is jazzhands: there is a CRC right at the end, covering the whole file. The whole file needs to be validated as a whole: if it is corrupted, or incomplete, we just toss it and start from scratch, so a single CRC would suffice. Writing it at the end makes the computation simpler, since we can wait till all the entries are done.

I have to confess that I failed initially to add this CRC. The paper did not mention what must have been such an obvious thing (yawn), but while writing this very section I noticed the problem… which in part is why I go through this.

Merge: cleaning up after yourself.

Append-only means disk usage grows and grows. merge is the cleanup crew: it walks every data file except the currently-active one, and compares each entry with the keydir to see if the specific (file_id, offset) is still what it points to for this key. If so, the entry is live and gets copied forward into a fresh output file (plus its hint record). If not — a newer write superseded it, or it’s a tombstone — it’s dead, and it just doesn’t get copied. That’s it.

Running merge on the five-file demo directory above collapses it down to two files, one per surviving key:

$ xxd 00000000000000000008.bitcask.data
00000000: 57ec 78af 0019 b56a 0400 0000 0a00 0000  W.x....j........
00000010: 6c61 6e67 7275 7374 2d61 6761 696e       langrust-again

lang’s stale first value ("rust", file 0) is just gone — not tombstoned, not marked deleted, never copied in the first place because by the time merge looked at it, the keydir already pointed at the overwrite in file 3 instead. year’s tombstone is gone too, and so is the real value it was shadowing. Two live keys went in as five files’ worth of history; two live keys came out as two files (since we are in one-file-per-key mode), each with its own hint file sitting right next to it, ready for the fast recovery path on the next restart.

Compare and swap

Now comes the kind of scenario that makes life hard: merge reads a key’s old value, then — potentially much later, since merge is designed to run safely while the database keeps taking live writes — tries to repoint the keydir at the copy it just made. If a concurrent put for that same key happened in between those two moments, a naive “just overwrite the keydir” would silently resurrect the stale value merge was copying and lose the real write.

The fix is a compare-and-swap (CAS): merge’s repoint only succeeds if the keydir entry is still exactly what merge observed when it started copying that key. If a racing write already won, merge’s copy just becomes an orphan nobody points to — harmless, and it gets swept up by the next merge pass, since by then it plainly isn’t live either. No locks need to be held across the whole operation, no blocking live traffic for the duration of a merge that could be walking gigabytes of history. It is kinda genius.

Now, the scenario that CAS comes to the rescue of is the kind of thing that gives me pause. Reasoning about multitasking code is tricky, and difficult, and surprising. It gives rise to issues that have eaten man weeks of time and ruined marriages. My approach to reasoning like that is to assume that I am going to miss something, or not get it right. I only know of two approaches to deal with things like that: one is to reach for a formalism or method that would help me with the reasoning; the other is to think of the invariants that the code must maintain for correctness.

In this space, considering serializability and linearizability can help inform the thinking, and more importantly, the testing. Techniques like fault injection and deterministic simulation, property testing and concurrency permutation testing can help here. I have done little of that yet, but I’m looking forward to it.

Closing thoughts

I am left entirely satisfied by the solidity of the design: the tombstone bit, the CAS-repoint, the hint files — so much falls out for free once you commit to “append-only, and scan order that’s also truth order.” Crash recovery isn’t a separate subsystem bolted on; it’s just “replay the log, which you already know how to write.” Concurrent merge isn’t a special locking dance; it’s “ask the same keydir the same question you’d ask for a normal write.” The constraint does the work.

I won’t pretend this is battle-tested — the README says so up front. There’s a known ordering gap where a key written truly concurrently with a merge touching that same key can, in rare cases, get resolved wrong on a subsequent recovery even though the live in-memory keydir stayed correct the whole time; closing it properly needs merge to reuse freed file ids through a carefully-ordered rename I haven’t built yet. should_sync_on_put defaults to false, which means writes survive a process crash but not a real power-cord-out-of-the-wall event unless you opt in. None of that is hidden, but it’s the difference between “I understand this well enough to have written it” and “I’d stake real data on it” and I want to be honest about which side of that line it’s on. I plan on using it in my own projects; something like this always inspires me to do other things. There’s also the issue of performance. I am happy with it, but I’ll do a writeup on it once I have wrapped my head around it. The crate has criterion benchmarks, but I have nothing to compare them against.

Still: there is a particular satisfaction in dumping a file you made and having every byte mean exactly what you expected it to, because you’re the one who decided what it should mean. The paper’s from 2010. It’s a classic.