1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
//! What each worker is like, right now.
//!
//! Every distribution here is chosen for one property: **its sufficient
//! statistics are additive**. A cell's summary is then the exact sum of its
//! members', so a mesh of millions of workers rolls up losslessly and no
//! broker ever has to hold — or ship — per-worker state for anyone else's
//! workers. Anything needing the original samples (raw histograms, medians)
//! is excluded by that rule.
//!
//! - service time → log-normal, statistics `(n, Σ ln x, Σ ln²x)`
//! - success, trust → Beta, statistics `(α, β)`
//!
//! Observations decay by a discount factor, so the estimate follows recent
//! behaviour rather than averaging over a worker's whole history.
/// Additive sufficient statistics for one worker (or one cell).
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Stats {
/// Observations, discounted — fractional, hence f64.
n: f64,
sum_log: f64,
sum_log_sq: f64,
successes: f64,
failures: f64,
verified: f64,
unverified: f64,
}
impl Default for Stats {
fn default() -> Self {
Self::new()
}
}
impl Stats {
pub fn new() -> Self {
Stats {
n: 0.0,
sum_log: 0.0,
sum_log_sq: 0.0,
successes: 0.0,
failures: 0.0,
verified: 0.0,
unverified: 0.0,
}
}
/// Record one completed request. `duration_ms` must be positive; a
/// non-positive or non-finite duration is not a measurement and is
/// ignored rather than poisoning the log-sums with NaN.
pub fn observe(&mut self, duration_ms: f64, success: bool) {
if success {
self.successes += 1.0;
} else {
self.failures += 1.0;
}
if duration_ms.is_finite() && duration_ms > 0.0 {
let l = duration_ms.ln();
self.n += 1.0;
self.sum_log += l;
self.sum_log_sq += l * l;
}
}
/// Record whether a request succeeded without its duration: for a
/// completion whose timing is known not to be representative, such as a
/// worker's first request, which pays its start-up cost (#438).
pub fn observe_outcome(&mut self, success: bool) {
self.observe(f64::NAN, success);
}
/// Record whether a returned result could be verified.
pub fn observe_trust(&mut self, verified: bool) {
match verified {
true => self.verified += 1.0,
false => self.unverified += 1.0,
}
}
/// Fold another summary in. This is what makes cell rollup exact: the
/// merge of two summaries equals the summary of the two sample sets.
pub fn merge(&mut self, other: &Stats) {
self.n += other.n;
self.sum_log += other.sum_log;
self.sum_log_sq += other.sum_log_sq;
self.successes += other.successes;
self.failures += other.failures;
self.verified += other.verified;
self.unverified += other.unverified;
}
/// Add `weight` pseudo-observations of service time drawn from `prior`'s
/// shape (its log-mean and log-spread), leaving success and trust alone.
///
/// This is a conjugate prior expressed in the same sufficient statistics:
/// `weight` observations at the prior's mean count exactly as much as
/// `weight` real ones would, so a worker with plenty of evidence barely
/// moves and one with a single observation is pulled most of the way.
/// A `prior` with nothing measured, or a non-positive `weight`, is a no-op.
pub fn with_service_prior(mut self, prior: &Stats, weight: f64) -> Stats {
if prior.n > 0.0 && weight > 0.0 && weight.is_finite() {
let f = weight / prior.n;
self.n += weight;
self.sum_log += prior.sum_log * f;
self.sum_log_sq += prior.sum_log_sq * f;
}
self
}
/// The service-time part of `self` with `other`'s taken out: the exact
/// inverse of [`Stats::merge`] for those three sums, so a pool's total
/// minus one member is the pool of the others, in O(1).
pub fn service_without(&self, other: &Stats) -> Stats {
Stats {
n: (self.n - other.n).max(0.0),
sum_log: self.sum_log - other.sum_log,
sum_log_sq: (self.sum_log_sq - other.sum_log_sq).max(0.0),
..Stats::new()
}
}
/// Age every observation by `factor` (0 < factor ≤ 1). One knob for how
/// fast the estimate forgets: a worker that was slow an hour ago and is
/// fast now should read as fast.
pub fn decay(&mut self, factor: f64) {
let f = factor.clamp(0.0, 1.0);
self.n *= f;
self.sum_log *= f;
self.sum_log_sq *= f;
self.successes *= f;
self.failures *= f;
self.verified *= f;
self.unverified *= f;
}
/// How many observations back this, after discounting.
pub fn weight(&self) -> f64 {
self.n
}
/// `None` until something has been measured — unknown is not zero, and
/// treating it as zero is what made an unmeasured worker rank as the
/// fastest one on the mesh.
pub fn median_service_ms(&self) -> Option<f64> {
(self.n > 0.0).then(|| (self.sum_log / self.n).exp())
}
/// The spread of log service time; `None` until two observations exist,
/// since one point has no spread to speak of.
pub fn log_sd(&self) -> Option<f64> {
if self.n < 2.0 {
return None;
}
let mean = self.sum_log / self.n;
let var = (self.sum_log_sq / self.n - mean * mean).max(0.0);
Some(var.sqrt())
}
/// Expected service time: the log-normal mean, `exp(μ + σ²/2)`, which sits
/// above the median because the distribution has a long right tail.
pub fn expected_service_ms(&self) -> Option<f64> {
let median = self.median_service_ms()?;
let sd = self.log_sd().unwrap_or(0.0);
Some(median * (sd * sd / 2.0).exp())
}
/// Posterior mean of the success rate, with a Beta(1,1) prior so a worker
/// with no history reads as 0.5 rather than as certain either way.
pub fn success_rate(&self) -> f64 {
(self.successes + 1.0) / (self.successes + self.failures + 2.0)
}
/// Posterior mean of the share of results that could be verified.
pub fn trust(&self) -> f64 {
(self.verified + 1.0) / (self.verified + self.unverified + 2.0)
}
/// Equal up to floating-point rounding. Merging is exact in real
/// arithmetic, but summing in a different order rounds differently, and
/// over a large fleet those roundings accumulate — which is why the
/// statistics are kept as sums rather than as running means.
#[cfg(test)]
pub(crate) fn close_to(&self, other: &Stats) -> bool {
let near = |a: f64, b: f64| (a - b).abs() <= 1e-9 * a.abs().max(b.abs()).max(1.0);
near(self.n, other.n)
&& near(self.sum_log, other.sum_log)
&& near(self.sum_log_sq, other.sum_log_sq)
&& near(self.successes, other.successes)
&& near(self.failures, other.failures)
&& near(self.verified, other.verified)
&& near(self.unverified, other.unverified)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn stats_of(samples: &[(f64, bool)]) -> Stats {
let mut s = Stats::new();
for (ms, ok) in samples {
s.observe(*ms, *ok);
}
s
}
/// The property the whole rollup rests on: a cell's summary must equal the
/// summary of its members' samples. Without it, "millions of workers" needs
/// per-worker state shipped across the mesh, which is the thing being
/// avoided.
/// A pool's total minus one member is the pool of the others, and a prior
/// of `w` pseudo-observations counts as `w` real ones at its median.
#[test]
fn a_service_prior_counts_as_that_many_observations_at_the_pool_median() {
let a = stats_of(&[(10.0, true), (10.0, true)]);
let b = stats_of(&[(1000.0, true)]);
let mut pool = a;
pool.merge(&b);
let others = pool.service_without(&b);
assert!((others.weight() - 2.0).abs() < 1e-9);
assert!((others.median_service_ms().unwrap() - 10.0).abs() < 1e-6);
// One observation at 1000 ms plus three pseudo-observations at 10 ms:
// the geometric mean of {1000, 10, 10, 10}.
let shrunk = b.with_service_prior(&others, 3.0);
assert!((shrunk.weight() - 4.0).abs() < 1e-9);
let want = (1000.0f64.ln() + 3.0 * 10.0f64.ln()) / 4.0;
assert!((shrunk.median_service_ms().unwrap().ln() - want).abs() < 1e-9);
// Success and trust are not part of the prior.
assert_eq!(shrunk.success_rate(), b.success_rate());
// Nothing to learn from: unchanged.
assert_eq!(b.with_service_prior(&Stats::new(), 3.0), b);
assert_eq!(b.with_service_prior(&others, 0.0), b);
}
#[test]
fn a_merged_summary_equals_the_summary_of_the_merged_samples() {
let left = [(10.0, true), (20.0, true), (40.0, false)];
let right = [(5.0, true), (80.0, true)];
let mut merged = stats_of(&left);
merged.merge(&stats_of(&right));
let together: Vec<(f64, bool)> = left.iter().chain(right.iter()).copied().collect();
let direct = stats_of(&together);
// Exact in real arithmetic; in floating point, addition is not
// associative, so the two differ by rounding (observed: 2 ULP). What
// must hold is that no information is lost, not that the bits match.
assert!(merged.close_to(&direct), "{merged:?} vs {direct:?}");
assert_eq!(merged.weight(), direct.weight());
assert_eq!(
merged.median_service_ms().map(|m| (m * 1e9).round()),
direct.median_service_ms().map(|m| (m * 1e9).round())
);
}
/// Hand-checkable: the log-normal's median is the geometric mean, and the
/// geometric mean of 1, 2, 4 and 8 is 64^(1/4) = 2.828…
#[test]
fn the_median_is_the_geometric_mean_of_what_was_seen() {
let s = stats_of(&[(1.0, true), (2.0, true), (4.0, true), (8.0, true)]);
let median = s.median_service_ms().expect("four observations");
assert!(
(median - 8f64.sqrt()).abs() < 1e-9,
"got {median}, want {}",
8f64.sqrt()
);
// The mean sits above the median: the distribution has a long tail.
assert!(s.expected_service_ms().unwrap() > median);
}
/// Unknown is not zero. Reading an unmeasured worker as 0 ms is what made
/// one that had never answered outrank a worker measured at 5 ms.
#[test]
fn nothing_measured_reads_as_unknown_not_as_instant() {
let empty = Stats::new();
assert_eq!(empty.median_service_ms(), None);
assert_eq!(empty.expected_service_ms(), None);
assert_eq!(empty.log_sd(), None);
assert_eq!(empty.weight(), 0.0);
// A coin-flip prior, not a verdict.
assert!((empty.success_rate() - 0.5).abs() < 1e-12);
assert!((empty.trust() - 0.5).abs() < 1e-12);
}
/// A worker that was slow and is now fast must read as fast, or the
/// estimate describes a machine that no longer exists.
#[test]
fn recent_behaviour_outweighs_old_behaviour() {
let mut s = Stats::new();
for _ in 0..50 {
s.observe(1000.0, true);
}
let before = s.median_service_ms().unwrap();
// The node got fast; each new observation ages the old ones.
for _ in 0..50 {
s.decay(0.8);
s.observe(10.0, true);
}
let after = s.median_service_ms().unwrap();
assert!(before > 900.0, "started slow: {before}");
assert!(after < 20.0, "followed the change: {after} (from {before})");
}
/// Decay must not quietly erase the record, or a worker would look
/// unmeasured again and be re-explored from nothing on every tick.
#[test]
fn decay_keeps_the_shape_of_what_was_learned() {
let mut s = stats_of(&[(10.0, true), (10.0, true), (10.0, false)]);
let median = s.median_service_ms().unwrap();
let rate = s.success_rate();
s.decay(0.5);
assert!((s.median_service_ms().unwrap() - median).abs() < 1e-9);
assert!(s.weight() > 0.0, "still measured");
// The rate moves toward the prior as evidence ages, but not past it.
assert!(s.success_rate() > 0.5 && s.success_rate() < rate + 1e-9);
}
/// A failure with no timing (a timeout) still counts against the success
/// rate, and must not poison the service-time statistics.
#[test]
fn a_timeout_counts_against_success_without_corrupting_the_timing() {
let mut s = stats_of(&[(10.0, true)]);
s.observe(f64::NAN, false);
s.observe(-1.0, false);
assert_eq!(s.weight(), 1.0, "only the real measurement timed");
assert!((s.median_service_ms().unwrap() - 10.0).abs() < 1e-9);
assert!(s.success_rate() < 0.5, "two failures against one success");
}
/// Small enough that a cell of 10k workers is well under a megabyte.
#[test]
fn a_worker_summary_stays_small() {
assert!(
std::mem::size_of::<Stats>() <= 64,
"{} bytes",
std::mem::size_of::<Stats>()
);
}
}
#[cfg(test)]
mod scale_tests {
use super::*;
/// The target is millions of workers. A cell's summary must cost the same
/// to read whether it covers ten workers or a million, and the per-worker
/// state must stay small enough to hold a whole cell in memory.
#[test]
fn a_million_workers_roll_up_into_one_summary_of_constant_size() {
let per_worker = std::mem::size_of::<Stats>();
assert!(per_worker <= 64, "{per_worker} bytes per worker");
// One cell of 10k workers, each with a handful of observations.
let mut cell = Stats::new();
for w in 0..10_000u32 {
let mut worker = Stats::new();
let ms = 5.0 + (w % 50) as f64;
worker.observe(ms, w % 97 != 0);
worker.observe(ms * 1.1, true);
cell.merge(&worker);
}
assert_eq!(cell.weight(), 20_000.0);
assert_eq!(
std::mem::size_of_val(&cell),
per_worker,
"still one summary"
);
// A hundred such cells is the million, and merging them is a hundred
// additions — not a million.
let mut mesh = Stats::new();
for _ in 0..100 {
mesh.merge(&cell);
}
assert_eq!(mesh.weight(), 2_000_000.0);
assert_eq!(std::mem::size_of_val(&mesh), per_worker);
let median = mesh.median_service_ms().expect("measured");
assert!(
(5.0..=60.0).contains(&median),
"the mesh-wide median is still meaningful: {median}"
);
}
}