Reading

The winning record

Several machines can hold a record for the same node. Each one wrote its own version into its own log files. A reader keeps all of them and picks one winner.

Two records compare on version first, read as an unsigned number, then on the 16 bytes of hash. The highest pair wins. The comparison is the same on every machine, so every reader reaches the same answer from the same set of records.

Two machines that write from the same starting version produce the same number, and the hash settles which one shows. The machine that loses records a conflict so an application can show the lost value. See Writing.

Finding it

A record lives at a known position: a machine, a day, a log file and an index within that file. The day index lists every record the day holds, sorted by node ID, so a lookup is a binary search.

1. For each machine, search its own records newest first: today's records, which the reader holds in memory, then each day index backwards in time.
2. Take the first record found for the node. That is the machine's latest, because a machine's own later writes always carry a higher version, and compaction copies are byte-identical to their originals.
3. Compare the machines' latest records by (version, hash), and take the highest.

Searching every day of every machine would be slow. Each day index carries a Bloom filter, so a lookup skips almost every day that does not hold the node. Month and year indexes carry merged tables, which cut the search to the current month's days, then months, then years.

Which nodes are visible

Structs and collections come from the schema, so they need no records. An entry exists while its container record is present, and that record is written by one machine: the creator named in the entry's own name.

A node is visible when both of these hold:

• every entry above it in the path has a container record, and none of them has a winning tombstone;
• every reference inside it points at a node that is present and live.

A reference whose target is unknown is hidden, because the target may be a record that has not arrived yet. A reference whose target is dead is hidden as well. Hiding a reference hides the entry that contains it, which is how a deletion travels outwards to the things that depend on it.

All of this is worked out when the data is read. Nothing is written to record it, and a node hidden this way comes back into view if the missing records arrive. Records are only ever removed on the strength of something present, or of an absence confirmed by a verified index. See Deleting.

Values

A value of 16 bytes or fewer sits in the record's hash field, so reading it costs nothing. A longer value sits in a data file, and the record holds the hash of the value and its length.

Small values are concatenated into one data file per log file. A value of 1 MiB or more gets a data file of its own. The day index gives the file and the offset, and the position can also be recomputed by walking the log.

The reader checks every value it loads against the record's hash. A value that does not match is treated as absent.

The last row matters for large values, which a machine deletes as soon as a newer version for that node sits in a sealed, verified index. Marking the deletion in the day index tells a reader to stop waiting for a file that will never arrive.

Two views of each machine

A reader keeps two views of every other machine at once.

A day index verifies when its own checksum holds, its log files are at least as long as it says, and their contents hash to the values it lists. Hashes are cached by path, size and modification time, so each version of a file is hashed once.

A rewritten log file names the day its moved records went to. That rewrite takes effect for a reader once the reader holds a verified index for the copy day, which keeps a record from disappearing from view while its copy is still in transit. See Compaction.

Listing children and following references

Each day index carries two more sorted tables. One lists records by parent node, and one lists references by target node.

Listing a node's children means reading the by-parent ranges from every machine and every day that holds them, collecting the child IDs, and then resolving each child's winner in the usual way. Duplicates collapse, because the ID identifies the node.

The by-target table answers the reverse question: which references point at this node. A reader uses it to hide the entries that depend on a node when that node dies, and a machine uses it to find the entries it needs to remove.

HTTP and WebSocket

An application talks to the server on its own machine. Paths follow the tree.

GET  /shared/channels/<id>/topic            200, body = the value, ETag: "7"
GET  /shared/channels/<id>?depth=2          200, JSON subtree with a version per node
GET  /users/alice/messages/<id>             readable by anyone, writable by alice's machines
PUT  /shared/channels/<id>/topic            If-Match: "7"  -> writes version 8
POST /shared/channels                       creates an entry, returns its name
DELETE /shared/channels/<id>                writes a tombstone

A node's ETag is its version, which makes a conditional write a plain If-Match. A dead node carries the highest possible version, so every conditional write to it fails.

A WebSocket subscribes to one path with a depth limit: 0 for the node itself, 1 for its children, and so on. The server walks a changed node's ancestors up to the deepest subscribed level and notifies the matching subscriptions. A subscription runs in one of two modes: a ping that says the subtree changed and leaves the client to fetch it, or a stream of the changed records.

While a machine is settling

Files arrive in any order, so a machine's data can be incomplete in ways the reader can see: a day listed in the index tree with no folder, an index whose logs have not arrived, or a rewritten log file whose copy day is still missing.

While that lasts, the reader:

• serves the live view, and can flag it as syncing;
• makes no decision that rests on a record being absent, which means dropping no tombstones and removing none of its own records;
• keeps answering from its local cache of the old index contents until the copies verify.

Ordinary writes carry on. A write made from an incomplete view carries a version that a newer record can beat, which gives the same result as two machines writing at once.

Related