1 · Data structure
A graph with edges both ways
Memories and sources form a directed acyclic graph (DAG), stored as adjacency lists. Each node keeps its edges up (the parents in each leg) and its edges down (the children that depend on it). A recall walks down; reading where a memory came from walks up.
A child link also stores which leg of the child it belongs to, so when a parent dies, exactly one counter changes.
Why there are no cycles: ids only go up, and a parent must exist before a child can name it. So every parent has a smaller id than its child, and plain id order is already a topological order. The code never has to compute one.
type node struct {
kind record.Type
dead bool
legs []leg // edges up
aliveLegs uint32 // 0 means the memory is dead
children []childRef // edges down
}
type leg struct {
parents []ID
deadParents uint32 // the leg is alive while this is 0
}
// "memory child depends on me through its leg number leg"
type childRef struct {
child ID
leg uint32
}
internal/ledger/state.go, lines 18–42 →
2 · Algorithm
Counters instead of rescans
A memory lives while any leg is alive (OR), and a leg lives only while all its parents are alive (AND). The slow way checks every parent of every child again after each death.
Instead, every leg counts its dead parents and every memory counts its alive legs. A parent's death bumps one counter per child, which is O(1) per edge. This is the in-degree trick from Kahn's algorithm: act when a count reaches zero.
In the example: recall B, and M1's leg [B] goes from 0 to 1 dead parents, so M1's alive legs drop from 2 to 1 and it survives. Recall A, and the count drops to 0, so M1 dies.
func (s *state) die(id ID, removed []ID) []ID {
n := s.node(id)
n.dead = true
if n.kind == record.TypeMemory {
removed = append(removed, id)
}
for _, ref := range n.children {
c := s.node(ref.child)
l := &c.legs[ref.leg]
l.deadParents++
if l.deadParents == 1 { // this leg just died
c.aliveLegs--
}
}
return removed
}
internal/ledger/state.go, lines 226–241 →
3 · Algorithm
BFS with a queue, never recursion
A recall is a breadth-first search down the child links. In Fair mode a child joins the queue only when its last leg dies, and since a node can only die once, no visited set is needed.
Strict mode removes every descendant, so it must remember what it has visited (diamonds in the graph) and walk through nodes that are already dead: an earlier recall may have killed a node while its child survived on another leg.
Why a queue and not recursion? Recursion keeps one waiting call per level of depth. A queue has no depth limit and shows exactly what is left to do. The work is proportional to the nodes the recall reaches, never the whole database. Recalling a source behind 10,000 memories takes about 5 ms (numbers).
queue := []ID{target}
var visited map[ID]bool
if m == Strict {
visited = map[ID]bool{target: true}
}
for len(queue) > 0 {
x := queue[0]
queue = queue[1:]
for _, ref := range s.node(x).children {
c := s.node(ref.child)
switch {
case m == Fair:
if !c.dead && c.aliveLegs == 0 {
removed = s.die(ref.child, removed)
queue = append(queue, ref.child)
}
case !visited[ref.child]:
visited[ref.child] = true
if !c.dead {
removed = s.die(ref.child, removed)
}
queue = append(queue, ref.child)
}
}
}
internal/ledger/state.go, lines 117–164 →
4 · Algorithm
One pass in id order (DP on a DAG)
If the machine crashes halfway through erasing text from disk, the next open must find everything that should have been erased: every dead node at or below any erased source.
That could be one BFS per erased source. But parents always have smaller ids, so by the time the loop reaches a node, the answer for every parent is already final. One loop in id order solves it: dynamic programming over a DAG in topological order, O(nodes + edges), with no queue at all.
// below[id]: id is an erase target or descends from one
below := make([]bool, len(s.nodes)+1)
for _, t := range s.eraseTargets {
below[t] = true
}
for i := range s.nodes {
id, n := ID(i+1), &s.nodes[i]
for _, l := range n.legs {
for _, p := range l.parents {
below[id] = below[id] || below[p]
}
}
if below[id] && n.dead && !n.redacted {
ids = append(ids, id)
}
}
internal/ledger/state.go, lines 277–301 →
5 · Data structure
Arrays, not hash maps
Ids are dense: 1, 2, 3, and so on with no gaps. So the graph, the table that says where each record sits on disk, and the search index's lookup are all plain slices indexed by id-1.
A slice lookup is one multiplication and one memory read: no hashing, no buckets, less memory per entry, and neighbouring ids sit next to each other in memory, which the CPU cache likes. The rule: when keys are small dense integers, use an array.
// the graph
func (s *state) node(id ID) *node { return &s.nodes[id-1] }
// where each record lives on disk
offsets []pos // offsets[id-1] = where record id lives
type pos struct {
seg uint32 // segment file number
off uint32 // byte offset inside it
}
internal/logfile/logfile.go, line 138 →
6 · Data structure
A hand-written min-heap for top-k
Search returns the k memories closest in meaning to a question. To keep the k highest scores, CheeseDB uses a min-heap: the worst of the current best k sits at the root, so a new result only has to beat that one to get in. That's O(n log k) for n vectors.
It is written out by hand, sift up and sift down, in about 30 lines. Ties are broken by id, so the same search always gives the same answer.
// topK holds the best k hits seen so far, as a min-heap:
// the worst of them sits at the top.
type topK []Hit
func (t topK) offer(h Hit, k int) topK {
if len(t) < k {
t = append(t, h)
// sift up: move the new hit up to its place
...
return t
}
if !better(h, t[0]) {
return t // not better than the worst: ignore
}
t[0] = h
// sift down: move the new hit down to its place
...
}
internal/vecindex/vecindex.go, lines 325–361 →
7 · Data structure
Swap-remove: delete in O(1)
Vectors sit packed together in one big block so a search can run straight through them. Deleting one from the middle would mean shifting everything after it, which is O(n).
Instead, the last row moves into the hole, the block shrinks by one, and the lookup array is fixed for the row that moved. Order doesn't matter for a full scan, so this is safe. The freed bytes are also wiped, because a recalled memory's vector must really be gone.
r := x.rowOf(target)
last := len(x.target) - 1
if r != last {
copy(x.codes[r*x.dims:(r+1)*x.dims], x.codes[last*x.dims:])
x.target[r] = x.target[last]
x.row[x.target[r]-1] = int32(r) // fix the moved row's lookup
...
}
clear(x.codes[last*x.dims:]) // wipe, don't just forget
x.codes = x.codes[:last*x.dims]
x.target = x.target[:last]
x.row[target-1] = -1
internal/vecindex/vecindex.go, lines 193–218 →
8 · Algorithm
Skipping work with a bound
To save memory, vectors are kept in RAM at one byte per number instead of four (scalar quantization), so they're four times smaller but slightly rounded. The precise vectors stay on disk.
Each row also remembers the most its rounded score can be off by (its slack, from the Cauchy–Schwarz inequality). A search scores every row cheaply, sets a bar from the k-th best guaranteed score, and reads from disk only the rows that could still clear the bar in the best case. The answer is the same as checking every precise vector.
It's the same idea as pruning in backtracking or branch and bound: skip a branch once you can prove it can't win.
// round 1: quick score from the 1-byte copy
est[r] = x.scale[r] * dot8(q, x.codes[r*x.dims:(r+1)*x.dims])
sure = sure.offer(Hit{..., Score: est[r] - x.slack[r]}, k)
// the k-th best score that is certain
bar = all[k-1].Score
// round 2: precise score only where it can matter
for r, e := range est {
if e+x.slack[r] < bar {
continue // cannot make the top k, even at best
}
v, err := exact(x.rec[r]) // read the precise vector
best = best.offer(Hit{..., Score: dot(q, v)}, k)
}
internal/vecindex/vecindex.go, lines 235–280 →
9 · Algorithm
Binary search over a sorted table
Records live in numbered segment files. The table of record positions is in id order, so it is also sorted by segment number. To find the first record of segment n, a binary search finds the first entry whose segment is n: a lower bound, in O(log n).
Go's standard library does the search. You give it the comparison.
// Offsets are in id order and grouped by segment,
// so a binary search finds segment n's first record.
func (l *Log) firstID(n int) uint64 {
i, _ := slices.BinarySearchFunc(l.offsets, uint32(n),
func(p pos, seg uint32) int {
return int(p.seg) - int(seg)
})
return uint64(i) + 1
}
internal/logfile/redact.go, lines 195–199 →
10 · Concurrency
A queue between goroutines
A write is safe only after fsync, when the disk confirms the bytes are stored. That takes milliseconds. If ten callers each did their own fsync, they would wait in line ten times.
Instead, callers send their writes down a Go channel to one committer goroutine, a producer–consumer queue. The committer takes everything already waiting, writes it all at once, does one fsync, then answers every caller. This is called group commit. There is no timer: under light load a batch is one write and adds no delay.
batch := []*request{req}
size := req.size
gather:
for {
select {
case r := <-l.reqs: // another write is already waiting
if size+r.size > MaxBatchBytes {
carry = r // too big: it starts the next batch
break gather
}
batch = append(batch, r)
size += r.size
default: // nothing else waiting: go
break gather
}
}
l.commit(batch, size) // one write, one fsync, answer all
internal/logfile/logfile.go, lines 555–596 →
Also in the code
- A hash chain. Each record stores the SHA-256 hash of the record before it, like a linked list where every link is a fingerprint. Change one old record and every hash after it stops matching.
- Checksums. CRC-32C on every record tells a half-written record after a power cut (a torn write) apart from a whole one.
- Copy, then rename. To rewrite a file safely, write a new copy, flush it, then swap it in with one atomic rename. A crash leaves either the old file or the new one, never half of each.
- An append-only log. Nothing is updated in place. On open, the engine replays the log to rebuild the graph in memory.
The full design, byte layout included, is in ARCHITECTURE.md.