TTL Cache with a Redis-Style Adaptive Reaper

This is a key/value cache whose entries can expire. Reads must never return an expired value, and memory held by expired keys must eventually be freed, even for keys that nobody reads again. The work to free that memory should not make the server stall.

Where it shows up

• Session and token stores: login sessions, OAuth tokens, CSRF nonces (Redis SET ... PX).
• Rate limiters and idempotency keys: counters and request ids that must disappear after a window.
• Distributed locks and leases: a lock that expires if its holder dies (see the redis-redlock-and-fencing-tokens lesson).
• Inventory holds: "held in cart for 10 minutes" in flash sales.

Design

Two mechanisms work together. Neither one is enough by itself.

1. Lazy (passive) expiry. Each entry stores an absolute deadline expiresAt = now + ttl. Every get/has/ttl/expire first checks expiresAt <= now and, if it has passed, deletes the entry before answering. This means reads are always correct. It costs O(1) and needs no background work. It does nothing for keys that are never read again. Demo step 2 writes 10,000 such keys, and they stay in memory forever.

2. Active sampling reaper. activeExpireCycle() follows the classic Redis algorithm:

repeat:
    if no keys have a TTL:                 stop ("empty")
    sample 20 random keys that have a TTL; delete the expired ones
    if expired/20 <= 25%:                  stop ("threshold": the rest is probably clean)
    every 16 rounds, if elapsed >= budget: stop ("budget": continue next cycle)

Call it every 100 ms (Redis hz 10) with start(), or drive it by hand. Sampling is adaptive. A mostly clean keyspace costs a single 20-key probe per cycle. A keyspace that is full of garbage gets worked on until either the sample looks clean or the time budget runs out.

Data structures. A Map holds key -> {value, expiresAt}. Keys that have a TTL (Redis calls these "volatile" keys) are also kept in a dense array plus a key -> index map. That gives O(1) uniform random sampling and O(1) removal: swap the removed key with the last element, then pop. Persistent keys are never sampled, just as Redis samples only its expires dict.

Invariants (checked by a randomized test against a reference model):

1. A read never returns a value whose deadline has passed.
2. volatile and volatileIndex describe exactly the set of stored keys with a finite deadline.
3. Every stop reason is reachable, and one cycle does bounded work: at most budget plus 16 rounds of overshoot.

Injectable time and randomness. clock(), random() and the timer functions are all constructor or start() parameters. The demo charges 10 µs of simulated time per sample, which makes the budget visible without real sleeping.

Complexity

Failure modes and trade-offs

• 25% is a stop heuristic, not a bound. A cycle ends at the first sample that looks clean. When keys expire faster than one cycle can clean them, the stale share settles well above the threshold. In demo step 3, about 250 keys expire per 100 ms and the peak stale share is about 54%. A 10% threshold brings that down to about 39% but takes about 1.5x the samples. Less garbage costs more CPU.
• Expiry waves. If 50k keys share one deadline (for example, all written by a batch job with the same TTL), cleanup takes many cycles. The budget spreads that cost out (demo step 4: 20 cycles of at most about 26 ms each) instead of one 500 ms stall. The usual mitigation is to add jitter to TTLs at write time.
• Memory is not reclaimed right away. size includes dead keys. If the cache has a hard memory cap, eviction (LRU/LFU) must also consider expired keys. Redis's volatile-ttl policy does this.
• Clock jumps. A wall-clock step forward expires everything early, and a step backward keeps keys alive too long. Production code uses a monotonic clock (performance.now() or process.hrtime) for relative TTLs. Redis itself uses wall-clock deadlines, so that deadlines survive restarts and replication.
• Replicas. A replica cannot expire keys on its own schedule without diverging from the primary. Redis replicas do not reap. The primary sends an explicit DEL when a key expires, and since Redis 3.2 replicas hide logically expired keys from reads.

How production systems do it

• Redis ≤ 5: expireIfNeeded() on every key lookup, plus activeExpireCycle(). The SLOW cycle runs from serverCron at hz (default 10) with a budget of 25% of CPU, which is 25 ms per call. A FAST cycle of at most 1 ms runs in beforeSleep. Each cycle samples 20 keys per DB (ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP), repeats while more than 25% of them were expired, and checks the time every 16 iterations. This lab implements the SLOW cycle.
• Redis ≥ 6.0: rewrote the cycle to walk hash-table buckets of the expires dict with a cursor instead of sampling at random. It added active-expire-effort (1–10). Higher effort raises the keys per loop and the CPU share and lowers the acceptable stale share. At the default effort the target is about 10%.
• Memcached: lazy expiry on fetch, plus the LRU crawler, a background thread (on by default since 1.5) that walks the tails of the LRU lists and frees expired items.
• Caffeine (Java): variable per-entry expiry uses a hierarchical timer wheel, which gives O(1) scheduling and precise reclamation. Maintenance work is amortized onto reads and writes rather than run on a dedicated thread.
• DynamoDB TTL: a background scanner deletes expired items, usually within a few days. Until then reads can still return expired items, so queries should filter on the TTL attribute. Cassandra writes TTL'd cells as tombstones and purges them during compaction after gc_grace_seconds.

Extension exercises

1. Implement the Redis 6 approach. Instead of random sampling, keep a cursor into volatile and scan forward a fixed number of slots per round. Compare the peak stale share and samples with the demo workload.
2. Add a FAST cycle: run it on each set() or get() when the last SLOW cycle stopped with budget, capped at 1 ms and at most once per 2 ms.
3. Add maxKeys with LRU eviction and a volatile-ttl policy (evict the key closest to expiring). Which should go first, a stale key or the LRU key?
4. Replace sampling with a hierarchical timing wheel (like Caffeine or Kafka's purgatory) and measure the precision against CPU trade-off.
5. Add TTL jitter (±10%) on set and show how much it shortens the expiry wave in demo step 4.