This is the 28th day of my participation in the August Challenge

Current limiting is heard more in our life, such as tourism, need to advance booking tickets for the scenic spot, actually this is also a kind of current limiting measures, if the traffic is big, in the software system cannot withstand a larger traffic, such problems if we don’t do some current limiting operation, That our system may cause the whole system is not available, the current limiter is a kind of system protection, when flow request access to more than a certain amount of time, you need to restrict the flow of the request, the request of the excess abandoned, to guarantee the system availability, current limit in the gateway, using more gateway need to limit flow to backend request too much, As a result, the back-end application cannot support so large a traffic request and can break down, the commonly used traffic limiting algorithms are: counter, missed bucket algorithm, token bucket, sliding window and other traffic limiting algorithms.

counter

  • An overview of the

The system counts the number of access requests in a specified period. When the number of access requests reaches the upper limit, the subsequent access requests are denied and can only be accessed in the next period. To implement this algorithm is simple, but when in a time period, there are a lot of request, will be thrown away a large number of requests in an instant, 1 second limit access to 5 times, for example, if the first five times processing is completed in 0.1 seconds, 0.9 seconds behind couldn’t request access to, services also deal with idle state, thus causing white waste of resources. Adopting counter scene, when sending the verification code, with more to prevent malicious brush verification code, verification code resource waste, general will limit this time can only send a 1 minute, when the number of input after reaching a number of times, will be frozen account login, every decrease after a period of time can be frozen, log back in.

  • Introduction to algorithm Implementation

The Semaphore class in the Java package is used to realize the implementation. A thread is opened in the code and the number of times of Semaphore is reset every 1 second. Then the while loop is used to simulate non-stop data requests

  • Simple code
    final Semaphore semaphore = new Semaphore(5);

        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        service.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run(a) {
                semaphore.release(5); }},1000.1000, TimeUnit.MILLISECONDS);

        // Simulate requests falling from the sky
        while (true) {
          // Determine the counter
          semaphore.acquire();
    }
Copy the code

Bucket algorithm

  • An overview of the

Bucket algorithm, like we usually meet bucket full of water, has a small hole in the following, at a constant speed can be water leakage, when we will meet under the barrels in tap water, when water is large, will soon fill the bucket, when the water will overflow, when the tap water is small or not, the hole will slowly put a bucket of water leakage. Here’s a picture from the InternetThis algorithm can effectively block the external request, when the request more than my bucket capacity, will be extra requests to throw away, but for internal is uniform request, when there is a peak business, will be extra request away, unable to cope with traffic peak, peak when the business will throw away a lot of requests, the business is not very friendly. The leaky bucket algorithm is commonly used in Nginx. It can limit the number of times that the same client accesses a website to prevent malicious attacks by the client.

HTTP {#$binary_remote_addr specifies that the remote_addr identifier is used as the key to restrict the same client IP address. #zone=one:10m indicates that a memory region with a size of 10m named ONE is generated to store the frequency information of access. #rate=1r/s indicates that clients with the same identity are allowed per second1Limit_req_zone $binary_REMOTE_ADDR zone=one:10m rate=1r/s; Server {location /limited/ {#zone=one #burst=5Buffer where requests exceeding the limit of access frequency can be placed first, similar to the queue length in code. #nodelay If set, returns when the access frequency is exceeded and the buffer is full503If not set, all requests are queued, similar to put or offer in code. limit_req zone=one burst=5nodelay; }}Copy the code
  • Introduction to algorithm Implementation

Then a thread is used to remove the elements from the LinkedBlockingQueue every one second to indicate that the request is being executed. A while loop is then used to continuously add elements to the LinkedBlockingQueue. If the LinkedBlockingQueue is not full, the element is added successfully, and when the queue is full, the element is thrown away.

  • Simple code
        // bucket, implemented with blocking queue, capacity 5
        final LinkedBlockingQueue<Integer> que = new LinkedBlockingQueue(5);
        // Timer, equivalent to service window, 1s processing one
        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        service.scheduleAtFixedRate((Runnable) () -> {
            int v = que.poll();
            System.out.println("Deal with:" + v);
        }, 1000.1000, TimeUnit.MILLISECONDS);
        int i = 0;
        while (true) {
            i++;
              System.out.println("put:" + i);
              que.offer(i, 1000, TimeUnit.MILLISECONDS);
        }
Copy the code

The token bucket

  • An overview of the

The token bucket is an upgrade of the leaky bucket algorithm. The leaky bucket limits the size of the leaky bucket, and the token limits the flow rate of water from the faucet each time, and then flows the water from the faucet into the bucket. The bucket can be expanded according to the amount of water, and then the bucket can be continuously scooped out of the bucket for treatment by subsequent requests. Here, a picture on the Internet is used to describe the implementation logic of the algorithmIn practice, the gateway of SpringCloud can be configured with token bucket algorithm to realize flow limiting control

‐ ID: limit_route URI: HTTP://localhost:8080/test Filters: ‐ name: RequestRateLimiter args: # Key for limiting streams. IpKeyResolver is a spring managed Bean that needs to be extended. Key ‐resolver:'#{@ipResolver}'# Average rate of token bucket replenishment per second, equivalent to the provisioning frequency in the code Redis ‐rate‐limiter. ReplenishRate:1‐rate‐limiter. BurstCapacity:3
Copy the code
  • Introduction to algorithm Implementation

Set the maximum capacity of the bucket, and then start a thread to increase the capacity of the Semaphore bucket at a uniform speed. When the capacity is smaller than the specified capacity, the token is stored in the bucket, and then simulate the request, obtain signals from Semaphore, when the subsequent execution logic is obtained. Not getting one waits until a token is generated.

  • Simple code
        final Semaphore semaphore = new Semaphore(3);
        ScheduledExecutorService service = Executors.newScheduledThreadPool(1);
        service.scheduleAtFixedRate(() -> {
            if (semaphore.availablePermits() < 3) { semaphore.release(); }},1000.1000, TimeUnit.MILLISECONDS);
Copy the code

The sliding window

  • An overview of the

Sliding window can be understood as splitting the limited number of times within a cycle into multiple segments, and the processing request of each segment is smaller than the upper limit of the segment, and the control of requests is more refined. Using a picture on the Internet, you should see it clearly, each time the window keeps sliding forward

The sliding window algorithm is widely used in the process of sending and reading TCP packets