diff options
| -rw-r--r-- | docs/dashboard.md | 5 | ||||
| -rw-r--r-- | src/api/dashboard/clocks.rs | 127 | ||||
| -rw-r--r-- | src/api/dashboard/dashboard.html | 51 | ||||
| -rw-r--r-- | src/api/dashboard/mod.rs | 15 |
4 files changed, 53 insertions, 145 deletions
diff --git a/docs/dashboard.md b/docs/dashboard.md index 80e9c19..5a66afd 100644 --- a/docs/dashboard.md +++ b/docs/dashboard.md @@ -77,8 +77,9 @@ Every member of the swarm, by alias (or a shortened node ID): * **Red outline**: this node holds it dormant (it has been silent, or said farewell). * **Dashed orange ring**: its clock is off the swarm's: it differs from the median of the members' clocks by more than `--clock-skew-warn`, beyond what the measurements - allow. The members report their peers' clocks with their links, so this works for - members this node doesn't reach itself; it needs three members compared. + allow. The page compares the clocks the reports on the map carry: this node's peers', + and the peers' of the nodes you subscribe to, so subscribing reaches members this node + doesn't; it needs three members compared. * **Amber**: it coordinates a remake of this node's epoch (then also with a golden halo, below), or voted for one, while that remake is open: voting, or committed until the member switched. A small amber breath as a remake is proposed (its coordinator) diff --git a/src/api/dashboard/clocks.rs b/src/api/dashboard/clocks.rs deleted file mode 100644 index 9f069be..0000000 --- a/src/api/dashboard/clocks.rs +++ /dev/null @@ -1,127 +0,0 @@ -//! Every member's clock against the swarm's, for the map: from the clocks each member -//! reports of its peers (`Link::clock`), chained from this node along the narrowest -//! bounds, then taken against their median. A member is off when it differs from the -//! median beyond its chained bound and the limit (`--clock-skew-warn`); with fewer than -//! three members compared, none is (two can't tell whose clock is off). An estimate for -//! the eye: each node judges its own clock by its peers' (`swarm::skew`). - -use std::cmp::Reverse; -use std::collections::{BTreeMap, BinaryHeap, HashMap}; - -use serde::Serialize; - -use crate::transport::Link; - -/// A member's clock against the swarm's. -#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)] -#[serde(rename_all = "camelCase")] -pub(super) struct MemberClock { - /// How far it is ahead of the median (behind if negative). - pub(super) offset_ms: i64, - /// Give or take: the bounds chained to it from this node. - pub(super) within_ms: u64, - pub(super) off: bool, -} - -/// From `local` and `reports` (each member's links), with `limit_ms`; by member. -pub(super) fn swarm<'a>( - local: &str, - reports: impl IntoIterator<Item = (&'a str, &'a [Link])>, - limit_ms: u64, -) -> BTreeMap<String, MemberClock> { - // Each way between two members: how far the far end's clock is ahead, give or take. - let mut edges: HashMap<&str, Vec<(&str, i64, u64)>> = HashMap::new(); - for (reporter, links) in reports { - for link in links { - if let Some(clock) = link.clock { - edges.entry(reporter).or_default().push(( - link.peer.as_str(), - clock.offset_ms, - clock.within_ms, - )); - edges.entry(link.peer.as_str()).or_default().push(( - reporter, - -clock.offset_ms, - clock.within_ms, - )); - } - } - } - // Ahead of this node's, along the narrowest chained bounds (Dijkstra). - let mut reached: HashMap<&str, (i64, u64)> = HashMap::new(); - let mut queue = BinaryHeap::from([Reverse((0_u64, local, 0_i64))]); - while let Some(Reverse((within, member, offset))) = queue.pop() { - if reached.contains_key(member) { - continue; - } - reached.insert(member, (offset, within)); - for &(next, step, step_within) in edges.get(member).into_iter().flatten() { - if !reached.contains_key(next) { - queue.push(Reverse(( - within.saturating_add(step_within), - next, - offset.saturating_add(step), - ))); - } - } - } - let mut offsets: Vec<i64> = reached.values().map(|(offset, _)| *offset).collect(); - offsets.sort_unstable(); - let median = offsets.get(offsets.len() / 2).copied().unwrap_or(0); - let judged = reached.len() >= 3 && limit_ms > 0; - reached - .into_iter() - .map(|(member, (offset, within))| { - let offset_ms = offset - median; - let off = judged && offset_ms.unsigned_abs() > within.saturating_add(limit_ms); - ( - member.to_owned(), - MemberClock { - offset_ms, - within_ms: within, - off, - }, - ) - }) - .collect() -} - -#[cfg(test)] -mod tests { - use super::*; - use crate::transport::paths::ClockOffset; - - fn link(peer: &str, offset_ms: i64) -> Link { - Link { - peer: peer.into(), - transport: None, - relayed: false, - down: false, - rtt_us: None, - dormant: false, - others: Vec::new(), - clock: Some(ClockOffset { - offset_ms, - within_ms: 20, - }), - } - } - - /// Chained through the reports: the one clock 10 s ahead is off, wherever it is. - #[test] - fn the_odd_clock_out() { - // a – b – c – d, d's clock 10 s ahead; a only knows b. - let a = [link("b", 0)]; - let b = [link("a", 0), link("c", 5)]; - let c = [link("d", 10_000)]; - let clocks = swarm("a", [("a", &a[..]), ("b", &b[..]), ("c", &c[..])], 2_000); - assert_eq!(clocks.len(), 4); - assert!(clocks["d"].off); - assert!(clocks["d"].offset_ms > 9_900); - assert!(!clocks["a"].off && !clocks["b"].off && !clocks["c"].off); - assert_eq!(clocks["d"].within_ms, 60); - // Two alone: none. - let two = swarm("a", [("a", &[link("b", 10_000)][..])], 2_000); - assert!(two.values().all(|clock| !clock.off)); - } -} diff --git a/src/api/dashboard/dashboard.html b/src/api/dashboard/dashboard.html index 3f02a64..5b776cd 100644 --- a/src/api/dashboard/dashboard.html +++ b/src/api/dashboard/dashboard.html @@ -546,6 +546,52 @@ function name(id) { } // Milliseconds as signed seconds: "+5.0 s". const seconds = ms => (ms < 0 ? "−" : "+") + (Math.abs(ms) / 1000).toFixed(1) + " s"; +// Every member's clock against the swarm's, for the map: from the clocks the reports +// carry of their peers (`clock` on each link: this node's own and subscribed nodes'), +// chained from this node along the narrowest bounds, then taken against their median. +// A member is off when it differs from the median beyond its chained bound and the +// limit (`--clock-skew-warn`); with fewer than three members compared, none is (two +// can't tell whose clock is off). An estimate for the eye: each node judges its own +// clock by its peers' (`clock-warning`). By member: { offsetMs, withinMs, off }. +function swarmClocks() { + // Each way between two members: how far the far end's clock is ahead, give or take. + const edges = new Map(); + const edge = (from, to, offset, within) => { + if (!edges.has(from)) edges.set(from, []); + edges.get(from).push([to, offset, within]); + }; + for (const [reporter, report] of Object.entries(state.graph.measured)) { + for (const link of report.links || []) { + if (!link.clock) continue; + edge(reporter, link.peer, link.clock.offsetMs, link.clock.withinMs); + edge(link.peer, reporter, -link.clock.offsetMs, link.clock.withinMs); + } + } + // Ahead of this node's, along the narrowest chained bounds (Dijkstra; the maps are small). + const reached = new Map(), queue = [[0, state.node.id, 0]]; + while (queue.length) { + let next = 0; + for (let i = 1; i < queue.length; i++) if (queue[i][0] < queue[next][0]) next = i; + const [within, member, offset] = queue.splice(next, 1)[0]; + if (reached.has(member)) continue; + reached.set(member, { offset, within }); + for (const [to, step, stepWithin] of edges.get(member) || []) { + if (!reached.has(to)) queue.push([within + stepWithin, to, offset + step]); + } + } + const offsets = [...reached.values()].map(r => r.offset).sort((a, b) => a - b); + const median = offsets[Math.floor(offsets.length / 2)] || 0; + const limit = (state.stats.clock || {}).limitMs || 0; + const judged = reached.size >= 3 && limit > 0; + const clocks = {}; + for (const [member, { offset, within }] of reached) { + const offsetMs = offset - median; + clocks[member] = { offsetMs, withinMs: within, + off: judged && Math.abs(offsetMs) > within + limit }; + } + return clocks; +} + // Whether `clock` (a peer's, `/peers`) differs from this node's beyond the limit for sure. function clockOff(clock) { const limit = (state.stats.clock || {}).limitMs || 0; @@ -1391,6 +1437,7 @@ function renderGraph() { // Above the lines and their labels, below the nodes. children.push(...hits); const { amber, coordinating } = inRemakes(); + const clocks = swarmClocks(); for (const id of nodes) { const p = positions.get(id), member = state.graph.members[id]; const reported = id in state.graph.measured; @@ -1411,7 +1458,7 @@ function renderGraph() { hoverable(element, id); }; // A clock off the swarm's: a dashed orange ring. - if (((state.graph.clocks || {})[id] || {}).off) { + if ((clocks[id] || {}).off) { children.push(drawing("clock " + id, "circle", { cx: p.x, cy: p.y, r: 11, fill: "none", stroke: "var(--warn)", "stroke-width": 1.5, "stroke-dasharray": "3 2" })); } @@ -1451,7 +1498,7 @@ function renderGraph() { stroke: dormant ? "var(--bad)" : voting ? AMBER : ring ? (following.status === "live" ? "var(--self)" : "var(--muted)") : member.self ? "var(--self)" : "var(--fg)", "stroke-width": dormant ? 2.5 : ring ? radius * 2 / 3 : 1.5 }, pressed); // Its clock against the swarm's, as the members' reports chain it (the node's). - const clock = ((state.graph.clocks || {})[id]); + const clock = clocks[id]; tooltip(circle, id + (reported ? "" : " (no links reported)") + (following ? (following.status === "live" ? " (subscribed)" : " (subscribed, not reached from here: " + following.why + ")") : "") + diff --git a/src/api/dashboard/mod.rs b/src/api/dashboard/mod.rs index e86475f..78e8352 100644 --- a/src/api/dashboard/mod.rs +++ b/src/api/dashboard/mod.rs @@ -15,10 +15,7 @@ //! member tells of a change as it happens; the same answers for all clients. Or, if //! asked (`POST /admin/dashboard/links?live=false`, for every client, until asked //! otherwise or the node restarts), only asked every `LINKS_EVERY`, without -//! subscribing: fewer messages in the swarm, a map up to `LINKS_EVERY` behind. With -//! the clocks the links carry, every member's clock against the swarm's (`clocks`). - -mod clocks; +//! subscribing: fewer messages in the swarm, a map up to `LINKS_EVERY` behind. use std::collections::{BTreeMap, BTreeSet}; use std::convert::Infallible; @@ -396,15 +393,6 @@ async fn build(state: &AppState, graph: &Graph, live: bool) -> JsonValue { "epoch": epoch_json(epochs.get(member).copied()) }), ); } - let clocks = clocks::swarm( - local, - std::iter::once((local, &own[..])).chain( - replies - .iter() - .map(|(member, _, member_links)| (member.as_str(), &member_links[..])), - ), - u64::try_from(state.clock_skew_warn.as_millis()).unwrap_or(u64::MAX), - ); // Everyone on the map: in the member list's graph, measured, or at the other end of // a link measured. A node that joined through others is linked to them before its // registration reaches this node, and before the graph is computed again @@ -435,7 +423,6 @@ async fn build(state: &AppState, graph: &Graph, live: bool) -> JsonValue { "members": members_json, "intended": intended, "measured": measured, - "clocks": clocks, "live": live, }, "remakes": remakes, |