Back
+20 XP
Concept

Embedded Database Part 2: In-Memory Indexing

Scanning append-only logs on every read is $O(N)$ slow. The Bitcask architecture maintains an in-memory index (Keydir) mapping each key to its latest log file offset, delivering $O(1)$ random lookups with a single disk seek ⚡.

python
import io
import struct

class MicroDB:
    def __init__(self):
        self.stream = io.BytesIO()
        self.keydir = {}  # {key: byte_offset}

    def put(self, key, val):
        offset = self.stream.tell()
        kb, vb = key.encode(), val.encode()
        self.stream.write(struct.pack("!II", len(kb), len(vb)) + kb + vb)
        self.keydir[key] = offset  # Latest offset overrides old

    def get(self, key):
        if key not in self.keydir:
            return None
        self.stream.seek(self.keydir[key])
        klen, vlen = struct.unpack("!II", self.stream.read(8))
        self.stream.read(klen)
        return self.stream.read(vlen).decode()

db = MicroDB()
db.put("status", "draft")
db.put("status", "published")
print(f"Latest status: {db.get('status')} ⚡")

# 111. Embedded Database Part 2: In-Memory Indexing Scanning append-only logs on every read is $O(N)$ slow. The Bitcask architecture maintains an in-memory index (Keydir) mapping each key to its latest log file offset, delivering $O(1)$ random lookups with a single disk seek ⚡. ```python import io import struct class MicroDB: def __init__(self): self.stream = io.BytesIO() self.keydir = {} # {key: byte_offset} def put(self, key, val): offset = self.stream.tell() kb, vb = key.encode(), val.encode() self.stream.write(struct.pack("!II", len(kb), len(vb)) + kb + vb) self.keydir[key] = offset # Latest offset overrides old def get(self, key): if key not in self.keydir: return None self.stream.seek(self.keydir[key]) klen, vlen = struct.unpack("!II", self.stream.read(8)) self.stream.read(klen) return self.stream.read(vlen).decode() db = MicroDB() db.put("status", "draft") db.put("status", "published") print(f"Latest status: {db.get('status')} ⚡") ``` Because the index resides entirely in RAM, write performance is bound solely by sequential disk append speeds, easily exceeding 100,000 writes/sec on modern NVMe drives 🚀! --- ### Question What is the primary memory advantage of keeping only key offsets in RAM (Bitcask pattern)? 🧠 - [ ] a. Keys and 8-byte offsets fit in memory, letting databases serve datasets far larger than total RAM with $O(1)$ speed ⚡ - [ ] b. Linux RAM cannot store string data structures - [ ] c. Offset pointers bypass operating system file permission checks - [ ] d. It prevents all possible SSD wear and tear --- ### Challenge Build `MicroDB` with in-memory offset indexing. Put `('color', 'red')`, then update with `('color', 'blue')`. Call `get('color')` and print the value. 🎯 <details> <summary>Solution</summary> ```python import io import struct class MicroDB: def __init__(self): self.stream = io.BytesIO() self.keydir = {} def put(self, k, v): off = self.stream.tell() kb, vb = k.encode(), v.encode() self.stream.write(struct.pack('!II', len(kb), len(vb)) + kb + vb) self.keydir[k] = off def get(self, k): if k not in self.keydir: return None self.stream.seek(self.keydir[k]) klen, vlen = struct.unpack('!II', self.stream.read(8)) self.stream.read(klen) return self.stream.read(vlen).decode() db = MicroDB() db.put('color', 'red') db.put('color', 'blue') print(db.get('color')) ``` </details>

Checkpoint

What is the primary memory advantage of keeping only key offsets in RAM (Bitcask pattern)? 🧠

Practice

Build `MicroDB` with in-memory offset indexing. Put `('color', 'red')`, then update with `('color', 'blue')`. Call `get('color')` and print the value. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks