Function: createhintfiles in log-structured-hash-table/bitcask.py

Date: 2026-05-29

Time: 06:47

createhintfiles — Bitcask Hint File Generator

Purpose

Hint files are a startup optimization. Normally, recovering the in-memory index requires scanning every record in every segment file — reading headers, keys, values, and CRCs. A hint file is a compact summary that stores only (keysize, offset, key) tuples, skipping the values entirely. On recovery, loadhintfile can rebuild the index from hint files in a fraction of the time, since it never touches the (potentially large) values.

createhintfiles generates these hint files for all frozen (non-active) segments. It's a batch operation — typically called after compaction or as a maintenance step.

Contract

• Precondition: self._index must be current and accurate. The method uses the index to determine which records are still live, so a stale index produces incorrect hint files.
• Precondition: The active segment file path (self.activepath) must be set.
• Postcondition: Every frozen segment gets a .hint file alongside its .dat file containing entries only for keys whose canonical location (per the index) is that specific segment at that specific offset.
• Invariant: Hint files never contain tombstones or stale entries.

Parameters

None — operates entirely on instance state (self.index, self.active_path, and the segment files on disk).

Return Value

None. This is a side-effect-only method.

Algorithm

1. Enumerate segments via findexistingsegments(), which lists all segmentNNNNNN.dat files sorted by ID.

2. Skip the active segment — it's still being written to, so a hint file would be immediately stale.

3. For each frozen segment, open a new hint file (overwriting any existing one) and scan the segment record by record:

• Read the 12-byte header (crc32, keysize, valuesize).
• Read the payload (keybytes + valuebytes).
• Skip tombstones — deleted keys don't belong in the hint file.
• Check the index: only emit a hint entry if self._index[key] points to *this exact segment and offset*. This is the critical filter — if a key was overwritten in a later segment, the old entry is stale and excluded.

4. Each hint entry is written as: struct.pack("!II", key_size, offset) followed by the raw key bytes.

The index check at step 3 is what makes this correct after compaction or repeated writes. Without it, the hint file would contain stale entries that point to values that are no longer the canonical version.

Side Effects

• Disk I/O: Creates or overwrites .hint files for every frozen segment. The hint file path is derived by replacing .dat with .hint in the segment filename.
• No index mutation: The in-memory index is read but never modified.
• No CRC validation: Unlike scansegment, this method does not verify the CRC of records it reads. It trusts that the segment data is intact.

Error Handling

There is essentially none. The method will raise:

• FileNotFoundError if a segment file has been deleted between enumeration and opening.
• struct.error if a file is corrupted in a way that produces a valid-length but unparseable header.
• UnicodeDecodeError if a key contains invalid UTF-8.

Partial reads (short header or payload) are handled gracefully by breaking out of the scan loop — this handles truncated segments from crashes.

Usage Patterns

Typically called:

• After compact() to generate hint files for the newly compacted segment.
• As a periodic maintenance operation.
• Before shutdown to speed up the next startup.

Note that compact() itself does not call createhintfiles, so the caller must do it explicitly. During recovery, _recover checks for hint files and uses them when present, falling back to full segment scans otherwise.

Dependencies

• struct for binary encoding/decoding of headers and hint entries.
• findexisting_segments() for segment enumeration.
• hintpath() for deriving the hint file path (.dat → .hint replacement).
• The HEADERFMT, HEADERSIZE, HINTENTRYFMT module-level constants.
• TOMBSTONE sentinel value for identifying deleted records.

Unenforced Assumptions

• Index accuracy: The method silently produces wrong hint files if the index is out of sync with disk. There's no validation.
• No concurrent writers: If another process or thread is writing to a segment while hint files are being generated, the results are undefined.
• Segment file format integrity: CRCs are not checked — a corrupted value could be indexed via the hint file, and the corruption would only surface on get().
• Hint file atomicity: The hint file is written directly, not via a temp-file-and-rename pattern. A crash mid-write leaves a partial hint file, which loadhint_file handles by stopping at the first short read — but this means some valid entries may be lost, requiring a full segment scan on next recovery for segments without complete hint files.

Beliefs

• hint-files-skip-tombstones — Hint files never contain entries for tombstoned (deleted) keys; tombstones are filtered during generation and absent from the hint format
• hint-files-only-canonical-entries — A hint entry is written only when the in-memory index confirms that the key's canonical location is the current segment and offset, preventing stale entries
• hint-generation-skips-active-segment — createhintfiles never generates a hint file for the active segment, only for frozen (immutable) segments
• hint-generation-no-crc-validation — Unlike scansegment, createhintfiles does not verify CRC checksums on the records it reads, meaning corrupted data can be indexed via hint files
• hint-file-write-not-atomic — Hint files are written directly (not via temp-file-and-rename), so a crash during generation can leave a partial hint file that causes incomplete index recovery