1
/**
2
 * What happens to the people waiting when demand passes capacity for a while.
3
 *
4
 * A service has some workers and each request takes some time, so it can answer so many a second. For a
5
 * stretch, more than that arrive. Somebody has to hear "no"; the only questions are how many, which ones,
6
 * and whether they hear it quickly or after waiting for nothing. The answer depends far less on capacity
7
 * than on what the service does with the request that does not fit, and that is what this simulates.
8
 *
9
 * The model, in one place:
10
 *
11
 *  - **Arrivals** are Poisson: `base` a second, then `spike` a second for 60 s, then `base` again.
12
 *    One minute of normal traffic before the spike and three minutes after it, so recovery is visible.
13
 *  - **Service** is exponential with the given mean, on `workers` identical workers.
14
 *  - **Each attempt** waits up to `timeout` for an answer. Then the client gives up on it, and if it has
15
 *    retries left, sends another about 1 s later, spread +-50%.
16
 *  - **The person** gives up 10 s after first trying. "Answered" means a successful response
17
 *    inside that, which is the definition that still means something once retries are counted.
18
 *  - **Work is not cancelled.** A request whose client has given up is still served when its turn comes,
19
 *    unless the policy checks first. That is wasted work, and it is most of what an overloaded unbounded
20
 *    queue does.
21
 *
22
 * The policies are the ones the backpressure post compares: an unbounded queue, skip the abandoned, a bounded
23
 * queue, a bounded queue that puts orders first (1 request in 5 is an order), a CoDel-style queue timeout set as
24
 * each request arrives (Maurer, "Fail at Scale", ACM Queue 2015), and adaptive LIFO on top of it.
25
 *
26
 * ⚠️ This is the same simulation as `backpressure/shed_sim.py` in mainlog-code, event for event and draw for
27
 * draw: the same mulberry32 generator, seeded the same way, consumed in the same order, and the same
28
 * tie-break on simultaneous events. With the post's inputs it prints the post's numbers, and the fixtures
29
 * pin exactly those. A change to the event order here that is not made there is a bug, and the fixtures
30
 * are what will say so.
31
 *
32
 * ⚠️ Where it stops being true: exponential service has a light tail, and real ones are heavier, which
33
 * makes every policy worse. Real clients do not retry on a perfect schedule. And one queue in front of one
34
 * pool is the simplest possible service; a chain of them multiplies retries (see the retry tools).
35
 */
36
import type { Cell, Field, Output, Series, Tool } from "@toolbench/sdk";
37

38
type Input = {
39
  workers: number;
40
  service: number;
41
  base: number;
42
  spike: number;
43
  timeout: number;
44
  retries: number;
45
  policy: string;
46
  /** The bounded policies' limit, in requests. 0, or absent, derives it from the timeout. */
47
  queue?: number;
48
};
49

50
/**
51
 * The model's other numbers, fixed rather than asked for. Each one changes the answer less than the seven inputs do,
52
 * and a form with twelve fields asks a reader to decide things they came here to have decided. The README says what
53
 * each is and why it has the value it has.
54
 */
55
type Params = Input & { duration: number; patience: number; backoff: number; bound: number; checkout: number };
56
const DURATION = 60;
57
const PATIENCE = 10;
58
const BACKOFF = 1;
59
const ORDER_SHARE = 20;
60
/**
61
 * When the reader leaves the queue size at 0, the bound is derived, from the rule the backpressure post teaches: a
62
 * bound sheds only if the work it holds is shorter than the caller's timeout. A quarter of the timeout's worth leaves
63
 * room for the service time and for bursts, and it is 50 at the post's numbers (2 s x 100/s / 4). A size the reader
64
 * types is used as it is, which is what shed_sim.py's `--queue-bound` does, so 1,024 runs the same draws there.
65
 */
66
const BOUND_SHARE = 0.25;
67

68
class InputError extends Error {
69
  readonly input: string;
70

71
  constructor(message: string, input: string) {
72
    super(message);
73
    this.name = "InputError";
74
    this.input = input;
75
  }
76
}
77

78
const POLICIES: Record<string, string> = {
79
  fifo: "Unbounded queue",
80
  fifo_skip: "Skip the abandoned",
81
  bounded: "Bounded queue",
82
  priority: "Bounded, orders first",
83
  codel: "Queue timeout (CoDel)",
84
  lifo: "Newest first (LIFO + CoDel)",
85
};
86

87
/** Before the spike and after it. Fixed, so the timeline always has room to show a recovery or its absence. */
88
const BEFORE = 60;
89
const AFTER = 180;
90
/** Fail at Scale's M and N. Not inputs: the point of the policy is that it has two numbers and keeps them. */
91
const CODEL_TARGET = 0.005;
92
const CODEL_INTERVAL = 0.1;
93
const WINDOW = 10;
94
/** A run this large is minutes of a worker's time. Refused up front rather than left to the timeout. */
95
const MAX_ARRIVALS = 2_000_000;
96
const SEED = 1;
97

98
/** mulberry32. The Python simulation implements the same function bit for bit. */
99
function rng(seed: number): () => number {
100
  let state = seed >>> 0;
101
  return () => {
102
    state = (state + 0x6d2b79f5) >>> 0;
103
    let t = state;
104
    t = Math.imul(t ^ (t >>> 15), t | 1);
105
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
106
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
107
  };
108
}
109

110
function exponential(next: () => number, mean: number): number {
111
  return -Math.log(1 - next()) * mean;
112
}
113

114
type Attempt = {
115
  user: number;
116
  checkout: boolean;
117
  t0: number;
118
  tries: number;
119
  gaveUp: boolean;
120
  finished: boolean;
121
  refused: boolean;
122
  limit: number;
123
};
124

125
type User = { first: number; checkout: boolean; outcome: string; latency: number; attempts: number };
126

127
type Kind = 0 | 1 | 2 | 3; // arrive, timeout, rejected, done
128
type Event = { t: number; seq: number; kind: Kind; a: Attempt };
129

130
/**
131
 * A binary min-heap on (time, sequence). The sequence number makes the order total, which is what makes it
132
 * the same order as Python's heapq: two events at the same instant come out in the order they were pushed.
133
 */
134
class Heap {
135
  private items: Event[] = [];
136

137
  get size(): number {
138
    return this.items.length;
139
  }
140

141
  private less(i: number, j: number): boolean {
142
    const a = this.items[i]!;
143
    const b = this.items[j]!;
144
    return a.t < b.t || (a.t === b.t && a.seq < b.seq);
145
  }
146

147
  push(e: Event): void {
148
    const items = this.items;
149
    items.push(e);
150
    let i = items.length - 1;
151
    while (i > 0) {
152
      const parent = (i - 1) >> 1;
153
      if (!this.less(i, parent)) break;
154
      [items[i], items[parent]] = [items[parent]!, items[i]!];
155
      i = parent;
156
    }
157
  }
158

159
  pop(): Event {
160
    const items = this.items;
161
    const top = items[0]!;
162
    const last = items.pop()!;
163
    if (items.length > 0) {
164
      items[0] = last;
165
      let i = 0;
166
      for (;;) {
167
        const l = 2 * i + 1;
168
        const r = l + 1;
169
        let m = i;
170
        if (l < items.length && this.less(l, m)) m = l;
171
        if (r < items.length && this.less(r, m)) m = r;
172
        if (m === i) break;
173
        [items[i], items[m]] = [items[m]!, items[i]!];
174
        i = m;
175
      }
176
    }
177
    return top;
178
  }
179
}
180

181
/**
182
 * A queue that can be taken from either end and, rarely, from the middle. An array with a moving head,
183
 * because `shift()` on a long array is linear and an unbounded queue in overload is exactly a long array.
184
 */
185
class Line {
186
  private items: Attempt[] = [];
187
  private head = 0;
188

189
  get length(): number {
190
    return this.items.length - this.head;
191
  }
192

193
  push(a: Attempt): void {
194
    this.items.push(a);
195
  }
196

197
  shift(): Attempt {
198
    const a = this.items[this.head]!;
199
    this.head++;
200
    if (this.head > 4096 && this.head * 2 > this.items.length) {
201
      this.items = this.items.slice(this.head);
202
      this.head = 0;
203
    }
204
    return a;
205
  }
206

207
  pop(): Attempt {
208
    return this.items.pop()!;
209
  }
210

211
  /** The newest price preview, removed; null if every queued request is an order. */
212
  takeNewestBrowse(): Attempt | null {
213
    for (let i = this.items.length - 1; i >= this.head; i--) {
214
      const a = this.items[i]!;
215
      if (!a.checkout) {
216
        this.items.splice(i, 1);
217
        return a;
218
      }
219
    }
220
    return null;
221
  }
222
}
223

