Kestrel Timer

High-performance async timer library based on Hierarchical Timing Wheel algorithm

📚 Table of Contents

Overview
Key Features
Quick Start
Architecture
Usage Examples
Configuration
Benchmarks
Use Cases
License

Overview

kestrel-timer is a high-performance async timer library based on the Hierarchical Timing Wheel algorithm, designed for Rust and Tokio runtime. It provides O(1) time complexity for timer operations and easily handles 10,000+ concurrent timers.

Core Advantages:

Hierarchical timing wheel architecture that automatically separates short-delay and long-delay tasks
2-12x performance improvement over traditional heap-based implementations
Support for timer postponement, batch operations, and completion notifications
Production-ready with comprehensive testing

Key Features

🏗️ Hierarchical Timing Wheel

Dual-layer design: L0 layer (high-precision short-delay) + L1 layer (long-delay) with automatic layering
Smart demotion: L1 tasks automatically demote to L0 layer when due
No round checks: L0 layer eliminates rounds checking for 90% of tasks

⚡ High Performance

O(1) time complexity: Insert, delete, and trigger operations are all O(1)
Optimized data structures: FxHashMap + parking_lot::Mutex
Bitwise optimization: Slot count is power of 2 for fast modulo operations
Large-scale support: Easily handles 10,000+ concurrent timers

🔄 Complete Features

✅ Async callback support (based on Tokio)
✅ Timer postponement (keep or replace callback)
✅ Batch operations (schedule, cancel, postpone)
✅ Completion notification mechanism
✅ TimerService (Actor-based management)
✅ Thread-safe

Quick Start

Installation

Add to your Cargo.toml:

[dependencies]

kestrel-timer = "0.1.0"

tokio = { version = "1.48", features = ["full"] }

Basic Usage

use kestrel_timer::{TimerWheel, CallbackWrapper};
use std::time::Duration;

#[tokio::main]
async fn main() {
    // Create timer with default config
    let timer = TimerWheel::with_defaults();
    
    // Create task + register
    let callback = Some(CallbackWrapper::new(|| async {
        println!("Timer fired!");
    }));
    let task = TimerWheel::create_task(Duration::from_secs(1), callback);
    let handle = timer.register(task);
    
    // Wait for completion
    handle.into_completion_receiver().0.await.ok();
}

Batch Operations

use kestrel_timer::CallbackWrapper;

let timer = TimerWheel::with_defaults();

// Batch create + register
let callbacks: Vec<_> = (0..100)
    .map(|i| {
        let delay = Duration::from_millis(100 + i * 10);
        let callback = Some(CallbackWrapper::new(move || async move {
            println!("Timer {} fired", i);
        }));
        (delay, callback)
    })
    .collect();

let tasks = TimerWheel::create_batch_with_callbacks(callbacks);
let batch_handle = timer.register_batch(tasks);

// Batch cancel
batch_handle.cancel_all();

Postpone Timer

let callback = Some(CallbackWrapper::new(|| async {
    println!("Original callback");
}));
let task = TimerWheel::create_task(Duration::from_millis(50), callback);
let task_id = task.get_id();
let handle = timer.register(task);

// Postpone and keep original callback
timer.postpone(task_id, Duration::from_millis(150), None);

// Postpone and replace callback
let new_callback = Some(CallbackWrapper::new(|| async {
    println!("New callback");
}));
timer.postpone(task_id, Duration::from_millis(200), new_callback);

TimerService Usage

use kestrel_timer::{TimerService, ServiceConfig};

let timer = TimerWheel::with_defaults();
let mut service = timer.create_service(ServiceConfig::default());

// Batch schedule
let callbacks = vec![
    (Duration::from_millis(100), Some(CallbackWrapper::new(|| async {}))),
    (Duration::from_millis(200), Some(CallbackWrapper::new(|| async {}))),
];
let tasks = TimerService::create_batch_with_callbacks(callbacks);
service.register_batch(tasks).unwrap();

// Receive timeout notifications
let mut timeout_rx = service.take_receiver().unwrap();
while let Some(task_id) = timeout_rx.recv().await {
    println!("Task {:?} completed", task_id);
}

service.shutdown().await;

Architecture

Hierarchical Timing Wheel Design

┌─────────────────────────────────────────────┐
│              L1 Layer (Upper)               │
│  Slots: 64 | Tick: 1s | Range: 64s          │
│              ↓ Demote to L0                 │
└─────────────────────────────────────────────┘
                    ↓
┌─────────────────────────────────────────────┐
│              L0 Layer (Lower)               │
│  Slots: 512 | Tick: 10ms | Range: 5.12s     │
│              ▲ Current Pointer              │
└─────────────────────────────────────────────┘

L0 Layer (Lower - High Precision):

Slots: 512 (default), Tick: 10ms
Coverage: 5.12 seconds
Handles 80-90% of short-delay tasks

L1 Layer (Upper - Long Duration):

Slots: 64 (default), Tick: 1000ms
Coverage: 64 seconds
Handles long-delay tasks with rounds mechanism

Workflow:

Short delay (< 5.12s) → Insert directly into L0 layer
Long delay (≥ 5.12s) → Insert into L1 layer
L1 task due → Automatically demote to L0 layer
L0 task due → Trigger immediately

Performance Optimizations

Hierarchical architecture: Avoids single-layer round checks, L0 layer requires no rounds checking
Efficient locking: parking_lot::Mutex is faster than standard Mutex
Bitwise optimization: Slot count is power of 2, uses & (n-1) for fast modulo
Cache optimization: Pre-compute slot masks, tick durations, and other frequently used values
Batch optimization: Reduce lock contention with smart small-batch handling

