RateLimiter::rollback_increment uses get_mut, promoting the rolled-back key to most-recently-used and skewing LRU eviction/cleanup toward failed-admission keys

[erskingardner]

Summary

RateLimiter::rollback_increment fetches the per-key entry with LruCache::get_mut, which promotes the key to the most-recently-used (MRU) position as a side effect. Rollback is a compensating undo of a previously admitted hit, so it should not refresh the key's recency. Using get_mut here makes a key whose admission is being rolled back look freshly accessed, moving it to the front of its stripe's LRU list — the opposite of what the operation means.

This is a low-probability, low-impact edge case (rollback only fires on the rare dispatch-admission-failure back-pressure path), filed as LOW for correctness/consistency.

Location

src/rate_limiter.rs:515 (rollback_increment):

pub async fn rollback_increment(&self, key: &K, reservation: RateLimitReservation) {
    let hit_id = reservation.0;
    let mut entries = self.stripe_for(key).write().await;
    let should_remove = if let Some(entry) = entries.get_mut(key) {   // <-- promotes key to MRU
        remove_hit(&mut entry.minute_hits, hit_id);
        remove_hit(&mut entry.hour_hits, hit_id);
        entry.minute_hits.is_empty() && entry.hour_hits.is_empty()
    } else {
        false
    };

    if should_remove && entries.pop(key).is_some() {
        self.entry_count.fetch_sub(1, Ordering::Relaxed);
    }
}

In the lru crate, get_mut moves the entry to the head of the LRU list, whereas peek_mut returns the same mutable reference without touching recency. This codebase already relies on that exact distinction elsewhere: SeenEventStore::mark_terminal (src/nostr/events/dedup.rs:110) deliberately uses peek_mut and then calls promote explicitly only when it wants MRU promotion — demonstrating the authors treat get_mut's implicit promotion as a behavior to opt into, not a default.

Analysis / impact

When a rollback does not empty the entry (the key still holds other in-window hits, e.g. concurrent admissions for the same encrypted-token hash or device token), should_remove is false and the entry survives — but get_mut has already moved it to MRU. Consequences, all bounded:

1. Eviction fairness skew. Both the admission-path eviction probe (evict_lru_admission_candidate, scans from the LRU tail, line 367) and the periodic cleanup sweep (also tail-first, line 546) look at the least-recently-used end. A key that repeatedly gets admitted-then-rolled-back is repeatedly pushed to MRU, so it resists eviction and cleanup longer than keys that were never rolled back. Under stripe cardinality pressure this makes legitimate new keys marginally more likely to hit ExceededCapacityLimit or be evicted, while a "squatting" failed-admission key lingers near the front.
2. Minor recency corruption in the ordinary case. Even without pressure, rollback silently reorders the stripe's LRU list, so subsequent eviction decisions no longer reflect true access recency.

Impact is small because rollback fires only when downstream dispatch admission fails (queue full / shutting down) — a rare, non-attacker-controlled back-pressure condition — and the effect is a fairness/eviction-ordering skew, not a limit-bypass or a panic.

Recommendation

Use peek_mut in rollback_increment so the undo does not alter LRU recency:

let should_remove = if let Some(entry) = entries.peek_mut(key) {
    remove_hit(&mut entry.minute_hits, hit_id);
    remove_hit(&mut entry.hour_hits, hit_id);
    entry.minute_hits.is_empty() && entry.hour_hits.is_empty()
} else {
    false
};

Add a regression test: admit key A, admit a second hit for A, admit filler keys to make A the LRU tail, roll back one of A's hits, then assert A is still the eviction/cleanup victim (i.e. the rollback did not promote it to MRU).

Why this is not a duplicate

• [LOW] RateLimiter::rollback_increment is identity-unaware (pop_back), so under concurrent processing of the same key it can remove the wrong hit #87 (rollback_increment identity-unaware pop_back) concerned which timestamp was removed and was fixed by introducing reservation IDs + remove_hit; that fix left the get_mut call — and thus the LRU-promotion side effect — in place. This issue is about the recency side effect, not hit identity.
• rate_limiter remove_hit scans front-first for a hit that is almost always at the back (use rposition) #251 (remove_hit front-vs-back scan → rposition) is about the deque scan direction inside an entry, not the cache-level LRU position.
• [MEDIUM] Dedup cache cleanup scans the most-recently-used end of the LRU, so expired entries are never reclaimed at scale #60 (dedup cleanup scanning the MRU end) is a different function (EventProcessor::cleanup) and concerns scan direction, not an unintended promotion during rollback.

None of them touch the get_mut-vs-peek_mut promotion in rollback_increment.