I was working my colleague to understand a fix we did recently and I heard a DS/Algo called Hashed Timing Wheel (it is being used in Netty server). It got me curious and I did some amount of researching to understand what it is.
The problem statement it solves is this:
We make a lot of Asynchronous operational call in our code. We cannot forever wait for the result, so we need someone to call expires after a specific wait time. How to you do it effectively is the problem.
A simple approach would be to put the tasks in a List. When we use a list, the following are the operations we do.
- When adding a new task, hold a lock on the list and add it.
- For every tick, the Timeout manager hold a lock and scan through the List, decrement toExpire time for the tasks and expire tasks what need to expire.
For a smaller system, this will work, But for a distributed system, this setup will start to fail due to the number of locks we acquire and growing length of the List.
What we need is a way in which the Timeout manager can directly go and find out the expired tasks and expire them.
Hashed Timing Wheel as saviour
The Approach of Hashed Timing Wheel is simple. We hold a hash map, having 60(No of seconds in a minute) slots. Each slot will contain the list of tasks to be expired on that second.
We will have the following operations on the map.
- When we add a new task, we compute taskToExpire mod 60, go to that key, hold the lock, take the list out and add tuple (counter, task) to the list where the counter is the timeToExpire / 60.
- For every sec, we go the key for that second and hold the lock on the list and scan through the list,expire all the task which have counter 0 and decrease the counter of rest of the task tuples.
Hashed Timing Wheel data structure is better as it holds lock only on that sec value of the list, and the TimeOut Manager exactly knows which tasks are supposed to the expired. I did a simple implementation of it here. That research paper can be found here .
