一、什么是限流
首先来解释下什么是限流？
在日常生活中限流很常见，例如去有些景区玩，每天售卖的门票数是有限的，例如 2000 张，即每天最多只有 2000 个人能进去游玩。
而通常我们说的限流指代的是 限制到达系统的并发请求数，使得系统能够正常的处理 部分 用户的请求，来保证系统的稳定性。
二、应用场景
日常的业务上有类似秒杀活动、双十一大促或者突发新闻等场景，用户的流量突增，后端服务的处理能力是有限的，如果不能处理好突发流量，后端服务很容易就被打垮。
亦或是爬虫等不正常流量，我们对外暴露的服务都要以最大恶意去防备我们的调用者。我们不清楚调用者会如何调用我们的服务。假设某个调用者开几十个线程一天二十四小时疯狂调用你的服务，不做啥处理咱服务也算完了。更胜的还有DDos攻击。
还有对于很多第三方开发平台来说，不仅仅是为了防备不正常流量，也是为了资源的公平利用，有些接口都免费给你用了，资源都不可能一直都被你占着吧，别人也得调的。
三、常见限流算法
3.1 固定窗口算法
在一段时间间隔内（时间窗）进行计数，超过阈值则限制访问
public class RateLimiterSimpleWindow {
// 阈值
private static Integer QPS = 2;
// 时间窗口（毫秒）
private static long TIME_WINDOWS = 1000;
// 计数器
private static AtomicInteger REQ_COUNT = new AtomicInteger();
private static long START_TIME = System.currentTimeMillis();
public synchronized static boolean tryAcquire() {
if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
REQ_COUNT.set(0);
START_TIME = System.currentTimeMillis();
}
return REQ_COUNT.incrementAndGet() <= QPS;
}
}
固定窗口算法存在临界问题
假设系统每秒允许 2个请求，第一个时间窗口的后500ms和第二个时间窗口的前500ms都进行了2次请求
虽然窗口内的计数没超过阈值，但是全局来看1秒内进行了4次请求
3.2 滑动窗口算法
为了解决固定窗口临界问题，可以把固定窗口近一步划分成多个格子，每次向后移动一小格，而不是固定窗口大小
比如每分钟可以分为6个10秒中的单元格，每个格子中分别维护一个计数器，窗口每次向前滑动一个单元格。每当请求到达时，只要窗口中所有单元格的计数总和不超过阈值都可以放行
public class RateLimiterSlidingWindow {
/**
* 阈值
*/
private int qps = 2;
/**
* 时间窗口总大小（毫秒）
*/
private long windowSize = 1000;
/**
* 多少个子窗口
*/
private Integer windowCount = 10;
/**
* 窗口列表
*/
private WindowInfo[] windowArray = new WindowInfo[windowCount];
public RateLimiterSlidingWindow(int qps) {
this.qps = qps;
long currentTimeMillis = System.currentTimeMillis();
for (int i = 0; i < windowArray.length; i++) {
windowArray[i] = new WindowInfo(currentTimeMillis, new AtomicInteger(0));
}
}
/**
* 1. 计算当前时间窗口
* 2. 更新当前窗口计数 & 重置过期窗口计数
* 3. 当前 QPS 是否超过限制
*
* @return
*/
public synchronized boolean tryAcquire() {
long currentTimeMillis = System.currentTimeMillis();
// 1. 计算当前时间窗口
int currentIndex = (int)(currentTimeMillis % windowSize / (windowSize / windowCount));
// 2. 更新当前窗口计数 & 重置过期窗口计数
int sum = 0;
for (int i = 0; i < windowArray.length; i++) {
WindowInfo windowInfo = windowArray[i];
if ((currentTimeMillis - windowInfo.getTime()) > windowSize) {
windowInfo.getNumber().set(0);
windowInfo.setTime(currentTimeMillis);
}
if (currentIndex == i && windowInfo.getNumber().get() < qps) {
windowInfo.getNumber().incrementAndGet();
}
sum = sum + windowInfo.getNumber().get();
}
// 3. 当前 QPS 是否超过限制
return sum <= qps;
}
private class WindowInfo {
// 窗口开始时间
private Long time;
// 计数器
private AtomicInteger number;
public WindowInfo(long time, AtomicInteger number) {
this.time = time;
this.number = number;
}
// get...set...
}
}
3.3 漏桶算法
漏桶算法中的漏桶是一个形象的比喻，这里可以用生产者消费者模式进行说明，请求是一个生产者，每一个请求都如一滴水，请求到来后放到一个队列（漏桶）中，而桶底有一个孔，不断的漏出水滴，就如消费者不断的在消费队列中的内容，消费的速率（漏出的速度）等于限流阈值。即假如 QPS 为 2，则每 1s / 2= 500ms 消费一次。漏桶的桶有大小，就如队列的容量，当请求堆积超过指定容量时，会触发拒绝策略。
public final class LeakyBucket {
// 桶的容量
private int capacity = 10;
// 水滴的流出的速率 每1000毫秒流出1滴
private int leakRate = 1;
// 木桶剩余的水滴的量(初始化的时候的空的桶)
private AtomicInteger water = new AtomicInteger(0);
// 第一次请求之后,木桶在这个时间点开始漏水
private long leakTimeStamp;
public synchronized boolean tryAcquire() {
// 如果是空桶，就当前时间作为桶开始漏出的时间
if (water.get() == 0) {
leakTimeStamp = System.currentTimeMillis();
water.addAndGet(1);
return capacity != 0;
}
// 先执行漏水，计算剩余水量
int waterLeft = water.get() - ((int) ((System.currentTimeMillis() - leakTimeStamp) / 1000)) * leakRate;
water.set(Math.max(0, waterLeft));
// 重新更新leakTimeStamp
leakTimeStamp = System.currentTimeMillis();
// 尝试加水,并且水还未满
if ((water.get()) < capacity) {
water.addAndGet(1);
return true;
} else {
// 水满，拒绝加水
return false;
}
}
}
3.4 令牌桶算法
令牌桶算法同样是实现限流是一种常见的思路，最为常用的 Google 的 Java 开发工具包 Guava 中的限流工具类 RateLimiter 就是令牌桶的一个实现。令牌桶的实现思路类似于生产者和消费之间的关系。
系统服务作为生产者，按照指定频率向桶（容器）中添加令牌，如 QPS 为 2，每 500ms 向桶中添加一个令牌，如果桶中令牌数量达到阈值，则不再添加。
请求执行作为消费者，每个请求都需要去桶中拿取一个令牌，取到令牌则继续执行；如果桶中无令牌可取，就触发拒绝策略，可以是超时等待，也可以是直接拒绝本次请求，由此达到限流目的。
local tokens_key = KEYS[1] -- 存放令牌数量的key
local timestamp_key = KEYS[2] -- 存放最近一次拿令牌的时间
--redis.log(redis.LOG_WARNING, "tokens_key " .. tokens_key)
local rate = tonumber(ARGV[1]) -- 每秒往桶里放的令牌数
local capacity = tonumber(ARGV[2]) -- 桶最大容量
local now = tonumber(ARGV[3]) -- 当前时间
local requested = tonumber(ARGV[4]) -- 每次算几个令牌
local fill_time = capacity/rate -- 从零开始多久满
local ttl = math.floor(fill_time*2) -- key的存活时间，如果过了这个时间，肯定就满了，每必要存了
--redis.log(redis.LOG_WARNING, "rate " .. ARGV[1])
--redis.log(redis.LOG_WARNING, "capacity " .. ARGV[2])
--redis.log(redis.LOG_WARNING, "now " .. ARGV[3])
--redis.log(redis.LOG_WARNING, "requested " .. ARGV[4])
--redis.log(redis.LOG_WARNING, "filltime " .. fill_time)
--redis.log(redis.LOG_WARNING, "ttl " .. ttl)
local last_tokens = tonumber(redis.call("get", tokens_key)) -- 目前桶里的令牌数
if last_tokens == nil then
last_tokens = capacity
end
--redis.log(redis.LOG_WARNING, "last_tokens " .. last_tokens)
local last_refreshed = tonumber(redis.call("get", timestamp_key)) --最近一次取令牌的时间
if last_refreshed == nil then
last_refreshed = 0
end
--redis.log(redis.LOG_WARNING, "last_refreshed " .. last_refreshed)
local delta = math.max(0, now-last_refreshed) --上次取令牌到现在过了多少秒
local filled_tokens = math.min(capacity, last_tokens+(delta*rate)) -- 放新令牌后的总数
local allowed = filled_tokens >= requested -- 现在桶里令牌够不够执行一次
local new_tokens = filled_tokens -- 当前令牌数
local allowed_num = 0
if allowed then
new_tokens = filled_tokens - requested -- 拿走一次令牌后剩余令牌数
allowed_num = 1
end
--redis.log(redis.LOG_WARNING, "delta " .. delta)
--redis.log(redis.LOG_WARNING, "filled_tokens " .. filled_tokens)
--redis.log(redis.LOG_WARNING, "allowed_num " .. allowed_num)
--redis.log(redis.LOG_WARNING, "new_tokens " .. new_tokens)
redis.call("setex", tokens_key, ttl, new_tokens) -- 更新令牌数
redis.call("setex", timestamp_key, ttl, now) -- 更新最后一次执行时间
return { allowed_num, new_tokens }
四、限流算法比较
固定窗口算法实现简单，容易理解。和漏斗算法相比，新来的请求也能够被马上处理到。但是流量曲线可能不够平滑，有“突刺现象”，在窗口切换时可能会产生两倍于阈值流量的请求。而滑动窗口算法作为计数器固定窗口算法的一种改进，有效解决了窗口切换时可能会产生两倍于阈值流量请求的问题。
漏桶算法能够对流量起到整流的作用，让随机不稳定的流量以固定的速率流出，但是不能解决流量突发的问题。令牌桶算法作为漏斗算法的一种改进，除了能够起到平滑流量的作用，还允许一定程度的流量突发。
五、支持限流的组件
- Sentinel
- Resilience4j
- Gateway
- Nginx
- Guava
- Redisson