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

crueber commented

2026-09-04 22:39:43 +00:00

Owner

Follow-up from the backend audit on issue #59 (origin/main @940ca8c).

Evidence: internal/social/service.go:168-230. Starred() LISTs the user's whole starred prefix (line 189) and GETs every record (lines 196-217), then truncates to the page (lines 224-228). Cost is O(total stars) GETs per page load with no backend bound (only the output is clamped to ListMaxPage).

Impact: a user with e.g. 10k stars costs ~10k GETs per tray page. Only unbounded read found in the Q3 sweep; everything else is O(1) or bounded-O(n).

Suggested fix: bound the backend scan with a documented truncation, or add a time-ordered per-user index so pagination does not need a full scan (keys are repo-keyed, not time-ordered, so server-side paging needs a new shape).

Follow-up from the backend audit on issue #59 (origin/main @940ca8c). Evidence: internal/social/service.go:168-230. Starred() LISTs the user's whole starred prefix (line 189) and GETs every record (lines 196-217), then truncates to the page (lines 224-228). Cost is O(total stars) GETs per page load with no backend bound (only the output is clamped to ListMaxPage). Impact: a user with e.g. 10k stars costs ~10k GETs per tray page. Only unbounded read found in the Q3 sweep; everything else is O(1) or bounded-O(n). Suggested fix: bound the backend scan with a documented truncation, or add a time-ordered per-user index so pagination does not need a full scan (keys are repo-keyed, not time-ordered, so server-side paging needs a new shape).

crueber referenced this issue

2026-09-04 22:59:37 +00:00

Repo delete leaves userspace references (stars/watches/notifications/invites) #63

crueber referenced this issue from a commit

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

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

crueber referenced this issue from a pull request that will close it,

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

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

crueber commented

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

Author

Owner

Fix open in PR #68 (branch fix/issue-65): Starred() is now keyset pagination over the key space (repo ascending) — 1 LIST from the after key aborted at the page edge, at most n+1 GETs + n+1 HEADs per page, flat in the total; skip-on-error preserved; no reverse index / users LIST / global scan. Evidence: page-1 cost identical at 60 and 600 stars. Sibling surfaces audited (watching, tray, releases list, fan-out) — all already bounded, no change. One note: TestStarConcurrentConverge flakes on unmodified main too (pre-existing, unrelated).

crueber commented

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

Author

Owner

PR #68 review (branch fix/issue-65, commit 60c3d63) — verified in scratch worktree, main worktree untouched.

PASS (all with file:line):

Prefix-scoped LIST, no reverse index / users LIST / global scan: Starred calls Store.List with prefix=users//starred/ only (internal/social/service.go:246,256); startAfter=prefix+rp+.json stays inside that dir. No new LIST call sites; CAS paths (bumpStars/casUpdate) untouched.
Abort-at-page-edge on every existing backend: errStarPageFull returned from the List callback (service.go:280) propagates unwrapped — memory.go:203-205, filesystem.go:747-749+766-768, s3.go:1050-1056, Prefixed store.go:286-291; sentinel-abort covered by existing tests (memory_test.go:223, filesystem_test.go:417, s3_test.go:895). No GCS backend exists in-tree, nothing to check there.
O(page) cost, +1 can't loop: entries collected to n+1 then hard abort; trim to n + more=true (service.go:279-290). Exactly one extra probe, no loop possible. Evidence test pins 1 LIST + 51 GETs + 51 HEADs at both 60 and 600 stars, page 2 probing only the 10 remaining (evidence_test.go:99-135).
Cursor: shape <starred_at>| unchanged; timestamp still validated by splitStarCursor (service.go:296-309), malformed -> ErrInvalid -> 400 plain-text (cover_test.go:77 maps ErrInvalid->400; http_test.go:222 pins body 'malformed after cursor'). Nuance: well-formed OLD cursors still parse and resume by repo key — a defined keyset position, not silent-wrong data; the order reset is documented ('single-session hints', 07 Decisions amendment).
#63 semantics preserved: dead repo -> skip (service.go:274-276), probe error -> keep (repoAlive fails open, social.go:179-185); corrupt/unreadable records skipped without failing the page.
n clamp before probes (service.go:240-245; handler rejects n<=0 with 400, http.go:293-301); []-not-null via make(...,0,...) at both layers (service.go:255, http.go:307), pinned by 'page3 exhausted' asserting "starred":[] (http_test.go:220,236).
Sort-order change documented in 07 §7 table + Decisions amendment; SDK comment updated (web/sdk/src/social.js:38).
Sibling audit (ONE spot-check): notify fan-out bounded — MaxSyncRecipients=100 with overflow-task fallback (internal/notify/emit.go:199), MaxWatchers=1000, MaxTeamFanout=100, tray/maintain scan caps (tasks.go:463,526). Plausible, no sibling action needed.
E8 budget lines honest: doc numbers (1 LIST + 51 GETs + 51 HEADs at 60 and 600) match the test assertions exactly.
Imports: +errors stdlib only, -sort; http_test +net/url stdlib. No third-party additions.

