2 ms·

From O(n) to O(1): Expiring 10M TTL Keys in Go

2 points by ankuranand 1y ago

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