I have participated in the weekend study program. Please click the link to see more details

The introduction

  • In Web development, functionality is the cornerstone, in addition to functionality to external transport and protection is a priority. Because during the operation of the website may be caused by sudden traffic anomalies, it is possible to suffer malicious attacks by others
  • Therefore, our interface needs to limit the traffic. Commonly known as QPS is also a description of the flow
  • The token-bucket algorithm is now most likely to be used for traffic limiting because it guarantees more throughput. In addition to the token bucket algorithm there are its predecessors the leaky bucket algorithm and the simple counting algorithm
  • So let’s look at these four algorithms

Fixed time window algorithm

  • Fixed time window algorithms can also be called simple counting algorithms. There are a lot of things on the web that separate out counting algorithms. But the author thinks that the counting algorithm is an idea, and the fixed time window algorithm is one of his implementation
  • Including the following sliding time window algorithm is also an implementation of the counting algorithm. Because counting loses the essence of stream limiting if it is not bound to time. It becomes a no

advantages

  • If the traffic overflows within a fixed period of time, you can limit the traffic immediately. Each time window does not interact
  • Ensure the stability of the system in the time unit. Maximum throughput of the system in a guaranteed time unit

disadvantages

  • His biggest problem, as the chart shows, is criticality. In the critical state the worst case will receive twice the traffic request
  • In addition to the critical case, there is also a request threshold in the early part of a unit time window if it is quickly exhausted. Then the rest of the time will be unrequested. In this case, the system will be unavailable for a period of time due to a flash of traffic. This is not acceptable in a highly available system over the Internet.

implementation

  • All right, so we’ve seen the principles and the pros and cons. So let’s do it
  • First of all, when we implement this kind of counting, redis is a very good choice. Here we do it through Redis

controller

	@RequestMapping(value = "/start",method = RequestMethod.GET)
    public Map<String,Object> start(@RequestParam Map<String, Object> paramMap) {
        return testService.startQps(paramMap);
    }
Copy the code

service

@Override
public Map<String, Object> startQps(Map<String, Object> paramMap) {
    // Go online according to the QPS transmitted by the front end
    Integer times = 100;
    if (paramMap.containsKey("times")) {
        times = Integer.valueOf(paramMap.get("times").toString());
    }
    String redisKey = "redisQps";
    RedisAtomicInteger redisAtomicInteger = new RedisAtomicInteger(redisKey, redisTemplate.getConnectionFactory());
    int no = redisAtomicInteger.getAndIncrement();
    // Set the duration of the fixed time window to 1S
    if (no == 0) {
        redisAtomicInteger.expire(1, TimeUnit.SECONDS);
    }
    Time =2; QPS =3
    if (no > times) {
        throw new RuntimeException("qps refuse request");
    }
    // Return a success message
    Map<String, Object> map = new HashMap<>();
    map.put("success"."success");
    return map;
}
Copy the code

Results of the test

  • We set QPS =3, and we can see that after five concurrent entries, the first three access normally, and the last two fail. Wait for a while, we are accessing concurrently, the first three can be accessed normally again. That means the next time window

Sliding time window algorithm

  • The disadvantage of fixed time window – the critical value of double traffic problem. Our sliding time window is created.
  • In fact, it makes sense to change the time window statistics from fixed intervals to finer units for fixed time Windows.
  • In our fixed time window demo above we set the time unit to be 1S. For 1S, let’s split 1S into a timestamp.
  • A fixed time window is a statistical unit that moves backwards over time. And the sliding window of time is what we think of by imagining a unit of time that is fixed in relativistic terms, our abstract unit of time that moves by itself. The abstract unit of time is smaller than the actual unit of time.
  • Readers can take a look at the GIF below to understand.

advantages

  • It is essentially an improvement of the fixed time window algorithm. So the disadvantage of a fixed time window is its advantage.
  • The interior abstracts a sliding time window to make time smaller. There’s less of a problem with boundaries. Customer perception is weaker.

disadvantages

  • Both the fixed time window and sliding time window algorithms are optimized based on the counter algorithm, but their current-limiting strategies are too rough.
  • Why say rough? They don’t limit the flow of normal release. Once the current limit is reached, it will reject directly. So we lose some of the requests. It’s not very friendly for a product

implementation

  • Sliding the time window is to make the time more detailed. Above we do this with redis#setnx. We won’t be able to get a uniform record through him here. We should add smaller units of time to store into a collection summary. The current limiting is then calculated based on the total amount of the set. Redis’ ZSETT data structure is exactly what we need.

  • The reason for choosing zset is that Redis’ zset has a weight in addition to the value. It’s going to sort by that weight. If we use our time unit and timestamp as our weight, then we only need to get the statistics according to a timestamp range.

  • Because the elements in the Zset are unique, our values take the UUID or id generator such as the Snowflake algorithm

controller

	@RequestMapping(value = "/startList",method = RequestMethod.GET)
    public Map<String,Object> startList(@RequestParam Map<String, Object> paramMap) {
        return testService.startList(paramMap);
    }
Copy the code

