S1 - Build Your Own Database

S1 · BUILD YOUR OWN DATABASE a log-structured key–value store · Bitcask model · ~150 lines of Go README / RESUME LINE “Built a persistent key–value store in Go: log-structured storage, WAL, in-memory hash index, crash recovery & compaction — ~50k writes/sec, fsync batched.” THE API · what a user calls db.Put(key, val) store / overwrite db.Get(key) read it back db.Delete(key) write a tombstone 1 · IN-MEMORY INDEX · a hash map key -> file offset size "user:1" -> log.0 0 40 "cart:9" -> log.0 40 30 "user:1" -> log.0 70 45 same key twice? newest offset wins lookup = O(1) -> value is ONE seek away 2 · APPEND-ONLY LOG · on disk, sequential writes user:1 @0 v='A' cart:9 @40 user:1 @70 (new!) user:1 ☠ tombstone append grows → writes only ever APPEND → disk does pure sequential I/O → fast + crash-safe (WAL) 1. append points at bytes ONE RECORD ON DISK · byte layout crc32 4 ksz 4 vsz 4 key … val … checksum catches disk corruption on read 3 · COMPACTION · reclaim dead space OLD LOG (bloated) user:1=A [dead] cart:9=X [live] user:1=B [live] user:1 [dead ☠] merge NEW LOG (only live keys) cart:9=X user:1=B stale + tombstones dropped → space freed a HINT file stores the index so restart is instant — no full log replay needed to rebuild the map. ( this is literally how Riak, LevelDB & RocksDB think ) JARGON, DECODED WAL = write-ahead log: append the change BEFORE acking → a crash mid-write can't lose data. log-structured = never edit in place; only append. Reads follow the index, not a scan. compaction = periodically rewrite the log keeping only the newest live value per key. offset = byte position in the file; a Get is seek(offset)+read(size), not a linear search.