British Fleming once said: “do not wait for luck, should strive to master knowledge.”

1 introduction

Hi, I’m Mu! Your harvest is my like, your thumbs-up is my approval.

Today, instead of talking about the Redis interview series, we are going to talk about limiting the flow and how it is used. It is very strange why the painting style suddenly changed. The previous article mentioned the redis flow limiting operation, but did not actually demonstrate and practice the use of the scene to friends. So, since I’ve been asked privately, let’s talk about that today.

Of course, it is not out of nowhere that I want to write this article. In the actual interview scenario, I will be asked by the interviewer. Generally a mature company, its current limit is through a middle service (out of China, the middle is not ali is a network upstream service), your app are through upstream of the validation, all requests for detection processing, if which interface is configured with current limiting, it can automatic monitoring alarm, then go to current limit, reduce, fusing measures. However, not many companies have a set of such a standard process, so most of them are based on Redis to do a simple version of the flow limiting service.

All right, new interview focus!

2 What is traffic limiting on an interface

Interviewer: “One year of experience, will not know what is the operation of limiting the flow.” Can you tell us your understanding of limiting traffic?

Interviewer: “God, out of line ah, I before but in outsourcing company, the number of users is not much, the flow is not big, QPS not to mention, this is clearly to make me, I move out of the theoretical knowledge”. As the name suggests, limiting traffic is limiting the number of requests; Then it is divided into total request traffic and concurrent traffic within a certain period of time.

Interviewer: According to your answer, traffic limiting is divided into two situations: the number of concurrent requests per unit and the total amount of traffic within a period of time. Can you describe the application scenario of traffic limiting respectively?

Interviewee: “I am really a mean mouth, why have no matter to say so much, to their own business to do all, the table under the middle finger”. Intermittent down: (1) Concurrent traffic roughly refers to the number of people visiting the website at the same time, the more the number of people, instantly brought traffic will be affected by the bandwidth. ② The total traffic in a certain time refers to the traffic brought by the total number of requests in a unit time.

Interviewer: Yes, I understand it quite clearly. How do you deal with the situation that the service performance is affected by heavy traffic? “Think to yourself: Even though you’ve only been working for a year, you want to test your knowledge of the subject and see if you can make it.”

Interviewer: “Babe, what are you going to do? Does it feel like I’m an advanced developer, that I’m so young, so handsome, and this is hard on me? Think of a noun you usually see on the Internet and brag about it. Our common means to deal with large traffic are: (1) cache (access cache as soon as possible, to prevent a large number of frequent requests DB); (2) limiting traffic (limiting requests within a certain range within a certain period of time to ensure that the system will not collapse); Degradation (refers to the strategic non-processing or simple processing of some services).

PS: Caching and degradation are not the solution to all high traffic situations. For example, when I was engaged in e-commerce before, tens of millions of users placed orders instantly, and a large number of database writing operations were beyond our control. The throughput of DB was a bottleneck. Therefore, the introduction of traffic limiting can greatly reduce the crash problem of the service.

Interviewer: “Know quite a lot, beyond my expectation, check out this young man’s bottom”. Basically, it is ok. Can you briefly talk about how you use flow limiting in actual projects? What are the schemes of flow limiting?

This interviewer must be screwing me

At present, there are four commonly used methods of flow limiting: counter, sliding window, leaky bucket algorithm and token bucket algorithm. We will explain them one by one below (PS: the company has practiced them before).

3.1 Counter Algorithm

Counter algorithm is the simplest and easiest way to implement the current limiting algorithm. Generally, this method is used to limit traffic on interfaces.

For example, let’s say that our website’s active task interface is 100/min. So our solution can do: ① set the counter counter; ② When the request comes, counter+1; ③ If the counter value is greater than 1000 and the difference between the current request time and the first request time is less than or equal to 1min, the request exceeds the load of the site and is directly blocked; ④ If the time difference between the current request and the first request is greater than 1min and the counter value is less than or equal to 100, then the reset counter returns to 0(the whole network is copying);

My personal understanding is that in addition to targeting heavy traffic, the traffic limiting operation can also be used to control user behavior and avoid generating spam requests. The most common actions such as Posting, liking, and replying to comments are controlled by limiting traffic (for individual user behavior). Not just a centralized request for all users of an interface.