service

		String redisKey = "qpsZset";
        Integer times = 100;
        if (paramMap.containsKey("times")) {
            times = Integer.valueOf(paramMap.get("times").toString());
        }
        long currentTimeMillis = System.currentTimeMillis();
        long interMills = inter * 1000L;
        Long count = redisTemplate.opsForZSet().count(redisKey, currentTimeMillis - interMills, currentTimeMillis);
        if (count > times) {
            throw new RuntimeException("qps refuse request");
        }
        redisTemplate.opsForZSet().add(redisKey, UUID.randomUUID().toString(), currentTimeMillis);
        Map<String, Object> map = new HashMap<>();
        map.put("success"."success");
        return map;
Copy the code

Results of the test

  • Use the same concurrency as the fixed time window. Why do we have a critical condition up here. Because in the code the unit time interval is larger than the fixed time interval. I showed you the fixed time window and the time unit was 1S and the worst case happened. Sliding time Windows are designed to be shorter. And when I set it to 10S, it didn’t get any worse
  • This is where the sliding ratio is better than the fixed one. If we had made it smaller it would have been less of a critical problem, but at the end of the day he would have avoided the critical problem

Bucket algorithm

  • Although sliding the time window can avoid the critical value problem to a great extent, it is still unavoidable
  • The timing algorithm also has a fatal problem. It can’t cope with a sudden surge of traffic because it simply refuses any additional traffic when it reaches the limit
  • For this problem, we continue to optimize our current-limiting algorithm. The leaky bucket algorithm was born

advantages

  • In the face of the current limit more flexible, not brutal rejection.
  • Added interface receptivity
  • Ensure the stability of downstream service reception. Evenly distributed

disadvantages

  • I think there are no faults. If I had to find fault with that, I’d have to say that leaky bucket capacity is a weakness

implementation

controller

@RequestMapping(value = "/startLoutong",method = RequestMethod.GET)
public Map<String,Object> startLoutong(@RequestParam Map<String, Object> paramMap) {
    return testService.startLoutong(paramMap);
}
Copy the code

service

  • In the service we use redis list function to simulate bucket effect. This is lab code. In the real world we also need to consider concurrency
@Override
public Map<String, Object> startLoutong(Map<String, Object> paramMap) {
    String redisKey = "qpsList";
    Integer times = 100;
    if (paramMap.containsKey("times")) {
        times = Integer.valueOf(paramMap.get("times").toString());
    }
    Long size = redisTemplate.opsForList().size(redisKey);
    if (size >= times) {
        throw new RuntimeException("qps refuse request");
    }
    Long aLong = redisTemplate.opsForList().rightPush(redisKey, paramMap);
    if (aLong > times) {
        // To prevent concurrent scenarios. I'm going to validate it after I've added it here. Even this code has problems with high concurrency. Demonstration here
        redisTemplate.opsForList().trim(redisKey, 0, times-1);
        throw new RuntimeException("qps refuse request");
    }
    Map<String, Object> map = new HashMap<>();
    map.put("success"."success");
    return map;
}
Copy the code

The downstream consumption

@Component
public class SchedulerTask {

    @Autowired
    RedisTemplate redisTemplate;

    private String redisKey="qpsList";

    @Scheduled(cron="*/1 * * * * ?" )
    private void process(a){
        // Consume two at a time
        System.out.println("Is spending...");
        redisTemplate.opsForList().trim(redisKey, 2, -1); }}Copy the code

test

  • We’re still going through 50 concurrent cycles of 10 visits. We can see that high throughput can only be achieved at the beginning. After the bucket’s capacity is filled. And the downstream droplet rate is slower than the upstream request rate. Access can only be received at a constant speed downstream.
  • His problems are obvious. The time window for the lack of leakage of the barrel is insufficient, but it is still insufficient. The request overflow problem cannot be completely avoided.
  • Request overflow is itself a catastrophic problem. None of the algorithms currently solve this problem. Just alleviating the problem he’s causing

Token bucket algorithm

  • Token buckets and leaky buckets are the same. I just changed the direction of the bucket.

  • The rate of discharge from the leaky bucket is constant, and if the flow increases suddenly, we can only refuse to enter the pool

  • But a token bucket is a token that goes into a bucket, and we know that normally a token is a string of characters that refuse to pool a token when the bucket is full, but in the face of high traffic normal plus our timeout leaves enough time to produce and consume the token. In this way, the request will not be rejected as much as possible

  • Finally, whether the token bucket is rejected for not getting the token, or the water in the leaky bucket is full and overflow, it is to ensure the normal use of most of the traffic, but a small part of the traffic is sacrificed


public Map<String, Object> startLingpaitong(Map<String, Object> paramMap) {
        String redisKey = "lingpaitong";
        String token = redisTemplate.opsForList().leftPop(redisKey).toString();
        // In normal cases, it is necessary to verify whether it is legal to prevent tampering
        if (StringUtils.isEmpty(token)) {
            throw new RuntimeException("Token bucket reject");
        }
        Map<String, Object> map = new HashMap<>();
        map.put("success"."success");
        return map;
    }

Copy the code

@Scheduled(cron="*/1 * * * * ?" )
    private void process(a){
        // Produce two at a time
        System.out.println("Is spending...");
        for (int i = 0; i < 2; i++) { redisTemplate.opsForList().rightPush(redisKey, i); }}Copy the code