本文目录：
-
什么场景需要限流？
-
计数器算法
-
滑动窗口计数算法
-
漏桶算法
-
令牌桶算法
-
补充：分布式限流
哈喽，大家好，我是呼噜噜。今天我们来聊一聊在企业级项目中，常见的几种限流手段的原理及其实现。
什么场景需要限流？
随着互联网的业务发展，比如
秒杀、双十一、618等
这些我们耳熟能详，也有被人恶意攻击的场景下，系统往往经受被高并发流量冲垮的风险，这个时候可以采用
限流
的方式，来保护自身的系统以及下游系统，当然还有其他各种方式手段，比如熔断、降级、隔离等，本文将重点来讲讲
限流
限流
就是就是对请求或并发数进行限制，通过在一定时间内对请求量进行限制，来达到保护系统正常运行的目的。常见的限流算法，有
计数器算法、滑动窗口计数算法、漏桶算法、令牌桶算法
计数器算法
计数器算法，
通过计数器在周期内累加访问次数
，并规定一个周期(
时间窗口
)内的系统处理的请求数量(
阈值
)，当在一个周期内，计数的值达到限流阈值时触发拒绝策略；到下一周期计数器就重置为0，重新开始计数，它是一种
简单
方便的限流算法
比如我们设置系统的
阈值
1s中最多请求100次
，在计数器算法中，我们需要把
时间划分固定大小窗口
(所以计数器算法又叫
固定窗口算法Fixed Window
)，这里我们将
1s
划分为一个时间窗口；然后用计数器来记录在每个时间窗口的处理的请求数量，如果请求数量超过
100次
，后续的请求会被直接拒绝，直到
1s
结束后，重新开始计数
计数器算法优点
实现简单, 占用内存小，性能较高
，但是有一个缺点，就是
临界问题
，因为在一个时间窗口中，请求或者流量并不是均匀分布的，比如，在
1.9s和2.1s
的时间点，分别被人恶意并发请求了
100次
，也就是说从
1.9s
开始后的
1s
时间窗口期间，被瞬间请求了
200次
已经超过系统的阈值了，即使
窗口2和窗口3
还是正常的，这样可能会导致系统直接挂掉
这里提供一个简单的demo(Java版，其他语言大家自行改写):
public class MyFixedWindowRateLimiterDemo {
// 阈值
private static Integer QPS = 2;
// 时间窗口（毫秒）
private static long TIME_WINDOWS = 1000;
// 计数器
private static AtomicInteger counter = new AtomicInteger();
//上一个窗口的开始时间
private static long START_TIME = System.currentTimeMillis();
public synchronized static boolean tryAcquire() {
if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
counter.set(0);
START_TIME = System.currentTimeMillis();
}
return counter.incrementAndGet() <= QPS;
}
public static void main(String[] args) throws InterruptedException {
for (int i = 0; i 10; i++) {
Thread.sleep(250);
LocalTime now = LocalTime.now();
if (!tryAcquire()) {
System.out.println(now + " 请求被限流");
} else {
System.out.println(now + " 请求通过");
}
}
}
}
滑动窗口计数算法
滑动窗口算法
(
Sliding Window
)出现于网络协议中传输层，是一种流量控制技术。我们这里对计数器(固定窗口)算法的临界问题，滑动窗口算法进行了改进，
不再固定窗口大小
，而是将把固定窗口近一步划分成多个小
周期
，每个周期都记录自己的请求访问次数，随着时间流逝，滑动时间窗口(每次向后移动一周期)，同时删除过期的小周期。
每次判断限流时，需要将一个窗口的所有小周期合起来，再与阈值进行比较
举个例子，上图我们将
1s
时间窗口，划分成
5个200ms的小周期
，记录每个周期的请求访问次数，这里沿用上一小节的情形在
1.9s和2.1s
的时间点，分别被人恶意并发请求了
100次
，当滑动到
第5个
小周期时，访问量为
100
次，未达到阈值；而当窗口滑动到
第6个
小周期时，访问数量变为：
200
，这个时候会超过阈值，触发拒绝访问的限制
这样就能限制住瞬时流量爆发。如果滑动窗口的单位区间划分越细的话，滑动窗口的滚动就越平滑，限流统计也会越精准。但随之而来的是实现滑动窗口算法
，需要更多的存储空间
。另外计数器算法实现起来比较简单，滑动窗口则更复杂
这里提供一个笔者感觉非常简单明了的demo，参考于简单的java实现滑动时间窗口限流算法，在此感谢
public class MySlidingWindowRateLimiterDemo {
/** 队列id和队列的映射关系，队列里面存储的是每一次通过时候的时间戳，这样可以使得程序里有多个限流队列 */
private volatile static Map> MAP = new ConcurrentHashMap<>();
//阈值
private static int QPS = 2;
//时间窗口总大小（毫秒）
private static long
WindowSize = 10 * 1000;
/**
* 滑动时间窗口限流算法
* 在指定时间窗口，指定限制次数内，是否允许通过
*
* @param listId 队列id
* @param count 限制次数
* @param timeWindow 时间窗口大小
* @return 是否允许通过
*/
public static synchronized boolean tryAcquire(String listId, int count, long timeWindow) {
// 获取当前时间
long nowTime = System.currentTimeMillis();
// 根据队列id，取出对应的限流队列，若没有则创建
List list = MAP.computeIfAbsent(listId, k -> new LinkedList<>());
// 如果队列还没满，则允许通过，并添加当前时间戳到队列开始位置
if (list.size() list.add(0, nowTime);
return true;
}
// 队列已满（达到限制次数），则获取队列中最早添加的时间戳
Long farTime = list.get(count - 1);
// 用当前时间戳 减去 最早添加的时间戳
if (nowTime - farTime <= timeWindow) {
// 若结果小于等于timeWindow，则说明在timeWindow内，通过的次数大于count
// 不允许通过
return false;
} else {
// 若结果大于timeWindow，则说明在timeWindow内，通过的次数小于等于count
// 允许通过，并删除最早添加的时间戳，将当前时间添加到队列开始位置
list.remove(count - 1);
list.add(0, nowTime);
return true;
}
}
public static void main(String[] args) throws InterruptedException {
for (int i = 0; i 20; i++) {
Thread.sleep(1000);
LocalTime now = LocalTime.now();
if (!tryAcquire("ip", QPS, WindowSize)) {// 任意10秒内，只允许2次通过;自定义限流规则“ip”
System.out.println(now + " 请求被限流");
} else {
System.out.println(now + " 请求通过");
}
}
}
}
美中不足的是，在滑动窗口算法，窗口中流量到达阈值时，流量会瞬间切断，而现实中我们还是更希望，让流量更平滑地放行到系统中，而不是简单粗暴地将其掐断
漏桶算法
我们再来看看
漏桶算法Leaky Bucket
，是一个非常贴切的比喻，意思是，水(就是
请求/流量
)从进水口(
生产端
)进入
桶
(队列)中，这个桶是漏的(比方说桶底有一个孔)，以一定的速度漏水(
消费端不断的在消费队列中的请求
)，当水进入桶的速度过大(大于漏水的速度)，会导致桶里的水堆积，当超过
桶容量
时会溢出来(
请求被拒绝
)。从而实现网络流量整形和限流的功能
这里漏水的速度其实就是限流的
阈值
，所谓的
阈值，表示在一个单位时间内允许的请求量
，比如如QPS为100，说明1秒内系统最多可以消费100个请求。如果
生产端的速率
超过
阈值
的话，请求会慢慢堆积，又因为
漏桶的容量是固定的
，最后会触发拒绝策略(溢出)
漏桶算法它的优点是，实现起来简单，很容易理解。它可以
严格限制
请求的处理速度，一旦超过该速度就拒绝服务，从而避免网络拥塞和系统过载
但它也有缺点：
-
即使没有大流量，也需要等待漏桶处理完成(流量限制过于严格)，这样就会导致请求处理延迟，不适用于实时性要求很高的场景
-
由于它请求的处理速度是固定的，哪怕网络没有发生拥塞时，也不能使某一个单独的数据流达到
生产端的速率
，也无法很好地应对突发特性的流量，不能充分利用系统资源
这里提供一个简单的demo(不完整，生产慎用，仅用来演示):
public class MyLeakyBucketRateLimiterDemo {
// 桶的容量
private final int capacity;
// 漏出速率
private final int rate;
// 剩余水量
private long leftWater;
// 上次注入时间
private long timeStamp = System.currentTimeMillis();
public MyLeakyBucketRateLimiterDemo(int rate, int capacity) {
this.capacity = capacity;
this.rate = rate;
}
public synchronized boolean tryAcquire() {
//1. 计算剩余水量
long now = System.currentTimeMillis();
long timeGap = (now - timeStamp) / 1000;
leftWater = Math.max(0, leftWater - timeGap * rate);
timeStamp = now;
// 如果未满，则放行；否则限流
if (leftWater leftWater += 1;
return true;
}
return false;
}
public static void main(String[] args) throws InterruptedException {
MyLeakyBucketRateLimiterDemo limiterDemo = new MyLeakyBucketRateLimiterDemo(2,5);
for (int i = 0; i 10; i++) {
Thread.sleep(500);
LocalTime now = LocalTime.now();
if (!limiterDemo.tryAcquire()) {
System.out.println(now + " 请求被限流");
} else {
System.out.println(now + " 请求通过");
}
}
}
}
令牌桶算法
令牌桶算法是漏桶算法的改进版，是网络流量整形(
Traffic Shaping
)和限流(
Rate Limiting
)中最常使用的一种算法，它也有一个桶，现在用来存放固定数量的令牌(
token
)，该算法会以一定的速率(
阈值
)往桶中发放令牌。每次请求都需要先获取到桶中的一个令牌才能继续执行，请求处理完毕之后将这个令牌丢弃，否则
执行拒绝策略
(一般有直接拒绝、排队等待 等)；另外放令牌的动作是持续不断进行的，如果桶装满了，则丢弃令牌
表面上看，令牌桶算法和漏桶算法是相反的，一个"进水"，一个是"漏水"。但与漏桶算法实际不同的是，令牌桶
不仅能够在限制客户端请求流量速率
的同时
还能允许一定程度的突发流量
。
限流和允许瞬时流量
其实并不矛盾，在大多数场景中，小批量的突发流量系统是完全可以接受的
