import * as Backfill from "@alchemy.run/domain/Backfill";
import type { Routed } from "@alchemy.run/domain/CatchUp";
import type { Delivery } from "@alchemy.run/domain/Platform";
import * as Effect from "effect/Effect";
import * as Semaphore from "effect/Semaphore";
/**
* A deterministic simulation of the backfill protocol: every role runs its
* real code over in-process storage, jobs and network, driven by a seeded
* scheduler that injects failures, crashes and stale code.
*/
/** A seeded PRNG (mulberry32): the same seed explores the same interleaving. */
const rng = (seed: number) => {
let a = seed >>> 0;
return () => {
a = (a + 0x6d2b79f5) >>> 0;
let t = a;
t = Math.imul(t ^ (t >>> 15), t | 1);
t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
};
class Crash extends Error {
override readonly name = "Crash";
}
export interface Faults {
/** Chance a call fails before it reaches its object. */
readonly callBefore: number;
/** Chance a call runs but its answer is lost. */
readonly callAfter: number;
/** Chance an exclusive section crashes before it commits (its writes roll back). */
readonly crash: number;
}
export const noFaults: Faults = { callBefore: 0, callAfter: 0, crash: 0 };
/** What one object did: Durable Object requests (calls in, and alarms), and rows read and written. */
export interface Stats {
requests: number;
rowsRead: number;
rowsWritten: number;
}
/** One durable object: sorted storage, an exclusive lock, and its scheduled jobs. */
class SimObject {
readonly data = new Map<string, unknown>();
overlay: Map<string, unknown> | undefined;
/** Pending jobs by id: when due, and a version so a replaced job's queue entry is skipped. */
readonly jobs = new Map<string, { readonly due: number; readonly version: number }>();
readonly stats: Stats = { requests: 0, rowsRead: 0, rowsWritten: 0 };
/** Requests by call or job, to see what makes an object hot. */
readonly methods = new Map<string, number>();
/**
* In the wall-time model: the milliseconds this object spends running events,
* one at a time. An event runs in the first free one at or after it arrives;
* awaiting its own outgoing calls doesn't keep the object busy.
*/
busy = new Set<number>();
/** Run an event that arrives at `at`: when it ends. */
occupy(at: number, service: number) {
let slot = Math.ceil(at);
while (this.busy.has(slot)) slot++;
this.busy.add(slot);
return slot + service;
}
private sorted: Array<string> = [];
private dirty = false;
constructor(
readonly address: string,
readonly sim: Sim,
/** Runs a job of this object by id. */
readonly run: (id: string) => Effect.Effect<void>,
) {}
private read(key: string) {
if (this.overlay?.has(key)) return this.overlay.get(key);
return this.data.get(key);
}
private write(key: string, value: unknown) {
// A delete leaves the key in the sorted list, skipped when read: only new keys re-sort.
if (value === undefined) this.data.delete(key);
else {
if (!this.data.has(key)) this.dirty = true;
this.data.set(key, value);
}
}
/** The first index in the sorted keys at or after `key`. */
private seek(key: string) {
if (this.dirty) {
this.sorted = [...this.data.keys()].sort();
this.dirty = false;
}
let lo = 0;
let hi = this.sorted.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (this.sorted[mid]! < key) lo = mid + 1;
else hi = mid;
}
return lo;
}
readonly storage: Backfill.Storage = {
get: <A>(key: string) =>
Effect.sync(() => {
this.stats.rowsRead += 1;
return this.read(key) as A | undefined;
}),
put: (entries) =>
Effect.sync(() => {
for (const [key, value] of Object.entries(entries)) {
this.stats.rowsWritten += 1;
if (this.overlay) this.overlay.set(key, value);
else this.write(key, value);
}
}),
delete: (keys) =>
Effect.sync(() => {
for (const key of keys) {
this.stats.rowsWritten += 1;
if (this.overlay) this.overlay.set(key, undefined);
else this.write(key, undefined);
}
}),
list: <A>(options: { prefix: string; startAfter?: string; limit?: number }) =>
Effect.sync(() => {
const after = options.startAfter;
const inRange = (key: string) =>
key.startsWith(options.prefix) && (after === undefined || key > after);
// Stored keys from the first in range, merged with the open section's new keys.
const stored: Array<string> = [];
const limit = options.limit ?? Number.POSITIVE_INFINITY;
for (
let i = this.seek(after !== undefined && after > options.prefix ? after : options.prefix);
i < this.sorted.length;
i++
) {
const key = this.sorted[i]!;
if (!key.startsWith(options.prefix)) break;
if (!inRange(key) || !this.data.has(key)) continue;
stored.push(key);
if (stored.length >= limit + (this.overlay?.size ?? 0)) break;
}
const added = [...(this.overlay?.keys() ?? [])].filter(
(key) => inRange(key) && !this.data.has(key),
);
const keys = added.length > 0 ? [...stored, ...added].sort() : stored;
const out: Array<readonly [string, A]> = [];
for (const key of keys) {
const value = this.read(key);
if (value === undefined) continue;
out.push([key, value as A]);
if (out.length >= limit) break;
}
this.stats.rowsRead += Math.max(1, out.length);
return out;
}),
exclusive: <A, E>(effect: Effect.Effect<A, E>) => this.section(effect, true),
};
private readonly lock = Semaphore.makeUnsafe(1);
/**
* One exclusive section: its writes commit together, or, when it crashes
* before committing, not at all. Client commits pass `crashes: false`.
*/
section<A, E>(effect: Effect.Effect<A, E>, crashes: boolean): Effect.Effect<A, E> {
return this.lock.withPermits(1)(
Effect.suspend(() => {
this.overlay = new Map();
return effect.pipe(
Effect.tap(() =>
crashes && this.sim.chance(this.sim.faults.crash)
? Effect.die(new Crash(`${this.address} crashed before committing`))
: Effect.void,
),
Effect.tap(() =>
Effect.sync(() => {
for (const [key, value] of this.overlay!) this.write(key, value);
}),
),
Effect.ensuring(
Effect.sync(() => {
this.overlay = undefined;
}),
),
);
}),
);
}
readonly jobsApi: Backfill.Jobs = {
schedule: (id, afterMillis) => Effect.sync(() => this.sim.schedule(this, id, afterMillis)),
};
}
/** A simulated source instance: an event log with routing, like an aggregate. */
interface SourceData {
readonly ref: Backfill.SourceRef;
readonly object: SimObject;
readonly events: Array<{
readonly seq: number;
readonly at: number;
readonly keys: ReadonlyArray<string>;
}>;
/** Runs code that knows the target only from this time on. */
staleUntil: number;
role: Backfill.Source;
}
/** A simulated consumer key: applies deliveries, deduping by source seq, like a view key. */
interface KeyData {
readonly key: string;
readonly object: SimObject;
readonly applied: Array<{ readonly delivery: Delivery; readonly backfilling: boolean }>;
readonly checkpoints: Map<string, number>;
/** Runs code from before the target's generation until this time. */
staleUntil: number;
role: Backfill.Consumer;
}
export class Sim {
readonly random: () => number;
now = 1_000_000;
readonly nodes = new Map<string, { object: SimObject; role: Backfill.Node }>();
readonly sources = new Map<string, SourceData>();
readonly keys = new Map<string, KeyData>();
/** Live deliveries waiting to be sent, in order per source (its outbox): retried until they land. */
readonly outbox = new Map<string, Array<Delivery>>();
/** Every consumer deployed together. */
get targets(): ReadonlyArray<string> {
return [this.target, ...this.others];
}
/** A key of `target`: the primary target's keys are plain, the others' are prefixed. */
keyOf(target: string, key: string) {
return target === this.target ? key : `${target}|${key}`;
}
/** The target a key belongs to. */
targetOfKey(key: string) {
const bar = key.indexOf("|");
return bar < 0 ? this.target : key.slice(0, bar);
}
/** Run something just before a run lists `path`: work that lands while it lists the directory. */
interject: ((path: string) => Effect.Effect<void>) | undefined = undefined;
/**
* The consumer is keyed by its source: each key hears only from the instance
* with its own id (commit each instance's events to a key named after it).
*/
singleSource = false;
/** The sources each consumer reads; unset, the root sweeps every subtree. */
sourcesOf: ((target: string) => ReadonlyArray<string> | undefined) | undefined = undefined;
/** What the deployed code knows of a consumer. */
planOf(target: string): Backfill.Plan {
const sources = this.sourcesOf?.(target);
return { ...(sources === undefined ? {} : { sources }), singleSource: this.singleSource };
}
/** Every plan, as a deploy announces them. */
plans(targets: ReadonlyArray<string> = this.targets) {
return Object.fromEntries(targets.map((target) => [target, this.planOf(target)]));
}
/** Whether instances of `source` feed `target`. */
feeds(source: string, target: string) {
return this.sourcesOf?.(target)?.includes(source) ?? true;
}
/** The target exists (the consumer is deployed). */
deployed = false;
calls = 0;
failures = 0;
constructor(
seed: number,
readonly target: string,
readonly faults: Faults = noFaults,
readonly limits: Backfill.Limits = {
...Backfill.defaultLimits,
page: 3,
nodePage: 2,
apply: 4,
leafSize: 3,
// Few, shallow leaves: they fill and split all the time.
depth: 1,
},
/** More consumers deployed at the same time: they share the directory and the sources. */
readonly others: ReadonlyArray<string> = [],
) {
this.random = rng(seed);
}
chance(p: number) {
return p > 0 && this.random() < p;
}
/**
* A Durable Object keeps the code it started with while calls keep it busy:
* a call to one still on older code holds it there for another 20 seconds.
*/
busy<O extends { staleUntil: number }>(object: O): O {
if (this.now < object.staleUntil)
object.staleUntil = Math.max(object.staleUntil, this.now + 20_000);
return object;
}
/**
* Latencies of the wall-time model, in milliseconds: a call's round trip, the
* time an object spends on one event, and how long an alarm takes to fire.
*/
latency = { rpc: 10, service: 1, alarm: 50 };
/**
* Run work due at the same time in wall-time order, as a real system would,
* rather than in a random order (which explores interleavings, but makes a
* busy object's queue hold work that started later).
*/
timed = false;
/** In the wall-time model: the time of the work running now, and the latest time anything ended. */
vt = 0;
makespan = 0;
/** In the wall-time model: when the root marked the target's history complete. */
completedAt: number | undefined = undefined;
/**
* Every call crosses the network: it may fail before it runs, or after. In the
* wall-time model it waits for its object to be free, which is how a hot
* object's queue shows up.
*/
private call<A>(
target: SimObject,
effect: () => Effect.Effect<A>,
method = "call",
): Effect.Effect<A> {
return Effect.suspend(() => {
this.calls += 1;
target.stats.requests += 1;
target.methods.set(method, (target.methods.get(method) ?? 0) + 1);
if (this.chance(this.faults.callBefore)) {
this.failures += 1;
return Effect.die(new Crash("call failed in transit"));
}
const caller = this.vt;
this.vt = target.occupy(caller + this.latency.rpc / 2, this.latency.service);
return effect().pipe(
Effect.tap(() =>
Effect.sync(() => {
this.vt += this.latency.rpc / 2;
this.makespan = Math.max(this.makespan, this.vt);
}),
),
Effect.tap(() => {
if (!this.chance(this.faults.callAfter)) return Effect.void;
this.failures += 1;
return Effect.die(new Crash("answer lost in transit"));
}),
);
});
}
// ------------------------------------------------------------ scheduler
/** Due jobs and sends, as a binary heap by time (ties in random order). */
private readonly queue: Array<{
readonly due: number;
readonly tie: number;
readonly vt: number;
readonly run: () => Effect.Effect<void>;
}> = [];
private versions = 0;
private push(entry: (typeof this.queue)[number]) {
const q = this.queue;
q.push(entry);
let i = q.length - 1;
while (i > 0) {
const parent = (i - 1) >> 1;
if (this.before(q[parent]!, q[i]!)) break;
[q[parent], q[i]] = [q[i]!, q[parent]!];
i = parent;
}
}
private before(a: (typeof this.queue)[number], b: (typeof this.queue)[number]) {
if (a.due !== b.due) return a.due < b.due;
if (this.timed && a.vt !== b.vt) return a.vt < b.vt;
return a.tie <= b.tie;
}
private pop() {
const q = this.queue;
const top = q[0];
const last = q.pop()!;
if (q.length > 0) {
q[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1;
const r = l + 1;
let m = i;
if (l < q.length && !this.before(q[m]!, q[l]!)) m = l;
if (r < q.length && !this.before(q[m]!, q[r]!)) m = r;
if (m === i) break;
[q[m], q[i]] = [q[i]!, q[m]!];
i = m;
}
}
return top;
}
/** Schedule a job on an object; a job with the same id replaces a pending one. */
schedule(object: SimObject, id: string, afterMillis: number) {
// The earliest request wins: a job already due sooner isn't postponed.
const pending = object.jobs.get(id);
if (pending !== undefined && pending.due <= this.now + afterMillis) return;
const version = ++this.versions;
object.jobs.set(id, { due: this.now + afterMillis, version });
const vt = this.vt + afterMillis + this.latency.alarm;
this.push({
due: this.now + afterMillis,
tie: this.random(),
vt,
run: () =>
Effect.suspend(() => {
if (object.jobs.get(id)?.version !== version) return Effect.void;
object.jobs.delete(id);
object.stats.requests += 1;
const job = `job:${id.split(":")[0]}`;
object.methods.set(job, (object.methods.get(job) ?? 0) + 1);
this.vt = object.occupy(vt, this.latency.service);
return object.run(id).pipe(
// A failed job is retried, like a durable callback.
Effect.catchCause(() =>
Effect.sync(() => {
if (!object.jobs.has(id)) this.schedule(object, id, 1_000);
}),
),
Effect.ensuring(
Effect.sync(() => {
this.makespan = Math.max(this.makespan, this.vt);
}),
),
);
}),
});
}
/** Queue the next send of a source's outbox, unless one is queued already. */
private sending = new Set<string>();
private queueSend(stream: string) {
if (this.sending.has(stream)) return;
this.sending.add(stream);
const vt = this.vt;
this.push({
due: this.now,
tie: this.random(),
vt,
run: () =>
Effect.suspend(() => {
this.sending.delete(stream);
const queue = this.outbox.get(stream) ?? [];
if (queue.length === 0) return Effect.void;
this.vt = vt;
return this.sendOne(queue[0]!).pipe(
Effect.tap(() => Effect.sync(() => queue.shift())),
// A failed send stays at the head.
Effect.catchCause(() => Effect.void),
Effect.ensuring(
Effect.sync(() => {
if (queue.length > 0) this.queueSend(stream);
}),
),
);
}),
});
}
readonly net: Backfill.Network = {
node: {
register: (path, ref) =>
this.call(
this.node(path).object,
() => this.node(path).role.register(path, ref),
"register",
),
child: (path, child) =>
this.call(this.node(path).object, () => this.node(path).role.child(path, child), "child"),
list: (path, after) =>
Effect.andThen(this.interject?.(path) ?? Effect.void, () =>
this.call(this.node(path).object, () => this.node(path).role.list(path, after), "list"),
),
},
source: {
read: (ref, target, key, after, limit) =>
this.call(
this.source(ref).object,
() => this.busy(this.source(ref)).role.read(target, key, after, limit),
"read",
),
cursor: (ref, target) =>
this.call(
this.source(ref).object,
() => this.busy(this.source(ref)).role.cursor(target),
"cursor",
),
log: (ref, after, limit) =>
this.call(
this.source(ref).object,
() => this.busy(this.source(ref)).role.log(after, limit),
"log",
),
handoff: (ref, target, key, through) =>
this.call(
this.source(ref).object,
() => this.busy(this.source(ref)).role.handoff(target, key, through),
"handoff",
),
},
consumer: {
push: (target, key, deliveries) =>
this.call(
this.key(key).object,
() => this.busy(this.key(key)).role.push(target, deliveries),
"push",
),
ready: (target, key, waitMillis) =>
this.call(
this.key(key).object,
() => this.busy(this.key(key)).role.ready(target, waitMillis),
"ready",
),
start: (target, key, ref, waitMillis) =>
this.call(
this.key(key).object,
() => this.busy(this.key(key)).role.start(target, ref, waitMillis),
"start",
),
},
scanner: {
scan: (target, ref, waitMillis) =>
this.call(
this.scanner(target, ref).object,
() => this.scanner(target, ref).role.scan(target, ref, waitMillis),
"scan",
),
ready: (target, ref, waitMillis) =>
this.call(
this.scanner(target, ref).object,
() => this.scanner(target, ref).role.ready(target, waitMillis),
"scanner-ready",
),
kick: (target, ref) =>
this.call(
this.scanner(target, ref).object,
() => this.scanner(target, ref).role.kick(target, ref),
"kick",
),
},
relay: {
run: (name, run, items) =>
this.call(this.relay(name), () => this.relays.run(name, run, items), "relay"),
},
run: {
begin: (target, plan) =>
this.call(
this.run_(target).object,
() => this.run_(target).role.begin(target, plan),
"begin",
),
phase: (target) =>
this.call(this.run_(target).object, () => this.run_(target).role.phase(target), "phase"),
progress: (target) =>
this.call(
this.run_(target).object,
() => this.run_(target).role.progress(target),
"progress",
),
},
};
/** The relays of runs: stateless, one object each. */
readonly relayObjects = new Map<string, SimObject>();
private readonly relays = Backfill.makeRelay(this.net);
relay(name: string) {
let object = this.relayObjects.get(name);
if (!object) {
object = new SimObject(`relay:${name}`, this, () => Effect.void);
this.relayObjects.set(name, object);
}
return object;
}
/** Each source instance's scanner, per target: an object of the consumer's class. */
readonly scanners = new Map<string, { object: SimObject; role: Backfill.Scanner }>();
scanner(target: string, ref: Backfill.SourceRef) {
const name = `${target}|${ref.source}/${ref.id}`;
let found = this.scanners.get(name);
if (!found) {
const object = new SimObject(`scanner:${name}`, this, (id) =>
this.scanners.get(name)!.role.run(id),
);
found = {
object,
role: Backfill.makeScanner(
object.storage,
object.jobsApi,
this.net,
{
// The consumer's own code routes the rows it reads from a source's log.
route: (target, ref, rows) =>
Effect.sync(() =>
(rows as SourceData["events"]).map((event) => ({
seq: event.seq,
deliveries: this.deliveries(this.source(ref), event, true, target),
})),
),
},
this.limits,
),
};
this.scanners.set(name, found);
}
return found;
}
/**
* Each consumer's run root. Like the deploy's Workflow, it makes one pass at a
* time (each one try at everything), again a second later until done.
*/
readonly runs = new Map<string, { object: SimObject; role: Backfill.Run }>();
run_(target: string) {
let found = this.runs.get(target);
if (!found) {
const object = new SimObject(`run:${target}`, this, (id) =>
this.runs.get(target)!.role.run(id),
);
found = {
object,
role: Backfill.makeRun(object.storage, object.jobsApi, this.net, {
waitMillis: 0,
againMillis: 1_000,
}),
};
this.runs.set(target, found);
}
return found;
}
/** The targets whose run is complete. */
completed() {
return this.targets.filter(
(target) =>
(
this.runs.get(target)?.object.data.get(`run:${encodeURIComponent(target)}`) as
| { phase: string }
| undefined
)?.phase === "complete",
);
}
node(path: string) {
let node = this.nodes.get(path);
if (!node) {
const object = new SimObject(`node:${path}`, this, (id) => this.node(path).role.run(id));
node = {
object,
role: Backfill.makeNode(object.storage, object.jobsApi, this.net, this.limits),
};
this.nodes.set(path, node);
}
return node;
}
private streamOf(ref: Backfill.SourceRef) {
return `${ref.source}/${ref.id}`;
}
/** An event's deliveries to one target (or every target). */
private deliveries(
source: SourceData,
event: SourceData["events"][number],
history = false,
only?: string,
): Array<Delivery> {
const stream = this.streamOf(source.ref);
return this.targets
.filter((target) => only === undefined || target === only)
.flatMap((target) => {
const [, rest] = target.split(":") as [string, string];
const [name, generation] = rest.split("#") as [string, string | undefined];
return event.keys.map((key) => ({
target: {
kind: "view" as const,
name,
...(generation ? { generation: Number(generation) } : {}),
},
key: this.keyOf(target, key),
source: stream,
seq: event.seq,
origin: source.ref.source,
tag: "E",
event: { _tag: "E", seq: event.seq },
envelope: { id: source.ref.id, stream, seq: event.seq, at: event.at, commandId: "" },
...(history ? { history } : {}),
}));
});
}
source(ref: Backfill.SourceRef): SourceData {
const id = this.streamOf(ref);
let source = this.sources.get(id);
if (!source) {
const object = new SimObject(`source:${id}`, this, () => this.sources.get(id)!.role.flush);
const data: SourceData = {
ref,
object,
events: [],
staleUntil: 0,
role: undefined as never,
};
const knows = () => this.deployed && this.now >= data.staleUntil;
data.role = Backfill.makeSource(
object.storage,
object.jobsApi,
this.net,
{
ref,
model: () => (knows() ? this.targets : []),
singleSource: () => this.singleSource,
log: (after, limit) =>
Effect.sync(() => data.events.filter((event) => event.seq > after).slice(0, limit)),
version: Effect.sync(() => data.events.length),
// Kept in the object's storage, so a crashed step rolls it back with the rest.
routed: object.storage.get<Routed>("routed"),
markLive: (target) =>
Effect.flatMap(object.storage.get<Routed>("routed"), (routed) =>
object.storage.put({ routed: { ...routed, [target]: data.events.length } }),
),
},
this.limits,
);
source = data;
this.sources.set(id, source);
}
return source;
}
key(key: string): KeyData {
let data = this.keys.get(key);
if (!data) {
const object = new SimObject(`key:${key}`, this, (id) =>
this.keys.get(key)!.role.merge(id.slice("bf-merge:".length)),
);
const keyData: KeyData = {
key,
object,
applied: [],
checkpoints: new Map(),
staleUntil: this.keyStaleUntil(key),
role: undefined as never,
};
keyData.role = Backfill.makeConsumer(
object.storage,
object.jobsApi,
this.net,
{
key,
// Older code runs the previous generation of the consumer.
target: () => {
const target = this.targetOfKey(key);
return this.now >= keyData.staleUntil ? target : target.replace(/#\d+$/, "");
},
singleSource: () => this.singleSource,
// The key's own code routes the rows it reads from its source's log.
history: (ref, rows) =>
Effect.sync(() =>
(rows as SourceData["events"]).map((event) => ({
seq: event.seq,
deliveries: this.deliveries(this.source(ref), event, true, this.targetOfKey(key)),
})),
),
apply: (deliveries) => Effect.sync(() => this.apply(keyData, deliveries, true)),
},
this.limits,
);
data = keyData;
this.keys.set(key, data);
}
return data;
}
private apply(key: KeyData, deliveries: ReadonlyArray<Delivery>, backfilling: boolean) {
for (const delivery of deliveries) {
if ((key.checkpoints.get(delivery.source) ?? 0) >= delivery.seq) continue;
key.checkpoints.set(delivery.source, delivery.seq);
key.applied.push({ delivery, backfilling });
}
}
/**
* Commit an event on a source, as an aggregate does: decide routing under its
* lock, then send what goes out live. The first commit lists it in the directory.
*/
commit(sourceId: string, keys: ReadonlyArray<string>, staleUntil = 0) {
const [name, id] = sourceId.split("/") as [string, string];
const source = this.source({ source: name, id });
if (source.events.length === 0) source.staleUntil = staleUntil;
this.busy(source);
const knows = this.deployed && this.now >= source.staleUntil;
// The first commit lists the instance in the directory before it persists.
const register =
source.events.length === 0
? this.retry(
this.net.node.register(Backfill.leafOf(source.ref, this.limits.depth), source.ref),
)
: Effect.void;
return register.pipe(
Effect.andThen(
source.object
.section(
Effect.gen({ self: this }, function* () {
const before = source.events.length;
const event = { seq: before + 1, at: this.now, keys };
source.events.push(event);
const storage = source.object.storage;
const routed = yield* storage.get<Routed>("routed");
if (!knows) {
// Code without the targets: it routes nothing to them, and its cursors stay.
yield* storage.put({ routed: { ...routed } });
return [] as ReadonlyArray<Delivery>;
}
let next: Record<string, number> = {
...(routed ?? Object.fromEntries(this.targets.map((t) => [t, before]))),
};
const send: Array<Delivery> = [];
for (const target of this.targets) {
const deliveries = this.deliveries(source, event, false, target);
if ((next[target] ?? 0) === before) {
next = { ...next, [target]: before + 1 };
send.push(...deliveries);
} else {
// Behind here: withheld, for its reader to read from the log.
yield* source.role.onCommit(target);
}
}
yield* storage.put({ routed: next });
return send as ReadonlyArray<Delivery>;
}),
// A client's command: it is retried by the client, never lost halfway.
false,
)
.pipe(
Effect.tap((send) =>
Effect.sync(() => {
for (const delivery of send) {
const queue = this.outbox.get(delivery.source) ?? [];
queue.push(delivery);
this.outbox.set(delivery.source, queue);
this.queueSend(delivery.source);
}
}),
),
),
),
);
}
/** Retry a call until it lands (a durable outbox would). */
retry<A>(effect: Effect.Effect<A>): Effect.Effect<A> {
return Effect.suspend(function loop(): Effect.Effect<A> {
return effect.pipe(Effect.catchCause(() => Effect.suspend(loop)));
});
}
/** Keys that run older code for a while: by key, until when. */
readonly staleKeys = new Map<string, number>();
private keyStaleUntil(key: string) {
return this.staleKeys.get(key) ?? 0;
}
/** Deliver one queued live delivery. */
private sendOne(delivery: Delivery) {
const key = this.key(delivery.key);
key.object.stats.requests += 1;
this.vt = key.object.occupy(this.vt + this.latency.rpc / 2, this.latency.service);
// Older code refuses a newer generation's delivery (its apply dies); the sender retries.
if (this.now < this.busy(key).staleUntil)
return Effect.die(new Crash("key still on older code"));
return key.role.admit(this.targetOfKey(delivery.key), [delivery]).pipe(
Effect.flatMap((apply) =>
apply
? key.object.storage.exclusive(Effect.sync(() => this.apply(key, [delivery], false)))
: Effect.void,
),
Effect.ensuring(
Effect.sync(() => {
this.makespan = Math.max(this.makespan, this.vt);
}),
),
);
}
/** Run the next due job or send (ties in random order), or move the clock to it. `false` when idle. */
step(): Effect.Effect<boolean> {
return Effect.suspend(() => {
const head = this.queue[0];
if (head === undefined) return Effect.succeed(false);
if (head.due > this.now) {
this.now = head.due;
return Effect.succeed(true);
}
return this.pop()!.run().pipe(Effect.as(true));
});
}
/** Requests, rows read and rows written, by kind of object and in total. */
totals() {
const sum = (objects: Iterable<SimObject>) => {
const total: Stats = { requests: 0, rowsRead: 0, rowsWritten: 0 };
let hottest = 0;
for (const object of objects) {
total.requests += object.stats.requests;
total.rowsRead += object.stats.rowsRead;
total.rowsWritten += object.stats.rowsWritten;
hottest = Math.max(hottest, object.stats.requests);
}
return { ...total, hottest };
};
const nodes = sum([...this.nodes.values()].map((n) => n.object));
const sources = sum([...this.sources.values()].map((n) => n.object));
const keys = sum([...this.keys.values()].map((n) => n.object));
return {
nodes,
sources,
keys,
total: {
requests: nodes.requests + sources.requests + keys.requests,
rowsRead: nodes.rowsRead + sources.rowsRead + keys.rowsRead,
rowsWritten: nodes.rowsWritten + sources.rowsWritten + keys.rowsWritten,
},
directory: {
nodes: this.nodes.size,
// Hash digits below a source's subtree root (`A:3f` is 2 deep).
depth: Math.max(
0,
...[...this.nodes.keys()].map((path) => path.slice(path.indexOf(":") + 1).length),
),
},
};
}
/** Reset every counter and the wall-time model (after seeding, before the deploy). */
resetMeasures() {
for (const object of [
...[...this.nodes.values()].map((n) => n.object),
...[...this.sources.values()].map((n) => n.object),
...[...this.keys.values()].map((n) => n.object),
]) {
object.stats.requests = 0;
object.stats.rowsRead = 0;
object.stats.rowsWritten = 0;
object.methods.clear();
object.busy.clear();
}
this.vt = 0;
this.makespan = 0;
this.completedAt = undefined;
}
/**
* Deploy the consumer: code that knows it, and the news of it. Instances
* running at the time keep their older code until they have been idle.
*/
deploy(options: { readonly running?: boolean } = {}) {
this.deployed = true;
if (options.running)
for (const source of this.sources.values())
source.staleUntil = Math.max(source.staleUntil, this.now + 20_000);
return Effect.forEach(
this.targets,
(target) => this.retry(this.net.run.begin(target, this.planOf(target))),
{ discard: true },
);
}
/** Run until nothing is left to do, interleaving `actions` (client commits). */
run(
actions: Array<() => Effect.Effect<unknown>> = [],
options: { readonly maxSteps?: number } = {},
) {
return Effect.gen({ self: this }, function* () {
const pending = [...actions];
for (let steps = 0; steps < (options.maxSteps ?? 200_000); steps++) {
if (pending.length > 0 && this.random() < 0.2) {
this.now += 1;
yield* pending.shift()!();
continue;
}
const busy = yield* this.step();
if (this.completedAt === undefined && this.completed().includes(this.target))
this.completedAt = this.vt;
if (!busy && pending.length === 0) return steps;
if (!busy) {
this.now += 1;
yield* pending.shift()!();
}
}
return yield* Effect.die(new Error("the simulation did not settle"));
});
}
/** Which targets' runs are complete. */
status() {
return Effect.sync(() => ({ complete: this.completed() }));
}
}