diff options
| -rw-r--r-- | docs/topology.md | 5 | ||||
| -rw-r--r-- | src/swarm/hyparview.rs | 27 | ||||
| -rw-r--r-- | src/transport/mod.rs | 4 | ||||
| -rw-r--r-- | src/transport/wire.rs | 3 |
4 files changed, 28 insertions, 11 deletions
diff --git a/docs/topology.md b/docs/topology.md index 674eaed..1781157 100644 --- a/docs/topology.md +++ b/docs/topology.md @@ -32,7 +32,10 @@ can compute every other node's neighbours, writers' trees can be built on it. agreed to be one (NEIGHBOUR, NEIGHBOUR_REPLY, DISCONNECT), about `k` of them (5 unless `--neighbours` is set, the paper's size for up to about 10 000 members). Members that fail leave it, and others are asked; each neighbour is asked again every minute whether -it still is, so a link lost at one end (a lost DISCONNECT) doesn't stay at the other. The passive view, whom to ask, is drawn from the +it still is, so a link lost at one end (a lost DISCONNECT) doesn't stay at the other. A +member one neighbour short says so when it asks, and one with `k` takes it as its +`k + 1`th: a few members one short, neighbours of each other, would otherwise ask only +full members and stay an island. The passive view, whom to ask, is drawn from the member list, not from the paper's JOIN and SHUFFLE (`swarm::hyparview`). There is no graph every node shares: writers' trees, recorded links, indirect probes and the dashboard's intended links do nothing. 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, |
