sailfork / t3code-github / .repos/ alchemy-effect/ packages/ domain/ src/ Backfill.ts

import * as Cause from "effect/Cause";
import * as Clock from "effect/Clock";
import * as Data from "effect/Data";
import * as Effect from "effect/Effect";
import * as Predicate from "effect/Predicate";
import * as Queue from "effect/Queue";
import * as Random from "effect/Random";
import * as Semaphore from "effect/Semaphore";
import { type ReplayInput, type ReplayResult, type Routed, routeLive } from "./CatchUp.ts";
import type { Delivery } from "./Platform.ts";

/**
 * Backfill: how a view or projection added after its sources recorded events
 * (or rebuilt by bumping its version) receives their history, in timestamp
 * order, without a central coordinator.
 *
 * Roles, each a durable object that owns its own storage:
 *
 * - **Directory nodes** form a tree (fan-out 16, one subtree per source) that
 *   lists every source instance. It is only an index: a run reads it.
 * - **A run** per consumer generation: its root lists the directory into
 *   subtrees and paces them through **relays**, each fanning out six ways,
 *   backing off when the account's load is refused. A consumer keyed by its
 *   source needs one pass; any other needs two, with a barrier between.
 * - **Sources** (aggregate instances, and view keys other consumers read)
 *   serve their stored rows on any code, and switch a consumer to live
 *   delivery once a reader has read all of them.
 * - **Scanners**, one per source instance and consumer generation, read its
 *   rows, route them with the consumer's code and push each key its part.
 * - **Consumer keys** (view keys, projection keys) buffer what they receive
 *   ordered by `(at, stream, seq)` and, told that every source's history is
 *   in, apply it in that order. A key keyed by its source reads its source's
 *   rows itself and applies them as it reads.
 *
 * Every step does a bounded amount of work, records its progress before it
 * answers, and is idempotent, so a crash, a retry or a redeploy at any point
 * resumes where it left off. Every continuation is a scheduled job, never a
 * nested call.
 *
 * @internal
 */

// ---------------------------------------------------------------- runtime

/** A key-ordered store, as a Durable Object's storage is. */
export interface Storage {
  readonly get: <A>(key: string) => Effect.Effect<A | undefined>;
  readonly put: (entries: Readonly<Record<string, unknown>>) => Effect.Effect<void>;
  readonly delete: (keys: ReadonlyArray<string>) => Effect.Effect<void>;
  /** Entries under `prefix`, in key order, after `startAfter`. */
  readonly list: <A>(options: {
    readonly prefix: string;
    readonly startAfter?: string;
    readonly limit?: number;
  }) => Effect.Effect<ReadonlyArray<readonly [string, A]>>;
  /** Run `effect` with every other call on this object held back. */
  readonly exclusive: <A, E>(effect: Effect.Effect<A, E>) => Effect.Effect<A, E>;
}

/** Durable, at-least-once jobs on one object: a job with the same id replaces a pending one. */
export interface Jobs {
  /**
   * Run job `id` after `afterMillis`. The earliest request wins: a job already due
   * sooner isn't postponed (every job is idempotent, so running early is safe),
   * including one asked for while that job runs.
   */
  readonly schedule: (id: string, afterMillis: number) => Effect.Effect<void>;
}

/** An instance listed in the directory: its source (aggregate or view) and id. */
export interface SourceRef {
  readonly source: string;
  readonly id: string;
  /**
   * A view key's generation, once its view has been rebuilt: each generation's
   * keys are their own objects, so this names the one that holds its entries.
   */
  readonly generation?: number;
}

/**
 * What a run needs to know of a consumer. The deploy that adds the consumer
 * passes it to the run, so the run never depends on what an object's code knows.
 */
export interface Plan {
  /** The sources (aggregates and views, by name) the consumer reads: the subtrees a run lists (all if absent). */
  readonly sources?: ReadonlyArray<string>;
  /** Each key reads one instance, the one with its own id: the leaf starts the keys itself. */
  readonly singleSource: boolean;
  /** The generation of each source that is a rebuilt view (see {@link SourceRef.generation}). */
  readonly generations?: Readonly<Record<string, number>>;
}

/** `ref` with its source's generation, by the plan. */
export const withGeneration = (ref: SourceRef, plan: Plan | undefined): SourceRef => {
  const generation = plan?.generations?.[ref.source];
  return generation === undefined || generation === 0 ? ref : { ...ref, generation };
};

export interface NodeRpc {
  readonly register: (path: string, ref: SourceRef) => Effect.Effect<void>;
  readonly child: (path: string, child: string) => Effect.Effect<void>;
  /**
   * A page of what a node lists: its own instances after `after`, and (on the
   * first page) its children. Any code answers it, whatever consumers it knows.
   */
  readonly list: (path: string, after: string | undefined) => Effect.Effect<Listing>;
}

/** A page of a directory node's listing. */
export interface Listing {
  readonly rows: ReadonlyArray<SourceRef>;
  readonly children: ReadonlyArray<string>;
  /** Where the next page starts, if there is one. */
  readonly next?: string;
}

export interface SourceRpc {
  /**
   * `cursor`, `log` and, at the end of the log, `handoff`, in one call: what a
   * reader of a short history needs. Older code doesn't have it: a reader falls
   * back to the three calls.
   */
  readonly read: (
    ref: SourceRef,
    target: string,
    key: string,
    after: number,
    limit: number,
  ) => Effect.Effect<Read>;
  /**
   * The last seq it routed live to `target`: a reader reads after it, since the
   * rows up to it reached their keys live. An instance with no cursors predates
   * catch-up: everything is live, up to its version.
   */
  readonly cursor: (ref: SourceRef, target: string) => Effect.Effect<number>;
  /**
   * Its stored rows (events, or a view key's entries) after `after`, as stored.
   * Any code answers it: nothing in it depends on the consumer asking.
   */
  readonly log: (
    ref: SourceRef,
    after: number,
    limit: number,
  ) => Effect.Effect<ReadonlyArray<unknown>>;
  /**
   * Route `target` live from now on, if the reader has read every row up to its
   * version (`through`): `"more"` if rows were added since, `"stale"` on code
   * without the target. `key` names the reader, for traces.
   */
  readonly handoff: (
    ref: SourceRef,
    target: string,
    key: string,
    through: number,
  ) => Effect.Effect<Handoff>;
}

/** What a source answers to `handoff`. */
export type Handoff = "live" | "more" | "stale";

/** What a reader gets from one `read`: rows after `from`, and at the end of the log, the handoff. */
export interface Read {
  /** Where it read from: after `after`, or where live routing stopped (for `after` 0). */
  readonly from: number;
  readonly rows: ReadonlyArray<unknown>;
  /** Fewer rows than asked for: the end of the log, and whether it switched the target to live there. */
  readonly handoff?: Handoff;
}

/** A page a key read from its source. */
export interface Pulled {
  readonly deliveries: ReadonlyArray<Delivery>;
  /** The source switched the key to live delivery: nothing more to read. */
  readonly live: boolean;
  /**
   * The last seq the source read for this page: the key's cursor moves past it,
   * even when those rows held nothing for the key.
   */
  readonly through?: number;
  /**
   * Nothing followed this page when it was read: the key reads again at once to
   * switch to live, rather than wait.
   */
  readonly end?: boolean;
}