224
type Run = {
225
  users: User[];
226
  wasted: number;
227
  useful: number;
228
  windows: number[];
229
  end: number;
230
  spikeStart: number;
231
  spikeEnd: number;
232
};
233

234
function simulate(p: Params, policy: string, signal?: AbortSignal): Run {
235
  const arrivals = rng(SEED);
236
  const service = rng(SEED + 1);
237
  const backoffs = rng(SEED + 2);
238
  const meanService = p.service / 1000;
239
  const spikeStart = BEFORE;
240
  const spikeEnd = BEFORE + p.duration;
241
  const end = spikeEnd + AFTER;
242

243
  const heap = new Heap();
244
  let seq = 0;
245
  const push = (t: number, kind: Kind, a: Attempt) => {
246
    seq++;
247
    heap.push({ t, seq, kind, a });
248
  };
249
  const attempt = (user: number, checkout: boolean, t0: number, tries: number): Attempt => ({
250
    user,
251
    checkout,
252
    t0,
253
    tries,
254
    gaveUp: false,
255
    finished: false,
256
    refused: false,
257
    limit: 0,
258
  });
259

260
  const users: User[] = [];
261
  let t = 0;
262
  for (;;) {
263
    const rate = spikeStart <= t && t < spikeEnd ? p.spike : p.base;
264
    t += exponential(arrivals, 1 / rate);
265
    if (t >= end) break;
266
    const checkout = arrivals() < p.checkout / 100;
267
    users.push({ first: t, checkout, outcome: "", latency: Number.NaN, attempts: 0 });
268
    push(t, 0, attempt(users.length - 1, checkout, t, 0));
269
  }
270

271
  const queue = new Line();
272
  const rejects = new Line();
273
  let busy = 0;
274
  let lastEmpty = 0;
275
  let wasted = 0;
276
  let useful = 0;
277
  const rejectCost = 0;
278

279
  const settle = (a: Attempt, outcome: string, now: number) => {
280
    const u = users[a.user]!;
281
    if (a.tries < p.retries) {
282
      const at = now + p.backoff * (0.5 + backoffs());
283
      if (at < u.first + p.patience) {
284
        push(at, 0, attempt(a.user, a.checkout, at, a.tries + 1));
285
        return;
286
      }
287
    }
288
    u.outcome = outcome;
289
  };
290
  const refuse = (a: Attempt, now: number) => {
291
    a.refused = true;
292
    settle(a, "refused", now);
293
  };
294
  const fullReject = (a: Attempt, now: number) => {
295
    if (rejectCost > 0) rejects.push(a);
296
    else refuse(a, now);
297
  };
298
  const start = (now: number) => {
299
    while (busy < p.workers && (rejects.length > 0 || queue.length > 0)) {
300
      if (rejects.length > 0) {
301
        const a = rejects.shift();
302
        busy++;
303
        push(now + rejectCost, 2, a);
304
        continue;
305
      }
306
      const congested = now - lastEmpty > CODEL_INTERVAL;
307
      const a = policy === "lifo" && congested ? queue.pop() : queue.shift();
308
      if (policy === "codel" || policy === "lifo") {
309
        // The limit set when it arrived, enforced as a worker picks it up.
310
        if (now - a.t0 > a.limit) {
311
          if (!a.gaveUp) refuse(a, now);
312
          continue;
313
        }
314
      }
315
      if (policy === "fifo_skip" && a.gaveUp) continue;
316
      busy++;
317
      push(now + exponential(service, meanService), 3, a);
318
    }
319
    if (queue.length === 0) lastEmpty = now;
320
  };
321

322
  let processed = 0;
323
  while (heap.size > 0) {
324
    if ((++processed & 0xffff) === 0) signal?.throwIfAborted();
325
    const { t: now, kind, a } = heap.pop();
326
    if (kind === 0) {
327
      users[a.user]!.attempts++;
328
      push(a.t0 + p.timeout, 1, a);
329
      const bounded = policy === "bounded" || policy === "priority";
330
      if (bounded && queue.length >= p.bound) {
331
        if (policy === "priority" && a.checkout) {
332
          const victim = queue.takeNewestBrowse();
333
          if (victim) {
334
            fullReject(victim, now);
335
          } else {
336
            fullReject(a, now);
337
            start(now);
338
            continue;
339
          }
340
        } else {
341
          fullReject(a, now);
342
          start(now);
343
          continue;
344
        }
345
      }
346
      if (policy === "codel" || policy === "lifo") {
347
        // Fail at Scale's onNewRequest: M if the queue has not been empty for the last N, otherwise N,
348
        // decided from the queue as this request finds it.
349
        if (queue.length === 0) lastEmpty = now;
350
        a.limit = now - lastEmpty > CODEL_INTERVAL ? CODEL_TARGET : CODEL_INTERVAL;
351
      }
352
      queue.push(a);
353
      start(now);
354
    } else if (kind === 1) {
355
      if (a.finished || a.refused) continue;
356
      a.gaveUp = true;
357
      settle(a, "timed_out", now);
358
    } else if (kind === 2) {
359
      busy--;
360
      if (!a.gaveUp) refuse(a, now);
361
      start(now);
362
    } else {
363
      busy--;
364
      if (a.gaveUp) {
365
        wasted++;
366
      } else {
367
        a.finished = true;
368
        useful++;
369
        const u = users[a.user]!;
370
        if (now - u.first <= p.patience) {
371
          u.outcome = "answered";
372
          u.latency = now - u.first;
373
        } else {
374
          u.outcome = "late";
375
        }
376
      }
377
      start(now);
378
    }
379
  }
380

381
  const windows: number[] = [];
382
  for (let w = 0; w < end - 1e-9; w += WINDOW) {
383
    let n = 0;
384
    let ok = 0;
385
    for (const u of users) {
386
      if (w <= u.first && u.first < w + WINDOW) {
387
        n++;
388
        if (u.outcome === "answered") ok++;
389
      }
390
    }
391
    windows.push((100 * ok) / Math.max(1, n));
392
  }
393
  return { users, wasted, useful, windows, end, spikeStart, spikeEnd };
394
}
395