Tests (scratch worktree @60c3d63): targeted Starred/evidence/cover/HTTP suites all PASS with -race; package coverage 99.2% (>=95% gate); gofmt clean; go vet clean.

PRE-EXISTING FLAKE (not this PR, not fixed): TestStarConcurrentConverge (service_test.go:55-77) fails intermittently (counts 3/4/8/9 vs want 2) with and without -race load; reproduces on base 87d9c2b in a separate scratch worktree, and the Star/bump path is byte-identical between base and PR. Suggest a separate issue for the Star check-then-act race; full suite passed once (1.049s ok) so it is scheduling-dependent.

No fixes pushed (nothing PR-caused to fix). MERGE RECOMMENDATION: ready to merge.

PR #68 review (branch fix/issue-65, commit 60c3d63) — verified in scratch worktree, main worktree untouched. PASS (all with file:line): - Prefix-scoped LIST, no reverse index / users LIST / global scan: Starred calls Store.List with prefix=users/<who>/starred/ only (internal/social/service.go:246,256); startAfter=prefix+rp+.json stays inside that dir. No new LIST call sites; CAS paths (bumpStars/casUpdate) untouched. - Abort-at-page-edge on every existing backend: errStarPageFull returned from the List callback (service.go:280) propagates unwrapped — memory.go:203-205, filesystem.go:747-749+766-768, s3.go:1050-1056, Prefixed store.go:286-291; sentinel-abort covered by existing tests (memory_test.go:223, filesystem_test.go:417, s3_test.go:895). No GCS backend exists in-tree, nothing to check there. - O(page) cost, +1 can't loop: entries collected to n+1 then hard abort; trim to n + more=true (service.go:279-290). Exactly one extra probe, no loop possible. Evidence test pins 1 LIST + 51 GETs + 51 HEADs at both 60 and 600 stars, page 2 probing only the 10 remaining (evidence_test.go:99-135). - Cursor: shape <starred_at>|<repo> unchanged; timestamp still validated by splitStarCursor (service.go:296-309), malformed -> ErrInvalid -> 400 plain-text (cover_test.go:77 maps ErrInvalid->400; http_test.go:222 pins body 'malformed after cursor'). Nuance: well-formed OLD cursors still parse and resume by repo key — a defined keyset position, not silent-wrong data; the order reset is documented ('single-session hints', 07 Decisions amendment). - #63 semantics preserved: dead repo -> skip (service.go:274-276), probe error -> keep (repoAlive fails open, social.go:179-185); corrupt/unreadable records skipped without failing the page. - n clamp before probes (service.go:240-245; handler rejects n<=0 with 400, http.go:293-301); []-not-null via make(...,0,...) at both layers (service.go:255, http.go:307), pinned by 'page3 exhausted' asserting "starred":[] (http_test.go:220,236). - Sort-order change documented in 07 §7 table + Decisions amendment; SDK comment updated (web/sdk/src/social.js:38). - Sibling audit (ONE spot-check): notify fan-out bounded — MaxSyncRecipients=100 with overflow-task fallback (internal/notify/emit.go:199), MaxWatchers=1000, MaxTeamFanout=100, tray/maintain scan caps (tasks.go:463,526). Plausible, no sibling action needed. - E8 budget lines honest: doc numbers (1 LIST + 51 GETs + 51 HEADs at 60 and 600) match the test assertions exactly. - Imports: +errors stdlib only, -sort; http_test +net/url stdlib. No third-party additions. Tests (scratch worktree @60c3d63): targeted Starred/evidence/cover/HTTP suites all PASS with -race; package coverage 99.2% (>=95% gate); gofmt clean; go vet clean. PRE-EXISTING FLAKE (not this PR, not fixed): TestStarConcurrentConverge (service_test.go:55-77) fails intermittently (counts 3/4/8/9 vs want 2) with and without -race load; reproduces on base 87d9c2b in a separate scratch worktree, and the Star/bump path is byte-identical between base and PR. Suggest a separate issue for the Star check-then-act race; full suite passed once (1.049s ok) so it is scheduling-dependent. No fixes pushed (nothing PR-caused to fix). MERGE RECOMMENDATION: ready to merge.

crueber closed this issue

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

crueber referenced this issue 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 commented

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

Author

Owner

Fixed by PR #68 (review clean; keyset pagination, O(page) pinned; 99.2% coverage), merged. Closing.

crueber referenced this issue

2026-09-04 23:29:07 +00:00