1 introduction

Before we get down to business, have a few small talk. Some people say that computer science, the software direction of the end of the study is mathematics, hardware direction of the end of the study is physics, the most relaxed is the group of users in the middle, can not understand physics, do not understand mathematics, still can use the computer as a tool to make a living. This rule has a general adaptation, look at the “timer” example, to the application layer research, Quartz, Spring Schedule and other frameworks; To distributed research, there are SchedulerX, ElasticJob and other distributed task scheduling; Look at the bottom implementation, and there are a variety of timers to achieve the principle of the program, work efficiency, data structure can be explored… Simple use of a framework, does not reflect the level of the individual, how to form a degree of differentiation with others? I think there’s at least one direction to go:

  1. Delve into the implementation principles of an existing framework, such as reading source code
  2. It is a good extension of a traditional technology in the distributed domain. Many mature traditional technologies may work well in a stand-alone work well, but distributed scenarios require a lot of additional consideration.
  3. From the point of view of the designer, if you design a wheel from scratch, how to use the appropriate algorithm, data structure, to achieve it.

Returning to the main theme of this article, I will first focus on the third topic: designing and implementing a timer, what algorithms can be used, and what data structures to use. Let’s move on to the first topic: some good implementation of timers.

2 Understanding timers

Timers are used in many scenarios, such as

  1. When a TCP persistent connection is used, the client needs to periodically send heartbeat requests to the server.
  2. The financial system generates statements at the end of each month.
  3. Turn on the kill switch regularly at 0 o ‘clock of double 11.

Timers, like water and air, are used in various scenarios. Timed tasks can be triggered after a fixed time, at a fixed frequency, or at a certain time. What is a timer? It can be understood as a data structure like this:

The user view supports the following operations: NewTask: adds a NewTask to the task set Cancel: cancellations a task. In the task scheduling view, the user view supports the following operations: Run: executes a scheduled task that is due

To determine whether a task is due, the polling method is basically adopted to check whether the latest task is due every other time slice. In addition, after the occurrence of NewTask and Cancel, the task scheduling policy will also be adjusted.

After all, timers are implemented by thread polling.

3 Data Structure

We mainly measure NewTask, Cancel, and Run, and analyze the time/space complexity of their use of different data structures.

3.1 Bidirectional ordered list

In Java, LinkedList is a natural two-way LinkedList

NewTask: O(N) Cancel: O(1) Run: O(1) N: number of tasks

NewTask O(N) is easy to understand, according to expireTime to find the appropriate location; Cancel O(1), the task will hold the reference of its own node when it cancels, so there is no need to find its position in the linked list, and the deletion of the current node can be realized. This is also the reason why we use bidirectional linked list instead of ordinary linked list. Run O(1), since the entire two-way list is ordered based on expireTime, the scheduler only needs to poll for the first task.

3.2 the heap

In Java, the PriorityQueue is a natural heap that can be used to determine the priority of its elements using the Comparator passed in.

NewTask: O(logN) Cancel: O(logN) Run: O(1) N: number of tasks

ExpireTime is the comparison parameter of Comparator. NewTask O(logN) and Cancel O(logN) correspond to the time complexity of inserting and deleting elements in the heap, respectively; Run O(1), the little root heap formed by expireTime, we can always find the fastest expiring task at the top of the heap.

Compared with bidirectional ordered lists, NewTask and Cancel form a trade off, but considering that in reality, there are not many scheduled task cancellations, so the timer implemented by the heap is better than bidirectional ordered lists.

3.3 time round

Optimized for I/O timeout scheduling scenarios, Netty implements the HashedWheelTimer time round algorithm.

HashedWheelTimer is a circular structure, which can be likened to a clock. There are many buckets on the clock face. Each bucket can store multiple tasks. And execute all tasks that expire on the corresponding bucket. The task is modded to determine which bucket it should go into. Similar to HashMap, newTask corresponds to put and uses List to resolve Hash conflicts.

In the figure above, assuming that a bucket is 1 second, the pointer rotates once to represent a period of 8s. Assuming that the current pointer points to 0, a task to be executed after 3s needs to be scheduled, which should obviously be added to the box (0+3=3), and the pointer can be executed after 3 times. If the task is to be executed in 10 seconds, it should wait until the pointer has completed a round of zero 2, so put 2 in and save round (1) to the task. If the round value is 0, the round value of other bucket tasks is reduced by 1.

Looking at bucket5 in the picture, we can see that bucket5 is in theAfter that, there are two tasks to perform inThere is a task to be performed.

