前言
咱们好,我是田螺.
最近一位朋友去拼夕夕面试,被问了这么一道题:限流算法有哪些?用代码完成令牌桶算法。跟星球老友讨论了一波,发现咱们都忘记得差不多了.所以田螺哥再收拾一波，常见的四种限流算法,以及简略代码完成,相信咱们看完,会恍然大悟的。
- 大众号：捡田螺的小男孩 （有田螺精心准备的面试PDF）
- github地址，感谢每颗star：github
1. 固定窗口限流算法
1.1 什么是固定窗口限流算法
固定窗口限流算法（
Fixed Window Rate Limiting Algorithm）是一种最简略的限流算法，其原理是在固定时刻窗口(单位时刻)内约束恳求的数量。该算法将时刻分红固定的窗口，并在每个窗口内约束恳求的数量。具体来说，算法将恳求依照时刻顺序放入时刻窗口中，并核算该时刻窗口内的恳求数量，假如恳求数量超出了约束，则回绝该恳求。
假定单位时刻(固定时刻窗口)是1秒，限流阀值为3。在单位时刻1秒内，每来一个恳求,计数器就加1，假如计数器累加的次数超越限流阀值3，后续的恳求全部回绝。等到1s结束后，计数器清0，重新开端计数。如下图：
1.2 固定窗口限流的伪代码完成
public static Integer counter = 0; //核算恳求数
public static long lastAcquireTime = 0L;
public static final Long windowUnit = 1000L ; //假定固定时刻窗口是1000ms
public static final Integer threshold = 10; // 窗口阀值是10
/**
* 固定窗口时刻算法
* 关注大众号：捡田螺的小男孩
* @return
*/
public synchronized boolean fixedWindowsTryAcquire() {
long currentTime = System.currentTimeMillis(); //获取体系当时时刻
if (currentTime - lastAcquireTime > windowUnit) { //查看是否在时刻窗口内
counter = 0; // 计数器清0
lastAcquireTime = currentTime; //敞开新的时刻窗口
}
if (counter < threshold) { // 小于阀值
counter++; //计数核算器加1
return true;
}
return false;
}
1.2 固定窗口算法的优缺陷
- 长处：固定窗口算法十分简略，易于完成和理解。
-
缺陷：存在显着的临界问题，比方: 假定限流阀值为
5个恳求，单位时刻窗口是1s,假如咱们在单位时刻内的前0.8-1s和1-1.2s，分别并发5个恳求。虽然都没有超越阀值，可是假如算0.8-1.2s,则并发数高达10，现已超越单位时刻1s不超越5阀值的定义啦。
2. 滑动窗口限流算法
2.1 什么是滑动窗口限流算法
滑动窗口限流算法是一种常用的限流算法，用于操控体系对外供给服务的速率，防止体系被过多的恳求压垮。它将单位时刻周期分为
n个小周期，分别记录每个小周期内接口的拜访次数，并且依据时刻滑动删去过期的小周期。它能够解决固定窗口临界值的问题。
用一张图解释滑动窗口算法，如下：
假定单位时刻还是1s，滑动窗口算法把它区分为5个小周期，也便是滑动窗口（单位时刻）被区分为5个小格子。每格表明0.2s。每过0.2s，时刻窗口就会往右滑动一格。然后呢，每个小周期，都有自己独立的计数器，假如恳求是0.83s抵达的，0.8~1.0s对应的计数器就会加1。
咱们来看下，滑动窗口,去解决固定窗口限流算法的临界问题，思维是怎样
假定咱们
1s内的限流阀值还是5个恳求，0.8~1.0s内（比方0.9s的时分）来了5个恳求，落在黄色格子里。时刻过了1.0s这个点之后，又来5个恳求，落在紫色格子里。假如是固定窗口算法，是不会被限流的，可是滑动窗口的话，每过一个小周期，它会右移一个小格。过了1.0s这个点后，会右移一小格，当时的单位时刻段是0.2~1.2s，这个区域的恳求现已超越限定的5了，已触发限流啦，实际上，紫色格子的恳求都被回绝啦。
当滑动窗口的格子周期区分的越多，那么滑动窗口的翻滚就越滑润，限流的核算就会越精确。
2.2 滑动窗口限流算法的伪代码完成
/**
* 单位时刻区分的小周期（单位时刻是1分钟，10s一个小格子窗口，总共6个格子）
*/
private int SUB_CYCLE = 10;
/**
* 每分钟限流恳求数
*/
private int thresholdPerMin = 100;
/**
* 计数器, k-为当时窗口的开端时刻值秒，value为当时窗口的计数
*/
private final TreeMap<Long, Integer> counters = new TreeMap<>();
/**
* 滑动窗口时刻算法完成
*/
public synchronized boolean slidingWindowsTryAcquire() {
long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //获取当时时刻在哪个小周期窗口
int currentWindowNum = countCurrentWindow(currentWindowTime); //当时窗口总恳求数
//超越阀值限流
if (currentWindowNum >= thresholdPerMin) {
return false;
}
//计数器+1
counters.get(currentWindowTime)++;
return true;
}
/**
* 核算当时窗口的恳求数
*/
private synchronized int countCurrentWindow(long currentWindowTime) {
//核算窗口开端方位
long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1);
int count = 0;
//遍历存储的计数器
Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Long, Integer> entry = iterator.next();
// 删去无效过期的子窗口计数器
if (entry.getKey() < startTime) {
iterator.remove();
} else {
//累加当时窗口的一切计数器之和
count =count + entry.getValue();
}
}
return count;
}
2.3 滑动窗口限流算法的优缺陷
长处：
- 简略易懂
- 精度高（经过调整时刻窗口的巨细来完成不同的限流作用）
- 可扩展性强（能够十分容易地与其他限流算法结合运用）
缺陷：
- 突发流量无法处理（无法应对短时刻内的很多恳求，可是一旦抵达限流后，恳求都会直接暴力被回绝。酱紫咱们会损失一部分恳求，这其实关于产品来说，并不太友爱），需求合理调整时刻窗口巨细。
3. 漏桶限流算法
3.1 什么是漏桶限流算法
漏桶限流算法（Leaky Bucket Algorithm）是一种流量操控算法，用于操控流入网络的数据速率，以防止网络拥塞。它的思维是将数据包看作是水滴，漏桶看作是一个固定容量的水桶，数据包像水滴一样从桶的顶部流入桶中，并经过桶底的一个小孔以必定的速度流出，然后约束了数据包的流量。
漏桶限流算法的基本工作原理是：关于每个到来的数据包，都将其加入到漏桶中，并查看漏桶中当时的水量是否超越了漏桶的容量。假如超越了容量，就将多余的数据包丢弃。假如漏桶中还有水，就以必定的速率从桶底输出数据包，保证输出的速率不超越预设的速率，然后到达限流的意图。
- 流入的水滴，能够看作是拜访体系的恳求，这个流入速率是不确定的。
- 桶的容量一般表明体系所能处理的恳求数。
- 假如桶的容量满了，就到达限流的阀值，就会丢弃水滴（回绝恳求）
- 流出的水滴，是恒定过滤的，对应服务依照固定的速率处理恳求。
3.2 漏桶限流算法的伪代码完成
/**
* LeakyBucket 类表明一个漏桶,
* 包含了桶的容量和漏桶出水速率等参数，
* 以及当时桶中的水量和前次漏水时刻戳等状况。
*/
public class LeakyBucket {
private final long capacity; // 桶的容量
private final long rate; // 漏桶出水速率
private long water; // 当时桶中的水量
private long lastLeakTimestamp; // 前次漏水时刻戳
public LeakyBucket(long capacity, long rate) {
this.capacity = capacity;
this.rate = rate;
this.water = 0;
this.lastLeakTimestamp = System.currentTimeMillis();
}
/**
* tryConsume() 办法用于测验向桶中放入必定量的水，假如桶中还有满足的空间，则回来 true，否则回来 false。
* @param waterRequested
* @return
*/
public synchronized boolean tryConsume(long waterRequested) {
leak();
if (water + waterRequested <= capacity) {
water += waterRequested;
return true;
} else {
return false;
}
}
/**
* 。leak() 办法用于漏水，依据当时时刻和前次漏水时刻戳核算出应该漏出的水量，然后更新桶中的水量和漏水时刻戳等状况。
*/
private void leak() {
long now = System.currentTimeMillis();
long elapsedTime = now - lastLeakTimestamp;
long leakedWater = elapsedTime * rate / 1000;
if (leakedWater > 0) {
water = Math.max(0, water - leakedWater);
lastLeakTimestamp = now;
}
}
}
3.3 漏桶限流算法的优缺陷
长处
- 能够滑润约束恳求的处理速度，防止瞬间恳求过多导致体系崩溃或许雪崩。
- 能够操控恳求的处理速度，使得体系能够习惯不同的流量需求，防止过载或许过度闲置。
- 能够经过调整桶的巨细和漏出速率来满足不同的限流需求，能够灵活地习惯不同的场景。
缺陷
- 需求对恳求进行缓存，会增加服务器的内存耗费。
- 关于流量波动比较大的场景，需求较为灵活的参数配置才干到达较好的作用。
- 可是面临突发流量的时分，漏桶算法还是循规蹈矩地处理恳求，这不是咱们想看到的啦。流质变突发时，咱们必定期望体系尽量快点处理恳求，提高用户体会嘛。
4. 令牌桶算法
4.1 什么是令牌桶算法
令牌桶算法是一种常用的限流算法，能够用于约束单位时刻内恳求的数量。该算法维护一个固定容量的令牌桶，每秒钟会向令牌桶中放入必定数量的令牌。当有恳求到来时，假如令牌桶中有满足的令牌，则恳求被答应经过并从令牌桶中耗费一个令牌，否则恳求被回绝。
4.2 令牌桶算法的伪代码完成
/**
* TokenBucket 类表明一个令牌桶
*/
public class TokenBucket {
private final int capacity; // 令牌桶容量
private final int rate; // 令牌生成速率，单位：令牌/秒
private int tokens; // 当时令牌数量
private long lastRefillTimestamp; // 前次令牌生成时刻戳
/**
* 结构函数中传入令牌桶的容量和令牌生成速率。
* @param capacity
* @param rate
*/
public TokenBucket(int capacity, int rate) {
this.capacity = capacity;
this.rate = rate;
this.tokens = capacity;
this.lastRefillTimestamp = System.currentTimeMillis();
}
/**
* allowRequest() 办法表明一个恳求是否答应经过，该办法运用 synchronized 关键字进行同步，以保证线程安全。
* @return
*/
public synchronized boolean allowRequest() {
refill();
if (tokens > 0) {
tokens--;
return true;
} else {
return false;
}
}
/**
* refill() 办法用于生成令牌，其间核算令牌数量的逻辑是依照令牌生成速率每秒钟生成必定数量的令牌，
* tokens 变量表明当时令牌数量，
* lastRefillTimestamp 变量表明前次令牌生成的时刻戳。
*/
private void refill() {
long now = System.currentTimeMillis();
if (now > lastRefillTimestamp) {
int generatedTokens = (int) ((now - lastRefillTimestamp) / 1000 * rate);
tokens = Math.min(tokens + generatedTokens, capacity);
lastRefillTimestamp = now;
}
}
}
4.3 令牌桶算法的优缺陷
长处：
- 稳定性高：令牌桶算法能够操控恳求的处理速度，能够使体系的负载变得稳定。
- 精度高：令牌桶算法能够依据实际情况动态调整生成令牌的速率，能够完成较高精度的限流。
- 弹性好：令牌桶算法能够处理突发流量，能够在短时刻内供给更多的处理能力，以处理突发流量。
Guava的RateLimiter限流组件，便是根据令牌桶算法完成的。
缺陷：
- 完成杂乱：相关于固定窗口算法等其他限流算法，令牌桶算法的完成较为杂乱。 对短时恳求难以处理：在短时刻内有很多恳求到来时，可能会导致令牌桶中的令牌被快速耗费完，然后限流。这种情况下，能够考虑运用漏桶算法。
- 时刻精度要求高：令牌桶算法需求在固定的时刻距离内生成令牌，因此要求时刻精度较高，假如体系时刻不准确，可能会导致限流作用不理想。
总体来说，令牌桶算法具有较高的稳定性和精度，但完成相对杂乱，适用于对稳定性和精度要求较高的场景。
