Deleting

What can be deleted

Deletion applies to collection entries. An entry is a node with a random-position name inside a collection, and it carries a container record written once by the machine that created it. That machine is the entry's creator.

Struct fields and union options keep fixed names derived from the schema. Those names never change, so a deleted field could never be written again. A field is cleared by writing an empty value, which is an ordinary versioned write. See Data model for the shapes that produce entries.

Deleting an entry deletes everything below it. Field records, nested entries, and references inside the entry all go with it.

The tombstone

A machine deletes an entry by writing a tombstone: a record for the entry's node with version set to all ones, length zero and hash zero. All ones is the highest version, so a tombstone beats every other record for that node in the merge.

A tombstone takes effect the moment it arrives. Readers hide the entry, hide every record beneath it, and hide any reference pointing at it. Writes to fields under a dead entry are refused by the local server.

Any machine may delete an entry in the shared area. In users/<u>, only that user's machines may write, so only they may delete.

A tombstone is 64 bytes and lives in the deleting machine's own log. It stays there until the entry is gone, which is the state the rest of this page describes.

The creator publishes the deletion

Only the creator ever writes an entry's container record. That single fact drives the whole protocol: the record exists in one machine's files and nowhere else, so that machine decides when it stops existing.

The creator watches for tombstones on the entries it created. An entry's name carries the creator's machine hash, so every tombstone can be filed under the machine that owns its target. Each day index carries a table of that day's tombstones sorted by creator hash, and the month and year indexes carry merged versions of the same table. See Indexes for the tables.

• At startup, the creator looks up its own hash in each other machine's root, year and month tables, and reads only the days where its hash appears. It then scans today's logs.
• While running, it checks each incoming tombstone record for its own hash.

The creator stores nothing locally to track this. Every tombstone still waiting for the creator is on disk in the deleter's files, because a deleter keeps its tombstone until the creator has acted. A restart finds them all again.

When the creator sees a tombstone for one of its entries, the entry is dead in its view. At the next compaction of the log file holding that entry's container record, the creator leaves the record out. The rewritten day index no longer lists it.

Gone

An entry is gone when a reader holds a verified day index for the entry's birth day and that index does not list the entry's container record.

Verification uses the index's own checksum and its hash in the month index. The logs need not match: the index states what the day contains, and the creator writes it only after the day's logs are complete.

Container records stay in their birth log file, compacted to the front of it when that file is rewritten. Everything else moves forward to today's log. That rule keeps the answer local: one day index settles the question, whatever else has or has not arrived.

An entry is also gone when any ancestor entry is gone. A nested entry whose parent entry has been removed can never become visible again, so its own records are garbage whether or not anybody tombstoned it.

What each machine does once an entry is gone

A witness is any machine that wrote records under the entry without creating or deleting it. Witnesses need no tombstone of their own. They check the creator's day index and clean up.

Cascading references

A reference is a record whose length is all ones and whose hash holds the target node's ID. A reference to a gone target is hidden, and so is the entry holding it.

The creator of the referring entry removes its container record, using the same step as a direct deletion. Machines find the affected entries through the by-target tables in the day indexes: when a target is verified gone, one lookup lists every record that refers to it, and their entries' birth days are scheduled for compaction.

A chain settles one hop at a time. A references B, B references C, C is deleted: C's creator removes C, then B's creator removes B, then A's creator removes A. Each hop waits for a compaction of a sealed birth file, so a chain of three takes a few days on machines that are online.

Timeline

Carol deletes entry N. Alice's laptop created N. Walter wrote a field under it.

1. Carol writes a tombstone for N in today's log. Every reader that receives it hides N and everything under it.
2. Alice's laptop finds the tombstone, through carol's day index or today's logs. N is dead in its view.
3. Alice's laptop compacts N's birth log file and leaves the container record out. It writes the new day index, then the month, year and root indexes.
4. Carol reads alice's day index, sees N gone, and drops her tombstone at her next compaction.
5. Walter reads the same index, sees N gone, and drops his field records at his next compaction.

Entries born today wait for the day to be sealed. Today's files are append-only and carry no index, so the earliest a container record can be removed is the following day. The tombstone hides the entry in the meantime.

Arrival order

Files arrive in any order. The protocol holds because every step that removes something rests on a record that is present, or on an index that verifies.

A machine that has been away can see N reappear for a while: it may hold carol's newer files, where the tombstone is gone, and alice's older files, where the container record is still listed. Nothing it does in that window is permanent. Edits under N become records with no visible ancestor. References to N stay hidden. When alice's new index arrives, N disappears for good.

Machines that stop

A creator that goes silent never removes its container records. Its entries never become gone, so tombstones for them stay in the deleters' logs, and hidden records under them stay in the witnesses' logs. Each is 64 bytes per deletion. The entry stays hidden everywhere, because the tombstone stays too.

That result is correct. The creator's container record is still in its files, and it needs suppressing for as long as it exists.

A creator that stops mid-day never seals that day, so entries born that day are never verifiable. A creator that restarts seals the previous day first, then continues.

Related