File: hash-index-storage/bitcask.py

Date: 2026-05-28

Time: 18:08

hash-index-storage/bitcask.py

Purpose

This file implements a Bitcask-style append-only key-value storage engine — the canonical hash-indexed log structure described in DDIA Chapter 3. It owns the full storage lifecycle: writing key-value records to append-only data files, maintaining an in-memory hash index (keydir) for O(1) lookups, and compacting old files to reclaim space from stale/deleted entries.

Bitcask is the simplest practical storage engine that separates the write path (sequential append) from the read path (random seek via index), trading RAM for read performance.

Key Components

Constants

KeyEntry (dataclass)

The in-memory index record. Maps a key to its physical location: which file_id, at what byte offset, how many bytes (size), and the write timestamp. This is the value type in the keydir hash map.

BitcaskStore

The main engine. Constructor parameters:

| Param | Default | Role |

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

| data_dir | required | Directory for all .data and .hint files |

| maxfilesize | 10 MB | Threshold for rotating to a new data file |

| sync_writes | True | Whether to fsync after every write (durability vs. throughput) |

Core state:

Patterns

1. Append-only log with in-memory index — Writes never overwrite; they append a new record and update the keydir pointer. This makes writes sequential and crash-safe (partial writes are just trailing garbage).

2. Tombstone deletion — delete() writes a record with an empty value ("") and removes the key from keydir. During compaction and index rebuild, zero-length values are treated as tombstones.

3. File rotation — When the active file exceeds maxfilesize, it becomes immutable and a new file takes over. Only immutable files are candidates for compaction.

4. Hint files — After compaction, a .hint file is written alongside each merged .data file. Hint files contain only index metadata (no values), so startup recovery can skip the expensive full-scan path via loadhintfile instead of scandatafile.

5. Single-writer model — There is exactly one active (writable) file at any time. All older files are read-only. This avoids write contention without locks.

Dependencies

Imports: Only stdlib — os, struct, time, dataclasses, typing. No external dependencies. This is intentional for a reference implementation.

Imported by: Test files in both hash-index-storage/ and log-structured-hash-table/, suggesting the latter reuses or mirrors this implementation for comparison.

Flow

Write path (put)


put(key, value)
  → _maybe_rotate()          # check if active file is full
  → _write_record(key, value) # pack header + key + value, append, flush, fsync
  → update keydir[key]        # point to new record location

Read path (get)


get(key)
  → keydir.get(key)           # O(1) hash lookup
  → _read_record(fid, off, sz) # seek + read from the right data file
  → assert key matches        # integrity check
  → return value (or None if tombstone)

Startup recovery (_init_)


__init__
  → _find_file_ids()          # scan directory for *.data files
  → _rebuild_index(ids)       # for each file: use hint file if available, else scan data file
  → _open_active_file()       # open the highest-numbered file for appending

Compaction (compact)

1. Identify immutable files (everything except active).

2. Scan them chronologically, keeping only the latest record per key (tombstones evict).

3. Filter further: skip keys whose keydir entry points to the active file (those immutable records are already stale).

4. Write surviving records into new merged file(s) with new file IDs.

5. Write hint files for the merged files.

6. Delete old immutable data and hint files.

7. Renumber the active file to sit after the merged files and reopen it.

Invariants

Error Handling

Minimal — appropriate for a reference implementation, but notable gaps:

Topics to Explore

Beliefs