Usage Examples

Full API documentation at docs.rs/kestrel-timer

Main APIs

TimerWheel:

TimerWheel::with_defaults() - Create with default config
TimerWheel::new(config) - Create with custom config
create_task(delay, callback) - Create task (static method)
register(task) - Register task
register_batch(tasks) - Batch register
postpone(task_id, delay, callback) - Postpone task
postpone_batch(updates) - Batch postpone

TimerHandle:

cancel() - Cancel timer
task_id() - Get task ID
into_completion_receiver() - Get completion notification

TimerService:

create_task(delay, callback) - Create task (static method)
register(task) - Register task
take_receiver() - Get timeout notification receiver
cancel_task(task_id) - Cancel task
postpone(task_id, delay, callback) - Postpone task
shutdown() - Shutdown service

Configuration

Default Configuration

let timer = TimerWheel::with_defaults();
// L0: 512 slots × 10ms = 5.12 seconds
// L1: 64 slots × 1s = 64 seconds

Custom Configuration

use kestrel_timer::WheelConfig;

let config = WheelConfig::builder()
    .l0_tick_duration(Duration::from_millis(10))  // L0 tick
    .l0_slot_count(512)                            // L0 slots (must be power of 2)
    .l1_tick_duration(Duration::from_secs(1))      // L1 tick
    .l1_slot_count(64)                             // L1 slots (must be power of 2)
    .build()?;
let timer = TimerWheel::new(config);

Recommended Configurations

High Precision (Network Timeouts):

let config = WheelConfig::builder()
    .l0_tick_duration(Duration::from_millis(5))
    .l0_slot_count(1024)
    .l1_tick_duration(Duration::from_millis(500))
    .l1_slot_count(64)
    .build()?;

Low Precision (Heartbeat Detection):

let config = WheelConfig::builder()
    .l0_tick_duration(Duration::from_millis(100))
    .l0_slot_count(512)
    .l1_tick_duration(Duration::from_secs(10))
    .l1_slot_count(128)
    .build()?;

Benchmarks

Run Benchmarks

cargo bench

Performance Comparison

Compared to traditional heap-based (BinaryHeap) timer implementations:

Operation	Hierarchical Wheel	Heap Implementation	Advantage
Insert Single	O(1) ~5μs	O(log n) ~10-20μs	2-4x faster
Batch Insert 1000	~2ms	~15-25ms	7-12x faster
Cancel Task	O(1) ~2μs	O(n) ~50-100μs	25-50x faster
Postpone Task	O(1) ~4μs	O(log n) ~15-30μs	4-7x faster

Large Scale Testing

cargo test --test integration_test test_large_scale_timers

✅ 10,000 concurrent timers
✅ Creation time < 100ms
✅ All timers fire correctly

Use Cases

1. Network Timeout Management

async fn handle_connection(timer: &TimerWheel, conn_id: u64) {
    let callback = Some(CallbackWrapper::new(move || async move {
        println!("Connection {} timed out", conn_id);
        close_connection(conn_id).await;
    }));
    let task = TimerWheel::create_task(Duration::from_secs(30), callback);
    let handle = timer.register(task);
    
    // Cancel timeout when connection completes
    // handle.cancel();
}

2. Heartbeat Detection

let timer = TimerWheel::with_defaults();
let mut service = timer.create_service(ServiceConfig::default());

for client_id in client_ids {
    let callback = Some(CallbackWrapper::new(move || async move {
        println!("Client {} heartbeat timeout", client_id);
    }));
    let task = TimerService::create_task(Duration::from_secs(30), callback);
    service.register(task).unwrap();
}

3. Cache Expiration

async fn set_cache(&self, key: String, value: String, ttl: Duration) {
    self.cache.lock().insert(key.clone(), value);
    
    let cache = Arc::clone(&self.cache);
    let callback = Some(CallbackWrapper::new(move || {
        let cache = Arc::clone(&cache);
        let key = key.clone();
        async move {
            cache.lock().remove(&key);
        }
    }));
    let task = TimerWheel::create_task(ttl, callback);
    self.timer.register(task);
}

4. Game Buff System

async fn apply_buff(
    timer: &TimerWheel,
    player_id: u64,
    buff_type: BuffType,
    duration: Duration
) -> TaskId {
    let callback = Some(CallbackWrapper::new(move || async move {
        remove_buff(player_id, buff_type).await;
    }));
    let task = TimerWheel::create_task(duration, callback);
    let task_id = task.get_id();
    timer.register(task);
    task_id
}

// Extend buff duration
timer.postpone(task_id, new_duration, None);

5. Retry Mechanism

async fn retry_with_backoff(timer: &TimerWheel, operation: impl Fn()) {
    for retry in 1..=5 {
        let delay = Duration::from_secs(2_u64.pow(retry - 1));
        let callback = Some(CallbackWrapper::new(move || async move {
            operation().await;
        }));
        let task = TimerWheel::create_task(delay, callback);
        timer.register(task);
    }
}

License

This project is licensed under either of:

MIT License (LICENSE-MIT or http://opensource.org/licenses/MIT)
Apache License 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)

Acknowledgments

The timing wheel algorithm was first proposed by George Varghese and Tony Lauck in the paper "Hashed and Hierarchical Timing Wheels" (SOSP '87).

Full Documentation: docs.rs/kestrel-timer

kestrel-timer 0.1.1