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.2.0"

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

Basic Usage

use kestrel_timer::{TimerWheel, CallbackWrapper, TimerTask, CompletionReceiver};
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 = TimerTask::new_oneshot(Duration::from_secs(1), callback);
    let handle = timer.register(task);
    
    // Wait for completion
    let (rx, _handle) = handle.into_parts();
    match rx {
        CompletionReceiver::OneShot(receiver) => {
            receiver.wait().await;
        },
        _ => {}
    }
}

Batch Operations

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

let timer = TimerWheel::with_defaults();

// Batch create + register
let tasks: 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);
        }));
        TimerTask::new_oneshot(delay, callback)
    })
    .collect();

let batch_handle = timer.register_batch(tasks);

// Batch cancel
batch_handle.cancel_all();

Postpone Timer

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

let timer = TimerWheel::with_defaults();

let callback = Some(CallbackWrapper::new(|| async {
    println!("Original callback");
}));
let task = TimerTask::new_oneshot(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::{TimerWheel, TimerService, TimerTask, CallbackWrapper, TaskNotification};
use kestrel_timer::config::ServiceConfig;
use std::time::Duration;

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

// Batch schedule
let tasks: Vec<_> = vec![
    TimerTask::new_oneshot(Duration::from_millis(100), Some(CallbackWrapper::new(|| async {}))),
    TimerTask::new_oneshot(Duration::from_millis(200), Some(CallbackWrapper::new(|| async {}))),
];
service.register_batch(tasks).unwrap();

// Receive timeout notifications
let mut timeout_rx = service.take_receiver().unwrap();
while let Some(notification) = timeout_rx.recv().await {
    match notification {
        TaskNotification::OneShot(task_id) => {
            println!("One-shot task {:?} completed", task_id);
        },
        TaskNotification::Periodic(task_id) => {
            println!("Periodic task {:?} called", 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:

1. Short delay (< 5.12s) → Insert directly into L0 layer
2. Long delay (≥ 5.12s) → Insert into L1 layer
3. L1 task due → Automatically demote to L0 layer
4. 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

TimerTask:

• TimerTask::new_oneshot(delay, callback) - Create one-shot task
• TimerTask::new_periodic(initial_delay, interval, callback, buffer_size) - Create periodic task
• get_id() - Get task ID
• get_task_type() - Get task type
• get_interval() - Get interval for periodic tasks

TimerWheel:

• TimerWheel::with_defaults() - Create with default config
• TimerWheel::new(config) - Create with custom config
• register(task) - Register task
• register_batch(tasks) - Batch register
• cancel(task_id) - Cancel task
• cancel_batch(task_ids) - Batch cancel
• postpone(task_id, delay, callback) - Postpone task
• postpone_batch(updates) - Batch postpone

TimerHandle:

• cancel() - Cancel timer
• task_id() - Get task ID
• into_parts() - Get completion receiver and handle

TimerService:

• register(task) - Register task
• register_batch(tasks) - Batch register
• take_receiver() - Get timeout notification receiver
• cancel_task(task_id) - Cancel task
• cancel_batch(task_ids) - Batch cancel
• postpone(task_id, delay, callback) - Postpone task
• postpone_batch(updates) - Batch postpone
• 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

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

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 = TimerTask::new_oneshot(Duration::from_secs(30), callback);
    let handle = timer.register(task);
    
    // Cancel timeout when connection completes
    // handle.cancel();
}

2. Heartbeat Detection

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

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 = TimerTask::new_oneshot(Duration::from_secs(30), callback);
    service.register(task).unwrap();
}

3. Cache Expiration

use kestrel_timer::{TimerTask, CallbackWrapper};
use std::sync::Arc;
use std::time::Duration;

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 = TimerTask::new_oneshot(ttl, callback);
    self.timer.register(task);
}

4. Game Buff System

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

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 = TimerTask::new_oneshot(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

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

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 = TimerTask::new_oneshot(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