常用限流算法指南-Toy模板网

这篇具有很好参考价值的文章主要介绍了常用限流算法指南。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

什么是限流

限流是一种防止系统被过度请求压垮的算法。简单来说，限流就是对系统中的请求进行数量控制，确保系统可以正常处理每个请求而不会因为流量过大而宕机。

举一个常见的例子：假设你家附近有一家三甲医院，其中某科室医生有限，每天只能够接待50名患者就诊。如果某一天同时有200个人到医院看病，这时候如果医院没有进行任何控制措施，所有人都会挤在门诊的门口等待入座，导致拥堵和混乱，以及医疗资源挤兑。但如果你使用了限流算法，你可以控制每小时只接受5个顾客的预约，让其他人等待下一个小时再来，也就是需要提前挂号，按照挂号单上的就诊时间区间就诊。

在网络领域中，同样也需要限流来保护系统。比如，一些应用程序可能会因为接收到过多的流量而无法及时响应导致服务宕机。如果使用限流算法来控制请求速率，就可以有效地防止过多的请求集中到服务器上，从而保证系统的稳定性和可靠性。

常用限流算法指南

为什么需要限流

就像我们前面提到的，限制流量对于维护系统稳定性至关重要。但是，哪些场景会影响系统稳定性并需要采取流量限制措施呢?

在业务开发过程中，用户流量可能突然激增的情况有很多，比如限时抢购、促销或突发新闻。但是，后端系统的处理能力有限，如果不能处理突然的流量，很容易崩溃。

此外，如果我们的服务暴露在公众面前，很容易受到web抓取或DDoS等异常流量攻击。因此，我们需要提高警惕，对恶意来电者采取最大程度的预防措施。

综上所述，流量限制的原因是为了切断超出后端系统处理能力的请求，以保证系统的稳定性。

常用的限流算法

固定窗口算法

固定窗口算法是最简单的一种限流算法，它是通过在单位时间内维护的计数器来控制该时间单位内的最大访问量。例如，假设我们想要限制每分钟请求量不超过60，我们可以设置一个计数器，当请求到达时，如果计数器到达阈值，则拒绝请求，否则计数器+1。每分钟结束时，我们将计数器重置为0，以便下一分钟重新开始计数。

优点：实现简单，我们只需要存储时间窗口内的计数器即可。此外，该算法能够确保处理更多的最新请求，不会因为旧请求的堆积而导致新请求被饿死。

然而，该算法存在一个临界问题，即当两个时间窗口交界处时，瞬时流量可能为2n。在这种情况下，边界处的请求可能被均分或者放行，没有实现流量的限制。因此，在实际应用中，我们需要考虑更加复杂的算法来解决这个问题。

代码实现：

/**
* 固定窗口限流算法
*/
public class SimpleWindowLimiter {
   // 阈值
   private static int QPS = 2;
   // 时间窗口（毫秒）
   private static long TIME_WINDOWS = 1000;
   // 计数器
   private static AtomicInteger REQ_COUNT = new AtomicInteger();

   private static long START_TIME = System.currentTimeMillis();

   public static synchronized boolean tryAcquire() {
       if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
           REQ_COUNT.set(0);
           START_TIME = System.currentTimeMillis();
       }
       return REQ_COUNT.incrementAndGet() <= QPS;
   }
}

滑动窗口限流算法

为了解决固定窗口大小所带来的临界问题，可以采用将固定窗口进一步细分成多个小格子的方法，并且每次向后滑动一个小格子的方式，而不是采用固定窗口的方式。

例如，将每秒钟分成5个0.2秒钟的小格子，每个小格子维护一个计数器，每次向前滑动一个小格子。当有请求到达时，只要窗口中所有小格子的计数总和不超过预设的阈值，则该请求可以被放行。值得注意的是，TCP协议中的数据包传输同样也采用了滑动窗口的方式进行流量控制。

优点：解决了计数器中的临界问题。当窗口划分的粒度越细，则流量控制更加精准和严格。

缺点：当窗口中流量到达阈值时，流量会瞬间切断，在实际应用中的限流效果往往不是把流量一下子掐断，而是让流量平滑地进入系统当中。