A schematic diagram is drawn below:

Public function counter() {$curr_time = time(); If ($this->first_request_time + $this->fix_time > $curr_time) {if ($this->first_request_time + $this->fix_time > $curr_time) ($this->request_count >= $this->request_limit) return false; $this->request_count++; return true; $this->first_request_time = $curr_time; $this-> request_time = $curr_time; $this->request_count = 1; return true; }}Copy the code

Interviewer: Nod your head slightly. What are the advantages and disadvantages of current limiting?

① Advantage: traffic limit flow realization is simple, suitable for the vast majority of the scene. At the same time, the QPS /min value can be dynamically configured with a server, just need to estimate the value of QPS. (2) Disadvantages: there is a critical point on the time, if the last 1s with the start of the next minute centralized request volume, then there is still a large flow of malicious requests, even beyond the estimated system bottleneck, resulting in service paralysis.

As you can see from the above, the user sent 200 requests in a second. So it’s completely beyond our limit of 100 requests per minute, so limiting traffic is effectively ineffective, and users can use this node to crash the service in an instant.

Interviewer: “Since you have said the shortcomings, then I reluctantly ask you have no solution, as if to say: you are so ox, I am not very face.” Have you thought of a solution to the shortcomings of the counter?

Interviewer: “I want to stun you with a punch, this call what matter, I have not done, have not practiced ah; This is not on purpose to let me answer up, pressure my salary; Brave to blow, anyway don’t want money. Boon boon forehead… I vaguely remember another scheme called the sliding window algorithm, which was used to compensate for the counter defect.

3.2 Sliding window algorithm

The meaning of sliding window is simply to slice fixed time into multiple parts, and move forward as time goes by. Then the critical point of the counter can be well avoided. Each grid has its own independent counter counter, and each grid calculates its own threshold. This shows that the more grids the sliding window is divided, the smoother the rolling of the sliding window will be, and the more accurate the statistics of current limiting will be. Let’s draw the illustration below:

From the above figure, we can see how the sliding window solves the critical point: the 100 requests arriving at 1:59 will fall into the blue grid, and the user reaches another 100 requests at 2 minutes, which will fall into the red grid. However, the grid will automatically move one space to the right, resulting in 200 requests, exceeding the 100 we performed, triggering the limiting operation (you can Google the information for yourself). Here’s the code:

Public function slide() {$key = 'slide:test:key:user'; $redis = new \Redis(); $now_time = time(); $redis->multi(); $redis->zAdd($key, $now_time, $now_time); $redis->zRemRangeByScore($key, 0, $now_time ->fix_time); $redis->zCard($key); $redis->expire($this->fix_time + 1); $this-> expire($key, $this->fix_time + 1); $result = $redis->exec(); $current_count = isset($result[3]) ? $result[3]:0; return $current_count < $this->request_limit; }Copy the code

Interviewer: “I have to give you a thumbs up. It’s clear. There are some flaws, but it’s more important to think about it.” Yes, yes, what you said here is still clear, there are some details are not in place, you can refer to the document when you are free. But overall, the answer is very good. More like what I expected…

3.3 Leaky bucket algorithm

Interviewee: The leaky bucket algorithm is relatively simple, which is probably such a process: ① Find a fixed capacity funnel; (2) Inject quantity into funnel at random rate; (3) Ensure that the capacity of the funnel is constant, uniform rate of outflow water; (4) the water exceeding the capacity is directly overflowed and discarded; The following is the overall flow chart: “Heart murmur, this really have no what to say, know the principle is ok, don’t ask me good!”

/** * @desc * @return bool */ public function leaky() {$curr_time = time(); $request_time = ($this->last_request_time) * $this->rate; $this->water = Max (0, $this->water - $out_water); $this->last_req_time = $curr_time; If ($this->water < $this->capacity) {$this->water = $this->water + 1; } return false; }Copy the code

Interviewer: “Yes, the core logic seems clear.” Well, the leaky bucket algorithm is relatively simple, as long as the principle flow is OK. Know there is such a thing, although use not much, but still want to inspect you to this convenient knowledge point (heart in fluctuation, now a year of experience of the lad all know so much). Do you use token buckets in your projects?

3.4 Token bucket algorithm

