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

main
ts 471 lines 17.4 KB
Raw
1 import * as Backfill from "@alchemy.run/domain/Backfill";
2 import { describe, expect, it } from "@alchemy.run/test";
3 import * as Effect from "effect/Effect";
4 import { type Faults, noFaults, Sim } from "./Backfill.sim.ts";
5
6 const TARGET = "view:V#1";
7
8 /**
9 * Check what a finished simulation must hold:
10 * - every key received exactly the events routed to it, once each, in seq order per source;
11 * - what a key applied while backfilling is in timestamp order, `(at, stream, seq)`;
12 * - every source routes the target live again, and no backfill state is left behind;
13 * - the root reports the target complete.
14 */
15 const verify = (sim: Sim) =>
16 Effect.gen(function* () {
17 const expected = new Map<string, Array<string>>();
18 for (const source of sim.sources.values()) {
19 const stream = `${source.ref.source}/${source.ref.id}`;
20 for (const event of source.events) {
21 for (const target of sim.targets) {
22 for (const key of event.keys.map((k) => sim.keyOf(target, k))) {
23 const list = expected.get(key) ?? [];
24 list.push(`${stream}#${event.seq}`);
25 expected.set(key, list);
26 }
27 }
28 }
29 }
30 for (const [key, events] of expected) {
31 const applied = sim.keys.get(key)?.applied ?? [];
32 const ids = applied.map(({ delivery }) => `${delivery.source}#${delivery.seq}`);
33 // Exactly once each.
34 expect([...ids].sort()).toEqual([...events].sort());
35 // In seq order per source.
36 const last = new Map<string, number>();
37 for (const { delivery } of applied) {
38 expect(delivery.seq).toBeGreaterThan(last.get(delivery.source) ?? 0);
39 last.set(delivery.source, delivery.seq);
40 }
41 // Everything the merge pulled is applied in timestamp order. Live deliveries
42 // keep their source's order, but may arrive after a later one was applied.
43 const backfilled = applied
44 .filter(({ backfilling, delivery }) => backfilling && delivery.history)
45 .map(({ delivery }) => delivery);
46 const order = (d: (typeof backfilled)[number]) =>
47 [String(d.envelope.at).padStart(15, "0"), d.source, String(d.seq).padStart(12, "0")].join(
48 ":",
49 );
50 expect(backfilled.map(order)).toEqual([...backfilled.map(order)].sort());
51 }
52 for (const source of sim.sources.values()) {
53 for (const target of sim.targets.filter((t) => sim.feeds(source.ref.source, t))) {
54 expect(
55 (source.object.data.get("routed") as Record<string, number> | undefined)?.[target],
56 ).toBe(source.events.length);
57 }
58 expect(
59 // A source keeps where its reader started (`bf:from:`), for a reader that asks again.
60 [...source.object.data.keys()].filter(
61 (key) => key.startsWith("bf:") && !key.startsWith("bf:q-") && !key.startsWith("bf:from:"),
62 ),
63 ).toEqual([]);
64 }
65 for (const key of sim.keys.values()) {
66 expect(
67 [...key.object.data.keys()].filter(
68 (row) => row.startsWith("bf:") && !row.startsWith("bf:done:"),
69 ),
70 ).toEqual([]);
71 }
72 for (const target of sim.targets) expect((yield* sim.status()).complete).toContain(target);
73 });
74
75 /** Commit `count` events on `sources` instances, each routed to one of `keys` keys. */
76 const history = (sim: Sim, sources: number, count: number, keys: number, prefix = "s") =>
77 Array.from({ length: count }, (_, i) => () => {
78 sim.now += 1;
79 return sim.commit(`A/${prefix}${i % sources}`, [`k${(i * 7) % keys}`]);
80 });
81
82 const scenario = (
83 name: string,
84 run: (sim: Sim) => Effect.Effect<void>,
85 options: {
86 readonly faults?: Faults;
87 readonly seeds?: number;
88 /** More consumers deployed at the same time. */
89 readonly others?: ReadonlyArray<string>;
90 } = {},
91 ) =>
92 it.effect(name, () =>
93 Effect.forEach(
94 Array.from({ length: options.seeds ?? 20 }, (_, seed) => seed + 1),
95 (seed) =>
96 Effect.gen(function* () {
97 const sim = new Sim(seed, TARGET, options.faults ?? noFaults, undefined, options.others);
98 yield* run(sim);
99 yield* verify(sim);
100 }).pipe(Effect.annotateLogs({ seed })),
101 { discard: true },
102 ),
103 );
104
105 /** History recorded before the consumer existed, then a deploy, then the backfill. */
106 const backfill = (sim: Sim, sources: number, events: number, keys: number) =>
107 Effect.gen(function* () {
108 for (const commit of history(sim, sources, events, keys)) yield* commit();
109 yield* sim.deploy();
110 yield* sim.run();
111 });
112
113 describe("Domain backfill (simulated)", () => {
114 scenario("a consumer with no history completes", (sim) =>
115 Effect.gen(function* () {
116 yield* sim.deploy();
117 yield* sim.run();
118 }),
119 );
120
121 scenario("one source, one key", (sim) => backfill(sim, 1, 12, 1));
122
123 scenario("many sources and keys, applied in timestamp order", (sim) => backfill(sim, 9, 60, 5));
124
125 scenario("a hot key fed by every source", (sim) => backfill(sim, 25, 80, 1));
126
127 scenario("leaves that fill split, and a run reaches the instances they moved", (sim) =>
128 Effect.gen(function* () {
129 yield* backfill(sim, 60, 120, 4);
130 // 60 instances over 16 leaves of 3: leaves split into deeper children.
131 const splits = [...sim.nodes.entries()].filter(([, node]) => node.object.data.get("split"));
132 expect(splits.length).toBeGreaterThan(0);
133 expect(
134 Math.max(...[...sim.nodes.keys()].map((path) => path.slice(path.indexOf(":") + 1).length)),
135 ).toBeGreaterThan(1);
136 }),
137 );
138
139 scenario(
140 "an instance that lists itself in a new leaf while a run lists the directory is caught up",
141 (sim) =>
142 Effect.gen(function* () {
143 for (const commit of history(sim, 3, 9, 2)) yield* commit();
144 const linked = new Set(sim.nodes.keys());
145 let interjected = false;
146 // While a run lists a node, an instance lists itself in a leaf that isn't linked yet.
147 sim.interject = (path) => {
148 if (interjected || path === "") return Effect.void;
149 interjected = true;
150 for (let i = 0; ; i++) {
151 const leaf = Backfill.leafOf({ source: "A", id: `n${i}` }, sim.limits.depth);
152 if (!linked.has(leaf)) {
153 sim.now += 1;
154 return sim.commit(`A/n${i}`, ["k0"]);
155 }
156 }
157 };
158 yield* sim.deploy();
159 yield* sim.run();
160 expect(interjected).toBe(true);
161 }),
162 );
163
164 /** Commit `count` events, each to the key named after its instance: a view keyed by its source. */
165 const own = (sim: Sim, sources: number, count: number, prefix = "s") =>
166 Array.from({ length: count }, (_, i) => () => {
167 sim.now += 1;
168 return sim.commit(`A/${prefix}${i % sources}`, [`${prefix}${i % sources}`]);
169 });
170
171 scenario("keyed by its source: each key takes its history as soon as its source has it", (sim) =>
172 Effect.gen(function* () {
173 sim.singleSource = true;
174 for (const commit of own(sim, 8, 60)) yield* commit();
175 yield* sim.deploy();
176 yield* sim.run();
177 }),
178 );
179
180 scenario("keyed by its source, with commits during the backfill and new instances", (sim) =>
181 Effect.gen(function* () {
182 sim.singleSource = true;
183 for (const commit of own(sim, 6, 40)) yield* commit();
184 yield* sim.deploy();
185 yield* sim.run([...own(sim, 6, 20), ...own(sim, 3, 9, "new")]);
186 }),
187 );
188
189 scenario("keyed by its source, with instances still on older code", (sim) =>
190 Effect.gen(function* () {
191 sim.singleSource = true;
192 for (let i = 0; i < 24; i++) {
193 sim.now += 1;
194 yield* sim.commit(`A/s${i % 6}`, [`s${i % 6}`], i % 3 === 0 ? sim.now + 120_000 : 0);
195 }
196 yield* sim.deploy({ running: true });
197 const traffic = Array.from({ length: 12 }, (_, i) => () => {
198 sim.now += 10_000;
199 return sim.commit(`A/s${i % 2}`, [`s${i % 2}`]);
200 });
201 yield* sim.run(traffic);
202 }),
203 );
204
205 scenario(
206 "keyed by its source: an instance created on older code after the run starts its key on the deployed code",
207 (sim) =>
208 Effect.gen(function* () {
209 sim.singleSource = true;
210 for (const commit of own(sim, 4, 16)) yield* commit();
211 yield* sim.deploy();
212 yield* sim.run();
213 // A host still on the code from before the deploy creates an instance the run never listed.
214 sim.now += 1;
215 yield* sim.commit("A/late", ["late"], sim.now + 60_000);
216 sim.now += 1;
217 yield* sim.commit("A/late", ["late"]);
218 yield* sim.run([
219 () => {
220 sim.now += 61_000;
221 return sim.commit("A/late", ["late"]);
222 },
223 ]);
224 }),
225 );
226
227 scenario(
228 "keyed by its source, with faults",
229 (sim) =>
230 Effect.gen(function* () {
231 sim.singleSource = true;
232 for (const commit of own(sim, 8, 60)) yield* commit();
233 yield* sim.deploy();
234 yield* sim.run(own(sim, 8, 16));
235 }),
236 { faults: { callBefore: 0.08, callAfter: 0.08, crash: 0.08 }, seeds: 60 },
237 );
238
239 scenario("a run walks only the subtrees of the sources the consumer reads", (sim) =>
240 Effect.gen(function* () {
241 sim.sourcesOf = () => ["A"];
242 // Instances of a source the consumer doesn't read: listed in their own subtree.
243 for (let i = 0; i < 12; i++) {
244 sim.now += 1;
245 yield* sim.commit(`B/b${i}`, []);
246 }
247 for (const commit of history(sim, 6, 30, 3)) yield* commit();
248 yield* sim.deploy();
249 yield* sim.run();
250 for (const source of sim.sources.values())
251 if (source.ref.source === "B") expect(source.object.stats.requests).toBe(0);
252 expect([...sim.nodes.keys()].some((path) => path.startsWith("B:"))).toBe(true);
253 }),
254 );
255
256 scenario("an event routed to several keys", (sim) =>
257 Effect.gen(function* () {
258 for (let i = 0; i < 30; i++) {
259 sim.now += 1;
260 yield* sim.commit(`A/s${i % 4}`, [`k${i % 3}`, `k${(i + 1) % 3}`]);
261 }
262 yield* sim.deploy();
263 yield* sim.run();
264 }),
265 );
266
267 scenario("commits during the backfill: to scanned sources, new keys, and new instances", (sim) =>
268 Effect.gen(function* () {
269 for (const commit of history(sim, 6, 40, 4)) yield* commit();
270 yield* sim.deploy();
271 yield* sim.run([...history(sim, 6, 20, 6, "s"), ...history(sim, 3, 9, 4, "new")]);
272 }),
273 );
274
275 scenario("instances still on older code catch up once they run the deployed code", (sim) =>
276 Effect.gen(function* () {
277 for (let i = 0; i < 20; i++) {
278 sim.now += 1;
279 // Every third instance keeps running code without the target for a while.
280 yield* sim.commit(`A/s${i % 6}`, [`k${i % 3}`], i % 3 === 0 ? sim.now + 120_000 : 0);
281 }
282 yield* sim.deploy();
283 yield* sim.run();
284 }),
285 );
286
287 scenario("a run reports its progress: every subtree and instance, once it is complete", (sim) =>
288 Effect.gen(function* () {
289 yield* backfill(sim, 9, 60, 5);
290 const progress = yield* sim.run_(TARGET).role.progress(TARGET);
291 expect(progress.phase).toBe("complete");
292 expect(progress.subtrees).toBeGreaterThan(0);
293 expect(progress.done).toBe(progress.subtrees);
294 // Two passes for a consumer with many sources: each instance's scanner, in the last.
295 expect(progress.instances).toBeGreaterThanOrEqual(9);
296 expect(progress.passes).toBeGreaterThanOrEqual(1);
297 }),
298 );
299
300 scenario(
301 "a run started again with another plan answers so, and keeps the plan it started with",
302 (sim) =>
303 Effect.gen(function* () {
304 for (const commit of history(sim, 5, 20, 3)) yield* commit();
305 yield* sim.deploy();
306 const other = { ...sim.planOf(TARGET), sources: ["A", "B"] };
307 const begun = yield* sim.run_(TARGET).role.begin(TARGET, other);
308 expect(begun.status).toBe("changed");
309 if (begun.status === "changed") expect(begun.started).toEqual(sim.planOf(TARGET));
310 yield* sim.run();
311 // Once complete, the same plan finds it complete, and another still answers so.
312 expect((yield* sim.run_(TARGET).role.begin(TARGET, sim.planOf(TARGET))).status).toBe(
313 "complete",
314 );
315 expect((yield* sim.run_(TARGET).role.begin(TARGET, other)).status).toBe("changed");
316 }),
317 );
318
319 scenario("a run started again, from several places, runs once", (sim) =>
320 Effect.gen(function* () {
321 for (const commit of history(sim, 5, 20, 3)) yield* commit();
322 yield* sim.deploy();
323 yield* sim.retry(sim.net.run.begin(TARGET, sim.planOf(TARGET)));
324 yield* sim.run();
325 yield* sim.retry(sim.net.run.begin(TARGET, sim.planOf(TARGET)));
326 yield* sim.run();
327 }),
328 );
329
330 scenario(
331 "calls that fail in transit, before or after they run",
332 (sim) => backfill(sim, 8, 50, 4),
333 { faults: { callBefore: 0.1, callAfter: 0.1, crash: 0 } },
334 );
335
336 scenario("objects that crash before committing a step", (sim) => backfill(sim, 8, 50, 4), {
337 faults: { callBefore: 0, callAfter: 0, crash: 0.1 },
338 });
339
340 scenario(
341 "every fault at once, with commits during the backfill",
342 (sim) =>
343 Effect.gen(function* () {
344 for (const commit of history(sim, 7, 40, 4)) yield* commit();
345 yield* sim.deploy();
346 yield* sim.run([...history(sim, 7, 25, 5), ...history(sim, 3, 10, 4, "new")]);
347 }),
348 { faults: { callBefore: 0.08, callAfter: 0.08, crash: 0.08 }, seeds: 40 },
349 );
350
351 scenario(
352 "an instance created on older code after the backfill completed is caught up by its leaf",
353 (sim) =>
354 Effect.gen(function* () {
355 for (const commit of history(sim, 4, 16, 3)) yield* commit();
356 yield* sim.deploy();
357 yield* sim.run();
358 // A host still on the code from before the deploy creates an instance, then
359 // moves to the deployed code; its history reaches keys that already finished.
360 sim.now += 1;
361 yield* sim.commit("A/late", ["k0"], sim.now + 60_000);
362 sim.now += 1;
363 yield* sim.commit("A/late", ["k1"]);
364 yield* sim.run([
365 () => {
366 sim.now += 61_000;
367 return sim.commit("A/late", ["k0"]);
368 },
369 ]);
370 }),
371 );
372
373 scenario(
374 "older code and faults together",
375 (sim) =>
376 Effect.gen(function* () {
377 for (let i = 0; i < 30; i++) {
378 sim.now += 1;
379 yield* sim.commit(`A/s${i % 6}`, [`k${i % 4}`], i % 4 === 0 ? sim.now + 90_000 : 0);
380 }
381 yield* sim.deploy();
382 yield* sim.run(history(sim, 6, 12, 5));
383 }),
384 { faults: { callBefore: 0.05, callAfter: 0.05, crash: 0.05 }, seeds: 30 },
385 );
386
387 scenario(
388 "stress: every fault, many seeds",
389 (sim) =>
390 Effect.gen(function* () {
391 for (const commit of history(sim, 10, 50, 6)) yield* commit();
392 yield* sim.deploy();
393 yield* sim.run([...history(sim, 10, 20, 8), ...history(sim, 4, 8, 6, "new")]);
394 }),
395 { faults: { callBefore: 0.1, callAfter: 0.1, crash: 0.1 }, seeds: 300 },
396 );
397
398 scenario(
399 "consumer keys still on older code refuse messages until they run the deployed code",
400 (sim) =>
401 Effect.gen(function* () {
402 for (let k = 0; k < 4; k++) if (k % 2 === 0) sim.staleKeys.set(`k${k}`, sim.now + 200_000);
403 for (const commit of history(sim, 6, 30, 4)) yield* commit();
404 yield* sim.deploy();
405 yield* sim.run(history(sim, 6, 10, 4));
406 }),
407 );
408
409 scenario(
410 "stale keys, stale sources and faults together",
411 (sim) =>
412 Effect.gen(function* () {
413 sim.staleKeys.set("k1", sim.now + 150_000);
414 for (let i = 0; i < 30; i++) {
415 sim.now += 1;
416 yield* sim.commit(`A/s${i % 5}`, [`k${i % 4}`], i % 5 === 0 ? sim.now + 90_000 : 0);
417 }
418 yield* sim.deploy();
419 yield* sim.run(history(sim, 5, 10, 4));
420 }),
421 { faults: { callBefore: 0.05, callAfter: 0.05, crash: 0.05 }, seeds: 40 },
422 );
423
424 scenario("instances busy at the deploy stay on older code while calls keep coming", (sim) =>
425 Effect.gen(function* () {
426 for (const commit of history(sim, 6, 30, 3)) yield* commit();
427 yield* sim.deploy({ running: true });
428 // Clients keep writing to two instances every 10 seconds for a few minutes:
429 // they stay on older code all that time, then catch up.
430 const traffic = Array.from({ length: 24 }, (_, i) => () => {
431 sim.now += 10_000;
432 return sim.commit(`A/s${i % 2}`, [`k${i % 3}`]);
433 });
434 yield* sim.run(traffic);
435 }),
436 );
437
438 scenario(
439 "busy instances, busy stale keys and faults together",
440 (sim) =>
441 Effect.gen(function* () {
442 sim.staleKeys.set("k0", sim.now + 40_000);
443 for (const commit of history(sim, 6, 30, 3)) yield* commit();
444 yield* sim.deploy({ running: true });
445 const traffic = Array.from({ length: 12 }, (_, i) => () => {
446 sim.now += 10_000;
447 return sim.commit(`A/s${i % 3}`, [`k${i % 3}`]);
448 });
449 yield* sim.run(traffic);
450 }),
451 { faults: { callBefore: 0.05, callAfter: 0.05, crash: 0.05 }, seeds: 40 },
452 );
453
454 scenario(
455 "two consumers deployed together share the directory, with nodes linking mid-sweep",
456 (sim) =>
457 Effect.gen(function* () {
458 for (const commit of history(sim, 4, 16, 3)) yield* commit();
459 yield* sim.deploy();
460 // New instances list themselves (and link new directory nodes) while both sweeps run.
461 yield* sim.run([...history(sim, 8, 16, 3, "new"), ...history(sim, 4, 8, 2)]);
462 }),
463 { others: ["view:W#1", "view:X#1"], seeds: 40 },
464 );
465
466 scenario("two consumers with faults", (sim) => backfill(sim, 6, 30, 3), {
467 others: ["view:W#1"],
468 faults: { callBefore: 0.05, callAfter: 0.05, crash: 0.05 },
469 seeds: 60,
470 });
471 });