396
type Summary = {
397
  answered: number;
398
  refused: number;
399
  timedOut: number;
400
  p50: number;
401
  p99: number;
402
  checkout: number;
403
  tries: number;
404
  wasted: number;
405
  recovered: number | null;
406
};
407

408
function share(users: User[], outcome: string | string[]): number {
409
  const want = Array.isArray(outcome) ? outcome : [outcome];
410
  return (100 * users.filter((u) => want.includes(u.outcome)).length) / Math.max(1, users.length);
411
}
412

413
function summarise(r: Run): Summary {
414
  const spike = r.users.filter((u) => r.spikeStart <= u.first && u.first < r.spikeEnd);
415
  const lat = spike
416
    .filter((u) => u.outcome === "answered")
417
    .map((u) => u.latency)
418
    .sort((a, b) => a - b);
419
  const pct = (q: number) => (lat.length ? lat[Math.floor(q * (lat.length - 1))]! * 1000 : Number.NaN);
420
  let recovered: number | null = null;
421
  for (let i = 0; i < r.windows.length; i++) {
422
    const s = i * WINDOW;
423
    if (s < r.spikeEnd) continue;
424
    if (r.windows.slice(i).every((w) => w >= 90)) {
425
      recovered = s - r.spikeEnd;
426
      break;
427
    }
428
  }
429
  return {
430
    answered: share(spike, "answered"),
431
    refused: share(spike, "refused"),
432
    timedOut: share(spike, ["timed_out", "late"]),
433
    p50: pct(0.5),
434
    p99: pct(0.99),
435
    checkout: share(
436
      spike.filter((u) => u.checkout),
437
      "answered",
438
    ),
439
    tries: spike.reduce((n, u) => n + u.attempts, 0) / Math.max(1, spike.length),
440
    wasted: r.wasted,
441
    recovered,
442
  };
443
}
444

