From O(n) to O(1): Expiring 10M TTL Keys in Go(github.com/ankur-anand)

2 points by ankuranand 5 hours ago | 1 comments

  • ankuranand 5 hours 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