3 ms·
I recently wrote about optimizing cache expiration for millions of TTL-based entries without melting the CPU. The naive approach — scanning every key every sec
by ankuranand 1y ago
I recently wrote about optimizing cache expiration for millions of TTL-based entries without melting the CPU.
The naive approach — scanning every key every second — works fine at small scale but collapses once you hit millions of entries.
So I implemented a Timing Wheel in Go — the same idea used in Kafka, Netty, and the Linux kernel — replacing the O(n) scan loop with an O(1) tick-based expiration model.
Here’s what I found when comparing both approaches at 10 million keys:
Avg Read Latency:
• Naive Scan → 4.68 ms
• Timing Wheel → 3.15 µs
Max Read Stall:
• Naive Scan → 500 ms
• Timing Wheel → ≈ 2 ms
At that scale, the naive loop stalls reads for half a second. The timing wheel glides through them in microseconds.
GitHub repo:
https://github.com/ankur-anand/taskwheel https://github.com/ankur-anand/taskwheel