限流算法很多,常见的有三类,分别是计数器算法、漏桶算法、令牌桶算法。
- 计数器： 在一段时间间隔内（时间窗/时间区间），处理请求的最大数量固定，超过部分不做处理。
- 漏桶： 漏桶大小固定，处理速度固定，但请求进入速度不固定（在突发情况请求过多时，会丢弃过多的请求）。
- 令牌桶： 令牌桶的大小固定，令牌的产生速度固定，但是消耗令牌（即请求）速度不固定（可以应对一些某些时间请求过多的情况）；每个请求都会从令牌桶中取出令牌，如果没有令牌则丢弃该次请求。
1. 计数器算法
在一段时间间隔内（时间窗/时间区间），处理请求的最大数量固定，超过部分不做处理。
简单粗暴,比如指定线程池大小，指定数据库连接池大小、nginx连接数等,这都属于计数器算法。
计数器算法是限流算法里最简单也是最容易实现的一种算法。
举个例子,比如我们规定对于A接口，我们1分钟的访问次数不能超过100个。
那么我们可以这么做：
-
在一开 始的时候，我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个请求的间隔时间还在1分钟之内，那么说明请求数过多，拒绝访问。
-
如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置 counter，就是这么简单粗暴。
计算器限流的实现
import java.util.concurrent.atomic.AtomicLong;
// 计速器 限速
public class CounterLimiter {
private static final Object lockObj = new Object();
// 起始时间
private static long startTime = System.currentTimeMillis();
// 时间区间的时间间隔 ms
private final static long interval = 1000;
// 每秒限制数量
private final static long maxCount = 2;
//累加器
private final static AtomicLong accumulator = new AtomicLong();
// 计数判断, 是否超出限制
private static boolean tryAcquire() {
long nowTime = System.currentTimeMillis();
//在时间区间之内
if (nowTime < startTime + interval) {
long count = accumulator.incrementAndGet();
return count <= maxCount;
} else {
//在时间区间之外
synchronized (lockObj) {
// 再一次判断，防止重复初始化
if (nowTime > startTime + interval) {
accumulator.set(0);
startTime = nowTime;
}
}
return true;
}
}
}
计数器限流的严重问题
这个算法虽然简单，但是有一个十分致命的问题，那就是临界问题:
从上图中我们可以看到，假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在 1秒里面，瞬间发送了200个请求。
我们刚才规定的是1分钟最多100个请求（规划的吞吐量），也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求， 可以瞬间超过我们的速率限制。
用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。
2.漏桶算法
漏桶算法限流的基本原理为：水（对应请求）从进水口进入到漏桶里，漏桶以一定的速度出水（请求放行），当水流入速度过大，桶内的总水量大于桶容量会直接溢出，请求被拒绝，如图所示。
大致的漏桶限流规则如下：
- 进水口（对应客户端请求）以任意速率流入进入漏桶。
- 漏桶的容量是固定的，出水（放行）速率也是固定的。
- 漏桶容量是不变的，如果处理速度太慢，桶内水量会超出了桶的容量，则后面流入的水滴会溢出，表示请求拒绝。
漏桶算法原理
漏桶算法思路：
水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会超过桶可接纳的容量时直接溢出。
可以看出漏桶算法能强行限制数据的传输速率。
漏桶算法其实很简单，可以粗略的认为就是注水漏水过程，往桶中以任意速率流入水，以一定速率流出水，当水超过桶容量（capacity）则丢弃，因为桶容量是不变的，保证了整体的速率。
削峰: 有大量流量进入时,会发生溢出,从而限流保护服务可用
1.漏桶算法实现
import java.util.concurrent.atomic.AtomicInteger;
// 漏桶 限流
public class LeakBucketLimiter {
// 计算的起始时间
private static long lastOutTime = System.currentTimeMillis();
// 流出速率 每秒 2 次
private final static int leakRate = 2;
// 桶的容量
private final static int capacity = 20;
//剩余的水量
private final static AtomicInteger water = new AtomicInteger(0);
//返回值说明：
// false 没有被限制到
// true 被限流
public static synchronized boolean isLimit() {
// 如果是空桶，就当前时间作为漏出的时间
if (water.get() == 0) {
lastOutTime = System.currentTimeMillis();
water.addAndGet(1);
return false;
}
// 执行漏水 计算 当前时间和上一次漏水时间间隔中应该有多少水应该漏掉
int waterLeaked = ((int)((System.currentTimeMillis() - lastOutTime) / 1000)) * leakRate;
// 计算剩余水量
int waterLeft = water.get() - waterLeaked;
water.set(Math.max(0, waterLeft));
// 重新更新leakTimeStamp
lastOutTime = System.currentTimeMillis();
// 尝试加水,并且水还未满 ，放行
if ((water.get()) < capacity) {
water.addAndGet(1);
return false;
} else {
// 水满，拒绝加水， 限流
return true;
}
}
}
2.漏桶的问题
漏桶的出水速度固定，也就是请求放行速度是固定的，所以不能应对突发流量。
3.令牌桶限流
令牌桶算法以一个设定的速率产生令牌并放入令牌桶，每次用户请求都得申请令牌，如果令牌不足，则拒绝请求。
令牌桶算法中新请求到来时会从桶里拿走一个令牌，如果桶内没有令牌可拿，就拒绝服务。当然，令牌的数量也是有上限的。令牌的数量与时间和发放速率强相关，时间流逝的时间越长，会不断往桶里加入越多的令牌，如果令牌发放的速度比申请速度快，令牌桶会放满令牌，直到令牌占满整个令牌桶，如图所示。
令牌桶限流大致的规则如下：
- 进水口按照某个速度，向桶中放入令牌。
- 令牌的容量是固定的，但是放行的速度不是固定的，只要桶中还有剩余令牌，一旦请求过来就能申请成功，然后放行。
- 如果令牌的发放速度，慢于请求到来速度，桶内就无牌可领，请求就会被拒绝。
总之，令牌的发送速率可以设置，从而可以对突发的出口流量进行有效的应对。
1.令牌桶算法
令牌桶与漏桶相似,不同的是令牌桶桶中放了一些令牌,服务请求到达后,要获取令牌之后才会得到服务,举个例子,我们平时去食堂吃饭,都是在食堂内窗口前排队的,这就好比是漏桶算法,大量的人员聚集在食堂内窗口外,以一定的速度享受服务,如果涌进来的人太多,食堂装不下了,可能就有一部分人站到食堂外了,这就没有享受到食堂的服务,称之为溢出,溢出可以继续请求,也就是继续排队,那么这样有什么问题呢?
如果这时候有特殊情况,比如有些赶时间的志愿者啦、或者高三要高考啦,这种情况就是突发情况,如果也用漏桶算法那也得慢慢排队,这也就没有解决我们的需求,对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。如图所示，令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。
2.令牌桶算法实现
import java.util.concurrent.atomic.AtomicInteger;
// 令牌桶 限速
public class TokenBucketLimiter {
// 上一次令牌发放时间
public long lastTime = System.currentTimeMillis();
// 桶的容量
public int capacity = 20;
// 令牌生成速度 /s
public int rate = 2;
// 当前令牌数量
public AtomicInteger tokens = new AtomicInteger(0);
//返回值说明：
// false 没有被限制到
// true 被限流
public synchronized boolean isLimited(int applyCount) {
long now = System.currentTimeMillis();
//时间间隔,单位为 ms
long gap = now - lastTime;
//计算时间段内的令牌数
int reversePermits = (int) (gap * rate / 1000);
int allPermits = tokens.get() + reversePermits;
// 当前令牌数
tokens.set(Math.min(capacity, allPermits));
if (tokens.get() < applyCount) {
// 若拿不到令牌,则拒绝
return true;
} else {
// 还有令牌，领取令牌
tokens.getAndAdd(-applyCount);
lastTime = now;
return false;
}
}
}
3.令牌桶的好处
令牌桶的好处之一就是可以方便地应对 突发出口流量
可以改变令牌的发放速度，算法能按照新的发送速率调大令牌的发放数量，使得后端扩容时能得到有效处理
令牌桶如果桶内不会积累令牌，就会退化成类似漏洞一样的效果