Fix #65: bound Starred-list fan-out #68

Merged

crueber merged 1 commit from fix/issue-65 into main

2026-09-04 23:19:23 +00:00

crueber commented

2026-09-04 23:15:35 +00:00

Owner

Bounds the Starred-list fan-out (#65): Starred() LISTed the whole users/

/starred/ prefix and GET+HEADed every record to sort newest-first, then truncated — O(total stars) round trips per page load.

Shape (no reverse index, no users LIST, no global scan):

Pages are keyset over the key space, repo (owner/name) ascending: one LIST resumed at the after repo key, aborted at the page edge via a filtered sentinel; at most n+1 record GETs + n+1 manifest HEADs per page (the +1 decides more exactly). O(page), flat in the total; later pages never re-probe earlier ones.
Cursor keeps its <starred_at>| shape (timestamp echoed; resumption keys off the repo). Order change resets in-flight pagination (cursors are single-session hints).
Skip-on-error preserved: dead repos, corrupt/unreadable records skipped; manifest probe errors keep the entry (fail-open per #63).
n default 50 / max 100 unchanged, applied before probes; []-not-null, plain-text errors unchanged.

Sibling surfaces audited, no change needed: no watching-list endpoint exists (single-record GetWatch; watcher_list capped at 1000 by the writer); notification tray LIST overflow already capped at 1000 GETs; releases list capped via ListScanCap; release fan-out reads the capped watcher_list. Starred was the only unbounded read, as the issue states.

Docs (law 12): 07 section 7 table + Decisions entry record the repo-order change; E8 budget row/analysis updated (page 1: 1 LIST + 51 GETs + 51 HEADs at both 60 and 600 stars; page 2 probes only the remainder); SDK comment updated.

Tests: TestStarredLists re-pinned to key order; new table-driven TestStarredPagesTable (HTTP twins: pages, ghost/corrupt skips mid-walk, n clamp, exhausted-page []-not-null, malformed-cursor 400); evidence test pins flat page-1 cost across 3/60/600 stars plus a no-overlap two-page walk at 60. gofmt/vet clean; go test -race passes; cover 99.2% (gate >=95%).

Note: TestStarConcurrentConverge flakes on unmodified origin/main too (fails with and without -race; extra star bump from the (c) resync racing an in-flight first bump) — pre-existing, untouched by this change, left for its own issue.

Bounds the Starred-list fan-out (#65): Starred() LISTed the whole users/<p>/starred/ prefix and GET+HEADed every record to sort newest-first, then truncated — O(total stars) round trips per page load. Shape (no reverse index, no users LIST, no global scan): - Pages are keyset over the key space, repo (owner/name) ascending: one LIST resumed at the after repo key, aborted at the page edge via a filtered sentinel; at most n+1 record GETs + n+1 manifest HEADs per page (the +1 decides more exactly). O(page), flat in the total; later pages never re-probe earlier ones. - Cursor keeps its <starred_at>|<repo> shape (timestamp echoed; resumption keys off the repo). Order change resets in-flight pagination (cursors are single-session hints). - Skip-on-error preserved: dead repos, corrupt/unreadable records skipped; manifest probe errors keep the entry (fail-open per #63). - n default 50 / max 100 unchanged, applied before probes; []-not-null, plain-text errors unchanged. Sibling surfaces audited, no change needed: no watching-list endpoint exists (single-record GetWatch; watcher_list capped at 1000 by the writer); notification tray LIST overflow already capped at 1000 GETs; releases list capped via ListScanCap; release fan-out reads the capped watcher_list. Starred was the only unbounded read, as the issue states. Docs (law 12): 07 section 7 table + Decisions entry record the repo-order change; E8 budget row/analysis updated (page 1: 1 LIST + 51 GETs + 51 HEADs at both 60 and 600 stars; page 2 probes only the remainder); SDK comment updated. Tests: TestStarredLists re-pinned to key order; new table-driven TestStarredPagesTable (HTTP twins: pages, ghost/corrupt skips mid-walk, n clamp, exhausted-page []-not-null, malformed-cursor 400); evidence test pins flat page-1 cost across 3/60/600 stars plus a no-overlap two-page walk at 60. gofmt/vet clean; go test -race passes; cover 99.2% (gate >=95%). Note: TestStarConcurrentConverge flakes on unmodified origin/main too (fails with and without -race; extra star bump from the (c) resync racing an in-flight first bump) — pre-existing, untouched by this change, left for its own issue.

crueber added 1 commit

2026-09-04 23:15:36 +00:00

Fix #65 : bound Starred-list fan-out with keyset pages 60c3d63764

Starred() LISTed the whole users/<p>/starred/ prefix and GET+HEADed every
record to sort newest-first, then truncated to the page: O(total stars)
store round trips per page load. Pages are now keyset over the key space
(repo owner/name ascending): one LIST resumed at the after repo's key,
aborted at the page edge, at most n+1 record GETs + n+1 manifest HEADs
per page (the +1 decides more exactly) — O(page), flat in the total.
Cursor keeps its <starred_at>|<repo> shape (resumption keys off the
repo); skip-on-error preserved (dead repos, corrupt records, fail-open
probes per #63). No reverse index, no users LIST, no global scan.

07 §7 table + Decisions record the order change; E8 budget table updated
(page 1 identical at 60 and 600 stars); SDK comment updated.

crueber referenced this pull request

2026-09-04 23:15:39 +00:00

Social Starred list is an unbounded GET-per-record scan #65

crueber referenced this pull request

2026-09-04 23:19:09 +00:00

Social Starred list is an unbounded GET-per-record scan #65

crueber merged commit f94a16d1e1 into main

2026-09-04 23:19:23 +00:00

crueber referenced this pull request from a commit

2026-09-04 23:19:24 +00:00

Merge pull request 'Fix #65: bound Starred-list fan-out' (#68) from fix/issue-65 into main

crueber referenced this pull request