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 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 | } |