所有分类
  • 所有分类
  • 未分类

常见的限流算法的原理以及优缺点

简介

说明

本文介绍限流常用的算法及其优缺点。

常用的限流算法有:

  1. 计数器(固定窗口)算法
  2. 滑动窗口算法
  3. 漏桶算法
  4. 令牌桶算法

下面将对这几种算法进行分别介绍,并给出具体的实现。

限流的含义

限流是指在系统面临高并发、大流量请求的情况下,限制新的流量对系统的访问,从而保证系统服务的安全性。

限流会对少部分用户的请求直接进行拒绝或者延迟处理,影响这些用户的体验。衡量系统处理能力的指标是每秒的QPS或者TPS,假设设置的系统每秒的流量阈值是1000,理论上一秒内有第1001个请求进来时,那么这个请求就会被限流。

以web服务、对外API为例,有以下几种可能导致机器被拖垮:

  1. 用户增长过快
  2. 因为某个热点事件(秒杀、微博热搜)
  3. 竞争对象爬虫
  4. 恶意的刷单

计数器算法

概述

计数器算法是限流算法里最简单也是最容易实现的一种算法。方案是:在单位时间内累加访问次数,当访问次数达到设定的阈值时,触发限流策略,当进入下一个单位时间时访问次数清零。

假设限制每分钟请求量不超过100。方法是:设置一个计数器,当请求到达时如果计数器到达阈值,则拒绝请求,否则计数器加1;每分钟重置计数器为0。如下图所示:

代码示例

public class CounterTest {
    public long timeStamp = getNowTime();
    public int reqCount = 0;
    public final int limit = 100; // 时间窗口内最大请求数
    public final long interval = 1000; // 时间窗口ms

    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        } else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }

    public long getNowTime() {
        return System.currentTimeMillis();
    }
}

优缺点

优点

简单,最容易实现。

缺点

临界问题(突刺现象)。

假设有一个恶意用户,他在0:59时,瞬间发送了100个请求,并且1:00又瞬间发送了100个请求,那么这个用户在 1秒里面,瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求,也就是每秒钟最多1.7个请求,用户通过在时间窗口的重置节点处突发请求, 可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞,压垮我们的应用。

刚才的问题其实是因为我们统计的精度太低。那么如何很好地处理这个问题呢?或者说,如何将临界问题的影响降低呢?我们可以看下面的滑动窗口算法。

滑动窗口算法

概述

滑动窗口:为了避免计数器中的临界问题,让限制更加平滑,将固定窗口中分割出多个小时间窗口,分别在每个小的时间窗口中记录访问次数,然后根据时间将窗口往前滑动并删除过期的小时间窗口。如下图所示:

整个红色的矩形框表示一个时间窗口,一个时间窗口是1分钟。我们将将滑动窗口 划成了6格,每格代表的是10秒钟。每过10秒钟,时间窗口往右滑动一格,每个格子都有自己独立的计数器counter,比如当一个请求 在0:35秒到达,那么0:30~0:39对应的counter就会加1。

滑动窗口怎么解决刚才的临界问题的呢?0:59到达的100个请求会落在灰色的格子中,而1:00到达的请求会落在橘黄色的格 子中。当时间到达1:00时,我们的窗口会往右移动一格,那么此时时间窗口内的总请求数量一共是200个,超过了限定的100个,所以此时能够检测出来触发了限流。

回顾刚才的计数器算法可以发现,计数器算法也是滑动窗口的一种。它没有对时间窗口做进一步地划分,所以只有1格。当滑动窗口的格子划分的越多,那么滑动窗口的滚动就越平滑,限流的统计就会越精确。

优缺点

优点

  1. 可以基本解决计数器算法的临街问题。

缺点

  1. 除了需要一个计数器来记录时间窗口内接口请求次数之外,还需要记录在时间窗口内每个接口请求到达的时间点,对内存的占用会比较多。 

漏桶算法

概述

请求就像水一样以任意速度注入漏桶,桶会按照固定的速度将水漏掉。当注入速度持续大于漏出的速度时,漏桶会变满,此时新进入的请求将会被丢弃(也可以延迟处理)。

限流 和 整形 是漏桶算法的两个核心能力。

代码示例

public class LeakyBucketLimiter {
    /**
     * 上次请求到来的时间
     */
    private long preTime = System.currentTimeMillis();
    /**
     * 漏水速率,n/s
     */
    private int leakRate;
    /**
     * 储蓄桶容量
     */
    private int capacity;
    /**
     * 当前水量
     */
    private int water;
 
    public LeakyBucketLimiter(int leakRate, int capacity) {
        this.leakRate = leakRate;
        this.capacity = capacity;
    }
 
    //省略get与set方法
 
    public boolean limit() {
        long now = System.currentTimeMillis();
 
        //先漏水,计算剩余水量
        water = Math.max(0, water - (int) ((now - preTime) / 1000) * leakRate);
        preTime = now;
 
        //桶未满
        if (water + 1 <= capacity) {
            water++;
            return true;
        }
 
        return false;
    }
}

优缺点

优点

  1. 确保网络中的突发流量被整合成平滑稳定的额流量。

缺点

  1. 漏桶对流量的控制过于严格,在有些场景下无法处理突发流量,不能充分使用系统资源。
    1. 因为漏桶的漏出速率是固定的,即使在某一时刻下游能够处理更大的流量,漏桶也不允许突发流量通过。

令牌桶算法

概述

令牌桶算法:以恒定速率向令牌桶发送令牌,请求到达时,尝试从令牌桶中拿令牌,只有拿到令牌才能放行,否则会触发限流策略(拒绝或者延迟处理)。令牌桶大小固定,若令牌桶已满,则不会生成新令牌。

令牌桶算法既能像漏桶那样匀速,又能像计数器那样处理突发请求。

令牌桶算法是流量整形(Traffic Shaping)和限速(Rate Limiting)最常用的算法。Nginx的limit_req模块就是使用令牌桶实现请求限流。

令牌桶示意图如下:

代码示例

public class TokenBucketLimiter {
    /**
     * 上次请求到来的时间
     */
    private long preTime = System.currentTimeMillis();
    /**
     * 放入令牌速率,n/s
     */
    private int putRate;
    /**
     * 令牌桶容量
     */
    private int capacity;
    /**
     * 当前令牌数
     */
    private int bucket;
 
    public TokenBucketLimiter(int putRate, int capacity) {
        this.putRate = putRate;
        this.capacity = capacity;
    }
 
    //省略get与set方法
 
    public boolean limit() {
        long now = System.currentTimeMillis();
 
        //先放入令牌,再获取令牌
        bucket = Math.min(capacity, bucket + (int) ((now - preTime) / 1000) * putRate);
        preTime = now;
 
        if (bucket == 0) {
            return false;
        }
 
        bucket--;
        return true;
    }
}

优缺点

优点

既能限流,又能接受突发请求。

处理突发请求的原理:当请求较少时,令牌桶中会积累一定数量的令牌,使得系统可以应对突发的请求;当请求增加时,令牌桶中的令牌可能会被消耗完,从而限制请求的处理速率。

缺点

这么完美了,还能有啥缺点?瑕不掩瑜😆 ​

3

评论0

请先

显示验证码
没有账号?注册  忘记密码?

社交账号快速登录