Application of clock wheel in RPC

Today's article introduces RPC How to use the clock wheel to achieve timed tasks , For example, the timeout processing of the caller 、 Timed heartbeat ....

What problems do timed tasks bring ？

Before explaining the clock wheel , Let's talk about scheduled tasks first . I believe you are in the process of development , Many scenarios use timed tasks , stay RPC It is also used in many places in the framework . Take the processing logic of the caller request timeout as an example , Let's take a look RPC The framework deals with timeout requests .

In the interpretation of the Future When I said ： Whether synchronous or asynchronous , The internal implementation of the caller is asynchronous , The caller will create a before sending a message to the server Future, And store this message ID and this Future Mapping , When the server receives the message and processes it, it sends a response message to the caller , After receiving the message, the caller will find this... According to the unique ID of the message Future, And inject the results into this Future.

In the process , What if the server does not respond to the message to the caller in time ？ How should the caller handle the timeout request ？

you 're right , You can use timed tasks . One at a time Future, We all record this Future The creation time of is the same as this Future Timeout for , And there is a scheduled task to detect , When this Future When the timeout is reached and not processed , That's what we're interested in Future Execute timeout logic .

How to realize the scheduled task ？

There is an implementation method like this , It's also the simplest . For every one created Future We all start a thread , after sleep, The processing logic that triggers the request timeout when the timeout time is reached .

This way , It's really simple , It can also be used in some scenarios , But the disadvantages are also obvious . Just like the one I just mentioned Future Examples of timeout processing , If we are faced with highly concurrent requests , A single machine sends tens of thousands of requests per second , The request timeout is set to 5 second , How many threads should we create to execute the timeout task ？ exceed 10 000 threads , This figure is really scary .

Don't worry. , We have another implementation . We can use one thread to handle all scheduled tasks , Just now Future An example of timeout processing . Suppose we want to start a thread , This thread runs every 100 Millisecond will scan all processing Future Timed out tasks , When you find a Future It's overtime , We will carry out this task , For this Future Execute timeout logic .

We use this method most , It also solves the problem of too many threads in the first way , But in fact, it also has obvious disadvantages .

It is also a highly concurrent request , Then the thread of the scanning task is every 100 How many scheduled tasks should be scanned in milliseconds ？ If the caller happens to be 1 Sent in seconds 1 Ten thousand requests , this 1 Ten thousand requests must be made in 5 Seconds before the timeout , So the scanning thread is in this 5 You'll be talking about this in seconds 1 Ten thousand tasks are scanned and traversed , Additional scanning 40 many times （ Every time 100 One millisecond scan ,5 Scan in seconds 50 Time ）, It's a waste CPU.

When we use timed tasks , The problems it brings , Is to make CPU A lot of additional polling traversal operations are done , wasted CPU, This phenomenon occurs when there are many scheduled tasks , especially .

What is a clock wheel ？

This problem is not difficult to solve , We just have to find a way , Just reduce the additional scanning operations . For example, my scheduled tasks are 5 Seconds later , I am here 4.9 Seconds later, it starts scanning these scheduled tasks , This greatly saves CPU. Then we can use the mechanism of the clock wheel .

Let's first look at the clock we use in our life .

I'm familiar with it , A clock has an hour hand 、 Minute and second hands , After the second hand beats for a week , That is, beating 60 After a scale , The minute hand beats 1 Time , The minute hand beats 60 A scale , Walk one step clockwise .

The realization principle of the clock wheel refers to the principle of clock beating in life .

In the clock wheel mechanism , There are time slots and clock wheels , The time slot is the scale of the clock , And the clock wheel is equivalent to a cycle of second hand and minute hand , We will put each task in the corresponding time slot .

The operating mechanism of the clock wheel is the same as that of the clock in life , Every fixed unit time , It will jump from one time slot to the next time slot , This is equivalent to our second hand beating once ;

The clock wheel can be divided into multiple layers , The unit time of each slot in the next layer clock wheel is the time of the whole cycle of the current time wheel , This is equivalent to 1 Minutes equal to 60 Second ; At that time, after the clock wheel beats all the slots of a cycle , It will take out a slot from the next clock wheel , Redistribute to the current clock wheel , The current clock wheel starts from 0 The groove starts beating again , This is equivalent to the... Of the next minute 1 second .

In order to facilitate you to understand the operating mechanism of the clock wheel , Let's use a scenario example to simulate , Let's watch this scene .

Suppose our clock wheel has 10 Slots , And the cycle of the clock round is 1 second , So the unit time of each slot is 100 millisecond , And the cycle of the next time wheel is 10 second , The unit time of each slot is 1 second , And the current clock wheel has just been initialized , That is the first. 0 jump , At present, it's in the second 0 Slots .

