aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/swarm/hyparview.rs27
-rw-r--r--src/transport/mod.rs4
-rw-r--r--src/transport/wire.rs3
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,