Skip to content

Commit 3a4da83

Browse files
author
Larry
committed
Drop covered read marks as retention admits them
Refilling a nearly full read-state budget with marks that a kept channel mark already covers used to admit one mark, rescan every kept mark to find it covered, free it, and repeat. A 480-mark peer merge against 1,115 kept catch-up marks made about 537,000 coverage calls. Now a mark whose cover is already kept is dropped as it comes up, without taking space. A full prune pass runs only to catch covers admitted after the marks they cover. The same merge now makes about 2,700 calls. The kept marks and recency are unchanged. Signed-off-by: Larry <627498bd4bd1f281a16431e3c6cce3b5c25b6692798c78672298aefbf2f8f8b5@buzz.block.builderlab.xyz>
1 parent c403d87 commit 3a4da83

2 files changed

Lines changed: 86 additions & 30 deletions

File tree

‎src/features/relay/read-state-retention.test.ts‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -401,3 +401,44 @@ it("retains every protected inherited floor at the exact serialized reserve cap"
401401
);
402402
expect(kept.reserve).toEqual(reserve);
403403
});
404+
it("refilling a full budget with covered marks scans each mark a bounded number of times", () => {
405+
// Carl's shape: thread catch-up marks nearly fill the budget, and a merge
406+
// brings many message marks that the kept channel mark already covers.
407+
const hex = (prefix: string, n: number) =>
408+
`${prefix}${n.toString(16).padStart(64, "0")}`;
409+
// 1,115 of these leave room for one more message mark at the local limit.
410+
const activity = Array.from({ length: 1115 }, (_, n) =>
411+
hex("thread-activity:", n),
412+
);
413+
const messages = Array.from({ length: 480 }, (_, n) => hex("msg:", n));
414+
const state = {
415+
frontiers: {
416+
room: 1000,
417+
...Object.fromEntries(activity.map((key, n) => [key, 2000 + n])),
418+
...Object.fromEntries(messages.map((key, n) => [key, 100 + n])),
419+
},
420+
overrides: {},
421+
};
422+
let calls = 0;
423+
const covered = (
424+
key: string,
425+
frontier: (key: string) => number | undefined,
426+
) => {
427+
calls++;
428+
return key.startsWith("msg:") &&
429+
(frontier("room") ?? -1) >= (frontier(key) ?? 0)
430+
? "room"
431+
: undefined;
432+
};
433+
// The catch-up marks are local; the message marks arrive from a peer.
434+
const recent = Object.fromEntries(activity.map((key, n) => [key, 5000 + n]));
435+
const kept = retainRead([state], recent, "fixture", undefined, covered);
436+
const marks = Object.keys(state.frontiers).length;
437+
expect(calls).toBeLessThan(4 * marks);
438+
expect(kept.state.frontiers.room).toBe(1000);
439+
for (const key of messages) expect(kept.state.frontiers[key]).toBeUndefined();
440+
// The freed space went to the catch-up marks.
441+
expect(
442+
activity.filter((key) => kept.state.frontiers[key] !== undefined).length,
443+
).toBeGreaterThan(1000);
444+
});

‎src/features/relay/read-state-retention.ts‎

