aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authortv <tv@krebsco.de>2026-11-16 16:23:51 +0000
committertv <tv@krebsco.de>2026-11-16 18:01:39 +0100
commit169b6b0e573ecc2a3f8e5f78d54f2e5c484a1373 (patch)
tree3391f9ee71d7ebe705c82c3f71f9878c8218a806
parent11244e60fbcef6b154c7b657ce2c50d56277bf7b (diff)
store: moving to a checkpoint, and starting from a pinned one
Once the fold names heads of a later checkpoint (events after the store's, none in another's history), the store builds the checkpoint at them, keeps what the fold keeps, forgets what came before them, and refuses every event not above them, with what waits on such an event. What it forgot is held as accounted for: brought again, it is held, and an event built on it isn't above the heads. A store starts from a checkpoint its operator pins, its events building on the heads the checkpoint was built at. A node starting from a checkpoint must judge the event that named it as every node does; the fold for the tests counts the heads of the checkpoint a state starts from as after the checkpoint current at them, so that it does.
-rw-r--r--src/federation/store/memory.rs236
-rw-r--r--src/federation/store/testfold.rs7
2 files changed, 235 insertions, 8 deletions
diff --git a/src/federation/store/memory.rs b/src/federation/store/memory.rs
index 85fac7f..6d265f4 100644
--- a/src/federation/store/memory.rs
+++ b/src/federation/store/memory.rs
@@ -65,19 +65,42 @@ pub(crate) struct Store<F: Fold> {
waits_for: HashMap<Id, BTreeSet<Id>>,
/// The events refused, and why.
refused: HashMap<Id, Refusal>,
+ /// What a move to a checkpoint forgot that came before its heads: held as accounted
+ /// for, and nothing after the checkpoint builds on it.
+ forgotten: HashSet<Id>,
}
impl<F: Fold> Store<F> {
- /// A store starting from its root, with the events the root keeps.
+ /// A store starting from its root, with the events the root keeps: its events build
+ /// on the root itself.
pub(crate) fn new(root: Vec<u8>, kept: Vec<Vec<u8>>) -> Result<Self, Refused> {
let id = Id::of(&root);
- let (_, keeps) = F::parts(&root).ok_or_else(|| Refused::new("no checkpoint"))?;
+ Self::starting(id, root, BTreeSet::from([id]), kept)
+ }
+
+ /// A store of ID `id` starting from a checkpoint its operator pins, with the events it
+ /// keeps: its events build on the heads it was built at.
+ pub(crate) fn pinned(id: Id, checkpoint: Vec<u8>, kept: Vec<Vec<u8>>) -> Result<Self, Refused> {
+ let (at, _) = F::parts(&checkpoint).ok_or_else(|| Refused::new("no checkpoint"))?;
+ if at.is_empty() {
+ return Err(Refused::new("a checkpoint without heads is a root"));
+ }
+ Self::starting(id, checkpoint, at.into_iter().collect(), kept)
+ }
+
+ fn starting(
+ id: Id,
+ checkpoint: Vec<u8>,
+ heads: BTreeSet<Id>,
+ kept: Vec<Vec<u8>>,
+ ) -> Result<Self, Refused> {
+ let (_, keeps) = F::parts(&checkpoint).ok_or_else(|| Refused::new("no checkpoint"))?;
let kept = matched(&keeps, kept)?;
- let start = F::start(&root, &kept.clone().into_iter().collect::<Vec<_>>())?;
+ let start = F::start(&checkpoint, &kept.clone().into_iter().collect::<Vec<_>>())?;
Ok(Self {
id,
- checkpoint: root,
- heads: BTreeSet::from([id]),
+ checkpoint,
+ heads,
kept,
state: start.clone(),
start,
@@ -86,6 +109,7 @@ impl<F: Fold> Store<F> {
waiting: HashMap::new(),
waits_for: HashMap::new(),
refused: HashMap::new(),
+ forgotten: HashSet::new(),
})
}
@@ -99,6 +123,11 @@ impl<F: Fold> Store<F> {
&self.checkpoint
}
+ /// The events the checkpoint keeps, as bytes, in the order of their IDs.
+ pub(crate) fn kept(&self) -> Vec<Vec<u8>> {
+ self.kept.values().cloned().collect()
+ }
+
/// What everything the store holds reads as.
pub(crate) fn state(&self) -> &F::State {
&self.state
@@ -152,7 +181,10 @@ impl<F: Fold> Store<F> {
/// takes it at its history.
pub(crate) fn offer(&mut self, bytes: Vec<u8>) -> Offered {
let id = Id::of(&bytes);
- if self.events.contains_key(&id) || self.kept.contains_key(&id) || self.heads.contains(&id)
+ if self.events.contains_key(&id)
+ || self.kept.contains_key(&id)
+ || self.heads.contains(&id)
+ || self.forgotten.contains(&id)
{
return Offered::Held;
}
@@ -209,12 +241,118 @@ impl<F: Fold> Store<F> {
}
first.get_or_insert(offered);
}
+ if !taken.is_empty() {
+ while self.moved() {}
+ }
match first.expect("one event considered") {
Offered::Taken(_) => Offered::Taken(taken),
other => other,
}
}
+ /// Moves to the checkpoint the fold names, where it names a later one: builds it at its
+ /// heads, forgets what came before them but what it keeps, and every event not above
+ /// them, refusing those from then on. Whether it moved.
+ fn moved(&mut self) -> bool {
+ let Some(named) = F::moves_to(&self.state) else {
+ return false;
+ };
+ let heads: BTreeSet<Id> = named.into_iter().collect();
+ if heads == self.heads
+ || heads.is_empty()
+ || !heads.iter().all(|head| self.events.contains_key(head))
+ {
+ return false;
+ }
+ let beside = heads.iter().any(|head| {
+ let history = self.history(&self.events[head].dependencies);
+ heads.iter().any(|other| history.contains(other))
+ });
+ if beside {
+ return false;
+ }
+ let ids: Vec<Id> = heads.iter().copied().collect();
+ let at = self.state_at(&ids);
+ let (checkpoint, keeps) = F::checkpoint(&at, &ids);
+ let Some(kept) = keeps
+ .iter()
+ .map(|id| self.get(id).map(<[u8]>::to_vec))
+ .collect::<Option<Vec<_>>>()
+ else {
+ return false;
+ };
+ let Ok(kept) = matched(&keeps, kept) else {
+ return false;
+ };
+ let Ok(start) = F::start(&checkpoint, &kept.clone().into_iter().collect::<Vec<_>>()) else {
+ return false;
+ };
+ let before = self.history(&ids);
+ let mut above: HashSet<Id> = HashSet::new();
+ for id in self.order.iter().filter(|id| !before.contains(id)) {
+ let dependencies = &self.events[id].dependencies;
+ let on = dependencies
+ .iter()
+ .all(|dependency| heads.contains(dependency) || above.contains(dependency));
+ let holds = dependencies
+ .iter()
+ .any(|dependency| above.contains(dependency))
+ || heads.iter().all(|head| dependencies.contains(head));
+ if on && holds {
+ above.insert(*id);
+ }
+ }
+ for id in &self.order {
+ if before.contains(id) {
+ if !kept.contains_key(id) && !heads.contains(id) {
+ self.forgotten.insert(*id);
+ }
+ } else if !above.contains(id) {
+ self.refused.insert(*id, Refusal::NotAbove);
+ }
+ }
+ let old = std::mem::replace(&mut self.heads, heads);
+ self.forgotten
+ .extend(old.into_iter().filter(|head| !self.heads.contains(head)));
+ self.forgotten.extend(
+ self.kept
+ .keys()
+ .filter(|id| !kept.contains_key(id))
+ .copied(),
+ );
+ self.checkpoint = checkpoint;
+ self.kept = kept;
+ self.order.retain(|id| above.contains(id));
+ self.events.retain(|id, _| above.contains(id));
+ let mut state = start.clone();
+ for id in &self.order {
+ F::add(&mut state, id, &self.events[id].bytes);
+ }
+ self.start = start;
+ self.state = state;
+ let stale: Vec<Id> = self
+ .waiting
+ .iter()
+ .filter(|(_, event)| {
+ event.dependencies.iter().any(|dependency| {
+ self.forgotten.contains(dependency) || self.refused.contains_key(dependency)
+ })
+ })
+ .map(|(id, _)| *id)
+ .collect();
+ for id in stale {
+ if let Some(event) = self.waiting.remove(&id) {
+ for dependency in &event.dependencies {
+ if let Some(waiting) = self.waits_for.get_mut(dependency) {
+ waiting.remove(&id);
+ }
+ }
+ }
+ self.refuse(id, Refusal::NotAbove);
+ }
+ true
+ }
+
/// The events that waited for `id` alone, now to be considered again.
fn woken(&mut self, id: &Id) -> Vec<(Id, Event)> {
let Some(waiters) = self.waits_for.remove(id) else {
@@ -243,7 +381,8 @@ impl<F: Fold> Store<F> {
return self.refuse(id, Refusal::BuiltOn(refused));
}
let before = |dependency: &Id| {
- self.kept.contains_key(dependency) && !self.heads.contains(dependency)
+ (self.kept.contains_key(dependency) || self.forgotten.contains(dependency))
+ && !self.heads.contains(dependency)
};
if event.dependencies.iter().any(before) {
return self.refuse(id, Refusal::NotAbove);
@@ -536,6 +675,89 @@ mod tests {
assert!(store.drop_taken(&[root]).is_err());
}
+ /// A store whose root holds puts and a lock, cut at the lock: the cut's ID, the lock's,
+ /// and the first put's, which the checkpoint forgets.
+ fn cut_at_a_lock() -> (Store<TestFold>, Id, Id, Id) {
+ let mut store = store();
+ let root = store.id();
+ let first = taken(store.offer(testfold::put(&[root], "a", "1")));
+ let second = taken(store.offer(testfold::put(&[first], "a", "2")));
+ let lock = taken(store.offer(testfold::lock(&[second], "b")));
+ let cut = taken(store.offer(testfold::cut(&[lock], 1, &[lock])));
+ (store, cut, lock, first)
+ }
+
+ #[test]
+ fn a_cut_moves_the_store_to_a_checkpoint() {
+ let (mut store, cut, lock, first) = cut_at_a_lock();
+ assert_eq!(
+ TestFold::parts(store.checkpoint()).map(|(at, _)| at),
+ Some(vec![lock])
+ );
+ assert_eq!(store.taken(), &[cut]);
+ assert_eq!(store.kept().len(), 1);
+ assert_eq!(store.state().counts()["a"], "2");
+ assert!(store.state().locks().contains("b"));
+ // After it: taken. On what it forgot, or the root: not above its heads.
+ assert!(matches!(
+ store.offer(testfold::put(&[cut], "a", "3")),
+ Offered::Taken(_)
+ ));
+ assert_eq!(store.state().counts()["a"], "3");
+ assert_eq!(
+ store.offer(testfold::put(&[first], "c", "1")),
+ Offered::Refused(Refusal::NotAbove)
+ );
+ let root = store.id();
+ assert_eq!(
+ store.offer(testfold::put(&[root], "c", "1")),
+ Offered::Refused(Refusal::NotAbove)
+ );
+ // A head brought again is held; so is what came before it.
+ assert_eq!(
+ store.offer(testfold::lock(
+ &[Id::of(&testfold::put(&[first], "a", "2"))],
+ "b"
+ )),
+ Offered::Held
+ );
+ assert_eq!(store.offer(testfold::put(&[root], "a", "1")), Offered::Held);
+ }
+
+ #[test]
+ fn what_was_taken_beside_the_heads_is_refused_by_the_move() {
+ let mut store = store();
+ let root = store.id();
+ let here = taken(store.offer(testfold::put(&[root], "a", "1")));
+ let beside = taken(store.offer(testfold::put(&[root], "b", "1")));
+ let on_beside = taken(store.offer(testfold::put(&[beside], "c", "1")));
+ let cut = taken(store.offer(testfold::cut(&[here], 1, &[here])));
+ assert_eq!(store.taken(), &[cut]);
+ assert_eq!(store.refusal(&beside), Some(&Refusal::NotAbove));
+ assert_eq!(store.refusal(&on_beside), Some(&Refusal::NotAbove));
+ assert!(!store.state().counts().contains_key("b"));
+ }
+
+ #[test]
+ fn a_node_starts_from_a_pinned_checkpoint() {
+ let (mut store, cut, _, _) = cut_at_a_lock();
+ let later = testfold::put(&[cut], "c", "1");
+ assert!(matches!(store.offer(later.clone()), Offered::Taken(_)));
+ let mut pinned: Store<TestFold> =
+ Store::pinned(store.id(), store.checkpoint().to_vec(), store.kept()).expect("pinned");
+ assert_eq!(pinned.offer(later.clone()), Offered::Waiting);
+ let cut_bytes = store.get(&cut).expect("held").to_vec();
+ assert_eq!(
+ pinned.offer(cut_bytes),
+ Offered::Taken(vec![cut, Id::of(&later)])
+ );
+ assert_eq!(pinned.state().counts(), store.state().counts());
+ assert_eq!(pinned.checkpoint(), store.checkpoint());
+ assert!(
+ Store::<TestFold>::pinned(store.id(), store.checkpoint().to_vec(), Vec::new()).is_err()
+ );
+ }
+
#[test]
fn an_event_waits_until_all_it_builds_on_is_held() {
let mut store = store();
diff --git a/src/federation/store/testfold.rs b/src/federation/store/testfold.rs
index 4b7e1b2..68397e7 100644
--- a/src/federation/store/testfold.rs
+++ b/src/federation/store/testfold.rs
@@ -176,7 +176,12 @@ impl State {
/// Whether `heads` may be a checkpoint's here, and the state is above them.
fn above(&self, heads: &[Id]) -> bool {
- let after = |id: &Id| self.graph.contains_key(id) && !self.before.contains(id);
+ // The heads of the checkpoint the state starts from count as after the checkpoint
+ // current at them, so that a node starting from it judges the cut naming it as
+ // every node does.
+ let after = |id: &Id| {
+ (self.graph.contains_key(id) && !self.before.contains(id)) || self.at.contains(id)
+ };
if heads.is_empty() || !heads.iter().all(after) {
return false;
}