export interface ConsumerRpc {
  /** History for a key, from a scanner: it buffers it until it is told every source's is in. */
  readonly push: (
    target: string,
    key: string,
    deliveries: ReadonlyArray<Delivery>,
  ) => Effect.Effect<void>;
  /**
   * Every source's history is with the key: apply it. `"settled"` once applied;
   * it works on it for up to `waitMillis` before it answers.
   */
  readonly ready: (
    target: string,
    key: string,
    waitMillis?: number,
  ) => Effect.Effect<"pending" | "settled">;
  /**
   * Start a key of a consumer keyed by its source: it reads `ref`'s log itself.
   * `"settled"` once it has its history: it works on it for up to `waitMillis`
   * before it answers.
   */
  readonly start: (
    target: string,
    key: string,
    ref: SourceRef,
    waitMillis?: number,
  ) => Effect.Effect<"pending" | "settled">;
}

/**
 * A scanner reads one source instance's log for a consumer, routes it with the
 * consumer's code, and pushes each key its history: one object per source
 * instance and consumer generation, new with the deploy.
 */
export interface ScannerRpc {
  /** Push every key its history from `ref`, up to now: `true` once done, after up to `waitMillis`. */
  readonly scan: (target: string, ref: SourceRef, waitMillis: number) => Effect.Effect<boolean>;
  /** Tell every key it pushed to that all history is in: `true` once each has applied it. */
  readonly ready: (target: string, ref: SourceRef, waitMillis: number) => Effect.Effect<boolean>;
  /** A commit found the target behind on `ref` with no reader: read it and push what is new. */
  readonly kick: (target: string, ref: SourceRef) => Effect.Effect<void>;
}

/** What a relay works through: directory nodes to list, and source instances. */
export type RelayItem = { readonly path: string } | { readonly ref: SourceRef };

/** A pass of a relay tree over the directory, for one consumer. */
export interface RelayRun {
  readonly target: string;
  readonly plan: Plan;
  /**
   * `discover`: start each key (keyed by its source), or scan each source;
   * `ready`: tell each source's keys that every source's history is in.
   */
  readonly phase: "discover" | "ready";
  /**
   * When the pass answers (epoch ms): each relay keeps at its items until then,
   * and answers `false` if not all of them are done. Now, for one try at everything.
   */
  readonly deadline: number;
}

export interface RelayRpc {
  /**
   * Work through `items` for a run, and answer `true` once all of it is done.
   * `name` is the relay's place in the tree: each one is its own object.
   */
  readonly run: (
    name: string,
    run: RelayRun,
    items: ReadonlyArray<RelayItem>,
  ) => Effect.Effect<RelayResult>;
}

/** What a relay answers: which of its items are done, and how many calls the account's load refused. */
export interface RelayResult {
  readonly done: ReadonlyArray<boolean>;
  readonly refused: number;
  /** Source instances done under it. */
  readonly instances?: number;
  /** A call it gave up on, and why. */
  readonly failure?: string;
}

/** How far a consumer's run has got: `ready` once every source's history is with its keys. */
export type Phase = "unknown" | "discover" | "ready" | "complete";

/** The root of a consumer's run: one object per consumer generation. */
export interface RunRpc {
  /**
   * Start the run, once. A run already started (or complete) is found, not
   * started again; one started with a different plan (the consumer reads other
   * sources now, without a version bump) answers `changed`.
   */
  readonly begin: (target: string, plan: Plan) => Effect.Effect<Begin>;
  readonly phase: (target: string) => Effect.Effect<Phase>;
  readonly progress: (target: string) => Effect.Effect<Progress>;
}

/** What starting a run answers. */
export type Begin =
  | { readonly status: "started" | "complete" }
  /** Started with another plan: it reads what `started` says, not what was asked. */
  | { readonly status: "changed"; readonly started: Plan };

/** Whether two plans read the same sources, at the same generations, the same way. */
export const samePlan = (a: Plan, b: Plan) => {
  const sources = (plan: Plan) =>
    plan.sources === undefined ? "*" : [...plan.sources].sort().join(",");
  const generations = (plan: Plan) =>
    Object.entries(plan.generations ?? {})
      .filter(([, generation]) => generation > 0)
      .sort(([x], [y]) => x.localeCompare(y))
      .map(([source, generation]) => `${source}#${generation}`)
      .join(",");
  return (
    a.singleSource === b.singleSource &&
    sources(a) === sources(b) &&
    generations(a) === generations(b)
  );
};

/**
 * Why a deploy can't wait on a run started with another plan: the consumer now
 * reads sources its run doesn't, and only a new generation reads them.
 */
