Since Redis 3.0 the eviction code keeps a persistent pool of candidate keys instead of simply evicting the best key of each random sample. How does that pool work, and what problem did it fix?

## The weakness of memoryless sampling The original approximation was memoryless: sample N keys, evict the idlest of the N, throw the rest away. If a round happened to surface an extremely idle key in second place, that knowledge was discarded and the next round started from scratch. The quality of every decision was therefore bounded by the quality of one small random draw, and the only tuning knob was to make every draw bigger, which costs CPU on the single command-execution thread on every eviction. ## What the pool adds Redis 3.0 introduced a persistent candidate structure, the eviction pool: a fixed array of 16 slots, each holding a key name, its database, and a score. The score is a monotone "how evictable is this" value - estimated idle time for the LRU policies, and a value derived from the inverse of the frequency counter for LFU, so that in both cases the highest score is the best victim. The array is kept sorted, so inserting a candidate is a small ordered insert and the best candidate is always at a known end. Each eviction round does the following: 1. Sample `maxmemory-samples` random keys from the policy's candidate dictionary. 2. Compute each sampled key's score and try to insert it into the pool; if the pool is full, the worst existing entry is displaced only when the newcomer is better. 3. Walk the pool from the best entry down, look the key up in the dictionary to confirm it still exists (it may have been deleted, expired or already evicted since it entered the pool), and evict the first one that does, removing it from the pool. 4. If memory is still above `maxmemory`, repeat. Because the pool survives between rounds, good candidates found earlier stay available. Over a burst of eviction the pool converges on the genuinely idle tail of the keyspace, so the outcome is much closer to true LRU than the sample size alone would suggest. This is why the documented accuracy of Redis 3.0 with 5 samples is comparable to Redis 2.8 with 10, and why the default was able to stay at 5. ## Details that matter in practice - The pool is per-instance eviction state, not per-database; each entry records which database the key came from, since eviction may span databases. - Entries are stale by design. A key can be modified, deleted or expire while sitting in the pool, which is why the eviction step re-validates before deleting - a pooled key is a hint, not a reservation. - The pool does not remove the randomness. It biases the search toward already-seen good candidates but still only ever sees keys that random sampling surfaced, so a key that is never sampled is never evicted no matter how idle it is. - Under LFU the same structure is reused; only the scoring function changes, which is why the tuning story (sample size versus CPU) is identical for both families. ## Why an interviewer asks this It separates candidates who have read how Redis eviction actually behaves from those who repeat "it samples five keys". The useful takeaway is the general technique: when exact global ordering is too expensive, keep a bounded window of the best candidates seen so far and refresh it incrementally, so accuracy accumulates over time instead of being re-purchased on every decision.