445
const one = (v: number) => `${v.toFixed(1)}%`;
446
const ms = (v: number) => (Number.isFinite(v) ? `${v.toFixed(0)} ms` : "none answered");
447
const recoveryText = (s: Summary, after: number) =>
448
  s.recovered === null ? `not within ${after} s` : s.recovered === 0 ? "at once" : `${s.recovered} s`;
449

450
/** Tries that fit in a person's patience: each one waits out the timeout, then the backoff, before the next. */
451
function triesInPatience(retries: number, timeout: number): number {
452
  return Math.min(1 + retries, Math.floor((PATIENCE - 1e-9) / (timeout + BACKOFF)) + 1);
453
}
454

455
export default {
456
  run(input: Input, ctx) {
457
    try {
458
      const positive: [keyof Input, string][] = [
459
        ["workers", "Workers"],
460
        ["service", "Service time"],
461
        ["base", "Normal rate"],
462
        ["spike", "Spike rate"],
463
        ["timeout", "Timeout"],
464
      ];
465
      for (const [key, label] of positive) {
466
        if (!(Number(input[key]) > 0)) throw new InputError(`${label} must be greater than zero.`, key);
467
      }
468
      if (!Number.isInteger(input.workers)) throw new InputError("Workers must be a whole number.", "workers");
469
      if (!(Number.isInteger(input.retries) && input.retries >= 0)) {
470
        throw new InputError("Retries must be a whole number, zero or more.", "retries");
471
      }
472
      if (!(input.policy in POLICIES)) throw new InputError("Unknown policy.", "policy");
473
      const queue = input.queue ?? 0;
474
      if (!(Number.isInteger(queue) && queue >= 0)) {
475
        throw new InputError("Queue size must be a whole number, zero or more.", "queue");
476
      }
477
      const capacity = input.workers / (input.service / 1000);
478
      const p: Params = {
479
        ...input,
480
        duration: DURATION,
481
        patience: PATIENCE,
482
        backoff: BACKOFF,
483
        checkout: ORDER_SHARE,
484
        bound: queue > 0 ? queue : Math.max(1, Math.round(BOUND_SHARE * input.timeout * capacity)),
485
      };
486
      const expected = (BEFORE + AFTER) * p.base + p.duration * p.spike;
487
      if (expected * (1 + p.retries) > MAX_ARRIVALS) {
488
        throw new InputError(
489
          `That is about ${Math.round(expected * (1 + p.retries)).toLocaleString("en-US")} attempts to simulate, over the ${MAX_ARRIVALS.toLocaleString("en-US")} this runs in a page. Scale the rates and the workers down together: the shares depend on their ratio.`,
490
          "spike",
491
        );
492
      }
493

494
      const run = simulate(p, p.policy, ctx?.signal);
495
      const s = summarise(run);
496
      const bounded = p.policy === "bounded" || p.policy === "priority";
497
      const timed = p.policy === "codel" || p.policy === "lifo";
498
      /*
499
       * Could a spike leave it stuck? Two conditions, said as numbers. First, can the queue hold people past their
500
       * timeout? An unbounded queue can; the derived bound and the queue timeout can't, unless the timeout is
501
       * shorter than the queue timeout's 100 ms. Second, once everyone times out, every person sends all the tries
502
       * that fit in their patience: if the normal rate times those tries is at least capacity, the queue can't drain.
503
       * Near 1 the simulation's randomness decides, so within 15% of it the answer is "borderline".
504
       *
505
       * This is a property of the service, not of this run, which is why "This run" says separately what happened.
506
       */
507
      const tries = triesInPatience(p.retries, p.timeout);
508
      const holdsPastTimeout = bounded ? p.bound / capacity >= p.timeout : timed ? p.timeout <= CODEL_INTERVAL : true;
509
      const stuckLoad = p.base * tries;
510
      const ratio = stuckLoad / capacity;
511
      /*
512
       * The same question as a sentence with its numbers, not a yes or no: the reader sees the two rates being
513
       * compared, and the note says what follows from them. Every note says "a spike can" or "cannot leave it stuck",
514
       * or that chance decides, so the conclusion is always in words.
515
       */
516
      const rate = (v: number) => `${Number(v.toFixed(1))}/s`;
517
      const borderline = Math.abs(ratio - 1) <= 0.15;
518
      let could: Field;
519
      if (p.base >= capacity) {
520
        could = {
521
          label: "Normal traffic",
522
          value: `${rate(p.base)} against ${rate(capacity)}`,
523
          tone: "bad",
524
          note: "Overloaded without a spike: the normal rate alone is at or over capacity.",
525
        };
526
      } else if (!holdsPastTimeout) {
527
        const wait = timed ? CODEL_INTERVAL * 1000 : Math.round((p.bound / capacity) * 1000);
528
        could = {
529
          label: "Longest wait in the queue",
530
          value: `${wait} ms`,
531
          note: timed
532
            ? `The queue timeout, under the ${p.timeout} s timeout, so a spike cannot leave it stuck.`
533
            : `The bound, ${p.bound}, is that much work: under the ${p.timeout} s timeout, so a spike cannot leave it stuck.`,
534
        };
535
      } else {
536
        could = {
537
          label: "Once everyone times out",
538
          value: `${rate(stuckLoad)} of tries against ${rate(capacity)}`,
539
          ...(ratio >= 1 && !borderline ? { tone: "bad" as const } : {}),
540
          note: `${
541
            bounded
542
              ? `The bound, ${p.bound.toLocaleString("en-US")}, is ${Number((p.bound / capacity).toFixed(1))} s of work, so it holds people past the ${p.timeout} s timeout. `
543
              : ""
544
          }${p.base}/s times ${tries} ${tries === 1 ? "try" : "tries"} within ${PATIENCE} s. ${
545
            borderline
546
              ? "Within 15% of capacity, so chance decides whether a spike leaves it stuck."
547
              : ratio >= 1
548
                ? "Retries alone fill it, so a spike can leave it stuck."
549
                : "It drains, so a spike cannot leave it stuck."
550
          }`,
551
        };
552
      }
553
      const stuck = s.recovered === null && ratio >= 1 && holdsPastTimeout;
554
      const thisRun: Field =
555
        s.recovered === 0
556
          ? { label: "This run", value: "recovered at once" }
557
          : s.recovered !== null
558
            ? { label: "This run", value: `recovered ${s.recovered} s after the spike` }
559
            : stuck
560
              ? { label: "This run", value: "stuck to the end", tone: "bad", note: `Still failing ${AFTER} s after the spike.` }
561
              : { label: "This run", value: "still draining at the end", note: `The backlog outlasted the ${AFTER} s after the spike.` };
562

563
      /*
564
       * The service's numbers and the run's tail, quietly, at the end. The shares and the median are in the
565
       * comparison, so they are not repeated.
566
       */
567
      const metrics: Field[] = [
568
        { label: "Capacity", value: `${capacity.toFixed(1)}/s`, note: `${p.workers} workers at ${p.service} ms each` },
569
        { label: "Spike against capacity", value: `${((p.spike / capacity) * 100).toFixed(0)}%`, note: `${p.spike}/s for ${p.duration} s` },
570
        { label: "Answered, p99", value: ms(s.p99), note: "From the first try, retries included" },
571
        { label: "Orders answered", value: one(s.checkout), note: `${ORDER_SHARE}% of requests are orders` },
572
        { label: "Tries per person", value: s.tries.toFixed(2) },
573
      ];
574

575
      const xs = run.windows.map((_, i) => i * WINDOW);
576
      const answered: Series = {
577
        label: POLICIES[p.policy]!,
578
        unit: "%",
579
        shape: "step",
580
        points: run.windows.map((w) => Number(w.toFixed(1))),
581
      };
582

583
      /*
584
       * Every policy at the same numbers, because the reason to run this is the comparison: same capacity, same
585
       * spike, and the share answered moves from a few percent to two thirds with nothing but the policy. The
586
       * reader's policy first and named as theirs, in words, since being current is not a judgement.
587
       */
588
      const others = new Map<string, Summary>();
589
      for (const name of Object.keys(POLICIES)) {
590
        others.set(name, name === p.policy ? s : summarise(simulate(p, name, ctx?.signal)));
591
      }
592
      const order = [p.policy, ...Object.keys(POLICIES).filter((name) => name !== p.policy)];
593
      // "Queue timeout (CoDel, yours)", not "(CoDel) (yours)".
594
      const named = (name: string) => {
595
        const label = POLICIES[name]!;
596
        if (name !== p.policy) return label;
597
        return label.endsWith(")") ? `${label.slice(0, -1)}, yours)` : `${label} (yours)`;
598
      };
599
      const rounded = (v: number) => Number(v.toFixed(1));
600
      /*
601
       * What happened to everyone who arrived during the spike, one bar per policy: answered in time, told no at
602
       * once, or kept waiting for nothing. The three add up to everyone, so the bars are the same length and the
603
       * split is the whole comparison.
604
       */
605
      const outcomes: Output = {
606
        kind: "series",
607
        chart: {
608
          xLabel: "Policy",
609
          yLabel: "People who arrived during the spike",
610
          yUnit: "%",
611
          x: order.map(named),
612
          orientation: "horizontal",
613
          series: [
614
            { label: "Answered in time", unit: "%", shape: "bar", stack: "people", points: order.map((n) => rounded(others.get(n)!.answered)) },
615
            /*
616
             * Series colours follow order: blue, orange, green. Waiting for nothing is the failure, so it is
617
             * second and takes orange; a fast no is the outcome a policy chooses on purpose, and takes green.
618
             */
619
            { label: "Waited for nothing", unit: "%", shape: "bar", stack: "people", points: order.map((n) => rounded(others.get(n)!.timedOut)) },
620
            { label: "Refused at once", unit: "%", shape: "bar", stack: "people", points: order.map((n) => rounded(others.get(n)!.refused)) },
621
          ],
622
        },
623
      };
624
      const rows: Cell[][] = order.map((name) => {
625
        const o = others.get(name)!;
626
        const recovery = o.recovered === null ? `over ${AFTER} s` : recoveryText(o, AFTER);
627
        return [named(name), one(o.answered), ms(o.p50), recovery, o.wasted.toLocaleString("en-US")];
628
      });
629

630
      const actions = whatToChange(p, s, others, { capacity, ratio, holdsPastTimeout, stuck, stuckLoad, tries });
631

632
      /*
633
       * The comparison first, as bars and then as numbers; then how this policy recovered; then whether a spike can
634
       * leave the service stuck, beside what this run did; then what to change, when there is something; then the
635
       * service's own numbers.
636
       */
637
      const parts: Output[] = [
638
        outcomes,
639
        {
640
          kind: "table",
641
          role: "comparison",
642
          // Short headers, because a comparison keeps its columns on a phone; the caption says what the last two are.
643
          caption: "Every policy at these numbers. Recovery: until every 10 s answers 90% again. Wasted: served after the client gave up",
644
          columns: [
645
            { label: "Policy", wrap: "prose", rowHeader: true },
646
            { label: "Answered", align: "end", mono: true, wrap: "none" },
647
            { label: "p50", align: "end", mono: true, wrap: "none" },
648
            { label: "Recovery", align: "end", mono: true, wrap: "none" },
649
            { label: "Wasted", align: "end", mono: true, wrap: "none" },
650
          ],
651
          rows,
652
        },
653
        {
654
          kind: "series",
655
          chart: {
656
            xLabel: "First tried at",
657
            xUnit: "s",
658
            yLabel: "Answered",
659
            yUnit: "%",
660
            x: xs,
661
            series: [answered],
662
            annotations: [
663
              { x: run.spikeStart, label: "spike" },
664
              { x: run.spikeEnd, label: "spike ends" },
665
            ],
666
            // What "back to normal" means in the table: every 10 s from here on answers 90% or more.
667
            thresholds: [{ y: 90, label: "90%, back to normal" }],
668
          },
669
        },
670
        { kind: "fields", fields: [could, thisRun] },
671
        ...(actions.length > 0
672
          ? [
673
              {
674
                kind: "table" as const,
675
                role: "actions",
676
                caption: "What to change, the worst problem first",
677
                columns: [{ label: "Change" }, { label: "What it does at these numbers" }],
678
                rows: actions,
679
              },
680
            ]
681
          : []),
682
        { kind: "fields", role: "metrics", fields: metrics },
683
      ];
684
      return { kind: "group", parts };
685
    } catch (error) {
686
      if (error instanceof InputError) return { kind: "error", message: error.message, input: error.input };
687
      throw error;
688
    }
689
  },
690
} satisfies Tool<Input>;
691

