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

Go language how to achieve a time wheel, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain for you in detail, people with this need can come to learn, I hope you can gain something.

Simple time wheel

What stores the task in the time wheel is a circular queue, which is implemented in an array at the bottom, and each element in the array can store a scheduled task list. The scheduled task list is a circular two-way linked list, and each item in the linked list represents a timed task item, which encapsulates the real scheduled task.

The time wheel consists of multiple time lattices, each of which represents the basic time span (tickMs) of the current time wheel. The number of time cells of the time wheel is fixed, which can be expressed by wheelSize, so the total time span (interval) of the whole time wheel can be calculated by the formula tickMs × wheelSize.

The time wheel also has a dial pointer (currentTime), which is used to indicate the current time of the time wheel, where currentTime is an integral multiple of tickMs. CurrentTime points to the timestick that is due, indicating all the tasks in the linked list corresponding to the timestick that needs to be processed.

The following picture shows a time wheel with a tickMs of 1s WheelSize equal to 10. Each box contains a scheduled task linked list with real task items in the list:

In the initial case, the dial pointer currentTime points to the timeframe 0. If the tickMs of the time wheel is 1ms and wheelSize equals 10, then interval equals 10s. In the following figure, a task with a timing of 2s is inserted and stored in the task linked list with a time grid of 2, marked in red. With the passage of time, the pointer currentTime continues to move forward, and if 2s has passed, then currentTime will point to the position of timestick 2, and the task list of this timeframe will be obtained and processed.

If the current pointer currentTime points to 2, then if a 9s task is inserted, the new task will take the original time grid linked list and will be stored in time box 1.

The time wheels we are talking about here are simple time wheels with only one layer, and the overall time range is between currentTime and currentTime+interval. If there is a 15s scheduled task that needs to reopen a time wheel, set a time wheel with a time span of at least 15s to be sufficient. But there is no bottom line for this expansion. If you need a time wheel of 10,000 seconds, then you need such a large array to store, which not only takes up a lot of memory space, but also reduces efficiency because you need to traverse such a large array.

Therefore, the concept of hierarchical time wheel is introduced.

Hierarchical time wheel

For example, the picture shows a two-layer time wheel, and the second time wheel is also composed of 10 time grids, each with a span of 10s. The tickMs of the time wheel of the second layer is the interval of the time wheel of the first layer, namely 10s. The wheelSize of each time wheel is fixed, which is 10, so the overall time span interval of the second layer time wheel is 100s.

The figure shows the expiration time range corresponding to each time grid, and we can clearly see that the expiration time range of the 0th time grid of the second time wheel is [0JRIX]. In other words, one time grid of the second time wheel can represent all (10) time grids of the first time wheel.

If you add a 15s task to the time wheel, when there is no room for the first time wheel, enter the second time wheel and insert it into the time grid with an expiration time of [10j19].

With the passage of time, when there are 5 seconds left in the original 15s task, there is a time round degraded operation, and the overall time span of the first time round is sufficient. This task is added to the time grid where the expiration time of the first time round is 5, and then after 5 seconds, the task really expires, and finally performs the corresponding expiration operation.

Code implementation

Because the time wheel code of our Go language version is written in imitation of Kafka, there are some small details when implementing the time round TimingWheel:

Each linked list in the time lattice of the time wheel has a root node to simplify the boundary conditions. It is an additional linked list node, as the first node, its value range does not store anything, but is introduced for the convenience of operation.

Except for the first layer time wheel, the start time (startMs) of the other high level time wheels is set to the currentTime of the previous round when the layer time wheel was created. The currentTime of each layer must be an integral multiple of tickMs, and if it is not satisfied, the currentTime will be trimmed to an integral multiple of tickMs. The pruning method is: currentTime = startMs-(startMs% tickMs)

Timers in Kafka only need to hold references to the first tier time wheel of TimingWheel, and will not directly hold other high-level time wheels, but each layer time wheel will have a reference (overflowWheel) pointing to a higher-level application.

Timers in Kafka use DelayQueue to help advance the time wheel. In the operation, each linked list in each time grid used will be added to the DelayQueue,DelayQueue and sorted according to the expiration time expiration corresponding to the time wheel, and the tasks with the shortest expiration will be placed at the head of the DelayQueue queue, and the tasks due in the DelayQueue will be obtained through separate threads.

Structure type TimingWheel struct {/ / time span Unit is millisecond tick int64 / / in milliseconds / / number of time wheels wheelSize int64 / / Total span interval int64 / / in milliseconds / / current pointer points to time currentTime int64 / / in milliseconds / / timeframe list buckets [] * bucket / / delay queue queue * delayqueue.DelayQueue / / the superior's time wheel quotes overflowWheel unsafe.Pointer / / type: * TimingWheel exitC chan struct {} waitGroup waitGroupWrapper}

Tick, wheelSize, interval and currentTime are easy to understand. The buckets field represents a timeline list, queue is a delay queue, all tasks are triggered by a delay queue, and overflowWheel is a reference to the upper time wheel.

Type bucket struct {/ / Expiration time of tasks expiration int64 mu sync.Mutex / / Task queues with the same expiration time timers * list.List}

Bucket actually encapsulates the task queue in the time grid, which contains tasks with the same expiration time. When it expires, the queue timers will be taken out for processing. What's interesting here is that because there are multiple threads accessing bucket concurrently, atomic classes are needed to get int64-bit values. In order to ensure consistency in reading 64-bit data on 32-bit systems, 64-bit alignment is required. You can take a look at this article: https://www.luozhiyun.com/archives/429, which is about thinking about memory alignment.

Type Timer struct {/ / Expiration time expiration int64 / / in milliseconds / / the specific task to be executed task func () / / bucket pointer b unsafe.Pointer / / type: * bucket / / bucket list corresponding element element * list.Element}

Timer is the minimum execution unit of the time wheel and the encapsulation of the timing task. When it expires, task will be called to execute the task.

Initialize the time wheel

For example, now initialize a time round in which tick is 1s and wheelSize is 10:

Func main () {tw: = timingwheel.NewTimingWheel (time.Second, 10) tw.Start ()} func NewTimingWheel (tick time.Duration, wheelSize int64) * TimingWheel {/ / convert the incoming tick to millisecond tickMs: = int64 (tick / time.Millisecond) / / if less than zero, then panic if tickMs

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.