NewTask: O(1) Cancel: O(1) Run: O(M) Tick: O(1) M: bucket, M ~ N/C, where C is the number of buckets in a single round. In Netty, the default value is 512

The complexity of the time round algorithm may be expressed incorrectly and is difficult to calculate. It is only for reference. In addition, its complexity is affected by multiple tasks being assigned to the same bucket. And there’s the overhead of a rotating pointer.

The traditional timer is task-oriented, while the time wheel timer is bucket oriented.

Netty’s HashedWheelTimer is constructed with two important parameters: tickDuration and ticksPerWheel.

  1. tickDuration: indicates the time represented by a bucket. The default value is 100ms. Netty does not need to change this parameter in most scenarios.
  2. ticksPerWheel: Specifies the number of buckets in a round. The default value is 512. If there are many tasks, increase this parameter to reduce the probability that tasks are assigned to the same bucket.

3.4 Level time wheel

Kafka optimizes the time wheel algorithm and implements the hierarchical time wheel TimingWheel

If the time span and number of tasks are large, the traditional HashedWheelTimer will result in a large round of tasks and a long List of tasks for a single bucket that will last for a long time. At this time, the roulette wheel can be classified by time granularity:

Now, in addition to maintaining the round on the current roulette, each task also calculates the round on all lower roulette disks. When the round of this layer is 0, the task is sent down to the lower wheel according to the lower round value, and is eventually executed on the lowest wheel.

NewTask: O(H) Cancel: O(H) Run: O(M) Tick: O(1) H: number of tiers

Consider a scheduled task timed for 3 days, 10 hours, 50 minutes, and 30 seconds, in a single-layer time wheel with tickDuration = 1s, through:A flick of the secondary pointer can be performed. But in a four-tiered time wheel of wheel1 tickDuration = 1 day, wheel2 tickDuration = 1 hour, wheel3 tickDuration = 1 minute, wheel4 tickDuration = 1 second, You just have to go throughThe flick of the secondary pointer!

Compared with single-layer time wheel, hierarchical time wheel has obvious advantages when the time span is large.

4 Common Implementations

4.1 the Timer

The Timer in the JDK was a very early implementation, and it’s not a good design at this point.

