A TimerWheel implementation in C# with flexible rescheduling

Recently we started a project that, among a lot of other stuff, required many objects to be scheduled (and rescheduled) for processing. Each of these objects could, potentially, require it's own interval; for example object A could be required to process each 10 seconds, object B could need an interval of 3600 seconds and object C could need to be processed each second. As long as there's a handful of objects, instantiating a timer for each object would be an option. But since our collection could grow to contain more than thousands of objects I felt that having a timer hanging around for each of those objects wasn't the best idea ever. This was just a gut-feel until I later stumbled upon a blog-post from one of my all-time favorite bloggers Raymond Chen. Although, apparently, it's okay to have many timers lying around I felt there had to be a more efficient way to solve my problem.


Of course we could find out if 2 or more items were scheduled to be processed at the same point in time but that would require a lot of processing each time an object had been processed and would only solve the problem partially and only when at least some object required processing at the same time. Then I thought about a single timer and having some sort of list or queue that I could "scan" each time the timer fired to find the objects to be processed and do the work. Again, this would require a lot of pointless processing each "tick" because there could be thousands of objects in the list and only 2 of them could require processing. So there would have to be some optimized list or list-of-lists or list-of-queues or something to optimize the retrieval of to-be-processed items so we wouldn't waste many CPU cycles each "tick" just figuring out which items to process before we could do the actual processing. There had to be a better way. And then I came up with a circular list and everything "clicked". It even turns out my idea wasn't new at all and has a name: a TimerWheel; it is described here and here but allow me to describe it here too

And since a picture is worth a 1000 words and conveys the idea much better, let's start with that:

TimerWheel (as seen elsewhere)

The idea is simple; you take one timer (represented by the red arrow) that, just like the second-hand on a watch, ticks each interval. Let's assume one-tenth of second, or 100ms. The wheel consists of, what I'd like to name, sectors. They have also been called sections, segments and "spokes". Each sector contains something, an item to be processed at that time, which might be a single item or a list or queue of items to process. The red arrow will make a complete "rotation" every 800ms in the above image. The number of sectors in the wheel is what we'll refer to as wheelsize.

By varying the interval and number of sectors you can control how long it takes the wheel to rotate and how many sectors will be processed per interval. For instance, if you make the wheel 3600 sectors large and set the interval to 1 second it will take exactly one hour for each sector to be processed once. If you make the wheel 10 sectors large and set the interval to 100ms it will take one second for the wheel to rotate once and, thus, process 10 sectors per second.

Let's start to code.

First things first: Interface time!

The interface is pretty simple; We need a way to start and stop the timer, hence the Start() and Stop() methods. We need something to indicate if the TimerWheel's internal timer is running, hence the Enabled property (which, for the Interface's purpose, we've left read-only). Once a wheel has been created we won't be able to re-size it; this brings all kinds of extra work to be done when implementing the wheel which I'll leave as an exercise for the reader. So a read-only WheelSize property will do. We might need to know "what time it is", or, at what tick the TimerWheel is currently at and possibly a way to "set the time". That is what the CurrentTick property is for. As a convenience we want to provide a way to reset the clock, or, CurrentTick so we require a Reset() method. The interval between the processing of two ticks needs to be set and, possibly, even changed later. And so we have an Interval property. Finally, each time the timer elapses we want to raise an event, the WheelTick event. The delegate for this event will be declared in an abstract base-class later on. Finally, we want the sectors to contain items of type something, so we'll tack a generic type parameter <T> on the ITimerWheel interface and because timers need to be disposed we'll promise to also implement IDisposable. Interface: done. We also stuff in a delegate for the WheelTick event we'll eventually need; more on that later.

We're ready to do some interface-implementing! We'll start with an abstract base-class  it will provide the base implementation of a TimerWheel from which we can derive specialized TimerWheels:

(Abstract) Implementation

Let's go over the code. The BaseTimerWheel<T> implements ITimerWheel<T>. Because we like constructors with as little as possible parameters we'll go ahead and define a default interval of 1 second, 1000ms that is, which felt most natural to me. We'll need an internal Timer, called _timer, a "second hand" to keep track of the current sector which we'll call _currenttick and here's something you might not expect: a DateTime variable _nexttick.

A timer will, over time, "drift" away from "wall clock time". Timers aren't guaranteed to fire at exactly interval X, the only guarantee you'll get is that they won't fire too soon. So when your timer, on average, fires at every 1015ms instead of every 1000ms, over a period of time you will "drift" from the actual time. What we'll do is use another approach: we'll use a one-shot timer (e.g.: elapses only once and then needs to be re-set) and, each tick, set it to elapse at a specific, "wall clock", time. When a timer fires 15ms late we'll set the next timer "15ms early" to correct for this "drifting". More on this later on in this article.

Then we create InternalSectors array; the actual sectors of the wheel of type T. So much for the private and protected stuff; let's get to the public stuff.

