1
/**
2
 * How many servers do you need?
3
 *
4
 * The question behind every capacity review: requests arrive at some rate, each takes some time, and
5
 * somebody wants to know how many workers, threads, connections or agents to run. The usual answer is
6
 * utilisation, "keep it under 80%", which is not an answer at all: 80% of two servers and 80% of two
7
 * hundred behave nothing alike. What actually decides it is queueing, and the closed form for that has
8
 * been known since 1917.
9
 *
10
 * This computes Erlang C for an M/M/c queue: Poisson arrivals, exponential service times, c identical
11
 * servers, first come first served, no balking and an unbounded queue. It reports the smallest c that meets a
12
 * target on the chance of waiting at all, or longer than a limit, with one server either side of it and the p99
13
 * wait at each, and it draws the curve so the shape is visible. The shape is the point. Wait does not rise linearly
14
 * with load; it is flat and then it is a cliff, and the cliff moves as c changes.
15
 *
16
 * A simulate mode runs a seeded Monte Carlo of the same queue and reports what fraction of arrivals
17
 * waited, which is there to disagree with the formula if the formula is wrong.
18
 *
19
 * ⚠️ Where the model stops being true, because a capacity number that quietly assumes the wrong world
20
 * is worse than no number:
21
 *
22
 *  - **Exponential service times.** Real service times have a tail. A heavier tail queues worse than
23
 *    this predicts, so treat the answer as a floor rather than a forecast.
24
 *  - **Poisson arrivals.** Bursty traffic, retries and thundering herds all violate this, and all of
25
 *    them make it worse rather than better.
26
 *  - **Identical servers, no setup cost.** No cold starts, no autoscaling lag, no cache warmth.
27
 *  - **An unbounded queue.** A real system sheds load, and shedding changes the arrival process.
28
 *
29
 * References: Erlang (1917) for the loss formula; Cooper, *Introduction to Queueing Theory*, for the
30
 * recursion used here and for the M/M/c waiting-time result.
31
 */
32
import type { Cell, Field, Output, Series, Tool } from "@toolbench/sdk";
33

34
type Input = { rate: number; service: number; target: number; limit: number; mode: string; trials: number };
35

36
/**
37
 * Named so the error path can say which input was wrong rather than "invalid input".
38
 *
39
 * ⚠️ The field is declared and assigned rather than written as a constructor parameter property. A
40
 * parameter property emits code, so it is not erasable, and `src/tools/tsconfig.json` sets
41
 * `erasableSyntaxOnly` for exactly this reason: tools are run by stripping types, and the failure arrives
42
 * as "TypeScript parameter property is not supported in strip-only mode" from the test runner rather than
43
 * from the compiler.
44
 */
45
class InputError extends Error {
46
  readonly input: string;
47

48
  constructor(message: string, input: string) {
49
    super(message);
50
    this.name = "InputError";
51
    this.input = input;
52
  }
53
}
54

55
/**
56
 * Erlang B, by the recursion rather than the textbook ratio.
57
 *
58
 * ⚠️ The plan for this tool said to compute Erlang C "in log space so it does not overflow". Log space
59
 * solves the overflow, and this solves it better: the recursion never forms `A^c` or `c!` at all, so
60
 * there is nothing to overflow and no `lgamma` or log-sum-exp to get subtly wrong. The direct form,
61
 * `B = (A^c / c!) / Σ(A^k / k!)`, overflows `A^c` around c = 170 for any interesting A, which is well
62
 * inside the range a real capacity question lands in.
63
 *
64
 *   B(0) = 1
65
 *   B(n) = A·B(n−1) / (n + A·B(n−1))
66
 *
67
 * Every intermediate value is a probability in [0, 1], and the loop is O(c) with one division per step.
68
 */
69
function erlangB(load: number, servers: number): number {
70
  let b = 1;
71
  for (let n = 1; n <= servers; n++) b = (load * b) / (n + load * b);
72
  return b;
73
}
74