// Run a scheduled task that will be executed one second later
Timer timer = new Timer();
timer.schedule(new TimerTask() {
    @Override
    public void run(a) {
        // do sth}},1000);
Copy the code

The core of using Timer to realize task scheduling is Timer and TimerTask. The Timer is responsible for setting the start and interval execution time of the TimerTask. The user simply creates a TimerTask inheritance class, implements its own run method, and throws it to the Timer to execute.

public class Timer {
    private final TaskQueue queue = new TaskQueue();
    private final TimerThread thread = new TimerThread(queue);
}
Copy the code

TaskQueue is a simple heap implemented using an array. Another notable property is TimerThread, which uses a single thread responsible for polling and executing the task. The advantage of Timer is that it is easy to use, but also because all tasks are scheduled by the same thread, the whole process is executed in serial. Only one task can be executed at a time, and the delay or exception of the previous task will affect the subsequent tasks.

If currentTime is less than heapfirst. executionTime, you can wait(executionTime – currentTime) to reduce unnecessary polling time. This is a commonly used optimization.

  1. TimerCan only be scheduled by a single thread
  2. TimerTaskAn exception that occurs inTimerThe execution.

Because of these two defects, JDK 1.5 supports a new timer scheme, ScheduledExecutorService.

4.2 ScheduledExecutorService

// Run a scheduled task that will be executed one second later
ScheduledExecutorService service = Executors.newScheduledThreadPool(10);
service.scheduleA(new Runnable() {
    @Override
    public void run(a) {
        //do sth}},1, TimeUnit.SECONDS);
Copy the code

Compared with Timer, ScheduledExecutorService solves the blocking problem of scheduling multiple tasks with the same Timer, and the exception of the task does not interrupt ScheduledExecutorService.

The ScheduledExecutorService provides two periodic scheduling methods: ScheduleAtFixedRate and ScheduleWithFixedDelay.

ScheduleAtFixedRate The schedule execution time is an interval of time since the last task is started. That is, the execution time is:..,…

ScheduleWithFixedDelay The execution time of each task is an interval since the end of the last task. That is, the execution time of each task is:...

ScheduleAtFixedRate schedules tasks at a fixed interval, and ScheduleWithFixedDelay schedules tasks at an unfixed interval, depending on the duration of each execution.

The underlying data structure of ScheduledExecutorService is PriorityQueue, and the task scheduling mode is common.

4.3 HashedWheelTimer

Timer timer = new HashedWheelTimer();
// Equivalent to Timer Timer = new HashedWheelTimer(100, timeunit.milliseconds, 512);
timer.newTimeout(new TimerTask() {
    @Override
    public void run(Timeout timeout) throws Exception {
        //do sth}},1, TimeUnit.SECONDS);
Copy the code

The data structure inside HashedWheelTimer in Netty was described earlier. The default constructor configures a polling period of 100ms and a bucket count of 512. It is used in a very similar way to the JDK Timer.

private final Worker worker = new Worker();// Runnable
private final Thread workerThread;// Thread
Copy the code

Due to space constraints, I’m not going to do a detailed source analysis, but the above two lines of code from HashedWheelTimer illustrate the fact that HashedWheelTimer internally also uses a single thread for task scheduling. Similar to the Timer of JDK, the problem exists that the execution time of the previous task is too long, and the execution of subsequent scheduled tasks is affected.

Understanding ticksPerWheel and tickDuration in HashedWheelTimer and configuring them reasonably can enable users to get the best performance in the appropriate scenario.

5 Best Practices

5.1 Selecting an Appropriate Timer

Needless to say, the JDK’s Timer uses the narrowest scenarios and can be replaced by the latter two. How to choose between ScheduledExecutorService and HashedWheelTimer requires a simple comparison between scenarios:

  1. ScheduledExecutorServiceIs task-oriented. When the number of tasks is very large, using the heap (PriorityQueue) to maintain the addition and deletion of tasks will lead to performance degradation, andHashedWheelTimerFor buckets, set a reasonable ticksPerWheel, tickDuration, which is not limited by the number of tasks. So in a lot of tasks,HashedWheelTimerIt can show its advantages.
  2. On the other hand, if the task is small,HashedWheelTimerThe internal Worker thread will still keep moving the pointer, which is not particularly performance consuming, but at least we can’t say:HashedWheelTimerMust be better thanScheduledExecutorServiceGood.
  3. HashedWheelTimerSince you have an array of buckets, this takes up a little more memory.

This comparison brings us to a best practice: performance gains from using HashedWheelTimer over a large number of tasks. For example, the heartbeat timing task in the service governance framework, where there are many service instances, each client needs to send a heartbeat regularly, and each server needs to check the connection status regularly, is a very suitable scenario for using HashedWheelTimer.

5.2 Single Thread and Service Thread Pools

Note that HashedWheelTimer uses a single thread to schedule tasks. If the tasks are time-consuming, a business thread pool should be set and the actual execution of the task should be given to the business thread pool using HashedWheelTimer as a timing trigger.

If all tasks meet the following requirements: taskNStartTime – taskn-1startTime > taskn-1costtime, that is, the interval between any two tasks is less than the execution time of the first task, then do not worry about this problem.

5.3 Global Timer

In practice, HashedWheelTimer should be used as a global task scheduler, such as static. Keep in mind that HashedWheelTimer corresponds to a thread. If you instantiate HashedWheelTimer each time, first of all, there will be too many threads and second, the time wheel algorithm will become completely meaningless.

5.4 Set proper parameters for HashedWheelTimer

TicksPerWheel and tickDuration are particularly important. TicksPerWheel controls the number of buckets in the time wheel and determines the probability of conflict. TickDuration determines the frequency of pointer towing. On the one hand, it determines CPU consumption. When the number of tasks is very large, consider increasing ticksPerWheel; The tickDuration can be increased appropriately when time precision is not required, but in most cases, the Care parameter is not required.

5.5 When to Use hierarchical Time Wheel

When the time span is large, improving the tickDuration of the single-layer time wheel can reduce the idling times, but it will lead to low time accuracy. The hierarchical time wheel can avoid both the accuracy reduction and the idling times of the pointer. If there are scheduled tasks with a long time span, they can be assigned to the hierarchical time round for scheduling. In addition, it is also possible to instantiate multiple single-layer time wheels with different functions, such as dayHashedWheelTimer, hourHashedWheelTimer, minHashedWheelTimer, and configure different tickDuration according to timing accuracy. This method is low, But it’s a solution. Netty’s HashedWheelTimer is designed specifically to optimize I/O scheduling. The scenarios are limited, so hierarchical time rounds are not implemented; In Kafka timers have a wider range of applications, so hierarchical time wheels are implemented to cope with more complex scenarios.

6 References

[1] www.ibm.com/developerwo…

[2] Novoland.github. IO/concurrency /2014/07/…

[3] www.cs.columbia.edu/~nahum/w699…

Welcome to follow my wechat official account: “Kirito technology sharing”, any questions about the article will be answered, bring more Java related technology sharing.