The CurrentTick property simply returns the backing-field and, when set, ensures that the tick is set within range (e.g. within 0 .. WheelSize). If not, we throw an ArgumentOutOfRangeException. The WheelSize property returns the actual size of the InternalSectors array; no backing-field so the value will always reflect the actual reality. The Enabled property is nothing more than a wrapper for our internal timer's Enabled property. We could consider to do the same for the Interval property, but there's a catch: since we'll be correcting the internal timer's interval to correct for drifting it won't reflect the actual ("desired") interval. That is why we have our "own" Interval property. You can modify this to be read/write, I prefer calling a Start() or Stop() method which, to me, conveys better that something will happen. Next we declare the Wheeltick event.

Constructors and methods

On to the constructor(s). The first constructor only accepts a wheelSize value and will assume the default interval of 1 second. The second constructor also accepts an interval and does the actual initialization of the timer and other internals as well as sanity-checking the wheelSize parameter. We'll leave it to the timer to throw when the interval parameter is invalid. The internal timer will be provided a method to call (Timer_Elapsed) when the timer...elapses. The final, or third, constructor also takes an IEnumerable<T> to initialize the sectors with. It will iterate the items and put each one in a consecutive sector, going round-and-round the wheel should the list of items be larger than the wheel's size (number of sectors).

I'll skip the Timer_Elapsed(), OnBeforeTick() and OnAfterTick() for a second; I'll get back to them later.

The Start() method determines when the next tick should occur, sets the internal timer's interval and starts it. It deliberately doesn't reset the CurrentTick property. That's what the Reset() method is for. This way, we have a way to "pause" the TimerWheel: simply by stopping and later starting it. The Stop() method is pretty boring; all it needs to do is stop the internal timer. The Reset() method is possibly even more boring because all it does is set the current tick to 0. This means we can call Reset() on an "Enabled" (or: "running") TimerWheel without stopping/starting it. We also implement IDisposable correctly and, because it's rather boilerplate code, we stuff it in a region. All we need to do is dispose our internal timer.

Back to the methods we skipped: Timer_Elapsed() is our private method that the timer will call each time it elapses. It will create a copy of the CurrentTick property to avoid race/re-entrant issues and a reference to the current sector. Next it will call into OnBeforeTick() which will handle raising the event. The event will contain the current tick being raised (when handling the event you can't really rely on the CurrentTick property of the TimerWheel because when your processing takes longer than one interval it will then reflect the next tick and not the tick you're currently processing) as well as the sector's content. When the event is raised the OnAfterTick() will be called which will advance the current tick by one, using the modulo operator to ensure our "second hand" neatly "wraps around" at the last sector to the first sector. Making these methods (OnBeforeTick() and OnAfterTick()) are virtual allows TimerWheel implementors to do some internal work just before and just after a WheelTick event is raised. You'll see later why this comes in handy. Finally, back in our Timer_Elapsed() method the next tick is calculated and the required interval to ensure the timer elapses at that time is calculated and the timer is (re)started. You'll notice that the minimum interval for the timer is set to 1. This means that, should processing a WheelTick for any reason take longer than the interval the next interval will be processed as soon as possible (1ms) but not immediately (0ms). Should some of these "slow intervals" happen in succession they will all be processed A.S.A.P. and, when the "pressure" drops the TimerWheel will, eventually, get back on track.

So take notice that, for "very demanding sectors" your TimerWheel can (and probably will) "drift off" as well as a "normal timer" will but it will try hard to keep on track and eventually will get back on track.

And that's it for our (abstract) base-class. We have an Interface and a base-class but still nothing to show for it. Let's get to it then!

Let's get concrete!

The actual TimerWheel<T> implementation is now a piece'o'cake. We inherit from BaseTimerWheel<T>, literally pass each constructor's parameters to the base constructor's parameters and all we do in this implementation is we expose the internal sectors as a read-only Sectors property so people can access each sector when desired. Note that the sectors themselves are read-only, not the sectors' contents!

All that's missing is the implementation of the WheelTickEventArgs<T>; the object that will be used to pass information to the user of the TimerWheel about the current tick.

This class inherits from EventArgs as we're supposed to. Other than that it only provides the CurrentTick (the "time", or tick, when the WheelTick event was raised) and the contents of the sector that is associated with that tick in the SectorContent property.

That's it. We have implemented a basic TimerWheel. But... we need to implement another requirement: each item can require processing at it's own interval. Our current wheel keeps each item in it's own sector causing each item to be processed exactly once per 'rotation'. To the batcave!

Let's go specialist!

So, we require a special implementation of a TimerWheel that, for each "tick", processes the sectors' item(s) and then reschedules these items at a later time, having the item specify when exactly it wants to be rescheduled. And, thus, we need a way of asking the item when it wants to be rescheduled; we want to be able to query it's "interval", specifically when it wants to be rescheduled. Let's define an interface for that:

