A preface.

Long time no see. Recently, there is a requirement in the business I have been working on. The approval timeout task needs to be notified to the front end through Websocket, and the front end displays the execution status of the approval order in real time. At first, the idea was to use a scheduled task to scan the data in the table every once in a while to detect expired data. However, if the scanning interval of this operation is short, there will be a lot of empty scanning for the database. If the scanning interval is long, then for example, I will expire the task at 11:00, and I will perform the scheduled task scanning at 11:05. Obviously, the accuracy of data cannot be guaranteed.

To solve the above business scenario problem, I used a lot of middleware, and the framework used a time wheel to solve it. This article will introduce a variety of implementation methods and use scenarios, if there is wrong, welcome to point out, common progress ~

Two. Time round introduction

If there are a large number of scheduling tasks in a system, and a large number of scheduling tasks if each uses its own scheduler to manage the task life cycle, it wastes CPU resources and is inefficient.

Time round is a scheduling model that efficiently uses thread resources for batch scheduling. Bind a large number of scheduling tasks to the same scheduler, and use this scheduler to manage, trigger and runnable all tasks. Able to efficiently manage various delayed tasks, periodic tasks, notification tasks and so on.

However, the time accuracy of the time scheduler may not be very high, and it may not be suitable for scheduling tasks with high precision requirements. Because the accuracy of the time wheel algorithm depends on the minimum granularity of the time “pointer” unit, for example, the grid of the time wheel jumps once a second, then tasks with scheduling accuracy less than one second cannot be scheduled by the time wheel.

2.1. Single-layer time wheel

As shown in the figure above, the above ring queue is regarded as a clock. The current ring queue executes 0 nodes, and the interval between each node is 1 minute. Each clock node points to a task queue. For example, if I want to execute a task five minutes later, I will place the task on node 5. When the time wheel turns to node 5, I will execute the tasks on node 5. After the execution is complete, I will clear the tasks on node 5.

2.2. Time wheel with number of turns

The flaws in the first, most basic, time wheel are obvious. For example, I set a time wheel with an interval of 1 minute and a ring queue of 60 nodes. So if my task is executed after 70 minutes (70%60=10), it overlaps tasks that will expire after 10 minutes. Then, when the time wheel rotates to 10 nodes, the 10-minute expired tasks and 70-minute expired tasks on the node will expire.

Therefore, the parameter of the number of turns of round should be added on the basis of the primary time round. For example, for the 70-minute task mentioned above, the number of turns is recorded as 1 when the task is added to the node. For the 10-minute task, the number of turns is recorded as 0; when the pointer moves to 10 nodes, only the data with the number of turns is executed and removed.

2.3. Multi-layer time wheel

Go back to 2.2. If the task spans a long time, the time wheel will idle, and the task will only be executed if round is 0, which is CPU intensive. Hence the introduction of the concept of a multi-layer time wheel

The span of the first layer is 1ms, the span of the second layer is 20ms, and the span of the third layer is 400ms. Then, for example, if the task we put is 501ms, it will be put into the first node of the third layer (501%400=101) with 101ms redundancy. When the pointer of the third layer is transferred to the first node, the task of 101ms will be transferred to the second layer and then put into the fifth node of the second layer (101%20=1). When redundant time is found when the pointer of layer 2 is moved to 5 lower nodes, the task is transferred to the first node of layer 1, and the first layer is executed once. The advantage of doing this is to avoid the situation of single wheel empty rotation.

Application three.

The use of time wheel is used in various frameworks and middleware, xxL-job, Netty, Kafka have their own implementation of time wheel. The idea is basically the same as deleting the time round strategy.

In daily business, if the delay of tasks is relatively fixed and there will not be a large span of time, the HashedWheelTimer class in Netty package can be called; if it is complicated, the delay queue in Kafka can be used. Same idea as above.

4. Reference

Time wheel in Kafka practice

Five. Contact me

If you think the article is well written, you can like it and comment + follow it

Nailing: louyanfeng25

WeChat: baiyan_lou