good , Now we have 3 A mission , They are tasks A（90 In milliseconds ）、 Mission B（610 In milliseconds ） And task C（1 second 610 In milliseconds ）, We will 3 Add a task to the clock wheel , Mission A Put in the second place 0 Slot position , Mission B Put in the second place 6 Slot position , Mission C Put on the next level of the time wheel 1 Slot position , As shown in the picture below .

When tasks A Just put into the clock wheel , It was immediately executed , Because it was placed in the 0 Slot position , The current time round just jumps to 0 Slot position （ Actually, it hasn't started beating yet , Status is No 0 jump ）;600 In milliseconds , The time wheel has been carried out 6 jump , The current slot is 6 Slot position , The first 6 All tasks in the slot are taken out and executed ;1 Seconds later , The... Of the current clock wheel 9 The jump is over , A new beginning 0 jump , At this time, the next clock wheel starts from 0 Jump to the 1 jump , Will be the first 1 Take out the task of slot , Distributed to the current clock wheel , Then the task C Take it out of the clock wheel of the next layer and put it in the... Of the current clock wheel 6 Slot position ;1 second 600 In milliseconds , Mission C Be performed .

After watching this scene , I believe you have understood the mechanism of the clock wheel . In this case , The scanning cycle of the clock wheel is still 100 millisecond , But the task has not been scanned repeatedly , It perfectly solves CPU The problem of waste .

This mechanism is not difficult to understand , But it is still very difficult to realize , There are also many problems to pay attention to .

Where is the clock wheel RPC Application in

Through the explanation of the clock wheel just now , I believe you can see , It is used to perform scheduled tasks , Can say in RPC As long as timing related operations are involved in the framework , We can use the clock wheel .

that RPC In which function implementation will the framework use it ？

The caller request timeout processing I just mentioned for example , Here we can apply it to the clock wheel , Every time we send a request , Create a timed task to handle request timeout and put it in the clock wheel , In high concurrency 、 In the case of high traffic , The clock wheel only poll the tasks in one time slot at a time , This will save a lot of CPU.

The startup timeout of the caller and the server can also be applied to the clock wheel , Take the caller as an example , Suppose we want to make the application deploy quickly , for example 1 In minutes , If exceeded 1 Minutes, start failed . We can create a scheduled task to handle the startup timeout when the caller starts , Put it in the clock wheel .

besides , What else can you think of RPC Where can the frame be applied to the clock wheel ？ And regular heartbeat .RPC The framework caller sends heartbeat to the server regularly , To maintain connectivity , We can encapsulate the heartbeat logic as a heartbeat task , Put it in the clock wheel .

At this time, you may have a question , The heartbeat is repeated regularly , The task in the clock wheel is removed once it is executed , How do we deal with this kind of timing task that needs to be repeated ？ At the end of the execution logic of the scheduled task , We can reset the execution time of this task , Throw it back into the clock wheel .

summary

Today we mainly talk about the mechanism of the clock wheel , And the clock wheel is RPC Application in the framework

This mechanism solves the problem of , Because each task creates a thread , Resulting in the problem of creating too many threads , And a thread scans all scheduled tasks , Give Way CPU Do a lot of extra polling traversal operations and waste CPU The problem of .

The implementation mechanism of the clock wheel is to simulate the clock in real life , Put each scheduled task on the corresponding time slot , This can reduce the additional traversal of other time slot timing tasks when scanning tasks .

In the use of time wheel , There are some problems that need your extra attention ：

• The shorter the unit time of the time slot , The more precise the time wheel triggers the task . For example, the unit time of the time slot is 10 millisecond , Then the time error of executing the scheduled task is 10 In milliseconds , If it is 100 millisecond , So the error is 100 In milliseconds
• The more slots of the time wheel , Then the probability of a task being scanned repeatedly is smaller , Because only the tasks in the multi-layer clock wheel will be scanned repeatedly . For example, the slot of a time wheel has 1000 individual , The unit time of a slot is 10 millisecond , Then the unit time of a slot in the next time wheel is 10 second , exceed 10 The second timed task will be put into the next time wheel , That is, only more than 10 The second timed task will be scanned and traversed twice , But if the slot is 10 individual , So over 100 Millisecond task , It will be scanned and traversed twice .

Combined with these characteristics , We can depend on the specific business scenario , Set the cycle of the clock wheel and the number of time slots .

stay RPC In the frame , As long as it involves scheduled tasks , We can all use the clock wheel , A typical example is the timeout processing at the caller 、 The startup timeout and timed heartbeat of the caller and the server .

This paper is written by mdnice Multi platform Publishing