|
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 Efforts to Make a More Efficient TimerWhen 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 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 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 Basic Structure and Terms of TimingWheelAs shown in Figure 1, the basic structure of TimingWheel is a fixed-size circular array:
Figure 1: The Basic Structure of TimingWheel (http://www./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./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 Code 1 below shows the method of calculating the time slot to store a timeout job. Code 1: TargetSlot Calculation Method.
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 ( Effects of TimingWheelIn 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. As Javascript of a browser runs based on a single thread, if you use many timers in the development of an HTML5 game, there will be a noticeable deterioration in game rendering. 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. Reference
|
|
|
