aboutsummaryrefslogtreecommitdiffstats
path: root/src/remake
diff options
context:
space:
mode:
Diffstat (limited to 'src/remake')
-rw-r--r--src/remake/catchup.rs88
-rw-r--r--src/remake/switch.rs23
2 files changed, 108 insertions, 3 deletions
diff --git a/src/remake/catchup.rs b/src/remake/catchup.rs
index e7184be..4f98d7a 100644
--- a/src/remake/catchup.rs
+++ b/src/remake/catchup.rs
@@ -128,6 +128,20 @@ pub(super) async fn check<H: Host>(host: &H) {
.filter(|(_, count)| *count >= required)
.collect();
+ // Holding a store, of two epochs decided for one, a node follows the lower ID
+ // (`docs/store.md`, Remakes); elsewhere, the one more peers are on.
+ #[cfg(feature = "federation")]
+ let lowest = host
+ .read_doc(|doc| {
+ matches!(
+ crate::access::policy::of(doc),
+ crate::access::policy::Policy::Store(_)
+ )
+ })
+ .await;
+ #[cfg(not(feature = "federation"))]
+ let lowest = false;
+
let mut aside = false;
let target = match corroborated.iter().map(|(epoch, _)| epoch.generation).max() {
Some(generation) => {
@@ -136,8 +150,14 @@ pub(super) async fn check<H: Host>(host: &H) {
.filter(|(epoch, _)| epoch.generation == generation)
.collect();
// Several epochs of the newest generation (two remakes committed for one
- // epoch): the one most peers are on, as `sideways` would pick.
- let target = most_followed(&targets).expect("corroborated has this generation");
+ // epoch): the one most peers are on, as `sideways` would pick; holding a
+ // store, the lowest ID.
+ let target = if lowest {
+ lowest_id(&targets)
+ } else {
+ most_followed(&targets)
+ }
+ .expect("corroborated has this generation");
if targets.len() > 1 {
let listed: Vec<String> =
targets.iter().map(|(epoch, _)| epoch.to_string()).collect();
@@ -152,7 +172,15 @@ pub(super) async fn check<H: Host>(host: &H) {
required, "A newer epoch is advertised, but not by enough peers yet"
);
}
- let sideways = ready.then(|| sideways(local, &serving, required)).flatten();
+ let sideways = ready
+ .then(|| {
+ if lowest {
+ lower(local, &serving, required)
+ } else {
+ sideways(local, &serving, required)
+ }
+ })
+ .flatten();
let Some(target) = sideways else {
if host.remake().catch_up().is_some() {
host.remake().set_catch_up(None);
@@ -212,6 +240,32 @@ fn sideways(local: Epoch, serving: &[(String, Epoch)], required: usize) -> Optio
most_followed(&others)
}
+/// For a ready node holding a store, another epoch of its own generation with a lower ID
+/// than its own that `required` peers are on, the lowest: of two epochs decided for one,
+/// a node follows the lower ID, and a node on the other rejoins it (`docs/store.md`,
+/// Remakes), however many are on each.
+fn lower(local: Epoch, serving: &[(String, Epoch)], required: usize) -> Option<Epoch> {
+ let mut counts: HashMap<Epoch, usize> = HashMap::new();
+ for (_, epoch) in serving {
+ if epoch.generation == local.generation && epoch.id < local.id {
+ *counts.entry(*epoch).or_default() += 1;
+ }
+ }
+ let lower: Vec<(Epoch, usize)> = counts
+ .into_iter()
+ .filter(|(_, count)| *count >= required)
+ .collect();
+ lowest_id(&lower)
+}
+
+/// Of epochs, the one with the lowest ID.
+fn lowest_id(epochs: &[(Epoch, usize)]) -> Option<Epoch> {
+ epochs
+ .iter()
+ .map(|(epoch, _)| *epoch)
+ .min_by_key(|epoch| epoch.id)
+}
+
/// Of epochs with how many peers are on each, the one most are on; of those, the one
/// with the lowest ID, so every node picks the same.
fn most_followed(epochs: &[(Epoch, usize)]) -> Option<Epoch> {
@@ -745,6 +799,34 @@ mod tests {
assert_eq!(sideways(ours, &serving, 2), Some(theirs));
}
+ /// Holding a store: of two epochs of the local generation, the lower ID, however many
+ /// peers are on each; a higher one isn't followed.
+ #[test]
+ fn holding_a_store_a_node_follows_the_lower_epoch() {
+ let epoch = |id: u8| Epoch {
+ generation: 1,
+ id: [id; 32],
+ };
+ let (low, ours, high) = (epoch(1), epoch(5), epoch(9));
+ let on = |peers: &[(&str, Epoch)]| -> Vec<(String, Epoch)> {
+ peers
+ .iter()
+ .map(|(peer, epoch)| ((*peer).to_owned(), *epoch))
+ .collect()
+ };
+ let serving = on(&[
+ ("a", ours),
+ ("b", ours),
+ ("c", ours),
+ ("d", low),
+ ("e", low),
+ ]);
+ assert_eq!(lower(ours, &serving, 2), Some(low));
+ assert_eq!(lower(ours, &on(&[("d", low)]), 2), None);
+ assert_eq!(lower(ours, &on(&[("d", high), ("e", high)]), 2), None);
+ assert_eq!(lowest_id(&[(high, 3), (low, 1)]), Some(low));
+ }
+
/// An old-epoch document with one own change after the base, and the swarm's
/// document of the next epoch (snapshot plus one foreign change).
fn scenario(policy: &JsonValue) -> (Document, Document, Epoch) {
diff --git a/src/remake/switch.rs b/src/remake/switch.rs
index 657b0f5..e56cd8c 100644
--- a/src/remake/switch.rs
+++ b/src/remake/switch.rs
@@ -117,6 +117,29 @@ async fn check<H: Host>(host: &H) {
return catchup::check(host).await;
}
[(id, record)] => (id.clone(), record.clone()),
+ // Holding a store, of two epochs decided for one, the lower ID (`docs/store.md`,
+ // Remakes).
+ #[cfg(feature = "federation")]
+ several
+ if host
+ .read_doc(|doc| {
+ matches!(
+ crate::access::policy::of(doc),
+ crate::access::policy::Policy::Store(_)
+ )
+ })
+ .await =>
+ {
+ let lowest = several
+ .iter()
+ .filter(|(_, record)| !record.contested)
+ .min_by_key(|(_, record)| record.committed_epoch().map(|epoch| epoch.id));
+ let Some((id, record)) = lowest else {
+ error!("Decisions on these remakes disagree; not switching on my own");
+ return catchup::check(host).await;
+ };
+ (id.clone(), record.clone())
+ }
several => {
// Majority voting prevents this; never guess which one is right. Peers
// that did switch can still be followed.