Not much to see here; when creating our "rescheduling timerwheel" we'll require objects to implement this interface and that's pretty much it. One thing to note is that the Rescheduling interval is actually the number of sectors the item will move forward (or back...) each time it has been processed. When the wheelsize is 5 and the object is first scheduled at sector 0 with a rescheduling interval of 2 it will be processed in tick 0, 2, 4, 1, 3, 5, 0, ... and so on. When the rescheduling interval is set to 0 (or 5 or a multiple of 5 for the current wheelsize) the item will effectively not move. And when a negative rescheduling interval of -2 is used the item will be processed in tick 0, 3, 1, 4, 2, 0, ... which equals a rescheduling interval of 3. It's a matter of perspective

ReschedulingTimerWheel: Interface and implementation

There's a "gotcha" when implementing our ReschedulingTimerWheel; when we put an item in our ordinary TimerWheel we'll know exactly where we put it and so it will be easy to access the item by accessing the Sectors property of the TimerWheel. However, in our ReschedulingTimerWheel the items will be constantly moving around. So we'll need a form of object tracking. And this means we need to watch every object going in or out of our TimerWheel so we can keep our administration. This means we'll need to expose methods to add/remove items (and, preferrably, batches of items; the same way a List<T> exposes Add() and AddRange() methods). Another "nice to have" would be the option to reschedule an item at our own discretion when the current tick is 2 on a wheelsize of 10 and the item is scheduled to be processed at 5 we might want to move it forward or postpone it's processing; a method to be able to do this would come in handy. And so here's the interface for our ReschedulingTimerWheel:

Next up: implementing the ReschedulingTimerWheel:

First thing to notice is that we use a generic type constraint to constrain types in the wheel to the ones that implement ITimerWheelReschedulableObject. Another thing to notice is that we wrap each type for each sector in a HashSet. This is done because, when we reschedule an item to be processed at a later time there is no guarantee that the sector is empty; it might be used by another item. A List<T> or Queue<T> would also work, I chose to use a HashSet<T> because we don't really care about order of the items in the sector; we just want them to be processed at the specific tick for that sector. Then there's a _syncroot object. This object will be used to lock on when we're busy "administering" objects in our TimerWheel. We track objects in the TimerWheel in _objecttracker by adding them to a Dictionary<T, int>. The object itself will function as key, the corresponding value will reflect the current sector the object is in.

Then there's two constructors; all they do is "waterfall" into the third constructor. The third constructor creates the wheel with the specified size and (default) interval and next puts a HashSet<T> in each sector. If any items are passed into this constructor each item will be added to a consecutive sector's HashSet, going round the wheel when required. Nothing too new here. The fourth constructor accepts an IEnumerable<IEnumerable<T>>; for example a List-of-arrays-of-T. Each array in this List will be put (or rather: added) in the corresponding sector. This is mostly just a convenience-constructor.

Now it will become clear why the OnBeforeTick() in our base-class was virtual; we want to do some work in our specialized TimerWheel before the event is raised. Most importantly we want to lock to avoid someone messing with our items in the sectors while we're working on them. Next we create a copy of the sector, raise the event passing the copy of the sectors' content and clear the sector that was just processed. Next, we'll use our copy to iterate over the items and put them in their new sectors keeping track of their new positions in our objecttracker. When we're done we release the lock. All magic has happened and we're ready for a new tick. No need to override the OnAfterTick in this case; we'll let the CurrentTick advance as usual.

The Add() and Remove() methods are simply wrappers that accept a single item of T and put them in the specified sector using the AddRange() and RemoveRange() methods. This is done to keep things DRY. These methods also take a lock since they'll be modifying the internal sectors. The AddRange() will check to ensure the RescheduleInterval is not larger than the wheel's size; that would cause undesired behaviour: when the wheelsize is 5 and you would use a rescheduleinterval of 7 the effective interval will be 2 since you would always schedule "once around the wheel + 2".

The AddRange() and RemoveRange() also take care of updating the internal objecttracker. The RemoveRange() will find items in the correct sectors' HashSet using the objecttracker and remove it from that sector. And then there's only one method left: Reschedule(). This method will take an item out of the wheel using the Remove() method and re-add it using the Add() method (again: keeping things DRY) at the specified offset of the current tick.

A positive offset will cause the item to be scheduled ahead of the current tick; a negative offset will schedule the item back relative to the current tick. An offset of 0 will cause the item to be scheduled at the current tick, but note that the current tick will always have been processed so that effectively the item will be scheduled an entire iteration later. If you want the item to be processed as soon as possible you need to reschedule it with an offset of 1.

And that's it. We have a pretty generic TimerWheel and ReschedulingTimerWheel, nice interfaces and neatly implemented all requirements we started off with. I can now create an 8-hour-1-second-interval wheel (28000 sectors) and schedule thousands of objects with different rescheduleintervals to be processed on the wheel or a 6-sector wheel with 10 minute interval with 6 items on it to be processed. There is room for a bit of polishing up, which I'll do shortly, and then we're done. Stuff it in a NuGet package and let others enjoy our hard work too!

I'd like to hear your remarks, comments and critisisms! So please, do leave a comment!  You might also want to take a peek at the comments over at Reddit.

Happy coding!