summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-19 01:48:57 +0000
committertv <tv@krebsco.de>2026-11-19 03:18:59 +0100
commit31d41eb1c902c907a5c6e5608510f96c4b1bc864 (patch)
tree5a1a38166c6b22312b4d1eb02adc5dc5f12bce95 /src
parent03744437a5ffc36fbb5e973a0ddfd6b91945b212 (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.rs5
-rw-r--r--src/federation/fold.rs2
-rw-r--r--src/federation/held.rs2
-rw-r--r--src/federation/store/memory.rs31
-rw-r--r--src/federation/store/mod.rs3
-rw-r--r--src/federation/store/testfold.rs2
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)
}