75
/**
76
 * Erlang C: the probability an arrival waits, given `servers` servers and `load` erlangs of offered work.
77
 *
78
 * Undefined at and above saturation, and that is not a rounding concern: at `servers <= load` the queue
79
 * grows without bound and "probability of waiting" tends to 1 while the mean wait tends to infinity. The
80
 * caller is expected to have excluded that range; returning 1 here would look like an answer.
81
 */
82
function erlangC(load: number, servers: number): number {
83
  if (servers <= load) return 1;
84
  const b = erlangB(load, servers);
85
  const utilisation = load / servers;
86
  return b / (1 - utilisation * (1 - b));
87
}
88

89
/** Mean seconds an arrival spends waiting, not counting its own service. */
90
function meanWaitSeconds(load: number, servers: number, serviceSeconds: number): number {
91
  if (servers <= load) return Number.POSITIVE_INFINITY;
92
  return (erlangC(load, servers) * serviceSeconds) / (servers - load);
93
}
94

95
/**
96
 * mulberry32, seeded from a constant.
97
 *
98
 * ⚠️ The seed is fixed and that is a contract requirement, not laziness: `pure` means a function of the
99
 * declared inputs, with "no randomness that is not seeded". `Math.random()` here would make every
100
 * fixture unreproducible and the build-time seed different on every build.
101
 */
102
function rng(seed: number): () => number {
103
  let state = seed >>> 0;
104
  return () => {
105
    state = (state + 0x6d2b79f5) >>> 0;
106
    let t = state;
107
    t = Math.imul(t ^ (t >>> 15), t | 1);
108
    t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
109
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
110
  };
111
}
112

113
/** An exponential draw with the given mean. `1 - u` because `u` can be exactly 0 and log(0) is not. */
114
function exponential(next: () => number, mean: number): number {
115
  return -Math.log(1 - next()) * mean;
116
}
117

118
/**
119
 * A discrete-event simulation of the same M/M/c queue, to be checked against the formula.
120
 *
121
 * Exact rather than time-stepped: each arrival is assigned to the server that frees up first, so the
122
 * wait is `max(0, earliestFree - arrival)` and no time quantum is involved. FCFS with c identical
123
 * servers makes "earliest free" the correct discipline.
124
 *
125
 * ⚠️ The first tenth is discarded. Every server is idle at t = 0, so the opening arrivals never wait and
126
 * would drag the estimate below the steady-state answer, which is exactly the direction that would make
127
 * a wrong formula look right.
128
 *
129
 * ⚠️ `signal` is checked and `progress` reported every 4096 arrivals. This tool declares
130
 * `thread: "worker"` because trials go to two million, where the loop is comfortably long enough to freeze
131
 * a page; a worker the runtime cannot interrupt is only half a boundary, and one that gives no sign of
132
 * life for a second looks broken.
133
 */
134
function simulate(
135
  arrivalsPerSecond: number,
136
  serviceSeconds: number,
137
  servers: number,
138
  trials: number,
139
  limit: number,
140
  signal: AbortSignal | undefined,
141
  report: ((fraction: number) => void) | undefined,
142
): { waitedFraction: number; overFraction: number; meanWaitSeconds: number; counted: number } {
143
  const next = rng(0x5eed);
144
  const freeAt = new Float64Array(servers);
145
  const warmup = Math.floor(trials / 10);
146
  let clock = 0;
147
  let waited = 0;
148
  let over = 0;
149
  let waitTotal = 0;
150
  let counted = 0;
151

152
  for (let i = 0; i < trials; i++) {
153
    if ((i & 0xfff) === 0) {
154
      signal?.throwIfAborted();
155
      report?.(i / trials);
156
    }
157

158
    clock += exponential(next, 1 / arrivalsPerSecond);
159

160
    let earliest = 0;
161
    for (let s = 1; s < servers; s++) if (freeAt[s]! < freeAt[earliest]!) earliest = s;
162

163
    const start = Math.max(clock, freeAt[earliest]!);
164
    const wait = start - clock;
165
    if (i >= warmup) {
166
      counted++;
167
      waitTotal += wait;
168
      if (wait > 0) waited++;
169
      if (wait > limit) over++;
170
    }
171
    freeAt[earliest] = start + exponential(next, serviceSeconds);
172
  }
173

174
  return {
175
    waitedFraction: counted > 0 ? waited / counted : 0,
176
    overFraction: counted > 0 ? over / counted : 0,
177
    meanWaitSeconds: counted > 0 ? waitTotal / counted : 0,
178
    counted,
179
  };
180
}
181

