//! The store a node of a swarm holding one holds (`docs/store.md`, What the store takes //! from the document): read from its document, each event taken as the store would take //! it from anywhere, and by the node's own: what it refused by what it took before, and //! what its operator had it drop, which it keeps in a file of its own (`--store-file`). //! It keeps nothing else of the store across a restart: whenever it starts, it reads the //! store anew from its document, from the root, or from a checkpoint its operator pins //! (`--store-checkpoint`), found in the document (`found`): once its store moved, a node //! reading from the root could take what was grown anew from it since, by keys of //! versions long replaced. //! //! 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. 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, RwLock}; use std::time::Duration; use anyhow::{Context, Result, bail}; use serde::{Deserialize, Serialize}; use tracing::{error, info, warn}; use super::event::{Does, Event, Signed}; use super::fold::Federation; use super::store::memory::{Built, Offered, Store}; use super::store::{Fold, Id}; use super::version::Version; use crate::document::{Change, ChangeHash, ReadDoc, ScalarValue, events, meta, store}; use crate::files::{FileKind, Files}; use crate::locks::{MutexExt, RwLockExt}; /// 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)] #[serde(rename_all = "camelCase", deny_unknown_fields)] struct Kept { #[serde(default)] refused: BTreeSet, #[serde(default)] dropped: BTreeSet, } impl Kept { fn of(own: &[Id], dropped: &[Id]) -> Self { Kept { refused: own.iter().map(Id::to_string).collect(), dropped: dropped.iter().map(Id::to_string).collect(), } } /// The IDs it holds: what was refused, and what dropped. fn ids(&self) -> Option<(Vec, Vec)> { let ids = |set: &BTreeSet| { set.iter() .map(|id| Id::from_hex(id)) .collect::>>() }; Some((ids(&self.refused)?, ids(&self.dropped)?)) } } /// The store a node holds, if its swarm holds one, the file it keeps its own in, the /// checkpoint its operator pins, and the party its operator says it is of. #[derive(Default)] pub(crate) struct Holding { file: Option<(PathBuf, Arc)>, pin: Option, party: Option, /// The members the store names, each with its party, as it reads now: apart from the /// store, so that whoever asks doesn't wait while the store takes events. members: RwLock>>, // A std mutex: never held while waiting for the document. inner: Mutex, } #[derive(Default)] struct Inner { /// None until a document holding a store holds its root. store: Option>, /// The document read from (`Replica::epoch_seq`), and its events read. epoch_seq: Option, read: HashSet, /// What the file holds, or will once written. kept: Kept, /// The root that is none, logged once. none: Option, /// The pinned checkpoint not found in the document, logged once. unfound: bool, /// The refused changes looked at, of those screening keeps (`look`). looked: HashSet, } /// What a document holds that its store wasn't offered from it. pub(crate) struct Unread { epoch_seq: u32, /// The root, where the store isn't started yet. root: Option>, events: BTreeMap>, } impl Holding { /// Keeping the node's own in the file at `path`, if any, which holds what it kept /// before: a missing file nothing. One that doesn't read is an error: the node would /// take what it refused. Its store starts from the checkpoint `pin`, if any; the node /// is of `party`. pub(crate) fn open( path: Option, files: Arc, pin: Option, party: Option, ) -> Result { let Some(path) = path else { return Ok(Holding { pin, party, ..Holding::default() }); }; let kept = match files .read(FileKind::Store, &path) .with_context(|| format!("Reading the store file {}", path.display()))? { None => Kept::default(), Some(bytes) => match serde_json::from_slice::(&bytes) { Ok(kept) if kept.ids().is_some() => kept, _ => bail!( "The store file {} doesn't read: move it away only knowing the node may then take what it refused", path.display() ), }, }; Ok(Holding { file: Some((path, files)), pin, party, members: RwLock::default(), inner: Mutex::new(Inner { kept, ..Inner::default() }), }) } /// What `doc` (the document `epoch_seq`) holds that the store wasn't offered from it, /// if it holds a store: everything, from another document. pub(crate) fn unread(&self, doc: &impl ReadDoc, epoch_seq: u32) -> Option { if !matches!( crate::access::policy::of(doc), crate::access::policy::Policy::Store(_) ) { return None; } let swarm = match store::read_plain(doc, &meta::path(&[meta::SWARM])) { Ok(Some(serde_json::Value::String(id))) => Id::from_hex(&id)?, _ => return None, }; let inner = self.inner.lock_or_recover(); let same = inner.epoch_seq == Some(epoch_seq); let events = events::ids(doc) .into_iter() .filter(|id| !same || !inner.read.contains(id)) .filter_map(|id| Some((id, events::bytes(doc, &id)?))) .collect(); let root = match &inner.store { None => Some(events::bytes(doc, &swarm)?), Some(_) => None, }; Some(Unread { epoch_seq, root, events, }) } /// Offers the store what was `unread`: started from the root first, by what the node /// kept of its own. What it refuses of its own from then on, it keeps. pub(crate) fn read(&self, unread: Unread) { let mut inner = self.inner.lock_or_recover(); let inner = &mut *inner; if inner.epoch_seq != Some(unread.epoch_seq) { inner.epoch_seq = Some(unread.epoch_seq); inner.read.clear(); } if inner.store.is_none() { let Some(root) = unread.root else { return; }; let id = Id::of(&root); let (own, dropped) = inner.kept.ids().unwrap_or_default(); let started = match self.pin { None => Store::new(root, Vec::new()), Some(pin) => match found(&pin, &root, &unread.events) { Some((checkpoint, kept)) => { info!(store = %id, checkpoint = %pin, "Found the pinned checkpoint in the document"); Store::pinned(id, checkpoint, kept.into_values().collect()) } None => { if !std::mem::replace(&mut inner.unfound, true) { warn!(store = %id, checkpoint = %pin, "The pinned checkpoint isn't in the document (yet): holding no store until it is"); } return; } }, }; match started { Ok(store) => { info!(store = %id, refused = own.len(), dropped = dropped.len(), "Reading the store from the document"); inner.store = Some(store.refusing(&own, &dropped)); } Err(why) => { if inner.none.replace(id) != Some(id) { error!(store = %id, why = %why.0, "The document's root is no store's: not reading it"); } return; } } } let store = inner.store.as_mut().expect("started"); let (mut taken, mut refused) = (0, 0); for (id, bytes) in unread.events { inner.read.insert(id); match store.offer(bytes) { Offered::Taken(ids) => taken += ids.len(), Offered::Refused(why) => { refused += 1; info!(event = %id, why = ?why, "The store refuses an event the document holds"); } Offered::Held | Offered::Waiting => {} } } if taken > 0 || refused > 0 { info!(taken, refused, "Read events from the document"); } let (own, dropped) = store.own(); let kept = Kept::of(&own, &dropped); if kept != inner.kept { for id in kept.refused.difference(&inner.kept.refused) { warn!(event = %id, "Refused an event its history takes, by what this node took before: kept so"); } inner.kept = kept; self.keep(&inner.kept); } let members: BTreeSet<(String, String)> = store.state().members().into_iter().collect(); let mut known = self.members.write_or_recover(); if known.as_ref() != Some(&members) { info!( members = members.len(), "The store's members, as it reads now" ); *known = Some(members); } } /// Writes what the node keeps of its own to its file, if it has one. fn keep(&self, kept: &Kept) { let Some((path, files)) = &self.file else { return; }; let written = serde_json::to_vec_pretty(kept) .map_err(std::io::Error::from) .and_then(|mut bytes| { bytes.push(b'\n'); files.write_atomic(FileKind::Store, path, &bytes) }); if let Err(error) = written { error!(path = %path.display(), error = %error, "Couldn't write the store file: a restart may take what this node refused"); } } /// 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() } /// Whether `node`, of `party`, is a member of the store as it reads now: one the fold /// names with that party. None while the node holds no store, and can't tell. pub(crate) fn member(&self, node: &str, party: Option<&str>) -> Option { let members = self.members.read_or_recover(); let members = members.as_ref()?; Some(party.is_some_and(|party| members.contains(&(node.to_owned(), party.to_owned())))) } /// The members the store names, each with its party, while the node holds a store. pub(crate) fn members(&self) -> Option> { self.members.read_or_recover().clone() } /// The party its operator says the node is of (`--store-party`). pub(crate) fn party(&self) -> Option<&str> { self.party.as_deref() } /// `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) } } /// The checkpoint `pin` names, found in the document's `events`: at heads a proposal's /// version names, built from their history, read from the root, as any node builds the /// checkpoint it moves to (`Store::checkpoint_at`). fn found(pin: &Id, root: &[u8], events: &BTreeMap>) -> Option { let named = events .values() .filter_map(|bytes| match Event::read_taken(bytes)? { Event::Signed(Signed { does: Does::Proposal { version, .. }, .. }) => Version::read(&version).ok()?.checkpoint, _ => None, }); for heads in named { let mut store = Store::::new(root.to_vec(), Vec::new()).ok()?; let mut history = heads.clone(); let mut seen = HashSet::new(); while let Some(id) = history.pop() { if let Some(bytes) = events.get(&id).filter(|_| seen.insert(id)) { history.extend(Federation::dependencies(bytes).unwrap_or_default()); store.offer(bytes.clone()); } } if let Some((checkpoint, kept)) = store.checkpoint_at(&heads) && Id::of(&checkpoint) == *pin { return Some((checkpoint, kept)); } } None } /// 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(); holding.unread(&replica.doc, replica.epoch_seq) }; if let Some(unread) = unread { holding.read(unread); } !holding.lacking(&doc.blocking_read().doc).is_empty() }); 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, } } } 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"), } } #[cfg(test)] mod tests { use super::*; use crate::document::typed::{TimestampFormat, Val}; use crate::document::{Document, ScalarValue}; use crate::federation::event::Checkpoint; use crate::federation::harness::{self, Party, Spec}; use crate::federation::version::Version; fn root_of(spec: &Spec) -> Vec { Checkpoint { at: Vec::new(), keeps: Vec::new(), version: Version::read(&spec.json()).expect("a version"), } .bytes() } fn put(doc: &mut Document, event: &[u8]) { crate::document::testing::change(doc, |doc| { store::write_val_path( doc, &events::event(&Id::of(event)), &Val::Scalar(ScalarValue::Bytes(event.to_vec())), store::Writing::sticky(TimestampFormat::default()), ) .unwrap(); }); } fn read(holding: &Holding, doc: &Document, epoch_seq: u32) { holding.read(holding.unread(doc, epoch_seq).unwrap()); } /// A checkpoint at a write of lass's built on two of tv's, a write of makefu's beside /// it: a node pinning it starts there, found in the document. #[test] fn a_node_starts_from_the_checkpoint_its_operator_pins() { let (tv, lass, makefu) = ( Party::new("tv", 1), Party::new("lass", 2), Party::new("makefu", 3), ); let first = Spec::first(&[&tv, &lass, &makefu], &[]); let root = root_of(&first); let on = first.hash(); let gone = tv.write(&[Id::of(&root)], "home/tv/a", harness::str("1")); let kept = tv.write(&[Id::of(&gone)], "home/tv/a", harness::str("2")); let head = lass.write(&[Id::of(&kept)], "home/lass/b", harness::str("3")); let beside = makefu.write(&[Id::of(&root)], "home/makefu/c", harness::str("4")); let mut next = first.after(on); next.checkpoint = Some(vec![Id::of(&head)]); let proposal = tv.propose(&[Id::of(&head)], &next.json()); let votes = [ tv.vote(&[Id::of(&proposal)], on, next.hash(), true), lass.vote(&[Id::of(&proposal)], on, next.hash(), true), ]; let written = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], next.hash()); let mut doc = events::started(Federation::NAME, &root).unwrap(); for event in [&gone, &kept, &head, &beside, &proposal] .into_iter() .chain(&votes) .chain([&written]) { put(&mut doc, event); } let from_root = Holding::default(); read(&from_root, &doc, 0); let pin = from_root.with(|store| Id::of(store.checkpoint())).unwrap(); assert_ne!(pin, Id::of(&root)); let files = Arc::new(Files::default()); let pinned = Holding::open(None, Arc::clone(&files), Some(pin), None).unwrap(); read(&pinned, &doc, 0); assert_eq!(pinned.with(|store| Id::of(store.checkpoint())), Some(pin)); let taken = |holding: &Holding| { let mut taken = holding.with(|store| store.taken().to_vec()).unwrap(); taken.sort_unstable(); taken }; assert_eq!(taken(&pinned), taken(&from_root)); assert_eq!( pinned.with(|store| store.holds(&Id::of(&beside))), Some(false) ); let elsewhere = Holding::open(None, files, Some(Id::of(b"elsewhere")), None).unwrap(); read(&elsewhere, &doc, 0); assert!(elsewhere.with(|_| ()).is_none()); } #[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], &[]); let root = root_of(&first); let mut doc = events::started(Federation::NAME, &root).unwrap(); let holding = Holding::default(); assert!(holding.unread(&Document::new(), 0).is_none()); read(&holding, &doc, 0); assert_eq!(holding.with(|store| store.id()), Some(Id::of(&root))); // Its first party lists a node. let node = harness::node_id(0); assert_eq!(holding.member(&node, Some("tv")), Some(true)); assert_eq!(holding.member(&node, Some("lass")), Some(false)); assert_eq!(holding.member(&node, None), Some(false)); assert_eq!(Holding::default().member(&node, Some("tv")), None); 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")); // What it builds on comes later: it waits for it. put(&mut doc, &on); read(&holding, &doc, 0); assert_eq!( holding.with(|store| store.is_waiting(&Id::of(&on))), Some(true) ); put(&mut doc, &write); read(&holding, &doc, 0); assert_eq!( holding.with(|store| store.taken().to_vec()), Some(vec![Id::of(&write), Id::of(&on)]) ); // Another document holding them: nothing new. let other = doc.fork(); read(&holding, &other, 1); assert_eq!(holding.with(|store| store.taken().len()), Some(2)); } /// Two version events changing version 0, each backed by tv and one other. #[test] fn a_node_read_anew_refuses_what_it_refused_of_its_own() { let (tv, lass, makefu) = ( Party::new("tv", 1), Party::new("lass", 2), Party::new("makefu", 3), ); let first = Spec::first(&[&tv, &lass, &makefu], &[]); let root = root_of(&first); let on = first.hash(); let one = first.after(on); let mut two = first.after(on); two.rules.push(("names/x".to_owned(), harness::str("tv"))); let p1 = tv.propose(&[Id::of(&root)], &one.json()); let p2 = lass.propose(&[Id::of(&root)], &two.json()); let votes = [ tv.vote(&[Id::of(&p1)], on, one.hash(), true), lass.vote(&[Id::of(&p1)], on, one.hash(), true), tv.vote(&[Id::of(&p2)], on, two.hash(), true), makefu.vote(&[Id::of(&p2)], on, two.hash(), true), ]; let v1 = harness::version_event(&[Id::of(&votes[0]), Id::of(&votes[1])], one.hash()); let v2 = harness::version_event(&[Id::of(&votes[2]), Id::of(&votes[3])], two.hash()); let before: Vec<&Vec> = [&p1, &p2].into_iter().chain(&votes).collect(); let taken = |holding: &Holding| holding.with(|store| store.taken().to_vec()).unwrap(); // The one a store reading all of them at once takes, and the other, which a node // took as it came first. let mut all = events::started(Federation::NAME, &root).unwrap(); for event in before.iter().copied().chain([&v1, &v2]) { put(&mut all, event); } let forgetting = Holding::default(); read(&forgetting, &all, 0); let (later, first_taken) = if taken(&forgetting).contains(&Id::of(&v1)) { (v1, v2) } else { (v2, v1) }; let dir = crate::files::scratch_dir("held"); let path = dir.join("store.json"); let files = Arc::new(Files::default()); let holding = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap(); let mut doc = events::started(Federation::NAME, &root).unwrap(); for event in before.iter().copied().chain([&first_taken]) { put(&mut doc, event); } read(&holding, &doc, 0); put(&mut doc, &later); read(&holding, &doc, 0); assert!(taken(&holding).contains(&Id::of(&first_taken))); assert!(!taken(&holding).contains(&Id::of(&later))); // Restarted: the store read anew, all at once, refuses the later as before. let anew = Holding::open(Some(path.clone()), Arc::clone(&files), None, None).unwrap(); read(&anew, &all, 0); assert!(taken(&anew).contains(&Id::of(&first_taken))); assert!(!taken(&anew).contains(&Id::of(&later))); std::fs::write(&path, b"{\"refused\": [\"not an ID\"]}").unwrap(); assert!(Holding::open(Some(path), files, None, None).is_err()); } }