Skip to content

Commit be46834

Browse files
committed
fix(shared): make keyed drainable worker drain quiescent
Snapshot-only drain missed work offered mid-drain (new keys, recreated lanes, follow-ups after a lane's drain resolved). Loop snapshot+drain until entry/version stabilization without holding the lane lock across waits.
1 parent 4eb57ab commit be46834

2 files changed

Lines changed: 122 additions & 10 deletions

File tree

‎packages/shared/src/DrainableWorker.test.ts‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -93,6 +93,85 @@ describe("makeKeyedDrainableWorker", () => {
9393
),
9494
);
9595

96+
it.live("drains work offered during drain, including new keys and follow-ups", () =>
97+
Effect.scoped(
98+
Effect.gen(function* () {
99+
const processed: string[] = [];
100+
const a1Started = yield* Deferred.make<void>();
101+
const releaseA1 = yield* Deferred.make<void>();
102+
const b1Started = yield* Deferred.make<void>();
103+
const releaseB1 = yield* Deferred.make<void>();
104+
const c1Started = yield* Deferred.make<void>();
105+
const releaseC1 = yield* Deferred.make<void>();
106+
const worker = yield* makeKeyedDrainableWorker(
107+
(item: { readonly key: string; readonly value: string }) => item.key,
108+
(item) =>
109+
Effect.gen(function* () {
110+
if (item.value === "a1") {
111+
yield* Deferred.succeed(a1Started, undefined);
112+
yield* Deferred.await(releaseA1);
113+
}
114+
if (item.value === "b1") {
115+
yield* Deferred.succeed(b1Started, undefined);
116+
yield* Deferred.await(releaseB1);
117+
}
118+
if (item.value === "c1") {
119+
yield* Deferred.succeed(c1Started, undefined);
120+
yield* Deferred.await(releaseC1);
121+
}
122+
processed.push(item.value);
123+
}),
124+
);
125+
126+
yield* worker.enqueue({ key: "a", value: "a1" });
127+
yield* worker.enqueue({ key: "b", value: "b1" });
128+
yield* Deferred.await(a1Started);
129+
yield* Deferred.await(b1Started);
130+
131+
const drained = yield* Deferred.make<void>();
132+
yield* Effect.forkChild(
133+
worker.drain.pipe(
134+
Effect.tap(() => Deferred.succeed(drained, undefined).pipe(Effect.orDie)),
135+
),
136+
);
137+
138+
// Let the forked drain snapshot lanes [a, b]: no other work can be
139+
// enqueued while this fiber only yields, so after ample scheduler
140+
// turns the drain is parked waiting on the blocked a1/b1 lanes.
141+
// (Scheduler turns only — no wall-clock.)
142+
for (let i = 0; i < 50; i++) {
143+
yield* Effect.yieldNow;
144+
}
145+
146+
// Offer a follow-up on existing lane "a" (a1 still blocked, so the
147+
// lane entry is stable and cannot be cleaned up mid-race) plus a
148+
// brand-new blocked key "c" — both strictly after the snapshot.
149+
// A snapshot-only drain never waits on "c", so it settles once
150+
// a/b release while c1 is still pending.
151+
yield* worker.enqueue({ key: "a", value: "a2" });
152+
yield* worker.enqueue({ key: "c", value: "c1" });
153+
yield* Deferred.await(c1Started);
154+
expect(yield* Deferred.isDone(drained)).toBe(false);
155+
156+
// Releasing a/b must not settle the drain while c1 is pending.
157+
yield* Deferred.succeed(releaseA1, undefined);
158+
yield* Deferred.succeed(releaseB1, undefined);
159+
// Give the drain ample scheduler turns to (incorrectly) settle: the
160+
// quiescent drain stays pending regardless of turns taken since c1
161+
// is still blocked.
162+
for (let i = 0; i < 50; i++) {
163+
yield* Effect.yieldNow;
164+
}
165+
expect(processed).not.toContain("c1");
166+
expect(yield* Deferred.isDone(drained)).toBe(false);
167+
168+
yield* Deferred.succeed(releaseC1, undefined);
169+
yield* Deferred.await(drained);
170+
expect(processed.toSorted()).toEqual(["a1", "a2", "b1", "c1"]);
171+
}),
172+
),
173+
);
174+
96175
it.live("creates a single lane under concurrent same-key enqueues", () =>
97176
Effect.scoped(
98177
Effect.gen(function* () {

‎packages/shared/src/DrainableWorker.ts‎

Lines changed: 43 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,9 @@ export interface DrainableWorker<A> {
4040
* across lanes.
4141
*
4242
* Each key gets its own FIFO lane while different keys process concurrently.
43-
* `drain` waits for every lane present when draining starts. Idle lanes are
43+
* `drain` is quiescent: it loops snapshot+drain until no lane holds
44+
* unprocessed work offered during the drain (new keys, recreated lanes, or
45+
* version-bumped lanes). Idle lanes are
4446
* removed once drained so key cardinality stays bounded.
4547
*
4648
* @param keyOf - Derives the lane key for an item.
@@ -111,16 +113,47 @@ export const makeKeyedDrainableWorker = <A, K, E, R>(
111113
}),
112114
);
113115

114-
const drain: DrainableWorker<A>["drain"] = laneLock
115-
.withPermit(Effect.sync(() => Array.from(entries.values())))
116-
.pipe(
117-
Effect.flatMap((lanes) =>
118-
Effect.forEach(lanes, (entry) => entry.worker.drain, {
119-
concurrency: "unbounded",
120-
discard: true,
116+
const drain: DrainableWorker<A>["drain"] = Effect.gen(function* () {
117+
while (true) {
118+
const snapshot = yield* laneLock.withPermit(
119+
Effect.sync(() =>
120+
Array.from(entries.entries()).map(([key, entry]) => ({
121+
key,
122+
entry,
123+
version: entry.version,
124+
})),
125+
),
126+
);
127+
if (snapshot.length === 0) {
128+
return;
129+
}
130+
yield* Effect.forEach(snapshot, ({ entry }) => entry.worker.drain, {
131+
concurrency: "unbounded",
132+
discard: true,
133+
});
134+
const settled = yield* laneLock.withPermit(
135+
Effect.sync(() => {
136+
const seen = new Map<K, { readonly entry: Entry; readonly version: number }>();
137+
for (const { key, entry, version } of snapshot) {
138+
seen.set(key, { entry, version });
139+
}
140+
for (const [key, current] of entries) {
141+
const prior = seen.get(key);
142+
if (prior === undefined) {
143+
return false;
144+
}
145+
if (current !== prior.entry || current.version !== prior.version) {
146+
return false;
147+
}
148+
}
149+
return true;
121150
}),
122-
),
123-
);
151+
);
152+
if (settled) {
153+
return;
154+
}
155+
}
156+
});
124157

125158
return { enqueue, drain } satisfies DrainableWorker<A>;
126159
});

0 commit comments

Comments
 (0)