Build a Key Value Store in Go From Scratch With a Log
Build a durable key value store in Go: an append only log, an in-memory index, crash recovery and compaction, with fsync costing 4.9ms a write
Most programmers use databases for years without ever writing one. The fastest way to understand what a database promises, and what that costs, is to build the smallest honest one. This article builds a key value store in Go 1.25.6 using only the standard library: a durable, concurrent, crash safe map from string keys to byte values, stored in one file. It follows the design of Bitcask, the storage engine that Basho published for Riak, which is the simplest design that is also a real one: an append only log plus an index in memory. By the end you will have code that survives a kill in the middle of a write, a compaction that reclaims space, tests that prove both, and measurements of what each guarantee costs.
Tested with Go 1.25.6, standard library only, macOS on Apple Silicon (arm64)
It belongs to the database cornerstone. The production grade versions of the ideas here are compared in embedded key value stores, and the next project, a tiny database engine, adds pages, an index and a write ahead log on top of the same ideas.
The design in one paragraph
Every change, an insert, an overwrite or a delete, is appended as a record at the end of one file. Nothing in the file is ever modified in place. A map in memory records, for each key, where in the file its latest record sits. A read looks the key up in the map and reads the value from that position with one ReadAt. A write appends and updates the map. To restart, read the file from the beginning and replay it, which rebuilds the map. To reclaim the space taken by old versions, copy the live records to a new file and swap it in.
That is the whole engine. Its properties follow from the design: writes are sequential, which disks do well; reads are one lookup and one read; recovery is a scan; and all keys must fit in memory. The rest of the article is the details that make it correct.
The record format
package main
import (
"bufio"
"encoding/binary"
"errors"
"fmt"
"hash/crc32"
"io"
"os"
"sync"
)
var ErrNotFound = errors.New("key not found")
// A record on disk: crc32 (4) | key length (4) | value length (4, all ones marks a delete) | key | value.
// The checksum covers everything after it, so a record cut short by a crash is detected when the log is read.
const headerSize = 12
const tombstone = ^uint32(0)
type entry struct {
offset int64 // where the record starts
size int64 // the whole record
vlen uint32
}
// Store is an append only log with an in memory index from key to the position of its latest value.
type Store struct {
mu sync.RWMutex
path string
f *os.File
end int64
index map[string]entry
synced bool
}
// Open reads the log from the start to rebuild the index, and cuts off a torn record at the end.
func Open(path string, syncEveryWrite bool) (*Store, error) {
f, err := os.OpenFile(path, os.O_RDWR|os.O_CREATE, 0o600)
if err != nil {
return nil, err
}
s := &Store{path: path, f: f, index: map[string]entry{}, synced: syncEveryWrite}
if err := s.load(); err != nil {
f.Close()
return nil, err
}
return s, nil
}
func (s *Store) load() error {
r := bufio.NewReader(io.NewSectionReader(s.f, 0, 1<<62))
var off int64
for {
hdr := make([]byte, headerSize)
if _, err := io.ReadFull(r, hdr); err != nil {
break // a clean end, or a header cut short
}
klen, vlen := binary.BigEndian.Uint32(hdr[4:8]), binary.BigEndian.Uint32(hdr[8:12])
n := int64(klen)
if vlen != tombstone {
n += int64(vlen)
}
body := make([]byte, n)
if _, err := io.ReadFull(r, body); err != nil {
break // a record cut short by a crash
}
sum := crc32.NewIEEE()
sum.Write(hdr[4:])
sum.Write(body)
if sum.Sum32() != binary.BigEndian.Uint32(hdr[0:4]) {
break // a record written only in part, or damaged
}
key := string(body[:klen])
size := int64(headerSize) + n
if vlen == tombstone {
delete(s.index, key)
} else {
s.index[key] = entry{off, size, vlen}
}
off += size
}
// Anything after the last good record is garbage from an interrupted write: remove it so new records start cleanly.
if err := s.f.Truncate(off); err != nil {
return err
}
s.end = off
return nil
}
func encode(key string, value []byte, deleted bool) []byte {
vlen := uint32(len(value))
if deleted {
vlen = tombstone
value = nil
}
buf := make([]byte, headerSize+len(key)+len(value))
binary.BigEndian.PutUint32(buf[4:8], uint32(len(key)))
binary.BigEndian.PutUint32(buf[8:12], vlen)
copy(buf[headerSize:], key)
copy(buf[headerSize+len(key):], value)
binary.BigEndian.PutUint32(buf[0:4], crc32.ChecksumIEEE(buf[4:]))
return buf
}
func (s *Store) append(rec []byte) (int64, error) {
if _, err := s.f.WriteAt(rec, s.end); err != nil {
return 0, err
}
if s.synced {
if err := s.f.Sync(); err != nil {
return 0, err
}
}
off := s.end
s.end += int64(len(rec))
return off, nil
}
func (s *Store) Put(key string, value []byte) error {
rec := encode(key, value, false)
s.mu.Lock()
defer s.mu.Unlock()
off, err := s.append(rec)
if err != nil {
return err
}
s.index[key] = entry{off, int64(len(rec)), uint32(len(value))}
return nil
}
func (s *Store) Get(key string) ([]byte, error) {
s.mu.RLock()
defer s.mu.RUnlock()
e, ok := s.index[key]
if !ok {
return nil, ErrNotFound
}
value := make([]byte, e.vlen)
if _, err := s.f.ReadAt(value, e.offset+e.size-int64(e.vlen)); err != nil {
return nil, fmt.Errorf("read %q: %w", key, err)
}
return value, nil
}
func (s *Store) Delete(key string) error {
s.mu.Lock()
defer s.mu.Unlock()
if _, ok := s.index[key]; !ok {
return ErrNotFound
}
if _, err := s.append(encode(key, nil, true)); err != nil {
return err
}
delete(s.index, key)
return nil
}
func (s *Store) Len() int {
s.mu.RLock()
defer s.mu.RUnlock()
return len(s.index)
}
func (s *Store) Size() int64 {
s.mu.RLock()
defer s.mu.RUnlock()
return s.end
}
func (s *Store) Sync() error { return s.f.Sync() }
// Compact writes only the live records to a new file and swaps it in, which is how overwritten and deleted data is reclaimed.
func (s *Store) Compact() error {
s.mu.Lock()
defer s.mu.Unlock()
tmp := s.path + ".compact"
nf, err := os.OpenFile(tmp, os.O_RDWR|os.O_CREATE|os.O_TRUNC, 0o600)
if err != nil {
return err
}
newIndex := make(map[string]entry, len(s.index))
var off int64
for key, e := range s.index {
rec := make([]byte, e.size)
if _, err := s.f.ReadAt(rec, e.offset); err != nil {
nf.Close()
return err
}
if _, err := nf.WriteAt(rec, off); err != nil {
nf.Close()
return err
}
newIndex[key] = entry{off, e.size, e.vlen}
off += e.size
}
if err := nf.Sync(); err != nil {
nf.Close()
return err
}
if err := os.Rename(tmp, s.path); err != nil {
nf.Close()
return err
}
s.f.Close()
s.f, s.index, s.end = nf, newIndex, off
return nil
}
func (s *Store) Close() error {
s.mu.Lock()
defer s.mu.Unlock()
if err := s.f.Sync(); err != nil {
return err
}
return s.f.Close()
}A record on disk is a 12 byte header followed by the key and value bytes: a CRC32 checksum of everything after it, the key length, and the value length. Three details matter.
The checksum covers the lengths and the data. When a process dies in the middle of a write, the file ends with half a record. A reader that trusted the lengths would read garbage or run off the end. With the checksum, load can tell a complete, intact record from a partial or damaged one, and stop at the first bad one. Without it, a crash would be silent corruption.
A delete is a record, not an absence. The delete record has no value and a value length of all ones (tombstone). Replaying the log, a delete record removes the key from the index. If deletes were only an in memory removal, a restart would resurrect every deleted key from its older records.
Records are self describing. Anyone can walk the file from byte zero with no other metadata: read a header, read klen and vlen bytes, verify, continue. That is why recovery needs no separate manifest.
Writing, reading, deleting
Put encodes the record and, under the write lock, appends it with WriteAt at the current end of file, then points the index at it. Get takes the read lock, looks up the entry and reads exactly the value bytes from offset + size - vlen, since the value is the last part of the record. Delete appends a tombstone and removes the key from the index, and returns ErrNotFound for a key that was not there.
A sync.RWMutex guards the index and the end offset, so reads run in parallel and writes take turns. The file is accessed with WriteAt and ReadAt, which do not share a seek position, so a reader never disturbs a writer. The concurrency test runs eight goroutines each writing and reading back 200 keys under the race detector, and ends with 1,600 keys.
Recovery
Open calls load, which reads the file front to back through a buffered reader. For each record it reads the header, then the body, verifies the checksum, updates the index and advances the offset. The first record that is incomplete or fails its checksum ends the scan, and load then truncates the file to the end of the last good record. That last step matters. If you left the garbage in place and appended new records after it, the next recovery would stop at the garbage and never see them, losing acknowledged writes.
Two tests prove it. TestTornWriteIsDropped writes two keys, then a 500 byte value, and cuts the file 100 bytes into the last record, as a crash would. After reopening, the torn key is gone, the two before it are intact, and the log is back to its length before the torn record (45 bytes, as the log line shows). It then writes a new key, reopens again, and finds it, showing the recovered log is usable. TestCorruptionIsDetected flips bits inside the last value instead, and shows the damaged record is rejected and the earlier one kept.
The whole test file follows, with its output after the last block. It covers the basic operations, reopening, the torn write, a damaged record, compaction, concurrent use and the every cut point sweep described below. It runs under the race detector, which matters here because the index is shared state.
package main
import (
"bytes"
"errors"
"fmt"
"os"
"path/filepath"
"sync"
"testing"
)
func open(t *testing.T) (*Store, string) {
t.Helper()
path := filepath.Join(t.TempDir(), "data.log")
s, err := Open(path, false)
if err != nil {
t.Fatal(err)
}
return s, path
}
func TestPutGetDelete(t *testing.T) {
s, _ := open(t)
defer s.Close()
if err := s.Put("a", []byte("one")); err != nil {
t.Fatal(err)
}
if err := s.Put("a", []byte("uno")); err != nil { // overwrite
t.Fatal(err)
}
got, err := s.Get("a")
if err != nil || string(got) != "uno" {
t.Fatalf("Get after overwrite: %q, %v", got, err)
}
if err := s.Delete("a"); err != nil {
t.Fatal(err)
}
if _, err := s.Get("a"); !errors.Is(err, ErrNotFound) {
t.Fatalf("Get after Delete: %v, want ErrNotFound", err)
}
if err := s.Delete("a"); !errors.Is(err, ErrNotFound) {
t.Fatalf("second Delete: %v", err)
}
}
func TestReopenRebuildsTheIndex(t *testing.T) {
s, path := open(t)
for i := 0; i < 1000; i++ {
_ = s.Put(fmt.Sprintf("k%d", i), []byte(fmt.Sprintf("v%d", i)))
}
_ = s.Delete("k10")
_ = s.Put("k20", []byte("changed"))
s.Close()
s2, err := Open(path, false)
if err != nil {
t.Fatal(err)
}
defer s2.Close()
if s2.Len() != 999 {
t.Fatalf("keys after reopen: %d, want 999", s2.Len())
}
if v, _ := s2.Get("k20"); string(v) != "changed" {
t.Fatalf("k20 = %q", v)
}
if _, err := s2.Get("k10"); !errors.Is(err, ErrNotFound) {
t.Fatalf("deleted key came back: %v", err)
}
t.Logf("reopened: %d keys, log is %d bytes", s2.Len(), s2.Size())
}
// A crash can leave half a record at the end of the log. Open must keep everything before it and drop the rest.
func TestTornWriteIsDropped(t *testing.T) {
s, path := open(t)
_ = s.Put("keep1", []byte("first"))
_ = s.Put("keep2", []byte("second"))
good := s.Size()
_ = s.Put("torn", bytes.Repeat([]byte("x"), 500))
s.Close()
// Cut the file in the middle of the last record, as a crash would.
if err := os.Truncate(path, good+100); err != nil {
t.Fatal(err)
}
s2, err := Open(path, false)
if err != nil {
t.Fatal(err)
}
defer s2.Close()
if _, err := s2.Get("torn"); !errors.Is(err, ErrNotFound) {
t.Fatalf("the torn record survived: %v", err)
}
if v, _ := s2.Get("keep2"); string(v) != "second" {
t.Fatalf("keep2 = %q", v)
}
if s2.Size() != good {
t.Fatalf("log length %d, want %d: the torn tail was not removed", s2.Size(), good)
}
// New writes after recovery must be readable again after another reopen.
_ = s2.Put("after", []byte("recovery"))
s2.Close()
s3, _ := Open(path, false)
defer s3.Close()
if v, _ := s3.Get("after"); string(v) != "recovery" {
t.Fatalf("write after recovery lost: %q", v)
}
t.Logf("torn tail of %d bytes removed; log back to %d bytes", 100, good)
}
func TestCorruptionIsDetected(t *testing.T) {
s, path := open(t)
_ = s.Put("a", []byte("aaaaaaaa"))
good := s.Size()
_ = s.Put("b", []byte("bbbbbbbb"))
s.Close()
data, _ := os.ReadFile(path)
data[len(data)-2] ^= 0xff // flip bits in the last value
_ = os.WriteFile(path, data, 0o600)
s2, _ := Open(path, false)
defer s2.Close()
if _, err := s2.Get("b"); !errors.Is(err, ErrNotFound) || s2.Size() != good {
t.Fatalf("a damaged record was accepted: %v, size %d", err, s2.Size())
}
}
func TestCompactionReclaimsSpace(t *testing.T) {
s, path := open(t)
defer s.Close()
for round := 0; round < 20; round++ {
for i := 0; i < 100; i++ {
_ = s.Put(fmt.Sprintf("k%d", i), bytes.Repeat([]byte{byte(round)}, 100))
}
}
for i := 0; i < 50; i++ {
_ = s.Delete(fmt.Sprintf("k%d", i))
}
before := s.Size()
if err := s.Compact(); err != nil {
t.Fatal(err)
}
after := s.Size()
if v, err := s.Get("k75"); err != nil || len(v) != 100 || v[0] != 19 {
t.Fatalf("k75 after compaction: %v %v", v[:1], err)
}
if _, err := s.Get("k10"); !errors.Is(err, ErrNotFound) {
t.Fatalf("deleted key back after compaction")
}
info, _ := os.Stat(path)
t.Logf("log before compaction %d bytes, after %d bytes (file on disk %d), %d keys", before, after, info.Size(), s.Len())
if after >= before/10 {
t.Fatalf("compaction kept too much: %d of %d", after, before)
}
}
func TestConcurrentUse(t *testing.T) {
s, _ := open(t)
defer s.Close()
var wg sync.WaitGroup
for w := 0; w < 8; w++ {
wg.Add(1)
go func() {
defer wg.Done()
for i := 0; i < 200; i++ {
k := fmt.Sprintf("w%d-%d", w, i)
if err := s.Put(k, []byte(k)); err != nil {
t.Error(err)
return
}
if v, err := s.Get(k); err != nil || string(v) != k {
t.Errorf("Get(%q) = %q, %v", k, v, err)
return
}
}
}()
}
wg.Wait()
if s.Len() != 1600 {
t.Fatalf("%d keys, want 1600", s.Len())
}
}
// Cut the log at every byte offset, as a crash at any moment could, and check that Open always succeeds and
// that what it returns is exactly the state after the last complete record.
func TestEveryCutPoint(t *testing.T) {
s, path := open(t)
type step struct {
key string
value string
del bool
end int64 // log length after this step
}
var steps []step
for i := 0; i < 40; i++ {
k := fmt.Sprintf("k%d", i%7)
if i%5 == 4 {
if err := s.Delete(k); err == nil {
steps = append(steps, step{k, "", true, s.Size()})
}
continue
}
v := fmt.Sprintf("value-%d", i)
_ = s.Put(k, []byte(v))
steps = append(steps, step{k, v, false, s.Size()})
}
full := s.Size()
s.Close()
data, _ := os.ReadFile(path)
for cut := int64(0); cut <= full; cut++ {
dir := t.TempDir()
p := filepath.Join(dir, "cut.log")
if err := os.WriteFile(p, data[:cut], 0o600); err != nil {
t.Fatal(err)
}
c, err := Open(p, false)
if err != nil {
t.Fatalf("cut at %d: Open failed: %v", cut, err)
}
want := map[string]string{}
for _, st := range steps {
if st.end > cut {
break
}
if st.del {
delete(want, st.key)
} else {
want[st.key] = st.value
}
}
if c.Len() != len(want) {
t.Fatalf("cut at %d: %d keys, want %d", cut, c.Len(), len(want))
}
for k, v := range want {
if got, err := c.Get(k); err != nil || string(got) != v {
t.Fatalf("cut at %d: %s = %q, %v; want %q", cut, k, got, err, v)
}
}
c.Close()
}
t.Logf("%d cut points, from an empty file to the whole %d byte log: every one recovered to the last complete record", full+1, full)
}=== RUN TestPutGetDelete
--- PASS: TestPutGetDelete (0.01s)
=== RUN TestReopenRebuildsTheIndex
kv_test.go:70: reopened: 999 keys, log is 19817 bytes
--- PASS: TestReopenRebuildsTheIndex (0.02s)
=== RUN TestTornWriteIsDropped
kv_test.go:108: torn tail of 100 bytes removed; log back to 45 bytes
--- PASS: TestTornWriteIsDropped (0.02s)
=== RUN TestCorruptionIsDetected
--- PASS: TestCorruptionIsDetected (0.01s)
=== RUN TestCompactionReclaimsSpace
kv_test.go:150: log before compaction 230540 bytes, after 5750 bytes (file on disk 5750), 50 keys
--- PASS: TestCompactionReclaimsSpace (0.03s)
=== RUN TestConcurrentUse
--- PASS: TestConcurrentUse (0.03s)
=== RUN TestEveryCutPoint
kv_test.go:241: 795 cut points, from an empty file to the whole 794 byte log: every one recovered to the last complete record
--- PASS: TestEveryCutPoint (4.43s)
PASS
ok example.test/lab 5.899spackage main
import (
"fmt"
"log"
"os"
"path/filepath"
)
func main() {
dir, err := os.MkdirTemp("", "kv662")
if err != nil {
log.Fatal(err)
}
defer os.RemoveAll(dir)
path := filepath.Join(dir, "data.log")
s, err := Open(path, false)
if err != nil {
log.Fatal(err)
}
for _, kv := range [][2]string{{"language", "go"}, {"database", "none"}, {"language", "Go 1.25"}} {
if err := s.Put(kv[0], []byte(kv[1])); err != nil {
log.Fatal(err)
}
}
v, _ := s.Get("language")
fmt.Printf("language = %s, keys = %d, log = %d bytes\n", v, s.Len(), s.Size())
_ = s.Delete("database")
_, err = s.Get("database")
fmt.Printf("after delete: %v, keys = %d, log = %d bytes (a delete is a record too)\n", err, s.Len(), s.Size())
_ = s.Close()
s, _ = Open(path, false)
v, _ = s.Get("language")
fmt.Printf("after reopening: language = %s, keys = %d\n", v, s.Len())
_ = s.Compact()
fmt.Printf("after compaction: keys = %d, log = %d bytes\n", s.Len(), s.Size())
_ = s.Close()
}language = Go 1.25, keys = 2, log = 73 bytes
after delete: key not found, keys = 1, log = 93 bytes (a delete is a record too)
after reopening: language = Go 1.25, keys = 1
after compaction: keys = 1, log = 27 bytesThe demo program shows the file at each step. Three writes (the third overwrites language) left two keys and 73 bytes: the old value is still in the log, only the index forgot it. A delete shrank the key count to 1 and grew the log to 93 bytes, since the delete is a record. After reopening, the index was rebuilt from the file with the same contents. Compaction then cut the log to 27 bytes, one live record.
Every possible crash
One torn write test shows one crash. The way to trust recovery code is to try them all. TestEveryCutPoint writes a mix of 40 puts and deletes over seven keys, remembers the log length after each, then cuts a copy of the file at every byte offset from an empty file to the full log. For each cut it opens the copy, computes what the state should be (the effect of every operation whose record ended at or before the cut), and compares: same number of keys, same value for each. If recovery ever returned a half written value, lost a complete record, or failed to open, one of the cuts would catch it. The log line gives the count, and the test passes at every offset.
This is a general technique worth keeping: for any code that writes a file in steps, enumerate the interruption points and assert an invariant at each. It runs in milliseconds for a small log, it needs no special tooling, and it finds the bugs that otherwise appear once a year in production. It tests process crashes and torn writes at the file level. It does not simulate a power failure in which the operating system reorders or drops writes, which needs a fault injection file system or a tool like dm-log-writes, and which is why real databases pair checksums with fsync at the right points.
Compaction
An append only log grows forever. Compact writes the live records, found through the index, into a temporary file, syncs it, and renames it over the log, which is atomic on POSIX file systems, then switches the store to the new file and a new index. The test overwrites 100 keys twenty times, deletes 50 and compacts: the log went from 230,540 bytes to 5,750, and the 50 remaining keys read back with their latest values.
The version here holds the write lock for the whole copy, so the store is unavailable while it runs. A production design copies in the background from a snapshot of the index, then takes the lock briefly to catch up on records written meanwhile, and swaps. It also compacts in segments rather than one file, so work is proportional to what is reclaimed. Both are extensions of the same idea, and neither changes the recovery logic.
What durability costs
Writing to a file does not make the data safe. The operating system keeps it in memory and writes it to the disk later, so a power failure can lose writes that WriteAt returned for. File.Sync asks the system to put the data on stable storage, and it is slow. The benchmark runs the same put loop twice, and reads a key back for comparison:
package main
import (
"bytes"
"fmt"
"path/filepath"
"testing"
)
func BenchmarkPut(b *testing.B) {
for _, sync := range []bool{false, true} {
b.Run(fmt.Sprintf("fsync=%v", sync), func(b *testing.B) {
s, err := Open(filepath.Join(b.TempDir(), "bench.log"), sync)
if err != nil {
b.Fatal(err)
}
defer s.Close()
val := bytes.Repeat([]byte("v"), 100)
b.ResetTimer()
for i := 0; i < b.N; i++ {
_ = s.Put(fmt.Sprintf("key-%d", i%10000), val)
}
})
}
}
func BenchmarkGet(b *testing.B) {
s, err := Open(filepath.Join(b.TempDir(), "bench.log"), false)
if err != nil {
b.Fatal(err)
}
defer s.Close()
val := bytes.Repeat([]byte("v"), 100)
for i := 0; i < 10000; i++ {
_ = s.Put(fmt.Sprintf("key-%d", i), val)
}
b.ResetTimer()
for i := 0; i < b.N; i++ {
if _, err := s.Get(fmt.Sprintf("key-%d", i%10000)); err != nil {
b.Fatal(err)
}
}
}goos: darwin
goarch: arm64
pkg: example.test/lab
cpu: Apple M1 Max
BenchmarkPut/fsync=false-10 520944 1920 ns/op 146 B/op 2 allocs/op
BenchmarkPut/fsync=true-10 265 4740799 ns/op 299 B/op 2 allocs/op
BenchmarkGet-10 1922617 616.3 ns/op 127 B/op 2 allocs/op
PASS
ok example.test/lab 6.680sThe results:
| Time per put | |
|---|---|
no fsync per write | 1,968 ns |
fsync on every write | 4,926,875 ns |
A put without fsync took about 2 microseconds. With fsync it took about 4.9 milliseconds, 2,500 times longer: on a laptop, Sync waits for the drive to confirm the write, and on macOS Go uses the strongest flush it has. That one setting separates "fast and loses the last moments in a power cut" from "slow and loses nothing it acknowledged". Real systems offer a policy: sync every write, sync every N milliseconds, or sync only on request (Store.Sync). They also batch: many writes, one fsync, which is how databases reach tens of thousands of durable commits a second. A process crash, as opposed to a power failure, loses nothing in either mode, since the data is already in the operating system.
A Get took 608 nanoseconds: a map lookup, a read lock and one ReadAt served from the operating system's cache. It allocates the value buffer, which a real store would avoid with a caller supplied buffer or a block cache.
Reading the tests as a specification
The test names describe the contract of a storage engine, and they are worth copying for any store you write or adopt. A value written is the value read, including after an overwrite. A deleted key stays deleted across a restart. A reopened store has the same keys. A write cut short loses only itself. A damaged record is refused rather than returned. Compaction changes the size and nothing else. Concurrent use gives the same answers as sequential use. When you evaluate a library for your own service, look for these tests in its repository. A store that cannot show you how it behaves when the process is killed at the worst moment has not been tested against the thing a database is for.
What this design cannot do
- Keys must fit in memory. The index holds every key. Billions of keys need an index on disk, such as an LSM tree or a B-tree, which is what bbolt, Badger and Pebble provide.
- No range queries. A hash index finds a key and cannot say what comes after it. Ordered iteration needs a sorted structure.
- No transactions. Each operation is atomic, because a record is all there or not at all. Several changes together are not: a crash between two puts keeps one. A batch record, with one checksum around many operations, would fix it.
- One process. Two processes appending to one file would interleave. A lock file, or a server, is needed.
- Compaction pauses. As above.
- Recovery time grows with the log. Replaying a 50 GB log takes minutes. Bitcask solves this with hint files holding the index, written at compaction.
Extending it
If you keep going, the useful steps in order: a batch write that commits several operations under one checksum, so multi key updates are atomic; a hint file written at close and compaction so start-up does not replay; segment files with rotation at a size limit and background compaction; an on disk sorted index to lift the memory limit; and a write ahead log with a separate data file, the design of the next project. Each one moves the store a step toward the systems it imitates, and each is a reason those systems are larger than 200 lines.
Test the failure paths the way this article does. A database that has only been tested on its happy path has not been tested. Cut the file at every byte offset in a loop and check that Open always succeeds and never returns a key that was not fully written. That single test finds most bugs in recovery code. The standard library pieces used are documented in os.File.Sync, hash/crc32 and os.Rename, and the guarantees of an atomic rename on the file systems you deploy to are worth reading before you rely on them.