692
/** The fewest whole workers whose capacity is over `rate` at this service time. */
693
const workersFor = (rate: number, service: number) => Math.floor((rate * service) / 1000) + 1;
694

695
/**
696
 * What to change, worst first: a service overloaded without a spike, then one a spike can leave stuck, then a better
697
 * policy at the same capacity, then capacity for the spike itself. Every number is from this run or the comparison
698
 * runs, never a promise about a run that was not made: "more workers" says the fewest that put capacity over the rate,
699
 * and leaves sizing them for a wait target to the capacity planner.
700
 */
701
function whatToChange(
702
  p: Params,
703
  s: Summary,
704
  others: Map<string, Summary>,
705
  k: { capacity: number; ratio: number; holdsPastTimeout: boolean; stuck: boolean; stuckLoad: number; tries: number },
706
): Cell[][] {
707
  const rows: Cell[][] = [];
708
  if (p.base >= k.capacity) {
709
    rows.push([
710
      { text: "Add workers: the normal traffic alone is more than the service can answer." },
711
      {
712
        text: `${workersFor(p.base, p.service)} workers is the fewest whose capacity is over the normal ${p.base}/s. Today's ${p.workers} answer ${k.capacity.toFixed(1)}/s.`,
713
      },
714
    ]);
715
  } else if (k.holdsPastTimeout && k.ratio >= 0.85) {
716
    /* The most retries that keep the load once everyone times out clear of the borderline band. */
717
    let fit = -1;
718
    for (let r = 0; r <= 10; r++) {
719
      if (p.base * triesInPatience(r, p.timeout) < k.capacity / 1.15) fit = r;
720
    }
721
    rows.push([
722
      {
723
        text:
724
          fit < 0
725
            ? "Bound the queue, or add a queue timeout, so nothing waits past the client's timeout."
726
            : fit === 0
727
              ? "Do not retry, or bound the queue so nothing waits past the timeout."
728
              : `Retry at most ${fit === 1 ? "once" : `${fit} times`}, or bound the queue so nothing waits past the timeout.`,
729
      },
730
      {
731
        text: `When everyone is timing out, each person sends ${k.tries} ${k.tries === 1 ? "try" : "tries"} in ${PATIENCE} s: ${p.base}/s times ${k.tries} is ${Number(k.stuckLoad.toFixed(1))}/s against ${Number(k.capacity.toFixed(1))}/s, so the queue ${k.ratio >= 1 ? "cannot" : "may not be able to"} drain${k.stuck ? ". In this run it did not" : ""}.`,
732
      },
733
    ]);
734
  }
735
  let best: string | null = null;
736
  for (const [name, o] of others) {
737
    if (name === p.policy) continue;
738
    const b = best ? others.get(best)! : null;
739
    if (!b || o.answered > b.answered + 0.05 || (Math.abs(o.answered - b.answered) <= 0.05 && o.timedOut < b.timedOut)) best = name;
740
  }
741
  const b = best ? others.get(best)! : null;
742
  if (best && b && (b.answered >= s.answered + 5 || (s.timedOut > 0.5 && b.timedOut <= s.timedOut - 5 && b.answered >= s.answered))) {
743
    rows.push([
744
      { text: `Switch to ${POLICIES[best]!.toLowerCase().replace("codel", "CoDel").replace("lifo", "LIFO")}.` },
745
      {
746
        text: `${one(b.answered)} answered instead of ${one(s.answered)}, and ${one(b.timedOut)} wait for nothing instead of ${one(s.timedOut)}. Back to normal: ${recoveryText(b, AFTER)}.`,
747
      },
748
    ]);
749
  }
750
  if (p.spike > k.capacity && p.base < k.capacity) {
751
    rows.push([
752
      { text: rows.length ? "Or add workers for the spike." : "Add workers for the spike." },
753
      {
754
        text: `${workersFor(p.spike, p.service)} workers is the fewest whose capacity is over the ${p.spike}/s spike. The capacity planner sizes them for a wait target.`,
755
      },
756
    ]);
757
  }
758
  return rows;
759
}