常用限流算法指南_限流算法效果由哪些因素决定

什么是限流

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

        举一个常见的例子：假设你家附近有一家三甲医院，其中某科室医生有限，每天只能够接待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);
        }
    }
}

使用场景总结

固定窗口计数器：实现非常简单，但是会存在临界窗口的问题和无法应对突发流量，如果系统能够容忍这种情况，为了能快速止损眼前的问题可以作为临时应急的方案。

滑动窗口计数器：很大程度上的缓解了临界窗口的问题，可以应对有少量突增流量场景，使用优先级比固定窗口更高。

漏桶算法：漏桶算法对于流量保持着宽进严出的策略，是流量最均匀的限流实现方式，一般用于流量“整形”，可以严格限时突发流量对后端服务的压力。

令牌桶算法：系统经常有突增流量，能够最大化利用服务的资源，是一种比较万金油的限流策略。

限流的难点

        每种限流方式都需要一个阈值来限制流量，如何确定这个阈值是一个难点。如果阈值定得太大，服务器可能无法承受；如果阈值定得太小，一些请求可能会被错误地拒绝，这会导致资源利用不充分，也会影响用户体验。

        有一种简单的方法可以估算阈值。首先，在实施限流之前，预估一个大概的阈值，然后不执行真正的限流操作，而是采用记录日志的方式进行打点。之后，对日志进行分析，查看限流效果，逐步调整阈值，推算出每台机器的处理能力和整个集群的处理能力。接着，可以对线上流量进行重放，测试真正的限流效果，并最终确定阈值并上线。

分布式限流器

       以上几种限流算法的实现都仅适合单机限流。虽然给每台机器平均分配限流配额可以达到限流的目的，但是由于机器性能，流量分布不均以及计算数量动态变化等问题，单机限流在分布式场景中的效果总是差强人意。

        在分布式系统中，仅仅使用单机的性能为指标作为限流的依据，极有可能将数据库、redis这种集中式的服务打挂，并且很难进行全局范围内的精确流量限制。因此需要一套分布式限流器在分布式环境中，对资源整体的QPS进行限流，解决因单机流量不均、实例数变化等场景造成的限流不准确、不易维护的问题。

        分布式限流最简单的实现就是利用中心化存储，将 单机限流存储在本地的数据存储到同一个存储空间中，如常见的Redis等。比较方便的一种实现方式是借助 Redis/Memcache做统一Token存储管理，然后实现上述所介绍的各种算法如令牌桶、计数器算法等来作为一个分布式限流器。

参考文献：面试必备：四种经典限流算法讲解