//! 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, HashMap, HashSet}; use std::path::PathBuf; use std::sync::{Arc, Mutex, RwLock}; use std::time::{Duration, Instant}; use anyhow::{Context, Result, bail}; use serde::{Deserialize, Serialize}; use tracing::{error, info, warn}; use super::client::Record; use super::event::{self, Does, Event, Signed}; use super::fold::Federation; use super::store::memory::{Built, Offered, Store}; use super::store::{Fold, Id, Refused}; use super::version::Version; use super::vote::{self, Act, Rules, Seen}; 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 parties among whose members, with those of its own, the node keeps some of its /// neighbours (`--store-neighbour-parties`). near: Vec, /// 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>>, /// What it votes for its party with, if it votes by itself. voter: Option, // A std mutex: never held while waiting for the document. inner: Mutex, } /// What a node voting by itself for its party signs with, keeps and goes by /// (`federation::vote`): a key its party's version names, kept on the node; its party's /// one record of its votes, in a file; and its operator's rules. pub(crate) struct Voter { pub(crate) key: ed25519_dalek::SigningKey, pub(crate) record: PathBuf, pub(crate) rules: Rules, } #[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, /// When, by its own clock, the node took each event its store took after its /// checkpoint, and when the store moved to its checkpoint, or started there. taken_at: HashMap, at_checkpoint: Option<(Id, Instant)>, /// Its party's record, voting by itself, once read; and why it isn't, said once. record: Option, unrecorded: Option, } /// 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, near: Vec::new(), members: RwLock::default(), voter: None, 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 { // A fork's root keeps events, which follow it in the document. None => { let keeps = Federation::parts(&root).map_or_else(Vec::new, |(_, keeps)| keeps); let kept: Option>> = keeps .iter() .map(|keep| unread.events.get(keep).cloned()) .collect(); let Some(kept) = kept else { return; }; Store::new(root, kept) } 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"); } self.settle(inner); } /// After the store changed: what the node keeps of its own, written to its file where /// it changed, and the members, as the store reads now. fn settle(&self, inner: &mut Inner) { let Some(store) = &inner.store else { return; }; let now = Instant::now(); let checkpoint = Id::of(store.checkpoint()); if inner.at_checkpoint.map(|(at, _)| at) != Some(checkpoint) { inner.at_checkpoint = Some((checkpoint, now)); } let taken: HashSet<&Id> = store.taken().iter().collect(); inner.taken_at.retain(|id, _| taken.contains(id)); for id in store.taken() { inner.taken_at.entry(*id).or_insert(now); } 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); } } /// Offers the store `bytes`, an event put at the node's API: what became of it. None /// while the node holds no store. pub(crate) fn offer(&self, bytes: Vec) -> Option { let mut inner = self.inner.lock_or_recover(); let offered = inner.store.as_mut()?.offer(bytes); self.settle(&mut inner); Some(offered) } /// Drops `ids`, events the store took after its checkpoint, with everything built on /// them, as its operator has the node do: it refuses them from then on, and keeps so /// (`docs/store.md`, A node's own). What it dropped, in the order taken. pub(crate) fn drop_taken(&self, ids: &[Id]) -> Option, Refused>> { let mut inner = self.inner.lock_or_recover(); let dropped = inner.store.as_mut()?.drop_taken(ids); if let Ok(dropped) = &dropped { warn!( dropped = dropped.len(), "Dropped events, as this node's operator says" ); } self.settle(&mut inner); Some(dropped) } /// Takes back what the node refused of its own, or dropped, among `ids`, and what was /// refused for building on them, as its operator says otherwise: the document's events /// are offered again, and taken where the store takes them then. Whether it holds a /// store. pub(crate) fn allow(&self, ids: &[Id]) -> bool { let mut inner = self.inner.lock_or_recover(); let Some(store) = inner.store.as_mut() else { return false; }; store.allow(ids); inner.read.clear(); inner.looked.clear(); self.settle(&mut inner); true } /// 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())))) } /// Whether the node holds a store, and so tells who is a member (`member`). pub(crate) fn tells_members(&self) -> bool { self.members.read_or_recover().is_some() } /// 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() } /// Itself, voting by itself for its party as `voter` says, if it does. pub(crate) fn voting(self, voter: Option) -> Self { Holding { voter, ..self } } /// Its party's record, read from its file, or begun on the current version where there /// is none: one of another store or party, or that doesn't read, it votes by none. fn record<'a>(&self, voter: &Voter, inner: &'a mut Inner) -> Option<&'a mut Record> { let store = inner.store.as_ref()?; let party = self.party.as_deref()?; if inner.record.is_none() { let read = match Record::load(&voter.record) { Ok(record) if record.store == store.id().to_string() && record.party == party => { Ok(record) } Ok(_) => Err(format!( "{}: the record of another store or party", voter.record.display() )), Err(_) if !voter.record.exists() => { let record = Record::begin(store.id(), party, store.state().current()); record.save(&voter.record).map(|()| record) } Err(why) => Err(why), }; match read { Ok(record) => inner.record = Some(record), Err(why) => { if inner.unrecorded.as_ref() != Some(&why) { error!(why = %why, "Voting by itself, without its party's record: votes none"); inner.unrecorded = Some(why); } return None; } } } inner.record.as_mut() } /// What it signs now, voting by itself by its operator's rules (`vote::decide`), or by /// hand (`hand`, `vote::by_hand`): recorded, the record written, and offered to the /// store; the events, to put into the document. By hand, why not where it isn't. fn sign(&self, hand: Option<(Id, bool)>) -> Result>, String> { let (Some(voter), Some(party)) = (&self.voter, &self.party) else { return Err("this node doesn't vote for its party".to_owned()); }; let mut inner = self.inner.lock_or_recover(); let inner = &mut *inner; self.record(voter, inner) .ok_or("this node holds no store, or no record of its party")?; let (Some(store), Some(record)) = (&inner.store, &inner.record) else { return Err("this node holds no store".to_owned()); }; let now = Instant::now(); let held = |id: &Id| inner.taken_at.get(id).map(|at| now.duration_since(*at)); let seen = Seen { store, held: &held, since_move: inner .at_checkpoint .map_or(Duration::ZERO, |(_, at)| now.duration_since(at)), }; let acts = match hand { Some((proposal, yes)) => { vec![vote::by_hand(&seen, &voter.rules, record, proposal, yes)?] } None => vote::decide(&seen, &voter.rules, record), }; if acts.is_empty() { return Ok(Vec::new()); } let current = store.state().current().clone(); let ballots = store.state().ballots(¤t.hash); let heads = store.heads(); let line = crate::access::sshsig::PublicKey(voter.key.verifying_key().to_bytes()).line(); let mut record = record.clone(); let mut signed = Vec::new(); for act in acts { match act { Act::Vote { proposal, yes, nays, } => { // On the events proposing it: above the heads it names for a // checkpoint wherever they are, so a version event may be written on // it, which the node's heads, holding what is beside them, may not be. let proposing = ballots .get(&proposal) .map_or_else(Vec::new, |ballot| ballot.proposals.clone()); let cast = event::signed( &voter.key, party, &line, if proposing.is_empty() { &heads } else { &proposing }, event::vote(current.hash, proposal, yes), ); record.cast(¤t, &cast, nays); info!(proposal = %proposal, yes, by_hand = hand.is_some(), "Voting for its party"); signed.push(cast); } Act::Propose(version) => { // On the heads it names for a checkpoint: above them. let at = Version::read(&version) .ok() .and_then(|version| version.checkpoint) .unwrap_or_else(|| heads.clone()); let proposing = event::signed(&voter.key, party, &line, &at, event::proposal(&version)); record.signed(&proposing); info!(proposal = %Id::of(&version.bytes()), "Proposing a checkpoint for its party"); signed.push(proposing); } } } // Written before anything is sent. record.save(&voter.record)?; inner.record = Some(record); let store = inner.store.as_mut().expect("held above"); for bytes in &signed { store.offer(bytes.clone()); } self.settle(inner); Ok(signed) } /// 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). pub(crate) fn passed(&self) -> Vec> { let mut inner = self.inner.lock_or_recover(); let inner = &mut *inner; let Some(store) = inner.store.as_mut() else { return Vec::new(); }; let state = store.state(); let writing: Vec> = state .ballots(&state.current().hash) .keys() .filter_map(|proposal| state.version_event(proposal)) .collect(); let mut written = Vec::new(); for bytes in writing { if let Offered::Taken(_) = store.offer(bytes.clone()) { info!(event = %Id::of(&bytes), "Writing a version that passed"); written.push(bytes); } } if !written.is_empty() { self.settle(inner); } written } /// What it signs now, voting by itself by its operator's rules: to put into the /// document. pub(crate) fn act(&self) -> Vec> { if self.voter.is_none() { return Vec::new(); } self.sign(None).unwrap_or_else(|why| { warn!(why = %why, "Couldn't vote by itself"); Vec::new() }) } /// A vote by hand through this node, which votes for its party and keeps its one /// record: the event, to put into the document, or why not. pub(crate) fn vote_by_hand(&self, proposal: Id, yes: bool) -> Result, String> { self.sign(Some((proposal, yes)))? .pop() .ok_or_else(|| "nothing to cast".to_owned()) } /// The party its operator says the node is of (`--store-party`). pub(crate) fn party(&self) -> Option<&str> { self.party.as_deref() } /// Itself, the node keeping some of its neighbours among the members of `parties`, /// with those of its own (`--store-neighbour-parties`). pub(crate) fn near(self, parties: Vec) -> Self { Holding { near: parties, ..self } } /// The parties among whose members, with those of its own, the node keeps some of its /// neighbours: its own first. pub(crate) fn nearby(&self) -> Vec<&str> { self.party .iter() .chain(&self.near) .map(String::as_str) .collect() } /// `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; writes what passed and what it signs voting by itself; 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; // Whether this node is a member of its store, as last said. let mut listed: 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); } let signed = holding.act(); let passed = holding.passed(); ( !holding.lacking(&doc.blocking_read().doc).is_empty(), signed, passed, ) }); let (lacking, signed, passed) = read.await.unwrap_or_else(|error| { error!(error = %error, "Reading the store from the document failed"); (false, Vec::new(), Vec::new()) }); for bytes in signed { if let Err(error) = write(&state, None, bytes).await { warn!(error = %error, "Couldn't put what it signed for its party: put again later"); } } for bytes in passed { if let Err(error) = write(&state, None, bytes).await { warn!(error = %error, "Couldn't write a version that passed: put again later"); } } let member = state .holding .member(state.local_id(), state.holding.party()); if member.is_some() && member != listed { match member { Some(false) => warn!( party = state.holding.party(), "This node isn't a member of its store, as it reads now: its party doesn't list it, and members don't sync with it" ), _ => info!( party = state.holding.party(), "This node is a member of its store" ), } listed = member; } 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. /// Puts `bytes`, an event, into the document at its ID unless it holds it: for `user`, who /// put it through the API, or for the node itself. pub(crate) async fn write( state: &crate::state::AppState, user: Option, bytes: Vec, ) -> Result<(), store::StoreError> { let id = Id::of(&bytes); state .mutate_doc_for( user, crate::document::signatures::Sign::Protocol, move |doc| { if events::bytes(doc, &id).is_none() { store::write_val_path( doc, &events::event(&id), &crate::document::typed::Val::Scalar(ScalarValue::Bytes(bytes)), store::Writing::sticky(Default::default()), )?; } Ok::<(), store::StoreError>(()) }, ) .await .map(|_| ()) } 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::Document; use crate::federation::harness::{self, Party, Spec}; use crate::federation::store::memory::Refusal; fn put(doc: &mut Document, event: &[u8]) { events::put(doc, &[event]); } 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 = first.root(); 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()); } /// An event put at the API is offered to the store; what the operator drops is /// refused, and kept so, until it allows it again. #[test] fn an_operator_drops_what_its_node_took_and_allows_it_again() { let tv = Party::new("tv", 1); let first = Spec::first(&[&tv], &[]); let root = first.root(); 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 holding = Holding::default(); assert_eq!(holding.offer(write.clone()), None); let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); put(&mut doc, &write); read(&holding, &doc, 0); assert!(matches!(holding.offer(on.clone()), Some(Offered::Taken(_)))); assert_eq!( holding.drop_taken(&[Id::of(&write)]), Some(Ok(vec![Id::of(&write), Id::of(&on)])) ); assert!(matches!(holding.drop_taken(&[Id::of(&root)]), Some(Err(_)))); assert_eq!(holding.with(|store| store.taken().len()), Some(0)); assert_eq!(holding.inner.lock_or_recover().kept.dropped.len(), 1); // Allowed again: the document's events are taken again as it reads them. assert!(holding.allow(&[Id::of(&write)])); read(&holding, &doc, 0); assert_eq!( holding.with(|store| store.taken().to_vec()), Some(vec![Id::of(&write)]) ); assert!(holding.inner.lock_or_recover().kept.dropped.is_empty()); } #[test] fn a_node_puts_again_what_its_document_lacks() { let tv = Party::new("tv", 1); let first = Spec::first(&[&tv], &[]); let root = first.root(); 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 = first.root(); 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 = first.root(); 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()); } // The store's attack rows (`docs/store.md`, Attacks) read from a document. /// tv's federation, its root, and a document started from it. fn tv_alone() -> (Party, Vec, Document) { let tv = Party::new("tv", 1); let root = Spec::first(&[&tv], &[]).root(); let doc = events::started(Federation::NAME, &root, &[]).unwrap(); (tv, root, doc) } /// An event whose dependencies never come: taken by no node; it stays in the document. #[test] fn store_attack_3() { let (tv, _, mut doc) = tv_alone(); let on = tv.write(&[Id::of(b"never")], "home/tv/x", harness::str("1")); put(&mut doc, &on); let holding = Holding::default(); read(&holding, &doc, 0); assert_eq!( holding.with(|store| store.is_waiting(&Id::of(&on))), Some(true) ); assert!(events::ids(&doc).contains(&Id::of(&on))); } /// The same event put by two changes at once, or again later: one event. #[test] fn store_attack_5() { let (tv, root, mut doc) = tv_alone(); let write = tv.write(&[Id::of(&root)], "home/tv/x", harness::str("1")); let mut other = doc.fork(); put(&mut doc, &write); put(&mut other, &write); doc.merge(&mut other).unwrap(); assert_eq!(events::ids(&doc).len(), 2); let holding = Holding::default(); read(&holding, &doc, 0); read(&holding, &doc.fork(), 1); assert_eq!( holding.with(|store| store.taken().to_vec()), Some(vec![Id::of(&write)]) ); } /// An event the fold refuses, beside others in one change: the store takes the others, /// and not that one, nor what is built on it. #[test] fn store_attack_6() { let (tv, root, mut doc) = tv_alone(); let good = tv.write(&[Id::of(&root)], "home/tv/x", harness::str("1")); let bad = tv.write(&[Id::of(&root)], "elsewhere/x", harness::str("1")); let on_bad = tv.write(&[Id::of(&bad)], "home/tv/y", harness::str("1")); events::put(&mut doc, &[&good, &bad, &on_bad]); let holding = Holding::default(); read(&holding, &doc, 0); assert_eq!( holding.with(|store| store.taken().to_vec()), Some(vec![Id::of(&good)]) ); assert!(matches!( holding.with(|store| store.refusal(&Id::of(&on_bad)).cloned()), Some(Some(Refusal::BuiltOn(_))) )); } /// Bytes that are none of the fold's events, or a root other than the store's: refused. #[test] fn store_attack_8() { let (_, _, mut doc) = tv_alone(); let junk = b"{\"not\":\"an event\"}".to_vec(); let other = Spec::first(&[&Party::new("lass", 2)], &[]).root(); put(&mut doc, &junk); put(&mut doc, &other); let holding = Holding::default(); read(&holding, &doc, 0); for bytes in [&junk, &other] { assert_eq!( holding.with(|store| store.refusal(&Id::of(bytes)).cloned()), Some(Some(Refusal::None)) ); } assert_eq!(holding.with(|store| store.taken().len()), Some(0)); } /// A node whose operator had it drop an event is sent it again, in another change, /// before or after a restart: not taken, with everything built on it. #[test] fn store_attack_20() { let (tv, root, mut doc) = tv_alone(); 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")); put(&mut doc, &write); let dir = crate::files::scratch_dir("held-attack-20"); 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(); read(&holding, &doc, 0); holding.drop_taken(&[Id::of(&write)]).unwrap().unwrap(); // Another document, the event in another change. let mut again = events::started(Federation::NAME, &root, &[]).unwrap(); events::put(&mut again, &[&write, &on]); read(&holding, &again, 1); assert_eq!(holding.with(|store| store.taken().len()), Some(0)); let restarted = Holding::open(Some(path), files, None, None).unwrap(); read(&restarted, &again, 0); assert_eq!(restarted.with(|store| store.taken().len()), Some(0)); } /// An event not above the heads of the checkpoint a node moved to: not taken; it stays /// in the document. #[test] fn store_attack_23() { let (tv, lass) = (Party::new("tv", 1), Party::new("lass", 2)); let makefu = Party::new("makefu", 3); let first = Spec::first(&[&tv, &lass, &makefu], &[]); let root = first.root(); let on = first.hash(); let head = tv.write(&[Id::of(&root)], "home/tv/a", harness::str("1")); 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 [&head, &proposal] .into_iter() .chain(&votes) .chain([&written]) { put(&mut doc, event); } let holding = Holding::default(); read(&holding, &doc, 0); assert_ne!( holding.with(|store| Id::of(store.checkpoint())), Some(Id::of(&root)) ); let beside = makefu.write(&[Id::of(&root)], "home/makefu/b", harness::str("1")); put(&mut doc, &beside); read(&holding, &doc, 0); assert_eq!( holding.with(|store| store.refusal(&Id::of(&beside)).cloned()), Some(Some(Refusal::NotAbove)) ); assert!(events::ids(&doc).contains(&Id::of(&beside))); } /// A fork's document: its store starts from the fork's root and the events it keeps, /// which follow it there, and takes what builds on it, not what the store it came from /// took after its heads. #[test] fn a_node_reads_a_forks_store_from_its_document() { let tv = Party::new("tv", 1); let first = Spec::first(&[&tv], &[]); let mut came_from = Store::::new(first.root(), Vec::new()).unwrap(); let write = tv.write(&[came_from.id()], "home/tv/x", harness::str("1")); let head = Id::of(&write); came_from.offer(write); let mut spec = first.after(first.hash()); spec.parties[0].nodes_since = 1; let (root, kept) = came_from.fork(&[head], &spec.json().bytes()).unwrap(); let stayed = tv.write(&[head], "home/tv/x", harness::str("2")); let went = tv.write(&[Id::of(&root)], "home/tv/y", harness::str("3")); let mut doc = events::started(Federation::NAME, &root, &kept).unwrap(); put(&mut doc, &stayed); put(&mut doc, &went); let holding = Holding::default(); read(&holding, &doc, 0); assert_eq!(holding.with(|store| store.id()), Some(Id::of(&root))); assert_eq!( holding.with(|store| store.state().value("home/tv/x").cloned()), Some(Some(harness::str("1"))) ); assert_eq!( holding.with(|store| store.taken().to_vec()), Some(vec![Id::of(&went)]) ); // Its root alone, the events it keeps not there yet: no store yet. let alone = events::started(Federation::NAME, &root, &[]).unwrap(); let waiting = Holding::default(); read(&waiting, &alone, 0); assert!(waiting.with(|_| ()).is_none()); } /// Two proposals on the first version passing at once, tv backing both: a node writes /// the one it takes, and refuses the other, of its own. #[test] fn a_node_writes_what_passed() { 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 = first.root(); 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 mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); for event in [ &p1, &p2, &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), ] { put(&mut doc, event); } let holding = Holding::default(); assert_eq!(holding.passed(), Vec::>::new()); read(&holding, &doc, 0); let written = holding.passed(); assert_eq!(written.len(), 1); let current = holding.with(|store| store.state().current().hash).unwrap(); assert!(current == one.hash() || current == two.hash()); let other = if current == one.hash() { &two } else { &one }; let refused = holding.with(|store| store.own().0).unwrap(); assert_eq!(refused.len(), 1); assert_eq!( holding.with(|store| store.state().version_event(&other.hash())), Some(None) ); assert_eq!(holding.passed(), Vec::>::new()); } /// tv's checkpoint at its write, and a write of lass's beside it: makefu's node, /// following tv, votes on the event proposing it, not on its heads, which hold lass's /// write too; so its vote is above the checkpoint's heads, the version event written /// on it is taken, and the node moves there. #[test] fn a_node_votes_above_the_heads_of_the_checkpoint_it_votes_on() { 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 = first.root(); let on = first.hash(); let write = tv.write(&[Id::of(&root)], "home/tv/x", harness::str("1")); let beside = lass.write(&[Id::of(&root)], "home/lass/x", harness::str("1")); let mut next = first.after(on); next.checkpoint = Some(vec![Id::of(&write)]); let proposal = tv.propose(&[Id::of(&write)], &next.json()); let yes = tv.vote(&[Id::of(&proposal)], on, next.hash(), true); let mut doc = events::started(Federation::NAME, &root, &[]).unwrap(); for event in [&write, &beside, &proposal, &yes] { put(&mut doc, event); } let record = crate::files::scratch_dir("held-votes-above").join("makefu.json"); let version = Version::read(&first.json()).unwrap(); let mut begun = Record::begin(Id::of(&root), "makefu", &version); begun.began = Id::of(b"before the federation").to_string(); begun.save(&record).unwrap(); let holding = Holding::open( None, Arc::new(Files::default()), None, Some("makefu".into()), ) .unwrap() .voting(Some(Voter { key: makefu.key.clone(), record, rules: Rules { follow: vec!["tv".to_owned()], ..Rules::default() }, })); read(&holding, &doc, 0); let cast = holding.act(); assert_eq!(cast.len(), 1); assert!(matches!( Event::read_taken(&cast[0]), Some(Event::Signed(Signed { deps, does: Does::Vote { yes: true, .. }, .. })) if deps == vec![Id::of(&proposal)] )); assert_eq!(holding.passed().len(), 1); assert_eq!( holding.with(|store| store.state().current().hash), Some(next.hash()) ); } /// Rows whose tests wait: remakes (stage 5), and flooding. const LATER: &[u32] = &[11, 12, 13, 15, 16, 21, 22, 28, 29, 30, 31]; #[test] fn every_row_has_its_test() { harness::every_row_has_its_test( include_str!("../../docs/store.md"), "store_attack_", &[ include_str!("held.rs"), include_str!("store/memory.rs"), include_str!("../access/holding.rs"), include_str!("../access/token.rs"), ], &[include_str!("../simtest/holding.rs")], LATER, ); } }