go-lru2q-scan-resistant-sharded-cache
All verified. Here's a summary of the work:
Root cause: Plain LRU is not scan-resistant. A one-pass scan of 100,000 distinct cold keys through a 10,000-slot cache means every cold insert evicts the LRU end — the 1,000 hot keys are re-accessed far less often than the ~10,000-insert eviction horizon, so they're always gone by re-access. Measured LRU hot ratio on the exact acceptance trace: 0%.
The fix (~/lru2q/): a generic, thread-safe 2Q cache (lru2q package):
recent (A1in): small FIFO absorbing every first-time Set — the entire scan dies here.reusable (Am): LRU queue; a second access (Get or Set hit in recent) promotes into it. Scan keys (one touch) can never reach it.out (A1out): bounded ghost directory of evicted keys; a Set for a ghosted key re-admits directly into reusable.Cleanup()/optional background loop driven by an O(1)-amortized timing wheel.sync.Mutex (2Q is a global policy), so everything is race-free; O(1) amortized Get/Set/Delete.Verification (Go 1.26, -race, 13 tests, all passing):
2Q hot-key hit ratio: 100.00% (20000/20000) — required > 85%
LRU hot-key hit ratio: 0.00% (0/20000) — collapsed < 10% (baseline)
Also verified: exact model parity over 200k random ops ("Get returns the latest Set value at every interleaving point"), ghost promotion/eviction semantics, TTL sweep correctness, structural invariants under random ops, and 16-goroutine concurrent stress under -race (including a background cleanup loop and post-concurrency hot-ratio re-check at 100%).
One interesting bug found during verification: my first concurrent test asserted Get == value immediately after SetWithTTL with TTLs as low as 1 ms. Under 16 goroutines + race detector, the entry legitimately expired during scheduler preemption between the two calls (confirmed via a removal stack dump: the miss came from Get's own lazy-expiry path). The cache was correct; the test now asserts a miss is only an error if the TTL could not have elapsed.
Deliverable: ~/lru2q/SOLUTION.md — self-contained markdown with root-cause analysis, full go.mod/2q.go/2q_test.go code, commands, actual outputs, and a per-test evidence table.
# Evidence - Problem class: go-lru2q-scan-resistant-sharded-cache - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-02T22:41:10.180Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a thread-safe, scan-resistant cache in Go implementing the 2Q (Two Queue) policy: a small FIFO 'recent' queue (hot entries on first access), promotion to an LRU 'reusable' queue on a second access, and a ghost 'out' directory of recently evicted keys that promotes a miss into reusable directly. Provide Get/Set/Delete with amortized O(1) time and a cleanup pass that evicts TTL-expired entries; all operations must stay race-free under `go test -race` with 16 goroutines. The acceptance harness replays a fixed trace: 1000 distinct hot keys repeatedly accessed while a single one-pass sequential scan of 100,000 cold keys streams through a cache of capacity 10,000, and asserts the hot-key hit ratio exceeds 85% (a plain LRU collapses below 10% on the same trace), then verifies Get returns the latest Set value for every key at every interleaving point.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-lru2q-scan-resistant-sharded-cache", "provider": "openrouter", "solved_at": "2026-09-02T22:41:10.181Z", "version": "1.26"}All verified. Here's a summary of the work:
Root cause: Plain LRU is not scan-resistant. A one-pass scan of 100,000 distinct cold keys through a 10,000-slot cache means every cold insert evicts the LRU end — the 1,000 hot keys are re-accessed far less often than the ~10,000-insert eviction horizon, so they're always gone by re-access. Measured LRU hot ratio on the exact acceptance trace: 0%.
The fix (~/lru2q/): a generic, thread-safe 2Q cache (lru2q package):
recent (A1in): small FIFO absorbing every first-time Set — the entire scan dies here.reusable (Am): LRU queue; a second access (Get or Set hit in recent) promotes into it. Scan keys (one touch) can never reach it.out (A1out): bounded ghost directory of evicted keys; a Set for a ghosted key re-admits directly into reusable.Cleanup()/optional background loop driven by an O(1)-amortized timing wheel.sync.Mutex (2Q is a global policy), so everything is race-free; O(1) amortized Get/Set/Delete.Verification (Go 1.26, -race, 13 tests, all passing):
2Q hot-key hit ratio: 100.00% (20000/20000) — required > 85%
LRU hot-key hit ratio: 0.00% (0/20000) — collapsed < 10% (baseline)
Also verified: exact model parity over 200k random ops ("Get returns the latest Set value at every interleaving point"), ghost promotion/eviction semantics, TTL sweep correctness, structural invariants under random ops, and 16-goroutine concurrent stress under -race (including a background cleanup loop and post-concurrency hot-ratio re-check at 100%).
One interesting bug found during verification: my first concurrent test asserted Get == value immediately after SetWithTTL with TTLs as low as 1 ms. Under 16 goroutines + race detector, the entry legitimately expired during scheduler preemption between the two calls (confirmed via a removal stack dump: the miss came from Get's own lazy-expiry path). The cache was correct; the test now asserts a miss is only an error if the TTL could not have elapsed.
Deliverable: ~/lru2q/SOLUTION.md — self-contained markdown with root-cause analysis, full go.mod/2q.go/2q_test.go code, commands, actual outputs, and a per-test evidence table.
# Evidence - Problem class: go-lru2q-scan-resistant-sharded-cache - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-09-02T22:41:10.180Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a thread-safe, scan-resistant cache in Go implementing the 2Q (Two Queue) policy: a small FIFO 'recent' queue (hot entries on first access), promotion to an LRU 'reusable' queue on a second access, and a ghost 'out' directory of recently evicted keys that promotes a miss into reusable directly. Provide Get/Set/Delete with amortized O(1) time and a cleanup pass that evicts TTL-expired entries; all operations must stay race-free under `go test -race` with 16 goroutines. The acceptance harness replays a fixed trace: 1000 distinct hot keys repeatedly accessed while a single one-pass sequential scan of 100,000 cold keys streams through a cache of capacity 10,000, and asserts the hot-key hit ratio exceeds 85% (a plain LRU collapses below 10% on the same trace), then verifies Get returns the latest Set value for every key at every interleaving point.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-lru2q-scan-resistant-sharded-cache", "provider": "openrouter", "solved_at": "2026-09-02T22:41:10.181Z", "version": "1.26"}