One hash lookup, one pread

A get is a constant-time keydir lookup followed by exactly one pread at the recorded offset — bounded at one disk seek worst case, and zero seeks when the page cache is hot.

Previously

The writer was sequential because the disk cares. The keydir doesn't — it's a hash, and lookups are O(1). One pread closes the loop.

Scene 03

One hash lookup, one pread

Watch
Try it
Predict
Capture

What to watch for

Watch a single GET k1. The keydir row pulses, an arrow flies to file 002 at offset 1432, and the pread cursor highlights exactly value_sz bytes — not the whole record (value_pos already skips the header). The pread counter ticks up by one.

Implementation

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

KeydirEntry (struct)

fixed-size RAM entry per live key — no value bytes

1struct KeydirEntry:
2    file_id    # which .data file holds the live record
3    value_pos  # byte offset of the VALUE (header skipped)
4    value_sz   # exact length to pread
5    tstamp     # last-write timestamp (wins on replay)

Bitcask.get

O(1) keydir lookup, then one pread at the recorded offset

1def get(key):
2    entry = keydir.get(key)        # O(1) hash probe
3    if entry is None:
4        return None                # key never existed / deleted
5    fd = fd_cache.open(entry.file_id)
6    buf = pread(fd,
7                n=entry.value_sz,  # exactly value_sz bytes
8                offset=entry.value_pos)
9    return buf                     # caller may verify CRC

OS.pread (kernel)

the syscall is the same; the kernel decides if disk is touched

1def pread(fd, n, offset):
2    page = (offset // PAGE_SIZE) * PAGE_SIZE
3    if page in page_cache:         # HOT — bytes already in RAM
4        return copy_from(page_cache[page], offset, n)
5    block = disk.seek_and_read(fd, page)  # COLD — one seek
6    page_cache[page] = block
7    return copy_from(block, offset, n)

Sources

Where this sits in Build a Bitcask-style KV store

Scene 03 of 9, in the Anatomy act — Log on disk, hash in RAM — and the four-step write.. get is a constant-time keydir lookup + at most one pread; bounded by one disk seek, zero when the page cache is hot.

Up next. One seek for any read, hot or cold. That ceiling exists because the index lives in RAM. The next scene asks how much RAM.

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