Lines changed: 45 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -119,61 +119,76 @@ export function retainRead(
119119
(a, b) => scope(a[0]) - scope(b[0]) || byUse(a, b),
120120
);
121121
const byRecent = [...frontiers].sort(byUse);
122-
const dropped = new Set<string>();
122+
// A dropped mark and the kept mark that covered it when it was dropped.
123+
const dropped = new Map<string, string>();
124+
const keptCover = (key: string, value: number) => {
125+
const cover = coveredBy?.(key, (other) =>
126+
other === key ? value : retained.get(other),
127+
);
128+
return cover !== undefined && cover !== key && retained.has(cover)
129+
? cover
130+
: undefined;
131+
};
132+
// A mark that a kept mark already covers is dropped as it comes up, without
133+
// taking space, so refilling never admits and then frees the same slot.
134+
const admit = (key: string, value: number, share = 1) => {
135+
const cover = keptCover(key, value);
136+
if (cover !== undefined) {
137+
dropped.set(key, cover);
138+
return true;
139+
}
140+
if (!take(frontierKey(key), value, share)) return false;
141+
retained.set(key, value);
142+
return true;
143+
};
123144
const select = () => {
124145
for (const [key, value] of scoped) {
125146
if (retained.has(key) || dropped.has(key)) continue;
126147
// Stop at the first broad mark that does not fit, so a narrower mark
127148
// never takes the share ahead of it.
128-
if (!take(frontierKey(key), value, SCOPED_SHARE)) break;
129-
retained.set(key, value);
149+
if (!admit(key, value, SCOPED_SHARE)) break;
130150
}
131151
for (const [key, value] of byRecent)
132-
if (
133-
!retained.has(key) &&
134-
!dropped.has(key) &&
135-
take(frontierKey(key), value)
136-
)
137-
retained.set(key, value);
152+
if (!retained.has(key) && !dropped.has(key)) admit(key, value);
138153
};
139154
select();
140-
// Refilling can keep more covered marks, so repeat until nothing drops.
155+
// A cover admitted after the marks it covers frees them here. Only then can
156+
// refilling keep more, so repeat until nothing drops.
141157
let pruned = true;
142158
while (coveredBy && pruned) {
143159
pruned = false;
144160
// Prune against the kept marks only: a cover that did not fit cannot
145161
// replace anything. Decide on one snapshot so a cover is never pruned
146162
// after it has already replaced another mark.
147-
const kept = new Map(retained);
148163
const covers = new Map<string, string>();
149-
for (const [key, value] of kept) {
150-
const cover = coveredBy(key, (other) =>
151-
other === key ? value : kept.get(other),
152-
);
153-
if (cover !== undefined && cover !== key && kept.has(cover))
154-
covers.set(key, cover);
164+
for (const [key, value] of retained) {
165+
const cover = keptCover(key, value);
166+
if (cover !== undefined) covers.set(key, cover);
155167
}
156-
// A cover that is itself covered passes the recency on to what replaced it.
157-
const final = (key: string) => {
158-
let cover = covers.get(key) ?? key;
159-
for (let hops = 0; covers.has(cover) && hops < covers.size; hops++)
160-
cover = covers.get(cover) as string;
161-
return cover;
162-
};
163-
for (const key of covers.keys()) {
164-
const cover = final(key);
165-
if (cover === key || covers.has(cover)) continue;
168+
for (const [key, cover] of covers) {
169+
// Chains end at a kept mark: scopes only get broader along them.
170+
let last = cover;
171+
for (let hops = 0; covers.has(last) && hops < covers.size; hops++)
172+
last = covers.get(last) as string;
173+
if (covers.has(last)) continue;
166174
const value = retained.get(key) as number;
167175
retained.delete(key);
168-
dropped.add(key);
176+
dropped.set(key, cover);
169177
pruned = true;
170178
used -= cost(frontierKey(key), value);
171179
keys--;
172-
if (nextRecent[key] !== undefined)
173-
nextRecent[cover] = Math.max(nextRecent[cover] ?? 0, nextRecent[key]);
174180
}
175181
if (pruned) select();
176182
}
183+
// A dropped mark gives its recency to the kept mark at the end of its chain.
184+
for (const [key, cover] of dropped) {
185+
if (nextRecent[key] === undefined) continue;
186+
let last = cover;
187+
for (let hops = 0; dropped.has(last) && hops < dropped.size; hops++)
188+
last = dropped.get(last) as string;
189+
if (retained.has(last))
190+
nextRecent[last] = Math.max(nextRecent[last] ?? 0, nextRecent[key]);
191+
}
177192
const state = Object.freeze({
178193
frontiers: Object.freeze(Object.fromEntries(retained)),
179194
overrides: protectedState.overrides,

0 commit comments

Comments
 (0)