Shulou(Shulou.com)05/31 Report--

How to analyze the Kafka time wheel principle, in view of this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

Kafka time wheel is the basis for Kafka to achieve efficient delay tasks. It simulates the representation of clock to time in real life. At the same time, the way of time wheel is not limited to Kafka, it is a general time representation. This paper mainly introduces the principle of time wheel in Kafka.

There are some scheduled tasks (DelayedOperation) in Kafka, such as DelayedFetch, DelayedProduce, DelayedHeartbeat and so on. In Kafka, the addition, rotation, execution and demise of scheduled tasks are realized by time wheel. (time wheel is not a unique design of Kafka, but a general way of implementation. Time wheel is also used in Netty.)

1. What is the time wheel?

Two pictures on the reference network (excerpt from https://blog.csdn.net/u013256816/article/details/80697456)

These two diagrams clearly illustrate the structure of the Kafka time wheel: similar to real clocks, it is composed of multiple circular arrays, each containing 20 time units, representing a time dimension (round). For example, the first layer time wheel, each element in the array represents 1ms, and one circle is 20ms. When the delay time is greater than 20ms, it is "rounded" to the second layer time wheel, which is in the second layer. Each "frame" means 20ms, and so on.

For a delayed task, it generally consists of three processes: entering the time round, demotion, and expiration.

Enter the time wheel

1. Calculate the "hierarchy" of the corresponding time wheel according to the delay time (for example, "hour" or "minute" or "second" in the clock is actually a process of continuous "upgrading" until the appropriate "level" is found)

two。 Calculate the position in the wheel and insert it (each bucket is a two-way linked list and may contain multiple delayed tasks, which is also a big reason for the efficiency of the time wheel, which will be mentioned later)

3. If the bucket is inserted for the first time, you need to add the bucket to the DelayQueue (DelayQueue was introduced to solve the "null propulsion", which will be mentioned later)

Downgrade

1. When the time "advances" to a certain bucket, it means that the task in the bucket has run out of time in the current time round, and needs to be "degraded", that is, to enter a smaller granularity time round, the process of reinsert is similar to entering the time round.

Due execution

1. During the reinsert process, if it is found that it has expired, perform these tasks

The overall process is roughly as follows:

two。 The "advance" of time

One intuitive idea is to walk "one by one" like a clock in real life, so that a thread is required to execute all the time, and in most cases, the bucket in the time wheel is mostly empty, and the "push" of the pointer has no real effect. Therefore, in order to reduce this "empty propulsion", Kafka introduces DelayQueue to join the queue in bucket units, that is, whenever bucket expires, that is, queue.poll can get the result. The "advance" of time reduces the overhead of idling of ExpiredOperationReaper threads.

3. Why use the time wheel?

When it comes to deferring tasks, the more direct ideas are DelayQueue and ScheduledThreadPoolExecutor, while the biggest advantage of the time wheel is in terms of time complexity:

Time complexity comparison:

Therefore, in theory, the time performance advantage of TimingWheel will be more obvious when there are more tasks.

Summarize several main reasons for the high performance of Kafka time wheel:

(1) the structure of the time wheel + two-way list bucket, so that the insertion operation can achieve O (1) time complexity.

(2) the design of Bucket makes multiple tasks "merge", so that multiple inserts of the same bucket only need to be queued once in delayQueue, at the same time, the number of elements in delayQueue is reduced, the depth of heap is also reduced, and the insertion and pop-up operation overhead of delayqueue is also less.

The answer to the question on how to analyze the principle of Kafka time wheel is shared here. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel to learn more about it.

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.