refactor(server): give the four LRU eviction min_by_key calls a total order

[inureyes]

Problem / Background

Four LRU eviction sites pick their victim with min_by_key applied directly to a HashMap iterator. Iterator::min_by_key returns the FIRST minimum, so when two entries tie on the timestamp key, which entry gets evicted is decided by HashMap iteration order, and RandomState seeds that order per map instance. The selection is therefore not pinned by the code; it is pinned only by the accident that the key never ties.

Severity, stated precisely: this is not a live bug, and it should not be described as four bugs. All four keys are std::time::Instant. Every writer computes let now = Instant::now() once per call and stamps a single entry with it, so any two entries take their stamps from two separate Instant::now() calls, which resolve to nanoseconds on the platforms this project targets and effectively never collide. Nothing misbehaves today, in any of the four.

What this is instead is a fragile pattern with no mechanical guard behind it. It becomes a real defect the moment the key becomes anything coarser than a per-call Instant: a seconds-granularity integer, a logical clock, a value hoisted out of a loop and shared across several entries in a batch operation, or a timestamp deserialized from disk at whatever resolution the format carries. The change that would break it is small, and it would not look like it has anything to do with eviction.

Current Behavior

All four verified at a0e402ad:

• src/server/prompt_cache/store.rs:315, in Inner::evict_oldest, over entries: HashMap<PromptCacheKeyDigest, EntrySlot> (declared at src/server/prompt_cache/store.rs:101), keyed on slot.entry.last_used(). Called from enforce_caps at src/server/prompt_cache/store.rs:355 and :363.
• src/server/prompt_cache/store.rs:336, in Inner::evict_oldest_snapshot, the same shape over snapshots: HashMap<PromptCacheKeyDigest, SnapshotSlot> (declared at src/server/prompt_cache/store.rs:111). Called from enforce_snapshot_caps at src/server/prompt_cache/store.rs:376 and :384.
• src/server/responses_store.rs:243, in ResponsesStore::evict_to_capacity(map: &mut HashMap<String, Entry>, target_size: usize), keyed on e.last_accessed.
• src/server/conversation_store.rs:151, in ConversationStore::evict_to_capacity(map: &mut HashMap<String, Entry>, target_size: usize), keyed on e.last_accessed.

Why the tie is unreachable today, per site. For the two stores, the writers are ResponsesStore::insert at src/server/responses_store.rs:161, ResponsesStore::get at src/server/responses_store.rs:182, ConversationStore::get at src/server/conversation_store.rs:83, and ConversationStore::append at src/server/conversation_store.rs:96. Each takes one Instant::now() and stamps one entry. For the prompt cache, PromptCacheEntry::touch (src/server/prompt_cache/entry.rs:274-280) and ModelSnapshotEntry::touch (src/server/prompt_cache/entry.rs:413-419) each write Instant::now() under their own mutex, one entry per call, and construction stamps the same way (src/server/prompt_cache/entry.rs:213, :329, :388, :441).

Proposed Solution

Give each key a total order by appending the map key, which is unique by construction. docs/code-guidelines.md (the "HashMap Iteration Order" section, starting at line 109) records the accepted forms and the rationale. The tuple form suits the Copy PromptCacheKeyDigest keys, and the comparator form suits the String keys, where a tuple key would force a clone:

// prompt_cache/store.rs, both sites. The digest is Copy, so the tuple is free.
.min_by_key(|(digest, slot)| (slot.entry.last_used(), *digest.as_bytes()))

// responses_store.rs and conversation_store.rs. The key is a String, so compare
// rather than build a tuple key that would clone it.
.min_by(|(key_a, a), (key_b, b)| a.last_accessed.cmp(&b.last_accessed).then_with(|| key_a.cmp(key_b)))

Exact call shapes are the implementer's choice; what matters is that no two distinct entries can compare equal, so HashMap iteration order cannot reach the result. One detail that will bite otherwise: PromptCacheKeyDigest derives only Clone, Copy, PartialEq, Eq, Hash (src/server/prompt_cache/key.rs:53-54), so it is not Ord and cannot go into a min_by_key tuple as-is. Either add PartialOrd, Ord to that derive, which is well defined for a BLAKE3 digest newtype over [u8; 32], or key on *digest.as_bytes() (src/server/prompt_cache/key.rs:58) and leave the type alone. Prefer the latter if you would rather not widen the type's public trait surface for one call site.

Add a short comment at each of the four sites naming the key component as the thing that makes the order total, per the same guideline. Without it the component reads as redundant and a later simplification pass removes it.

Scope

