Writing

One writer per directory

A machine appends to the log file of its own current day, inside its own directory. It never writes into another machine's directory, and it never goes back to an earlier day. A change to data another machine created is a new record in the writer's own files, carrying a higher version.

That keeps every file under a single writer, which is what lets a shared folder carry the database without ever having to resolve a conflict between two copies of a file.

Creating an entry

A collection entry is created by one machine, and that machine writes the entry's container record: 64 bytes with version 0, no value. No other machine writes that record, whatever it later does to the entry's fields.

The server assigns the entry's name from the position it is about to write to.

name (16 bytes) = day (u32) | file (u16) | index (u16) | H(user/machine)[0:8]

The name is unique without any random bits, because only that machine writes that position. It also says two useful things to every reader: which machine is the creator, and which day index answers the question of whether the entry still exists.

Clients never choose names. A client asks for an entry to be created and gets the name back in the reply. A client that goes offline and replays a queued create gets a new position, so it creates a second entry. A deleted entry can never be recreated at its old name, and the records other machines wrote under it stay hidden for good.

Entries are always containers. A collection of plain values stores each value one level down, at <entry>/value, so the entry's own record is written once and then only ever removed.

Writing a value

A value write carries the version one above the highest the machine knows for that node. The first write to a node is version 1.

1. Work out the new version from the merged view.
2. Append the value to a data file: a value of 16 bytes or fewer goes into the record itself, a value under 1 MiB is concatenated onto the current small data file, and anything larger gets a data file of its own.
3. Append the 64-byte record to the log.

The value goes first. A complete record therefore always has its value already on disk, and a crash between the two leaves a value that nothing points at, which the next startup removes.

A write to a field under an entry is an ordinary record like any other. The entry's own record stays untouched, which is why a machine editing another machine's entry never needs to write anything the creator owns.

References

A reference is a record with length set to 0xFFFF…FF and the target's node ID in the hash field. The server writes one only when it can see the target as present and live on its own machine. A reference to a node that has already died is refused.

The schema says which references cascade. A cascading reference removes the entry that holds it when its target dies, and it is written once, when the entry is created. A reference the application can change later reads as empty once its target dies, and takes nothing with it.

Where a machine may write

A reader checks these rules against the directory a record came from and ignores anything that breaks them. A record alice's laptop writes under users/bob/ counts for nothing, and neither does a container record found in a directory that does not match its name.

The local server applies the same rules to its own clients and answers 403.

Conditional writes

A node's ETag is its version, so a client that has read a value can write the next one conditionally.

GET /shared/channels/<id>/topic
200  ETag: "7"

PUT /shared/channels/<id>/topic
If-Match: "7"
200  ETag: "8"        the stored version was 7, so this write becomes 8

PUT /shared/channels/<id>/topic
If-Match: "7"
412  ETag: "9"        something else was written first; re-read and try again

A 412 means the version the client based its write on is no longer the current one on this machine. The reply carries the current version, so the client can read the value again and decide what to do.

A write without If-Match takes the highest version the machine knows and adds one. That is the right call for a value the application is setting outright, and it removes a round trip.

POST to a collection creates an entry. DELETE on an entry writes a tombstone, which is accepted unconditionally, because a deletion beats every other record for that node.

Two machines writing at once

Two machines that both hold version 7 and both write will both produce version 8. The hash decides which one shows, the same way on every machine.

The machine whose write lost sees a record with its own version number and a winning hash. It writes a conflict entry into its own user's area:

users/<user>/conflicts/<H(node id | version)>
    node    reference to the node that was written
    version the version both machines used
    value   the value this machine wrote and lost

The name is worked out from the node and the version, so a restart, or a second machine belonging to the same user, writes the same entry instead of a duplicate. The reference to the node means the conflict entry disappears when the node does. An application decides what to show: a note, a merge screen, or nothing at all.

Resolving a conflict is an ordinary write of the next version, followed by a delete of the conflict entry.

Writing from a stale view

A machine writes from what it holds. Records from another machine may still be in transit, so the version it picks can be one another machine has already used, or lower than one already written elsewhere.

Both cases settle by the same comparison as a genuine simultaneous write: equal versions go to the hash, and a lower version loses. A machine that has been offline for a week and comes back mid-sync is in the same position as a machine writing at the same instant as another, and needs no special handling.

Writes the server refuses

The day boundary

Days are UTC, and a machine writes to max(today, the last day it wrote), so a clock that moves backwards never reopens a day that has been sealed.

On its first write of a new day, and at startup if the last day it wrote is earlier, a machine seals the day it has left behind:

1. finish the day's log and data files;
2. write the day index, which lists every record in the day and the tables that make it searchable;
3. update the month, year and root indexes.

Today's files carry no index and are never compacted. A sealed day can be compacted, and its index is what other machines read to answer questions about what that day holds. See Indexes.

After a crash

A machine may stop in the middle of an append. At startup it repairs its own current day:

1. truncate the log file to a whole number of 64-byte records;
2. recompute the expected length of each data file by walking the log;
3. truncate any data file that runs past that length.

Because values are written before records, a value that survives with no record is simply dropped, and a record that survives always has its value. Everything already synced elsewhere is a prefix of the repaired file, so other machines see nothing change.

Related