@devries-cameron20 / t3code Mirror · read-only
Fork 0

The best way to control Claude Code, Codex and more from any computer or phone

Mirrored from https://github.com/Camo67/t3code.git

Synced Nov 21, 06:00 UTC

main
ts 1,023 lines 34.4 KB
Raw
1 import * as Backfill from "@alchemy.run/domain/Backfill";
2 import type { Routed } from "@alchemy.run/domain/CatchUp";
3 import type { Delivery } from "@alchemy.run/domain/Platform";
4 import * as Effect from "effect/Effect";
5 import * as Semaphore from "effect/Semaphore";
6
7 /**
8 * A deterministic simulation of the backfill protocol: every role runs its
9 * real code over in-process storage, jobs and network, driven by a seeded
10 * scheduler that injects failures, crashes and stale code.
11 */
12
13 /** A seeded PRNG (mulberry32): the same seed explores the same interleaving. */
14 const rng = (seed: number) => {
15 let a = seed >>> 0;
16 return () => {
17 a = (a + 0x6d2b79f5) >>> 0;
18 let t = a;
19 t = Math.imul(t ^ (t >>> 15), t | 1);
20 t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
21 return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
22 };
23 };
24
25 class Crash extends Error {
26 override readonly name = "Crash";
27 }
28
29 export interface Faults {
30 /** Chance a call fails before it reaches its object. */
31 readonly callBefore: number;
32 /** Chance a call runs but its answer is lost. */
33 readonly callAfter: number;
34 /** Chance an exclusive section crashes before it commits (its writes roll back). */
35 readonly crash: number;
36 }
37
38 export const noFaults: Faults = { callBefore: 0, callAfter: 0, crash: 0 };
39
40 /** What one object did: Durable Object requests (calls in, and alarms), and rows read and written. */
41 export interface Stats {
42 requests: number;
43 rowsRead: number;
44 rowsWritten: number;
45 }
46
47 /** One durable object: sorted storage, an exclusive lock, and its scheduled jobs. */
48 class SimObject {
49 readonly data = new Map<string, unknown>();
50 overlay: Map<string, unknown> | undefined;
51 /** Pending jobs by id: when due, and a version so a replaced job's queue entry is skipped. */
52 readonly jobs = new Map<string, { readonly due: number; readonly version: number }>();
53 readonly stats: Stats = { requests: 0, rowsRead: 0, rowsWritten: 0 };
54 /** Requests by call or job, to see what makes an object hot. */
55 readonly methods = new Map<string, number>();
56 /**
57 * In the wall-time model: the milliseconds this object spends running events,
58 * one at a time. An event runs in the first free one at or after it arrives;
59 * awaiting its own outgoing calls doesn't keep the object busy.
60 */
61 busy = new Set<number>();
62 /** Run an event that arrives at `at`: when it ends. */
63 occupy(at: number, service: number) {
64 let slot = Math.ceil(at);
65 while (this.busy.has(slot)) slot++;
66 this.busy.add(slot);
67 return slot + service;
68 }
69 private sorted: Array<string> = [];
70 private dirty = false;
71 constructor(
72 readonly address: string,
73 readonly sim: Sim,
74 /** Runs a job of this object by id. */
75 readonly run: (id: string) => Effect.Effect<void>,
76 ) {}
77
78 private read(key: string) {
79 if (this.overlay?.has(key)) return this.overlay.get(key);
80 return this.data.get(key);
81 }
82
83 private write(key: string, value: unknown) {
84 // A delete leaves the key in the sorted list, skipped when read: only new keys re-sort.
85 if (value === undefined) this.data.delete(key);
86 else {
87 if (!this.data.has(key)) this.dirty = true;
88 this.data.set(key, value);
89 }
90 }
91
92 /** The first index in the sorted keys at or after `key`. */
93 private seek(key: string) {
94 if (this.dirty) {
95 this.sorted = [...this.data.keys()].sort();
96 this.dirty = false;
97 }
98 let lo = 0;
99 let hi = this.sorted.length;
100 while (lo < hi) {
101 const mid = (lo + hi) >>> 1;
102 if (this.sorted[mid]! < key) lo = mid + 1;
103 else hi = mid;
104 }
105 return lo;
106 }
107
108 readonly storage: Backfill.Storage = {
109 get: <A>(key: string) =>
110 Effect.sync(() => {
111 this.stats.rowsRead += 1;
112 return this.read(key) as A | undefined;
113 }),
114 put: (entries) =>
115 Effect.sync(() => {
116 for (const [key, value] of Object.entries(entries)) {
117 this.stats.rowsWritten += 1;
118 if (this.overlay) this.overlay.set(key, value);
119 else this.write(key, value);
120 }
121 }),
122 delete: (keys) =>
123 Effect.sync(() => {
124 for (const key of keys) {
125 this.stats.rowsWritten += 1;
126 if (this.overlay) this.overlay.set(key, undefined);
127 else this.write(key, undefined);
128 }
129 }),
130 list: <A>(options: { prefix: string; startAfter?: string; limit?: number }) =>
131 Effect.sync(() => {
132 const after = options.startAfter;
133 const inRange = (key: string) =>
134 key.startsWith(options.prefix) && (after === undefined || key > after);
135 // Stored keys from the first in range, merged with the open section's new keys.
136 const stored: Array<string> = [];
137 const limit = options.limit ?? Number.POSITIVE_INFINITY;
138 for (
139 let i = this.seek(after !== undefined && after > options.prefix ? after : options.prefix);
140 i < this.sorted.length;
141 i++
142 ) {
143 const key = this.sorted[i]!;
144 if (!key.startsWith(options.prefix)) break;
145 if (!inRange(key) || !this.data.has(key)) continue;
146 stored.push(key);
147 if (stored.length >= limit + (this.overlay?.size ?? 0)) break;
148 }
149 const added = [...(this.overlay?.keys() ?? [])].filter(
150 (key) => inRange(key) && !this.data.has(key),
151 );
152 const keys = added.length > 0 ? [...stored, ...added].sort() : stored;
153 const out: Array<readonly [string, A]> = [];
154 for (const key of keys) {
155 const value = this.read(key);
156 if (value === undefined) continue;
157 out.push([key, value as A]);
158 if (out.length >= limit) break;
159 }
160 this.stats.rowsRead += Math.max(1, out.length);
161 return out;
162 }),
163 exclusive: <A, E>(effect: Effect.Effect<A, E>) => this.section(effect, true),
164 };
165
166 private readonly lock = Semaphore.makeUnsafe(1);
167
168 /**
169 * One exclusive section: its writes commit together, or, when it crashes
170 * before committing, not at all. Client commits pass `crashes: false`.
171 */
172 section<A, E>(effect: Effect.Effect<A, E>, crashes: boolean): Effect.Effect<A, E> {
173 return this.lock.withPermits(1)(
174 Effect.suspend(() => {
175 this.overlay = new Map();
176 return effect.pipe(
177 Effect.tap(() =>
178 crashes && this.sim.chance(this.sim.faults.crash)
179 ? Effect.die(new Crash(`${this.address} crashed before committing`))
180 : Effect.void,
181 ),
182 Effect.tap(() =>
183 Effect.sync(() => {
184 for (const [key, value] of this.overlay!) this.write(key, value);
185 }),
186 ),
187 Effect.ensuring(
188 Effect.sync(() => {
189 this.overlay = undefined;
190 }),
191 ),
192 );
193 }),
194 );
195 }
196
197 readonly jobsApi: Backfill.Jobs = {
198 schedule: (id, afterMillis) => Effect.sync(() => this.sim.schedule(this, id, afterMillis)),
199 };
200 }
201
202 /** A simulated source instance: an event log with routing, like an aggregate. */
203 interface SourceData {
204 readonly ref: Backfill.SourceRef;
205 readonly object: SimObject;
206 readonly events: Array<{
207 readonly seq: number;
208 readonly at: number;
209 readonly keys: ReadonlyArray<string>;
210 }>;
211 /** Runs code that knows the target only from this time on. */
212 staleUntil: number;
213 role: Backfill.Source;
214 }
215
216 /** A simulated consumer key: applies deliveries, deduping by source seq, like a view key. */
217 interface KeyData {
218 readonly key: string;
219 readonly object: SimObject;
220 readonly applied: Array<{ readonly delivery: Delivery; readonly backfilling: boolean }>;
221 readonly checkpoints: Map<string, number>;
222 /** Runs code from before the target's generation until this time. */
223 staleUntil: number;
224 role: Backfill.Consumer;
225 }
226
227 export class Sim {
228 readonly random: () => number;
229 now = 1_000_000;
230 readonly nodes = new Map<string, { object: SimObject; role: Backfill.Node }>();
231 readonly sources = new Map<string, SourceData>();
232 readonly keys = new Map<string, KeyData>();
233 /** Live deliveries waiting to be sent, in order per source (its outbox): retried until they land. */
234 readonly outbox = new Map<string, Array<Delivery>>();
235 /** Every consumer deployed together. */
236 get targets(): ReadonlyArray<string> {
237 return [this.target, ...this.others];
238 }
239
240 /** A key of `target`: the primary target's keys are plain, the others' are prefixed. */
241 keyOf(target: string, key: string) {
242 return target === this.target ? key : `${target}|${key}`;
243 }
244
245 /** The target a key belongs to. */
246 targetOfKey(key: string) {
247 const bar = key.indexOf("|");
248 return bar < 0 ? this.target : key.slice(0, bar);
249 }
250
251 /** Run something just before a run lists `path`: work that lands while it lists the directory. */
252 interject: ((path: string) => Effect.Effect<void>) | undefined = undefined;
253
254 /**
255 * The consumer is keyed by its source: each key hears only from the instance
256 * with its own id (commit each instance's events to a key named after it).
257 */
258 singleSource = false;
259
260 /** The sources each consumer reads; unset, the root sweeps every subtree. */
261 sourcesOf: ((target: string) => ReadonlyArray<string> | undefined) | undefined = undefined;
262
263 /** What the deployed code knows of a consumer. */
264 planOf(target: string): Backfill.Plan {
265 const sources = this.sourcesOf?.(target);
266 return { ...(sources === undefined ? {} : { sources }), singleSource: this.singleSource };
267 }
268
269 /** Every plan, as a deploy announces them. */
270 plans(targets: ReadonlyArray<string> = this.targets) {
271 return Object.fromEntries(targets.map((target) => [target, this.planOf(target)]));
272 }
273
274 /** Whether instances of `source` feed `target`. */
275 feeds(source: string, target: string) {
276 return this.sourcesOf?.(target)?.includes(source) ?? true;
277 }
278
279 /** The target exists (the consumer is deployed). */
280 deployed = false;
281 calls = 0;
282 failures = 0;
283
284 constructor(
285 seed: number,
286 readonly target: string,
287 readonly faults: Faults = noFaults,
288 readonly limits: Backfill.Limits = {
289 ...Backfill.defaultLimits,
290 page: 3,
291 nodePage: 2,
292 apply: 4,
293 leafSize: 3,
294 // Few, shallow leaves: they fill and split all the time.
295 depth: 1,
296 },
297 /** More consumers deployed at the same time: they share the directory and the sources. */
298 readonly others: ReadonlyArray<string> = [],
299 ) {
300 this.random = rng(seed);
301 }
302
303 chance(p: number) {
304 return p > 0 && this.random() < p;
305 }
306
307 /**
308 * A Durable Object keeps the code it started with while calls keep it busy:
309 * a call to one still on older code holds it there for another 20 seconds.
310 */
311 busy<O extends { staleUntil: number }>(object: O): O {
312 if (this.now < object.staleUntil)
313 object.staleUntil = Math.max(object.staleUntil, this.now + 20_000);
314 return object;
315 }
316
317 /**
318 * Latencies of the wall-time model, in milliseconds: a call's round trip, the
319 * time an object spends on one event, and how long an alarm takes to fire.
320 */
321 latency = { rpc: 10, service: 1, alarm: 50 };
322 /**
323 * Run work due at the same time in wall-time order, as a real system would,
324 * rather than in a random order (which explores interleavings, but makes a
325 * busy object's queue hold work that started later).
326 */
327 timed = false;
328 /** In the wall-time model: the time of the work running now, and the latest time anything ended. */
329 vt = 0;
330 makespan = 0;
331 /** In the wall-time model: when the root marked the target's history complete. */
332 completedAt: number | undefined = undefined;
333
334 /**
335 * Every call crosses the network: it may fail before it runs, or after. In the
336 * wall-time model it waits for its object to be free, which is how a hot
337 * object's queue shows up.
338 */
339 private call<A>(
340 target: SimObject,
341 effect: () => Effect.Effect<A>,
342 method = "call",
343 ): Effect.Effect<A> {
344 return Effect.suspend(() => {
345 this.calls += 1;
346 target.stats.requests += 1;
347 target.methods.set(method, (target.methods.get(method) ?? 0) + 1);
348 if (this.chance(this.faults.callBefore)) {
349 this.failures += 1;
350 return Effect.die(new Crash("call failed in transit"));
351 }
352 const caller = this.vt;
353 this.vt = target.occupy(caller + this.latency.rpc / 2, this.latency.service);
354 return effect().pipe(
355 Effect.tap(() =>
356 Effect.sync(() => {
357 this.vt += this.latency.rpc / 2;
358 this.makespan = Math.max(this.makespan, this.vt);
359 }),
360 ),
361 Effect.tap(() => {
362 if (!this.chance(this.faults.callAfter)) return Effect.void;
363 this.failures += 1;
364 return Effect.die(new Crash("answer lost in transit"));
365 }),
366 );
367 });
368 }
369
370 // ------------------------------------------------------------ scheduler
371
372 /** Due jobs and sends, as a binary heap by time (ties in random order). */
373 private readonly queue: Array<{
374 readonly due: number;
375 readonly tie: number;
376 readonly vt: number;
377 readonly run: () => Effect.Effect<void>;
378 }> = [];
379 private versions = 0;
380
381 private push(entry: (typeof this.queue)[number]) {
382 const q = this.queue;
383 q.push(entry);
384 let i = q.length - 1;
385 while (i > 0) {
386 const parent = (i - 1) >> 1;
387 if (this.before(q[parent]!, q[i]!)) break;
388 [q[parent], q[i]] = [q[i]!, q[parent]!];
389 i = parent;
390 }
391 }
392 private before(a: (typeof this.queue)[number], b: (typeof this.queue)[number]) {
393 if (a.due !== b.due) return a.due < b.due;
394 if (this.timed && a.vt !== b.vt) return a.vt < b.vt;
395 return a.tie <= b.tie;
396 }
397 private pop() {
398 const q = this.queue;
399 const top = q[0];
400 const last = q.pop()!;
401 if (q.length > 0) {
402 q[0] = last;
403 let i = 0;
404 while (true) {
405 const l = 2 * i + 1;
406 const r = l + 1;
407 let m = i;
408 if (l < q.length && !this.before(q[m]!, q[l]!)) m = l;
409 if (r < q.length && !this.before(q[m]!, q[r]!)) m = r;
410 if (m === i) break;
411 [q[m], q[i]] = [q[i]!, q[m]!];
412 i = m;
413 }
414 }
415 return top;
416 }
417
418 /** Schedule a job on an object; a job with the same id replaces a pending one. */
419 schedule(object: SimObject, id: string, afterMillis: number) {
420 // The earliest request wins: a job already due sooner isn't postponed.
421 const pending = object.jobs.get(id);
422 if (pending !== undefined && pending.due <= this.now + afterMillis) return;
423 const version = ++this.versions;
424 object.jobs.set(id, { due: this.now + afterMillis, version });
425 const vt = this.vt + afterMillis + this.latency.alarm;
426 this.push({
427 due: this.now + afterMillis,
428 tie: this.random(),
429 vt,
430 run: () =>
431 Effect.suspend(() => {
432 if (object.jobs.get(id)?.version !== version) return Effect.void;
433 object.jobs.delete(id);
434 object.stats.requests += 1;
435 const job = `job:${id.split(":")[0]}`;
436 object.methods.set(job, (object.methods.get(job) ?? 0) + 1);
437 this.vt = object.occupy(vt, this.latency.service);
438 return object.run(id).pipe(
439 // A failed job is retried, like a durable callback.
440 Effect.catchCause(() =>
441 Effect.sync(() => {
442 if (!object.jobs.has(id)) this.schedule(object, id, 1_000);
443 }),
444 ),
445 Effect.ensuring(
446 Effect.sync(() => {
447 this.makespan = Math.max(this.makespan, this.vt);
448 }),
449 ),
450 );
451 }),
452 });
453 }
454
455 /** Queue the next send of a source's outbox, unless one is queued already. */
456 private sending = new Set<string>();
457 private queueSend(stream: string) {
458 if (this.sending.has(stream)) return;
459 this.sending.add(stream);
460 const vt = this.vt;
461 this.push({
462 due: this.now,
463 tie: this.random(),
464 vt,
465 run: () =>
466 Effect.suspend(() => {
467 this.sending.delete(stream);
468 const queue = this.outbox.get(stream) ?? [];
469 if (queue.length === 0) return Effect.void;
470 this.vt = vt;
471 return this.sendOne(queue[0]!).pipe(
472 Effect.tap(() => Effect.sync(() => queue.shift())),
473 // A failed send stays at the head.
474 Effect.catchCause(() => Effect.void),
475 Effect.ensuring(
476 Effect.sync(() => {
477 if (queue.length > 0) this.queueSend(stream);
478 }),
479 ),
480 );
481 }),
482 });
483 }
484
485 readonly net: Backfill.Network = {
486 node: {
487 register: (path, ref) =>
488 this.call(
489 this.node(path).object,
490 () => this.node(path).role.register(path, ref),
491 "register",
492 ),
493 child: (path, child) =>
494 this.call(this.node(path).object, () => this.node(path).role.child(path, child), "child"),
495 list: (path, after) =>
496 Effect.andThen(this.interject?.(path) ?? Effect.void, () =>
497 this.call(this.node(path).object, () => this.node(path).role.list(path, after), "list"),
498 ),
499 },
500 source: {
501 read: (ref, target, key, after, limit) =>
502 this.call(
503 this.source(ref).object,
504 () => this.busy(this.source(ref)).role.read(target, key, after, limit),
505 "read",
506 ),
507 cursor: (ref, target) =>
508 this.call(
509 this.source(ref).object,
510 () => this.busy(this.source(ref)).role.cursor(target),
511 "cursor",
512 ),
513 log: (ref, after, limit) =>
514 this.call(
515 this.source(ref).object,
516 () => this.busy(this.source(ref)).role.log(after, limit),
517 "log",
518 ),
519 handoff: (ref, target, key, through) =>
520 this.call(
521 this.source(ref).object,
522 () => this.busy(this.source(ref)).role.handoff(target, key, through),
523 "handoff",
524 ),
525 },
526 consumer: {
527 push: (target, key, deliveries) =>
528 this.call(
529 this.key(key).object,
530 () => this.busy(this.key(key)).role.push(target, deliveries),
531 "push",
532 ),
533 ready: (target, key, waitMillis) =>
534 this.call(
535 this.key(key).object,
536 () => this.busy(this.key(key)).role.ready(target, waitMillis),
537 "ready",
538 ),
539 start: (target, key, ref, waitMillis) =>
540 this.call(
541 this.key(key).object,
542 () => this.busy(this.key(key)).role.start(target, ref, waitMillis),
543 "start",
544 ),
545 },
546 scanner: {
547 scan: (target, ref, waitMillis) =>
548 this.call(
549 this.scanner(target, ref).object,
550 () => this.scanner(target, ref).role.scan(target, ref, waitMillis),
551 "scan",
552 ),
553 ready: (target, ref, waitMillis) =>
554 this.call(
555 this.scanner(target, ref).object,
556 () => this.scanner(target, ref).role.ready(target, waitMillis),
557 "scanner-ready",
558 ),
559 kick: (target, ref) =>
560 this.call(
561 this.scanner(target, ref).object,
562 () => this.scanner(target, ref).role.kick(target, ref),
563 "kick",
564 ),
565 },
566 relay: {
567 run: (name, run, items) =>
568 this.call(this.relay(name), () => this.relays.run(name, run, items), "relay"),
569 },
570 run: {
571 begin: (target, plan) =>
572 this.call(
573 this.run_(target).object,
574 () => this.run_(target).role.begin(target, plan),
575 "begin",
576 ),
577 phase: (target) =>
578 this.call(this.run_(target).object, () => this.run_(target).role.phase(target), "phase"),
579 progress: (target) =>
580 this.call(
581 this.run_(target).object,
582 () => this.run_(target).role.progress(target),
583 "progress",
584 ),
585 },
586 };
587
588 /** The relays of runs: stateless, one object each. */
589 readonly relayObjects = new Map<string, SimObject>();
590 private readonly relays = Backfill.makeRelay(this.net);
591 relay(name: string) {
592 let object = this.relayObjects.get(name);
593 if (!object) {
594 object = new SimObject(`relay:${name}`, this, () => Effect.void);
595 this.relayObjects.set(name, object);
596 }
597 return object;
598 }
599
600 /** Each source instance's scanner, per target: an object of the consumer's class. */
601 readonly scanners = new Map<string, { object: SimObject; role: Backfill.Scanner }>();
602 scanner(target: string, ref: Backfill.SourceRef) {
603 const name = `${target}|${ref.source}/${ref.id}`;
604 let found = this.scanners.get(name);
605 if (!found) {
606 const object = new SimObject(`scanner:${name}`, this, (id) =>
607 this.scanners.get(name)!.role.run(id),
608 );
609 found = {
610 object,
611 role: Backfill.makeScanner(
612 object.storage,
613 object.jobsApi,
614 this.net,
615 {
616 // The consumer's own code routes the rows it reads from a source's log.
617 route: (target, ref, rows) =>
618 Effect.sync(() =>
619 (rows as SourceData["events"]).map((event) => ({
620 seq: event.seq,
621 deliveries: this.deliveries(this.source(ref), event, true, target),
622 })),
623 ),
624 },
625 this.limits,
626 ),
627 };
628 this.scanners.set(name, found);
629 }
630 return found;
631 }
632
633 /**
634 * Each consumer's run root. Like the deploy's Workflow, it makes one pass at a
635 * time (each one try at everything), again a second later until done.
636 */
637 readonly runs = new Map<string, { object: SimObject; role: Backfill.Run }>();
638 run_(target: string) {
639 let found = this.runs.get(target);
640 if (!found) {
641 const object = new SimObject(`run:${target}`, this, (id) =>
642 this.runs.get(target)!.role.run(id),
643 );
644 found = {
645 object,
646 role: Backfill.makeRun(object.storage, object.jobsApi, this.net, {
647 waitMillis: 0,
648 againMillis: 1_000,
649 }),
650 };
651 this.runs.set(target, found);
652 }
653 return found;
654 }
655
656 /** The targets whose run is complete. */
657 completed() {
658 return this.targets.filter(
659 (target) =>
660 (
661 this.runs.get(target)?.object.data.get(`run:${encodeURIComponent(target)}`) as
662 | { phase: string }
663 | undefined
664 )?.phase === "complete",
665 );
666 }
667
668 node(path: string) {
669 let node = this.nodes.get(path);
670 if (!node) {
671 const object = new SimObject(`node:${path}`, this, (id) => this.node(path).role.run(id));
672 node = {
673 object,
674 role: Backfill.makeNode(object.storage, object.jobsApi, this.net, this.limits),
675 };
676 this.nodes.set(path, node);
677 }
678 return node;
679 }
680
681 private streamOf(ref: Backfill.SourceRef) {
682 return `${ref.source}/${ref.id}`;
683 }
684
685 /** An event's deliveries to one target (or every target). */
686 private deliveries(
687 source: SourceData,
688 event: SourceData["events"][number],
689 history = false,
690 only?: string,
691 ): Array<Delivery> {
692 const stream = this.streamOf(source.ref);
693 return this.targets
694 .filter((target) => only === undefined || target === only)
695 .flatMap((target) => {
696 const [, rest] = target.split(":") as [string, string];
697 const [name, generation] = rest.split("#") as [string, string | undefined];
698 return event.keys.map((key) => ({
699 target: {
700 kind: "view" as const,
701 name,
702 ...(generation ? { generation: Number(generation) } : {}),
703 },
704 key: this.keyOf(target, key),
705 source: stream,
706 seq: event.seq,
707 origin: source.ref.source,
708 tag: "E",
709 event: { _tag: "E", seq: event.seq },
710 envelope: { id: source.ref.id, stream, seq: event.seq, at: event.at, commandId: "" },
711 ...(history ? { history } : {}),
712 }));
713 });
714 }
715
716 source(ref: Backfill.SourceRef): SourceData {
717 const id = this.streamOf(ref);
718 let source = this.sources.get(id);
719 if (!source) {
720 const object = new SimObject(`source:${id}`, this, () => this.sources.get(id)!.role.flush);
721 const data: SourceData = {
722 ref,
723 object,
724 events: [],
725 staleUntil: 0,
726 role: undefined as never,
727 };
728 const knows = () => this.deployed && this.now >= data.staleUntil;
729 data.role = Backfill.makeSource(
730 object.storage,
731 object.jobsApi,
732 this.net,
733 {
734 ref,
735 model: () => (knows() ? this.targets : []),
736 singleSource: () => this.singleSource,
737 log: (after, limit) =>
738 Effect.sync(() => data.events.filter((event) => event.seq > after).slice(0, limit)),
739 version: Effect.sync(() => data.events.length),
740 // Kept in the object's storage, so a crashed step rolls it back with the rest.
741 routed: object.storage.get<Routed>("routed"),
742 markLive: (target) =>
743 Effect.flatMap(object.storage.get<Routed>("routed"), (routed) =>
744 object.storage.put({ routed: { ...routed, [target]: data.events.length } }),
745 ),
746 },
747 this.limits,
748 );
749 source = data;
750 this.sources.set(id, source);
751 }
752 return source;
753 }
754
755 key(key: string): KeyData {
756 let data = this.keys.get(key);
757 if (!data) {
758 const object = new SimObject(`key:${key}`, this, (id) =>
759 this.keys.get(key)!.role.merge(id.slice("bf-merge:".length)),
760 );
761 const keyData: KeyData = {
762 key,
763 object,
764 applied: [],
765 checkpoints: new Map(),
766 staleUntil: this.keyStaleUntil(key),
767 role: undefined as never,
768 };
769 keyData.role = Backfill.makeConsumer(
770 object.storage,
771 object.jobsApi,
772 this.net,
773 {
774 key,
775 // Older code runs the previous generation of the consumer.
776 target: () => {
777 const target = this.targetOfKey(key);
778 return this.now >= keyData.staleUntil ? target : target.replace(/#\d+$/, "");
779 },
780 singleSource: () => this.singleSource,
781 // The key's own code routes the rows it reads from its source's log.
782 history: (ref, rows) =>
783 Effect.sync(() =>
784 (rows as SourceData["events"]).map((event) => ({
785 seq: event.seq,
786 deliveries: this.deliveries(this.source(ref), event, true, this.targetOfKey(key)),
787 })),
788 ),
789 apply: (deliveries) => Effect.sync(() => this.apply(keyData, deliveries, true)),
790 },
791 this.limits,
792 );
793 data = keyData;
794 this.keys.set(key, data);
795 }
796 return data;
797 }
798
799 private apply(key: KeyData, deliveries: ReadonlyArray<Delivery>, backfilling: boolean) {
800 for (const delivery of deliveries) {
801 if ((key.checkpoints.get(delivery.source) ?? 0) >= delivery.seq) continue;
802 key.checkpoints.set(delivery.source, delivery.seq);
803 key.applied.push({ delivery, backfilling });
804 }
805 }
806
807 /**
808 * Commit an event on a source, as an aggregate does: decide routing under its
809 * lock, then send what goes out live. The first commit lists it in the directory.
810 */
811 commit(sourceId: string, keys: ReadonlyArray<string>, staleUntil = 0) {
812 const [name, id] = sourceId.split("/") as [string, string];
813 const source = this.source({ source: name, id });
814 if (source.events.length === 0) source.staleUntil = staleUntil;
815 this.busy(source);
816 const knows = this.deployed && this.now >= source.staleUntil;
817 // The first commit lists the instance in the directory before it persists.
818 const register =
819 source.events.length === 0
820 ? this.retry(
821 this.net.node.register(Backfill.leafOf(source.ref, this.limits.depth), source.ref),
822 )
823 : Effect.void;
824 return register.pipe(
825 Effect.andThen(
826 source.object
827 .section(
828 Effect.gen({ self: this }, function* () {
829 const before = source.events.length;
830 const event = { seq: before + 1, at: this.now, keys };
831 source.events.push(event);
832 const storage = source.object.storage;
833 const routed = yield* storage.get<Routed>("routed");
834 if (!knows) {
835 // Code without the targets: it routes nothing to them, and its cursors stay.
836 yield* storage.put({ routed: { ...routed } });
837 return [] as ReadonlyArray<Delivery>;
838 }
839 let next: Record<string, number> = {
840 ...(routed ?? Object.fromEntries(this.targets.map((t) => [t, before]))),
841 };
842 const send: Array<Delivery> = [];
843 for (const target of this.targets) {
844 const deliveries = this.deliveries(source, event, false, target);
845 if ((next[target] ?? 0) === before) {
846 next = { ...next, [target]: before + 1 };
847 send.push(...deliveries);
848 } else {
849 // Behind here: withheld, for its reader to read from the log.
850 yield* source.role.onCommit(target);
851 }
852 }
853 yield* storage.put({ routed: next });
854 return send as ReadonlyArray<Delivery>;
855 }),
856 // A client's command: it is retried by the client, never lost halfway.
857 false,
858 )
859 .pipe(
860 Effect.tap((send) =>
861 Effect.sync(() => {
862 for (const delivery of send) {
863 const queue = this.outbox.get(delivery.source) ?? [];
864 queue.push(delivery);
865 this.outbox.set(delivery.source, queue);
866 this.queueSend(delivery.source);
867 }
868 }),
869 ),
870 ),
871 ),
872 );
873 }
874
875 /** Retry a call until it lands (a durable outbox would). */
876 retry<A>(effect: Effect.Effect<A>): Effect.Effect<A> {
877 return Effect.suspend(function loop(): Effect.Effect<A> {
878 return effect.pipe(Effect.catchCause(() => Effect.suspend(loop)));
879 });
880 }
881
882 /** Keys that run older code for a while: by key, until when. */
883 readonly staleKeys = new Map<string, number>();
884 private keyStaleUntil(key: string) {
885 return this.staleKeys.get(key) ?? 0;
886 }
887
888 /** Deliver one queued live delivery. */
889 private sendOne(delivery: Delivery) {
890 const key = this.key(delivery.key);
891 key.object.stats.requests += 1;
892 this.vt = key.object.occupy(this.vt + this.latency.rpc / 2, this.latency.service);
893 // Older code refuses a newer generation's delivery (its apply dies); the sender retries.
894 if (this.now < this.busy(key).staleUntil)
895 return Effect.die(new Crash("key still on older code"));
896 return key.role.admit(this.targetOfKey(delivery.key), [delivery]).pipe(
897 Effect.flatMap((apply) =>
898 apply
899 ? key.object.storage.exclusive(Effect.sync(() => this.apply(key, [delivery], false)))
900 : Effect.void,
901 ),
902 Effect.ensuring(
903 Effect.sync(() => {
904 this.makespan = Math.max(this.makespan, this.vt);
905 }),
906 ),
907 );
908 }
909
910 /** Run the next due job or send (ties in random order), or move the clock to it. `false` when idle. */
911 step(): Effect.Effect<boolean> {
912 return Effect.suspend(() => {
913 const head = this.queue[0];
914 if (head === undefined) return Effect.succeed(false);
915 if (head.due > this.now) {
916 this.now = head.due;
917 return Effect.succeed(true);
918 }
919 return this.pop()!.run().pipe(Effect.as(true));
920 });
921 }
922
923 /** Requests, rows read and rows written, by kind of object and in total. */
924 totals() {
925 const sum = (objects: Iterable<SimObject>) => {
926 const total: Stats = { requests: 0, rowsRead: 0, rowsWritten: 0 };
927 let hottest = 0;
928 for (const object of objects) {
929 total.requests += object.stats.requests;
930 total.rowsRead += object.stats.rowsRead;
931 total.rowsWritten += object.stats.rowsWritten;
932 hottest = Math.max(hottest, object.stats.requests);
933 }
934 return { ...total, hottest };
935 };
936 const nodes = sum([...this.nodes.values()].map((n) => n.object));
937 const sources = sum([...this.sources.values()].map((n) => n.object));
938 const keys = sum([...this.keys.values()].map((n) => n.object));
939 return {
940 nodes,
941 sources,
942 keys,
943 total: {
944 requests: nodes.requests + sources.requests + keys.requests,
945 rowsRead: nodes.rowsRead + sources.rowsRead + keys.rowsRead,
946 rowsWritten: nodes.rowsWritten + sources.rowsWritten + keys.rowsWritten,
947 },
948 directory: {
949 nodes: this.nodes.size,
950 // Hash digits below a source's subtree root (`A:3f` is 2 deep).
951 depth: Math.max(
952 0,
953 ...[...this.nodes.keys()].map((path) => path.slice(path.indexOf(":") + 1).length),
954 ),
955 },
956 };
957 }
958
959 /** Reset every counter and the wall-time model (after seeding, before the deploy). */
960 resetMeasures() {
961 for (const object of [
962 ...[...this.nodes.values()].map((n) => n.object),
963 ...[...this.sources.values()].map((n) => n.object),
964 ...[...this.keys.values()].map((n) => n.object),
965 ]) {
966 object.stats.requests = 0;
967 object.stats.rowsRead = 0;
968 object.stats.rowsWritten = 0;
969 object.methods.clear();
970 object.busy.clear();
971 }
972 this.vt = 0;
973 this.makespan = 0;
974 this.completedAt = undefined;
975 }
976
977 /**
978 * Deploy the consumer: code that knows it, and the news of it. Instances
979 * running at the time keep their older code until they have been idle.
980 */
981 deploy(options: { readonly running?: boolean } = {}) {
982 this.deployed = true;
983 if (options.running)
984 for (const source of this.sources.values())
985 source.staleUntil = Math.max(source.staleUntil, this.now + 20_000);
986 return Effect.forEach(
987 this.targets,
988 (target) => this.retry(this.net.run.begin(target, this.planOf(target))),
989 { discard: true },
990 );
991 }
992
993 /** Run until nothing is left to do, interleaving `actions` (client commits). */
994 run(
995 actions: Array<() => Effect.Effect<unknown>> = [],
996 options: { readonly maxSteps?: number } = {},
997 ) {
998 return Effect.gen({ self: this }, function* () {
999 const pending = [...actions];
1000 for (let steps = 0; steps < (options.maxSteps ?? 200_000); steps++) {
1001 if (pending.length > 0 && this.random() < 0.2) {
1002 this.now += 1;
1003 yield* pending.shift()!();
1004 continue;
1005 }
1006 const busy = yield* this.step();
1007 if (this.completedAt === undefined && this.completed().includes(this.target))
1008 this.completedAt = this.vt;
1009 if (!busy && pending.length === 0) return steps;
1010 if (!busy) {
1011 this.now += 1;
1012 yield* pending.shift()!();
1013 }
1014 }
1015 return yield* Effect.die(new Error("the simulation did not settle"));
1016 });
1017 }
1018
1019 /** Which targets' runs are complete. */
1020 status() {
1021 return Effect.sync(() => ({ complete: this.completed() }));
1022 }
1023 }