- Notifications
You must be signed in to change notification settings - Fork0
ikod/timingwheels
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
Timing Wheels Implementation
Timing wheels is data structure to store and retrieve huge number of timers with O(1) complexity (at the cost of grouping them).
See
http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf
https://www.snellman.net/blog/archive/2016-07-27-ratas-hierarchical-timer-wheel/
https://cwiki.apache.org/confluence/display/KAFKA/Purgatory+Redesign+Proposal
Timing wheels do not operate on real time, but on abstract intervals (ticks). When scheduling a timer, you specify the number of ticks before it runs. The duration of the tick is set "outside" of the library and determines the accuracy with which the timers will be executed. Multiple timers can fall into one tick and will be saved and executed together.
This library require from Timer class to implement methodid() which must return some kind of unique ID. Type of this id can be some integer type or string.
Seehttps://ikod.github.io/timingwheels/ for actual docs
schedule(timer, t); - schedule timer for executiont ticks in the future. t must be > 0.
cancel(timer) - drop timer from wheels. You can't cancel cancelled timer.
advance(t) - advance wheels ont ticks. Advance on single tick will return all timers scheduled for the next tick (if any).t must be in interval (0, 256].
timeUnitNextEvent(Tick, now) return real time to next timer using provided tick duration.
Here is complete example with comments
import std; globalLogLevel = LogLevel.info;auto rnd =Random(142);/// track executionint counter; SysTime last;/// this is our TimerclassTimer {staticulong __id;privateulong _id;privatestring _name;this(string name) { _id = __id++; _name = name; }/// must provide id() methodulongid() {return _id; } }enum IOWakeUpInterval =100;// to simulate random IO wakeups in interval 0 - 100.msecs// each tick span some time interval - this is our link with time in realityauto Tick =5.msecs; TimingWheels!Timer w; w.init();autodurationToTicks(Duration d) {// we have to adjust w.now and realtime 'now' before scheduling timerauto real_now =Clock.currStdTime;auto tw_now = w.currStdTime(Tick);auto delay = (real_now- tw_now).hnsecs;return (d+ delay)/Tick; }voidprocess_timer(Timer t) {switch(t._name) {case"periodic":if ( last.stdTime==0) {// initialize tracking last =Clock.currTime-50.msecs; }auto delta =Clock.currTime- last; shouldApproxEqual((1e0*delta.split!"msecs".msecs),50e0,1e-1); writefln("@ %s - delta: %sms (should be 50ms)", t._name, (Clock.currTime- last).split!"msecs".msecs); last =Clock.currTime; counter++; w.schedule(t,durationToTicks(50.msecs));// rearmbreak;default: writefln("@ %s", t._name);break; } }// emulate some random initial delayauto randomInitialDelay = uniform(0,500, rnd).msecs;Thread.sleep(randomInitialDelay);//// start one arbitrary timer and one periodic timer//auto some_timer =new Timer("some");auto periodic_timer =new Timer("periodic"); w.schedule(some_timer,durationToTicks(32.msecs)); w.schedule(periodic_timer,durationToTicks(50.msecs));while(counter<10) {auto realNow =Clock.currStdTime;auto randomIoInterval = uniform(0, IOWakeUpInterval, rnd).msecs;auto nextTimerEvent = max(w.timeUntilNextEvent(Tick, realNow),0.msecs);// wait for what should happen earlierauto time_to_sleep = min(randomIoInterval, nextTimerEvent); writefln("* sleep until timer event or random I/O for %s", time_to_sleep);Thread.sleep(time_to_sleep);// make steps if requiredint ticks = w.ticksToCatchUp(Tick,Clock.currStdTime);if (ticks>0) {auto wr = w.advance(ticks);foreach(t; wr.timers) { process_timer(t); } }// emulate some random processing timeThread.sleep(uniform(0,5, rnd).msecs); }}
About
dlang timing wheels implementation