182
/** Rounded to a fixed number of places, as a string, so a fixture pins a value rather than a float. */
183
const fixed = (value: number, places: number): string => value.toFixed(places);
184
const percent = (fraction: number): string => `${(fraction * 100).toFixed(2)}%`;
185

186
/** Milliseconds, at a precision that stays useful from microseconds to minutes. */
187
function millis(seconds: number): string {
188
  if (!Number.isFinite(seconds)) return "unbounded";
189
  if (seconds === 0) return "0 ms";
190
  const ms = seconds * 1000;
191
  if (ms >= 10000) return `${(ms / 1000).toFixed(1)} s`;
192
  if (ms >= 1) return `${ms.toFixed(1)} ms`;
193
  return `${(ms * 1000).toFixed(0)} µs`;
194
}
195

196
/**
197
 * The chance an arrival waits longer than `limit` seconds: the M/M/c waiting-time tail,
198
 *
199
 *   P(W > t) = C(c, A) x exp(-(c x mu - lambda) x t)
200
 *
201
 * An arrival waits at all with probability C, and once it waits, the wait is exponential with rate c x mu - lambda,
202
 * the rate at which the servers' spare capacity drains the queue. At t = 0 this is C itself.
203
 */
204
export function waitOver(load: number, servers: number, serviceSeconds: number, limit: number): number {
205
  if (servers <= load) return 1;
206
  return erlangC(load, servers) * Math.exp(-((servers - load) / serviceSeconds) * limit);
207
}
208

209
/**
210
 * The wait that a share `p` of arrivals stay under: the same tail, inverted. `ln(C / (1 - p)) / (c x mu - lambda)`,
211
 * and zero when at least `p` of arrivals never wait, which is the common case for a well-sized pool and the reason
212
 * a p95 wait of zero is an answer rather than a rounding error.
213
 */
214
export function waitPercentile(load: number, servers: number, serviceSeconds: number, p: number): number {
215
  if (servers <= load) return Number.POSITIVE_INFINITY;
216
  const c = erlangC(load, servers);
217
  if (c <= 1 - p) return 0;
218
  return Math.log(c / (1 - p)) / ((servers - load) / serviceSeconds);
219
}
220

