Ratas Hierarchical Timer Wheel

Ratas uses a hierarchical timer wheel to manage events scheduled for the future. A timer wheel is a ring buffer of linked lists of events. As time advances, a pointer moves through the buffer, executing events in the slots it passes.

To handle long-term scheduling, the implementation layers multiple wheels at different resolutions. When an event is scheduled too far in the future for the innermost (core) wheel, it is placed in an outer wheel. As the inner wheels rotate, events are 'promoted' from outer wheels to inner wheels until they reach the core wheel and are ready for execution.

Ratas uses a hierarchical timer wheel implementation to manage scheduled events. A timer wheel is a ring buffer of linked lists of events. As time advances, a pointer moves through the buffer, executing events in the slots it passes.

A hierarchical wheel layers multiple wheels at different resolutions.

• Core Wheel: The innermost wheel handles high-resolution (immediate) events.
• Outer Wheels: Events scheduled too far in the future for the core wheel are placed in outer wheels.
• Promotion: On each rotation of an inner wheel, one slot's worth of events is promoted to the next wheel up (e.g., from the second wheel to the core). This continues up the hierarchy.

Use these methods to inspect the state of the TimerWheel:

• now(): Returns the current tick value. Note that during a callback, this returns the tick the event was scheduled for.
• ticks_to_next_event(Tick max = ..., int level = 0): Returns the number of ticks until the next event. If max is provided, it returns the smaller of the remaining ticks or max. If no events are scheduled, it returns max. Returns 0 if there are unprocessed events from a previous advance() call that hit a max_execute limit.

Use ticks_to_next_event(max, level) to determine how many ticks remain until the next event is scheduled to execute.

• max: The maximum tick value to return. If no events are scheduled, it returns max.
• level: The hierarchy level to start searching from (defaults to 0).
• If advance() returned false in a previous call (meaning there is a backlog of unprocessed events), this returns 0.

If you want an event to invoke a specific member function of a class instance rather than a standalone callback, use MemberTimerEvent. This is useful for integrating timers directly into object lifecycles.

template<typename T, void(T::*MFun)() >
class MemberTimerEvent : public TimerEventInterface;

// Usage:
class Test {
  public:
    Test() : inc_timer_(this) {}
    void start(TimerWheel* timers) {
        timers->schedule(&inc_timer_, 10);
    }
    void on_inc() { count_++; }
  private:
    MemberTimerEvent<Test, &Test::on_inc> inc_timer_;
    int count_ = 0;
};

All events implement TimerEventInterface.

• Automatic Cancellation: Events are automatically canceled when they are destroyed.
• cancel(): Unschedules the event. It is safe to call this even if the event is already inactive.
• active(): Returns true if the event is currently scheduled.
• scheduled_at(): Returns the absolute tick value at which the event is set to execute.

To prevent a scheduled event from executing, call the cancel() method on the event object. It is safe to call cancel() on an event that is not currently scheduled (inactive).

Note: TimerEvent objects automatically call cancel() upon destruction, ensuring no dangling scheduled events.

Use schedule() to register a TimerEvent or MemberTimerEvent to be executed a specific number of ticks from the current time. The delta (number of ticks) must be greater than 0.

// Example: Scheduling a callback
typedef std::function<void()> Callback;
TimerWheel timers;
Callback my_cb = []() { /* do something */ };
TimerEvent<Callback> timer(my_cb);

// Schedule to run 5 ticks from now
timers.schedule(&timer, 5);

typedef std::function<void()> Callback;
TimerWheel timers;
int count = 0;
TimerEvent<Callback> timer([&count] () { ++count; });

timers.schedule(&timer, 5);
timers.advance(4);
assert(count == 0);
timers.advance(1);
assert(count == 1);

Use schedule_in_range() to schedule an event to occur within a specific window of ticks from the current time. The TimerWheel will choose a specific time within the [start, end] range to minimize the overhead of rescheduling or promoting the event through the hierarchy.

Constraints:

• start and end must be non-zero.
• end must be greater than start.

The advance(delta, max_execute) method moves the timer wheel forward by a specified number of ticks and executes any events scheduled for those ticks.

Key behaviors:

• Interleaving: You can limit the number of events executed in a single call using max_execute. If the limit is reached, the function returns false, and remaining events will be processed on the next call to advance().
• Safety: It is safe to cancel or schedule new events from within an event's callback. However, you must not call advance() from within an event callback.
• Ordering: Events are executed in order; all events for tick $X$ run before events for tick $X+1$.
• Observability: During a callback, now() returns the tick the event was scheduled for, not the current advanced time.

TimerEvent<CBType> is a concrete implementation of TimerEventInterface that takes a callback function of type CBType as a constructor parameter. When the timer triggers, the provided callback is executed.

typedef std::function<void()> Callback;
TimerEvent<Callback> timer([]() {
    // Your logic here
});