TimingWheel: Learning Hierarchical Timing Wheels with LLMs

Project Goal

This project demonstrates how hierarchical timing wheels work for efficient cache expiration. Built iteratively with the help of Claude Code, it transforms an O(N) naive cleanup approach into an O(1) amortized solution for handling TTL-based expirations up to 24 hours.

How Timing Wheels Work

Core Concept

A timing wheel is a circular buffer where each "slot" represents a time bucket. Instead of scanning all entries to find expired ones (O(N)), timing wheels achieve O(1) insertions and amortized O(1) cleanup by organizing entries by their expiration time.

Single-Level Wheel

• Structure: Circular array of slots, each representing a fixed time duration (e.g., 1 second)
• Insertion: Calculate target slot based on TTL, append entry to that slot's list
• Cleanup: Background goroutine "ticks" the wheel, processing only the current slot's entries
• Limitation: Maximum TTL = slotCount × tickDuration (e.g., 60 seconds for 60 slots × 1s)

Hierarchical Wheels

To handle longer TTLs efficiently, multiple wheels cascade:

• Seconds Wheel: 60 slots × 1s = 60s capacity
• Minutes Wheel: 60 slots × 1min = 3600s (1 hour) capacity

Cascading Process:

1. Entry with 90s TTL → Minutes wheel (1 minute) + Seconds wheel (30s remaining)
2. After 1 minute → Cascades to seconds wheel
3. After 30 more seconds → Expires

Key Benefits

• O(1) Insertion: Direct slot calculation
• Bounded Memory: Only current slot entries processed per tick instead of iterating the entire cache for expiring entries

WheelCache: Timing Wheel Integrated Cache

The WheelCache combines lazy expiration (for consistency) with timing wheel background cleanup (for efficiency). This hybrid approach ensures:

• Consistent Reads: Get() always checks expiration timestamps
• Efficient Cleanup: Background wheel processes expirations without blocking
• Thread Safety: RWMutex allows concurrent reads during cleanup

Key Features

• O(1) amortized operations
• Handles TTLs up to 1 hour -> 60 mins -> 3600 seconds
• Lazy + proactive expiration hybrid
• Graceful shutdown support

Usage

cache := cache.NewWheelCache()
cache.Set("key", "value", 30*time.Second)
value, found := cache.Get("key") // Returns false after expiration
cache.Stop() // Cleanup

WheelCache Implementation Files

Core Cache

• cache/wheel_cache.go - Main cache implementation with timing wheel integration
• cache/cache_with_expiry.go - CacheEntry struct with expiration timestamps

Timing Wheel Components

• timingwheel/wheel.go - Single-level timing wheel (60 slots × 1s)
• timingwheel/entry.go - Basic entry structure passed to callbacks
• timingwheel/hierarchical_wheel.go - Multi-level wheel system (seconds + minutes)

Testing

• cache/wheel_cache_test.go - Unit tests for cache operations and expiration

Planning & Documentation

• IMPLEMENTATION_PLAN.md - Detailed development roadmap and learning progression

Reference Blog:

https://medium.com/@ankur_anand/killing-o-n-how-timing-wheels-expire-10-million-keys-effortlessly-in-golang-9a6b8709fd91