Shulou(Shulou.com)06/02 Report--

This article mainly explains "what is the role of HashedWheelTimer". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what is the role of HashedWheelTimer".

Discuss with colleagues the need for a scheduled audit, and the operation sets the time for passing the audit. After this time, the relevant content is automatically approved, which is originally a small requirement, but considering that if there are a lot of things to review regularly, a series of problems brought about by such a large number of scheduled tasks, and then gradually discussed the implementation of netty's HashedWheelTimer.

Scheme 1 single timer scheme description:

Put all resources that need to be audited regularly into redis, such as sorted set, and the time it takes to pass the audit is taken as the score value. The background starts a timer and polls sortedSet regularly. When the score value is less than the current time, the running task is approved.

problem

This solution has no problem in the case of small batches of data, but there will be problems in the case of large quantities of tasks, because every time you have to poll the full amount of data to determine whether it needs to be executed one by one. Once the polling task is executed for a long time, there will be the problem that the task cannot be executed at a scheduled time.

Scenario 2 description of multi-timer scheme

Each task that needs to be completed on a regular basis starts a scheduled task and then waits for completion to be destroyed.

problem

The problem caused by this scheme is obvious, in the case of more scheduled tasks, a lot of threads will be started, so that the server can not afford to crash later. Basically, this plan will not be adopted.

Scenario 3 borrows the expiration notification function description of redis

Similar to solution 1, set the expiration time for each task that requires regular audit, that is, the time when the audit is passed, subscribe to the expiration event of redis, and execute the corresponding audit pass task when this event occurs.

problem

This solution borrows middleware such as redis to implement our function, which is actually part of redis's publish and subscribe function. For redis publish and subscribe function, it is not recommended for us to do business operations in a production environment, usually within redis (for example, redis cluster nodes go online and offline, election, etc.) When our business system uses this event, it will give rise to the following two problems: 1, the instability of redis publish subscriptions 2, and the reliability of redid publish subscriptions. For more information, please see https://my.oschina.net/u/2457218/blog/3065021 (publish subscription defects of redis).

Scheme 4 Hash hierarchical timing wheel algorithm

Maybe this is the first time you've heard of this thing, like me, which is designed for mass timed task management. For details of the paper, see the reference [2].

Algorithm outline

In a nutshell, this is a wheel with a pointer, the pointer will rotate according to the set unit of time, and the task will fall on the corresponding slot according to some algorithms. The figure below is as follows

First of all, there will be a wheel, which is divided into eight slots here. When the task is added, the number of slots will be modeled according to the corresponding algorithm to get which slot the task will be stored in. Each slot is a linked list structure. The task stores the expiration time of the task (task execution time). The tick will go down a slot every unit of time, and then query the stored tasks in this slot, and the remaining number of rounds stored in the task will be reduced by one. When the remaining number of rounds is less than or equal to 00:00, the task will be started, and the task will be deleted from this slot after execution.

For example, the image above: the Bucket pointer with 8 slots will go down one slot every time interval (100ms). This time interval is called tickDuration, which is equivalent to every 8*100ms=800ms and will be polled.

HashedWheelTimer

The algorithm is relatively simple to understand, and there is also a mature implementation, that is, there is a HashedWheelTimer class in netty to implement this algorithm. Next, analyze and analyze this code of it.

Initialization

There are several more important properties defined on this class

/ * this work is an internal class that implements the Runable interface and is a core class that wraps the operation of a specific task, puts the task on how to put it on a slot, the specific method for the pointer to go down, task cancellation, and so on. * / private final Worker worker = new Worker (); / * worker thread, this is the starting point of the entire HashedWheelTimer startup * / private final Thread workerThread; / * the status of the current task. 1 indicates that the task has started execution, 0 task initialization, 2 task has been closed * / public static final int WORKER_STATE_INIT = 0; public static final int WORKER_STATE_STARTED = 1 Public static final int WORKER_STATE_SHUTDOWN = 2; / * the core concept is the unit in which the pointer goes down. In the HashedWheelTimer class, the default is that the 100ms pointer goes down one unit * / private final long tickDuration / * this refers to the time wheel, how many slots there are, and how big the wheel is. The default slot in HashedWheelTimer is * / private final HashedWheelBucket [] wheel; / * which slot the main auxiliary computing tasks will be stored in, mask = wheel.length-1 * / private final int mask / * Task queue for all tasks to be executed * / private final Queue timeouts = PlatformDependent.newMpscQueue (); / * Task queue for all tasks to be cancelled * / private final Queue cancelledTimeouts = PlatformDependent.newMpscQueue (); / * HashedWheelTimer instance starts running in nanoseconds, starting time is System.nanotime () * / private volatile long startTime

The definitions and concepts of these attributes are mapped to the above time wheel algorithm as shown in the following figure.

HashedWheelTimer initialization is mainly in its constructor, providing a variety of overloading methods, you only need to look at the most complete constructor.

/ * Creates a new timer. The time interval in which the * @ param threadFactory factory where the task is executed * @ param tickDuration pointer goes down one step * @ param unit pointer goes down one step, in seconds, milliseconds. Nanosecond * @ param ticksPerWheel time wheel size, that is, the number of slots * / public HashedWheelTimer (ThreadFactory threadFactory, long tickDuration, TimeUnit unit, int ticksPerWheel, boolean leakDetection, long maxPendingTimeouts) {/ * check the validity of the parameter, for threadFactory, time unit, time interval The size of the time wheel is limited * / if (threadFactory = = null) {throw new NullPointerException ("threadFactory") } if (unit = = null) {throw new NullPointerException ("unit") } if (tickDuration 0) {/ * calculation task is about to fall into the slot, which is supposed to be a modular operation, but a little trick is used here, that is, to replace the modular operation with "bitwise and", because "bitwise and" is much faster than modular operation. * this technique is that when the value of mast is 2 to the n-1, it can achieve the effect of modularization. Here, I would like to thank Wang Hongtao for sharing * / int idx = (int) (tick & mask); processCancelledTasks (); / / get the specific bucket, and then take the task from the blocking queue and put it in bucket HashedWheelBucket bucket = wheel [idx] TransferTimeoutsToBuckets (); / / all HashedWheelTimeout methods are called here to see if the remaining number of wheels is greater than 0, if so, it will be executed, if not, the remaining number of rounds minus 1 bucket.expireTimeouts (deadline); tick++ }} while (WORKER_STATE_UPDATER.get (HashedWheelTimer.this) = = WORKER_STATE_STARTED)

Of course, HashedWheelTimer belongs to full-memory task computing, usually in our real business, we don't put these tasks directly into jvm memory, otherwise the tasks will disappear after restart, so we need to rewrite HashedWheelTimer. We only need to rewrite the addition and acquisition of its tasks to the corresponding persistence middleware (such as database or es, etc.)

References and references

[1] [publish and subscribe defects of redis]

[[2]] [Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facil] [Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facil]: http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facil"

[[3]] [Hashed and Hierarchical Timing Wheels] [Hashed and Hierarchical Timing Wheels]: http://www.cse.wustl.edu/~cdgill/courses/cs6874/TimingWheels.ppt "Hashed and Hierarchical Timing Wheels"

Thank you for your reading, the above is the content of "what is the role of HashedWheelTimer", after the study of this article, I believe you have a deeper understanding of what the role of HashedWheelTimer is, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.