代码实现：

    /**
     * 限流方法
     *
     * @param key 限流标识
     * @param period 限流时间范围（单位：秒）
     * @param maxCount 最大运行访问次数
     */
    private static boolean isPeriodLimiting(String key, int period, int maxCount) {
        long nowTimes = System.currentTimeMillis();
        // 删除非时间段内的请求数据（清除旧访问数据，比如 period=60 时，标识清除 60s 以前的请求记录）
        JEDIS_CLIENT.zremrangeByScore(key, 0, nowTimes - period * 1000);
        long currCount = JEDIS_CLIENT.zcard(key); // 当前请求次数
        if (currCount >= maxCount) {
            // 超过最大请求次数，执行限流
            return false;
        }
        // 未达到最大请求数，正常通过
        JEDIS_CLIENT.zadd(key, nowTimes, "" + nowTimes); // 请求记录 +1
        return true;
    }

漏桶算法

如果我们把服务比作是一个漏桶，请求比作是水滴，水滴持续不断地滴入桶中，底部再定速流出。如果水滴滴入的速率大于流出的速率，当桶中的水满时就会溢出。

漏桶算法的规则如下：当请求来了放入桶中，如果桶内的请求量满了拒绝请求，服务只能定速地从桶内拿请求并处理。

优点：平滑突发的流量，提供一种机制来确保网络中的突发流量被整合成平滑稳定的流量。

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

代码实现：

/**
 * 漏桶
 */
public class LeakyBucketLimiter {
    //流水速率  固定
    private double rate;
    //桶的大小
    private double burst;
    //最后更新时间
    private long refreshTime;
    //桶里面的水量
    private int water;

    public LeakyBucketLimiter(double rate, double burst) {
        this.rate = rate;
        this.burst = burst;
    }

    /**
     * 刷新桶的水量
     */
    private void refreshWater() {
        LocalDateTime time = LocalDateTime.now(); //每秒生成
        int now = time.getSecond();
        //现在时间-上次更新的时间   中间花费的时间(秒)*流水速率=流水量(处理的请求的数量)  通过上次水总量减去流水量等于现在的水量
        water = (int) Math.max(0, water - (now - refreshTime) * rate);
        //更新上次时间
        refreshTime = now;
    }

    public synchronized boolean tryAcquire() {
        // 刷新桶的水量
        refreshWater();
        // 如果桶的水量小于桶的容量就可以添加进来
        if (water < burst) {
            water++;
            return Boolean.TRUE;
        } else {
            return Boolean.FALSE;
        }
    }

    public static final LeakyBucketLimiter LEAKY_BUCKET = new LeakyBucketLimiter(1, 5);

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10; i++) {
            LocalTime now = LocalTime.now();
            if (!LEAKY_BUCKET.tryAcquire()) {
                System.out.println(now + "被限流");
            } else {
                System.out.println(now + "正常执行方法");
            }
        }
    }
}

令牌桶算法

令牌桶算法主要是用于限制流量的平均流入速率，并且允许出现一定程度的突发流量。在令牌桶算法中，固定容量的桶中会以一定速率放入令牌，当用户请求到来时，必须先获取到令牌才能继续执行，否则进行等待或者直接丢弃该请求。需要注意的是，虽然令牌桶和漏桶都可以用于在高并发、大流量的场景下实现流量管制，让系统负载处于比较均衡的水位，不会因为峰值流量过大而导致系统被击垮，但是这两种算法的限流方向是截然不同的，令牌桶限制的是流量的平均流入速率，且允许一定程度的突发流量，而漏桶限制的是流量的平均流出速率，且流出速率是固定不变的。

令牌桶算法的规则如下：定速的往桶内放入令牌,如果令牌的数量超过桶的容量，丢弃令，请求来了先向桶内索要令牌，索要成功则通过，反之拒绝。

优点：令牌桶算法可以控制请求的处理速度，可以根据实际情况动态调整生成令牌的速率，可以实现较高精度的限流，还可以处理突发流量。

缺点：实现较为复杂，令牌桶算法需要在固定的时间间隔内生成令牌，因此要求时间精度较高。

/**
 * Guava 实现限流：令牌桶
 */
public class GuavaRateLimiter {
    // 每秒产生 10 个令牌（每 100 ms 产生一个）
    public static final RateLimiter RATE_LIMITER = RateLimiter.create(10);

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 11; i++) {
            new Thread(() -> {
                LocalTime now = LocalTime.now();
                // 尝试获取 1 个令牌
                if (!RATE_LIMITER.tryAcquire()) {
                    System.out.println(now + "-被限流");
                } else {
                    System.out.println(now + "-正常执行方法");
                }
            }).start();
            Thread.sleep(50L);
        }
    }
}