Original address: mp.weixin.qq.com/s/jL8_23pjY…

directory

  • preface
  • Delay queue definition
  • Application scenarios
  • Implementation scheme
    • Redis zset
    • TimeWheel
    • Time wheel structure
    • Time wheel running logic
  • conclusion

preface

Delay queue is a technical solution that we frequently contact in daily development. As the name implies, a delay queue is a message queue with delay capability. For example, if a message is sent to the queue with a delay of 60 seconds, the message will be received after 60 seconds. Oneself search on the net data collation, study, undertook a summary for this and share the knowledge.

Delay queue definition

First of all, you’re familiar with queue data structures, which are fifO data structures. The elements in a normal queue are ordered, and they follow a first-in, first-out rule, that is, the first to queue is executed first, and the last to queue is executed last.

The biggest difference between a delay queue and a common queue lies in the attribute of delay. In a common queue, the tasks that are queued first are executed first, while in a delay queue, a delay time is specified to indicate that the queue expects to be processed after the specified time. For example, if you place an order in a shopping app and you don’t pay, the payment interface will remind you to cancel after 15 minutes. This is a typical example of delayed queue.

Application scenarios

In our real life, the use of delay queue is more common, such as the following scenarios:

  • The order will be automatically cancelled if it is not paid over time

  • After the user places the order, when there are 15 minutes left before the timeout time, the system will remind the delivery boy to deliver the food in time to avoid the timeout

  • The system will give 5 stars after 7 days by default

.

The use of deferred queues is ubiquitous. In the above scenario, if the delay queue is not used, the business side is required to rotate the database every second to compare the current time with the set time, and each business side needs the same repetition logic. As a result, we could abstract it out as a common component, and thus the hero of the day, the delay queue, was born.

With the delay queue, each business side only needs to add the task to the delay queue and set the delay time. When the time is specified, the task will be automatically triggered and the corresponding logical method will be called for processing.

Delay queues provide us with a reasonable solution to solve a large number of tasks that need to be delayed. Let’s take a look at how delay queuing is actually implemented.

Implementation scheme

Redis zset

The message that the client needs to delay execution is called a delayed task, so we can use Redis ZSet data structure to store it. The ID of the delayed task is the key value, the value is the details of the whole task, and the score value is the message delay time of the delayed execution.

We can implement a delay queue using Redis’ ZSet data structure by following several steps:

  • ZADD key Score value syntax is used to join the team. The ID of the delayed task is taken as the key value, the details of the entire task is taken as the value, and the delay time of the task is taken as the score.

  • The ZRANGEBYSCORE KEY -INF + INF limit 0 1 WITHSCORES method is used to check whether the task in the ZSet is executable. There are two situations:

  • If the queried score is smaller than the current timestamp, the task can be executed. In this case, the task is executed asynchronously

  • If the queried score is greater than the current timestamp, it indicates that there is no task to be executed in the queue. Then sleep for one second and train again

In terms of implementation steps, implementing delay queues through Redis Zset is an easy way to understand and relatively simple to implement. And we can rely on Redis own persistence to achieve persistence, using Redis cluster to support high concurrency and high availability, is a good implementation scheme of deferred queue.

TimeWheel

TimeWheel algorithm is also one of the schemes to implement delay queue. The time wheel can be found in Netty, Akka, Quartz, ZooKeeper, Kafka and other components.

Time wheel structure

As shown above, the time wheel is a circular queue storing delayed tasks, and the bottom layer is implemented by array. Each element in the array can store a HashedWheelBucket, which is a circular bidirectional linked list (red in the figure). Each item in the linked list represents a deferred task item, which encapsulates the true deferred task of the chain.

A time wheel is made up of multiple time cells, each representing the basic span of the current time. And the number of time cells is fixed.

The time wheel also has a dial pointer, which is used to represent the time currently indicated by the time wheel. With the time migration, the corresponding delayed tasks in the time cell are continuously processed.

Time wheel running logic

When the time wheel starts, it records the current startTime and assigns a value to startTime. When adding delayed tasks, the time wheel will first calculate a delay time. For example, if the delay time of a task is 30s, it will calculate a timestamp (delay time) by adding the current time + 30s-time wheel start time. Then, the delayed tasks are added to the linked list of corresponding time cells and wait for execution.

Then you need to calculate several parameter values:

  1. Delay total number of tasks to be delayed: Calculate the number of ticks of the tick based on the delay time/time bar of each task

  2. Calculate the number of time rounds: According to the calculated number of steps (total times – number of current ticks)/ number of time cells, for example, we need to add a delay task with a delay of 24 seconds. If the current tick is 0, then the number of rounds =(24-0)/20=1, then the round will be removed and reduced by one for each run of the pointer. So you have to go to the second round to get round zero and then it will run

  3. Calculate the slot that the task needs to be placed in the time wheel, and then add it to the end of the slot list

After placing the data in timeouts into the time wheel, calculate the position of the slot to which the current hour hand moves, take out the linked list data in the slot, compare the deadline with the current time, and run the expired data xx.

The delay queue implemented by time wheel can support the efficient triggering of a large number of tasks. In the implementation scheme of Kafka’s time rotation algorithm, DelayQueue is introduced. DelayQueue is used to push the time wheel rolling, and the adding and deleting operations of delayed tasks are placed in the time wheel. This design greatly improves the execution efficiency of the whole DelayQueue.

conclusion

Delay queue is widely used in our daily development. In this paper, we introduce two ways to realize delay queue using Redis Zset and TimeWheel respectively. From the implementation process, it can be found that using Redis Zset to implement the delay queue is the easiest to understand and can quickly fall to the ground. However, Redis is based on memory after all, although there is a persistence mechanism, there is still the possibility of data loss. Using TimeWheel algorithm is a very clever scheme, but it is also the most difficult scheme to understand. At this point, the article is basically over, and I hope this article gives you some ideas for implementing delay queues.

The article will be updated continuously. You can search “Maimo Coding” on wechat to read it for the first time. Every day to share quality articles, big factory experience, big factory face, help interview, is worth paying attention to every programmer platform.