Log on disk, hash in RAM

A Bitcask is exactly two structures: an append-only log of records on disk and a single in-memory hash (the keydir) mapping each live key to the byte offset of its newest record.

Scene 01

Log on disk, hash in RAM

Watch
Try it
Predict
Capture

What to watch for

An empty Bitcask: no data files written, no keydir rows. Watch what a PUT actually does — one record lands on disk, one row appears in the keydir. Two structures, growing in lockstep.

Implementation

Highlighted lines are the ones running in the diagram right now.

Record on disk

fixed-size header + two variable blobs; appended at tail

1# one entry in <file_id>.data, written end-to-end:
2record = struct(
3    crc: u32, # checksum of the bytes that follow
4    tstamp: u32, # logical write time
5    ksz: u32, # key size in bytes
6    vsz: u32, # value size in bytes
7    key: bytes[ksz],
8    value: bytes[vsz],
9)
10# closed files are immutable forever; only the active file appends.

Bitcask.put

append a record at the active tail, then retarget the keydir slot

1def put(key, value):
2    tstamp = now()
3    bytes = encode(crc, tstamp, len(key), len(value), key, value)
4    offset = active_file.size # current end-of-file
5    active_file.append(bytes) # sequential write
6    fsync_if_policy(active_file) # sync_strategy
7    keydir[key] = Entry(
8        file_id = active_file.id,
9        value_pos = offset + header_sz + len(key),
10        value_sz = len(value),
11        tstamp = tstamp,
12    ) # one slot per LIVE key
13    return ok

Bitcask.get

one hash lookup; one pread at the recorded offset

1def get(key):
2    entry = keydir.lookup(key)
3    if entry is None: return not_found
4    fd = open_or_reuse(entry.file_id)
5    bytes = pread(fd, entry.value_pos, entry.value_sz)
6    return bytes # at most one disk seek

Sources

Where this sits in Build a Bitcask-style KV store

Scene 01 of 9, in the Anatomy act — Log on disk, hash in RAM — and the four-step write.. A Bitcask is exactly two structures: an append-only log of records on disk + a single in-memory hash (the keydir). Every other property follows from this split.

Up next. Two structures, two responsibilities — but every PUT touches both, in a specific order. Get the order wrong and the ack means nothing. Time to look at the four steps the writer actually takes.

All 9 scenes in Build a Bitcask-style KV store · Every curriculum

Designs that use this

Built with Arqly

Every scene in Build a Bitcask-style KV store builds on the one before it.All 9 Build a Bitcask-style KV store scenes