diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/document/events.rs | 19 | ||||
| -rw-r--r-- | 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<Vec<u8>> { } } +/// The events `change` puts: bytes, each at a key that is its ID. +pub(crate) fn carried(change: &Change) -> Vec<Vec<u8>> { + 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<Id>, + /// The refused changes looked at, of those screening keeps (`look`). + looked: HashSet<ChangeHash>, } /// 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<ChangeHash> = 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<u8>)> { + let held: HashSet<Id> = 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<T>(&self, f: impl FnOnce(&Store<Federation>) -> T) -> Option<T> { 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<tokio::time::Instant> = 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<Change> = 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<tokio::time::Instant>) { + 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::<usize, store::StoreError>(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"), } } @@ -283,6 +425,31 @@ mod tests { } #[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); let first = Spec::first(&[&tv], &[]); |
