In high concurrency scenarios, we often optimize and protect the system in such ways as: multi-level caching, resource isolation, fusing degradation, limiting traffic, and so on.

Today we are going to talk about limiting current.

primers

Why do we need to limit traffic?

Take A simple example. Normally, an employee A can handle 10 tasks every day, but suddenly 100 tasks come one day. At this time, if employee A still handles 100 tasks, there is only one possibility that the employee will be overwhelmed.

If we knew in advance that 100 tasks would come back, we could add employees or define message queues and so on. But we often don’t anticipate the unexpected. According to Murphy’s Law, bad things happen, and it’s possible that a failure in one spot will cause a failure in the whole world (an avalanche). So we had to do something to protect our system. Limiting traffic is one of them.

You can also take some traffic limiting measures to avoid affecting the whole system.

Current limiting counter (Sliding window protocol)

Speed limit, the first thing that might come to mind is that I’m using a counter. If I exceed the counter threshold, I’m going too fast. One counter per second.


Counter. PNG

I’ve only taken screenshots of the main code snippets for ease of reading.




Code snippet

This has a problem is: the granularity is too large, uneven, for 1 second, can not distinguish.

Can we break down the granularity, one second into 10 100 milliseconds. Each 100 ms has a counter. Those of you who know TCP/IP know that TCP/IP has a “sliding window protocol” to increase and control transmission speeds.

No matter how fine it is, it cannot solve the problem of constant speed limitation.

And there is a critical point problem, for example, if a second limit 10 requests, in the first seconds, 2 seconds, 10 seconds during the second half of the time request 1, 2 seconds before half 10 request, during the second half of the 1 seconds + 2 seconds before half time in one second is composed of 20 request, did not have the effect of the speed limit.

Is there a better way?

Leakage bucket algorithm for speed limiting mode

In life, if a bucket has a small hole, and we fill it with water, we can see that the water is falling drop by drop at a uniform speed, which we can achieve this way through the program.

A drop of water is a request. If the bucket is full, the request is rejected. If the bucket is not full, the request is processed.


Leaky bucket algorithm. PNG

Code snippet




Bucket algorithm


In snippets of code

  • Start by calculating how much water has leaked since this request came in compared to the last one.
  • See how much water is left in the bucket and if it overflows.
  • If the overflow rejects the request, if the current drop is not added. Process requests.

In addition to limiting the average data transfer rate, some degree of burst transmission is required for many application scenarios. In this case, the leaky bucket algorithm may not be suitable, but the token bucket algorithm is more suitable.

What does that mean? This means that I have been idle for a long time and suddenly a lot of requests come in (in bucket capacity) and I have to process them quickly.

Token bucket algorithm for speed limiting mode

Generate tokens at a constant rate, drop them in the bucket, and see if there are any extra tokens on each request. If a token is obtained for normal business, there is no speed limit.


The token bucket. PNG

Code snippet




Token bucket code


In this way, you can allow instantaneous mass processing and then do speed limiting processing.

  • When the request comes in, count the number of tokens currently in the bucket. By doing this, you don’t have to start a thread to place tokens uniformly, which is called lazy calculation.
  • Then count the number of tokens owned by the bucket. Then get the token. Reject or process.

The above code can be found at github.com/hirudy/java… To find it.

Stand-alone limiter RateLimiter

Amway is an efficient speed limiter. Google’s base library, Guava, includes RateLimiter, a toket-based limiter. It’s easy to use.




The test sample

All see here, pay attention to a public number, exchange and study together




Rudy_tan_home is an official wechat account