In scope: the four call sites listed above, in src/server/prompt_cache/store.rs, src/server/responses_store.rs, and src/server/conversation_store.rs, plus a comment at each.

Out of scope: any change to the eviction policy itself, to the cap-enforcement loops, or to what the stores are bounded by. Byte-bounding of the two stores is #1248. No other min_by_key or max_by_key call in the tree, and no other iteration-order site.

Implementation Notes

• Reuse: follow the forms already recorded in docs/code-guidelines.md, and the fixes that landed under fix(distributed): registry accessors return HashMap order, so node routing and failover re-routing are not reproducible #1277 (PR fix(distributed): give registry node accessors a defined order #1284) and fix(distributed): eviction candidate sorts are stable, so HashMap order still picks which tied sequence is evicted #1286 (PR fix(distributed): break eviction sort ties on the unique id #1288), rather than inventing a new shape.
• Constraints: this must not change behavior in any reachable case. Since no reachable input ties, the fix is behavior-preserving by construction; if it changes an existing test's expected victim, that test was depending on a tie and the change needs explaining, not accepting.
• Do not: swap the containers to BTreeMap. All four are on lookup-hot paths and the guideline's fix(distributed): registry accessors return HashMap order, so node routing and failover re-routing are not reproducible #1277 precedent kept HashMap for exactly this reason.
• Edge cases: empty map (the existing else { break; } and None => 0 arms already handle it and must keep working); a single entry (the total order is a no-op there); the prompt cache's last_used read taking a mutex per entry, which the tuple key must not turn into a double lock, so read it once per element.
• Error handling: unchanged. None of the four sites can fail; the poisoned-lock fallbacks in entry.rs and the store guards stay as they are.

Acceptance Criteria

• All four sites select their victim through a total order, so the choice cannot depend on HashMap iteration order.
• Each of the four sites carries a comment naming the tie-break component as what makes the order total, so a later simplification pass does not strip it.
• Behavior on every reachable input is unchanged: no existing test in src/server/prompt_cache/store_tests.rs, src/server/responses_store.rs, or src/server/conversation_store.rs changes its expected outcome.
• A decision is recorded in the PR body on whether a regression test is worth adding, either way, with the reason. A test is optional here and deliberately so: the tie is not reachable through the public API, so a test would have to construct entries carrying a deliberately equal Instant, which no production path produces. If one is added it must follow the guideline's testing rule (fresh map per iteration, 32 or more iterations, an actual constructed tie, validated by failing against the unfixed code first). If the implementer judges that such a test would only pin an unreachable state and prefers to rely on the comment plus the guideline, that is an acceptable outcome and should be stated.
• make verify-test-cuda passes.

Verification

make verify-fmt
make verify-test-cuda
# Targeted, faster than the full gate while iterating:
cargo test --profile test-fast --features cuda prompt_cache -- --test-threads=1
cargo test --profile test-fast --features cuda responses_store conversation_store -- --test-threads=1

On Apple Silicon the equivalent gate is make verify-fmt && make verify-clippy && make verify-test. verify-clippy builds with --features metal,accelerate and does not run on a CUDA box; on Linux, make verify-fmt plus make verify-test-cuda is the gate.

A pass is: fmt clean, no new clippy warnings on the platform where clippy runs, and no test failures attributable to this change.

Technical Considerations

Where these four came from. They are the residue of the sweep recorded in docs/code-guidelines.md under "HashMap Iteration Order" (#1287, PR #1290). That guideline documents seven instances of the same class that WERE live and were fixed: #1265 (PR #1266), #1267 (PR #1269), #1276 (PR #1281), #1277 (PR #1284), and #1286 (PR #1288). It also records why no static check was adopted, and these four sites are precisely the reason the min_by_key candidate rule was declined: run over all 1,248 .rs files under src/, it flags exactly these four, catches 0 of the 7 real instances, and gating on it would have meant suppressing four of four findings on the day it landed, with a suppression that does not re-arm on the change that would make the pattern real. Fixing the four by hand removes that tension and leaves the guideline's decision intact.

Coordination with #1248. src/server/responses_store.rs and src/server/conversation_store.rs are already in scope for #1248 (status:ready, open, no PR as of filing), which bounds those two stores by bytes rather than entry count. Two of the four sites are therefore cheaper to fix inside that work than separately, and #1248 may well rewrite the eviction loop around them. Check #1248's state before starting. If it is in flight, folding those two into it and leaving only the two src/server/prompt_cache/store.rs sites here is the better split. Note also that a byte-bounded eviction policy is exactly the kind of change that could introduce a coarser key and make this reachable, which raises the value of doing it alongside rather than after.