posted last year in Dev Platform category by Dongsoon Choi
Developers often use a timer when developing an application. A timer is especially needed when you process a timeout for sessions. With the TimerWheel data structure, you can perform this type of task more efficiently than you would with
java.util.Timer provided by JDK. However, there are some limitations which I will cover in this article. I will also explain how I used TimerWheel in multiple projects in our company.
Efforts to Make a More Efficient Timer
When you are developing an application, you will need to use a timer frequently. If you use an application with Java, you can implement a timer easily by using the
java.util.Timer provided by JDK. But when a timer needs to be used very frequently, it is difficult to get satisfactory performance with
java.util.Timer alone. This is because of the synchronization that occurs when you add or delete a timertask.
In 2010, when I was involved in a project at NHN to develop a Comet-based communication server, I applied a data structure called TimingWheel. TimingWheel is a timer implementation approach that can achieve much better performance than
java.util.Timer in some cases. But it is not possible to apply TimingWheel to every timer requirement.
At its core, TimingWheel is a data structure required to implement a timer used to process data retransfer and protocol recovery at the network protocol level. But it can be used for a variety of purposes depending on how it is applied.
When I was developing a Comet-based communication server, I considered using TimingWheel when I was seeking an efficient method to process tasks, such as ping/pong or timeout, that needed to be performed at a certain interval for each session (connection). At that time, the maximum number of sessions was 10,000, and as it was necessary to process various kinds of timeout, including ping/pong, re-connection and session expiration, for each session, I could not meet this requirement with
For this reason, I applied TimingWheel to process timeout more efficiently. TimingWheel is a data structure that enables you to handle a timer process at
O(1) time complexity.
Basic Structure and Terms of TimingWheel
As shown in Figure 1, the basic structure of TimingWheel is a fixed-size circular array:
Figure 1: The Basic Structure of TimingWheel (http://www.transitmagazine.com/lib0071.html).
Each bucket of the array is called a time slot, and contains a list of tasks to be processed when a timeout occurs. As its basic operation, TimingWheel circulates time slots at a slot interval, processing the content contained in the relevant time slot.
Figure 2 below shows the situation in which when the slot interval is 50 ms, the timeout job that will occur after 200 ms is registered (registration of a timeout job with the time interval of 200 ms).
Figure 2. The Process of Registering a Timeout Job (http://www.transitmagazine.com/lib0071.html).
As the slot interval is 50 ms, a timeout job for a timer that will occur after 200 ms should be stored in the slot that is located after four slots from the current cursor. In this way, you can store a timeout job with
O(1). As it moves to the next slot at a 50 ms interval, the cursor will arrive at the time slot that is located after four slots from its origin after 200 ms from the current time. If the cursor moves to the slot, TimingWheel will read the value of the time slot and process the timeout task. Whenever the cursor travels through the time slots, TimingWheel can process all the designated timeout tasks, and thus it is not necessary to conduct an additional inspection for timer processing during a timeout job, or in the logic used to process a timeout job. Therefore, you can implement a timer within the time complexity of
Code 1 below shows the method of calculating the time slot to store a timeout job.
Code 1: TargetSlot Calculation Method.
targetSlot = ( currentSlot + (timeInterval / slotInterval)) % timeSlotCount
In the project where TimingWheel was employed, I also used the Code 1 method to implement TimingWheel. Figure 3 shows a circular array which has been expressed more intuitively.
Figure 3: Operation of a Simple TimingWheel.
When I implemented TimingWheel in the project, I had a timeout job processed in a separate thread pool in order to have a separate thread to run TimingWheel and a thread to process a timeout job.
However, TimingWheel cannot be applied to every case in which a timer is required. As shown in Figure 2, there is a cap in max interval. If the number of time slots is 7 and the interval is 50 ms, as in Figure 2, you cannot register a value exceeding 350 ms.
If the interval is 1 second, you need a total of 4995 time slots (
60*60 + 23*60 + 15), a huge memory requirement to process the time interval of 1h 23m 15s without any overflow. To address this problem, of course, you may use Hashed TimingWheel or Hierarchical TimingWheel. But as you can't use TimingWheel for every timer requirement, it is advised to implement TimingWheel after determining the appropriateness of implementing TimingWheel in your project.
Effects of TimingWheel
In addition to the Comet project conducted in 2010, I also took part in two other projects where TimingWheel was implemented.
First, I applied TimingWheel to a project in which when multiple timeout jobs had to be simultaneously performed, the CPU usage, which had normally been only 1-2%, reached 100%. This high CPU usage occurred because there were many timeout jobs to be executed simultaneously, but after applying TimingWheel, timeout jobs could be performed stably.
I also applied TimingWheel to a project for developing an HTML5-based game.
In addition, as shown in Figure 4 below, HTML5 game engines, which are used in the development of games, provide a method for frame-based operation. If this method is used for timers in any area other than animation effects, the number of frames will drop due to excessive use of resources (see Figure 4).
Figure 4: Method of Frame Processing in HTML5 Game Engines.
As shown in C in Figure 5, if a timer that runs at 1-minute intervals uses OnAction, 3659 unnecessary calls will be wasted.
Figure 5: Examples of Unnecessary Use of Resources.
I applied TimingWheel to address this problem. I was able to meet the requirement with a single TimingWheel timer, and succeeded in maintaining the number of frames stably.
By Dongsoon Choi, Senior Software Engineer at Game Platform Development Center, NHN Corporation.
- Implement lower timer granularity for retransmission of TCP: http://www.ibm.com/developerworks/aix/library/au-lowertime/index.html
- Hashed and hierarchical timing wheels: efficient data structures for implementing a timer facility: http://dl.acm.org/citation.cfm?id=270876
- PPT Document of Reference 2: http://ebookbrowse.com/timingwheels-ppt-d195376642
- Real-Time Concepts for Embedded Systems (Chapter 11): http://www.transitmagazine.com/lib0069.html