diff options
| author | tv <tv@krebsco.de> | 2026-11-15 18:48:10 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-15 18:48:10 +0000 |
| commit | 036b968712c6c4d5e467de3d1df17ffa538a23c5 (patch) | |
| tree | eb14d5690fa8dc93a6008d2aa8c6b61bf3172f8d /src/remake/delta.rs | |
| parent | fe058b3356edcad7f3d069a4e84af1bbedffada6 (diff) | |
remakes: links replayed in the order their changes were made
Under a strict policy, the links of the chains to signed values were
ordered across places by their changes' timestamps. How a link is
judged in the new epoch depends on what was replayed before it: a key
added to a user's entry, a capability granted. A write signed with a
key added a moment before, through a node whose clock is behind, went
first, was refused and quarantined, though every node had taken it.
The changes replayed (`between`) now come each after those it builds
on, clocks deciding only between changes neither of which saw the
other, then the lower hash; the links follow that order, and an
envelope takes its time from the first change that wrote it there.
remakes.md says so, and what becomes of a place where a link is
refused. Without a strict policy there are no links, and nothing
changes.
Diffstat (limited to 'src/remake/delta.rs')
| -rw-r--r-- | src/remake/delta.rs | 174 |
1 files changed, 143 insertions, 31 deletions
diff --git a/src/remake/delta.rs b/src/remake/delta.rs index 78a8097..388eae7 100644 --- a/src/remake/delta.rs +++ b/src/remake/delta.rs @@ -38,9 +38,11 @@ //! one the new document holds there to the one the old document reads, each in a //! change of its own, by its signer, at its own time, so that each replaces the one //! before it as every node checks; and only where the new document holds a lower `seq` -//! there, as values signed by their users are read by `seq`, not by clocks. A place is -//! found from the changes' operations as well as from the diff, which says nothing of a -//! value that changed beside Automerge's own choice. +//! there, as values signed by their users are read by `seq`, not by clocks. The links of +//! all places go in the order their changes were made ([`between`]), clocks deciding +//! only between changes neither of which saw the other. A place is found from the +//! changes' operations as well as from the diff, which says nothing of a value that +//! changed beside Automerge's own choice. use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet}; @@ -144,23 +146,30 @@ pub(crate) fn replay_newest( let theirs = touched(dst, &newer); let mut by_time: BTreeMap<(i64, Option<String>), Vec<Vec<String>>> = BTreeMap::new(); - // The links of the chains to signed values, each a change of its own, before what is - // written at the same time (it may decide who may write that). - let mut links: BTreeMap<(i64, usize), (Vec<String>, String, String)> = BTreeMap::new(); + // The links of the chains to signed values, each a change of its own: in the order + // their changes were made, each after those it builds on, whatever the clocks say + // (one may add the key the next is signed with); and before what is written at the + // same time (it may decide who may write that). + let mut ordered: BTreeMap<(usize, usize), Link> = BTreeMap::new(); for place in signed { match chain(src, after, &changes, &place, dst) { Chain::Links(chain) => { - // In their order, whatever their clocks say. - let mut at = i64::MIN; - for (when, envelope, user) in chain { - at = at.max(when); - links.insert((at, links.len()), (place.clone(), envelope, user)); + for (made, when, envelope, user) in chain { + ordered.insert((made, ordered.len()), (when, place.clone(), envelope, user)); } } Chain::Held => stats.superseded += 1, Chain::Broken(why) => stats.quarantined.push((place, why)), } } + let mut at = i64::MIN; + let links: Vec<Link> = ordered + .into_values() + .map(|(when, place, envelope, user)| { + at = at.max(when); + (at, place, envelope, user) + }) + .collect(); for (path, (at, user)) in paths.into_iter().zip(ours) { if user.is_none() && others_entry(&path, node) { continue; @@ -182,10 +191,10 @@ pub(crate) fn replay_newest( let mut refused: HashSet<Vec<String>> = HashSet::new(); let mut links = links.into_iter().peekable(); for ((at, user), paths) in by_time { - while let Some(((when, _), _)) = links.peek() + while let Some((when, ..)) = links.peek() && *when <= at { - let ((when, _), (place, envelope, signer)) = links.next().expect("peeked"); + let (when, place, envelope, signer) = links.next().expect("peeked"); write_link( dst, epoch, @@ -237,7 +246,7 @@ pub(crate) fn replay_newest( } } } - for ((when, _), (place, envelope, signer)) in links { + for (when, place, envelope, signer) in links { write_link( dst, epoch, @@ -393,10 +402,14 @@ fn signed_places( (places, rest) } +/// A link to write: its time, its place, the envelope and its signer. +type Link = (i64, Vec<String>, String, String); + /// What replaying a signed place takes. enum Chain { - /// The envelopes to write, in order, each with its change's time and its signer. - Links(Vec<(i64, String, String)>), + /// The envelopes to write, in order, each with where its change is among those + /// replayed (`between`), its time and its signer. + Links(Vec<(usize, i64, String, String)>), /// The new document holds as high a `seq` there already. Held, /// No chain leads there from what the new document holds: why. @@ -433,9 +446,10 @@ fn chain( { return Chain::Held; } - // Every envelope the changes left at the place, by its digest, with its time. - let mut known: HashMap<String, (i64, String)> = HashMap::new(); - for hash in changes { + // Every envelope the changes left at the place, by its digest, with where its first + // change is among them and its time. + let mut known: HashMap<String, (usize, i64, String)> = HashMap::new(); + for (made, hash) in changes.iter().enumerate() { let wrote = store::changed_by(src, hash, InLists::Whole) .is_some_and(|paths| paths.iter().any(|path| path == place)); let Some(at) = wrote @@ -452,7 +466,7 @@ fn chain( && envelope::read(&text).is_ok() { let digest = envelope::digest(Some(&text)); - known.entry(digest).or_insert((time, text)); + known.entry(digest).or_insert((made, time, text)); } } } @@ -463,16 +477,16 @@ fn chain( let Ok(payload) = envelope::read(¤t) else { return Chain::Broken("a link of its chain isn't a value its user signed".to_owned()); }; - let time = known + let (made, time) = known .get(&envelope::digest(Some(¤t))) - .map_or(0, |(time, _)| *time); + .map_or((changes.len(), 0), |(made, time, _)| (*made, *time)); let prev = payload.prev.clone(); - links.push((time, current, payload.user)); + links.push((made, time, current, payload.user)); if prev == from { break; } match known.get(&prev) { - Some((_, before)) if links.len() <= known.len() => current = before.clone(), + Some((_, _, before)) if links.len() <= known.len() => current = before.clone(), _ => { return Chain::Broken( "the new epoch holds another value there, not one it replaced".to_owned(), @@ -481,6 +495,12 @@ fn chain( } } links.reverse(); + // Each after the one it replaces, as written. + let mut made = 0; + for link in &mut links { + made = made.max(link.0); + link.0 = made; + } Chain::Links(links) } @@ -506,23 +526,51 @@ fn judged( } /// The changes of `doc` after `before` up to `after`: those `after` builds on that -/// `before` doesn't. +/// `before` doesn't, each after those it builds on; of changes neither builds on, the +/// earlier by its clock first, then the lower hash. fn between(doc: &Document, before: &[ChangeHash], after: &[ChangeHash]) -> Vec<ChangeHash> { - let deps: HashMap<ChangeHash, Vec<ChangeHash>> = doc + let all: HashMap<ChangeHash, (i64, Vec<ChangeHash>)> = doc .get_changes(before) .iter() - .map(|change| (change.hash(), change.deps().to_vec())) + .map(|change| (change.hash(), (change.timestamp(), change.deps().to_vec()))) .collect(); let mut found = HashSet::new(); let mut todo: Vec<ChangeHash> = after.to_vec(); while let Some(hash) = todo.pop() { - if let Some(parents) = deps.get(&hash) + if let Some((_, parents)) = all.get(&hash) && found.insert(hash) { todo.extend(parents.iter().copied()); } } - found.into_iter().collect() + let mut waiting: HashMap<ChangeHash, usize> = HashMap::new(); + let mut builders: HashMap<ChangeHash, Vec<ChangeHash>> = HashMap::new(); + let mut ready: BTreeSet<(i64, ChangeHash)> = BTreeSet::new(); + for hash in &found { + let (time, parents) = &all[hash]; + let inside: Vec<&ChangeHash> = parents.iter().filter(|p| found.contains(*p)).collect(); + for parent in &inside { + builders.entry(**parent).or_default().push(*hash); + } + if inside.is_empty() { + ready.insert((*time, *hash)); + } else { + waiting.insert(*hash, inside.len()); + } + } + let mut ordered = Vec::with_capacity(found.len()); + while let Some((_, hash)) = ready.pop_first() { + ordered.push(hash); + for builder in builders.remove(&hash).unwrap_or_default() { + let left = waiting.get_mut(&builder).expect("waits for its parents"); + *left -= 1; + if *left == 0 { + waiting.remove(&builder); + ready.insert((all[&builder].0, builder)); + } + } + } + ordered } /// A change's time, the user it names (`replica::user_of`), and the store paths it @@ -1105,11 +1153,20 @@ mod tests { } fn signed_after(key: &ed25519_dalek::SigningKey, prev: Option<&str>, value: i64) -> String { + signed_at(key, "config", prev, value) + } + + fn signed_at( + key: &ed25519_dalek::SigningKey, + place: &str, + prev: Option<&str>, + value: i64, + ) -> String { use crate::access::sshsig; let payload = crate::document::signed::Payload { value: json!(value), swarm: "s".to_owned(), - path: vec!["config".to_owned()], + path: vec![place.to_owned()], user: "alice".to_owned(), at: 1, seq: prev.and_then(envelope::seq).map_or(0, |seq| seq + 1), @@ -1120,8 +1177,12 @@ mod tests { } fn alice_writes(doc: &mut Document, at: i64, envelope: &str) { + alice_writes_at(doc, at, "config", envelope); + } + + fn alice_writes_at(doc: &mut Document, at: i64, place: &str, envelope: &str) { let mut transaction = doc.transaction(); - store::write_path(&mut transaction, &["config".to_owned()], &json!(envelope)).unwrap(); + store::write_path(&mut transaction, &[place.to_owned()], &json!(envelope)).unwrap(); transaction.commit_with( automerge::transaction::CommitOptions::default() .with_time(at) @@ -1226,6 +1287,57 @@ mod tests { ); } + /// The links of several places replayed in the order their changes were made, each + /// after those it builds on, whatever the clocks say. + #[test] + fn signed_values_replay_in_the_order_written() { + use crate::access::{Right, sshsig}; + let path = |text: &str| -> Vec<String> { text.split('/').map(str::to_owned).collect() }; + let key = ed25519_dalek::SigningKey::from_bytes(&[7; 32]); + let mut old = strict_with(&key); + let mut alice = crate::access::registry::entry( + "root", + 1, + &[ + (path("config"), &[Right::Write][..]), + (path("other"), &[Right::Write][..]), + ], + ); + alice["keys"] = json!({ "k": sshsig::PublicKey(key.verifying_key().to_bytes()).line() }); + change(&mut old, |doc| { + store::write_path( + doc, + &path("_continuum/access/userSigned"), + &json!([["config"], ["other"]]), + ) + .unwrap(); + store::write_path(doc, &path("_continuum/users/alice"), &alice).unwrap(); + }); + let base = old.get_heads(); + let mut replayed = old.clone().with_actor(automerge::ActorId::random()); + let since = replayed.get_heads(); + // The second made after the first, by a clock that is behind. + alice_writes_at(&mut old, 50, "config", &signed_at(&key, "config", None, 1)); + alice_writes_at(&mut old, 10, "other", &signed_at(&key, "other", None, 2)); + let stats = replay_newest( + &old, + &base, + &old.get_heads(), + &mut replayed, + crate::document::replica::Epoch::GENESIS, + "node", + &Translator::default(), + Superseded::Drop, + ); + assert!(stats.quarantined.is_empty(), "{:?}", stats.quarantined); + let written: Vec<Vec<Vec<String>>> = replayed + .get_changes(&since) + .iter() + .filter_map(|change| store::changed_by(&replayed, &change.hash(), InLists::Whole)) + .collect(); + assert_eq!(written, [vec![path("config")], vec![path("other")]]); + } + /// The first group refused: those after it still replayed, still the node's (a /// fork, taking the refused one back, has no author of its own). #[test] |