export const planChanged = (target: string, started: Plan, asked: Plan) => {
  const list = (plan: Plan) =>
    plan.sources === undefined ? "every source" : plan.sources.join(", ");
  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.`;
};

/** A consumer reads other sources than its backfill was started with, at the same version. */
export class PlanChanged extends Data.TaggedError("BackfillPlanChanged")<{
  readonly message: string;
}> {}

/** How far a run has got, for a deploy to report while it waits. */
export interface Progress {
  readonly target: string;
  readonly phase: Phase;
  /** The subtrees of the directory this phase works through, and how many are done. */
  readonly subtrees: number;
  readonly done: number;
  /** Source instances (keys keyed by their source, or scanners) done in this phase. */
  readonly instances: number;
  /** Passes over the directory so far: a pass that isn't done in time is followed by another. */
  readonly passes: number;
  /** Calls Cloudflare refused for the account's load: the run backs off when it does. */
  readonly refused: number;
  /** When the run began, and when it last moved, in epoch milliseconds. */
  readonly startedAt?: number;
  readonly updatedAt?: number;
  /** The last call it gave up on, if any, and why. */
  readonly lastError?: string;
}

/** How the roles reach each other. */
export interface Network {
  readonly node: NodeRpc;
  readonly source: SourceRpc;
  readonly consumer: ConsumerRpc;
  readonly scanner: ScannerRpc;
  readonly relay: RelayRpc;
  readonly run: RunRpc;
}

/** Tuning, in rows and calls per step. */
export interface Limits {
  /** History rows a reader (a key keyed by its source, or a scanner) reads per call. */
  readonly page: number;
  /** Source instances a directory node handles per step, and calls it makes at once. */
  readonly nodePage: number;
  readonly concurrency: number;
  /** Buffered rows a key applies per step. */
  readonly apply: number;
  /** How long to wait before calling a stale source again, in milliseconds. */
  readonly staleRetryMillis: number;
  /**
   * How long before the first retry of a refused or failed call, in milliseconds:
   * right after a deploy its new code may not have reached the object yet.
   */
  readonly firstRetryMillis: number;
  /** How long a key without sources waits before asking whether discovery is complete again. */
  readonly pollMillis: number;
  /**
   * Instances a directory node lists before it splits into 16 children, so every
   * node's share of a listing stays bounded and the tree grows as log16 of the instances.
   */
  readonly leafSize: number;
  /** The depth instances list themselves at, before any split. */
  readonly depth: number;
}

/**
 * The depth instances list themselves at: 256 leaves, each splitting once it
 * fills. Wide enough that first commits spread over many objects, few enough
 * that a small Domain's directory stays small (every node costs a listing).
 */
export const DEPTH = 2;

export const defaultLimits: Limits = {
  // A long history arrives in few round trips: each one costs more than its rows.
  page: 1_000,
  nodePage: 25,
  concurrency: 5,
  apply: 200,
  staleRetryMillis: 30_000,
  firstRetryMillis: 1_000,
  pollMillis: 5_000,
  leafSize: 256,
  depth: DEPTH,
};

// ---------------------------------------------------------------- keys

const enc = encodeURIComponent;
const pad = (n: number, width: number) => String(Math.max(0, Math.floor(n))).padStart(width, "0");

/** Log a protocol step at debug level (`backfill <step>` and a JSON body), to follow a backfill. */
const trace = (step: string, fields: Record<string, unknown>) =>
  Effect.logDebug(`backfill ${step} ${JSON.stringify(fields)}`);

/**
 * The directory has one subtree per source (`Account:`, `Deposits:`), so a run
 * for a consumer walks only the sources it reads. Within a subtree a node's path
 * is the source, a colon and a prefix of the instance's hash: `Account:a3`.
 */
export const leafOf = (ref: SourceRef, depth: number = DEPTH): string =>
  `${ref.source}:${hashOf(ref).slice(0, depth)}`;

/** The hash digits of a path: its depth within its source's subtree. */
const digitsOf = (path: string) => path.slice(path.indexOf(":") + 1);

/** The source a node's subtree lists, or `undefined` for the root (and news relays). */
export const sourceOfPath = (path: string): string | undefined => {
  const colon = path.indexOf(":");
  return colon < 0 ? undefined : path.slice(0, colon);
};

/** The FNV-1a hash of an instance's source and id, as 8 hex digits: its path in the tree. */
const hashOf = ({ source, id }: SourceRef): string => {
  let hash = 0x811c9dc5;
  for (const char of `${source}/${id}`) {
    hash ^= char.charCodeAt(0);
    hash = Math.imul(hash, 0x01000193) >>> 0;
  }
  // FNV-1a barely moves the high bits for ids that differ in their last characters
  // (`b0`, `b1`, …): mix them in (murmur3's finalizer), so the tree fills evenly.
  hash ^= hash >>> 16;
  hash = Math.imul(hash, 0x85ebca6b);
  hash ^= hash >>> 13;
  hash = Math.imul(hash, 0xc2b2ae35);
  hash ^= hash >>> 16;
  return (hash >>> 0).toString(16).padStart(8, "0");
};

/** The child of a split node that lists an instance: one more hex digit of its hash. */
const childFor = (path: string, ref: SourceRef) =>
  `${ref.source}:${hashOf(ref).slice(0, digitsOf(path).length + 1)}`;

/** A source's subtree (`Account:`) hangs off the root; a news relay (`a3`) climbs by digit. */
const parentOf = (path: string) => (path.endsWith(":") ? "" : path.slice(0, -1));
const refKey = (ref: SourceRef) => `${enc(ref.source)}:${enc(ref.id)}`;

/** A buffered delivery's place in a key's merge: timestamp, then stream, then seq. */
export const orderKey = (target: string, delivery: Delivery) =>
  `bf:b:${enc(target)}:${pad(delivery.envelope.at, 15)}:${enc(delivery.source)}:${pad(delivery.seq, 12)}`;

// ---------------------------------------------------------------- outbox

type Message =
  /** Start the key of a consumer keyed by its source, which no run started. */
  | {
      readonly kind: "start";
      readonly target: string;
      readonly key: string;
      readonly ref: SourceRef;
    }
  /** Ask a scanner to read a source instance no run read. */
  | { readonly kind: "kick"; readonly target: string; readonly ref: SourceRef };

const OUTBOX_LEASE_MS = 60_000;

/**
 * How long before a failed send is tried again: past the ~20s a Durable Object
 * must sit idle before it leaves the code it ran before a deploy, so retries to
 * one still on older code don't keep it there.
 */
const RETRY_MS = 30_000;

/** Instances a directory node lists per page. */
const LIST_PAGE = 512;

/** How long a key started with a wait pauses between pages that couldn't go further. */
const WAIT_PAUSE_MS = 50;

/**
 * Cloudflare refuses calls when an account puts too much load on Durable
 * Objects, and resets an isolate whose objects (many share one) use too much
 * memory. Either is a sign to send less: a refused call is tried again later,
 * not at once, so a wide run backs off to the load the account can take
 * rather than collapse under its own retries.
 */
export const overloaded = (cause: Cause.Cause<unknown>) => {
  const error = Cause.squash(cause);
  return /too much load|too many concurrent|overloaded|try again later|exceeded its memory limit/i.test(
    Predicate.hasProperty(error, "message") ? String(error.message) : String(error),
  );
};

/** A wait after `failures` failures in a row: doubling from `base`, up to `max`, jittered. */
const backoff = (failures: number, base: number, max: number) =>
  Effect.map(Random.next, (jitter) =>
    Math.round(Math.min(max, base * 2 ** Math.max(0, failures - 1)) * (0.5 + jitter)),
  );

/** A key's pause between pages: short while it makes progress, backing off while calls fail. */
const pause = (failures: number) =>
  failures === 0 ? Effect.succeed(WAIT_PAUSE_MS) : backoff(failures, 250, 5_000);

/**
 * Run a job again after a refusal or a failure, waiting twice as long each time:
 * from `firstRetryMillis`, so a one-off failure (or a deploy's code still on its
 * way to an object) costs seconds, up to four times the slow pace. Cloudflare moves
 * a Durable Object to new code when it is evicted after sitting idle: calls at a
 * short, fixed pace would keep one on older code, so the gaps grow until it can.
 */
const makeRetry = (storage: Storage, jobs: Jobs, limits: Limits) => {
  const key = (id: string) => `bf:retry:${id}`;
  return {
    later: (id: string, slowMillis: number) =>
      Effect.gen(function* () {
        const tries = (yield* storage.get<number>(key(id))) ?? 0;
        yield* storage.put({ [key(id)]: tries + 1 });
        yield* jobs.schedule(
          id,
          Math.min(slowMillis * 4, limits.firstRetryMillis * 2 ** Math.min(tries, 20)),
        );
      }),
    /** The job went through: its next failure retries soon again. */
    clear: (id: string) =>
      Effect.gen(function* () {
        if ((yield* storage.get(key(id))) !== undefined) yield* storage.delete([key(id)]);
      }),
  };
};
type Retry = ReturnType<typeof makeRetry>;

/** A call that counts as lost if it hasn't answered in time: a hung call would stall its caller. */
const bounded = <A, E>(call: Effect.Effect<A, E>) => call.pipe(Effect.timeout("20 seconds"));

/** Where `ref`'s live routing to `target` stopped; 0 (read it all) if it can't say (older code). */
const cursorOf = (net: Network, ref: SourceRef, target: string) =>
  bounded(net.source.cursor(ref, target)).pipe(Effect.catchCause(() => Effect.succeed(0)));

/**
 * Read a page of `ref`'s log for `target` in one call (see `SourceRpc.read`).
 * A source on older code has no `read`: fall back to `cursor` and `log`, and
 * the caller asks for the handoff itself. A call the account's load refused
 * fails, for the caller to back off.
 */
const readAt = (
  net: Network,
  ref: SourceRef,
  target: string,
  key: string,
  after: number,
  limit: number,
): Effect.Effect<Read, unknown> =>
  bounded(net.source.read(ref, target, key, after, limit)).pipe(
    Effect.catchCauseIf(
      (cause) => !overloaded(cause),
      () =>
        Effect.gen(function* () {
          const from = after > 0 ? after : yield* cursorOf(net, ref, target);
          const rows = yield* bounded(net.source.log(ref, from, limit));
          return { from, rows } satisfies Read;
        }),
    ),
  );

/** A target's generation: `view:Name#2` is 2. */
const generationOf = (target: string) => Number(/[#@](\d+)$/.exec(target)?.[1] ?? 0);

/** Refused by an instance still on older code; the sender tries again later. */
class Stale extends Data.TaggedError("Stale")<{ readonly message: string }> {}

/**
 * A source's durable outbox of control messages: staged with the state change
 * that produced them, sent in order, deleted once sent. One flush at a time.
 */
const outbox = (storage: Storage, jobs: Jobs, net: Network, retry: Retry) => {
  const send = (message: Message): Effect.Effect<void> =>
    message.kind === "start"
      ? Effect.asVoid(net.consumer.start(message.target, message.key, message.ref))
      : net.scanner.kick(message.target, message.ref);
  const acquire = storage.exclusive(
    Effect.gen(function* () {
      const held = yield* storage.get<number>("bf:q-lease");
      const now = yield* Effect.sync(() => Date.now());
      if (held !== undefined && held > now) return false;
      yield* storage.put({ "bf:q-lease": now + OUTBOX_LEASE_MS });
      return true;
    }),
  );
  /** Send every staged message; `true` when the outbox is empty. */
  const flush: Effect.Effect<boolean> = Effect.gen(function* () {
    // Nothing staged: no lease to take.
    if ((yield* storage.list({ prefix: "bf:q:", limit: 1 })).length === 0) return true;
    // Another flush holds the lease; it may stop before this one's rows: try again later.
    if (!(yield* acquire)) return yield* Effect.as(jobs.schedule("bf-flush", RETRY_MS), false);
    return yield* Effect.gen(function* () {
      while (true) {
        const rows = yield* storage.list<Message>({ prefix: "bf:q:", limit: 50 });
        if (rows.length === 0) {
          yield* retry.clear("bf-flush");
          return true;
        }
        for (const [key, message] of rows) {
          yield* send(message);
          yield* storage.delete([key]);
        }
      }
    }).pipe(
      // A send failed: the rest stay staged, and the backstop sends them later.
      Effect.catchCause(() => Effect.as(retry.later("bf-flush", RETRY_MS), false)),
      Effect.ensuring(storage.delete(["bf:q-lease"])),
    );
  });
  return {
    /** Stage messages; call inside the exclusive section that commits their cause. */
    stage: (messages: ReadonlyArray<Message>) =>
      Effect.gen(function* () {
        if (messages.length === 0) return;
        const last = ((yield* storage.get<number>("bf:q-seq")) ?? 0) + messages.length;
        const rows: Record<string, Message> = { "bf:q-seq": last as never };
        messages.forEach((message, index) => {
          rows[`bf:q:${pad(last - messages.length + index + 1, 12)}`] = message;
        });
        yield* storage.put(rows);
        // The backstop: sent even if this instance dies before a flush runs.
        yield* jobs.schedule("bf-flush", 5_000);
      }),
    flush,
  };
};

// ---------------------------------------------------------------- sources

/** What a source instance gives the protocol. */
export interface SourceHost {
  readonly ref: SourceRef;
  /** Every consumer in the model this instance's code runs: a target outside it is from newer code. */
  readonly model: () => ReadonlyArray<string>;
  /** Whether `target`'s keys are keyed by their source: each reads its own source's log. */
  readonly singleSource?: (target: string) => boolean;
  /** Its current version: the seq of its last event or entry. */
  readonly version: Effect.Effect<number>;
  readonly routed: Effect.Effect<Routed | undefined>;
  /** Route `target` live from the current version on. Called holding the exclusive section. */
  readonly markLive: (target: string) => Effect.Effect<void>;
  /** Its stored rows after `after`, as stored: what a reader routes with its own code. */
  readonly log: (after: number, limit: number) => Effect.Effect<ReadonlyArray<unknown>>;
}

/**
 * A source instance's part of the protocol: it serves its log as stored, on
 * any code, and switches a target to live delivery once a reader has read all
 * of it. Until then a commit withholds the target's deliveries (the reader
 * reads them from the log). The first commit to withhold them on code that
 * knows the target asks for a reader: an instance no run listed (one created
 * on older code during a rollout) is caught up that way.
 */
export const makeSource = (
  storage: Storage,
  jobs: Jobs,
  net: Network,
  host: SourceHost,
  limits: Limits = defaultLimits,
) => {
  const retry = makeRetry(storage, jobs, limits);
  const queue = outbox(storage, jobs, net, retry);
  const kickedKey = (target: string) => `bf:kick:${enc(target)}`;

  const fromKey = (target: string) => `bf:from:${enc(target)}`;

  /**
   * Where live routing to `target` stopped (see `SourceRpc.cursor`), as it was
   * when its reader first asked: kept, so a reader that asks again (its answer
   * lost after the source went live) starts at the same row, not past it.
   */
  const cursor = (target: string) =>
    storage.exclusive(
      Effect.gen(function* () {
        const kept = yield* storage.get<number>(fromKey(target));
        if (kept !== undefined) return kept;
        const routed = yield* host.routed;
        const from = routed === undefined ? yield* host.version : (routed[target] ?? 0);
        yield* storage.put({ [fromKey(target)]: from });
        return from;
      }),
    );

  const handoff = (target: string, key: string, through: number) =>
    Effect.gen(function* () {
      if (!host.model().includes(target)) return "stale" as Handoff;
      const result = yield* storage.exclusive(
        Effect.gen(function* () {
          // Rows were added after the reader read up to `through`: it reads them first.
          if ((yield* host.version) > through) return "more" as const;
          const routed = yield* host.routed;
          if (routed !== undefined && (routed[target] ?? 0) < through) yield* host.markLive(target);
          yield* storage.delete([kickedKey(target)]);
          return "live" as const;
        }),
      );
      yield* trace("handoff", { source: host.ref, target, key, through, result });
      return result as Handoff;
    });

  return {
    /**
     * A commit withheld `target`'s deliveries: it is behind here. Ask for a
     * reader, once. Call inside the commit's exclusive section.
     */
    onCommit: (target: string) =>
      Effect.gen(function* () {
        if ((yield* storage.get(kickedKey(target))) !== undefined) return;
        yield* storage.put({ [kickedKey(target)]: true });
        yield* queue.stage([
          host.singleSource?.(target) === true
            ? { kind: "start", target, key: host.ref.id, ref: host.ref }
            : { kind: "kick", target, ref: host.ref },
        ]);
      }),

    log: (after: number, limit: number) => host.log(after, limit),

    cursor: (target: string) => cursor(target),

    read: (target: string, key: string, after: number, limit: number) =>
      Effect.gen(function* () {
        const from = after > 0 ? after : yield* cursor(target);
        const rows = yield* host.log(from, limit);
        if (rows.length >= limit) return { from, rows } satisfies Read;
        // Rows are numbered without gaps: these end at `from + rows.length`.
        return {
          from,
          rows,
          handoff: yield* handoff(target, key, from + rows.length),
        } satisfies Read;
      }),

    handoff: (target: string, key: string, through: number) => handoff(target, key, through),

    /** The backstop job: send what is staged. */
    flush: Effect.asVoid(queue.flush),
  };
};

export type Source = ReturnType<typeof makeSource>;

// ---------------------------------------------------------------- scanners

/** What a scanner gives the protocol: the consumer's routing, in the code it runs. */
export interface ScannerHost {
  /** Route a source's stored rows (from its `log`) to `target`: each row's seq and its deliveries. */
  readonly route: (
    target: string,
    ref: SourceRef,
    rows: ReadonlyArray<unknown>,
  ) => Effect.Effect<
    ReadonlyArray<{ readonly seq: number; readonly deliveries: ReadonlyArray<Delivery> }>
  >;
}

/** A scanner's progress through one source instance, for one target. */
interface ScanState {
  readonly ref: SourceRef;
  /** It has asked the source where live routing stopped, and starts there. */
  readonly started?: boolean;
  /** Every row up to this seq is with its keys. */
  readonly through: number;
  /** Read to the end of the log at least once: the history a run waits for is with its keys. */
  readonly scanned: boolean;
  /** The source routes the target live: nothing more to read. */
  readonly live: boolean;
  /**
   * Past the run's barrier: keys it pushes to from now on are told at once that
   * all history is in (no pass will tell them).
   */
  readonly readied?: boolean;
  /** Started by a commit, not a run: it asks the run whether it is past the barrier. */
  readonly kicked?: boolean;
}

/**
 * A scanner: reads one source instance's log, as stored, routes it with the
 * consumer's code, and pushes each key the deliveries it gets. At the end of
 * the log it asks the source to route the target live from there; a source
 * still on older code can't, so the scanner reads on later (what it reads then
 * is newer than the deploy, and arrives as live deliveries would).
 */
export const makeScanner = (
  storage: Storage,
  jobs: Jobs,
  net: Network,
  host: ScannerHost,
  limits: Limits = defaultLimits,
) => {
  const retry = makeRetry(storage, jobs, limits);
  const stateKey = (target: string) => `bf:sc:${enc(target)}`;
  const keysPrefix = (target: string) => `bf:sk:${enc(target)}:`;
  const jobId = (target: string) => `bf-scan:${target}`;
  const getState = (target: string) => storage.get<ScanState>(stateKey(target));

  /** Start where the source's live routing stopped: the keys have every row before it. */
  const start = (target: string, state: ScanState) =>
    Effect.gen(function* () {
      const cursor = yield* cursorOf(net, state.ref, target);
      return yield* storage.exclusive(
        Effect.gen(function* () {
          const current = (yield* getState(target)) ?? state;
          if (current.started) return current;
          const started = { ...current, started: true, through: Math.max(current.through, cursor) };
          yield* storage.put({ [stateKey(target)]: started });
          return started;
        }),
      );
    });

  /** Whether the run is past its barrier, as far as this scanner knows (it asks only if a commit started it). */
  const pastBarrier = (target: string, state: ScanState) =>
    Effect.gen(function* () {
      if (state.readied) return true;
      if (!state.kicked) return false;
      const phase = yield* net.run.phase(target);
      if (phase !== "ready" && phase !== "complete") return false;
      yield* storage.exclusive(
        Effect.gen(function* () {
          const current = yield* getState(target);
          if (current !== undefined && !current.readied)
            yield* storage.put({ [stateKey(target)]: { ...current, readied: true } });
        }),
      );
      return true;
    });

  const init = (target: string, ref: SourceRef, kicked = false) =>
    storage.exclusive(
      Effect.gen(function* () {
        const state = yield* getState(target);
        if (state !== undefined) return state;
        const fresh: ScanState = {
          ref,
          through: 0,
          scanned: false,
          live: false,
          ...(kicked ? { kicked } : {}),
        };
        yield* storage.put({ [stateKey(target)]: fresh });
        return fresh;
      }),
    );

  /**
   * One step: read and push a page, or at the end of the log, ask the source
   * to route the target live. `pushed` once the history up to now is with its
   * keys; `next` says whether to step again now, later (the source is on older
   * code), or never (it routes the target live).
   */
  const step = (
    target: string,
  ): Effect.Effect<{ readonly pushed: boolean; readonly next: "now" | "later" | "never" }> =>
    Effect.gen(function* () {
      const found = yield* getState(target);
      if (found === undefined || found.live) return { pushed: true, next: "never" } as const;
      const state = found.started ? found : yield* start(target, found);
      const rows = yield* bounded(net.source.log(state.ref, state.through, limits.page)).pipe(
        Effect.orDie,
      );
      if (rows.length > 0) {
        const routed = yield* host.route(target, state.ref, rows);
        const through = routed.length > 0 ? routed[routed.length - 1]!.seq : state.through;
        const byKey = new Map<string, Array<Delivery>>();
        for (const row of routed)
          for (const delivery of row.deliveries) {
            const list = byKey.get(delivery.key) ?? [];
            list.push(delivery);
            byKey.set(delivery.key, list);
          }
        yield* Effect.forEach(
          byKey,
          ([key, deliveries]) =>
            bounded(net.consumer.push(target, key, deliveries)).pipe(Effect.orDie),
          { concurrency: limits.concurrency, discard: true },
        );
        // The keys first, so a `ready` pass lists them; then, past the barrier (which no
        // pass will tell them of), tell them here; only then move past these rows, so a
        // step that fails telling them reads and tells them again. (`ready` marks the
        // state before it lists keys, so a key is told by one or the other.)
        const keys: Record<string, true> = {};
        for (const key of byKey.keys()) keys[`${keysPrefix(target)}${enc(key)}`] = true;
        yield* storage.exclusive(storage.put(keys));
        const current = yield* getState(target);
        if (current === undefined || current.through !== state.through)
          return { pushed: state.scanned, next: "now" } as const;
        if (yield* pastBarrier(target, current))
          yield* Effect.forEach(
            byKey.keys(),
            (key) => bounded(net.consumer.ready(target, key, 0)).pipe(Effect.orDie),
            { concurrency: limits.concurrency, discard: true },
          );
        yield* storage.exclusive(
          Effect.gen(function* () {
            const latest = yield* getState(target);
            if (latest !== undefined && latest.through === state.through)
              yield* storage.put({ [stateKey(target)]: { ...latest, through } });
          }),
        );
        if (rows.length >= limits.page) return { pushed: state.scanned, next: "now" } as const;
      }
      // The end of the log: ask the source to deliver live from here.
      const after = (yield* getState(target))!;
      const handoff = yield* bounded(net.source.handoff(after.ref, target, "", after.through)).pipe(
        Effect.catchCause(() => Effect.succeed("stale" as Handoff)),
      );
      if (handoff === "more") return { pushed: after.scanned, next: "now" } as const;
      yield* storage.exclusive(
        Effect.gen(function* () {
          const current = yield* getState(target);
          if (current === undefined || current.through !== after.through) return;
          yield* storage.put({
            [stateKey(target)]: { ...current, scanned: true, live: handoff === "live" },
          });
        }),
      );
      yield* trace("scanned", { ref: after.ref, target, through: after.through, handoff });
      // Still on older code: read on later, past what arrives meanwhile.
      if (handoff === "stale") yield* retry.later(jobId(target), limits.staleRetryMillis);
      else yield* retry.clear(jobId(target));
      return { pushed: true, next: handoff === "live" ? "never" : "later" } as const;
    });

  /** Keep stepping until the history up to now is pushed, or `until` (epoch ms). */
  const scanUntil = (target: string, until: number) =>
    Effect.gen(function* () {
      while (true) {
        const { pushed, next } = yield* step(target);
        if (pushed) return true;
        if (next !== "now" || (yield* Clock.currentTimeMillis) >= until) {
          // The rest in jobs; the run asks again.
          if (next === "now") yield* jobs.schedule(jobId(target), 0);
          return false;
        }
      }
    });

  return {
    scan: (target: string, ref: SourceRef, waitMillis: number) =>
      Effect.gen(function* () {
        const state = yield* init(target, ref);
        if (state.scanned) return true;
        return yield* scanUntil(target, (yield* Clock.currentTimeMillis) + waitMillis);
      }),

    ready: (target: string, waitMillis: number) =>
      Effect.gen(function* () {
        // Marked before it lists keys: one pushed to after the listing is told by `step`.
        yield* storage.exclusive(
          Effect.gen(function* () {
            const current = yield* getState(target);
            if (current !== undefined && !current.readied)
              yield* storage.put({ [stateKey(target)]: { ...current, readied: true } });
          }),
        );
        const until = (yield* Clock.currentTimeMillis) + waitMillis;
        let after: string | undefined;
        let done = true;
        while (true) {
          const rows = yield* storage.list({
            prefix: keysPrefix(target),
            ...(after === undefined ? {} : { startAfter: after }),
            limit: 256,
          });
          if (rows.length === 0) return done;
          const settled = yield* Effect.forEach(
            rows,
            ([row]) =>
              Effect.gen(function* () {
                const key = decodeURIComponent(row.slice(keysPrefix(target).length));
                while (true) {
                  const left = until - (yield* Clock.currentTimeMillis);
                  const wait = Math.max(0, Math.min(RELAY_KEY_WAIT_MS, left));
                  const result = yield* net.consumer
                    .ready(target, key, wait)
                    .pipe(Effect.timeout(`${wait + CALL_TIMEOUT_MS} millis`), Effect.orDie);
                  if (result === "settled") return true;
                  if ((yield* Clock.currentTimeMillis) >= until) return false;
                }
              }),
            { concurrency: limits.concurrency },
          );
          done = done && settled.every(Boolean);
          after = rows[rows.length - 1]![0];
        }
      }),

    kick: (target: string, ref: SourceRef) =>
      Effect.gen(function* () {
        const state = yield* init(target, ref, true);
        if (!state.live) yield* jobs.schedule(jobId(target), 0);
      }),

    /** Run a scheduled job by its id. */
    run: (id: string) =>
      Effect.gen(function* () {
        const { next } = yield* step(id.slice("bf-scan:".length));
        if (next === "now") yield* jobs.schedule(id, 0);
      }).pipe(Effect.catchCause(() => retry.later(id, RETRY_MS))),
  };
};

export type Scanner = ReturnType<typeof makeScanner>;

// ---------------------------------------------------------------- consumer keys

/** A consumer key's view of one of its sources during a backfill. */
interface Feed {
  readonly ref: SourceRef | null;
  /** The last seq pulled. */
  readonly cursor: number;
  /** Switched to live delivery: nothing more to pull. */
  readonly live: boolean;
  /** Deliveries from it waiting in the buffer. */
  readonly buffered: number;
}

/** What a consumer key gives the protocol. */
export interface ConsumerHost {
  readonly key: string;
  /** This consumer's target id in the code this instance runs. */
  readonly target: () => string;
  /**
   * Whether each key hears only from the source instance with its own id: then
   * it reads that instance's log itself, as soon as its leaf starts it (no
   * barrier), and applies what it reads directly (nothing to merge).
   */
  readonly singleSource?: () => boolean;
  /**
   * Route a source's stored rows (from its `log`) to this consumer: each row's
   * seq and its deliveries. Runs this key's code, whatever code the source runs.
   */
  readonly history?: (
    ref: SourceRef,
    rows: ReadonlyArray<unknown>,
  ) => Effect.Effect<
    ReadonlyArray<{ readonly seq: number; readonly deliveries: ReadonlyArray<Delivery> }>
  >;
  /** The sources this consumer reads (`Account`, `Deposits`): where it asks about discovery. */
  readonly sources?: () => ReadonlyArray<string>;
  /**
   * Apply deliveries in order, as the live path would. Called holding the
   * exclusive section.
   */
  readonly apply: (deliveries: ReadonlyArray<Delivery>) => Effect.Effect<void>;
  /** Work an `apply` left for after its exclusive section commits (pushes, sends). */
  readonly after?: Effect.Effect<void>;
}

/**
 * A consumer key's part of the protocol. Its host passes every delivery for
 * the current target through {@link Consumer.admit} before applying it, and
 * serves `source` and `ready`.
 */
export const makeConsumer = (
  storage: Storage,
  jobs: Jobs,
  net: Network,
  host: ConsumerHost,
  limits: Limits = defaultLimits,
) => {
  const T = (target: string) => enc(target);
  const backfillKey = (target: string) => `bf:c:${T(target)}`;
  const doneKey = (target: string) => `bf:done:${T(target)}`;
  const feedKey = (target: string, stream: string) => `bf:f:${T(target)}:${enc(stream)}`;
  const feedsPrefix = (target: string) => `bf:f:${T(target)}:`;
  /** Feeds still pulling with nothing buffered: the merge can't apply past them. */
  const starvedKey = (target: string, stream: string) => `bf:x:${T(target)}:${enc(stream)}`;
  const starvedPrefix = (target: string) => `bf:x:${T(target)}:`;
  const pullingKey = (target: string, stream: string) => `bf:p:${T(target)}:${enc(stream)}`;
  const pullingPrefix = (target: string) => `bf:p:${T(target)}:`;
  const bufferPrefix = (target: string) => `bf:b:${T(target)}:`;
  /** A buffered delivery held, not counted: see `buffer`. */
  const heldKey = (row: string) => `bf:h:${row.slice("bf:b:".length)}`;
  const jobId = (target: string) => `bf-merge:${target}`;
  /** Keyed by its source: it has read its source's log to the end (its history is here). */
  const caughtKey = (target: string) => `bf:caught:${T(target)}`;
  const retry = makeRetry(storage, jobs, limits);
  /**
   * A message for another generation of this consumer. A newer one means this
   * instance still runs older code: refuse it, so the sender tries again once
   * it runs the deployed code. An older one is from a superseded backfill.
   */
  const stale = (target: string) =>
    generationOf(target) > generationOf(host.target())
      ? Effect.die(new Stale({ message: `${host.key} runs ${host.target()}, not ${target} yet` }))
      : Effect.void;

  interface Backfill {
    /** Every source's history is here: apply it in order. */
    readonly ready: boolean;
    /** A scanner pushed it history: that scanner tells it when it is ready. */
    readonly pushed?: boolean;
  }

  const begin = (target: string) =>
    Effect.gen(function* () {
      const existing = yield* storage.get<Backfill>(backfillKey(target));
      if (existing) return existing;
      const backfill: Backfill = { ready: false };
      yield* storage.put({ [backfillKey(target)]: backfill });
      yield* jobs.schedule(jobId(target), 0);
      return backfill;
    });

  /** Record a feed's buffered count and whether it starves the merge. */
  const starves = (feed: Feed | undefined) =>
    feed !== undefined && !feed.live && feed.buffered === 0;
  const putFeed = (target: string, stream: string, feed: Feed) =>
    Effect.gen(function* () {
      const before = yield* storage.get<Feed>(feedKey(target, stream));
      yield* storage.put({ [feedKey(target, stream)]: feed });
      // The indexes change only when the feed's state does: one write per row otherwise.
      if (before === undefined || before.live !== feed.live) {
        if (!feed.live) yield* storage.put({ [pullingKey(target, stream)]: true });
        else yield* storage.delete([pullingKey(target, stream)]);
      }
      if (before === undefined || starves(before) !== starves(feed)) {
        if (starves(feed)) yield* storage.put({ [starvedKey(target, stream)]: true });
        else yield* storage.delete([starvedKey(target, stream)]);
      }
    });

  /** Buffer deliveries in merge order. Callers hold the exclusive section. */
  const buffer = (target: string, deliveries: ReadonlyArray<Delivery>, live: boolean) =>
    Effect.gen(function* () {
      // Each feed is written once per call, however many of its deliveries arrive.
      const feeds = new Map<string, Feed>();
      for (const delivery of deliveries) {
        const key = orderKey(target, delivery);
        const feed = feeds.get(delivery.source) ??
          (yield* storage.get<Feed>(feedKey(target, delivery.source))) ?? {
            ref: null,
            cursor: 0,
            // Arriving live from a source it never heard of: one with no history for this key.
            live,
            buffered: 0,
          };
        if ((yield* storage.get(key)) !== undefined) {
          // Held live, now read from the log too: it counts.
          if (!live && (yield* storage.get(heldKey(key))) !== undefined) {
            yield* storage.delete([heldKey(key)]);
            feeds.set(delivery.source, { ...feed, buffered: feed.buffered + 1 });
          }
          continue;
        }
        yield* storage.put({ [key]: delivery });
        if (live && feed.ref !== null && !feed.live) {
          // Live from a source this key is still reading: the source went live before
          // the key had the rows before this one (the answer that said so was lost). Held,
          // not counted, so the merge waits for those rows before it applies this.
          yield* storage.put({ [heldKey(key)]: true });
          feeds.set(delivery.source, feed);
          continue;
        }
        feeds.set(delivery.source, { ...feed, buffered: feed.buffered + 1 });
      }
      for (const [stream, feed] of feeds) yield* putFeed(target, stream, feed);
    });

  /**
   * Read a page of the source's log and route it with this key's code. At the
   * end of the log, ask the source to deliver live from there: `caughtUp` either
   * way, since the key has every row the source had.
   */
  const readLog = (target: string, ref: SourceRef, from: number) =>
    Effect.gen(function* () {
      // At first, start where the source's live routing stopped: this key has the rest.
      const read = yield* readAt(net, ref, target, host.key, from, limits.page);
      const rows = read.rows;
      const routed = yield* host.history!(ref, rows);
      const through = routed.length > 0 ? routed[routed.length - 1]!.seq : read.from;
      const deliveries = routed
        .flatMap((row) => row.deliveries)
        .filter((delivery) => delivery.key === host.key);
      if (rows.length >= limits.page)
        return { deliveries, live: false, through, caughtUp: false } satisfies Pulled & {
          readonly caughtUp: boolean;
        };
      const handoff =
        read.handoff ??
        (yield* bounded(net.source.handoff(ref, target, host.key, through)).pipe(
          Effect.catchCause(() => Effect.succeed("stale" as Handoff)),
        ));
      return {
        deliveries,
        live: handoff === "live",
        through,
        // Rows were added meanwhile: read them at once.
        end: handoff === "more",
        caughtUp: handoff !== "more",
      } satisfies Pulled & { readonly caughtUp: boolean };
    });

  /** Pull a page for each feed that starves the merge. */
  const pullStarved = (target: string) =>
    Effect.gen(function* () {
      const starved = yield* storage.list({
        prefix: starvedPrefix(target),
        limit: limits.concurrency * 4,
      });
      const streams = starved.map(([row]) =>
        decodeURIComponent(row.slice(starvedPrefix(target).length)),
      );
      // A page that reached the end of its source is followed at once by the pull
      // that switches the feed to live, so the merge never stops to wait for it.
      const pullFeed = (stream: string): Effect.Effect<boolean> =>
        Effect.gen(function* () {
          const feed = yield* storage.get<Feed>(feedKey(target, stream));
          if (!feed || feed.live || feed.ref === null) return false;
          // Keyed by its source: the key reads the source's log and routes it itself.
          const pulled = yield* readLog(target, feed.ref, feed.cursor).pipe(
            // Refused (still on older code) or lost in transit: pull it again later.
            Effect.catchCause(() => Effect.void),
          );
          if (pulled === undefined) return true;
          yield* storage.exclusive(
            Effect.gen(function* () {
              const current = yield* storage.get<Feed>(feedKey(target, stream));
              if (!current || current.cursor !== feed.cursor) return;
              // Read up to the end of its source's log: its history is here, whether
              // or not the source could switch it to live delivery yet.
              if (
                "caughtUp" in pulled &&
                pulled.caughtUp &&
                !(yield* storage.get(caughtKey(target)))
              ) {
                yield* storage.put({ [caughtKey(target)]: true });
                yield* trace("caught-up", { key: host.key, target });
              }
              // Its only source, and nothing buffered ahead: the page is already in
              // order, so apply it rather than buffer it.
              const direct =
                host.singleSource?.() === true &&
                (yield* storage.list({ prefix: bufferPrefix(target), limit: 1 })).length === 0;
              if (direct) {
                for (const delivery of pulled.deliveries) yield* host.apply([delivery]);
              } else yield* buffer(target, pulled.deliveries, false);
              const after = (yield* storage.get<Feed>(feedKey(target, stream)))!;
              yield* putFeed(target, stream, {
                ...after,
                cursor: Math.max(
                  after.cursor,
                  pulled.through ?? 0,
                  ...pulled.deliveries.map((d) => d.seq),
                ),
                live: pulled.live,
              });
            }),
          );
          if (pulled.end === true && !pulled.live) return yield* pullFeed(stream);
          // A source on code without the target can't deliver live yet: read again later.
          return "caughtUp" in pulled && pulled.caughtUp === true && !pulled.live;
        });
      const failed = yield* Effect.forEach(streams, pullFeed, {
        concurrency: limits.concurrency,
      });
      return failed.some((stale) => stale);
    });

  /**
   * Apply buffered deliveries in merge order while no pulling feed starves the
   * merge. Once ready, with no feed left to pull and nothing buffered, the
   * backfill is done and the key goes back to applying directly.
   */
  const applyBuffered = (target: string) =>
    storage.exclusive(
      Effect.gen(function* () {
        const backfill = yield* storage.get<Backfill>(backfillKey(target));
        if (!backfill) return "done" as const;
        if ((yield* storage.list({ prefix: starvedPrefix(target), limit: 1 })).length > 0)
          return "starved" as const;
        // A page in merge order, each delivery applied on its own (as live, so watchers and
        // downstream consumers see every change), each feed written once. It stops after
        // the delivery that leaves a feed still pulling with nothing buffered.
        const page = yield* storage.list<Delivery>({
          prefix: bufferPrefix(target),
          limit: limits.apply,
        });
        const feeds = new Map<string, Feed>();
        const applied: Array<Delivery> = [];
        let starved = false;
        for (const [, delivery] of page) {
          const feed =
            feeds.get(delivery.source) ??
            (yield* storage.get<Feed>(feedKey(target, delivery.source)))!;
          // A held delivery wasn't counted (see `buffer`).
          const row = orderKey(target, delivery);
          const held = (yield* storage.get(heldKey(row))) !== undefined;
          if (held) yield* storage.delete([heldKey(row)]);
          const next = held ? feed : { ...feed, buffered: feed.buffered - 1 };
          feeds.set(delivery.source, next);
          yield* host.apply([delivery]);
          applied.push(delivery);
          if (starves(next)) {
            starved = true;
            break;
          }
        }
        if (applied.length > 0) {
          yield* storage.delete(page.slice(0, applied.length).map(([row]) => row));
          for (const [stream, feed] of feeds) yield* putFeed(target, stream, feed);
        }
        if (starved) return "starved" as const;
        if (page.length >= limits.apply) return "more" as const;
        if (!backfill.ready) return "waiting" as const;
        if ((yield* storage.list({ prefix: pullingPrefix(target), limit: 1 })).length > 0)
          return "starved" as const;
        // Ready, every feed live and the buffer empty: done, atomically with the last apply.
        for (const prefix of [feedsPrefix(target), starvedPrefix(target), pullingPrefix(target)]) {
          while (true) {
            const rows = yield* storage.list({ prefix, limit: 128 });
            if (rows.length === 0) break;
            yield* storage.delete(rows.map(([key]) => key));
          }
        }
        yield* storage.delete([backfillKey(target), `bf:asked:${T(target)}`, caughtKey(target)]);
        yield* storage.put({ [doneKey(target)]: true });
        return "done" as const;
      }),
    );

  /** Keyed by its source: it has its history (read to the end of its log, or done). */
  const settled = (target: string) =>
    Effect.map(
      Effect.all([storage.get(doneKey(target)), storage.get(caughtKey(target))]),
      ([done, caught]) => done !== undefined || caught !== undefined,
    );

  /**
   * Keyed by its source: read `ref`'s log from the start. Ready at once, since
   * it has no other source to wait for. Callers hold the exclusive section.
   */
  const follow = (target: string, ref: SourceRef) =>
    Effect.gen(function* () {
      const backfill = yield* begin(target);
      if (!backfill.ready)
        yield* storage.put({ [backfillKey(target)]: { ...backfill, ready: true } });
      const stream = `${ref.source}/${ref.id}`;
      const feed = yield* storage.get<Feed>(feedKey(target, stream));
      if (feed === undefined || feed.ref === null)
        yield* putFeed(target, stream, {
          ref,
          cursor: 0,
          live: false,
          buffered: feed?.buffered ?? 0,
        });
    });

  /** The merge job for one target. */
  /** The merge job for one target: `true` when it couldn't go on (a call failed), and waits. */
  const merge = (target: string): Effect.Effect<boolean> =>
    Effect.gen(function* () {
      const backfill = yield* storage.get<Backfill>(backfillKey(target));
      if (!backfill) return false;
      if (!backfill.ready) {
        // A key with history is told it is ready by the scanners that pushed it. One
        // fed only live (no history) has no one to tell it: it asks the run.
        if (backfill.pushed) return false;
        const phase = yield* net.run.phase(target).pipe(Effect.catchCause(() => Effect.void));
        if (phase === undefined)
          return yield* Effect.as(retry.later(jobId(target), RETRY_MS), true);
        yield* trace("waiting", { key: host.key, target, phase });
        if (phase !== "ready" && phase !== "complete")
          return yield* Effect.as(jobs.schedule(jobId(target), limits.pollMillis), false);
        yield* storage.exclusive(
          Effect.gen(function* () {
            const current = yield* storage.get<Backfill>(backfillKey(target));
            if (current) yield* storage.put({ [backfillKey(target)]: { ...current, ready: true } });
          }),
        );
      }
      const outcome = yield* applyBuffered(target);
      yield* trace("merge", { key: host.key, target, outcome });
      if (host.after) yield* host.after;
      if (outcome === "done" || outcome === "waiting")
        return yield* Effect.as(retry.clear(jobId(target)), false);
      // A remote failure never fails the job (which a durable callback would retry
      // with a growing delay, then park): it asks again after a fixed wait.
      const failed = outcome === "starved" ? yield* pullStarved(target) : false;
      if (failed) return yield* Effect.as(retry.later(jobId(target), RETRY_MS), true);
      yield* retry.clear(jobId(target));
      yield* jobs.schedule(jobId(target), 0);
      return false;
    });

  return {
    /**
     * Deliveries for `target` arriving at this key. `true`: apply them now, as
     * usual. `false`: the key is backfilling, and they were buffered.
     */
    admit: (target: string, deliveries: ReadonlyArray<Delivery>) =>
      Effect.gen(function* () {
        const known = yield* storage.exclusive(
          Effect.gen(function* () {
            if (yield* storage.get(doneKey(target))) return "apply" as const;
            if (!(yield* storage.get(backfillKey(target)))) return "unknown" as const;
            yield* buffer(target, deliveries, true);
            yield* jobs.schedule(jobId(target), 0);
            return "buffered" as const;
          }),
        );
        if (known !== "unknown") return known === "apply";
        if (host.singleSource?.() === true) {
          // Keyed by its source: it needs no one to start it. It reads its source's
          // log, and takes these in order with it (a new instance's key reads little).
          // Its source is the instance with its own id.
          const source = deliveries[0]!.origin;
          yield* storage.exclusive(
            Effect.gen(function* () {
              yield* follow(target, { source, id: host.key });
              yield* buffer(target, deliveries, true);
            }),
          );
          yield* jobs.schedule(jobId(target), 0);
          return false;
        }
        // A key's first delivery for this target: is a run still pushing history?
        const phase = yield* net.run.phase(target);
        return yield* storage.exclusive(
          Effect.gen(function* () {
            if (yield* storage.get(doneKey(target))) return true;
            if (phase === "complete" && !(yield* storage.get(backfillKey(target)))) {
              yield* storage.put({ [doneKey(target)]: true });
              return true;
            }
            yield* begin(target);
            yield* buffer(target, deliveries, true);
            yield* jobs.schedule(jobId(target), 0);
            return false;
          }),
        );
      }),

    push: (target: string, deliveries: ReadonlyArray<Delivery>) =>
      Effect.gen(function* () {
        const applied = yield* storage.exclusive(
          Effect.gen(function* () {
            if (target !== host.target()) {
              yield* stale(target);
              // An older generation's run: superseded.
              return false;
            }
            if (yield* storage.get(doneKey(target))) {
              // Its history is in: these are newer (read from a source still on older
              // code), and arrive as live deliveries would. The checkpoints drop repeats.
              yield* host.apply(deliveries.map(({ history: _, ...live }) => live));
              return true;
            }
            const backfill = yield* begin(target);
            if (!backfill.pushed)
              yield* storage.put({ [backfillKey(target)]: { ...backfill, pushed: true } });
            yield* buffer(target, deliveries, true);
            return false;
          }),
        );
        if (applied && host.after) yield* host.after;
      }),

    start: (target: string, ref: SourceRef, waitMillis = 0) =>
      Effect.gen(function* () {
        const started = yield* storage.exclusive(
          Effect.gen(function* () {
            yield* trace("start", { key: host.key, target });
            if (target !== host.target()) {
              yield* stale(target);
              // An older generation's run: superseded, nothing to wait for.
              return "settled" as const;
            }
            if (yield* settled(target)) return "settled" as const;
            yield* follow(target, ref);
            return "pending" as const;
          }),
        );
        if (started === "settled") return started;
        // Worked on here when asked to wait; the job takes over only if it isn't done in time.
        if (waitMillis <= 0) return yield* Effect.as(jobs.schedule(jobId(target), 0), started);
        // Work on it here, rather than wait for an alarm to run the job: read its
        // source's log a page at a time until it has its history, or time is up.
        const until = (yield* Clock.currentTimeMillis) + waitMillis;
        for (let failures = 0; ;) {
          failures = (yield* merge(target)) ? failures + 1 : 0;
          if (yield* settled(target)) return "settled" as const;
          if ((yield* Clock.currentTimeMillis) >= until)
            return yield* Effect.as(jobs.schedule(jobId(target), 0), "pending" as const);
          yield* Effect.sleep(`${yield* pause(failures)} millis`);
        }
      }),

    ready: (target: string, waitMillis = 0) =>
      Effect.gen(function* () {
        const told = yield* storage.exclusive(
          Effect.gen(function* () {
            yield* trace("told-ready", { key: host.key, target });
            if (target !== host.target()) {
              yield* stale(target);
              return "settled" as const;
            }
            if (yield* storage.get(doneKey(target))) return "settled" as const;
            const backfill = yield* begin(target);
            if (!backfill.ready)
              yield* storage.put({ [backfillKey(target)]: { ...backfill, ready: true } });
            return "pending" as const;
          }),
        );
        if (told === "settled") return told;
        yield* jobs.schedule(jobId(target), 0);
        if (waitMillis <= 0) return told;
        // Apply it here, rather than wait for an alarm to run the job.
        const until = (yield* Clock.currentTimeMillis) + waitMillis;
        for (let failures = 0; ;) {
          failures = (yield* merge(target)) ? failures + 1 : 0;
          if (yield* storage.get(doneKey(target))) return "settled" as const;