1 限流介绍

1.1 什么是限流

顾名思义，就是流量限制。限流是对服务下游的保护，保证在大量请求面前，还能从容不迫的提供正常服务；

限流是对某一时间窗口内的请求数进行限制，保持系统的可用性和稳定性，防止因流量激增而导致的系统运行缓慢或宕机。

1.2 为什么要限流

当瞬时海量请求传入服务下游，往往会对下游服务造成毁灭性打击，最直接的，可能导致数据库压力过大，性能明显下降甚至崩溃；
恶意高频率访问，如果不做任何处理，可能使服务下游响应速度下降；

1.3 常见的限流算法

常见有4种限流算法，分别是：固定窗口、滑动窗口、漏桶算法以及令牌桶算法。

2 限流算法实现

本文只讨论应用层面的限流实现，即单机限流。

2.1 固定窗口

2.1.1 实现原理

在固定时间窗口内累计访问次数，当访问次数达到设定的时间窗口阈值时，触发限流策略，当进入下一个时间窗口时进行访问次数的清零。如图所示。

2.1.2 代码

@Slf4j
public class FixedRateLimiter {
    Logger logger = LoggerFactory.getLogger(FixedRateLimiter.class);
    long size;
    int maxCount;
    AtomicInteger counter = new AtomicInteger(0);
    long rightBorder; //窗口右边界
    public FixedRateLimiter(long windowSize, int maxRequestCount) {
        this.size = windowSize;
        this.maxCount = maxRequestCount;
        this.rightBorder = System.currentTimeMillis() + windowSize;
    }
    public synchronized boolean tryAcquire() {
        long currentTime = System.currentTimeMillis();
        if (rightBorder < currentTime) {
            while ((rightBorder += size) < currentTime){
                rightBorder += size;
            }
            counter = new AtomicInteger(0);
            logger.info("窗口重置");
        }

        if (counter.intValue() < maxCount) {
            counter.incrementAndGet();
            logger.info("请求成功");
            return true;
        } else {
            logger.info("请求失败");
            return false;
        }
    }
}

2.1.3 优缺点

优点：实现简单；

缺点：存在边界问题。例如时间窗口为5秒，限流200个请求，考虑前四秒没有请求，在第四秒到第六秒之间来了400个请求，由于第五秒会重置permits，所以导致400个请求都能通过，突破了我们的5秒内只允许200个请求的限制。

2.2 滑动窗口

2.2.1 算法原理

基于固定窗口，滑动窗口的起止时间是动态的，窗口的大小固定，这样能够较好地处理窗口边界问题。更具体的，在固定窗口的基础上，将设置的窗口大小等份分割为若干子窗口，每次只滑动一个子窗口，同时每个子窗口单独计数，但是所有子窗口的计数求和不应大于整体窗口的阈值。这样的话，当新请求的时间点大于时间窗口右边界时，窗口右移一个子窗口，最左边的子窗口的计数值舍弃。如图所示，假设设置4秒内允许通过200请求，分块后变为每秒50请求，总体4秒200请求。

2.2.2 算法实现

@Slf4j
public class SlidingWindowRateLimiter {
    Logger logger = LoggerFactory.getLogger(SlidingWindowRateLimiter.class);
    long size;
    int shardNum; //分片窗口数
    int maxPermits; //允许通过的最大请求数
    int[] shardCount;   //各个窗口内请求数
    int totalCount; //当前请求总数
    int shardId; //当前窗口下标
    long subWindowSize; //每个子窗口大小，毫秒
    //窗口右边界
    long rightBorder;

    public SlidingWindowRateLimiter(long windowSize, int shardNum, int maxRequestCount) {
        this.size = windowSize;
        this.shardNum = shardNum;
        this.maxPermits = maxRequestCount;
        this.shardCount = new int[shardNum];
        this.subWindowSize = windowSize / shardNum;
        this.rightBorder = System.currentTimeMillis();
    }
    public synchronized boolean tryAcquire() {
        long currentTime = System.currentTimeMillis();
        if (rightBorder < currentTime) {
            do {
                // 为新的子窗口分配id
                shardId = (++shardId) % shardNum;
                // 释放过期的 permits
                totalCount -= shardCount[shardId];
                // 为新的子窗口初始化计数器
                shardCount[shardId] = 0;
                // 移动有边界
                rightBorder += subWindowSize;
                logger.info("窗口重置");
            } while (rightBorder < currentTime);
        }

        if (totalCount < maxPermits) {
            logger.info("请求成功:{}", shardId);
            shardCount[shardId]++;
            totalCount++;
            return true;
        } else {
            logger.info("请求失败");
            return false;
        }
    }
}

