Crossoverjie. Top
preface
Before the festival, there was an updated article about timed task named “Time Wheel of Delayed Message”. Some friends proposed that common timed task schemes could be introduced completely, so this article was created.
Timer
This meeting will mainly discuss the most commonly used schemes. The first one is Timer Timer, which can run tasks after a specified time or periodically. It’s also very simple to use:
This allows you to create two simple scheduled tasks that run after 3s/5s.
It’s really simple to use, but it has a lot of bugs, and the first thing you need to understand is how it works.
Realize the principle of
For scheduled tasks to be scheduled at a given time, we need a sortable container to hold these tasks.
A TaskQueue is built into the Timer to store all scheduled tasks.
In essence, it is a minimal heap with an array to implement, it can be written each time the scheduled task is sorted according to the execution time, ensure that the task execution time at the top of the heap is minimal.
In this way, when tasks need to be executed, only the tasks on the top of the heap need to be taken out each time, so it is very efficient to take out tasks
It is easier to understand with the code:
When writing a task, some basic attributes are stored (task scheduling time, period, initialization task status, etc.). Finally, the task is written to the built-in queue.
At the heart of the task writing process is the fixUp() method, which compares the written task from the middle of the queue to the previous task by execution time, continuously forward.
If this time is the earliest executed, it will eventually be moved to the top of the heap.
And you can see that through this processTimerThe time complexity of a new task is
If you look at how it performs the task, it actually starts a thread in the background when it initializes the Timer to get the task from the TaskQueue and schedule it.
So we just look at his run().
It is clear from this code that this thread is constantly being called
task = queue.getMin();Copy the codeTo get the task, and finally use task.run() to execute the task.
As you can see from the getMin() method, the top of the heap is fetched each time.
The task can be run as soon as its execution time meets the requirement, and it needs to be removed from the queue of the minimal heap implementation; That is, the queue.removemin () method called.
In fact, its core principle is similar to the write task, but the bottom of the heap to the top of the heap, and then compare tasks in order to move back until they reach the appropriate position.
As you can see from the write and delete tasks, the minimum heap is relatively ordered but not absolutely ordered.
Read the source code, nature can also come to its problems.
- There is only one thread for scheduling tasks in the background. As a result, tasks are blocked. Once the execution period of one task is too long, other tasks will be affected.
TimerNo other exceptions are caught themselves (only that they areInterruptedException), if the task is abnormal (such as null pointer), subsequent tasks will not be executed.
ScheduledExecutor
Since there are some problems in the Timer, so in the process of contract awarding in JDK1.5 and introduced a ScheduledThreadPoolExecutor instead of the Timer, from its own package path can also see that it itself is to support task to execute concurrently.
Let’s take a look at the class inheritance diagram:
You can see that it is also a thread pool, inheriting ThreadPoolExecutor.
As you can see from its constructor, it essentially creates a thread pool, but the blocking queue in this thread pool is a custom DelayedWorkQueue (the same as TaskQueue in Timer).
A new task
When we write a scheduled task, we first write the task to the DelayedWorkQueue, which is essentially the smallest heap implemented using an array.
The offer() method is eventually called when a new task is created, where siftUp() is used to move the written task to the top of the heap.
The principle is similar to the previous Timer, except that it is sorted by a custom comparator, which is obviously compared by the execution time of the task.
Run the task
So this allows tasks to be placed in order of execution time on a blocking queue in the thread pool.
It’s time to review the thread pool:
In the thread pool, the background thread at initialization is used to fetch tasks from the blocking queue, except in this case the blocking queue is DelayedWorkQueue, so the tasks must be fetched first in order of execution time.
Similar to Timer, finishPoll() is called after the task is fetched to delete it, and the last task is raised to the top of the heap and then moved to the appropriate position.
The consumption of the DelayedWorkQueue is triggered when a task is written.
The task is essentially written by calling ThreadPoolExecutor’s addWorker(), so consuming DelayedWorkQueue is also triggered there.
This is more about thread pools. If you don’t know much about thread pools, you can look at the thread pools summarized earlier.
- Thread pools are not as simple as you might think
- Thread pools Are Not as simple as you Think (continued)
After reading the principle, you can see the advantage of Timer.
| Timer | ScheduledThreadPoolExecutor |
|---|---|
| Single thread blocking | Multi-threaded tasks do not affect each other |
| The task stops when an exception occurs | Depending on the thread pool, an exception in a single task does not affect other tasks |
So when there is a need for timed tasks, it is obvious that timers should be eliminated.
Time round
The last one is a timed task based on a time wheel, which I covered in detail in my last post, Time Wheel for Delayed Messages.
Through source code analysis we can also do a comparison:
| ScheduledThreadPoolExecutor | Based on time wheel | |
|---|---|---|
| Write the efficiency | Based on the minimum heap, more tasks are less efficient |
与 HashMapWrite similar, very efficient. |
| Execution efficiency | It’s efficient to take out the first one every time |
Toggle one pointer fetching task per second |
Therefore, it is recommended to use the time wheel for high write efficiency when there are many writing tasks.
But when the task is seldom actually ScheduledThreadPoolExecutor also good, after all, it will not use to touch every 1 second pointer CPU, but once there is no task thread will block until there is a new task to write in.
RingBufferWheel update
In the previous “Time Wheel of Delayed Message”, I customized a timing task tool RingBufferWheel based on the time wheel. At the suggestion of netizens, I also made some adjustments this time by optimizing the API and adding the API of canceling tasks.
In the previous API, it felt weird to call start() every time a new task was created; This time it makes more sense to merge the start function directly into addTask.
Concurrent writing of tasks is also supported.
However, it is important to note that start() can be executed concurrently only once, so CAS is used to ensure that only one thread can execute successfully at the same time.
A taskId is returned when a new task is created. This ID can be used to cancel the task (although it is rare), as follows:
Interested friends can look at the source code is also easy to understand.
Distributed scheduled Task
As a final extension, all of the solutions we mentioned above are stand-alone versions that can only be used in a single process.
Once we need to realize the high availability and maintainable requirements of scheduled task in distributed scenario, we need a perfect support of distributed scheduling platform.
There are many popular open source solutions on the market:
- xxl_job
- elastic_job
- light-task-scheduler
I have only used the first two in my work, which can well solve the needs of distributed scheduling; Such as high availability, unified management, log alarm and so on.
Of course, these open source tools are inseparable from some of the schemes mentioned above in the function of timing scheduling, but need to combine some knowledge about distribution; Such as remote calls, unified coordination, distributed locking, load balancing, etc.
Interested friends can check their source code or official documents.
conclusion
A small timer actually involves a lot of knowledge points, including data structure, multi-threading, etc., I hope you see how much help, by the way, help to like forwarding up 🥳.
All source code involved in this article:
Github.com/crossoverJi…
Your likes and shares are the biggest support for me
