summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-19 03:54:54 +0000
committertv <tv@krebsco.de>2026-11-19 05:12:07 +0100
commit5611555bd31e5b05bcee6c6e4450adeffd2e820b (patch)
tree5169171f4f67e3893c96dbddeff13c2711af2332
parent6c6f978189eafa15add0df865f713dc946dfc5cb (diff)
held: a node merges its store's heads beyond what an event may name
Past 64 heads, no event is above them all, and what is written builds on the earliest 64 alone: where nobody writes, heads apart stay apart, and a checkpoint naming them is never written. Under a revision with merge events, a node its party lists signs merge events with its node key where its store holds more heads than an event may name, each on as many as it may, the earliest taken first, until no more are left (`Holding::merge`). The worker does so a random wait after the heads first were too many, as it puts again what the document lacks, so that of the members few do at once. `federation.md` says so under Nodes, and the guides say what a node writes by itself and what its log says.
-rw-r--r--docs/federation.md5
-rw-r--r--docs/guides/federation/running-a-node.md4
-rw-r--r--docs/guides/federation/watching.md5
-rw-r--r--src/federation/held.rs136
-rw-r--r--src/identity.rs5
5 files changed, 148 insertions, 7 deletions
diff --git a/docs/federation.md b/docs/federation.md
index ecc3f21..d10a220 100644
--- a/docs/federation.md
+++ b/docs/federation.md
@@ -595,7 +595,10 @@ puts whatever events it is given, its party's and others' alike: what counts is
an event, not which node put it. So a party without nodes of its own writes through any
node that takes its events. Under a revision with merge events, a node its party lists
signs merge events with its own key ([Events](#events)): they count for nothing, and only
-gather what they build on into the history of what builds on them.
+gather what they build on into the history of what builds on them. It does so by itself
+where its store holds more heads than an event may name, a random wait after it first
+did, so that of the members few do at once: each on as many as an event may name, the
+earliest taken first, until no more are left.
### Forks
diff --git a/docs/guides/federation/running-a-node.md b/docs/guides/federation/running-a-node.md
index 6444bbd..94781d4 100644
--- a/docs/guides/federation/running-a-node.md
+++ b/docs/guides/federation/running-a-node.md
@@ -109,6 +109,10 @@ it takes the checkpoint only where its operator pins it. Pin it, and restart the
* **Events its document lacks**, that its store would take and that it has: after a
remake, a rejoin, or a change of another node it refused (`Put again events the
document lacked`).
+* **Merge events**, under a revision with them, where its party lists it and its store
+ holds more heads than an event may name (64): signed with its node key, a random wait
+ after there first were (`Merged heads beyond what an event may name`). They count for
+ nothing, and gather the heads apart, so that what is written after builds on them all.
* **Its own protocol data**: its entry, its acks of remakes, and the remakes it
coordinates. Remakes are compactions only, acked by the members
([`remakes.md`](../../remakes.md)).
diff --git a/docs/guides/federation/watching.md b/docs/guides/federation/watching.md
index a54dd7f..da4a93f 100644
--- a/docs/guides/federation/watching.md
+++ b/docs/guides/federation/watching.md
@@ -55,9 +55,10 @@ At warn or error:
read-only disk;
* `Couldn't vote by itself`, `Voting by itself, without its party's record: votes none`;
* `Couldn't put what it signed for its party: put again later`, `Couldn't write a version
- that passed: put again later`, `Couldn't put again events the document lacks`;
+ that passed: put again later`, `Couldn't put again events the document lacks`,
+ `Couldn't put a merge event: put again later`;
* `Dropped events, as this node's operator says`: whoever may use the node's API did it.
At info, worth knowing: `The store's members, as it reads now`, `Writing a version that
passed`, `Voting for its party`, `Proposing a checkpoint for its party`, `This node is a
-member of its store`.
+member of its store`, `Merged heads beyond what an event may name`.
diff --git a/src/federation/held.rs b/src/federation/held.rs
index 8d9d095..6e00e51 100644
--- a/src/federation/held.rs
+++ b/src/federation/held.rs
@@ -32,6 +32,7 @@ use tracing::{error, info, warn};
use super::client::Record;
use super::event::{self, Does, Event, Signed};
use super::fold::Federation;
+use super::revision::Feature;
use super::store::memory::{Built, Offered, Store};
use super::store::{Fold, Id, Refused};
use super::version::Version;
@@ -788,6 +789,63 @@ impl Holding {
Ok(signed)
}
+ /// Whether its store holds more heads than an event may name, and the node, `key`'s,
+ /// merges them: under a revision with merge events, its party listing it, its store not
+ /// stopped.
+ pub(crate) fn apart(&self, key: &crate::identity::NodeKey) -> bool {
+ let inner = self.inner.lock_or_recover();
+ inner.store.as_ref().is_some_and(|store| {
+ self.merges_in(store, key) && store.heads().len() > event::DEPENDENCIES
+ })
+ }
+
+ /// Whether the node, `key`'s, merges in `store`: under a revision with merge events,
+ /// its party listing it, the store not stopped.
+ fn merges_in(&self, store: &Store<Federation>, key: &crate::identity::NodeKey) -> bool {
+ let Some(party) = &self.party else {
+ return false;
+ };
+ let state = store.state();
+ let current = state.current();
+ store.stopped().is_none()
+ && current.revision.has(Feature::MergeEvents)
+ && state.nodes_of(party, current).contains(&key.id())
+ }
+
+ /// The merge events the node signs with `key` until its store holds no more heads than
+ /// an event may name, each on as many as it may (`Store::building_on`), offered to its
+ /// store: those it takes, to put into the document. None where it doesn't merge
+ /// (`apart`).
+ pub(crate) fn merge(&self, key: &crate::identity::NodeKey) -> Vec<Vec<u8>> {
+ let mut inner = self.inner.lock_or_recover();
+ let inner = &mut *inner;
+ let (Some(store), Some(party)) = (inner.store.as_mut(), &self.party) else {
+ return Vec::new();
+ };
+ if !self.merges_in(store, key) {
+ return Vec::new();
+ }
+ let line = crate::access::sshsig::PublicKey(key.public()).line();
+ let mut merged = Vec::new();
+ while store.heads().len() > event::DEPENDENCIES {
+ let deps = store.building_on();
+ let bytes = event::signed(key.signing(), party, &line, &deps, event::merge());
+ let Offered::Taken(_) = store.offer(bytes.clone()) else {
+ break;
+ };
+ merged.push(bytes);
+ }
+ if !merged.is_empty() {
+ info!(
+ merged = merged.len(),
+ heads = store.heads().len(),
+ "Merged heads beyond what an event may name"
+ );
+ self.settle(inner);
+ }
+ merged
+ }
+
/// The version events writing what passed on the current version, as its store reads
/// now, offered to it: those it takes, to put into the document. A node writes a version
/// as soon as it holds it passed (`docs/federation.md`, Changing the policy).
@@ -952,10 +1010,13 @@ fn found(pin: &Id, root: &[u8], events: &BTreeMap<Id, Vec<u8>>) -> Option<Built>
/// Reads the store from the document whenever it changes, and from the changes the node
/// refused now and then; writes what passed and what it signs voting by itself; puts again
-/// what the document lacks, a random wait after it first lacked it.
+/// what the document lacks, a random wait after it first lacked it; and merges the store's
+/// heads where they are more than an event may name, a random wait after they first were,
+/// so that of the members few do at once.
pub(crate) async fn run_worker(state: crate::state::AppState) {
let mut changed = state.change_tx.subscribe();
let mut due: Option<tokio::time::Instant> = None;
+ let mut merge_due: Option<tokio::time::Instant> = None;
// Whether this node is a member of its store, as last said.
let mut listed: Option<bool> = None;
let mut looks = tokio::time::interval(LOOK);
@@ -974,6 +1035,7 @@ pub(crate) async fn run_worker(state: crate::state::AppState) {
} else {
Vec::new()
};
+ let key = state.node_key.clone();
let read = tokio::task::spawn_blocking(move || {
// Read from the document under its lock; taken without it. A rejoin's
// document isn't the node's until it follows the epoch (`Holding::follows`)
@@ -982,7 +1044,7 @@ pub(crate) async fn run_worker(state: crate::state::AppState) {
let unread = {
let replica = doc.blocking_read();
if !replica.writable {
- return (false, Vec::new(), Vec::new());
+ return (false, false, Vec::new(), Vec::new());
}
holding.unread(&replica.doc, replica.epoch_seq)
};
@@ -994,13 +1056,14 @@ pub(crate) async fn run_worker(state: crate::state::AppState) {
let passed = holding.passed();
(
!holding.lacking(&doc.blocking_read().doc).is_empty(),
+ key.is_some_and(|key| holding.apart(&key)),
signed,
passed,
)
});
- let (lacking, signed, passed) = read.await.unwrap_or_else(|error| {
+ let (lacking, apart, signed, passed) = read.await.unwrap_or_else(|error| {
error!(error = %error, "Reading the store from the document failed");
- (false, Vec::new(), Vec::new())
+ (false, false, Vec::new(), Vec::new())
});
for bytes in signed {
if let Err(error) = write(&state, None, bytes).await {
@@ -1033,6 +1096,11 @@ pub(crate) async fn run_worker(state: crate::state::AppState) {
Some(due) => Some(due),
None => Some(tokio::time::Instant::now() + wait()),
};
+ merge_due = match merge_due {
+ _ if !apart => None,
+ Some(due) => Some(due),
+ None => Some(tokio::time::Instant::now() + wait()),
+ };
tokio::select! {
changed = changed.changed() => {
if changed.is_err() {
@@ -1043,6 +1111,20 @@ pub(crate) async fn run_worker(state: crate::state::AppState) {
put_again(&state).await;
due = None;
}
+ () = sleep_until(merge_due), if merge_due.is_some() => {
+ merge_due = None;
+ let (holding, key) = (Arc::clone(&state.holding), state.node_key.clone());
+ let merged = tokio::task::spawn_blocking(move || {
+ key.map_or_else(Vec::new, |key| holding.merge(&key))
+ })
+ .await
+ .unwrap_or_default();
+ for bytes in merged {
+ if let Err(error) = write(&state, None, bytes).await {
+ warn!(error = %error, "Couldn't put a merge event: put again later");
+ }
+ }
+ }
_ = looks.tick() => look = true,
}
}
@@ -1951,6 +2033,52 @@ mod tests {
assert!(holding.vote_by_hand(next.hash(), true).is_ok());
}
+ /// A node its party lists merges its store's heads where they are more than an event
+ /// may name, under a revision with merge events: one merge event on the earliest 64,
+ /// beside the one left. Under the base revision, or listed by no party, it doesn't.
+ #[test]
+ fn a_node_merges_heads_beyond_what_an_event_may_name() {
+ let holding_of = |first: &Spec| {
+ let root = first.root();
+ let tv = Party::new("tv", 1);
+ let mut doc = events::started(Federation::NAME, &root, &[]).unwrap();
+ for n in 0..=event::DEPENDENCIES {
+ let write = tv.write(
+ &[Id::of(&root)],
+ &format!("home/tv/k{n}"),
+ harness::str("1"),
+ );
+ put(&mut doc, &write);
+ }
+ let holding =
+ Holding::open(None, Arc::new(Files::default()), None, Some("tv".into())).unwrap();
+ read(&holding, &doc, 0);
+ holding
+ };
+ let parties = [Party::new("tv", 1), Party::new("lass", 2)];
+ let mut first = Spec::first(&[&parties[0], &parties[1]], &[]);
+ // tv lists node 0 (`Spec::first`), whose key this is (`harness::node_key`).
+ let listed = crate::identity::NodeKey::from_seed([128; 32]);
+ let other = crate::identity::NodeKey::from_seed([129; 32]);
+ let base = holding_of(&first);
+ assert!(!base.apart(&listed));
+ assert!(base.merge(&listed).is_empty());
+ first.revision = Feature::MergeEvents.revision();
+ let holding = holding_of(&first);
+ assert!(!holding.apart(&other));
+ assert!(holding.merge(&other).is_empty());
+ assert!(holding.apart(&listed));
+ let merged = holding.merge(&listed);
+ assert_eq!(merged.len(), 1);
+ assert_eq!(
+ holding.with(|store| store.heads().len()),
+ Some(2),
+ "the one left, and the merge event"
+ );
+ assert!(!holding.apart(&listed));
+ assert!(holding.merge(&listed).is_empty());
+ }
+
/// Row 70 (`docs/federation.md`): a checkpoint's version proposed again, by an event
/// beside its heads. A node backs it all the same, as a proposal lapses with the move,
/// and votes on the event proposing it above the heads alone: a version event written
diff --git a/src/identity.rs b/src/identity.rs
index 23c4f0f..6021a61 100644
--- a/src/identity.rs
+++ b/src/identity.rs
@@ -68,6 +68,11 @@ impl NodeKey {
self.signing.verifying_key().to_bytes()
}
+ /// The key itself: for what signs as SSH does (`federation::event::signed`).
+ pub(crate) fn signing(&self) -> &SigningKey {
+ &self.signing
+ }
+
pub(crate) fn sign(&self, message: &[u8]) -> [u8; 64] {
use ed25519_dalek::Signer;
self.signing.sign(message).to_bytes()