Follow Mic to learn architecture 2022-08-06 17:39:13 阅读数:835
Hello everyone, I'm Mic, a Java programmer who has no talent and can only rely on his looks.
A programmer who has been working for 7 years, went to byte interview and was asked the question of the time round.
He came back from the interview and told me that this question was beyond his knowledge. He also found some articles on the Internet to study, but his understanding was not very deep.
Want me to write an interview essay about the time wheel problem.
Who told me to be so kind?Immediately arranged for this fan.
About the question "What is the time wheel, please tell us your understanding of the time wheel",
I put the master's answers into a 10W interview document, you can scan the QR code at the end of the article to get it
Look at the master's answer below
Partners who need expert interview documents and interview documents can scan the QR code at the bottom of the articlespan>
The time wheel, simply understood, is a ring-shaped array used to store a series of timed tasks. Its entire working principle is similar to the dial of our clock.
It consists of two parts, one is a ring array and the other is a pointer to traverse the ring array.
First, define a fixed-length ring array, and then each element of the array represents a time scale, assuming it is 1s, then if it is an array of length 8, it represents 8 seconds.
Then, there is a pointer that loops through the array in a clockwise direction, advancing one array index every minimum time unit.
This pointer makes one revolution to represent 8 seconds, and two revolutions to represent 16 seconds. Assuming that it starts from 0:00:00, it will reach 0:00:9 seconds after one revolution.
Each element in the ring array is a container used to store timed tasks. When we add a timed task to the time wheel, we will calculate the array index stored in it according to the execution time of the timed task..
It is possible that there are multiple timed tasks on a certain time scale, which will be stored in a doubly linked list at this time.
When the pointer points to an array, the tasks stored in the array will be taken out, and then the linked list will be traversed to run the tasks in it one by one.
If the execution time of a scheduled task is greater than the length represented by the ring array, a lap number can generally be used to represent the delayed execution time of the task.
That is to say, if it is the task to be executed in the 16th second, it means that this task should be executed at the subscript 0 position of the array in the second circle.
The benefits of using a time wheel to manage multiple scheduled tasks are many, and I think there are two core reasons:
Reduce the time complexity of adding and deleting scheduled tasks and improve performance.
It can guarantee that each execution of the timer task is O(1) complexity. In the case of intensive timer tasks, the performance advantage is very obvious.
Of course, it also has drawbacks, for very time-critical tasks, the time wheel is not very suitable, because the accuracy of the time wheel algorithm depends on the granularity of the smallest time unit.Assuming that 1s is used as a time scale, tasks that are less than 1s cannot be scheduled by time rounding.
The time wheel algorithm is used in many places, such as Dubbo, Netty, Kafka, etc.
The time wheel algorithm is an interesting design.
It is widely used, but in practical applications, most students have very little contact.
I think this design idea or this data structure can also be used for reference in some specific scenarios in our practical application.
Such as timing retry, decay retry, etc.
Also, I made all Java interview series into full interview documents.Its convenience is that you can find the interview questions you want by searching. Currently, 180 issues have been updated, with a total of more than 15W words!
copyright：author[Follow Mic to learn architecture]，Please bring the original link to reprint, thank you. https://en.javamana.com/2022/218/202208061722414386.html