# The replica protocol
What a replica must do to be kept in sync by this engine, whatever language it
is written in and whatever database it keeps its rows in. The engine's own
replica (`src/replica.rs`, on SQLite) is one implementation of it; this
document is the contract that one follows, and any other must.
The messages are in
[`proto/sync.proto`](https://github.com/rsansores/magic_sync/blob/main/magic_sync/proto/sync.proto).
Generate code for your language from it; the engine's own types are generated
from it too, and a test fails while they differ.
The words **must**, **must not** and **should** mean what they mean in RFCs.
Sections 1 to 10 are what a replica does, and the whole of what an
implementation needs. What the server does with what a replica sends is in
[Appendix A](#appendix-a-what-the-server-does-with-it): it explains the
rules, and no replica has to implement any of it.
---
## 1. The parties
- The **server** owns the truth. It decides which rows each replica should
hold, sends the difference, and records what each replica holds.
- A **replica** holds a copy of some of the server's tables, and may write
tables of its own that go up to the server. It is identified by a UUID the
server knows.
- The **transport** carries messages between them. The engine does not depend
on which one, but it requires what section 2 lists.
A replica never decides what it should hold. It applies what it is sent,
reports what it could not apply, and reports what it holds. It follows one
server installation: two that send it messages each take the other's for a
new epoch, and provision it again and again.
---
## 2. What the transport must provide
The server sends one kind of message, `ToReplica`, which carries a `Down`, an
`EndSnapshot` or a `Filed`. A replica sends one kind, `Up`, on one or more
lanes (section 7). A transport carries bytes and nothing else: it never needs
to know what is inside. Whatever it is — a broker, HTTP over a queue of your
own, files on a USB stick — it **must** provide, in both directions:
1. **Nothing it took is lost.** Once the transport accepted a message, it
delivers it: while the other end is unreachable, and across a restart of
either end or of the transport itself. It stores, then forwards.
2. **In order.** A replica's messages are delivered in the order the server
sent them, and a replica's `Up`s on one lane reach the server in the order
it sent them.
3. **One at a time, down.** The next message to a replica is not delivered
until the replica acknowledged the previous one (5.1).
4. **At least once.** A message that was not acknowledged is delivered
again. Each side therefore treats every message as one it may have seen
before (4.1, 7).
5. **An acknowledgement names its message.** It releases that message and no
other: one that arrives twice, or late, never releases a message the
replica has not applied.
With NATS JetStream, that is a stream on file storage, and per replica a
durable pull consumer with explicit acknowledgements and
`max_ack_pending = 1`; up, a stream the server consumes per lane in order.
A message the transport carries has a size limit of its own; the server keeps
every message within it, and a replica must keep every `Up` within it
(section 7).
A **transport acknowledgement** (section 5.1) is what makes the transport
deliver the next message. It is not the same as telling the server what was
applied (section 5.2).
A transport that loses a message anyway costs time, not data: the next message
names the one before it, so the replica knows it missed one and is provisioned
again (4.1); a replica that leaves messages unconfirmed while nothing newer goes
to it is provisioned again (A.1), an upload the server did not answer is sent
again (section 7), and a digest that disagrees provisions the replica again
(section 8). That is the engine's safety net, not a licence: until it acts, the
replica holds less than it should.
---
## 3. Rows and keys
Each table travels in **its own encoding**, agreed between the server and the
replica for that table: either a protobuf message with one field per column,
or a JSON object of its columns (the column names as keys). The engine's
messages carry those rows as opaque bytes, so this protocol never changes when
a table does.
A row's **key** is its primary key, as text, in key order:
- a UUID part: lowercase, hyphenated (`0196…-…`);
- an integer part: decimal;
- the parts joined by `|` where a single text is needed (`a1b2…|3`).
This is the one form keys are compared in, and every key a side writes into
a message **must** be in it. A side reading a key parses each part as its
column types it and writes it back in this form before using it (a UUID that
came uppercase or without hyphens is the same key); a key that does not
parse is malformed.
A table that travels as **JSON** is a JSON object with one member per column,
named as the column, each value as the column's type writes it in JSON —
except a 64-bit integer, which is its decimal text (`"9007199254740993"`): a
JSON number would be rounded by a reader that holds numbers as doubles. A
decimal is its text, a UUID its canonical form, an instant RFC 3339.
---
## 4. Applying what the server sends
### 4.0 The protocol version
Every `ToReplica` and every `Up` carries `protocol`, the version of this
document its sender speaks (now `1`).
- A replica **must** set `protocol` on every `Up` it sends.
- A replica that receives a `ToReplica` of a **later** protocol than its own
**must not** act on it and **must not** acknowledge it to the transport: it
waits to be updated, and the message is delivered again then. Every message
behind it waits too, which is right, because they speak the same version.
- The server does the same with an `Up` of a later protocol than its own,
and drops an `Up` of protocol 0 as malformed.
A message that is **malformed** — bytes that do not decode as a `ToReplica`; one
of protocol 0 (unset), or of the replica's own protocol or earlier whose body it
does not know, or that has none; numbers no server sends (4.1) — carries nothing
a replica can act on: it **must** apply none of it, **should** log it, and
**must** acknowledge it, so it does not hold back the queue. The digests
(section 8) find whatever it carried, if it mattered.
What a server sends, field by field — anything else is a number no server
sends, and the corpus of malformed messages (`tests/golden/malformed.txt`)
has a case of each:
- `protocol`: 1 to the replica's own. Cases: `no_protocol`.
- `sequence`: 1 to 2^63 − 1. Cases: `sequence_zero`, `sequence_too_large`.
- `nonce`: 1 to 2^63 − 1. Cases: `no_nonce`, `nonce_too_large`.
- `previous`: below `sequence`. Cases: `follows_itself`, `follows_a_later_one`.
- `previous_nonce`: 0 with `previous` 0, and otherwise 1 to 2^63 − 1. Cases:
`follows_without_its_nonce`, `follows_nothing_with_a_nonce`,
`follows_a_nonce_too_large`.
- `epoch`: a UUID. Cases: `epoch_no_uuid`.
- `snapshot_id`: a UUID; empty on a message of no snapshot. Cases:
`snapshot_no_uuid`, `ends_a_snapshot_of_no_id`.
- `mac`: 16 bytes. Cases: `no_mac`, `mac_too_short`, `mac_too_long`.
- `keys`: one per upsert. Cases: `keys_not_one_per_row`.
- `tables`, `deletes`, `upserts`, `uploads`: no more rows — upserts and deletes
together — and no more tables, or uploads, than the replica takes in a
message: the server's limits, or more (500 each by default). Cases:
`more_rows_than_a_message_carries`, `more_tables_than_a_message_carries`,
`ends_more_tables_than_a_message_carries`,
`files_more_uploads_than_a_message_carries`.
A row's own fields are the row's to answer for, not the message's: a key
that does not parse, a row that does not decode, a table the replica does
not hold — the row is rejected, or its delete ignored (4.1), and the rest
applied (`a_delete_of_a_key_that_does_not_parse`, `a_row_beside_another_key`).
What changes the protocol's number: a new kind of body, or a field whose
meaning changes. What does not: a new field. A side **must** ignore fields it
does not know, so a message with a field added means to a side that predates
it what it meant before.
### 4.1 `Down`: rows to hold, rows to let go
A replica **must** apply a `Down` in one transaction: either all of it, or
none of it.
**The number comes first.** Every `Down` carries a `sequence` and an
`epoch`, a `nonce` of its own — a number the server draws at random for it —
and `previous` and `previous_nonce`: the sequence and nonce of the message
the server sent this replica before this one, in this epoch — both 0 on a
message that begins a snapshot (4.2), which follows nothing. It carries a
`mac` too, the server's seal, which the replica keeps as it came and gives
back (5.2). The replica keeps the `(epoch, sequence, nonce, mac)` of the last
message it applied, and checks, in order:
- `sequence` 0 or above 2^63 − 1, an `epoch` that is not a UUID, a
`previous` at or past `sequence`, a `nonce` 0 or above 2^63 − 1, a
`mac` of other than 16 bytes, a `previous_nonce` above 2^63 − 1, a
`previous` of 0 with a `previous_nonce`, or another `previous` without
one, or a `previous` of 0 on a message that begins no snapshot: no server
numbers a message so; nor sends a table whose `keys` are not one per
upsert. The message is malformed (4.0).
- the same `epoch` and a `sequence` **at or below** the last one: the message
changes nothing. The replica **must not** apply it, and **must**
acknowledge it to the transport: it is a redelivery, or the server's
database was restored from an older copy and is numbering again — its
nonce then is another, but the replica need not tell: either way it
**should** tell the server the last message it applied again (5.2), and a
restored server finds out from that.
- `previous` 0: the message begins a snapshot, and the replica applies it,
whatever it applied before — of this epoch, or of another, which is a
server installed again or restored: it keeps that epoch's numbers from
now on — and whatever gap it had. A new epoch always begins with a
snapshot.
- otherwise the message **must** follow the last one applied: `previous`
and `previous_nonce` are its sequence and nonce, of the same epoch. If
not, the replica missed one — lost on the way, or the replica's own
database restored from an older copy, or the server's numbering again —
and has a **gap**. Once it has a gap, it applies **nothing** but a message
that begins a snapshot: not even one that follows the last applied. It
**must not** apply the message, **must** acknowledge it to the transport,
and keeps the sequence of the newest message it could not follow, which
it says to the server (5.2) until a snapshot begins. The server answers
with one.
- a message that follows the last applied and names a snapshot other than
the one in progress — or none, while one is in progress, or one while
none is — is one no server sends: malformed (4.0, 4.2).
Then the replica applies `tables` **in the order given**. The server puts
parents' rows before their children's, and children's deletes before their
parents', so in that order no row ever points at a row the replica lacks.
It keeps a table's deletes in the message that carries its upserts: the
rows from a table's first upsert to its last delete are split across
messages only when they do not fit one on their own. So a unique value one
row lets go of is there, in the same message, for another row to take.
For each `Table`:
A table the replica holds from the server is one the server writes: a
catalog, or a table written on both sides. Rows of any other table — a
record of the replica's own, a table it does not know — are rejected, and
their deletes ignored.
1. **Deletes**, first: a value a row lets go of — a unique one — is then
free for an upsert of the same part to take. The keys in `deletes` are
let go of together:
- a row that a row staying for the replica points at — a row of its own,
through any foreign key: one that would refuse the delete, checked at
once or at commit, and one that would cascade or set the pointing
row's columns, which would change a row the server never sent; or a row
it retired — is retired instead (4.3), and so, in turn, are the rows a
row retired so points at among them. Where the table has nothing to
retire it by, the row is kept, and a rejection recorded (section 6);
- every other is deleted, together, so rows that point only at one
another — a tree, a row that points at itself — go whatever the order
of their keys. One the database refuses to let go — a trigger, or a
row of the server's that stays and points at it — is kept, and a
rejection recorded.
2. **Upserts.** Each entry of `upserts` is one row, encoded as the table's
message; `keys[i]` is the key of `upserts[i]`, and there **must** be one
key per upsert. A row whose own key is not the one beside it is no row
the server meant: the replica rejects it under the key beside it. For
each row:
- insert it, or overwrite the stored row with the same key, **whatever
its version**: the messages of an epoch are ordered by their chain
(4.1), so the one applied last is the server's latest, even when its
version is older than the stored one — a server restored from a copy,
or whose clock was set back, sends what it has;
- columns the replica owns in a table written by both sides are **not**
overwritten;
- a row the replica had retired (4.3) becomes live again;
- a row of its own it deleted, in a table keyed by the replica, whose
delete the server has not filed yet (4.4), is **not** taken: the
server sent it before it heard of the delete. The replica records it
**held back** — a rejection marked `held_back` (section 6) — so the
server does not count it held, and sends it again should it keep the
row.
A key both let go of and upserted in one part is held: its upsert comes
after. A key upserted twice in one part is the last row beside it.
**A row the database refuses is tried again once the rest of its part is in, and
once the whole message is** — every part of it, the deletes of later parts
included — each while that takes one more: it may point at a row after it, or
take a unique value a row after it, or a delete after it, gives up. One that a
later part lets go of is not tried again: the server let go of it; nor is one
a later part sends again: the later row is the one, and the earlier is
dropped, neither taken nor rejected. What is still
refused then is rejected (section 6). Two rows that swap a unique value cannot
be taken one at a time — the database checks each row as it is written — so both
are rejected, and keep what they held, until the server sends them otherwise.
**A row the replica cannot take, or let go of, does not fail the message.**
If a row does not decode, if the replica's database refuses it for its data
(a constraint, a trigger), or if the replica does not know the table at all,
the replica **must** leave that row as it was, apply everything else, and
record a **rejection** (section 6) in the same transaction. Nothing a message
carries fails it — not even a row whose refusal rolls the whole transaction
back (a trigger's `RAISE(ROLLBACK)`), nor one a foreign key checked at commit
refuses — because the row it points at is not held, or because rows point
at a value of it the message changed or let go of: a constraint that fails
the commit is the replica finding such a row, never a failure of its
storage. The replica applies the message again, row by row, finds the rows
at fault — by the database's own check of its keys — and applies it once
more with them rejected before they are tried; and should the database
still refuse it for what no row of it explains, it applies it with every
row of it rejected, so that the rest of what it says stands. Anything else
the database answers of a row — a trigger's own error included — refuses
that row. Only a failure of the replica's own storage (the database is
unavailable, the disk is full, the file is damaged) fails the message: then
the replica **must not** acknowledge it, and it will be delivered again.
### 4.2 Snapshots
When the server provisions a replica from scratch, it sends everything the
replica should hold in `Down` messages that carry a `snapshot_id`, then an
`EndSnapshot` naming the tables the snapshot covered. A snapshot of nothing
is its `EndSnapshot` alone.
The `snapshot_id` is a UUID, as the `epoch` is; a message naming anything else
is malformed (4.1).
- A snapshot **begins with its first message**, the one whose `previous` is
0 — the `EndSnapshot` itself, for a snapshot of nothing. It supersedes the
snapshot in progress, if any: the replica forgets what that one named. The
messages after it follow it, as any do (4.1).
- While applying a `Down` of the snapshot in progress, the replica **must**
remember the key of every row it carried, per table — the ones it refused
as well: a refused row keeps whatever the replica had of it.
- On `EndSnapshot`, the replica **must** let go of every row of the named
tables that the snapshot did not name (delete, or retire as in 4.3),
children before parents: **in reverse** of the order the tables are
listed. A row it refused was named, so it is never swept. The rejections
it recorded for those tables before the snapshot began are forgotten — the
snapshot sent again what it should hold — and the ones it recorded since
stand. Then the snapshot is no longer in progress.
- A part of a snapshot's `Down` may carry `recorded`: keys of a setting the
server records the replica holding, which no other field of the part
concerns. Of those, the replica **must** note each row it does not hold as
its own delete (section 7), so the server lets go of it as it files the
delete; one it holds it has noted already, as the snapshot began.
- The messages of a snapshot follow one another, and nothing else comes
between them: a message that follows the last applied and names a
snapshot other than the one in progress — one that ended, or was
superseded — or names none while one is in progress, is one no server
sends: malformed (4.0).
- `EndSnapshot` carries `sequence`, `epoch`, `nonce`, `previous`,
`previous_nonce` and `mac`, and follows the same rules as `Down` (4.1). It
needs no count of what the snapshot sent: its messages are chained, and one
lost is a gap.
### 4.3 Retired rows
A replica that must let go of a row that one of its own rows still points at
(a receipt that names an order) keeps the row and marks it retired: a column
the replica owns, set to when it was retired. Retired rows are out of
everything the replica offers its users, but stay for what points at them,
and only that long: once nothing that stays points at them — a live row or
a retired one, of any table — the replica lets go of them, children first.
It looks after every message it applies, once that message is applied and
apart from it, so a row it cannot let go of never holds a message back; and
it says nothing of one it cannot. A retired row holds none of its unique values against a live one.
A retired row the server sends again becomes live.
A row of a table written on both sides that the replica edited, and whose
edit the server has not filed yet (section 7), is retired too when it is let
go of, rather than deleted: the edit still goes up, as the row is. Once the
server files it (4.4), the replica lets go of the row. Where the table has
nothing to retire it by, the replica refuses to let it go (section 6), and
the server sends the delete again later.
### 4.4 `Filed`
The server answers each upload (section 7) once it has filed it. On `Filed`,
the replica **must** forget the notes those uploads carried — the ones whose
latest send carried that number, and no other: a note sent again since is
forgotten only on the answer to that send, and a row written since the send
goes up again. A number none of its sends carries — meant for another
replica, or for this one before it was restored — names nothing. The answer
may arrive before the replica recorded that the transport took the upload:
it counts all the same.
### 4.5 Wishes
A **setting** is a table of the replica's own whose rows go up as a record's
with a version do (section 7) — a value the replica holds and acts on: a
module's configuration, a screen's brightness — some columns of which the
server may **wish** other values. Which columns a wish sets, and which column
is the version, is the table's declaration, agreed between the server and the
replica as the table's encoding is (section 3). A replica that holds settings
holds the server's wishes in a table of the engine's, `sync_wishes`: a table
written on both sides (4.1), its rows encoded as the `Wish` message, its key
the wish's `id`. A replica that holds none needs none of this section: it
rejects the rows of `sync_wishes` as those of any table it does not know.
A wish is one row of a setting — `table`, `key` — and what the server wants
it to hold: `wanted`, the row encoded as `table`'s own, of which the replica
takes the columns a wish sets, and nothing else. One row has one wish at
most; a new one replaces it, under a new `version`, a number the server draws
at random: only whether an answer is of the wish the replica holds matters,
never which version is the later. The server owns `id` to `note`; the replica
owns the answer — `answered`, the version it answers, `outcome`, `reason` and
`answered_at` — which it **must not** take from a message: a wish it takes
that it did not hold is one it has not answered.
Once the message that brought a wish is committed — **never** inside the
transaction that applies a message, since carrying one out may take time and
reach outside the database — and while no snapshot is in progress (4.2: its
end may let go of a wish), the replica carries out every wish it holds, not
retired (4.3), that it has not answered, or answered `waiting`. It takes them
**one at a time, each read again just before**, so a wish replaced or
withdrawn meanwhile is carried out as it is then, or not at all:
1. It reads `key` as `table`'s key (section 3) and `wanted` as `table`'s row.
A table it holds as no setting, or a row it cannot read — a table or an
encoding this build does not know — it answers `waiting`, and carries out
with a build that can. A key that is not the table's, a row whose key is
not `key`, or a row of another replica than itself (by the setting's
origin) it answers `refused`.
2. A row it does not hold it answers `waiting` (it holds no such row yet),
and carries the wish out once it does: it never writes a row a wish
names.
3. With `if_unchanged`, the wish is based on the version `wanted` carries: if
the replica holds the row at another version, it answers `superseded`,
and does not carry it out — the replica's value stands. Versions are
compared as text: an integer decimal; an instant in UTC, RFC 3339,
**truncated** toward the past to the microsecond, always six fractional
digits and `Z` (`2026-10-12T10:00:00.123456Z` for `.1234567`).
4. Otherwise it carries it out, however the setting takes it, and answers
`applied` — then, in **one** transaction, it writes the wished columns
onto the row as it holds it then, its version moved past what it was (an
integer one more; an instant now, truncated so, or a microsecond past the
old one when the clock is behind), and records the answer: a version that
cannot move (an integer at its largest), or a write its database refuses,
is answered `refused`, with why, and the row left as it was; `refused`,
with why — the row as it was — final for that wish; or `waiting`, with
why, and carries it out again later.
An answer is recorded only while the wish the replica holds is still the one
it answers (the same `version`, not retired); a wish replaced meanwhile is
carried out next, and the row keeps what carrying out the last one wrote. A
`waiting` answer is recorded when it is new — another reason — not every time
it waits again. The answer and the row it wrote are noted like any write of
the replica's (section 7): the answer as an edit of the columns the replica
owns of a two-way row.
A replica that stops after carrying a wish out and before it records the
answer carries it out again: carrying out the same wish twice **must** leave
the setting as once does.
---
## 5. Acknowledging
There are two acknowledgements, and a replica gives both.
### 5.1 To the transport
After the transaction that applied a message **commits**, the replica
acknowledges the message to the transport, which then delivers the next one.
Never before the commit: a replica that acknowledged and then failed to commit
would never be sent that message again.
### 5.2 To the server: what was applied
The server counts a row as held by a replica **only once the replica says it
applied the message that carried it**. Until then, the row is "on its way".
That is what makes the server's progress figures true.
The replica **must** tell the server the `(epoch, sequence, nonce, mac)`
of the last message it applied, as that message carried them, in an `Up`
on its first lane (section 7) that carries them in `epoch`, `sequence`,
`nonce` and `mac`. It may do so after every message, or once for several
(a replica that applied messages 5, 6 and 7 reports 7). It should do so
within seconds of applying, and again whenever it applied something new,
or was delivered a message at or below the last it applied. `sequence` 0
says it has applied nothing yet.
A replica with a gap (4.1) **must** say so: `gap`, the sequence of the
newest message it could not follow, on every `Up` of its first lane, with
its last applied, until a snapshot begins; and it **must** send one at once
whenever that sequence grows. The server answers with a snapshot (A.2).
---
## 6. Rejections
A row the replica could not take, or could not let go of (4.1), is a
**rejection**: the table, the key — **required**, in the form of section 3:
the one the row came beside, `keys[i]`, or its delete's — why,
and the `(epoch, sequence)` of the message that carried the row, or its
delete — for a row the end of a snapshot could not let go of, the
`EndSnapshot`'s; for a row held retired for the replica's edits (4.3) that
it could not let go of once they were filed, the message that let go of
it. A row whose key cannot be told is logged and not reported. A row held
back (4.1) is a rejection marked `held_back`: nothing is at fault, so the
server raises no alarm over it; the rules below hold for it all the same.
- The replica **must** record a rejection in the same transaction that left
the row out, so it cannot be lost.
- It **must** report each rejection to the server in an `Up` (`rejected`),
**no later than** the `Up` that says it applied the message that refused
it (5.2): the server counts the rows a message carried as held once it
hears the message was applied.
- It **must** keep the rejection until it takes the row (a later message
carries the row and it applies) or lets go of it (a delete, or a snapshot
that does not name it): a digest (section 8) leaves rejected rows out, as
the server leaves out the rows recorded refused. It reports only the
rejections of the epoch it follows; a snapshot of a new epoch clears the
others — those of the tables it names as it ends, and those of a table it
does not hold from the server, which no snapshot names. A rejection of a
row it holds no copy of — of a table it does not hold from the server, or
a row it never took — leaves nothing out of a digest: it **may** forget
that one once reported, and the engine does, so what it keeps of
rejections is bounded by what it holds.
- It keeps what the server said within bounds: a reason **may** be cut (to
512 bytes), and rows of a table it does not know, named or keyed longer
than that, are logged rather than kept — no server sends such a table. So
any rejection fits a message up — the backlog (section 7) waiting for the
next one when it would leave the first rejection no room — and never
holds back the confirmation. Rejections count against a message's rows
as the rows it carries do.
---
## 7. Sending rows up
For a table the replica writes and the server mirrors:
1. **Note** every insert, update and delete in the writing transaction: the
table and the key — on an update that changes the key, the old key too,
which is gone. (A trigger is the only way no write path can forget.)
What the replica writes while applying what the server sent is not
noted: it is the server's already. A row of a table written on both sides
begins on the server; the replica edits only its own columns of it, and
only those edits go up: it **must** refuse an insert of one, an update
of a column it does not own, and a delete of one but a row keyed by
itself, in a table keyed by the replica. A record without a version is
history, written once. A setting is noted as a record with a version is;
and in the transaction that begins a snapshot (4.2) the replica **must**
note again every row of its settings, and every answer it gave to a wish
it holds (4.5): the server's record of them may be behind — it, or the
replica, restored from an older copy — and is set straight by what the
replica says it holds now (A.3). Such a note is **re-stated** until the
upload that carries it is filed, a later write of the row
notwithstanding: its row goes up in a part of its own, `restated` set.
2. **Upload** noted rows, as they are **at upload time**, in an `Up`:
- each row in `tables[].upserts`, encoded as its table's message;
- a row that is gone by now, as its key in `tables[].deletes`, but only
for a table keyed by the replica that wrote it: history a replica pruned
is not the server's to delete;
- one key per row in `tables[].keys`;
- `tables[].restated` set on a part of re-stated rows only: a table's
rows go in two parts when some are re-stated and some are not, and a
delete always goes in a part without it;
- upserts parents first, in the order the tables point at one another,
then deletes children first;
- in `uploads`, the number of this upload: a **fresh** one on every send,
resends included, drawn **at random** from 1 to 2^63 − 1, so an answer
meant for another replica, or for this replica before it was restored
from an older copy, never names its notes;
- within the transport's size limit: what does not fit waits for the next
upload. A row that can never fit is set aside — kept, counted in the
backlog, never sent until the replica runs again with a build that may
send it. An `Up` the transport refuses for good is sent again with half
its rows and rejections, and so on, until what it refuses is alone: that
row is set aside, that rejection taken as told (it must not hold back
the confirmation of what was applied), and nothing beside them — but only
if the transport took some other message of that stream meanwhile: a
transport that refuses every message says nothing of any one row, and
the replica sets nothing aside, raises the alarm and asks again after a
backoff.
3. **Wait for `Filed`** (4.4) naming that upload, then forget its notes. An
upload not answered after a while (minutes) should be sent again; the
server files the same rows idempotently.
A replica **may** say what it wrote and the server has not filed yet, in
`Up.backlog`: per table, rows not sent yet (`unsent`), rows sent and not
yet `Filed` (`unfiled`), and rows set aside (`set_aside`). Say it
when it changes — at once when it empties — and not on every write; say it
again now and then while it is not empty, and to a server whose epoch
changed, either of which may have lost it. An `Up` without `backlog` leaves
the last one standing (A.3). A replica that never says leaves the server with
nothing to show, and nothing breaks.
A replica may send its writes on several **lanes** — streams of `Up`s the
transport keeps apart, each carrying the writes of some of its tables, so a
table that writes often never waits behind the rest. Every table that goes up
is on exactly one lane. Rejections, the last applied message, digests and
the backlog go on the first. The transport keeps each lane in order
(section 2): the backlog an earlier `Up` carried must not arrive after a
later one's.
One `Up` may carry several of these at once: rows, rejections, digests, the
backlog, and the last applied message.
---
## 8. Digests
From time to time (hourly is reasonable), a replica **should** report what it
holds of every table the server sends it, in `Up.digests`, together with the
`(epoch, sequence, nonce, mac)` of the last message it applied (5.2). It
**must** leave out a table it wrote rows of that the server has not filed
(`Filed`, 4.4); the reason is given at the end of this section.
- `table`: the table;
- `count`: how many rows it holds, **leaving out** rows it retired (4.3) and
rows it rejected (6);
- `fingerprint`: FNV-1a, 64 bits, over the keys of those rows as text (section
3), **sorted** (byte order), each followed by a newline (`\n`):
```
hash = 0xcbf29ce484222325
for each key, sorted:
for each byte of key + "\n":
hash = hash XOR byte
hash = hash × 0x100000001b3 (mod 2^64)
```
Test vectors: no keys → `0xcbf29ce484222325`; the single key `a` →
`0x089bdc07b544e7b2`.
It **should** report its settings and its answers as well, which the server
records as the replica uploads them: a server restored from an older copy
records what the replica said before, and no message it sends shows it. Their
lines are fingerprinted the same way, and say more than the key:
- a setting: each row it holds, as its key, a tab (`\t`), and its version as
text (4.5);
- `sync_wishes`: each wish it holds, left out as above, as its key, a tab,
the version it answered, a tab, and the outcome — each empty for a wish it
has not answered.
Test vectors: the setting line `a\t1` alone → `0x6f375e81eb6a6700`; the
unanswered wish `w` (`w\t\t`) → `0xba0c6af6f14e26d2`; `w` applied at version 7
(`w\t7\tapplied`) → `0x2e00e679fcb6ffe0`.
A replica **must** leave out of its digests every table of which it wrote
rows the server has not filed yet (section 7): what the server records of
it is about to change, and a comparison now would find them apart for
nothing: the server records a row the replica deleted as held until it
files the delete, and then records it held no more only where the replica had
applied every message that carries the row (Appendix A.3).
That holds from when it reads them to when it sends them: a table written in
between — a write that may go up in the very message — goes without its
digest too.
---
## 9. A session, start to finish
```
server replica
│ (every arrow down is a ToReplica carrying the message named)
│ Down {snapshot s1, seq 101, previous 0, products…}
│ ──▶ begins s1, applies, remembers its keys
│ Down {snapshot s1, seq 102, previous 101, orders…}
│ ──▶ applies
│ EndSnapshot {s1, seq 103, previous 102, [products,orders]}
│ ──▶ sweeps what s1 did not name
│ ◀── Up {epoch E, sequence 103} "applied up to 103"
│ progress: holds 3,200 of 3,200
│
│ (a product is renamed)
│ Down {seq 104, previous 103, products: 1 row}
│ ──▶ applies
│ ◀── Up {epoch E, sequence 104}
│
│ (a row the replica refuses: a check it has, the server lacks)
│ Down {seq 105, previous 104, orders: 2 rows}
│ ──▶ applies one, rejects one
│ ◀── Up {sequence 105, rejected [orders 9f…: "check failed"]}
│ the row is set aside for this replica
│
│ (writes two receipts)
│ ◀── Up {tables [receipts: 2 rows], uploads [57]}
│ filed
│ Filed {uploads [57]} ──▶ forgets the notes upload 57 carried
│
│ ◀── Up {digests […], epoch E, sequence 105} (hourly)
│ matches what the server records: nothing to do
```
---
## 10. Conformance checklist
The engine's repository holds test vectors, each line a name, what the
other side makes of the message, and the message in hex; each file's header
says how to read it.
- `tests/golden/to_replica.txt`: what the server sends one replica, step by
step — a provisioning of several messages, the first delivered again,
updates, a row the replica's own check refuses, a delete of a row a row
of its own points at, a snapshot cut short and the one that supersedes
it, a message lost on the way, the gap after it and what comes during the
gap, the answer to an upload, a version older than the one held, a field
the replica does not know, a new epoch, a wish of a setting the replica
holds — carried through a provisioning — and its withdrawal. Each message
says what the
replica makes of it (`applied`, `ended`, `filed`, `already`, `gap`, or
`lost` on the way), and each step is followed by a `holds` line: what
the replica then holds, as JSON.
- `tests/golden/malformed.txt`: messages no server sends — and the few
that set the scene between them — each with what a replica makes of it,
`malformed` for most.
- `tests/golden/to_server.txt`: what a replica sends up after the steps
of `to_replica.txt` before its upload is answered — its rows, its
rejections and what it applied; its digests; the same with a seal the
server never made — each with what the server makes of it.
- `tests/golden/to_server_verdicts.txt`: uploads a replica sends after a
provisioning, a change and a take-back it applied — a refused delete
with what it applied, an edit of a two-way row, a delete of a row of its
own, a refused sweep, a row of its own held back, an answer to a wish and
to one withdrawn, a setting and an older version of it, a gap, what it
applied said again lower, of another
epoch, and past anything sent — each with what the server makes of it.
A replica implementation is complete when:
- [ ] it reads every message as a `ToReplica`, leaves one of a later protocol
unacknowledged, and sets `protocol` on every `Up`;
- [ ] it applies a `Down` in one transaction, tables in the order given;
- [ ] it ignores a message at or below the last applied in the same epoch,
and says again what it applied; acknowledges without applying a
malformed message (4.0, 4.1);
- [ ] it applies a message only when it follows the last applied —
sequence and nonce — or begins a snapshot; one that follows another is
a gap, after which it applies nothing until a snapshot begins, and it
says the newest message it could not follow on its first lane,
again whenever that grows (4.1, 5.2);
- [ ] it overwrites a row with what the server sends, whatever its version;
- [ ] it never overwrites the columns it owns;
- [ ] it retires a row it cannot delete, and revives a retired row sent again;
- [ ] it applies a table's deletes before its upserts, lets go of the deletes
together, and tries a refused upsert again once the rest are in (4.1);
- [ ] it begins a snapshot with the message that follows nothing — an
`EndSnapshot` included — and sweeps on its end, in reverse table order;
- [ ] it leaves as it was and records, in the same transaction, a row it
cannot take or let go of;
- [ ] it reports rejections, each with the message that refused it, before
it says it applied that message, and keeps them until it takes the
row or lets it go — a row of its own whose delete is not filed among
them, marked `held_back` (4.1);
- [ ] it acknowledges the transport only after committing;
- [ ] it reports the last applied `(epoch, sequence, nonce, mac)` to the
server, as the message carried them;
- [ ] it notes its own writes in the writing transaction, uploads them as they
are within the transport's limit, gives every send a fresh random
number, and forgets on `Filed` only the notes that send carried, as it
carried them;
- [ ] it reports digests with the fingerprint above (optional, recommended);
- [ ] it says its backlog when it changes (optional, recommended);
- [ ] if it holds settings: it holds their wishes as a two-way table, takes
no answer from the server, carries each out after the message that
brought it is committed — superseded, unread or applied as 4.5 says —
and records the answer, with the row it wrote, in one transaction;
notes every setting and every answer again when a snapshot begins,
and sends them re-stated until filed (section 7); deletes each row a
snapshot records it holding that it does not (4.2); its digests, if it
reports them, include its settings and its answers (section 8).
---
## Appendix A. What the server does with it
Nothing here is a duty of a replica. It is what the server does with what a
replica sends, written down so that a replica's author knows why the rules
above are what they are, and what to expect when a replica breaks one. The
sections it explains are named at each part.
### A.1 What the server guarantees in return
- Every change committed on the server reaches every replica that should hold
the row, as the row is at sending time.
- A row is sent with every row it points at that the replica lacks, and is
taken back only once nothing the replica keeps points at it.
- Every message carries a number and a random nonce of its own, and the
numbers a replica is sent rise within an epoch in the order it is sent
them; each names the one before it, number and nonce, so a replica can
tell it missed one — even when a restored server numbers a message as
one it applied. What a message carries is recorded before it is sent,
and a message that the transport did not take is sent again, under the
same number and nonce, before anything after it.
- A replica that leaves the last messages it was sent unconfirmed, while
nothing newer goes to it, is provisioned again after a while: the transport
may have lost them.
One that says it missed a message is provisioned again at once.
- A server whose database was restored from an older copy finds out from
the first replica that says it applied a message the server sealed and
that copy has no record of sending it, and provisions every replica
again, under a new epoch. A replica restored from an older copy finds
out from the next message it is sent, and says so; on a server with
nothing to send it, the server finds out from what it says it applied,
which is less than it said before.
- A row the server cannot send to a replica, or that a replica rejected, is
set aside and sent again after a fix: it is never silently dropped.
- An upload is answered with `Filed` only after the transaction that filed it
committed.
### A.2 What the server makes of "what I applied" (section 5.2)
The server checks the seal: one it did not make — a replica that lies, or a bug
— is ignored, and resets nothing. It ignores a report that does not parse, and
one of another epoch — unless it last heard the replica apply a message of its
own epoch: a replica only goes forward, so it follows an epoch this database
never had, which was restored from a copy older than that epoch began. The
server provisions that replica again, unless a snapshot written for it since is
on its way. A sealed one it judges against what it recorded sending the replica:
- a message past the last it recorded sending it — or, having recorded
none since it last provisioned it, past every number it drew — or one at
the sequence of the last it sent it, or of the last it heard applied,
with another nonce: the server sealed it, and has no record of it. Its
own database was restored from a copy older than what the replica
applied. It raises an alarm — whoever runs it should know the database
went back — takes a new epoch, with a new secret, drops what it was about
to send, and provisions every replica again;
- a message older than the last it heard the replica applied: the replica
was restored from an older copy, and holds less than the server records.
The server provisions it again, unless a snapshot written for it since
is on its way;
- otherwise the server counts the rows of every message up to it as held.
A replica with a gap (4.1) is provisioned again, unless a snapshot that
began after that message is on its way: a snapshot that began before it is
one the replica lost the beginning of, or applied before it was restored
from an older copy. A gap past every message the server sent the replica is
none it could have missed: malformed, and left out.
Neither a gap nor a message older than the last applied carries a seal the
server can check, so what a replica says of itself provisions it again at
most once a minute, and twice as long between each time while it keeps
saying so, up to 32 minutes; one quiet for 64 minutes starts over. One that
says it sooner is provisioned again once it may: the server notes it for
then.
### A.3 How the server files an upload (section 7)
The server files an upload under **the replica it came from** (the transport
says which), whatever the rows themselves claim: a row of a table keyed by its
replica that names another replica there is malformed, and left out. A row of a
table written on both sides is an edit of the columns the replica owns, filed
only as an update of a row the server has and records the replica holding. One
it does not record the replica holding while it provisions the replica again —
the provisioning pending, or written and not confirmed — is kept, and filed once
it does; otherwise, one of a row the replica no longer holds — the server
deleted it, or is taking it back — is left out: the server's wins. One of a row
it never sent the replica is malformed, and left out. A row the server cannot
file, or a delete its database refuses, is kept on the server, not lost, and
filed later; so are an upload's rows whose filing fails as a whole for a reason
a resend cannot cure. Either still counts as filed for `Filed`. A replica's
delete of a row of its own is a fact whether the server's database lets the
row go or refuses to: the server records the replica holding it no more, and
sends it again a row it kept — but for a row that a message the replica had
not applied when it sent the delete carries (the last it says it applied, or
else the last the server heard it apply). That one the server still records
held: the replica takes that message's version if it hears the delete filed
first, and the server's own delete of the row, if it let it go, follows;
otherwise the replica holds it back (4.1), and its rejection, which comes no
later than it says it applied the message, records the row refused (A.4). A
delete filed later, from what the server kept, leaves the row held the same
way: a delete of a row a replica does not hold changes nothing there. The server
keeps, of each row, the newest upload of it: a later upload of the row replaces
what it kept, or drops it once filed, so what is filed later never rolls the row
back. A record with a version is filed only over an older version of it, and so is
a **setting** — a value the replica holds and acts on — but one in a part
`restated` (section 7), which is filed whatever its version: it is what the
replica holds now, even when a replica restored from an older copy says an older
version; a delete is filed whether its part is `restated` or not. The server
keeps a row only with its key in `keys`: one without is malformed, and left
out. What the upload says of the replica — rejections, the last applied
message, a gap, digests, the backlog — is filed apart from its rows, so neither
holds back the other. Deletes of a table not keyed by the replica, and keys that
are not the table's, are malformed and left out. An upload beyond the server's
limits — more bytes than a message takes, or more rows and rejections together
than one carries: a rejection counts as a row — is malformed: dropped,
unanswered, so it waits on the replica until a server that takes it runs. A
replica's limits are the server's, or less. So is an upload from a sender that
is no replica of the server's.
The server keeps the last backlog it was told, with the time, and shows the
replica as catching up while it is not empty.
### A.4 How the server records a rejection (section 6)
On a rejection of the last message that carried the row, the server records the
row **refused**: still held for every decision that takes rows back — a delete
still goes when the row leaves the replica's scope, and a refused delete is sent
again — and not held for progress, or for digests. The row is set aside for that
replica, and sent again, or its delete, when the relay restarts or on a timer,
which is after a deploy on either side has had the chance to fix the cause; it
is taken once the replica applies a later message that carries it. A rejection
of a delete re-records the row the server took back. A row a replica held
back (`held_back`) is recorded the same way and raises no alarm — nothing is at
fault, and a fix is awaited for nothing: the retry sends it again, should the
server keep the row. A rejection of a message
other than the last one that carried the row, or of another epoch, names a
version that no longer matters, or none it was sent, and is left out. The key is
read as its table's key (section 3) whatever its spelling. A rejection of
anything else — a table the server does not send, no key or one that is not the
table's, a message never sent the replica — is malformed and left out. Nobody
repairs the row by hand.
### A.5 How the server compares digests (section 8)
The server compares a digest only when the replica has applied every message
recorded for it (the same epoch and last sequence, sealed by the server), and
against what it recorded as of that message: when it has sent the replica
more meanwhile, it waits for the next digests. It compares a setting's
against the rows of it it holds of that replica, and those of `sync_wishes`
against the answers it keeps — neither while it keeps rows of that table the
replica uploaded and it could not file yet, as the replica leaves out a table
it wrote rows of that are not filed. If they differ, it provisions the replica
again from scratch (4.2): the replica re-states its settings and its answers
as the snapshot begins (section 7), and deletes those the snapshot records it
holding that it does not. Digests that differ again
within a day of the provisioning they caused are a bug no provisioning cures:
the server logs them and does not act on them. A digest of a table the server
neither sends the replica nor holds as a setting — the replica's records, a
later build's table, one it no longer mirrors — is skipped. Two digests of one table are malformed: none of that `Up`'s digests
is compared. The server compares a replica's digests at most once every ten
minutes: those that come sooner are not compared. A replica that skips
digests loses only this safety net.
### A.6 How the server keeps wishes (section 4.5)
The server writes a wish of a setting row when its host asks, in the host's
transaction, under a version it draws at random — so a server restored from
an older copy wishes under other numbers than it did — and sends it to the
replica the row belongs to (the setting's `origin`), as it sends any row: one
withdrawn is deleted, and taken back as a row is. It never sends an answer
down. It files an answer as the edit of a two-way row it is (A.3): only while
it records the replica holding the wish — so an answer to a wish withdrawn is
left out — and keeps it beside the wish; a wish stands as its answer says
only while that answer is of its version: `pending` until then. A final answer
— `applied`, `refused`, `superseded` — stands against a later upload of
another answer to the same version, which the transport may have kept back,
but for one re-stated (section 7). It keeps the row wished apart from any
encoding, and encodes it as it sends the wish: the setting row it holds, or
the one wished when it holds none, with the wished columns and the version the
wish is based on laid over it. Table names beginning `sync_` are the
engine's: no host table may take one.