Topic: The original Bitcask paper's hint file design and how this implementation diverges (e.g., no CRC, variable-length key encoding)

Date: 2026-05-29

Time: 08:44

Bitcask Hint Files: Paper Design vs. Implementation

What the Original Paper Specifies

The Bitcask paper (Sheehy & Smith, 2010) defines hint files as an optimization for startup. Without them, rebuilding the in-memory keydir requires scanning every data file record — reading keys and values just to populate a (file_id, offset, size, timestamp) index. Hint files eliminate this by storing a compact summary of each record alongside the key, so only hint files need to be read on recovery.

The paper's hint entry format is:


| tstamp | ksz | value_sz | value_pos | key |

Where tstamp is a timestamp, ksz is the key size, valuesz is the value size, valuepos is the byte offset of the record in the data file, and key is the actual key bytes. Critically, each hint entry mirrors the data record's header fields — everything needed to reconstruct a keydir entry without touching the data file. The paper also specifies that data records carry a CRC for integrity, and production implementations (like the Erlang Bitcask) extend CRC protection to hint files as well.

Two Implementations, Two Divergences

This repo has two Bitcask implementations that handle hint files quite differently.

hash-index-storage/bitcask.py — Rich but CRC-less hints

This implementation's hint format (bitcask.py:13) is:


HINT_FORMAT = "<IQId"  # file_id(uint32), offset(uint64), size(uint32), timestamp(double)

Each hint entry is written as this fixed header followed by a variable-length key (writehint_file, line 157–165):


f.write(struct.pack(HINT_FORMAT, entry.file_id, entry.offset,
                    entry.size, entry.timestamp))
f.write(struct.pack("<I", len(key_bytes)))
f.write(key_bytes)

And read back the same way (loadhint_file, line 141–154):


fid, offset, size, ts = struct.unpack(HINT_FORMAT, data[pos:pos + HINT_HEADER_SIZE])
pos += HINT_HEADER_SIZE
key_size = struct.unpack("<I", data[pos:pos + 4])[0]
pos += 4
key = data[pos:pos + key_size].decode("utf-8")

Divergences from the paper:

1. No CRC on hint entries. The data record header (HEADERFORMAT = "<dII", line 10) also lacks a CRC — it stores only (timestamp, keysize, value_size). A corrupted hint file will silently load bad index entries. The paper's data records include CRC; production hint files extend that protection.

2. fileid stored explicitly in the hint. The paper's design assumes one hint file per data file, so the fileid is implicit (it's the hint file's own name). This implementation writes fileid into each hint entry (HINTFORMAT includes I for file_id), which is redundant for non-compacted files but necessary during compaction when merged output may span multiple files.

3. No valuesz in hint entries. The paper includes valuesz so the keydir can serve value_size without a disk seek. This implementation stores size (total record size) instead, which works for reads — you know how many bytes to fetch — but loses the ability to report value size without parsing the record header.

4. Variable-length key encoding uses a separate length prefix. The key size is encoded as a 4-byte <I *after* the fixed hint header, rather than being part of the fixed header itself. The paper embeds ksz in the fixed-width header. This is a minor structural difference but means the hint format isn't a single struct.unpack call per entry.

log-structured-hash-table/bitcask.py — Minimal hints with CRC on data

This implementation takes a more stripped-down approach. The hint format (bitcask.py:12) is:


HINT_ENTRY_FMT = "!II"  # key_size, offset

That's it — just 8 bytes of fixed header per entry, followed by the key bytes (loadhint_file, line 108–120):


key_size, offset = struct.unpack(HINT_ENTRY_FMT, header)
key_bytes = f.read(key_size)

Divergences from the paper:

1. No timestamp, no valuesz, no fileid in hints. The hint stores only (keysize, offset). This means the keydir can't know the timestamp without reading the data record, which breaks the paper's invariant that the keydir entry is fully reconstructable from hints alone. The index here stores (segpath, offset) — no timestamp, no size.

2. CRC on data records but not on hints. The data record header (HEADERFMT = "!III", line 10) includes a CRC32 and the implementation validates it on every read (get, line 178–183) and during segment scanning (scan_segment, line 99–100). But hint files have zero integrity protection — a bit flip in a hint offset silently points reads to the wrong location.

3. Hint files don't record tombstones. During loadhint_file (line 108–120), every entry is blindly added to the index. There's no mechanism to represent a deleted key in the hint file. If a segment contains a tombstone, the hint file will point to it, and the get path will return the tombstone sentinel. This is handled by processing segments in order (oldest first) during recovery, so a later segment's live entry overwrites an earlier tombstone — but only if the key was re-written after deletion.

Summary Table

| Feature | Bitcask Paper | hash-index-storage | log-structured-hash-table |

|---|---|---|---|

| CRC on data records | Yes | No | Yes |

| CRC on hint entries | Yes (in production) | No | No |

| Hint fields | tstamp, ksz, valuesz, valuepos, key | fileid, offset, size, timestamp, keysize, key | key_size, offset, key |

| Keydir fully from hints | Yes | Yes | No (missing timestamp, size) |

| Tombstone handling in hints | Omitted from hints | Omitted (filtered during compaction) | Not represented |

| Key length encoding | In fixed header (ksz) | Separate 4-byte prefix after fixed header | In fixed header (key_size) |

The hash-index-storage variant is closer to the paper's spirit (hint files are self-sufficient for keydir reconstruction) but trades away integrity checking. The log-structured-hash-table variant prioritizes data-path correctness (CRC on every read) but treats hint files as a lossy optimization — on recovery, if hints are missing or corrupt, it falls back to a full segment scan.

Topics to Explore

Beliefs