Something went wrong. Try again.
declarative relay deployment on hetzner relay-eval.waow.tech
atproto relay
Something went wrong. Try again.
11 kB · 239 lines
Zig
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240//! quorum-union coverage math.//!//! the eval denominator is the set of DIDs the network *agrees* are active —//! DIDs seen by at least `quorum` relays — rather than the raw union, which a//! single flooding relay (e.g. one emitting a large set of DIDs no other relay//! carries) can inflate, cratering every other relay's reported coverage.//!//! to keep history continuous and the quorum a query-time choice, each run//! stores a per-relay *overlap histogram* instead of a single deflated number://! `hist[k-1]` = count of this relay's DIDs that exactly `k` relays saw in total.//! from the per-relay histograms of a run, coverage at any quorum is a re-sum://!//! N_k = (Σ_relay hist_relay[k]) / k // distinct DIDs seen by exactly k relays//! union(q) = Σ_{k≥q} N_k//! numerator(q) = Σ_{k≥q} hist_relay[k] // this relay's DIDs in the consensus set//! coverage(q) = numerator(q) / union(q)//!//! q=1 reproduces the raw union exactly (union(1) = total distinct DIDs,//! numerator(1) = this relay's total unique DIDs), so the stored q=1 history//! stays self-consistent and comparable.
const std = @import("std");
/// build a relay's overlap histogram from the global per-DID contributor counts/// of just the DIDs that relay saw. `num_relays` is the histogram length (the/// number of relays in the run); `seen_counts[i]` is how many relays in total/// saw the relay's i-th DID. result[k-1] = count of those DIDs with count == k./// caller owns the returned slice.pub fn buildHistogram(allocator: std.mem.Allocator, num_relays: usize, seen_counts: []const u16) ![]u32 { const hist = try allocator.alloc(u32, num_relays); @memset(hist, 0); for (seen_counts) |k| { if (k >= 1 and k <= num_relays) hist[k - 1] += 1; } return hist;}
/// this relay's DIDs that are in the consensus set (seen by ≥ quorum relays).pub fn numeratorAtQuorum(hist: []const u32, quorum: usize) u32 { const q = @max(quorum, 1); var sum: u32 = 0; var k = q; while (k <= hist.len) : (k += 1) sum += hist[k - 1]; return sum;}
/// the consensus-union size: distinct DIDs seen by ≥ quorum relays across the/// run, recovered from every relay's overlap histogram. each DID seen by/// exactly k relays appears in k of the histograms at bucket k, so dividing the/// per-k cross-relay sum by k recovers the distinct count.pub fn unionAtQuorum(hists: []const []const u32, quorum: usize) u32 { const q = @max(quorum, 1); var max_len: usize = 0; for (hists) |h| max_len = @max(max_len, h.len);
var total: u32 = 0; var k = q; while (k <= max_len) : (k += 1) { var s: u64 = 0; for (hists) |h| if (k <= h.len) { s += h[k - 1]; }; total += @intCast(s / k); } return total;}
/// serialize a histogram as a compact JSON array, e.g. "[2,1,3]". caller owns.pub fn formatHistogram(allocator: std.mem.Allocator, hist: []const u32) ![]u8 { var out: std.ArrayList(u8) = .empty; errdefer out.deinit(allocator); try out.append(allocator, '['); for (hist, 0..) |v, i| { if (i > 0) try out.append(allocator, ','); try out.print(allocator, "{d}", .{v}); } try out.append(allocator, ']'); return out.toOwnedSlice(allocator);}
/// parse a histogram written by formatHistogram. returns null for empty input/// (e.g. runs predating the overlap column) or malformed data; callers treat/// null as "no histogram → fall back to the raw q=1 union".pub fn parseHistogram(allocator: std.mem.Allocator, s: []const u8) ?[]u32 { const trimmed = std.mem.trim(u8, s, " \t\r\n"); if (trimmed.len < 2 or trimmed[0] != '[' or trimmed[trimmed.len - 1] != ']') return null; const inner = std.mem.trim(u8, trimmed[1 .. trimmed.len - 1], " ");
// note: a null return is not an error, so errdefer won't fire — free explicitly. var out: std.ArrayList(u32) = .empty; if (inner.len == 0) return out.toOwnedSlice(allocator) catch null;
var it = std.mem.splitScalar(u8, inner, ','); while (it.next()) |tok| { const v = std.fmt.parseInt(u32, std.mem.trim(u8, tok, " "), 10) catch { out.deinit(allocator); return null; }; out.append(allocator, v) catch { out.deinit(allocator); return null; }; } return out.toOwnedSlice(allocator) catch { out.deinit(allocator); return null; };}
// --- tests ---
const testing = std.testing;
test "buildHistogram buckets by contributor count" { // 6 DIDs: three seen by all 3 relays, one by 2, two singletons. const counts = [_]u16{ 3, 3, 3, 2, 1, 1 }; const hist = try buildHistogram(testing.allocator, 3, &counts); defer testing.allocator.free(hist); try testing.expectEqualSlices(u32, &[_]u32{ 2, 1, 3 }, hist);}
test "buildHistogram ignores out-of-range counts" { // a count of 0 (impossible for a DID the relay saw) or > num_relays is dropped. const counts = [_]u16{ 0, 2, 5 }; const hist = try buildHistogram(testing.allocator, 3, &counts); defer testing.allocator.free(hist); try testing.expectEqualSlices(u32, &[_]u32{ 0, 1, 0 }, hist);}
test "quorum union drops singletons; q=1 reproduces raw union" { // 3 relays. core = 100 DIDs all three saw. relay A floods 20 singletons. // relay B sees the 100 core + 0 extra. relay C sees 100 core + 0 extra. // so DIDs by contributor count: 100 seen by 3, 20 seen by 1 (A only). const a = [_]u32{ 20, 0, 100 }; // A: 20 singletons, 0 by-2, 100 by-3 const b = [_]u32{ 0, 0, 100 }; const c = [_]u32{ 0, 0, 100 }; const hists = [_][]const u32{ &a, &b, &c };
// q=1: raw union = 120 (100 core + 20 singletons) try testing.expectEqual(@as(u32, 120), unionAtQuorum(&hists, 1)); // q=2: consensus union = 100 (the singletons drop out) try testing.expectEqual(@as(u32, 100), unionAtQuorum(&hists, 2));
// numerators: at q=1 each relay's count is its total; at q=2 the flood is // stripped from A's numerator too — A is not credited for DIDs only it saw. try testing.expectEqual(@as(u32, 120), numeratorAtQuorum(&a, 1)); try testing.expectEqual(@as(u32, 100), numeratorAtQuorum(&a, 2)); try testing.expectEqual(@as(u32, 100), numeratorAtQuorum(&b, 2));
// coverage(q=2): every relay is 100/100 = 100%. the flood no longer craters // B and C the way 100/120 = 83% did under the raw union. try testing.expectEqual(numeratorAtQuorum(&b, 2), unionAtQuorum(&hists, 2));}
test "histogram round-trips through format/parse" { const hist = [_]u32{ 20, 0, 100, 7 }; const s = try formatHistogram(testing.allocator, &hist); defer testing.allocator.free(s); try testing.expectEqualStrings("[20,0,100,7]", s);
const back = parseHistogram(testing.allocator, s).?; defer testing.allocator.free(back); try testing.expectEqualSlices(u32, &hist, back);}
test "parseHistogram rejects empty and malformed input" { try testing.expect(parseHistogram(testing.allocator, "") == null); // old NULL rows try testing.expect(parseHistogram(testing.allocator, "garbage") == null); try testing.expect(parseHistogram(testing.allocator, "[1,x,3]") == null); // a well-formed empty array is valid (0-relay run), distinct from null. const empty = parseHistogram(testing.allocator, "[]").?; defer testing.allocator.free(empty); try testing.expectEqual(@as(usize, 0), empty.len);}
test "partial overlap: DIDs seen by exactly 2 of 3 relays" { // 50 DIDs all three saw; 30 DIDs seen by exactly relays A and B. const a = [_]u32{ 0, 30, 50 }; const b = [_]u32{ 0, 30, 50 }; const c = [_]u32{ 0, 0, 50 }; const hists = [_][]const u32{ &a, &b, &c };
try testing.expectEqual(@as(u32, 80), unionAtQuorum(&hists, 1)); // 50 + 30 try testing.expectEqual(@as(u32, 80), unionAtQuorum(&hists, 2)); // both groups ≥2 try testing.expectEqual(@as(u32, 50), unionAtQuorum(&hists, 3)); // only the core
// C carries 50 of the 80 consensus DIDs → it genuinely misses the 30 A+B saw. try testing.expectEqual(@as(u32, 50), numeratorAtQuorum(&c, 2)); try testing.expectEqual(@as(u32, 80), numeratorAtQuorum(&a, 2));}
// --- "behind lately" verdict ---//// the lay-visitor question is "is any relay behind?" — behind the *network*,// not behind its own recent baseline (that self-relative signal lives in the// /api/relays monitor). a relay is behind in a single run when it carried less// than `behind_run_threshold` of the consensus (quorum) union; it is "behind// lately" when that happened persistently across the recent window, so one bad// run doesn't flag and one good run doesn't clear.
/// per-run: behind when coverage of the quorum union falls below this fraction.pub const behind_run_threshold: f64 = 0.85;
/// minimum scored runs before a verdict is offered — "lately" implies history.pub const behind_min_runs: usize = 3;
/// was this relay behind in a single run? `dids` = its consensus numerator,/// `union_val` = the run's consensus union. a run with no usable union scores/// nobody.pub fn runIsBehind(dids: i64, union_val: i64) bool { if (union_val <= 0) return false; const ratio = @as(f64, @floatFromInt(dids)) / @as(f64, @floatFromInt(union_val)); return ratio < behind_run_threshold;}
/// window verdict: behind in at least a third of scored runs.pub fn isBehindLately(behind_runs: usize, total_runs: usize) bool { if (total_runs < behind_min_runs) return false; return behind_runs * 3 >= total_runs;}
test "runIsBehind thresholds" { try testing.expect(runIsBehind(0, 100)); // saw nothing try testing.expect(runIsBehind(84, 100)); // just below try testing.expect(!runIsBehind(85, 100)); // at threshold = keeping up try testing.expect(!runIsBehind(100, 100)); try testing.expect(!runIsBehind(120, 100)); // replay inflation isn't "behind" try testing.expect(!runIsBehind(0, 0)); // no union → no verdict}
test "isBehindLately requires persistence and history" { try testing.expect(!isBehindLately(1, 1)); // too little history try testing.expect(!isBehindLately(2, 2)); try testing.expect(isBehindLately(1, 3)); // 1/3 of runs is the floor try testing.expect(!isBehindLately(0, 24)); try testing.expect(!isBehindLately(7, 24)); // 7*3=21 < 24 try testing.expect(isBehindLately(8, 24)); // 8*3=24 ≥ 24 try testing.expect(isBehindLately(24, 24));}