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

main
ts 2,230 lines 91.9 KB
Raw
1 import * as Cause from "effect/Cause";
2 import * as Clock from "effect/Clock";
3 import * as Data from "effect/Data";
4 import * as Effect from "effect/Effect";
5 import * as Predicate from "effect/Predicate";
6 import * as Queue from "effect/Queue";
7 import * as Random from "effect/Random";
8 import * as Semaphore from "effect/Semaphore";
9 import { type ReplayInput, type ReplayResult, type Routed, routeLive } from "./CatchUp.ts";
10 import type { Delivery } from "./Platform.ts";
11
12 /**
13 * Backfill: how a view or projection added after its sources recorded events
14 * (or rebuilt by bumping its version) receives their history, in timestamp
15 * order, without a central coordinator.
16 *
17 * Roles, each a durable object that owns its own storage:
18 *
19 * - **Directory nodes** form a tree (fan-out 16, one subtree per source) that
20 * lists every source instance. It is only an index: a run reads it.
21 * - **A run** per consumer generation: its root lists the directory into
22 * subtrees and paces them through **relays**, each fanning out six ways,
23 * backing off when the account's load is refused. A consumer keyed by its
24 * source needs one pass; any other needs two, with a barrier between.
25 * - **Sources** (aggregate instances, and view keys other consumers read)
26 * serve their stored rows on any code, and switch a consumer to live
27 * delivery once a reader has read all of them.
28 * - **Scanners**, one per source instance and consumer generation, read its
29 * rows, route them with the consumer's code and push each key its part.
30 * - **Consumer keys** (view keys, projection keys) buffer what they receive
31 * ordered by `(at, stream, seq)` and, told that every source's history is
32 * in, apply it in that order. A key keyed by its source reads its source's
33 * rows itself and applies them as it reads.
34 *
35 * Every step does a bounded amount of work, records its progress before it
36 * answers, and is idempotent, so a crash, a retry or a redeploy at any point
37 * resumes where it left off. Every continuation is a scheduled job, never a
38 * nested call.
39 *
40 * @internal
41 */
42
43 // ---------------------------------------------------------------- runtime
44
45 /** A key-ordered store, as a Durable Object's storage is. */
46 export interface Storage {
47 readonly get: <A>(key: string) => Effect.Effect<A | undefined>;
48 readonly put: (entries: Readonly<Record<string, unknown>>) => Effect.Effect<void>;
49 readonly delete: (keys: ReadonlyArray<string>) => Effect.Effect<void>;
50 /** Entries under `prefix`, in key order, after `startAfter`. */
51 readonly list: <A>(options: {
52 readonly prefix: string;
53 readonly startAfter?: string;
54 readonly limit?: number;
55 }) => Effect.Effect<ReadonlyArray<readonly [string, A]>>;
56 /** Run `effect` with every other call on this object held back. */
57 readonly exclusive: <A, E>(effect: Effect.Effect<A, E>) => Effect.Effect<A, E>;
58 }
59
60 /** Durable, at-least-once jobs on one object: a job with the same id replaces a pending one. */
61 export interface Jobs {
62 /**
63 * Run job `id` after `afterMillis`. The earliest request wins: a job already due
64 * sooner isn't postponed (every job is idempotent, so running early is safe),
65 * including one asked for while that job runs.
66 */
67 readonly schedule: (id: string, afterMillis: number) => Effect.Effect<void>;
68 }
69
70 /** An instance listed in the directory: its source (aggregate or view) and id. */
71 export interface SourceRef {
72 readonly source: string;
73 readonly id: string;
74 /**
75 * A view key's generation, once its view has been rebuilt: each generation's
76 * keys are their own objects, so this names the one that holds its entries.
77 */
78 readonly generation?: number;
79 }
80
81 /**
82 * What a run needs to know of a consumer. The deploy that adds the consumer
83 * passes it to the run, so the run never depends on what an object's code knows.
84 */
85 export interface Plan {
86 /** The sources (aggregates and views, by name) the consumer reads: the subtrees a run lists (all if absent). */
87 readonly sources?: ReadonlyArray<string>;
88 /** Each key reads one instance, the one with its own id: the leaf starts the keys itself. */
89 readonly singleSource: boolean;
90 /** The generation of each source that is a rebuilt view (see {@link SourceRef.generation}). */
91 readonly generations?: Readonly<Record<string, number>>;
92 }
93
94 /** `ref` with its source's generation, by the plan. */
95 export const withGeneration = (ref: SourceRef, plan: Plan | undefined): SourceRef => {
96 const generation = plan?.generations?.[ref.source];
97 return generation === undefined || generation === 0 ? ref : { ...ref, generation };
98 };
99
100 export interface NodeRpc {
101 readonly register: (path: string, ref: SourceRef) => Effect.Effect<void>;
102 readonly child: (path: string, child: string) => Effect.Effect<void>;
103 /**
104 * A page of what a node lists: its own instances after `after`, and (on the
105 * first page) its children. Any code answers it, whatever consumers it knows.
106 */
107 readonly list: (path: string, after: string | undefined) => Effect.Effect<Listing>;
108 }
109
110 /** A page of a directory node's listing. */
111 export interface Listing {
112 readonly rows: ReadonlyArray<SourceRef>;
113 readonly children: ReadonlyArray<string>;
114 /** Where the next page starts, if there is one. */
115 readonly next?: string;
116 }
117
118 export interface SourceRpc {
119 /**
120 * `cursor`, `log` and, at the end of the log, `handoff`, in one call: what a
121 * reader of a short history needs. Older code doesn't have it: a reader falls
122 * back to the three calls.
123 */
124 readonly read: (
125 ref: SourceRef,
126 target: string,
127 key: string,
128 after: number,
129 limit: number,
130 ) => Effect.Effect<Read>;
131 /**
132 * The last seq it routed live to `target`: a reader reads after it, since the
133 * rows up to it reached their keys live. An instance with no cursors predates
134 * catch-up: everything is live, up to its version.
135 */
136 readonly cursor: (ref: SourceRef, target: string) => Effect.Effect<number>;
137 /**
138 * Its stored rows (events, or a view key's entries) after `after`, as stored.
139 * Any code answers it: nothing in it depends on the consumer asking.
140 */
141 readonly log: (
142 ref: SourceRef,
143 after: number,
144 limit: number,
145 ) => Effect.Effect<ReadonlyArray<unknown>>;
146 /**
147 * Route `target` live from now on, if the reader has read every row up to its
148 * version (`through`): `"more"` if rows were added since, `"stale"` on code
149 * without the target. `key` names the reader, for traces.
150 */
151 readonly handoff: (
152 ref: SourceRef,
153 target: string,
154 key: string,
155 through: number,
156 ) => Effect.Effect<Handoff>;
157 }
158
159 /** What a source answers to `handoff`. */
160 export type Handoff = "live" | "more" | "stale";
161
162 /** What a reader gets from one `read`: rows after `from`, and at the end of the log, the handoff. */
163 export interface Read {
164 /** Where it read from: after `after`, or where live routing stopped (for `after` 0). */
165 readonly from: number;
166 readonly rows: ReadonlyArray<unknown>;
167 /** Fewer rows than asked for: the end of the log, and whether it switched the target to live there. */
168 readonly handoff?: Handoff;
169 }
170
171 /** A page a key read from its source. */
172 export interface Pulled {
173 readonly deliveries: ReadonlyArray<Delivery>;
174 /** The source switched the key to live delivery: nothing more to read. */
175 readonly live: boolean;
176 /**
177 * The last seq the source read for this page: the key's cursor moves past it,
178 * even when those rows held nothing for the key.
179 */
180 readonly through?: number;
181 /**
182 * Nothing followed this page when it was read: the key reads again at once to
183 * switch to live, rather than wait.
184 */
185 readonly end?: boolean;
186 }
187
188 export interface ConsumerRpc {
189 /** History for a key, from a scanner: it buffers it until it is told every source's is in. */
190 readonly push: (
191 target: string,
192 key: string,
193 deliveries: ReadonlyArray<Delivery>,
194 ) => Effect.Effect<void>;
195 /**
196 * Every source's history is with the key: apply it. `"settled"` once applied;
197 * it works on it for up to `waitMillis` before it answers.
198 */
199 readonly ready: (
200 target: string,
201 key: string,
202 waitMillis?: number,
203 ) => Effect.Effect<"pending" | "settled">;
204 /**
205 * Start a key of a consumer keyed by its source: it reads `ref`'s log itself.
206 * `"settled"` once it has its history: it works on it for up to `waitMillis`
207 * before it answers.
208 */
209 readonly start: (
210 target: string,
211 key: string,
212 ref: SourceRef,
213 waitMillis?: number,
214 ) => Effect.Effect<"pending" | "settled">;
215 }
216
217 /**
218 * A scanner reads one source instance's log for a consumer, routes it with the
219 * consumer's code, and pushes each key its history: one object per source
220 * instance and consumer generation, new with the deploy.
221 */
222 export interface ScannerRpc {
223 /** Push every key its history from `ref`, up to now: `true` once done, after up to `waitMillis`. */
224 readonly scan: (target: string, ref: SourceRef, waitMillis: number) => Effect.Effect<boolean>;
225 /** Tell every key it pushed to that all history is in: `true` once each has applied it. */
226 readonly ready: (target: string, ref: SourceRef, waitMillis: number) => Effect.Effect<boolean>;
227 /** A commit found the target behind on `ref` with no reader: read it and push what is new. */
228 readonly kick: (target: string, ref: SourceRef) => Effect.Effect<void>;
229 }
230
231 /** What a relay works through: directory nodes to list, and source instances. */
232 export type RelayItem = { readonly path: string } | { readonly ref: SourceRef };
233
234 /** A pass of a relay tree over the directory, for one consumer. */
235 export interface RelayRun {
236 readonly target: string;
237 readonly plan: Plan;
238 /**
239 * `discover`: start each key (keyed by its source), or scan each source;
240 * `ready`: tell each source's keys that every source's history is in.
241 */
242 readonly phase: "discover" | "ready";
243 /**
244 * When the pass answers (epoch ms): each relay keeps at its items until then,
245 * and answers `false` if not all of them are done. Now, for one try at everything.
246 */
247 readonly deadline: number;
248 }
249
250 export interface RelayRpc {
251 /**
252 * Work through `items` for a run, and answer `true` once all of it is done.
253 * `name` is the relay's place in the tree: each one is its own object.
254 */
255 readonly run: (
256 name: string,
257 run: RelayRun,
258 items: ReadonlyArray<RelayItem>,
259 ) => Effect.Effect<RelayResult>;
260 }
261
262 /** What a relay answers: which of its items are done, and how many calls the account's load refused. */
263 export interface RelayResult {
264 readonly done: ReadonlyArray<boolean>;
265 readonly refused: number;
266 /** Source instances done under it. */
267 readonly instances?: number;
268 /** A call it gave up on, and why. */
269 readonly failure?: string;
270 }
271
272 /** How far a consumer's run has got: `ready` once every source's history is with its keys. */
273 export type Phase = "unknown" | "discover" | "ready" | "complete";
274
275 /** The root of a consumer's run: one object per consumer generation. */
276 export interface RunRpc {
277 /**
278 * Start the run, once. A run already started (or complete) is found, not
279 * started again; one started with a different plan (the consumer reads other
280 * sources now, without a version bump) answers `changed`.
281 */
282 readonly begin: (target: string, plan: Plan) => Effect.Effect<Begin>;
283 readonly phase: (target: string) => Effect.Effect<Phase>;
284 readonly progress: (target: string) => Effect.Effect<Progress>;
285 }
286
287 /** What starting a run answers. */
288 export type Begin =
289 | { readonly status: "started" | "complete" }
290 /** Started with another plan: it reads what `started` says, not what was asked. */
291 | { readonly status: "changed"; readonly started: Plan };
292
293 /** Whether two plans read the same sources, at the same generations, the same way. */
294 export const samePlan = (a: Plan, b: Plan) => {
295 const sources = (plan: Plan) =>
296 plan.sources === undefined ? "*" : [...plan.sources].sort().join(",");
297 const generations = (plan: Plan) =>
298 Object.entries(plan.generations ?? {})
299 .filter(([, generation]) => generation > 0)
300 .sort(([x], [y]) => x.localeCompare(y))
301 .map(([source, generation]) => `${source}#${generation}`)
302 .join(",");
303 return (
304 a.singleSource === b.singleSource &&
305 sources(a) === sources(b) &&
306 generations(a) === generations(b)
307 );
308 };
309
310 /**
311 * Why a deploy can't wait on a run started with another plan: the consumer now
312 * reads sources its run doesn't, and only a new generation reads them.
313 */
314 export const planChanged = (target: string, started: Plan, asked: Plan) => {
315 const list = (plan: Plan) =>
316 plan.sources === undefined ? "every source" : plan.sources.join(", ");
317 return `${target} now reads ${list(asked)}, but its backfill was started reading ${list(started)}. Bump its version to rebuild it from every source's history.`;
318 };
319
320 /** A consumer reads other sources than its backfill was started with, at the same version. */
321 export class PlanChanged extends Data.TaggedError("BackfillPlanChanged")<{
322 readonly message: string;
323 }> {}
324
325 /** How far a run has got, for a deploy to report while it waits. */
326 export interface Progress {
327 readonly target: string;
328 readonly phase: Phase;
329 /** The subtrees of the directory this phase works through, and how many are done. */
330 readonly subtrees: number;
331 readonly done: number;
332 /** Source instances (keys keyed by their source, or scanners) done in this phase. */
333 readonly instances: number;
334 /** Passes over the directory so far: a pass that isn't done in time is followed by another. */
335 readonly passes: number;
336 /** Calls Cloudflare refused for the account's load: the run backs off when it does. */
337 readonly refused: number;
338 /** When the run began, and when it last moved, in epoch milliseconds. */
339 readonly startedAt?: number;
340 readonly updatedAt?: number;
341 /** The last call it gave up on, if any, and why. */
342 readonly lastError?: string;
343 }
344
345 /** How the roles reach each other. */
346 export interface Network {
347 readonly node: NodeRpc;
348 readonly source: SourceRpc;
349 readonly consumer: ConsumerRpc;
350 readonly scanner: ScannerRpc;
351 readonly relay: RelayRpc;
352 readonly run: RunRpc;
353 }
354
355 /** Tuning, in rows and calls per step. */
356 export interface Limits {
357 /** History rows a reader (a key keyed by its source, or a scanner) reads per call. */
358 readonly page: number;
359 /** Source instances a directory node handles per step, and calls it makes at once. */
360 readonly nodePage: number;
361 readonly concurrency: number;
362 /** Buffered rows a key applies per step. */
363 readonly apply: number;
364 /** How long to wait before calling a stale source again, in milliseconds. */
365 readonly staleRetryMillis: number;
366 /**
367 * How long before the first retry of a refused or failed call, in milliseconds:
368 * right after a deploy its new code may not have reached the object yet.
369 */
370 readonly firstRetryMillis: number;
371 /** How long a key without sources waits before asking whether discovery is complete again. */
372 readonly pollMillis: number;
373 /**
374 * Instances a directory node lists before it splits into 16 children, so every
375 * node's share of a listing stays bounded and the tree grows as log16 of the instances.
376 */
377 readonly leafSize: number;
378 /** The depth instances list themselves at, before any split. */
379 readonly depth: number;
380 }
381
382 /**
383 * The depth instances list themselves at: 256 leaves, each splitting once it
384 * fills. Wide enough that first commits spread over many objects, few enough
385 * that a small Domain's directory stays small (every node costs a listing).
386 */
387 export const DEPTH = 2;
388
389 export const defaultLimits: Limits = {
390 // A long history arrives in few round trips: each one costs more than its rows.
391 page: 1_000,
392 nodePage: 25,
393 concurrency: 5,
394 apply: 200,
395 staleRetryMillis: 30_000,
396 firstRetryMillis: 1_000,
397 pollMillis: 5_000,
398 leafSize: 256,
399 depth: DEPTH,
400 };
401
402 // ---------------------------------------------------------------- keys
403
404 const enc = encodeURIComponent;
405 const pad = (n: number, width: number) => String(Math.max(0, Math.floor(n))).padStart(width, "0");
406
407 /** Log a protocol step at debug level (`backfill <step>` and a JSON body), to follow a backfill. */
408 const trace = (step: string, fields: Record<string, unknown>) =>
409 Effect.logDebug(`backfill ${step} ${JSON.stringify(fields)}`);
410
411 /**
412 * The directory has one subtree per source (`Account:`, `Deposits:`), so a run
413 * for a consumer walks only the sources it reads. Within a subtree a node's path
414 * is the source, a colon and a prefix of the instance's hash: `Account:a3`.
415 */
416 export const leafOf = (ref: SourceRef, depth: number = DEPTH): string =>
417 `${ref.source}:${hashOf(ref).slice(0, depth)}`;
418
419 /** The hash digits of a path: its depth within its source's subtree. */
420 const digitsOf = (path: string) => path.slice(path.indexOf(":") + 1);
421
422 /** The source a node's subtree lists, or `undefined` for the root (and news relays). */
423 export const sourceOfPath = (path: string): string | undefined => {
424 const colon = path.indexOf(":");
425 return colon < 0 ? undefined : path.slice(0, colon);
426 };
427
428 /** The FNV-1a hash of an instance's source and id, as 8 hex digits: its path in the tree. */
429 const hashOf = ({ source, id }: SourceRef): string => {
430 let hash = 0x811c9dc5;
431 for (const char of `${source}/${id}`) {
432 hash ^= char.charCodeAt(0);
433 hash = Math.imul(hash, 0x01000193) >>> 0;
434 }
435 // FNV-1a barely moves the high bits for ids that differ in their last characters
436 // (`b0`, `b1`, …): mix them in (murmur3's finalizer), so the tree fills evenly.
437 hash ^= hash >>> 16;
438 hash = Math.imul(hash, 0x85ebca6b);
439 hash ^= hash >>> 13;
440 hash = Math.imul(hash, 0xc2b2ae35);
441 hash ^= hash >>> 16;
442 return (hash >>> 0).toString(16).padStart(8, "0");
443 };
444
445 /** The child of a split node that lists an instance: one more hex digit of its hash. */
446 const childFor = (path: string, ref: SourceRef) =>
447 `${ref.source}:${hashOf(ref).slice(0, digitsOf(path).length + 1)}`;
448
449 /** A source's subtree (`Account:`) hangs off the root; a news relay (`a3`) climbs by digit. */
450 const parentOf = (path: string) => (path.endsWith(":") ? "" : path.slice(0, -1));
451 const refKey = (ref: SourceRef) => `${enc(ref.source)}:${enc(ref.id)}`;
452
453 /** A buffered delivery's place in a key's merge: timestamp, then stream, then seq. */
454 export const orderKey = (target: string, delivery: Delivery) =>
455 `bf:b:${enc(target)}:${pad(delivery.envelope.at, 15)}:${enc(delivery.source)}:${pad(delivery.seq, 12)}`;
456
457 // ---------------------------------------------------------------- outbox
458
459 type Message =
460 /** Start the key of a consumer keyed by its source, which no run started. */
461 | {
462 readonly kind: "start";
463 readonly target: string;
464 readonly key: string;
465 readonly ref: SourceRef;
466 }
467 /** Ask a scanner to read a source instance no run read. */
468 | { readonly kind: "kick"; readonly target: string; readonly ref: SourceRef };
469
470 const OUTBOX_LEASE_MS = 60_000;
471
472 /**
473 * How long before a failed send is tried again: past the ~20s a Durable Object
474 * must sit idle before it leaves the code it ran before a deploy, so retries to
475 * one still on older code don't keep it there.
476 */
477 const RETRY_MS = 30_000;
478
479 /** Instances a directory node lists per page. */
480 const LIST_PAGE = 512;
481
482 /** How long a key started with a wait pauses between pages that couldn't go further. */
483 const WAIT_PAUSE_MS = 50;
484
485 /**
486 * Cloudflare refuses calls when an account puts too much load on Durable
487 * Objects, and resets an isolate whose objects (many share one) use too much
488 * memory. Either is a sign to send less: a refused call is tried again later,
489 * not at once, so a wide run backs off to the load the account can take
490 * rather than collapse under its own retries.
491 */
492 export const overloaded = (cause: Cause.Cause<unknown>) => {
493 const error = Cause.squash(cause);
494 return /too much load|too many concurrent|overloaded|try again later|exceeded its memory limit/i.test(
495 Predicate.hasProperty(error, "message") ? String(error.message) : String(error),
496 );
497 };
498
499 /** A wait after `failures` failures in a row: doubling from `base`, up to `max`, jittered. */
500 const backoff = (failures: number, base: number, max: number) =>
501 Effect.map(Random.next, (jitter) =>
502 Math.round(Math.min(max, base * 2 ** Math.max(0, failures - 1)) * (0.5 + jitter)),
503 );
504
505 /** A key's pause between pages: short while it makes progress, backing off while calls fail. */
506 const pause = (failures: number) =>
507 failures === 0 ? Effect.succeed(WAIT_PAUSE_MS) : backoff(failures, 250, 5_000);
508
509 /**
510 * Run a job again after a refusal or a failure, waiting twice as long each time:
511 * from `firstRetryMillis`, so a one-off failure (or a deploy's code still on its
512 * way to an object) costs seconds, up to four times the slow pace. Cloudflare moves
513 * a Durable Object to new code when it is evicted after sitting idle: calls at a
514 * short, fixed pace would keep one on older code, so the gaps grow until it can.
515 */
516 const makeRetry = (storage: Storage, jobs: Jobs, limits: Limits) => {
517 const key = (id: string) => `bf:retry:${id}`;
518 return {
519 later: (id: string, slowMillis: number) =>
520 Effect.gen(function* () {
521 const tries = (yield* storage.get<number>(key(id))) ?? 0;
522 yield* storage.put({ [key(id)]: tries + 1 });
523 yield* jobs.schedule(
524 id,
525 Math.min(slowMillis * 4, limits.firstRetryMillis * 2 ** Math.min(tries, 20)),
526 );
527 }),
528 /** The job went through: its next failure retries soon again. */
529 clear: (id: string) =>
530 Effect.gen(function* () {
531 if ((yield* storage.get(key(id))) !== undefined) yield* storage.delete([key(id)]);
532 }),
533 };
534 };
535 type Retry = ReturnType<typeof makeRetry>;
536
537 /** A call that counts as lost if it hasn't answered in time: a hung call would stall its caller. */
538 const bounded = <A, E>(call: Effect.Effect<A, E>) => call.pipe(Effect.timeout("20 seconds"));
539
540 /** Where `ref`'s live routing to `target` stopped; 0 (read it all) if it can't say (older code). */
541 const cursorOf = (net: Network, ref: SourceRef, target: string) =>
542 bounded(net.source.cursor(ref, target)).pipe(Effect.catchCause(() => Effect.succeed(0)));
543
544 /**
545 * Read a page of `ref`'s log for `target` in one call (see `SourceRpc.read`).
546 * A source on older code has no `read`: fall back to `cursor` and `log`, and
547 * the caller asks for the handoff itself. A call the account's load refused
548 * fails, for the caller to back off.
549 */
550 const readAt = (
551 net: Network,
552 ref: SourceRef,
553 target: string,
554 key: string,
555 after: number,
556 limit: number,
557 ): Effect.Effect<Read, unknown> =>
558 bounded(net.source.read(ref, target, key, after, limit)).pipe(
559 Effect.catchCauseIf(
560 (cause) => !overloaded(cause),
561 () =>
562 Effect.gen(function* () {
563 const from = after > 0 ? after : yield* cursorOf(net, ref, target);
564 const rows = yield* bounded(net.source.log(ref, from, limit));
565 return { from, rows } satisfies Read;
566 }),
567 ),
568 );
569
570 /** A target's generation: `view:Name#2` is 2. */
571 const generationOf = (target: string) => Number(/[#@](\d+)$/.exec(target)?.[1] ?? 0);
572
573 /** Refused by an instance still on older code; the sender tries again later. */
574 class Stale extends Data.TaggedError("Stale")<{ readonly message: string }> {}
575
576 /**
577 * A source's durable outbox of control messages: staged with the state change
578 * that produced them, sent in order, deleted once sent. One flush at a time.
579 */
580 const outbox = (storage: Storage, jobs: Jobs, net: Network, retry: Retry) => {
581 const send = (message: Message): Effect.Effect<void> =>
582 message.kind === "start"
583 ? Effect.asVoid(net.consumer.start(message.target, message.key, message.ref))
584 : net.scanner.kick(message.target, message.ref);
585 const acquire = storage.exclusive(
586 Effect.gen(function* () {
587 const held = yield* storage.get<number>("bf:q-lease");
588 const now = yield* Effect.sync(() => Date.now());
589 if (held !== undefined && held > now) return false;
590 yield* storage.put({ "bf:q-lease": now + OUTBOX_LEASE_MS });
591 return true;
592 }),
593 );
594 /** Send every staged message; `true` when the outbox is empty. */
595 const flush: Effect.Effect<boolean> = Effect.gen(function* () {
596 // Nothing staged: no lease to take.
597 if ((yield* storage.list({ prefix: "bf:q:", limit: 1 })).length === 0) return true;
598 // Another flush holds the lease; it may stop before this one's rows: try again later.
599 if (!(yield* acquire)) return yield* Effect.as(jobs.schedule("bf-flush", RETRY_MS), false);
600 return yield* Effect.gen(function* () {
601 while (true) {
602 const rows = yield* storage.list<Message>({ prefix: "bf:q:", limit: 50 });
603 if (rows.length === 0) {
604 yield* retry.clear("bf-flush");
605 return true;
606 }
607 for (const [key, message] of rows) {
608 yield* send(message);
609 yield* storage.delete([key]);
610 }
611 }
612 }).pipe(
613 // A send failed: the rest stay staged, and the backstop sends them later.
614 Effect.catchCause(() => Effect.as(retry.later("bf-flush", RETRY_MS), false)),
615 Effect.ensuring(storage.delete(["bf:q-lease"])),
616 );
617 });
618 return {
619 /** Stage messages; call inside the exclusive section that commits their cause. */
620 stage: (messages: ReadonlyArray<Message>) =>
621 Effect.gen(function* () {
622 if (messages.length === 0) return;
623 const last = ((yield* storage.get<number>("bf:q-seq")) ?? 0) + messages.length;
624 const rows: Record<string, Message> = { "bf:q-seq": last as never };
625 messages.forEach((message, index) => {
626 rows[`bf:q:${pad(last - messages.length + index + 1, 12)}`] = message;
627 });
628 yield* storage.put(rows);
629 // The backstop: sent even if this instance dies before a flush runs.
630 yield* jobs.schedule("bf-flush", 5_000);
631 }),
632 flush,
633 };
634 };
635
636 // ---------------------------------------------------------------- sources
637
638 /** What a source instance gives the protocol. */
639 export interface SourceHost {
640 readonly ref: SourceRef;
641 /** Every consumer in the model this instance's code runs: a target outside it is from newer code. */
642 readonly model: () => ReadonlyArray<string>;
643 /** Whether `target`'s keys are keyed by their source: each reads its own source's log. */
644 readonly singleSource?: (target: string) => boolean;
645 /** Its current version: the seq of its last event or entry. */
646 readonly version: Effect.Effect<number>;
647 readonly routed: Effect.Effect<Routed | undefined>;
648 /** Route `target` live from the current version on. Called holding the exclusive section. */
649 readonly markLive: (target: string) => Effect.Effect<void>;
650 /** Its stored rows after `after`, as stored: what a reader routes with its own code. */
651 readonly log: (after: number, limit: number) => Effect.Effect<ReadonlyArray<unknown>>;
652 }
653
654 /**
655 * A source instance's part of the protocol: it serves its log as stored, on
656 * any code, and switches a target to live delivery once a reader has read all
657 * of it. Until then a commit withholds the target's deliveries (the reader
658 * reads them from the log). The first commit to withhold them on code that
659 * knows the target asks for a reader: an instance no run listed (one created
660 * on older code during a rollout) is caught up that way.
661 */
662 export const makeSource = (
663 storage: Storage,
664 jobs: Jobs,
665 net: Network,
666 host: SourceHost,
667 limits: Limits = defaultLimits,
668 ) => {
669 const retry = makeRetry(storage, jobs, limits);
670 const queue = outbox(storage, jobs, net, retry);
671 const kickedKey = (target: string) => `bf:kick:${enc(target)}`;
672
673 const fromKey = (target: string) => `bf:from:${enc(target)}`;
674
675 /**
676 * Where live routing to `target` stopped (see `SourceRpc.cursor`), as it was
677 * when its reader first asked: kept, so a reader that asks again (its answer
678 * lost after the source went live) starts at the same row, not past it.
679 */
680 const cursor = (target: string) =>
681 storage.exclusive(
682 Effect.gen(function* () {
683 const kept = yield* storage.get<number>(fromKey(target));
684 if (kept !== undefined) return kept;
685 const routed = yield* host.routed;
686 const from = routed === undefined ? yield* host.version : (routed[target] ?? 0);
687 yield* storage.put({ [fromKey(target)]: from });
688 return from;
689 }),
690 );
691
692 const handoff = (target: string, key: string, through: number) =>
693 Effect.gen(function* () {
694 if (!host.model().includes(target)) return "stale" as Handoff;
695 const result = yield* storage.exclusive(
696 Effect.gen(function* () {
697 // Rows were added after the reader read up to `through`: it reads them first.
698 if ((yield* host.version) > through) return "more" as const;
699 const routed = yield* host.routed;
700 if (routed !== undefined && (routed[target] ?? 0) < through) yield* host.markLive(target);
701 yield* storage.delete([kickedKey(target)]);
702 return "live" as const;
703 }),
704 );
705 yield* trace("handoff", { source: host.ref, target, key, through, result });
706 return result as Handoff;
707 });
708
709 return {
710 /**
711 * A commit withheld `target`'s deliveries: it is behind here. Ask for a
712 * reader, once. Call inside the commit's exclusive section.
713 */
714 onCommit: (target: string) =>
715 Effect.gen(function* () {
716 if ((yield* storage.get(kickedKey(target))) !== undefined) return;
717 yield* storage.put({ [kickedKey(target)]: true });
718 yield* queue.stage([
719 host.singleSource?.(target) === true
720 ? { kind: "start", target, key: host.ref.id, ref: host.ref }
721 : { kind: "kick", target, ref: host.ref },
722 ]);
723 }),
724
725 log: (after: number, limit: number) => host.log(after, limit),
726
727 cursor: (target: string) => cursor(target),
728
729 read: (target: string, key: string, after: number, limit: number) =>
730 Effect.gen(function* () {
731 const from = after > 0 ? after : yield* cursor(target);
732 const rows = yield* host.log(from, limit);
733 if (rows.length >= limit) return { from, rows } satisfies Read;
734 // Rows are numbered without gaps: these end at `from + rows.length`.
735 return {
736 from,
737 rows,
738 handoff: yield* handoff(target, key, from + rows.length),
739 } satisfies Read;
740 }),
741
742 handoff: (target: string, key: string, through: number) => handoff(target, key, through),
743
744 /** The backstop job: send what is staged. */
745 flush: Effect.asVoid(queue.flush),
746 };
747 };
748
749 export type Source = ReturnType<typeof makeSource>;
750
751 // ---------------------------------------------------------------- scanners
752
753 /** What a scanner gives the protocol: the consumer's routing, in the code it runs. */
754 export interface ScannerHost {
755 /** Route a source's stored rows (from its `log`) to `target`: each row's seq and its deliveries. */
756 readonly route: (
757 target: string,
758 ref: SourceRef,
759 rows: ReadonlyArray<unknown>,
760 ) => Effect.Effect<
761 ReadonlyArray<{ readonly seq: number; readonly deliveries: ReadonlyArray<Delivery> }>
762 >;
763 }
764
765 /** A scanner's progress through one source instance, for one target. */
766 interface ScanState {
767 readonly ref: SourceRef;
768 /** It has asked the source where live routing stopped, and starts there. */
769 readonly started?: boolean;
770 /** Every row up to this seq is with its keys. */
771 readonly through: number;
772 /** Read to the end of the log at least once: the history a run waits for is with its keys. */
773 readonly scanned: boolean;
774 /** The source routes the target live: nothing more to read. */
775 readonly live: boolean;
776 /**
777 * Past the run's barrier: keys it pushes to from now on are told at once that
778 * all history is in (no pass will tell them).
779 */
780 readonly readied?: boolean;
781 /** Started by a commit, not a run: it asks the run whether it is past the barrier. */
782 readonly kicked?: boolean;
783 }
784
785 /**
786 * A scanner: reads one source instance's log, as stored, routes it with the
787 * consumer's code, and pushes each key the deliveries it gets. At the end of
788 * the log it asks the source to route the target live from there; a source
789 * still on older code can't, so the scanner reads on later (what it reads then
790 * is newer than the deploy, and arrives as live deliveries would).
791 */
792 export const makeScanner = (
793 storage: Storage,
794 jobs: Jobs,
795 net: Network,
796 host: ScannerHost,
797 limits: Limits = defaultLimits,
798 ) => {
799 const retry = makeRetry(storage, jobs, limits);
800 const stateKey = (target: string) => `bf:sc:${enc(target)}`;
801 const keysPrefix = (target: string) => `bf:sk:${enc(target)}:`;
802 const jobId = (target: string) => `bf-scan:${target}`;
803 const getState = (target: string) => storage.get<ScanState>(stateKey(target));
804
805 /** Start where the source's live routing stopped: the keys have every row before it. */
806 const start = (target: string, state: ScanState) =>
807 Effect.gen(function* () {
808 const cursor = yield* cursorOf(net, state.ref, target);
809 return yield* storage.exclusive(
810 Effect.gen(function* () {
811 const current = (yield* getState(target)) ?? state;
812 if (current.started) return current;
813 const started = { ...current, started: true, through: Math.max(current.through, cursor) };
814 yield* storage.put({ [stateKey(target)]: started });
815 return started;
816 }),
817 );
818 });
819
820 /** Whether the run is past its barrier, as far as this scanner knows (it asks only if a commit started it). */
821 const pastBarrier = (target: string, state: ScanState) =>
822 Effect.gen(function* () {
823 if (state.readied) return true;
824 if (!state.kicked) return false;
825 const phase = yield* net.run.phase(target);
826 if (phase !== "ready" && phase !== "complete") return false;
827 yield* storage.exclusive(
828 Effect.gen(function* () {
829 const current = yield* getState(target);
830 if (current !== undefined && !current.readied)
831 yield* storage.put({ [stateKey(target)]: { ...current, readied: true } });
832 }),
833 );
834 return true;
835 });
836
837 const init = (target: string, ref: SourceRef, kicked = false) =>
838 storage.exclusive(
839 Effect.gen(function* () {
840 const state = yield* getState(target);
841 if (state !== undefined) return state;
842 const fresh: ScanState = {
843 ref,
844 through: 0,
845 scanned: false,
846 live: false,
847 ...(kicked ? { kicked } : {}),
848 };
849 yield* storage.put({ [stateKey(target)]: fresh });
850 return fresh;
851 }),
852 );
853
854 /**
855 * One step: read and push a page, or at the end of the log, ask the source
856 * to route the target live. `pushed` once the history up to now is with its
857 * keys; `next` says whether to step again now, later (the source is on older
858 * code), or never (it routes the target live).
859 */
860 const step = (
861 target: string,
862 ): Effect.Effect<{ readonly pushed: boolean; readonly next: "now" | "later" | "never" }> =>
863 Effect.gen(function* () {
864 const found = yield* getState(target);
865 if (found === undefined || found.live) return { pushed: true, next: "never" } as const;
866 const state = found.started ? found : yield* start(target, found);
867 const rows = yield* bounded(net.source.log(state.ref, state.through, limits.page)).pipe(
868 Effect.orDie,
869 );
870 if (rows.length > 0) {
871 const routed = yield* host.route(target, state.ref, rows);
872 const through = routed.length > 0 ? routed[routed.length - 1]!.seq : state.through;
873 const byKey = new Map<string, Array<Delivery>>();
874 for (const row of routed)
875 for (const delivery of row.deliveries) {
876 const list = byKey.get(delivery.key) ?? [];
877 list.push(delivery);
878 byKey.set(delivery.key, list);
879 }
880 yield* Effect.forEach(
881 byKey,
882 ([key, deliveries]) =>
883 bounded(net.consumer.push(target, key, deliveries)).pipe(Effect.orDie),
884 { concurrency: limits.concurrency, discard: true },
885 );
886 // The keys first, so a `ready` pass lists them; then, past the barrier (which no
887 // pass will tell them of), tell them here; only then move past these rows, so a
888 // step that fails telling them reads and tells them again. (`ready` marks the
889 // state before it lists keys, so a key is told by one or the other.)
890 const keys: Record<string, true> = {};
891 for (const key of byKey.keys()) keys[`${keysPrefix(target)}${enc(key)}`] = true;
892 yield* storage.exclusive(storage.put(keys));
893 const current = yield* getState(target);
894 if (current === undefined || current.through !== state.through)
895 return { pushed: state.scanned, next: "now" } as const;
896 if (yield* pastBarrier(target, current))
897 yield* Effect.forEach(
898 byKey.keys(),
899 (key) => bounded(net.consumer.ready(target, key, 0)).pipe(Effect.orDie),
900 { concurrency: limits.concurrency, discard: true },
901 );
902 yield* storage.exclusive(
903 Effect.gen(function* () {
904 const latest = yield* getState(target);
905 if (latest !== undefined && latest.through === state.through)
906 yield* storage.put({ [stateKey(target)]: { ...latest, through } });
907 }),
908 );
909 if (rows.length >= limits.page) return { pushed: state.scanned, next: "now" } as const;
910 }
911 // The end of the log: ask the source to deliver live from here.
912 const after = (yield* getState(target))!;
913 const handoff = yield* bounded(net.source.handoff(after.ref, target, "", after.through)).pipe(
914 Effect.catchCause(() => Effect.succeed("stale" as Handoff)),
915 );
916 if (handoff === "more") return { pushed: after.scanned, next: "now" } as const;
917 yield* storage.exclusive(
918 Effect.gen(function* () {
919 const current = yield* getState(target);
920 if (current === undefined || current.through !== after.through) return;
921 yield* storage.put({
922 [stateKey(target)]: { ...current, scanned: true, live: handoff === "live" },
923 });
924 }),
925 );
926 yield* trace("scanned", { ref: after.ref, target, through: after.through, handoff });
927 // Still on older code: read on later, past what arrives meanwhile.
928 if (handoff === "stale") yield* retry.later(jobId(target), limits.staleRetryMillis);
929 else yield* retry.clear(jobId(target));
930 return { pushed: true, next: handoff === "live" ? "never" : "later" } as const;
931 });
932
933 /** Keep stepping until the history up to now is pushed, or `until` (epoch ms). */
934 const scanUntil = (target: string, until: number) =>
935 Effect.gen(function* () {
936 while (true) {
937 const { pushed, next } = yield* step(target);
938 if (pushed) return true;
939 if (next !== "now" || (yield* Clock.currentTimeMillis) >= until) {
940 // The rest in jobs; the run asks again.
941 if (next === "now") yield* jobs.schedule(jobId(target), 0);
942 return false;
943 }
944 }
945 });
946
947 return {
948 scan: (target: string, ref: SourceRef, waitMillis: number) =>
949 Effect.gen(function* () {
950 const state = yield* init(target, ref);
951 if (state.scanned) return true;
952 return yield* scanUntil(target, (yield* Clock.currentTimeMillis) + waitMillis);
953 }),
954
955 ready: (target: string, waitMillis: number) =>
956 Effect.gen(function* () {
957 // Marked before it lists keys: one pushed to after the listing is told by `step`.
958 yield* storage.exclusive(
959 Effect.gen(function* () {
960 const current = yield* getState(target);
961 if (current !== undefined && !current.readied)
962 yield* storage.put({ [stateKey(target)]: { ...current, readied: true } });
963 }),
964 );
965 const until = (yield* Clock.currentTimeMillis) + waitMillis;
966 let after: string | undefined;
967 let done = true;
968 while (true) {
969 const rows = yield* storage.list({
970 prefix: keysPrefix(target),
971 ...(after === undefined ? {} : { startAfter: after }),
972 limit: 256,
973 });
974 if (rows.length === 0) return done;
975 const settled = yield* Effect.forEach(
976 rows,
977 ([row]) =>
978 Effect.gen(function* () {
979 const key = decodeURIComponent(row.slice(keysPrefix(target).length));
980 while (true) {
981 const left = until - (yield* Clock.currentTimeMillis);
982 const wait = Math.max(0, Math.min(RELAY_KEY_WAIT_MS, left));
983 const result = yield* net.consumer
984 .ready(target, key, wait)
985 .pipe(Effect.timeout(`${wait + CALL_TIMEOUT_MS} millis`), Effect.orDie);
986 if (result === "settled") return true;
987 if ((yield* Clock.currentTimeMillis) >= until) return false;
988 }
989 }),
990 { concurrency: limits.concurrency },
991 );
992 done = done && settled.every(Boolean);
993 after = rows[rows.length - 1]![0];
994 }
995 }),
996
997 kick: (target: string, ref: SourceRef) =>
998 Effect.gen(function* () {
999 const state = yield* init(target, ref, true);
1000 if (!state.live) yield* jobs.schedule(jobId(target), 0);
1001 }),
1002
1003 /** Run a scheduled job by its id. */
1004 run: (id: string) =>
1005 Effect.gen(function* () {
1006 const { next } = yield* step(id.slice("bf-scan:".length));
1007 if (next === "now") yield* jobs.schedule(id, 0);
1008 }).pipe(Effect.catchCause(() => retry.later(id, RETRY_MS))),
1009 };
1010 };
1011
1012 export type Scanner = ReturnType<typeof makeScanner>;
1013
1014 // ---------------------------------------------------------------- consumer keys
1015
1016 /** A consumer key's view of one of its sources during a backfill. */
1017 interface Feed {
1018 readonly ref: SourceRef | null;
1019 /** The last seq pulled. */
1020 readonly cursor: number;
1021 /** Switched to live delivery: nothing more to pull. */
1022 readonly live: boolean;
1023 /** Deliveries from it waiting in the buffer. */
1024 readonly buffered: number;
1025 }
1026
1027 /** What a consumer key gives the protocol. */
1028 export interface ConsumerHost {
1029 readonly key: string;
1030 /** This consumer's target id in the code this instance runs. */
1031 readonly target: () => string;
1032 /**
1033 * Whether each key hears only from the source instance with its own id: then
1034 * it reads that instance's log itself, as soon as its leaf starts it (no
1035 * barrier), and applies what it reads directly (nothing to merge).
1036 */
1037 readonly singleSource?: () => boolean;
1038 /**
1039 * Route a source's stored rows (from its `log`) to this consumer: each row's
1040 * seq and its deliveries. Runs this key's code, whatever code the source runs.
1041 */
1042 readonly history?: (
1043 ref: SourceRef,
1044 rows: ReadonlyArray<unknown>,
1045 ) => Effect.Effect<
1046 ReadonlyArray<{ readonly seq: number; readonly deliveries: ReadonlyArray<Delivery> }>
1047 >;
1048 /** The sources this consumer reads (`Account`, `Deposits`): where it asks about discovery. */
1049 readonly sources?: () => ReadonlyArray<string>;
1050 /**
1051 * Apply deliveries in order, as the live path would. Called holding the
1052 * exclusive section.
1053 */
1054 readonly apply: (deliveries: ReadonlyArray<Delivery>) => Effect.Effect<void>;
1055 /** Work an `apply` left for after its exclusive section commits (pushes, sends). */
1056 readonly after?: Effect.Effect<void>;
1057 }
1058
1059 /**
1060 * A consumer key's part of the protocol. Its host passes every delivery for
1061 * the current target through {@link Consumer.admit} before applying it, and
1062 * serves `source` and `ready`.
1063 */
1064 export const makeConsumer = (
1065 storage: Storage,
1066 jobs: Jobs,
1067 net: Network,
1068 host: ConsumerHost,
1069 limits: Limits = defaultLimits,
1070 ) => {
1071 const T = (target: string) => enc(target);
1072 const backfillKey = (target: string) => `bf:c:${T(target)}`;
1073 const doneKey = (target: string) => `bf:done:${T(target)}`;
1074 const feedKey = (target: string, stream: string) => `bf:f:${T(target)}:${enc(stream)}`;
1075 const feedsPrefix = (target: string) => `bf:f:${T(target)}:`;
1076 /** Feeds still pulling with nothing buffered: the merge can't apply past them. */
1077 const starvedKey = (target: string, stream: string) => `bf:x:${T(target)}:${enc(stream)}`;
1078 const starvedPrefix = (target: string) => `bf:x:${T(target)}:`;
1079 const pullingKey = (target: string, stream: string) => `bf:p:${T(target)}:${enc(stream)}`;
1080 const pullingPrefix = (target: string) => `bf:p:${T(target)}:`;
1081 const bufferPrefix = (target: string) => `bf:b:${T(target)}:`;
1082 /** A buffered delivery held, not counted: see `buffer`. */
1083 const heldKey = (row: string) => `bf:h:${row.slice("bf:b:".length)}`;
1084 const jobId = (target: string) => `bf-merge:${target}`;
1085 /** Keyed by its source: it has read its source's log to the end (its history is here). */
1086 const caughtKey = (target: string) => `bf:caught:${T(target)}`;
1087 const retry = makeRetry(storage, jobs, limits);
1088 /**
1089 * A message for another generation of this consumer. A newer one means this
1090 * instance still runs older code: refuse it, so the sender tries again once
1091 * it runs the deployed code. An older one is from a superseded backfill.
1092 */
1093 const stale = (target: string) =>
1094 generationOf(target) > generationOf(host.target())
1095 ? Effect.die(new Stale({ message: `${host.key} runs ${host.target()}, not ${target} yet` }))
1096 : Effect.void;
1097
1098 interface Backfill {
1099 /** Every source's history is here: apply it in order. */
1100 readonly ready: boolean;
1101 /** A scanner pushed it history: that scanner tells it when it is ready. */
1102 readonly pushed?: boolean;
1103 }
1104
1105 const begin = (target: string) =>
1106 Effect.gen(function* () {
1107 const existing = yield* storage.get<Backfill>(backfillKey(target));
1108 if (existing) return existing;
1109 const backfill: Backfill = { ready: false };
1110 yield* storage.put({ [backfillKey(target)]: backfill });
1111 yield* jobs.schedule(jobId(target), 0);
1112 return backfill;
1113 });
1114
1115 /** Record a feed's buffered count and whether it starves the merge. */
1116 const starves = (feed: Feed | undefined) =>
1117 feed !== undefined && !feed.live && feed.buffered === 0;
1118 const putFeed = (target: string, stream: string, feed: Feed) =>
1119 Effect.gen(function* () {
1120 const before = yield* storage.get<Feed>(feedKey(target, stream));
1121 yield* storage.put({ [feedKey(target, stream)]: feed });
1122 // The indexes change only when the feed's state does: one write per row otherwise.
1123 if (before === undefined || before.live !== feed.live) {
1124 if (!feed.live) yield* storage.put({ [pullingKey(target, stream)]: true });
1125 else yield* storage.delete([pullingKey(target, stream)]);
1126 }
1127 if (before === undefined || starves(before) !== starves(feed)) {
1128 if (starves(feed)) yield* storage.put({ [starvedKey(target, stream)]: true });
1129 else yield* storage.delete([starvedKey(target, stream)]);
1130 }
1131 });
1132
1133 /** Buffer deliveries in merge order. Callers hold the exclusive section. */
1134 const buffer = (target: string, deliveries: ReadonlyArray<Delivery>, live: boolean) =>
1135 Effect.gen(function* () {
1136 // Each feed is written once per call, however many of its deliveries arrive.
1137 const feeds = new Map<string, Feed>();
1138 for (const delivery of deliveries) {
1139 const key = orderKey(target, delivery);
1140 const feed = feeds.get(delivery.source) ??
1141 (yield* storage.get<Feed>(feedKey(target, delivery.source))) ?? {
1142 ref: null,
1143 cursor: 0,
1144 // Arriving live from a source it never heard of: one with no history for this key.
1145 live,
1146 buffered: 0,
1147 };
1148 if ((yield* storage.get(key)) !== undefined) {
1149 // Held live, now read from the log too: it counts.
1150 if (!live && (yield* storage.get(heldKey(key))) !== undefined) {
1151 yield* storage.delete([heldKey(key)]);
1152 feeds.set(delivery.source, { ...feed, buffered: feed.buffered + 1 });
1153 }
1154 continue;
1155 }
1156 yield* storage.put({ [key]: delivery });
1157 if (live && feed.ref !== null && !feed.live) {
1158 // Live from a source this key is still reading: the source went live before
1159 // the key had the rows before this one (the answer that said so was lost). Held,
1160 // not counted, so the merge waits for those rows before it applies this.
1161 yield* storage.put({ [heldKey(key)]: true });
1162 feeds.set(delivery.source, feed);
1163 continue;
1164 }
1165 feeds.set(delivery.source, { ...feed, buffered: feed.buffered + 1 });
1166 }
1167 for (const [stream, feed] of feeds) yield* putFeed(target, stream, feed);
1168 });
1169
1170 /**
1171 * Read a page of the source's log and route it with this key's code. At the
1172 * end of the log, ask the source to deliver live from there: `caughtUp` either
1173 * way, since the key has every row the source had.
1174 */
1175 const readLog = (target: string, ref: SourceRef, from: number) =>
1176 Effect.gen(function* () {
1177 // At first, start where the source's live routing stopped: this key has the rest.
1178 const read = yield* readAt(net, ref, target, host.key, from, limits.page);
1179 const rows = read.rows;
1180 const routed = yield* host.history!(ref, rows);
1181 const through = routed.length > 0 ? routed[routed.length - 1]!.seq : read.from;
1182 const deliveries = routed
1183 .flatMap((row) => row.deliveries)
1184 .filter((delivery) => delivery.key === host.key);
1185 if (rows.length >= limits.page)
1186 return { deliveries, live: false, through, caughtUp: false } satisfies Pulled & {
1187 readonly caughtUp: boolean;
1188 };
1189 const handoff =
1190 read.handoff ??
1191 (yield* bounded(net.source.handoff(ref, target, host.key, through)).pipe(
1192 Effect.catchCause(() => Effect.succeed("stale" as Handoff)),
1193 ));
1194 return {
1195 deliveries,
1196 live: handoff === "live",
1197 through,
1198 // Rows were added meanwhile: read them at once.
1199 end: handoff === "more",
1200 caughtUp: handoff !== "more",
1201 } satisfies Pulled & { readonly caughtUp: boolean };
1202 });
1203
1204 /** Pull a page for each feed that starves the merge. */
1205 const pullStarved = (target: string) =>
1206 Effect.gen(function* () {
1207 const starved = yield* storage.list({
1208 prefix: starvedPrefix(target),
1209 limit: limits.concurrency * 4,
1210 });
1211 const streams = starved.map(([row]) =>
1212 decodeURIComponent(row.slice(starvedPrefix(target).length)),
1213 );
1214 // A page that reached the end of its source is followed at once by the pull
1215 // that switches the feed to live, so the merge never stops to wait for it.
1216 const pullFeed = (stream: string): Effect.Effect<boolean> =>
1217 Effect.gen(function* () {
1218 const feed = yield* storage.get<Feed>(feedKey(target, stream));
1219 if (!feed || feed.live || feed.ref === null) return false;
1220 // Keyed by its source: the key reads the source's log and routes it itself.
1221 const pulled = yield* readLog(target, feed.ref, feed.cursor).pipe(
1222 // Refused (still on older code) or lost in transit: pull it again later.
1223 Effect.catchCause(() => Effect.void),
1224 );
1225 if (pulled === undefined) return true;
1226 yield* storage.exclusive(
1227 Effect.gen(function* () {
1228 const current = yield* storage.get<Feed>(feedKey(target, stream));
1229 if (!current || current.cursor !== feed.cursor) return;
1230 // Read up to the end of its source's log: its history is here, whether
1231 // or not the source could switch it to live delivery yet.
1232 if (
1233 "caughtUp" in pulled &&
1234 pulled.caughtUp &&
1235 !(yield* storage.get(caughtKey(target)))
1236 ) {
1237 yield* storage.put({ [caughtKey(target)]: true });
1238 yield* trace("caught-up", { key: host.key, target });
1239 }
1240 // Its only source, and nothing buffered ahead: the page is already in
1241 // order, so apply it rather than buffer it.
1242 const direct =
1243 host.singleSource?.() === true &&
1244 (yield* storage.list({ prefix: bufferPrefix(target), limit: 1 })).length === 0;
1245 if (direct) {
1246 for (const delivery of pulled.deliveries) yield* host.apply([delivery]);
1247 } else yield* buffer(target, pulled.deliveries, false);
1248 const after = (yield* storage.get<Feed>(feedKey(target, stream)))!;
1249 yield* putFeed(target, stream, {
1250 ...after,
1251 cursor: Math.max(
1252 after.cursor,
1253 pulled.through ?? 0,
1254 ...pulled.deliveries.map((d) => d.seq),
1255 ),
1256 live: pulled.live,
1257 });
1258 }),
1259 );
1260 if (pulled.end === true && !pulled.live) return yield* pullFeed(stream);
1261 // A source on code without the target can't deliver live yet: read again later.
1262 return "caughtUp" in pulled && pulled.caughtUp === true && !pulled.live;
1263 });
1264 const failed = yield* Effect.forEach(streams, pullFeed, {
1265 concurrency: limits.concurrency,
1266 });
1267 return failed.some((stale) => stale);
1268 });
1269
1270 /**
1271 * Apply buffered deliveries in merge order while no pulling feed starves the
1272 * merge. Once ready, with no feed left to pull and nothing buffered, the
1273 * backfill is done and the key goes back to applying directly.
1274 */
1275 const applyBuffered = (target: string) =>
1276 storage.exclusive(
1277 Effect.gen(function* () {
1278 const backfill = yield* storage.get<Backfill>(backfillKey(target));
1279 if (!backfill) return "done" as const;
1280 if ((yield* storage.list({ prefix: starvedPrefix(target), limit: 1 })).length > 0)
1281 return "starved" as const;
1282 // A page in merge order, each delivery applied on its own (as live, so watchers and
1283 // downstream consumers see every change), each feed written once. It stops after
1284 // the delivery that leaves a feed still pulling with nothing buffered.
1285 const page = yield* storage.list<Delivery>({
1286 prefix: bufferPrefix(target),
1287 limit: limits.apply,
1288 });
1289 const feeds = new Map<string, Feed>();
1290 const applied: Array<Delivery> = [];
1291 let starved = false;
1292 for (const [, delivery] of page) {
1293 const feed =
1294 feeds.get(delivery.source) ??
1295 (yield* storage.get<Feed>(feedKey(target, delivery.source)))!;
1296 // A held delivery wasn't counted (see `buffer`).
1297 const row = orderKey(target, delivery);
1298 const held = (yield* storage.get(heldKey(row))) !== undefined;
1299 if (held) yield* storage.delete([heldKey(row)]);
1300 const next = held ? feed : { ...feed, buffered: feed.buffered - 1 };
1301 feeds.set(delivery.source, next);
1302 yield* host.apply([delivery]);
1303 applied.push(delivery);
1304 if (starves(next)) {
1305 starved = true;
1306 break;
1307 }
1308 }
1309 if (applied.length > 0) {
1310 yield* storage.delete(page.slice(0, applied.length).map(([row]) => row));
1311 for (const [stream, feed] of feeds) yield* putFeed(target, stream, feed);
1312 }
1313 if (starved) return "starved" as const;
1314 if (page.length >= limits.apply) return "more" as const;
1315 if (!backfill.ready) return "waiting" as const;
1316 if ((yield* storage.list({ prefix: pullingPrefix(target), limit: 1 })).length > 0)
1317 return "starved" as const;
1318 // Ready, every feed live and the buffer empty: done, atomically with the last apply.
1319 for (const prefix of [feedsPrefix(target), starvedPrefix(target), pullingPrefix(target)]) {
1320 while (true) {
1321 const rows = yield* storage.list({ prefix, limit: 128 });
1322 if (rows.length === 0) break;
1323 yield* storage.delete(rows.map(([key]) => key));
1324 }
1325 }
1326 yield* storage.delete([backfillKey(target), `bf:asked:${T(target)}`, caughtKey(target)]);
1327 yield* storage.put({ [doneKey(target)]: true });
1328 return "done" as const;
1329 }),
1330 );
1331
1332 /** Keyed by its source: it has its history (read to the end of its log, or done). */
1333 const settled = (target: string) =>
1334 Effect.map(
1335 Effect.all([storage.get(doneKey(target)), storage.get(caughtKey(target))]),
1336 ([done, caught]) => done !== undefined || caught !== undefined,
1337 );
1338
1339 /**
1340 * Keyed by its source: read `ref`'s log from the start. Ready at once, since
1341 * it has no other source to wait for. Callers hold the exclusive section.
1342 */
1343 const follow = (target: string, ref: SourceRef) =>
1344 Effect.gen(function* () {
1345 const backfill = yield* begin(target);
1346 if (!backfill.ready)
1347 yield* storage.put({ [backfillKey(target)]: { ...backfill, ready: true } });
1348 const stream = `${ref.source}/${ref.id}`;
1349 const feed = yield* storage.get<Feed>(feedKey(target, stream));
1350 if (feed === undefined || feed.ref === null)
1351 yield* putFeed(target, stream, {
1352 ref,
1353 cursor: 0,
1354 live: false,
1355 buffered: feed?.buffered ?? 0,
1356 });
1357 });
1358
1359 /** The merge job for one target. */
1360 /** The merge job for one target: `true` when it couldn't go on (a call failed), and waits. */
1361 const merge = (target: string): Effect.Effect<boolean> =>
1362 Effect.gen(function* () {
1363 const backfill = yield* storage.get<Backfill>(backfillKey(target));
1364 if (!backfill) return false;
1365 if (!backfill.ready) {
1366 // A key with history is told it is ready by the scanners that pushed it. One
1367 // fed only live (no history) has no one to tell it: it asks the run.
1368 if (backfill.pushed) return false;
1369 const phase = yield* net.run.phase(target).pipe(Effect.catchCause(() => Effect.void));
1370 if (phase === undefined)
1371 return yield* Effect.as(retry.later(jobId(target), RETRY_MS), true);
1372 yield* trace("waiting", { key: host.key, target, phase });
1373 if (phase !== "ready" && phase !== "complete")
1374 return yield* Effect.as(jobs.schedule(jobId(target), limits.pollMillis), false);
1375 yield* storage.exclusive(
1376 Effect.gen(function* () {
1377 const current = yield* storage.get<Backfill>(backfillKey(target));
1378 if (current) yield* storage.put({ [backfillKey(target)]: { ...current, ready: true } });
1379 }),
1380 );
1381 }
1382 const outcome = yield* applyBuffered(target);
1383 yield* trace("merge", { key: host.key, target, outcome });
1384 if (host.after) yield* host.after;
1385 if (outcome === "done" || outcome === "waiting")
1386 return yield* Effect.as(retry.clear(jobId(target)), false);
1387 // A remote failure never fails the job (which a durable callback would retry
1388 // with a growing delay, then park): it asks again after a fixed wait.
1389 const failed = outcome === "starved" ? yield* pullStarved(target) : false;
1390 if (failed) return yield* Effect.as(retry.later(jobId(target), RETRY_MS), true);
1391 yield* retry.clear(jobId(target));
1392 yield* jobs.schedule(jobId(target), 0);
1393 return false;
1394 });
1395
1396 return {
1397 /**
1398 * Deliveries for `target` arriving at this key. `true`: apply them now, as
1399 * usual. `false`: the key is backfilling, and they were buffered.
1400 */
1401 admit: (target: string, deliveries: ReadonlyArray<Delivery>) =>
1402 Effect.gen(function* () {
1403 const known = yield* storage.exclusive(
1404 Effect.gen(function* () {
1405 if (yield* storage.get(doneKey(target))) return "apply" as const;
1406 if (!(yield* storage.get(backfillKey(target)))) return "unknown" as const;
1407 yield* buffer(target, deliveries, true);
1408 yield* jobs.schedule(jobId(target), 0);
1409 return "buffered" as const;
1410 }),
1411 );
1412 if (known !== "unknown") return known === "apply";
1413 if (host.singleSource?.() === true) {
1414 // Keyed by its source: it needs no one to start it. It reads its source's
1415 // log, and takes these in order with it (a new instance's key reads little).
1416 // Its source is the instance with its own id.
1417 const source = deliveries[0]!.origin;
1418 yield* storage.exclusive(
1419 Effect.gen(function* () {
1420 yield* follow(target, { source, id: host.key });
1421 yield* buffer(target, deliveries, true);
1422 }),
1423 );
1424 yield* jobs.schedule(jobId(target), 0);
1425 return false;
1426 }
1427 // A key's first delivery for this target: is a run still pushing history?
1428 const phase = yield* net.run.phase(target);
1429 return yield* storage.exclusive(
1430 Effect.gen(function* () {
1431 if (yield* storage.get(doneKey(target))) return true;
1432 if (phase === "complete" && !(yield* storage.get(backfillKey(target)))) {
1433 yield* storage.put({ [doneKey(target)]: true });
1434 return true;
1435 }
1436 yield* begin(target);
1437 yield* buffer(target, deliveries, true);
1438 yield* jobs.schedule(jobId(target), 0);
1439 return false;
1440 }),
1441 );
1442 }),
1443
1444 push: (target: string, deliveries: ReadonlyArray<Delivery>) =>
1445 Effect.gen(function* () {
1446 const applied = yield* storage.exclusive(
1447 Effect.gen(function* () {
1448 if (target !== host.target()) {
1449 yield* stale(target);
1450 // An older generation's run: superseded.
1451 return false;
1452 }
1453 if (yield* storage.get(doneKey(target))) {
1454 // Its history is in: these are newer (read from a source still on older
1455 // code), and arrive as live deliveries would. The checkpoints drop repeats.
1456 yield* host.apply(deliveries.map(({ history: _, ...live }) => live));
1457 return true;
1458 }
1459 const backfill = yield* begin(target);
1460 if (!backfill.pushed)
1461 yield* storage.put({ [backfillKey(target)]: { ...backfill, pushed: true } });
1462 yield* buffer(target, deliveries, true);
1463 return false;
1464 }),
1465 );
1466 if (applied && host.after) yield* host.after;
1467 }),
1468
1469 start: (target: string, ref: SourceRef, waitMillis = 0) =>
1470 Effect.gen(function* () {
1471 const started = yield* storage.exclusive(
1472 Effect.gen(function* () {
1473 yield* trace("start", { key: host.key, target });
1474 if (target !== host.target()) {
1475 yield* stale(target);
1476 // An older generation's run: superseded, nothing to wait for.
1477 return "settled" as const;
1478 }
1479 if (yield* settled(target)) return "settled" as const;
1480 yield* follow(target, ref);
1481 return "pending" as const;
1482 }),
1483 );
1484 if (started === "settled") return started;
1485 // Worked on here when asked to wait; the job takes over only if it isn't done in time.
1486 if (waitMillis <= 0) return yield* Effect.as(jobs.schedule(jobId(target), 0), started);
1487 // Work on it here, rather than wait for an alarm to run the job: read its
1488 // source's log a page at a time until it has its history, or time is up.
1489 const until = (yield* Clock.currentTimeMillis) + waitMillis;
1490 for (let failures = 0; ;) {
1491 failures = (yield* merge(target)) ? failures + 1 : 0;
1492 if (yield* settled(target)) return "settled" as const;
1493 if ((yield* Clock.currentTimeMillis) >= until)
1494 return yield* Effect.as(jobs.schedule(jobId(target), 0), "pending" as const);
1495 yield* Effect.sleep(`${yield* pause(failures)} millis`);
1496 }
1497 }),
1498
1499 ready: (target: string, waitMillis = 0) =>
1500 Effect.gen(function* () {
1501 const told = yield* storage.exclusive(
1502 Effect.gen(function* () {
1503 yield* trace("told-ready", { key: host.key, target });
1504 if (target !== host.target()) {
1505 yield* stale(target);
1506 return "settled" as const;
1507 }
1508 if (yield* storage.get(doneKey(target))) return "settled" as const;
1509 const backfill = yield* begin(target);
1510 if (!backfill.ready)
1511 yield* storage.put({ [backfillKey(target)]: { ...backfill, ready: true } });
1512 return "pending" as const;
1513 }),
1514 );
1515 if (told === "settled") return told;
1516 yield* jobs.schedule(jobId(target), 0);
1517 if (waitMillis <= 0) return told;
1518 // Apply it here, rather than wait for an alarm to run the job.
1519 const until = (yield* Clock.currentTimeMillis) + waitMillis;
1520 for (let failures = 0; ;) {
1521 failures = (yield* merge(target)) ? failures + 1 : 0;
1522 if (yield* storage.get(doneKey(target))) return "settled" as const;
1523 if ((yield* Clock.currentTimeMillis) >= until) return "pending" as const;
1524 yield* Effect.sleep(`${yield* pause(failures)} millis`);
1525 }
1526 }),
1527
1528 /** The merge job for one target. */
1529 merge,
1530
1531 /** Is a backfill of `target` still running on this key? */
1532 backfilling: (target: string) =>
1533 Effect.map(storage.get(backfillKey(target)), (backfill) => backfill !== undefined),
1534 };
1535 };
1536
1537 export type Consumer = ReturnType<typeof makeConsumer>;
1538
1539 // ---------------------------------------------------------------- directory
1540
1541 /**
1542 * A directory node: lists instances, links itself into its parent, and splits
1543 * into 16 children once it lists more than `leafSize`. Runs only read it.
1544 */
1545 export const makeNode = (
1546 storage: Storage,
1547 jobs: Jobs,
1548 net: Network,
1549 limits: Limits = defaultLimits,
1550 ) => {
1551 const retry = makeRetry(storage, jobs, limits);
1552
1553 /** Remember this node's path (jobs read it), written once. */
1554 const keepPath = (path: string) =>
1555 Effect.gen(function* () {
1556 if ((yield* storage.get<string>("path")) !== path) yield* storage.put({ path });
1557 });
1558
1559 /**
1560 * Link this node into its parent, and so on up to the root, before answering:
1561 * an instance's first commit waits for it, so every instance with an event
1562 * can be reached from the root. Only a node's first registration pays for it.
1563 */
1564 const ensureLinked = (path: string) =>
1565 Effect.gen(function* () {
1566 if (path === "" || (yield* storage.get("linked"))) return;
1567 // One link at a time: registrations arriving together all find the node
1568 // unlinked, and would each call its parent, and so on up to a flooded root.
1569 yield* linking.withPermits(1)(
1570 Effect.gen(function* () {
1571 if (yield* storage.get("linked")) return;
1572 yield* net.node.child(parentOf(path), path);
1573 yield* storage.exclusive(storage.put({ linked: true, path }));
1574 }),
1575 );
1576 });
1577 const linking = Semaphore.makeUnsafe(1);
1578
1579 /**
1580 * Move a page of listed instances to the children, until none are left here.
1581 * Each is listed at its child before it leaves here, so a reader that lists a
1582 * node's own instances before its children never misses one.
1583 */
1584 const split = (path: string) =>
1585 Effect.gen(function* () {
1586 const rows = yield* storage.list<SourceRef>({ prefix: "i:", limit: limits.nodePage });
1587 if (rows.length === 0) return;
1588 yield* Effect.forEach(rows, ([, ref]) => net.node.register(childFor(path, ref), ref), {
1589 concurrency: limits.concurrency,
1590 discard: true,
1591 });
1592 yield* storage.exclusive(storage.delete(rows.map(([key]) => key)));
1593 yield* jobs.schedule("split", 0);
1594 });
1595
1596 return {
1597 register: (path: string, ref: SourceRef) =>
1598 Effect.gen(function* () {
1599 const forward = yield* storage.exclusive(
1600 Effect.gen(function* () {
1601 // Split: its children list instances now.
1602 if (yield* storage.get("split")) return childFor(path, ref);
1603 const key = `i:${refKey(ref)}`;
1604 if ((yield* storage.get(key)) !== undefined) return undefined;
1605 const count = ((yield* storage.get<number>("count")) ?? 0) + 1;
1606 yield* keepPath(path);
1607 yield* storage.put({ [key]: ref, count });
1608 // Full: split into 16 children by the next hex digit, a page at a time.
1609 if (count > limits.leafSize && digitsOf(path).length < 8) {
1610 yield* storage.put({ split: true });
1611 yield* jobs.schedule("split", 0);
1612 }
1613 return undefined;
1614 }),
1615 );
1616 yield* ensureLinked(path);
1617 if (forward !== undefined) yield* net.node.register(forward, ref);
1618 }),
1619
1620 child: (path: string, child: string) =>
1621 Effect.gen(function* () {
1622 yield* storage.exclusive(
1623 Effect.gen(function* () {
1624 yield* keepPath(path);
1625 if ((yield* storage.get(`c:${child}`)) === undefined)
1626 yield* storage.put({ [`c:${child}`]: true });
1627 }),
1628 );
1629 yield* ensureLinked(path);
1630 }),
1631
1632 list: (path: string, after: string | undefined) =>
1633 storage.exclusive(
1634 Effect.gen(function* () {
1635 const rows = yield* storage.list<SourceRef>({
1636 prefix: "i:",
1637 ...(after === undefined ? {} : { startAfter: after }),
1638 limit: LIST_PAGE,
1639 });
1640 // Its own rows before its children: a row a split moves on is listed at the
1641 // child before it leaves here, so a reader that lists the child later finds it.
1642 const children =
1643 after === undefined
1644 ? (yield* storage.list({ prefix: "c:" })).map(([key]) => key.slice(2))
1645 : [];
1646 return {
1647 rows: rows.map(([, ref]) => ref),
1648 children,
1649 ...(rows.length === LIST_PAGE ? { next: rows[rows.length - 1]![0] } : {}),
1650 } satisfies Listing;
1651 }),
1652 ),
1653
1654 /** Run a scheduled job by its id. */
1655 run: (id: string) =>
1656 Effect.gen(function* () {
1657 const path = (yield* storage.get<string>("path")) ?? "";
1658 if (id === "split") yield* split(path);
1659 yield* retry.clear(id);
1660 }).pipe(
1661 // A remote failure tries again after a fixed wait, rather than failing the job.
1662 Effect.catchCause(() => retry.later(id, RETRY_MS)),
1663 ),
1664 };
1665 };
1666
1667 export type Node = ReturnType<typeof makeNode>;
1668
1669 // ---------------------------------------------------------------- relay
1670
1671 /**
1672 * How many calls a relay makes at once: Cloudflare runs at most six outgoing
1673 * calls per invocation, so a wider relay would queue its own calls.
1674 */
1675 export const RELAY_FANOUT = 6;
1676
1677 /** How long a key works on its history before it answers a relay that is waiting for it. */
1678 const RELAY_KEY_WAIT_MS = 10_000;
1679
1680 /**
1681 * How many subtrees a run's root lists the directory into, at least: small
1682 * steps for its window, a few hundred keys each at a million instances.
1683 */
1684 const FRONTIER_SIZE = 512;
1685
1686 /** A relay's count of the calls the account's load refused. */
1687 interface Tally {
1688 refused: number;
1689 /** Source instances done. */
1690 instances: number;
1691 /** A call given up on, and why. */
1692 failure?: string;
1693 }
1694
1695 /** How long a call may take, beyond the work it was asked to wait for, before it counts as lost. */
1696 const CALL_TIMEOUT_MS = 20_000;
1697
1698 /**
1699 * How long a relay waits before it calls again after a failure, doubling each
1700 * time up to {@link RELAY_RETRY_MAX_MS}: an object still on older code moves to
1701 * the deployed code only once it has been idle, so calls at a fixed short pace
1702 * would keep it there.
1703 */
1704 const RELAY_RETRY_MS = 250;
1705 const RELAY_RETRY_MAX_MS = 30_000;
1706 /** Calls the account's load refused before a relay gives an item back to the run's root. */
1707 const RELAY_REFUSALS = 3;
1708
1709 /** Failed calls a relay makes again at once, before it waits. */
1710 const RELAY_RETRY_AT_ONCE = 2;
1711
1712 /**
1713 * A relay: one node of the tree a pass of a run fans out over, each its own
1714 * object. Given more than {@link RELAY_FANOUT} items it splits them among as
1715 * many child relays; given one directory node, it lists it and works through
1716 * what it lists; given a few, it handles each source instance itself and
1717 * hands each directory node to a child relay. Every relay answers once
1718 * everything under it is done, so a pass is done when the first one answers,
1719 * after about log6 of the instances levels of calls.
1720 *
1721 * For each source instance, it starts the instance's key (a consumer keyed by
1722 * its source), or calls the instance's scanner: to push its history
1723 * (`discover`), or to tell the keys it pushed to that all history is in
1724 * (`ready`).
1725 *
1726 * It keeps no state: a relay that fails is called again, and work already
1727 * done answers at once. It reads the directory, which any code serves, and
1728 * calls keys and scanners, which are new with the deploy: so a run never
1729 * waits for an existing object to run the deployed code.
1730 */
1731 export const makeRelay = (net: Network) => {
1732 /**
1733 * Keep at `effect` until it succeeds or `until` (epoch ms) has passed; `undefined`
1734 * then, after logging why (`what` names the call).
1735 */
1736 const persist = <A>(
1737 effect: Effect.Effect<A>,
1738 until: number,
1739 what: () => string,
1740 /** How long one attempt may take before it counts as lost: a hung call would stall its subtree. */
1741 attempt: () => Effect.Effect<number> = () => Effect.succeed(CALL_TIMEOUT_MS),
1742 /** Counts the calls the account's load refused, for the run's root to pace itself by. */
1743 tally?: Tally,
1744 ): Effect.Effect<A | undefined> =>
1745 Effect.gen(function* () {
1746 // A pass with no time to retry (one try at everything) expects failures: it doesn't log them.
1747 const quiet = until <= (yield* Clock.currentTimeMillis);
1748 for (let tries = 0, refusals = 0; ; tries++) {
1749 const limit = yield* attempt();
1750 const result = yield* (
1751 quiet ? effect : effect.pipe(Effect.timeout(`${limit} millis`))
1752 ).pipe(
1753 Effect.map((value) => ({ value })),
1754 Effect.catchCause((cause) => Effect.succeed({ cause })),
1755 );
1756 if ("value" in result) return result.value;
1757 // A call lost in transit: try again at once, a couple of times, then wait. A
1758 // call the account's load refused: wait at once, longer each time.
1759 const refused = overloaded(result.cause);
1760 const failure = () => `${what()}: ${String(Cause.squash(result.cause)).slice(0, 300)}`;
1761 if (refused && tally !== undefined) tally.refused += 1;
1762 // Refused a few times: give it back to the run's root, which sends it again at a
1763 // lower load, rather than hold the rest of its round until the pass's deadline.
1764 if (refused && ++refusals >= RELAY_REFUSALS) {
1765 if (tally !== undefined) tally.failure ??= failure();
1766 return undefined;
1767 }
1768 if (!refused && tries < RELAY_RETRY_AT_ONCE) continue;
1769 const wait = yield* backoff(
1770 refused ? tries + 1 : tries - RELAY_RETRY_AT_ONCE + 1,
1771 refused ? 1_000 : RELAY_RETRY_MS,
1772 RELAY_RETRY_MAX_MS,
1773 );
1774 if ((yield* Clock.currentTimeMillis) + wait >= until) {
1775 if (!quiet) yield* Effect.logInfo(`backfill relay-failed ${failure()}`);
1776 if (tally !== undefined) tally.failure ??= failure();
1777 return undefined;
1778 }
1779 yield* Effect.sleep(`${wait} millis`);
1780 }
1781 });
1782
1783 /** Every page a directory node lists: its instances' keys, and its children. */
1784 const listed = (path: string, run: RelayRun, until: number, tally?: Tally) =>
1785 Effect.gen(function* () {
1786 const items: Array<RelayItem> = [];
1787 let after: string | undefined;
1788 while (true) {
1789 const page = yield* persist(
1790 net.node.list(path, after),
1791 until,
1792 () => `list ${path}`,
1793 undefined,
1794 tally,
1795 );
1796 if (page === undefined) return undefined;
1797 for (const ref of page.rows) items.push({ ref: withGeneration(ref, run.plan) });
1798 // The root lists one subtree per source: only those the consumer reads.
1799 const sources = path === "" ? run.plan.sources : undefined;
1800 for (const child of page.children)
1801 if (sources === undefined || sources.includes(sourceOfPath(child) ?? ""))
1802 items.push({ path: child });
1803 if (page.next === undefined) return items;
1804 after = page.next;
1805 }
1806 });
1807
1808 /** One source instance's part of a pass; keep at it until it is done, or time is up. */
1809 const instance = (run: RelayRun, ref: SourceRef, until: number, tally: Tally) =>
1810 Effect.gen(function* () {
1811 const call = (wait: number): Effect.Effect<boolean> =>
1812 run.plan.singleSource
1813 ? Effect.map(
1814 net.consumer.start(run.target, ref.id, ref, wait),
1815 (started) => started === "settled",
1816 )
1817 : run.phase === "discover"
1818 ? net.scanner.scan(run.target, ref, wait)
1819 : net.scanner.ready(run.target, ref, wait);
1820 const quiet = until <= (yield* Clock.currentTimeMillis);
1821 while (true) {
1822 const left = until - (yield* Clock.currentTimeMillis);
1823 const wait = Math.max(0, Math.min(RELAY_KEY_WAIT_MS, left));
1824 const done = yield* persist(
1825 call(wait),
1826 until,
1827 () => `${run.phase} ${ref.source}/${ref.id}`,
1828 () => Effect.succeed(wait + CALL_TIMEOUT_MS),
1829 tally,
1830 );
1831 if (done === true) {
1832 tally.instances += 1;
1833 return true;
1834 }
1835 if ((yield* Clock.currentTimeMillis) >= until) {
1836 if (done === false && !quiet)
1837 yield* Effect.logInfo(
1838 `backfill relay-pending ${run.target} ${run.phase} ${ref.source}/${ref.id}`,
1839 );
1840 return false;
1841 }
1842 }
1843 });
1844
1845 const run = (
1846 name: string,
1847 relayRun: RelayRun,
1848 items: ReadonlyArray<RelayItem>,
1849 ): Effect.Effect<RelayResult> =>
1850 Effect.gen(function* () {
1851 const tally: Tally = { refused: 0, instances: 0 };
1852 const done = yield* work(name, relayRun, items, tally);
1853 return {
1854 done,
1855 refused: tally.refused,
1856 instances: tally.instances,
1857 ...(tally.failure === undefined ? {} : { failure: tally.failure }),
1858 };
1859 });
1860
1861 /** Work through `items`: whether each is done. */
1862 const work = (
1863 name: string,
1864 relayRun: RelayRun,
1865 items: ReadonlyArray<RelayItem>,
1866 tally: Tally,
1867 ): Effect.Effect<ReadonlyArray<boolean>> =>
1868 Effect.gen(function* () {
1869 const until = relayRun.deadline;
1870 const child = (suffix: string, chunk: ReadonlyArray<RelayItem>) =>
1871 Effect.map(
1872 persist(
1873 net.relay.run(`${name}${suffix}`, relayRun, chunk),
1874 until,
1875 () => `relay ${name}${suffix}`,
1876 // A child answers by the pass's deadline: allow it that, and a little more.
1877 () => Effect.map(Clock.currentTimeMillis, (now) => until - now + CALL_TIMEOUT_MS),
1878 tally,
1879 ),
1880 (result): ReadonlyArray<boolean> => {
1881 if (result === undefined) return chunk.map(() => false);
1882 tally.refused += result.refused;
1883 tally.instances += result.instances ?? 0;
1884 tally.failure ??= result.failure;
1885 return result.done;
1886 },
1887 );
1888 if (items.length > RELAY_FANOUT) {
1889 // Too many to call at once: split them among child relays.
1890 const size = Math.ceil(items.length / RELAY_FANOUT);
1891 const chunks = Array.from({ length: RELAY_FANOUT }, (_, i) =>
1892 items.slice(i * size, (i + 1) * size),
1893 ).filter((chunk) => chunk.length > 0);
1894 const done = yield* Effect.forEach(chunks, (chunk, i) => child(`/${i}`, chunk), {
1895 concurrency: RELAY_FANOUT,
1896 });
1897 return done.flat();
1898 }
1899 const only = items.length === 1 ? items[0]! : undefined;
1900 if (only !== undefined && "path" in only) {
1901 // One directory node: list it, and work through what it lists here.
1902 const next = yield* listed(only.path, relayRun, until, tally);
1903 if (next === undefined) return [false];
1904 yield* trace("relay-listed", { name, path: only.path, items: next.length });
1905 return [(yield* work(name, relayRun, next, tally)).every(Boolean)];
1906 }
1907 return yield* Effect.forEach(
1908 items,
1909 (item, i) =>
1910 "path" in item
1911 ? Effect.map(child(`.${i}`, [item]), (done) => done[0] === true)
1912 : instance(relayRun, item.ref, until, tally),
1913 { concurrency: RELAY_FANOUT },
1914 );
1915 });
1916
1917 /**
1918 * The subtrees a run's root paces its passes over: the directory listed level
1919 * by level until there are at least {@link FRONTIER_SIZE} of them (or nothing
1920 * left to list), with any instances listed above them. Many small subtrees
1921 * let the root steer its load finely.
1922 */
1923 const frontier = (run: RelayRun, until: number) =>
1924 Effect.gen(function* () {
1925 let level: ReadonlyArray<RelayItem> = [{ path: "" }];
1926 while (level.length < FRONTIER_SIZE && level.some((item) => "path" in item)) {
1927 const next: Array<RelayItem> = [];
1928 const listings = yield* Effect.forEach(
1929 level,
1930 (item): Effect.Effect<ReadonlyArray<RelayItem> | undefined> =>
1931 "path" in item ? listed(item.path, run, until) : Effect.succeed([item]),
1932 { concurrency: RELAY_FANOUT },
1933 );
1934 for (const listing of listings) {
1935 if (listing === undefined) return undefined;
1936 next.push(...listing);
1937 }
1938 level = next;
1939 }
1940 return level;
1941 });
1942
1943 return { run, frontier };
1944 };
1945
1946 export type Relay = ReturnType<typeof makeRelay>;
1947
1948 // ---------------------------------------------------------------- runs
1949
1950 /** A run's progress, at its root. */
1951 interface RunState {
1952 readonly plan: Plan;
1953 readonly phase: "discover" | "ready" | "complete";
1954 /** Passes in a row that weren't done: the next waits longer (see {@link RELAY_RETRY_MS}). */
1955 readonly misses?: number;
1956 /** How many subtrees it works through at once: see {@link makeRun}. */
1957 readonly window?: number;
1958 }
1959
1960 /** Subtrees a run's root starts with at once: it grows to all of them while the account takes the load. */
1961 const RUN_WINDOW = 16;
1962
1963 /** Calls a run's root keeps out at once: one object runs at most six. */
1964 const RUN_CALLS = 6;
1965
1966 /**
1967 * The root of a consumer's run: it drives passes of a relay tree from its own
1968 * jobs. A consumer keyed by its source needs one pass (each key reads its own
1969 * source). Any other needs two, with a barrier between: `discover` pushes every
1970 * source's history to its keys, and only once all of it is in does `ready`
1971 * tell the keys to apply it, in timestamp order. Each pass is repeated until
1972 * it is done.
1973 */
1974 export const makeRun = (
1975 storage: Storage,
1976 jobs: Jobs,
1977 net: Network,
1978 options: {
1979 /** How long a pass keeps at it before it answers (0: one try at everything). */
1980 readonly waitMillis: number;
1981 /** How long before a pass that wasn't done runs again, doubling each time up to 30s. */
1982 readonly againMillis: number;
1983 },
1984 ) => {
1985 const relay = makeRelay(net);
1986 const stateKey = (target: string) => `run:${enc(target)}`;
1987 const getState = (target: string) => storage.get<RunState>(stateKey(target));
1988 const progressKey = (target: string) => `prog:${enc(target)}`;
1989 const getProgress = (target: string) => storage.get<Progress>(progressKey(target));
1990
1991 /** A frontier item's mark that it is done in a phase: a pass that runs again skips it. */
1992 const doneKey = (target: string, phase: string, item: RelayItem) =>
1993 `rd:${enc(target)}:${phase}:${"path" in item ? `p:${item.path}` : `i:${refKey(item.ref)}`}`;
1994
1995 const drive = (target: string): Effect.Effect<void> =>
1996 Effect.gen(function* () {
1997 const state = yield* getState(target);
1998 if (state === undefined || state.phase === "complete") return;
1999 const started = yield* Clock.currentTimeMillis;
2000 const deadline = started + options.waitMillis;
2001 // One try at everything: every round runs in this pass, whatever the clock says.
2002 const quiet = options.waitMillis <= 0;
2003 const relayRun: RelayRun = {
2004 target,
2005 plan: state.plan,
2006 phase: state.phase,
2007 deadline,
2008 };
2009 const items = yield* relay.frontier(relayRun, deadline);
2010 const todo: Array<RelayItem> = [];
2011 for (const item of items ?? [])
2012 if ((yield* storage.get(doneKey(target, state.phase, item))) === undefined) todo.push(item);
2013 // What a deploy reports while it waits: kept apart from the state, written as it moves.
2014 const before = yield* getProgress(target);
2015 let progress: Progress = {
2016 target,
2017 phase: state.phase,
2018 subtrees: items?.length ?? before?.subtrees ?? 0,
2019 done: (items?.length ?? 0) - todo.length,
2020 instances: before?.phase === state.phase ? before.instances : 0,
2021 passes: (before?.phase === state.phase ? before.passes : 0) + 1,
2022 refused: before?.refused ?? 0,
2023 startedAt: before?.startedAt ?? started,
2024 updatedAt: started,
2025 ...(before?.lastError === undefined ? {} : { lastError: before.lastError }),
2026 };
2027 yield* storage.put({ [progressKey(target)]: progress });
2028 // Up to `window` subtrees out at once, in six calls (one object runs at most six at
2029 // once), each handing the relay tree its share; a new call as each one answers, with
2030 // what was given back sent again later. Like TCP's congestion window, `window` doubles
2031 // while the account takes the load, then grows slowly, and halves (once per window)
2032 // when Cloudflare refuses calls: a wide run stays under the account's limit rather
2033 // than hit it all at once and wait it out.
2034 let window = state.window ?? RUN_WINDOW;
2035 let growing = state.window === undefined;
2036 const queue = [...todo];
2037 let active = 0;
2038 let calls = 0;
2039 let refused = 0;
2040 let done = items !== undefined;
2041 let cutAt = 0;
2042 const finished = yield* Queue.unbounded<{
2043 readonly batch: ReadonlyArray<RelayItem>;
2044 readonly result: RelayResult;
2045 readonly launched: number;
2046 }>();
2047 while (queue.length > 0 || active > 0) {
2048 const open = quiet || (yield* Clock.currentTimeMillis) < deadline;
2049 while (open && active < RUN_CALLS && queue.length > 0) {
2050 const batch = queue.splice(0, Math.max(1, Math.round(window / RUN_CALLS)));
2051 const launched = yield* Clock.currentTimeMillis;
2052 const name = `${state.phase}-${state.misses ?? 0}/${calls++}`;
2053 yield* Effect.forkChild(
2054 relay
2055 .run(name, relayRun, batch)
2056 .pipe(Effect.flatMap((result) => Queue.offer(finished, { batch, result, launched }))),
2057 );
2058 active += 1;
2059 }
2060 if (active === 0) break;
2061 const { batch, result, launched } = yield* Queue.take(finished);
2062 active -= 1;
2063 refused += result.refused;
2064 const marks: Record<string, true> = {};
2065 const back: Array<RelayItem> = [];
2066 batch.forEach((item, i) => {
2067 if (result.done[i] === true) marks[doneKey(target, state.phase, item)] = true;
2068 else back.push(item);
2069 });
2070 progress = {
2071 ...progress,
2072 done: progress.done + Object.keys(marks).length,
2073 instances: progress.instances + (result.instances ?? 0),
2074 refused: progress.refused + result.refused,
2075 updatedAt: yield* Clock.currentTimeMillis,
2076 ...(result.failure === undefined ? {} : { lastError: result.failure }),
2077 };
2078 yield* storage.put({ ...marks, [progressKey(target)]: progress });
2079 if (result.refused > 0) {
2080 growing = false;
2081 if (launched >= cutAt) {
2082 window = Math.max(1, window / 2);
2083 cutAt = yield* Clock.currentTimeMillis;
2084 }
2085 } else {
2086 const step = batch.length;
2087 window = Math.min(todo.length, growing ? window + step : window + (step * step) / window);
2088 }
2089 if (back.length === 0) continue;
2090 // One try at everything: what wasn't done waits for the next pass.
2091 if (quiet) {
2092 done = false;
2093 continue;
2094 }
2095 queue.push(...back);
2096 // Nothing went through: wait a little before sending it again.
2097 if (back.length === batch.length)
2098 yield* Effect.sleep(`${yield* backoff(1, 1_000, 5_000)} millis`);
2099 }
2100 if (queue.length > 0) done = false;
2101 window = Math.max(1, Math.round(window));
2102 yield* Effect.logInfo(
2103 `backfill run-pass ${target} ${state.phase} done=${done} subtrees=${todo.length} window=${window} refused=${refused} in ${(yield* Clock.currentTimeMillis) - started}ms`,
2104 );
2105 if (!done) {
2106 const misses = (state.misses ?? 0) + 1;
2107 yield* storage.put({ [stateKey(target)]: { ...state, misses, window } });
2108 return yield* jobs.schedule(
2109 `drive:${target}`,
2110 Math.min(RELAY_RETRY_MAX_MS, options.againMillis * 2 ** (misses - 1)),
2111 );
2112 }
2113 const phase =
2114 state.plan.singleSource || state.phase === "ready" ? "complete" : ("ready" as const);
2115 yield* storage.put({
2116 [stateKey(target)]: { plan: state.plan, phase, window },
2117 [progressKey(target)]: {
2118 ...progress,
2119 phase,
2120 updatedAt: yield* Clock.currentTimeMillis,
2121 } satisfies Progress,
2122 });
2123 if (phase !== "complete") yield* jobs.schedule(`drive:${target}`, 0);
2124 else yield* clearPrefix(`rd:${enc(target)}:`);
2125 });
2126
2127 const clearPrefix = (prefix: string) =>
2128 Effect.gen(function* () {
2129 while (true) {
2130 const rows = yield* storage.list({ prefix, limit: 128 });
2131 if (rows.length === 0) return;
2132 yield* storage.delete(rows.map(([key]) => key));
2133 }
2134 });
2135
2136 return {
2137 begin: (target: string, plan: Plan) =>
2138 storage.exclusive(
2139 Effect.gen(function* () {
2140 const state = yield* getState(target);
2141 if (state !== undefined) {
2142 // The first plan stands: a run reads one set of sources, start to finish.
2143 if (!samePlan(state.plan, plan))
2144 return { status: "changed", started: state.plan } satisfies Begin;
2145 return { status: state.phase === "complete" ? "complete" : "started" } satisfies Begin;
2146 }
2147 yield* storage.put({
2148 [stateKey(target)]: { plan, phase: "discover" } satisfies RunState,
2149 });
2150 yield* jobs.schedule(`drive:${target}`, 0);
2151 return { status: "started" } satisfies Begin;
2152 }),
2153 ),
2154 phase: (target: string) =>
2155 Effect.map(getState(target), (state): Phase => state?.phase ?? "unknown"),
2156 /** How far the run has got; its phase is the run's own, so it never reads ahead of it. */
2157 progress: (target: string) =>
2158 Effect.gen(function* () {
2159 const phase: Phase = (yield* getState(target))?.phase ?? "unknown";
2160 const progress = yield* getProgress(target);
2161 return {
2162 target,
2163 subtrees: 0,
2164 done: 0,
2165 instances: 0,
2166 passes: 0,
2167 refused: 0,
2168 ...progress,
2169 phase,
2170 } satisfies Progress;
2171 }),
2172 /** Run a scheduled job by its id. */
2173 run: (id: string) => (id.startsWith("drive:") ? drive(id.slice("drive:".length)) : Effect.void),
2174 };
2175 };
2176
2177 export type Run = ReturnType<typeof makeRun>;
2178
2179 // ---------------------------------------------------------------- host glue
2180
2181 /**
2182 * Route a commit's deliveries (an aggregate's events, or a view key's entries):
2183 * live to caught-up consumers, and through the backfill to lagging ones. Call
2184 * inside the commit's exclusive section; returns what to send and the new cursors.
2185 */
2186 export const routeCommit = (
2187 source: Source,
2188 targets: ReadonlyArray<string>,
2189 routed: Routed | undefined,
2190 before: number,
2191 after: number,
2192 deliveries: ReadonlyArray<Delivery>,
2193 ) =>
2194 Effect.gen(function* () {
2195 const live = routeLive(targets, routed, before, after, deliveries);
2196 // A target behind here has its deliveries withheld: its reader reads them from the
2197 // log. An instance with no cursors predates catch-up: everything is live.
2198 if (routed !== undefined)
2199 for (const target of targets)
2200 if ((routed[target] ?? 0) !== before) yield* source.onCommit(target);
2201 return { send: live.deliveries, routed: live.routed };
2202 });
2203
2204 /** Route stored rows to one target only, as history: each row's seq and its deliveries. */
2205 export const routeRows = <Row>(
2206 replay: (input: ReplayInput<Row>) => Effect.Effect<ReplayResult>,
2207 id: string,
2208 targets: ReadonlyArray<string>,
2209 target: string,
2210 rows: ReadonlyArray<Row>,
2211 seqOf: (row: Row) => number,
2212 ) =>
2213 Effect.forEach(rows, (row) =>
2214 Effect.map(
2215 replay({
2216 id,
2217 routed: Object.fromEntries(
2218 targets.map((t) => [t, t === target ? seqOf(row) - 1 : Number.MAX_SAFE_INTEGER]),
2219 ),
2220 rows: [row],
2221 }),
2222 ({ deliveries }) => ({ seq: seqOf(row), deliveries }),
2223 ),
2224 );
2225
2226 /** A consumer's kind and name from its target id: `view:Name#2` is the view `Name`. */
2227 export const consumerOf = (target: string) => {
2228 const [kind, rest] = target.split(/:(.*)/s) as [string, string];
2229 return { kind: kind as "view" | "projection", name: rest.replace(/[#@]\d+$/, "") };
2230 };