Technical analysis

If you pay more attention to the current form of technology, you will know that microservices are hot at the moment. Of course, every coin has two sides, and microservices are not the master key to solve the problems of technology and architecture. If the benefits of servitization outweigh the disadvantages, CAI CAI still recommends servitization of the system. As the process of servitization continues to evolve, various concepts and technologies follow. Any solution exists to solve the problem. For example: fusing design, interface idempotence design, retry mechanism design, and today’s dishes to talk about the flow limiting design, and so on these technologies are almost filled in every system.

Limiting, in today’s sense, protects the system by limiting concurrent access or requests or requests within a time window. Once a critical limit is reached, existing systems can be protected from avalanche by denial of service, queuing, or waiting.

Limiting the flow is like doing the subway in the imperial capital. If you live in Xierqi or Tiantongyuan, you may realize it more deeply. I am more used to explain it from the perspective of consumers in terms of technology. The general reason for limiting traffic is that consumers have limited capacity and the purpose is to avoid system failure due to exceeding consumers’ capacity. Of course, there are other similar situations that can be solved by limiting the current.

Most forms of current limiting can be divided into two categories:

  1. Limit the number of customers. You can also say the maximum capacity of consumption. For example, the database connection pool is focused on the total number of connections. There is also the thread pool of dishes written before, which essentially limits the maximum consumption capacity of consumers.
  2. The number of requests that can be consumed. The number can be instantaneous or total concurrency over a period of time. That’s what CAI CAI is going to do for YY girl today.

In addition, traffic limiting can be performed in other forms, for example, traffic limiting by network traffic or CPU usage. According to the scope of traffic limiting, it can be divided into distributed traffic limiting, application traffic limiting, interface traffic limiting and so on. Regardless of the variation, current limiting can be expressed as follows:

Common technology implementation

Token bucket algorithm

A token bucket is a bucket that holds tokens of a fixed capacity. Tokens are added to the bucket at a fixed rate. When the bucket is full, tokens are discarded. Token buckets allow a certain amount of burst traffic, which can be processed as long as there are tokens, and support holding multiple tokens at a time. The token bucket contains tokens.

Bucket algorithm

Leaky bucket A leaky bucket of a fixed capacity flows out requests at a constant rate. The inflow rate is arbitrary. If the number of incoming requests reaches the leaky bucket capacity, new incoming requests are rejected. A leaky bucket can be regarded as a queue with a fixed capacity and a fixed outbound rate. The leaky bucket limits the outbound rate of requests. The leaky bucket contains requests.

counter

Sometimes we use counters to limit the total number of concurrent requests in a given period of time, such as database connection pools, thread pools, and spread-kill concurrency. Counter current limiting as long as the total number of requests within a certain period of time exceeds the set threshold, the current limiting is a simple and crude total quantity current limiting, rather than average rate current limiting.

In addition, different traffic limiting algorithms can be used in different service scenarios. However, there is only one rule: The traffic limiting policy that meets the current service scenario is the best

Other basic knowledge of current limiting please Baidu!!

Another way to solve the girl problem

Regression problem, YY sister’s problem, vegetables are not available to the above algorithms to help her. The dish preparation limits the flow in a way that limits the total number of requests by time period. The general idea is this:

  1. A ring is used to represent the passing request container.
  2. With a pointer to the current request to the location index, to determine the current request time and the current location of the last request time difference, according to this to determine whether is restricted.
  3. If the request passes, the current pointer moves forward one position; if it does not, it does not move position
  4. Repeat the above steps forever…….

Code is king

The following code can be used in a production environment unchanged or with minor modifications

The core idea of the following code is that the difference between the current time element and the current time determines whether the request is allowed or not, so that the request passes smoothly in time.

The idea is far more important than the language, any language can also be, please Phper, Golanger, Javaer to achieve their own again

Class LimitService {// Int currentIndex = 0; Int limitTimeSencond = 1; // Request loop container array DateTime? [] requestRing = null; Object objLock = new object(); public LimitService(int countPerSecond,int _limitTimeSencond) { requestRing = new DateTime? [countPerSecond]; limitTimeSencond= _limitTimeSencond; Public bool IsContinue() {lock (objLock) {var currentNode = requestRing[currentIndex]; // if the currentNode value plus the set second exceeds the current time, the limit is exceeded. = null&& currentNode.Value.AddSeconds(limitTimeSencond) >DateTime.Now) { return false; } requestRing[currentIndex] = datetime.now; // MoveNextIndex(ref currentIndex); } return true; } public bool ChangeCountPerSecond(int countPerSecond) {lock (objLock) {requestRing = new DateTime? [countPerSecond]; currentIndex = 0; } return true; } private void MoveNextIndex(ref int currentIndex) {if (currentIndex! = requestRing.Length - 1) { currentIndex = currentIndex + 1; } else { currentIndex = 0; }}}Copy the code

The test procedure is as follows:

static LimitService l = new LimitService(1000, 1); static void Main(string[] args) { int threadCount = 50; while (threadCount >= 0) { Thread t = new Thread(s => { Limit(); }); t.Start(); threadCount--; } Console.Read(); } static void Limit() { int i = 0; int okCount = 0; int noCount = 0; Stopwatch w = new Stopwatch(); w.Start(); while (i < 1000000) { var ret = l.IsContinue(); if (ret) { okCount++; } else { noCount++; } i++; } w.Stop(); Console.WriteLine($" use {w.lapsedmilliseconds}, allow: {okCount}, intercept: {noCount}"); }Copy the code

The test results are as follows:

The maximum time is 15 seconds, and a total of 1000000*50=5000000 requests are processed

No GC operations occurred and memory utilization was very low, processing 3 million + requests per second. The above program was modified to 10 threads in about 4 seconds

Processing will be faster if the server is strong or if there are fewer threads

Write in the last

The code above is simple, but it is the core of the stream limiting code (which can be optimized), and can be used in Webapi filters or other scenarios with other packages. Girl problem solved, do you want her to buy me dinner?

More interesting articles

  • Distributed large concurrent series
  • Architectural Design Series
  • Series of interesting algorithms and data structures
  • Design Pattern series