The best way to control Claude Code, Codex and more from any computer or phone
Mirrored from https://github.com/Camo67/t3code.git
Synced Nov 21, 06:00 UTC
| 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 | }; |