Interviewer: Hello, interviewer. In fact, I seldom use the algorithm of token bucket in actual projects, because it is a little complicated, and our company does not have a large flow, and even less use of concurrency. It involves a lack of knowledge, so I want to change a working environment; Ability to improve their level through bigger platform and excellent technical solutions; “Inside palpitation glance, still want a bit modest, can’t too outstanding, show the interviewer very dish, I simply say own view calculate”. I haven’t used it, but I’d like to share my thoughts on token buckets.

We can see that the leaky bucket algorithm will appear such a scene: because the flow speed of the leaky bucket is fixed, if the instantaneous large flow impact, it may lead to the overflow of water in the bucket, which means a large number of requests are discarded. Hence the token bucket, to solve this problem. (1) The token bucket generation rate is still constant; (2) the rate of requests to get tokens is unlimited (random); (3) if the request cannot get tokens in the bucket, the request is rejected; (4) If the bucket capacity reaches the full value, the excess token is discarded; (5) The majority of traffic requests are guaranteed to be normal, while a small portion of traffic requests are sacrificed

The working principle is as follows: The token data in the bucket starts to be 0, and the bucket is filled with tokens at a fixed rate until the bucket is full and the excess tokens are discarded. Each request comes to take the token first, get it removed, otherwise reject the request.

Here is the token bucket use case code:

Public function token() {$curr_time = time(); $inside_token = ($curr_time - $this->last_request_time) * $this->create_token_rate; $this->tokens = min($this->capacity_size, $this->tokens + $inside_token); $this->last_req_time = $curr_time; If ($this->tokens < 1) return false; $this->tokens = $this->tokens - 1; return true; }Copy the code

Interviewer: “is not said to speak of not zha ground, it seems to be quite understanding.” You have made the situation analysis and application process principles clear above. It’s basically the same principle, but it gets more and more compact, it gets better and better. Do you have any ideas if you use Redis to make token buckets?

Interviewer: Using Redis to make token buckets. I have seen PHP + Swool do stream limiting operations on the Internet before. LPush and rPop are used to add and remove tokens. Using Swool’s timer is the perfect solution to this problem. Here’s my code from memory:

@param int $num * @return int */ public function insert($num = 0) {$num = 0 $curr_count = intval($this->redis->lLen($this->queue_name)); $num = $this->max_volume >= $curr_count + $num? $num : $this->max_volume - $curr_count; If ($num <= 0) return 0; $tokens = array_fill(0, $num, 1); $result = $this->redis->lPush($this->queue_name,... $tokens); if ($result) return $num; return 0; }Copy the code

Interviewer: “Not bad not bad, this is still said to be explained by memory, feeling like actual combat appearance, give you a thumbs-up. We’ll have to let the other team leaders interview him to see how he does.” I did not expect that you have such a thorough understanding of interface flow limiting, so detailed, compared with my interview, you are a more solid foundation of one; Although I am not the most experienced, I am full of stamina. I hope I can further improve my skills in the future. Let’s take a break and interview you with the group leader of the second interview…

PS: The above is part of the code to realize the centralized scheme of limiting traffic, the detailed code: github.com/woshiamu/am…

The final summary

Interviewer: Hello, interviewer. Although I am not fully used in the actual practice, I will try my best to practice locally, and then simulate and create a large flow to test the results. In this way, I have deepened my understanding of these concepts. I hope to be admitted to your company and follow you to further practice in the project.

So what we did above is we went through a step-by-step guide and then we created a question to answer the flow of the whole flow limiting scheme. Let’s be honest: there are a lot of similar cases on the Internet; I hope to unlock the current limiting scene and actual combat through this slowly iterative introduction. So we prefer to use counters and Redis token buckets to achieve flow limiting, one is common use, one can be used accurately, according to their own scenarios to choose. Of course, there are more solutions, such as: flow limiting middleware (Google it for you), Nginx+Lua(I use this solution a lot), and so on can be better implemented.

Hayao Miyazaki once said, “What you meet is fate, and what you have is luck. It doesn’t matter if you’re not perfect. Everything has cracks, and that’s where the light comes in.” Our study is also so, only the interviewer abuse me thousands of times, I can treat the interviewer as the first love; Imperfection is the opportunity for improvement.

Ok, I am a mu, a worker who does not want to be eliminated at the age of 30 ⛽️ ⛽️ college.