Indexes
Each machine publishes an index of its own files. The index says what a day contains, proves that a reader holds the whole of it, and answers lookups without opening a log.
The index tree
A machine writes four kinds of index file, one per level of its directory tree.
| File | Holds | Rewritten when |
|---|---|---|
2026/09/15/index | Everything about that day: per log file counts and hashes, and the lookup tables | The day is sealed, or one of its log files is compacted |
2026/09/index | One entry per day: the day, and the hash of its day index | A day in that month changes |
2026/index | One entry per month: the month, and the hash of its month index | A month in that year changes |
index | One entry per year: the year, and the hash of its year index | A year changes |
Compacting one log file rewrites four small files: that day, its month, its year and the root. Every other day keeps the files it already had. A chain that ran through the days would rewrite every later link on each compaction, so the tree carries the hashes instead.
A machine writes the files leaf first: the day index, then the month, year and root, each one through a temporary name and a rename. A reader that holds a parent hash therefore also holds a child that existed.
Today has no index. A machine writes the day index when it seals the day.
The day index
The day index opens with one entry per log file in that day.
| Field | Meaning |
|---|---|
file | Log file number |
count | Number of records the index accounts for |
hash | Hash of the first count × 64 bytes of that log |
copied_into | Set when the file has been compacted: the day that received its live records |
| value marks | Records whose large value has been deleted as garbage |
After that come the lookup tables. Each one is sorted, so a reader answers a query with a binary search and a single read.
| Table | Sorted by | Answers |
|---|---|---|
| By node ID | node ID | Does this machine hold a record for node X that day, at which position, and at which version |
| By parent | parent ID, then child ID | Listing the children of a node |
| By reference target | target ID | Which nodes point at a given node, for hiding and cascades |
| Entry containers | node ID | Which entries were born that day and are still present |
| Tombstones | creator machine hash, then entry ID | Which of my entries other machines have deleted |
The entry container table carries the weight of deletion. An entry's name holds its birth day and its creator's machine hash, so any machine can name the one index that settles whether that entry still exists. Deleting covers that rule.
The tombstone table is sorted by creator machine hash so that a machine can find deletions of its own entries with one range read per index, without scanning every record another machine wrote.
A by-ID entry holds the node ID, the log file, the record index and the version, which is 32 bytes. A machine may instead store the whole 64-byte record and the location of its value, at about 88 bytes per entry. Readers then never open a sealed log: they take record headers from the index and values straight from the data files.
Verification
A reader checks an index at one of three levels, and picks the level the operation needs.
| Level | Needs | Proves |
|---|---|---|
| Integrity | The index file, with its own checksum, or its hash in the parent index | This is a complete index that the machine wrote |
| Presence | A directory listing | The logs and data files are at least as long as the index expects |
| Content | Hashing each log against the count and hash in the index | Every log matches the index exactly |
Content checks are cached outside the shared folder by path, size and modified time, so a reader hashes each version of a file at most once.
Verifying the tree above a day proves something different: that the reader holds every day the machine has sealed. A day listed in a month index with no directory on disk is a day still on its way.
What each operation needs
| Operation | Needs |
|---|---|
| Deciding that an entry is gone | Integrity of the day index for that entry's birth day |
| Looking up a node, listing children, finding referrers | Integrity of the index being searched |
| Reading a record from a log | A check on that read: the record at the listed position must hash to the node ID the index lists, with the listed version |
| Reading a value | The bytes must hash to the record's hash field |
| Compaction | The machine's own files, plus index integrity for other machines it consults |
Decisions that rest on something being absent need the index alone. A machine writes a day index only when that day's logs are complete, so the index is a full account of the day. An older version of the index still lists everything a newer version lists, apart from records the machine has deliberately removed.
When a per-read check fails, the reader holds a different version of that log than the index describes, which happens while a compaction is on its way. The reader treats that record as pending and tries again when the file changes. Nothing is decided from the mismatch.
Compacted files and copied_into
Compaction copies a log file's live records into today's log, waits for that day to be sealed and indexed, and then rewrites the old file. The day index entry for the rewritten file carries copied_into, naming the day that received the copies.
A reader applies one rule: a rewritten log file takes effect once the reader holds a verified index for its copied_into day. Until then the reader keeps answering from what it already has.
Records move more than once over time, so the pointers chain: a file compacted into day C1 has an index entry naming C1, and when C1 is later compacted its entry names C2. A rewritten file takes effect once its copied_into day takes effect, and the chain ends at a day that exists, because each rewrite waited for the next day to be sealed first.
Entry container records stay in the day they were born, so a compaction never moves the record that proves an entry exists. That keeps the deletion rules pinned to one index.
Memory and lookups
A server holds a small amount in memory and reads the rest from index files when it needs it.
| In memory | Why |
|---|---|
| Today's records from every machine | No day index covers them yet |
| Verification state per machine | Which days verify, and the hashes already checked |
| Dead entries with tombstones outstanding | Suppressing writes, and tracking when a tombstone can go |
| Subscriptions and a cache of recently used nodes | Live updates and fast reads |
| Own file accounting | Live counts per log file, to choose what to compact |
Memory then follows today's activity and the working set, and stays flat as history grows.
A lookup for node X runs newest first: today's records in memory, then day indexes backwards in time. The first hit is that machine's latest record for X, because a machine's own later writes carry higher versions and compaction copies records unchanged. The winner across the database is then the highest version and hash among the machines. Reading covers the merge.
Searching every day of every machine costs too much on its own, so two things cut it down:
- A Bloom filter in each day index. A few bytes per record, and a lookup skips almost every day that lacks the node.
- Merged tables higher up. A month index also carries a by-ID table holding that machine's latest record per node for the month, and a year index does the same for the year. A lookup touches a handful of days, a handful of months, and a few years per machine.
The local cache
A server keeps its own cache outside the shared folder, keyed by the index hashes it has verified: the merged node index, the per-file hash state, and its own file accounting.
At startup it loads the cache and compares each machine's root index with what the cache recorded. It re-reads only the days whose hash changed, plus every machine's current day. Startup then follows what changed since the last run.
Losing the cache costs time and nothing else. A server rebuilds it by reading the index files and today's logs.