221
export default {
222
  run(input: Input, ctx) {
223
    try {
224
      const { rate, service, target, mode, trials } = input;
225
      const limit = Number(input.limit ?? 0);
226

227
      if (!(rate > 0)) throw new InputError("Arrival rate must be greater than zero.", "rate");
228
      if (!(service > 0)) throw new InputError("Service time must be greater than zero.", "service");
229
      if (!(target > 0 && target < 100)) {
230
        throw new InputError("Target must be between 0 and 100 percent, exclusive.", "target");
231
      }
232
      if (!(limit >= 0)) throw new InputError("The wait limit cannot be negative. Use 0 to size for no wait at all.", "limit");
233

234
      const serviceSeconds = service / 1000;
235
      const limitSeconds = limit / 1000;
236
      /*
237
       * Offered load in erlangs: the number of servers that would be busy if none ever queued. This is
238
       * the one number the whole answer turns on, and it is why "requests per second" alone can never
239
       * size anything: 100/s of 10ms work and 10/s of 100ms work are the same erlang.
240
       */
241
      const load = rate * serviceSeconds;
242

243
      /* Below this the queue is unstable however patient anyone is. Strictly greater than the load. */
244
      const minimumServers = Math.floor(load) + 1;
245

246
      /*
247
       * What the target applies to: waiting at all when the limit is 0, which is Erlang C, or waiting longer
248
       * than the limit, which is the tail. Both fall as servers are added, so the first count that meets the
249
       * target is the answer either way.
250
       */
251
      const sized = (c: number) => waitOver(load, c, serviceSeconds, limitSeconds);
252
      const targetFraction = target / 100;
253
      let chosen = minimumServers;
254
      /*
255
       * A bound rather than a while(true). Both measures fall monotonically in c, so a target above zero is
256
       * always reachable, but "always" here rests on floating point: at very small targets C underflows
257
       * to 0 and the loop would already have stopped. The cap keeps a pathological input from spinning.
258
       */
259
      const searchLimit = minimumServers + 10000;
260
      while (chosen < searchLimit && sized(chosen) > targetFraction) chosen++;
261

262
      const chosenC = erlangC(load, chosen);
263
      const chosenWait = meanWaitSeconds(load, chosen, serviceSeconds);
264
      const chosenOver = sized(chosen);
265
      const what = limit > 0 ? `wait longer than ${limit} ms` : "wait";
266
      /* The reader's own number, as they typed it: "5%", not "5.00%". */
267
      const targetText = `${Number(target.toFixed(2))}%`;
268

269
      /*
270
       * ⚠️ The answer comes FIRST, as one number, and the order decides what a card shows.
271
       *
272
       * A compact card renders the first part, and the backpressure post embeds this tool capped at one part. The
273
       * note carries the step that decides it, one server fewer, because "11 servers" with no evidence beside it is
274
       * a claim, and the step between two counts is the whole decision. No tone: a size is not a pass or a fail.
275
       */
276
      const fewer = chosen - 1;
277
      const within = `With ${chosen}, ${percent(chosenOver)} of requests ${what}, within your ${targetText} target.`;
278
      const note =
279
        fewer < 1
280
          ? within
281
          : fewer <= load
282
            ? `With ${fewer}, the queue grows without limit. ${within}`
283
            : `With ${fewer}, ${percent(sized(fewer))} of requests ${what}, over your ${targetText} target. With ${chosen}, ${percent(chosenOver)}.`;
284
      const key: Output = {
285
        kind: "fields",
286
        role: "key",
287
        fields: [{ label: "Servers needed", value: `${chosen} servers`, note }],
288
      };
289

290
      /*
291
       * The span of the curve, from the stability floor to a little past the answer, and the three counts the
292
       * table compares: one fewer, the answer, one more.
293
       */
294
      const span = Math.max(6, Math.ceil((chosen - minimumServers) * 1.6));
295
      const xs: number[] = [];
296
      for (let c = minimumServers; c <= minimumServers + span; c++) xs.push(c);
297

298
      const sizedLabel = limit > 0 ? `Chance of waiting over ${limit} ms` : "Chance of waiting";
299
      /*
300
       * One series on one axis. An earlier version drew the mean wait on a second axis, which put a target line
301
       * meant for the percentage across a curve in milliseconds and labelled the axis "(ms) (ms)". The mean wait
302
       * at the answer is in the method notes instead.
303
       *
304
       * Log, because the chance falls by an order of magnitude every few servers, and on a linear axis everything
305
       * past the answer sits on zero, which is exactly the region the reader is choosing in.
306
       */
307
      const waitChance: Series = {
308
        label: sizedLabel,
309
        unit: "%",
310
        shape: "line",
311
        markers: true,
312
        points: xs.map((c) => Number((sized(c) * 100).toFixed(3))),
313
      };
314

315
      const status = (c: number): Cell => {
316
        if (c <= load) return { text: "Cannot keep up", tone: "bad" };
317
        if (sized(c) > targetFraction) return { text: "Misses", tone: "bad" };
318
        if (c === chosen) return "Fewest that meet it";
319
        return "Headroom";
320
      };
321
      const rows: Cell[][] = [fewer, chosen, chosen + 1]
322
        .filter((c) => c >= 1)
323
        .map((c) => [
324
          { text: String(c), mono: true },
325
          status(c),
326
          ...(limit > 0 ? [{ text: c <= load ? "all" : percent(sized(c)), mono: true }] : []),
327
          { text: c <= load ? "all" : percent(erlangC(load, c)), mono: true },
328
          { text: millis(waitPercentile(load, c, serviceSeconds, 0.99)), mono: true },
329
        ]);
330

331
      const parts: Output[] = [
332
        key,
333
        {
334
          kind: "text",
335
          role: "formula",
336
          mono: true,
337
          text: `${rate} ${rate === 1 ? "request" : "requests"}/s x ${service} ms = ${fixed(load, 2)} erlangs of load`,
338
        },
339
        {
340
          kind: "table",
341
          role: "comparison",
342
          caption: "Nearby server counts",
343
          columns: [
344
            { label: "Servers", mono: true, wrap: "none", rowHeader: true },
345
            { label: `Your ${targetText} target`, wrap: "none" },
346
            ...(limit > 0 ? [{ label: `Waits over ${limit} ms`, align: "end" as const, mono: true, wrap: "none" as const }] : []),
347
            { label: "Wait at all", align: "end", mono: true, wrap: "none" },
348
            { label: "p99 wait", align: "end", mono: true, wrap: "none" },
349
          ],
350
          rows,
351
        },
352
        {
353
          kind: "series",
354
          chart: {
355
            xLabel: "Servers",
356
            yLabel: sizedLabel,
357
            yUnit: "%",
358
            yScale: "log",
359
            x: xs,
360
            series: [waitChance],
361
            annotations: [{ x: chosen, label: `${chosen} servers` }],
362
            thresholds: [{ y: target, label: `your ${targetText} target` }],
363
          },
364
        },
365
      ];
366

367
      if (mode === "simulate") {
368
        if (!(trials >= 1000)) throw new InputError("Simulating needs at least 1000 trials.", "trials");
369
        const sim = simulate(
370
          rate,
371
          serviceSeconds,
372
          chosen,
373
          Math.round(trials),
374
          limitSeconds,
375
          ctx?.signal,
376
          ctx ? (fraction) => ctx.progress(fraction) : undefined,
377
        );
378
        /*
379
         * Reported beside the formula rather than instead of it. The interesting case is disagreement:
380
         * if these two diverge by more than sampling error, one of them is wrong, and the fixtures for
381
         * this tool exist to notice that.
382
         *
383
         * ⚠️ `group`, not a label suffixed with a space to dodge a collision. The SDK keys a field by group
384
         * AND label, so the same quantity reported two ways no longer collides.
385
         */
386
        const over = (group: string, value: number): Field[] =>
387
          limit > 0 ? [{ group, label: `Waits over ${limit} ms`, value: percent(value) }] : [];
388
        parts.push({
389
          kind: "fields",
390
          fields: [
391
            { group: "Simulated", label: "Chance of waiting", value: percent(sim.waitedFraction), note: `${sim.counted} arrivals after warmup` },
392
            ...over("Simulated", sim.overFraction),
393
            { group: "Simulated", label: "Mean wait", value: millis(sim.meanWaitSeconds) },
394
            { group: "Formula", label: "Chance of waiting", value: percent(chosenC) },
395
            ...over("Formula", chosenOver),
396
            { group: "Formula", label: "Mean wait", value: millis(chosenWait) },
397
          ],
398
        });
399
      }
400

401
      /*
402
       * Last, and quiet: how the number was reached. The mean wait is here rather than beside the answer because
403
       * it averages over every request, most of which never wait, so it reads as reassurance the p99 does not give.
404
       */
405
      const method = "How this was worked out";
406
      parts.push({
407
        kind: "fields",
408
        role: "method",
409
        fields: [
410
          {
411
            group: method,
412
            label: "Offered load",
413
            value: `${fixed(load, 2)} erlangs`,
414
            note: `${rate} ${rate === 1 ? "request" : "requests"} a second, ${service} ms each: the servers that would be busy if nobody ever queued.`,
415
          },
416
          { group: method, label: "Fewest that keep up", value: String(minimumServers), note: "With fewer, the queue grows without limit." },
417
          {
418
            group: method,
419
            label: "Mean wait",
420
            value: millis(chosenWait),
421
            note: `The average time in the queue with ${chosen} servers, over every request, including those that never wait.`,
422
          },
423
        ],
424
      });
425
      return { kind: "group", parts };
426
    } catch (error) {
427
      if (error instanceof InputError) return { kind: "error", message: error.message, input: error.input };
428
      throw error;
429
    }
430
  },
431
} satisfies Tool<Input>;