The best way to control Claude Code, Codex and more from any computer or phone
| 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 | }); |