From ff97d657d76508af290a29ed11e478575317c7df Mon Sep 17 00:00:00 2001 From: tv Date: Mon, 16 Nov 2026 19:58:26 +0000 Subject: federation: events put again A node puts again, in changes of its own, every event its store holds that its document lacks (`docs/store.md`, What the store takes from the document): one it took from the document it left, at a drop or a rejoin, or from a change it refused, whose events the store is offered as from anywhere (`Holding::look`, every few seconds, of the changes screening keeps). It puts each after its dependencies, what the checkpoint keeps first, then what the store took after it in the order taken, up to 1 MiB of events a change, once a wait of its own has passed: random, between one and ten seconds after the document first lacked them, so that not every node puts the same, and none another node put meanwhile, as it looks again when it writes. --- src/document/events.rs | 19 +++++- src/federation/held.rs | 181 +++++++++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 192 insertions(+), 8 deletions(-) diff --git a/src/document/events.rs b/src/document/events.rs index ee16de7..687079e 100644 --- a/src/document/events.rs +++ b/src/document/events.rs @@ -8,7 +8,7 @@ //! (`store::write_path`). Its writer is the first 16 bytes of the root's ID, its time 0, //! and it has no message. -use automerge::legacy::OpType; +use automerge::legacy::{Key, OpType}; use automerge::transaction::CommitOptions; use automerge::{ObjId, ObjType, ScalarValue, Value}; use serde_json::Value as JsonValue; @@ -51,6 +51,22 @@ pub(crate) fn bytes(doc: &impl ReadDoc, id: &Id) -> Option> { } } +/// The events `change` puts: bytes, each at a key that is its ID. +pub(crate) fn carried(change: &Change) -> Vec> { + super::changes::decode(change) + .operations + .into_iter() + .filter_map(|op| match (op.key, op.action) { + (Key::Map(key), OpType::Put(ScalarValue::Bytes(bytes))) + if Id::of(&bytes).to_string() == key.as_str() => + { + Some(bytes) + } + _ => None, + }) + .collect() +} + /// The policy of a swarm holding a store of the fold `fold`. pub(crate) fn policy(fold: &str) -> JsonValue { serde_json::json!({"version": 2, "store": fold}) @@ -159,6 +175,7 @@ mod tests { ); assert_eq!(ids(&doc), vec![id]); assert_eq!(bytes(&doc, &id).as_deref(), Some(ROOT)); + assert_eq!(carried(&genesis("federation", ROOT)), vec![ROOT.to_vec()]); } #[test] diff --git a/src/federation/held.rs b/src/federation/held.rs index 28f4ca5..5c0d8c8 100644 --- a/src/federation/held.rs +++ b/src/federation/held.rs @@ -8,11 +8,19 @@ //! A worker reads the events the document holds that it hasn't read yet, whenever the //! document changes (`run_worker`). Which change put an event, and how often, changes //! nothing; nor does another document (a drop, a rejoin), whose events it reads as it -//! comes, the store going on. +//! comes, the store going on. It offers the store the events carried by changes the node +//! refused, too (`look`). +//! +//! The node puts again, in changes of its own, every event its store holds that its +//! document lacks: one it took from a change it refused, or from the document it left. +//! It puts each after its dependencies, in the order the store took them, once a wait of +//! its own has passed, random, so that not every node puts the same, and none another +//! node put meanwhile (`put_again`). use std::collections::{BTreeMap, BTreeSet, HashSet}; use std::path::PathBuf; use std::sync::{Arc, Mutex}; +use std::time::Duration; use anyhow::{Context, Result, bail}; use serde::{Deserialize, Serialize}; @@ -21,10 +29,19 @@ use tracing::{error, info, warn}; use super::fold::Federation; use super::store::Id; use super::store::memory::{Offered, Store}; -use crate::document::{ReadDoc, events, meta, store}; +use crate::document::{Change, ChangeHash, ReadDoc, ScalarValue, events, meta, store}; use crate::files::{FileKind, Files}; use crate::locks::MutexExt; +/// How long a node waits before it puts again what its document lacks, at least and at +/// most: random in between, so that not every node puts the same. +const PUT_WAIT: (Duration, Duration) = (Duration::from_secs(1), Duration::from_secs(10)); +/// How often the worker looks at the changes the node refused, for the events they carry. +const LOOK: Duration = Duration::from_secs(5); +/// The bytes of events a change puts again, at most: the next event begins the next +/// change. +const PUT_BYTES: usize = 1024 * 1024; + /// What a node keeps of its own of its store across restarts, as its file holds it: the /// events it refused by what it took before, and those its operator had it drop, by ID. #[derive(Clone, Debug, Default, PartialEq, Eq, Serialize, Deserialize)] @@ -74,6 +91,8 @@ struct Inner { kept: Kept, /// The root that is none, logged once. none: Option, + /// The refused changes looked at, of those screening keeps (`look`). + looked: HashSet, } /// What a document holds that its store wasn't offered from it. @@ -216,19 +235,80 @@ impl Holding { } } + /// Offers the store the events carried by `refused`, changes the node refused, that it + /// didn't look at before: it takes them as from anywhere, and the node puts them again + /// (`lacking`). + pub(crate) fn look(&self, refused: &[Change]) { + let mut inner = self.inner.lock_or_recover(); + let inner = &mut *inner; + let Some(store) = inner.store.as_mut() else { + return; + }; + let now: HashSet = refused.iter().map(Change::hash).collect(); + inner.looked.retain(|hash| now.contains(hash)); + for change in refused { + if !inner.looked.insert(change.hash()) { + continue; + } + for bytes in events::carried(change) { + if let Offered::Taken(ids) = store.offer(bytes) { + info!(change = %change.hash(), taken = ids.len(), "Took events a refused change carried"); + } + } + } + } + + /// The events the store holds that `doc` lacks, each after its dependencies: what its + /// checkpoint keeps, then what it took after it, in that order. + pub(crate) fn lacking(&self, doc: &impl ReadDoc) -> Vec<(Id, Vec)> { + let held: HashSet = events::ids(doc).into_iter().collect(); + self.with(|store| { + store + .kept() + .into_iter() + .map(|bytes| (Id::of(&bytes), bytes)) + .chain( + store + .taken() + .iter() + .filter_map(|id| Some((*id, store.get(id)?.to_vec()))), + ) + .filter(|(id, _)| !held.contains(id)) + .collect() + }) + .unwrap_or_default() + } + /// `f` of the store, where the node holds one. pub(crate) fn with(&self, f: impl FnOnce(&Store) -> T) -> Option { self.inner.lock_or_recover().store.as_ref().map(f) } } -/// Reads the store from the document whenever it changes. +/// Reads the store from the document whenever it changes, and from the changes the node +/// refused now and then; puts again what the document lacks, a random wait after it +/// first lacked it. pub(crate) async fn run_worker(state: crate::state::AppState) { let mut changed = state.change_tx.subscribe(); + let mut due: Option = None; + let mut looks = tokio::time::interval(LOOK); + looks.set_missed_tick_behavior(tokio::time::MissedTickBehavior::Delay); + let mut look = false; loop { let holding = Arc::clone(&state.holding); let doc = Arc::clone(&state.doc); + let refused: Vec = if std::mem::take(&mut look) && holding.with(|_| ()).is_some() { + state + .screening + .lock_or_recover() + .refused() + .map(|refused| refused.change.clone()) + .collect() + } else { + Vec::new() + }; let read = tokio::task::spawn_blocking(move || { + holding.look(&refused); // Read from the document under its lock; taken without it. let unread = { let replica = doc.blocking_read(); @@ -237,13 +317,75 @@ pub(crate) async fn run_worker(state: crate::state::AppState) { if let Some(unread) = unread { holding.read(unread); } + !holding.lacking(&doc.blocking_read().doc).is_empty() }); - if let Err(error) = read.await { + let lacking = read.await.unwrap_or_else(|error| { error!(error = %error, "Reading the store from the document failed"); + false + }); + due = match due { + _ if !lacking => None, + Some(due) => Some(due), + None => Some(tokio::time::Instant::now() + wait()), + }; + tokio::select! { + changed = changed.changed() => { + if changed.is_err() { + return; + } + } + () = sleep_until(due), if due.is_some() => { + put_again(&state).await; + due = None; + } + _ = looks.tick() => look = true, } - if changed.changed().await.is_err() { - return; - } + } +} + +async fn sleep_until(due: Option) { + if let Some(due) = due { + tokio::time::sleep_until(due).await; + } +} + +/// A wait within `PUT_WAIT`, random. +fn wait() -> Duration { + let mut bytes = [0u8; 8]; + // Without randomness, the longest: the others put first. + let random = getrandom::fill(&mut bytes).map_or(u64::MAX, |()| u64::from_le_bytes(bytes)); + let (least, most) = PUT_WAIT; + least + (most - least).mul_f64(random as f64 / u64::MAX as f64) +} + +/// Puts again, in a change of its own, the events the store holds that the document +/// lacks still, each after its dependencies, up to `PUT_BYTES` of them. +async fn put_again(state: &crate::state::AppState) { + let holding = Arc::clone(&state.holding); + let put = state + .mutate_doc(move |doc| { + let mut bytes_put = 0; + let mut put = 0; + for (id, bytes) in holding.lacking(doc) { + if bytes_put > 0 && bytes_put + bytes.len() > PUT_BYTES { + break; + } + bytes_put += bytes.len(); + store::write_val_path( + doc, + &events::event(&id), + &crate::document::typed::Val::Scalar(ScalarValue::Bytes(bytes)), + store::Writing::sticky(Default::default()), + )?; + put += 1; + } + Ok::(put) + }) + .await; + match put { + Ok(0) => {} + Ok(put) => info!(put, "Put again events the document lacked"), + Err(error) => warn!(error = %error, "Couldn't put again events the document lacks"), } } @@ -282,6 +424,31 @@ mod tests { holding.read(holding.unread(doc, epoch_seq).unwrap()); } + #[test] + fn a_node_puts_again_what_its_document_lacks() { + let tv = Party::new("tv", 1); + let first = Spec::first(&[&tv], &[]); + let root = root_of(&first); + let write = tv.write(&[Id::of(&root)], "home/tv/x", harness::str("1")); + let on = tv.write(&[Id::of(&write)], "home/tv/x", harness::str("2")); + let mut left = events::started(Federation::NAME, &root).unwrap(); + put(&mut left, &write); + let holding = Holding::default(); + read(&holding, &left, 0); + // Another document, without it; and a refused change carrying what builds on it. + let doc = events::started(Federation::NAME, &root).unwrap(); + let mut elsewhere = left.fork(); + put(&mut elsewhere, &on); + let carrying = elsewhere.get_last_local_change().unwrap().clone(); + holding.look(&[carrying]); + read(&holding, &doc, 1); + assert_eq!( + holding.lacking(&doc), + vec![(Id::of(&write), write.clone()), (Id::of(&on), on.clone())] + ); + assert_eq!(holding.lacking(&elsewhere), Vec::new()); + } + #[test] fn the_store_takes_the_events_the_document_holds() { let tv = Party::new("tv", 1); -- cgit v1.3.1