Persistent Key-Value Store on Disk
Embedded databases like Bitcask and dbm achieve immense write speeds using an append-only log paired with an in-memory hash index. Writes append records to the end of the log and update in-memory file offsets, allowing O(1) random disk seeks for key lookups.
import struct
# Write record: [KEY_LEN: 2B, VAL_LEN: 4B, KEY, VAL]
hdr = struct.pack('>HI', len(key), len(val))
file.seek(0, 2) # Seek to end of file
# Persistent Key-Value Store on Disk When you need an ultra-fast embedded key-value store without running a separate PostgreSQL or Redis server, how does an engine like Riak’s Bitcask achieve 50,000 writes per second on rotating hard drives? 💾⚡ The secret is **Append-Only Logging + In-Memory Indexing**: 1. **`set(key, value)`**: Never modifies old data in place. It appends a binary record `[klen: uint16, vlen: uint32, key, val]` to the end of the log file in a single sequential disk write, and updates an in-memory dictionary `index[key] = (file_offset, vlen)`. Sequential disk writes are up to 100x faster than random writes. 2. **`get(key)`**: Looks up `(offset, vlen)` in the in-memory index in $O(1)$ time, performs a single `f.seek(offset)` to the exact byte, and reads `vlen` bytes. 3. **Startup Recovery**: On boot, scan the log file once from start to finish to rebuild the index. ```python import struct # Record: 2 bytes KEY_LEN + 4 bytes VAL_LEN header = struct.pack(">HI", len(key_bytes), len(val_bytes)) ``` ## Pop Quiz Why does the Bitcask append-only storage architecture achieve faster write throughput than B-tree databases? - [ ] Every write is a purely sequential disk append without requiring random disk seeks or page splits. - [ ] It compresses data blocks using LZO algorithms inside CPU registers. - [ ] It skips file flushing and relies on operating system swap space. - [ ] Because Bitcask files bypass the operating system kernel cache entirely. ## Real-World Challenge Implement `DiskKVStore(filepath: str)`. - Rebuilds an in-memory hash index on instantiation by scanning any existing file records. - `set(key: str, value: bytes)`: Appends binary record to disk, flushes, and updates the in-memory index. - `get(key: str) -> bytes`: Seeks directly to the value offset and reads the bytes. Raises `KeyError` if absent. - `close()`: Flushes and closes file handles. <details> <summary>Solution</summary> ```python import struct import os class DiskKVStore: HEADER_FORMAT = ">HI" # 2 bytes key length, 4 bytes value length HEADER_SIZE = struct.calcsize(HEADER_FORMAT) def __init__(self, filepath: str): self.filepath = filepath self._index = {} # key -> (offset, val_length) self._file = open(filepath, "a+b") self._rebuild_index() def _rebuild_index(self): self._file.seek(0) while True: header_bytes = self._file.read(self.HEADER_SIZE) if len(header_bytes) < self.HEADER_SIZE: break klen, vlen = struct.unpack(self.HEADER_FORMAT, header_bytes) key_bytes = self._file.read(klen) key = key_bytes.decode("utf-8") val_offset = self._file.tell() self._file.seek(val_offset + vlen) # Latest append supersedes previous writes for the same key self._index[key] = (val_offset, vlen) def set(self, key: str, value: bytes): kbytes = key.encode("utf-8") header = struct.pack(self.HEADER_FORMAT, len(kbytes), len(value)) self._file.seek(0, os.SEEK_END) self._file.write(header) self._file.write(kbytes) val_offset = self._file.tell() self._file.write(value) self._file.flush() self._index[key] = (val_offset, len(value)) def get(self, key: str) -> bytes: if key not in self._index: raise KeyError(f"Key '{key}' not found") offset, length = self._index[key] self._file.seek(offset) return self._file.read(length) def close(self): if not self._file.closed: self._file.flush() self._file.close() # Verification db_file = "/tmp/test_persistent_kv.db" if os.path.exists(db_file): os.remove(db_file) db1 = DiskKVStore(db_file) db1.set("session:alpha", b"ACTIVE_TOKEN_1") db1.set("session:beta", b"EXPIRED_TOKEN_2") db1.set("session:alpha", b"RENEWED_TOKEN_3") # Append overwrite assert db1.get("session:alpha") == b"RENEWED_TOKEN_3" assert db1.get("session:beta") == b"EXPIRED_TOKEN_2" db1.close() # Re-open in fresh instance and verify persistence recovery db2 = DiskKVStore(db_file) assert db2.get("session:alpha") == b"RENEWED_TOKEN_3" assert db2.get("session:beta") == b"EXPIRED_TOKEN_2" db2.close() os.remove(db_file) ``` </details>