2.2.3 优缺点

优点：解决了固定窗口算法的窗口边界问题。

缺点：还是存在限流不够平滑的问题。

2.3 漏桶算法

2.3.1 原理

漏桶算法可以有效地控制数据的传输速率以及防止网络拥塞。顾名思义，如果将外部请求比作注入漏桶的水，漏桶会存储一定水量并以固定速率出水，即匀速通过请求，如果请求量超过漏桶容量则会被丢弃，消息中间件就是采用漏桶算法的思想。如图所示：

2.3.2 算法实现

@Slf4j
public class LeakyBucketRateLimiter {
    Logger logger = LoggerFactory.getLogger(LeakyBucketRateLimiter.class);
    int capacity;
    AtomicInteger waterLevel = new AtomicInteger(); // 当前水位
    long startTimestamp;
    int leakRate;

    public LeakyBucketRateLimiter(int capacity, int leakRate) {
        this.capacity = capacity;
        this.leakRate = leakRate;
    }

    public synchronized boolean tryAcquire() {
        //桶中没有水， 重新开始计算
        if (waterLevel.get() == 0) {
            logger.info("开始漏水");
            startTimestamp = System.currentTimeMillis();
            waterLevel.incrementAndGet();
            return waterLevel.get() < capacity;
        }
        //先漏水，计算剩余水量
        long currentTime = System.currentTimeMillis();
        int leakedWater = (int) ((currentTime - startTimestamp) / 1000 * leakRate);
        logger.info("开始放行时间:{}, 当前时间:{}. 放行流量:{}", startTimestamp, currentTime, leakedWater);
        if (leakedWater != 0) {
            // 重新计算水位
            int leftWater = waterLevel.get() - leakedWater;
            waterLevel.set(leftWater > 0 ? leakedWater : 0);
            // 重置开始时间戳
            startTimestamp = System.currentTimeMillis();
        }
        logger.info("剩余容量:{}", capacity - waterLevel.get());
        if (waterLevel.get() < capacity) {
            logger.info("请求成功");
            waterLevel.incrementAndGet();
            return true;
        } else {
            logger.info("请求失败");
            return false;
        }
    }
}

2.3.3 优缺点

优点： 通过固定速率处理请求，可以有效的避免流量突发情况，具有很好的削峰填谷的作用，同时面对大量请求时，直接丢弃超过桶容量的请求，实现保护下游服务的目的。

缺点：

虽然可以用漏桶出口的固定速率平滑突增流量，但也正是由于固定速率，使得在流量较小的时候也无法更快的处理请求；
丢失请求，在超过桶容量的流量请求时，会丢弃掉超过的部分；

2.4 令牌桶算法

2.4.1 原理

令牌桶算法可以总结为：以固定速率生成令牌放入桶中，令牌数不会超过桶容量，当有请求到来时，会尝试申请一块令牌，如果没有令牌则会拒绝请求，有足够的令牌则会处理请求，并且减少桶内令牌数，当然，你可以申请多块令牌，这就为处理突发流量提供前提。如图所示：

2.4.2 代码实现

可以直接用Guava的RateLimiter，他是基于令牌桶实现的。

导入依赖：

<dependency>
	<groupId>com.google.guava</groupId>
	<artifactId>guava</artifactId>
	<version>31.0.1-jre</version>
</dependency>

代码：

@Slf4j
public class GuavaRateLimiter {

    private RateLimiter rateLimiter;

    public GuavaRateLimiter(double permitsPerSecond) {
        this.rateLimiter = RateLimiter.create(permitsPerSecond);
    }
    public GuavaRateLimiter(double permitsPerSecond, long warmUpPeriodAsSecond, TimeUnit timeUnit) {
        this.rateLimiter = RateLimiter.create(permitsPerSecond, warmUpPeriodAsSecond, timeUnit);
    }

    public boolean tryAcquire(int permits){
        return rateLimiter.tryAcquire(permits);
    }

    public boolean tryAcquire(int permits, long warmUpPeriodAsSecond, TimeUnit timeUnit){
        return rateLimiter.tryAcquire(permits, warmUpPeriodAsSecond, timeUnit);
    }
    
    public double acquire() {
        return rateLimiter.acquire();
    }
}

预热：为什么要做预热，可以使下游更平滑的接受大量突发请求，在预热期间，速率逐渐升高，从初始速率逐渐趋近于指定的速率。