aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-16 13:59:28 +0000
committertv <tv@krebsco.de>2026-11-16 15:06:15 +0100
commit3b5045838daec9d8ffb46ff030bf17e08fd53148 (patch)
tree93f31cc2872c0761f1570a4b82a5ba692b2ae0fc
parent56eafff2d109633042e5b56ec8d695989d81eeee (diff)
docs/store: checkpoints
A store holds a checkpoint, the state at some heads written down (those heads, the events before them its fold keeps, and what the fold says of the rest), and the events after it. The fold says when a node moves to a later checkpoint: the node builds it itself, forgets what it doesn't keep and every event whose history lacks its heads, and refuses such events from then on, so that it holds what is relevant and nothing else. A checkpoint a node can't build, as it was away too long or joins, it takes only where its operator pins it. A store's root is its first checkpoint, and a fork's root a checkpoint at the heads it forks at, which nodes holding the history up to them check, and others take on their operator's word. On Automerge, a remake's snapshot holds the store as it is at the base, so what a checkpoint forgot leaves the document there.
-rw-r--r--docs/store.md223
1 files changed, 147 insertions, 76 deletions
diff --git a/docs/store.md b/docs/store.md
index eddf3cf..dbe2f59 100644
--- a/docs/store.md
+++ b/docs/store.md
@@ -1,11 +1,14 @@
# The store: a design
-A design, not what the code does: none of this is built. The store is a set of events
-that only grows. Each event is named by the hash of its bytes and names the events it
-builds on; it is judged where it was written, at that history, so every node judges it
-alike; and the events a node holds read as one state. What the events are, how one is
-judged and what they read as is a **fold**'s, and the store is generic over it. The
-federation ([`federation.md`](federation.md)) is its first fold.
+A design, not what the code does: none of this is built. The store holds events. Each
+event is named by the hash of its bytes and names the events it builds on; it is judged
+where it was written, at that history, so every node judges it alike; and the events a
+node holds read as one state. The store starts from a checkpoint, the state at some
+heads written down, and holds what came after it; moving to a later checkpoint, a node
+forgets what matters no more, so that it holds what is relevant and nothing else. What
+the events are, how one is judged, what they read as and when the store moves to a
+checkpoint is a **fold**'s, and the store is generic over it. The federation
+([`federation.md`](federation.md)) is its first fold.
The store asks nothing of what carries its events. It is built first inside a swarm's
Automerge document (On Automerge): continuum's sync, transports, saving and remakes
@@ -17,16 +20,54 @@ feature: without it, continuum builds and behaves as it does.
An **event** is bytes, named by its **ID**: the SHA-256 of its bytes, written as 64
lower-case hex digits. In its bytes it names the events it builds on, its
**dependencies**, by their IDs; how it names them is its fold's. An event's **history**
-is everything it builds on: its dependencies, theirs, and so on, which its ID fixes. A
-set of events is **whole** where it holds every event's history; the **heads** of a
-whole set are the events nothing in it builds on.
+is everything it builds on: its dependencies, theirs, and so on, which its ID fixes. The
+**heads** of a set of events are the events nothing in it builds on. An event is
+**above** some heads where it has them all in its history, and so has every event in its
+history that isn't one of them or in their history: it builds on them, and on nothing
+written beside them.
-A store has one **root**, given when the store is made: an event it takes without
-judging, whose ID is the store's. Every other event it takes is in the root's history,
-or has the root in its own: a root that builds on nothing starts a store anew, and one
-that builds on another store's events starts a fork, which carries their history
-(Forks). A store takes an event only once it holds its dependencies, so it is whole at
-all times.
+## Checkpoints
+
+A **checkpoint** is the state at some heads, written down: those heads, the events
+before them its fold keeps, by their IDs, and what the fold says of the rest (the
+federation: the version current there, and every event that counts there). It is named
+by the hash of its encoding, which its fold gives, and built byte for byte from its
+heads, so every node holding the history up to them builds the same one.
+
+A store holds a checkpoint, the events it keeps, byte for byte, and the events after it:
+each above the checkpoint's heads, its dependencies among those heads and the events
+after them; a root is its own checkpoint's one head (below). A store takes an event only
+once it holds its dependencies, so it holds every event's history back to its
+checkpoint.
+
+A store's first checkpoint is its **root**, taken without judging, whose ID is the
+store's. A root without heads starts a store anew; one at another store's heads starts a
+fork (Forks). Its events build on the root itself, whatever heads it was built at: until
+the store moves to a later checkpoint, the root's ID is the one head they all have in
+their history.
+
+### Moving to a checkpoint
+
+The fold says when the store moves to a later checkpoint, and at which heads (the
+federation: by a version that names them, once a node takes it). A node then builds the
+checkpoint at those heads, forgets every event before them that it doesn't keep and
+every event not above them, and refuses such events from then on. The fold names heads
+that whatever makes the store move is above, so that moving refuses none of it. Judging
+an event after those heads needs nothing the node forgot, as the fold keeps what judging
+reads; and what is read from the checkpoint and the events after it is what the whole
+history reads, but for what the fold lets a checkpoint forget. Its tests check both
+(Tests). A node keeps what it forgot for as long as its operator sets, and gives it to
+nodes catching up.
+
+### Pinned checkpoints
+
+A node builds every checkpoint it moves to itself, from the one before and the events up
+to the new heads, and judges every event after it. A checkpoint it can't build, as it
+was away longer than its peers kept what they forgot, or as it joins, it takes only
+where its operator pins it, by its ID, and then judges every event after it as any. A
+node joining starts from the root its operator names, the swarm's ID, or from a
+checkpoint its operator pins. So a node takes nothing on a peer's word: what it didn't
+build or judge itself, its operator vouched for.
## The fold
@@ -36,9 +77,11 @@ A fold says, of its events:
are none, and are refused;
* **whether an event is taken where its history reads as a given state**: judging. A
root is taken only as its own store's, never by judging;
-* **the state a whole set of events reads as**, built by adding its events one at a
- time, each after its dependencies, and the same whatever order they come in: the state
- of a node's store, and the state at an event's history, which judging reads;
+* **the state a checkpoint and the events after it read as**, built by adding the events
+ one at a time, each after its dependencies, and the same whatever order they come in:
+ the state of a node's store, and the state at an event's history, which judging reads;
+* **the checkpoint at some heads**: what of the history before them it keeps, and what
+ it says of the rest; and when the store moves to one;
* **the store's members**, the nodes that carry it, at a state, each with the name of
its group (Members);
* where it needs to, **what a node refuses that its history takes**, by what the node
@@ -48,7 +91,7 @@ In Rust, roughly:
```rust
pub trait Fold {
- type State: Clone + Default;
+ type State: Clone;
/// What the event builds on; `None` where its bytes are none of this fold's events.
fn dependencies(event: &[u8]) -> Option<Vec<Id>>;
/// Whether the event is taken where its history reads as `at`.
@@ -59,6 +102,12 @@ pub trait Fold {
fn keeps(_now: &Self::State, _id: &Id, _event: &[u8]) -> bool {
true
}
+ /// The checkpoint at `heads`, read as `at`: its bytes, and the events it keeps.
+ fn checkpoint(at: &Self::State, heads: &[Id]) -> (Vec<u8>, Vec<Id>);
+ /// The state a checkpoint reads as, with the events it keeps.
+ fn start(checkpoint: &[u8], kept: &[(Id, Vec<u8>)]) -> Result<Self::State, Refused>;
+ /// The heads of a later checkpoint, where a store reading as `now` moves to one.
+ fn moves_to(now: &Self::State) -> Option<Vec<Id>>;
/// The nodes that carry the store, each with its group.
fn members(state: &Self::State) -> Vec<(NodeId, String)>;
}
@@ -72,41 +121,46 @@ which its tests check (Tests).
## What is promised
1. **Every node takes an event or none**, but for what a fold has a node refuse by what
- it took, and what an operator has its node drop (A node's own). An event is judged at
- its history, which its ID fixes, so every node judges it alike, whenever and from
- whomever it comes. An event refused is refused with everything built on it.
-2. **Nodes that hold the same events read the same state**, whatever order the events
- came in, and whatever carried them.
+ it took, what an operator has its node drop (A node's own), and what moving to a
+ checkpoint refuses. An event is judged at its history, which its ID fixes, so every
+ node judges it alike, whenever and from whomever it comes. An event refused is
+ refused with everything built on it.
+2. **Nodes that hold the same checkpoint and the same events after it read the same
+ state**, whatever order the events came in, and whatever carried them.
3. **Nothing underneath adds an event or takes one away.** What a node holds is what it
- took. Which document carries the events, which changes put them, a remake, a rejoin:
- the fold sees none of it (On Automerge).
+ took, less what a checkpoint forgot. Which document carries the events, which changes
+ put them, a remake, a rejoin: the fold sees none of it (On Automerge).
+4. **A node takes nothing on a peer's word.** It builds every checkpoint itself and
+ judges every event after it, but for a checkpoint its operator pins (Pinned
+ checkpoints).
Not promised: that an event reaches every node, as a node may withhold what it holds;
-that the store stays small, as it keeps every event and nothing in it shrinks; that it
-stays fast.
+that an event not above a checkpoint's heads is taken once nodes moved to it; that a
+checkpoint a node takes on its operator's word is the one the others built; that the
+store stays fast.
## A node's own
A fold may have a node refuse an event its history takes, by what the node took before:
-the federation's node takes a version only where it changes the one the node reads
-([`federation.md`](federation.md), Changing the policy). And an operator may have its
-node **drop** events it took. Either way the node refuses the event and everything built
-on it, from whoever brings it, until its operator says otherwise, and reports it. No
-peer's word moves a node; its operator's does. A node that refuses what another took
-holds other events, and reads its own state from them; two that hold the same read the
-same.
+the federation's node takes a version only where it changes the one the node reads, and
+moves to a checkpoint as it takes a version naming one
+([`federation.md`](federation.md), Changing the policy, Checkpoints). And an operator
+may have its node **drop** events it took. Either way the node refuses the event and
+everything built on it, from whoever brings it, until its operator says otherwise, and
+reports it. No peer's word moves a node; its operator's does. A node that refuses what
+another took holds other events, and reads its own state from them; two that hold the
+same read the same.
## Forks
-A **fork** is a store whose root builds on events of another, at heads its maker
-chooses. It carries the root's history, byte for byte, each event judged at its history
-as in the store it came from: a fork is whole from its root back to the first, and any
-node checks it from those events alone, whether or not it holds the store the fork came
-from. Then it takes only events with its root in their history. What the store it came
-from takes beside or after those heads, the fork never takes; nor does that store take
-what the fork takes, as no store takes another's root, nor anything built on it. A
-node's own refusals are its store's: in a fork it follows, it judges the root's history
-afresh. What a fork's root holds, and who makes one, is its fold's: the federation
+A **fork** is a store whose root is a checkpoint at heads of another, which its maker
+chooses, with what the fork's fold says there (the federation: the fork's version). A
+node holding the history up to those heads builds the root and checks it; one that
+doesn't takes it on its operator's word, which names the fork anyway. The fork takes
+only events with its root in their history: what the store it came from takes after
+those heads, the fork never takes; nor does that store take what the fork takes, as no
+store takes another's root, nor anything built on it. A node's own refusals are its
+store's. What a fork's root holds, and who makes one, is its fold's: the federation
builds one byte for byte from its version and its heads, so that one version and one set
of heads make one fork ([`federation.md`](federation.md), Forks).
@@ -114,13 +168,14 @@ of heads make one fork ([`federation.md`](federation.md), Forks).
The store's first home is a swarm's document, which continuum's sync, transports, saving
and remakes carry. A swarm holds a store from its genesis change, or not at all, and its
-document holds nothing but the store's events and continuum's protocol data.
+document holds nothing but the store and continuum's protocol data.
### What the document holds
| Where | What |
|---|---|
-| `_continuum/events/<ID>` | an event, as bytes, at its ID |
+| `_continuum/events/<ID>` | an event, as bytes, at its ID: the root, the events a checkpoint keeps, and those after it |
+| `_continuum/checkpoint` | the store's checkpoint, as bytes, where a snapshot holds one other than the root |
| `_continuum/access/policy` | `{"version": 2, "store": "<fold>"}`: a store, and its fold |
| `_continuum/swarm` | the swarm's ID: the root's |
| elsewhere under `_continuum` | continuum's protocol data, as far as this says |
@@ -128,10 +183,10 @@ document holds nothing but the store's events and continuum's protocol data.
The **genesis change**, the swarm's first, writes the policy, the swarm's ID, its epoch
and the root, and nothing else, built byte for byte from the root: its writer from the
root's ID, time 0, no message. So one root makes one swarm, and a node joining builds
-the genesis change and checks it. A fork's genesis change holds its root's history too,
-each event at its ID, built the same way. Continuum reads the policy as one asking for
-signed changes, as a strict one does, and nothing else of a strict policy: the document
-holds no values but events.
+the genesis change and checks it. A fork's genesis change holds the events its root
+keeps too, each at its ID, built the same way. Continuum reads the policy as one asking
+for signed changes, as a strict one does, and nothing else of a strict policy: the
+document holds no values but events.
### What a change writes
@@ -142,7 +197,7 @@ A change of a swarm holding a store writes nothing but:
same change; taken by the fold at its history, and by the node's own (A node's own);
* **continuum's protocol data**: by a member, its own entry, its own acks, a remake's
record and proposal; by a remake's coordinator only, its decision or its abort; by an
- epoch's first change, epochs and the swarm's ID.
+ epoch's first change, epochs, the swarm's ID and the checkpoint.
Everything else is closed, a write at, within or above it refused: whatever isn't under
`_continuum`, users, bans, logouts, sessions, forgotten nodes, `_continuum/access` with
@@ -164,7 +219,10 @@ event of a change refused for something else it writes, or for its writer, still
the store; one refused by the fold, or by the node's own, takes with it only the events
built on it. So two nodes' documents may differ where the events they hold don't: a
writer's two changes of one number, which part the nodes holding one from those holding
-the other (Where Automerge sets limits), part no events.
+the other (Where Automerge sets limits), part no events. A node moving to a checkpoint
+drops, the same way, every change it holds that carries an event the move refuses. Until
+the next remake, the document still holds what the node forgot, and the node reads none
+of it.
### Members
@@ -181,8 +239,8 @@ operator names, so that a group naming many nodes can't be every node's neighbou
At its API, a node takes no token another node issued, and whoever its operator lets in
may have it put events, whoever signed them, and write its own protocol data;
-`--protocol-writers` names nobody. It shows the events, its heads, and what its fold
-reads from them.
+`--protocol-writers` names nobody. It shows the events, its heads, its checkpoint, and
+what its fold reads from them.
### Remakes
@@ -192,9 +250,10 @@ every swarm: acks tell an honest coordinator when to commit, and bind nobody. A
holding a store takes compaction only, whose snapshot is a function of its base and its
record (its ID, its coordinator): two remakes at one base are two epochs.
-* **The snapshot** holds the events at the base, each at its ID, and of continuum's
+* **The snapshot** holds the store as it is at the base: its checkpoint, where it isn't
+ the root, the events it keeps and those after it, each at its ID; and of continuum's
protocol data what a compaction carries, but the entries of nodes that aren't members
- at the base.
+ at the base. What a checkpoint forgot leaves the document here.
* **A node follows a decision** only where the fold names its coordinator a member, as
the node reads it when it switches. It builds the snapshot itself, from a base it
holds, syncing what it lacks of the base from peers that keep the old epoch, and
@@ -209,15 +268,16 @@ record (its ID, its coordinator): two remakes at one base are two epochs.
on it and puts again what it takes there. Each event is taken again as it was: its
history is in the new epoch too.
* **A node with an empty document**, or one that can't build a remake as no peer keeps
- its base, takes the epoch its peers give it, or the one its operator pins, judging
- every event in it from the root, whose ID is the swarm's, and puts again what it held.
- Where it refuses an event the snapshot holds, it stays where it is. A made-up epoch
- can withhold events from it, and keep it apart from the others, but make it take
- nothing it wouldn't.
+ its base, takes the epoch its peers give it, or the one its operator pins, where the
+ snapshot's checkpoint is one it can build, the root its operator names, or one its
+ operator pins (Pinned checkpoints); it judges every event after it, and puts again
+ what it held. Where it refuses an event the snapshot holds, it stays where it is. A
+ made-up epoch can withhold events from it, and keep it apart from the others, but make
+ it take nothing it wouldn't.
So a remake changes no event a node holds, only which document carries them, which the
fold never sees. A swarm that never remakes holds what one that remakes all the time
-holds; it only grows.
+holds; its document only grows.
### Where Automerge sets limits
@@ -244,8 +304,8 @@ documents stay together.
`Signatures::forks`)*. The events of both reach both sides, each putting them again,
so the store isn't parted, only the documents, which remake apart, until an operator
has its node drop the change it took; no event is lost by it.
-* **History.** The document keeps every operation, which remakes bound; the store keeps
- every event, which nothing bounds.
+* **History.** The document keeps every operation, which remakes bound; the store holds
+ its checkpoint and what came after it, which checkpoints bound.
## Attacks
@@ -265,35 +325,43 @@ crafted changes. *Sim*: a simulation. *Bench*: measured, not judged.
| 8 | Bytes that are none of the fold's events, or a root other than the store's | Refused | unit |
| 9 | A fork's events brought to the store it came from, or the other way | Never taken: their history lacks the root | unit |
| 10 | A writer forked: two changes, one number | The documents part, the events reach both sides, the state is the same | sim |
-| 11 | A snapshot holding other events than its base's | Not followed: a node builds its own and checks it against the epoch | sim |
+| 11 | A snapshot holding another checkpoint, or other events, than its base's | Not followed: a node builds its own and checks it against the epoch | sim |
| 12 | Events written beyond a base, on nodes that switch and on nodes that don't yet | Put again in the new epoch: the same events, the same state | sim |
| 13 | A coordinator shows one of two decisions for an epoch to some nodes, the other to the rest | Each follows the one it holds; a node holding both follows neither; their operators bring them together | sim |
| 14 | A decision or abort written by a node not its coordinator; a decision whose coordinator isn't a member | Refused; none | unit |
-| 15 | A node with an empty document handed a made-up epoch | It judges every event from the root: the epoch withholds, at worst | sim |
-| 16 | A node away while the others switch | It syncs the rest of the base from a peer that keeps the old epoch, builds, and switches; or takes the epoch its peers give it, judging every event | sim |
+| 15 | A node with an empty document handed a made-up epoch | It takes its checkpoint only where it builds it, or its operator named or pinned it, and judges every event after it: the epoch withholds, at worst | sim |
+| 16 | A node away while the others switch | It syncs the rest of the base from a peer that keeps the old epoch, builds, and switches; or takes an epoch as a node with an empty document does | sim |
| 17 | A token from another node | Refused: a node takes only its own | unit |
| 18 | A node writing another node's entry, or under `_continuum` where this doesn't say | Refused | unit |
| 19 | A group naming many nodes, to be every node's neighbours | Each node keeps some among its own group's and those its operator names | sim |
| 20 | A node whose operator had it drop an event is sent it again, in another change | Refused, with everything built on it, until its operator says otherwise | unit |
| 21 | A node no longer a member writes changes at a history where it was one | Taken where valid there: their events count by who signed them, and nobody follows a remake it decides | unit |
-| 22 | Flooding: events, writers, history, remakes | Slow, or out of memory; not wrong | bench |
+| 22 | A checkpoint a node can't build, handed to it by peers | Taken only where its operator pinned it | unit |
+| 23 | An event not above the heads of the checkpoint a node moved to | Refused; a change the node holds that carries one is dropped, its other events put again | unit |
+| 24 | A node away while the others moved to a checkpoint and forgot what came before | It builds the checkpoint from what a peer kept, or takes it where its operator pins it | sim |
+| 25 | Flooding: events, writers, history, remakes | Slow, or out of memory; not wrong | bench |
## Tests
What the tests check of the store, with a fold made for them:
-* **Order.** For every order of a whole set of events that puts each after its
- dependencies (all of them for small sets, seeded ones for larger), the state is the
- same, and so for the orders in which several nodes get them.
+* **Order.** For every order of a set of events that puts each after its dependencies
+ (all of them for small sets, seeded ones for larger), the state is the same, and so
+ for the orders in which several nodes get them.
* **History.** The state at a history is the state of its events added anew, and judging
at it gives the same verdict whatever states the store kept.
* **Refusal.** An event refused is refused with everything built on it, on every node,
whatever the order.
-* **On Automerge.** For any run of events, changes, refusals, drops, remakes, rejoins
- and writers forked, the events a node's document holds are the events it took, and its
- state is that of a store given those events alone.
-* **Bytes.** Fixed vectors, byte for byte: events and their IDs, a genesis change, a
- fork's, a snapshot.
+* **Checkpoints.** Judging any event after a checkpoint gives the verdict judging it
+ with the whole history gives, and reading gives what the whole history reads, but for
+ what the fold lets a checkpoint forget; a node moving to a checkpoint reads the same
+ state whenever it moves, as long as it holds the same events after.
+* **On Automerge.** For any run of events, changes, refusals, drops, checkpoints,
+ remakes, rejoins and writers forked, the events a node's document holds, but for what
+ it forgot, are the events it took, and its state is that of a store given those events
+ alone.
+* **Bytes.** Fixed vectors, byte for byte: events and their IDs, checkpoints, a genesis
+ change, a fork's, a snapshot.
## Roads not taken
@@ -302,5 +370,8 @@ What the tests check of the store, with a fold made for them:
Automerge numbers a writer's changes in a chain, so that a writer's events would build
on each other, or each would need a writer of its own, which costs every node memory
without end.
+* **Every event kept**, so that every node checks everything from the first. Every node
+ would hold what counted no more years ago; a checkpoint its operator pins stands in
+ for what it can't build.
* **Remakes of other kinds** (`replace`, `import`, `strict`). Their snapshot is what
someone gives; a compaction's, every node builds itself from the base.