diff options
| author | tv <tv@krebsco.de> | 2026-11-13 17:06:37 +0000 |
|---|---|---|
| committer | tv <tv@krebsco.de> | 2026-11-13 17:06:37 +0000 |
| commit | f6a5c50e0f24736e48c96e9f7a0d14e9d7474b2d (patch) | |
| tree | 4f8c454ac4293fc2ca29092cc19f7753c7e5887f /src | |
| parent | 96b4ae2984e7b0b1d9970acbb20b9165b1e3f2f0 (diff) | |
hyparview: a member with k takes one a neighbour short
A member one neighbour short asks once per `ONE_SHORT_EVERY` (300 s), and a
member with `k` refused it. When a member most others had as a neighbour
went away, three members ended up each with the other two as neighbours,
one short each; each asked once, was refused by a full member, and waited
five minutes. Changes pass only between neighbours: the three got none of
what was written meanwhile (`active_views_settle_and_heal`, timed out
waiting for the same heads).
NEIGHBOUR says now whether its sender is one short, and a member with `k`
takes such an ask as its `k + 1`th, the most it keeps; one with `k + 1`
still refuses. Asks stay as rare as they were, and one is enough but where
those asked have `k + 1`. Wire version 50.
Diffstat (limited to 'src')
| -rw-r--r-- | src/swarm/hyparview.rs | 27 | ||||
| -rw-r--r-- | src/transport/mod.rs | 4 | ||||
| -rw-r--r-- | src/transport/wire.rs | 3 |
3 files changed, 24 insertions, 10 deletions
diff --git a/src/swarm/hyparview.rs b/src/swarm/hyparview.rs index 004f528..1f2bdc6 100644 --- a/src/swarm/hyparview.rs +++ b/src/swarm/hyparview.rs @@ -7,7 +7,10 @@ //! link both ends agreed to (NEIGHBOUR, answered by NEIGHBOUR_REPLY), not one every //! node computes alike. A node with fewer asks others from its passive view, one at a //! time per missing neighbour; one that has none asks with high priority, and is taken -//! even where that means dropping another (told so: DISCONNECT). One left with none +//! even where that means dropping another (told so: DISCONNECT). One a neighbour short +//! says so, and a member with `k` takes it as its `k + 1`th, the most it keeps: else +//! a few members one short each, neighbours of each other, would ask only members with +//! `k`, be refused, and stay an island (`ONE_SHORT_EVERY`). One left with none //! (dropped so itself) while its asks are low ones has one of them, or another, made //! high at once, even of a member that refused before. A neighbour that fails //! (judged unreachable: unanswered HELLOs, dormant, not alive lately) leaves the active @@ -52,8 +55,9 @@ const ASK_FOR: Duration = Duration::from_secs(20); const REFUSED_FOR: Duration = Duration::from_secs(60); /// A member one neighbour short asks this seldom: in a swarm whose members mostly have -/// `k`, those that refuse are full, and asking each in turn kept NEIGHBOURs going in a -/// quiet swarm (up to 300 in 20 s at 50 members). Two or more short, it asks at once. +/// `k`, asking each in turn kept NEIGHBOURs going in a quiet swarm (up to 300 in 20 s +/// at 50 members). Two or more short, it asks at once. A member with `k` takes it (it +/// says it is one short), so one ask is enough but where those asked have `k + 1`. const ONE_SHORT_EVERY: Duration = Duration::from_secs(300); /// Each neighbour is asked again this often whether it still is (NEIGHBOUR, as a new @@ -196,7 +200,7 @@ impl Topology for HyParView { let reachable = Self::reachable_members(&local, inputs); let now = Instant::now(); let mut to_leave = Vec::new(); - let (changed, to_ask) = { + let (changed, to_ask, one_short) = { let mut views = self.views.lock_or_recover(); let mut changed = false; // Told all the same: one we judge unreachable may only be silent towards @@ -331,7 +335,9 @@ impl Topology for HyParView { views.reaffirmed = Some(now); to_ask.extend(views.active.iter().map(|member| (member.clone(), false))); } - (changed, to_ask) + // Said with each ask: a member with `k` takes one a neighbour short. + let one_short = !views.active.is_empty() && views.active.len() + 1 == inputs.k; + (changed, to_ask, one_short) }; if changed { self.version.fetch_add(1, Ordering::Relaxed); @@ -364,6 +370,7 @@ impl Topology for HyParView { epoch, epoch_seq, high, + one_short: one_short && !high, }), ) .await; @@ -378,9 +385,13 @@ impl Topology for HyParView { let mut views = self.views.lock_or_recover(); if views.active.contains(peer) { (true, None) - } else if request.high || views.active.len() < k { - // Full: room made by dropping another, at random. - let dropped = if views.active.len() >= k { + } else if request.high + || views.active.len() < k + || (request.one_short && views.active.len() == k) + { + // Full, and asked with high priority: room made by dropping + // another, at random. One a neighbour short is our `k + 1`th. + let dropped = if request.high && views.active.len() >= k { let others: Vec<String> = views.active.iter().cloned().collect(); let dropped = some_of(others, 1).pop(); if let Some(dropped) = &dropped { diff --git a/src/transport/mod.rs b/src/transport/mod.rs index 2778ed7..e366f72 100644 --- a/src/transport/mod.rs +++ b/src/transport/mod.rs @@ -488,7 +488,8 @@ pub(crate) struct TreeLink { /// NEIGHBOUR: the sender asks the recipient to be neighbours (`swarm::hyparview`), as /// HyParView's NEIGHBOR; `high` when the sender has none (then the recipient makes room -/// if it must). +/// if it must), `one_short` when it has one less than `k` (then a recipient with `k` +/// takes it as its `k + 1`th). #[derive(Debug, Clone, Serialize, Deserialize)] pub(crate) struct NeighbourRequest { #[serde(with = "crate::transport::wire::codec::epoch")] @@ -496,6 +497,7 @@ pub(crate) struct NeighbourRequest { /// See `SyncEnvelope::epoch_seq`. pub(crate) epoch_seq: u32, pub(crate) high: bool, + pub(crate) one_short: bool, } /// NEIGHBOUR_REPLY (whether the recipient of a NEIGHBOUR agreed) and DISCONNECT (never diff --git a/src/transport/wire.rs b/src/transport/wire.rs index 3b67a74..c0db2e2 100644 --- a/src/transport/wire.rs +++ b/src/transport/wire.rs @@ -14,7 +14,7 @@ use super::{EncodedMessage, MessageKind, ParsedMessage}; /// The wire format's version, the first byte of every payload. Bump it with every change /// to a message type or a codec (`golden_bytes` fails then). -pub(crate) const VERSION: u8 = 49; +pub(crate) const VERSION: u8 = 50; /// What the second byte of a payload says. fn tag(kind: MessageKind) -> u8 { @@ -534,6 +534,7 @@ pub(crate) fn samples() -> Vec<ParsedMessage> { epoch, epoch_seq: 1, high: true, + one_short: false, }), ParsedMessage::NeighbourReply(crate::transport::NeighbourAnswer { epoch, |
