diff options
| author | tv <tv@krebsco.de> | 2026-11-19 01:48:57 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-19 03:18:59 +0100 |
| commit | 31d41eb1c902c907a5c6e5608510f96c4b1bc864 (patch) | |
| tree | 5a1a38166c6b22312b4d1eb02adc5dc5f12bce95 /src | |
| parent | 03744437a5ffc36fbb5e973a0ddfd6b91945b212 (diff) | |
store: a new event builds on as many heads as an event may name
A party's client builds on the heads its node shows (`GET /events`), and a node on its
own heads; an event names at most 64 dependencies. With more heads than that, where many
write at once and nothing merges, every event built on them was none.
`Store::building_on` gives the heads, as many as an event may name
(`Fold::DEPENDENCIES`, the federation's 64), the earliest taken first, so that what is
written merges what stayed apart the longest; `GET /events` shows those, and a node
voting by itself builds on them.
Diffstat (limited to 'src')
| -rw-r--r-- | src/api/events.rs | 5 | ||||
| -rw-r--r-- | src/federation/fold.rs | 2 | ||||
| -rw-r--r-- | src/federation/held.rs | 2 | ||||
| -rw-r--r-- | src/federation/store/memory.rs | 31 | ||||
| -rw-r--r-- | src/federation/store/mod.rs | 3 | ||||
| -rw-r--r-- | src/federation/store/testfold.rs | 2 |
6 files changed, 40 insertions, 5 deletions
diff --git a/src/api/events.rs b/src/api/events.rs index 214882a..b13de63 100644 --- a/src/api/events.rs +++ b/src/api/events.rs @@ -81,7 +81,8 @@ fn why(refusal: &Refusal) -> String { } } -/// `GET /events`: the store's ID, its checkpoint's, its heads, how many events it took +/// `GET /events`: the store's ID, its checkpoint's, its heads, as many as an event may +/// name, what a new event builds on (`Store::building_on`), how many events it took /// after its checkpoint, the event it stopped at, if any, the node's party, and whether /// the node votes for it by itself. async fn summary(State(state): State<AppState>) -> Response { @@ -94,7 +95,7 @@ async fn summary(State(state): State<AppState>) -> Response { json!({ "store": store.id().to_string(), "checkpoint": Id::of(store.checkpoint()).to_string(), - "heads": ids(store.heads()), + "heads": ids(store.building_on()), "taken": store.taken().len(), "stopped": stopped, "party": party, diff --git a/src/federation/fold.rs b/src/federation/fold.rs index 7986a13..46f56e1 100644 --- a/src/federation/fold.rs +++ b/src/federation/fold.rs @@ -626,6 +626,8 @@ impl Fold for Federation { const LARGEST: usize = event::LARGEST; + const DEPENDENCIES: usize = event::DEPENDENCIES; + fn dependencies(event: &[u8]) -> Option<Vec<Id>> { Event::read(event).map(|event| event.deps().to_vec()) } diff --git a/src/federation/held.rs b/src/federation/held.rs index 93e2505..8d9d095 100644 --- a/src/federation/held.rs +++ b/src/federation/held.rs @@ -728,7 +728,7 @@ impl Holding { return Ok(Vec::new()); } let current = store.state().current().clone(); - let heads = store.heads(); + let heads = store.building_on(); let line = crate::access::sshsig::PublicKey(voter.key.verifying_key().to_bytes()).line(); let mut record = record.clone(); let mut signed = Vec::new(); diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs index 8493735..05479e3 100644 --- a/src/federation/store/memory.rs +++ b/src/federation/store/memory.rs @@ -263,8 +263,8 @@ impl<F: Fold> Store<F> { ordered } - /// What a new event builds on: the events nothing else held builds on, or the - /// checkpoint's heads where nothing came after it. + /// The heads of what the store holds: the events nothing else held builds on, in the + /// order taken, or the checkpoint's heads where nothing came after it. pub(crate) fn heads(&self) -> Vec<Id> { let built_on: HashSet<&Id> = self .events @@ -284,6 +284,15 @@ impl<F: Fold> Store<F> { } } + /// What a new event builds on: its heads, as many as an event may name + /// (`Fold::DEPENDENCIES`), the earliest taken first, so that what is written merges + /// what stayed apart the longest. + pub(crate) fn building_on(&self) -> Vec<Id> { + let mut heads = self.heads(); + heads.truncate(F::DEPENDENCIES); + heads + } + /// Offers an event: it is taken once the store holds its dependencies, where the fold /// takes it at its history. pub(crate) fn offer(&mut self, bytes: Vec<u8>) -> Offered { @@ -1139,6 +1148,24 @@ mod tests { assert!(store.drop_taken(&[lock]).is_err()); } + /// A new event builds on as many heads as an event may name, the earliest taken first: + /// a later one merges the rest. + #[test] + fn a_new_event_builds_on_the_earliest_heads_an_event_may_name() { + let mut store = store(); + let root = store.id(); + let apart: Vec<Id> = (0..=TestFold::DEPENDENCIES) + .map(|n| taken(store.offer(testfold::put(&[root], &format!("k{n}"), "1")))) + .collect(); + assert_eq!(store.heads(), apart); + assert_eq!(store.building_on(), apart[..TestFold::DEPENDENCIES]); + let merged = taken(store.offer(testfold::put(&store.building_on(), "m", "1"))); + assert_eq!( + store.building_on(), + vec![apart[TestFold::DEPENDENCIES], merged] + ); + } + /// Heads leave out what is neither among them, in their history, nor above them. #[test] fn heads_leave_out_what_is_beside_them() { diff --git a/src/federation/store/mod.rs b/src/federation/store/mod.rs index c80f5b8..d2028da 100644 --- a/src/federation/store/mod.rs +++ b/src/federation/store/mod.rs @@ -79,6 +79,9 @@ pub(crate) trait Fold { /// The most bytes an event may have: larger ones are none. const LARGEST: usize; + /// The most events an event may build on: what a new event builds on is no more. + const DEPENDENCIES: usize = usize::MAX; + /// What the event builds on; `None` where its bytes are none of this fold's events. fn dependencies(event: &[u8]) -> Option<Vec<Id>>; diff --git a/src/federation/store/testfold.rs b/src/federation/store/testfold.rs index 17e039b..6dd1460 100644 --- a/src/federation/store/testfold.rs +++ b/src/federation/store/testfold.rs @@ -295,6 +295,8 @@ impl Fold for TestFold { const LARGEST: usize = 64 * 1024; + const DEPENDENCIES: usize = 8; + fn dependencies(event: &[u8]) -> Option<Vec<Id>> { decode(event).map(|(deps, _)| deps) } |
