1.为什么要限流
- 系统上游流量未知，如果超载引起雪崩。
- 系统下游吞吐能力一般，直连带宽有限。
2.常见的几种限流算法
1. 计数器限流
在一段时间间隔内，对请求进行计数，与阀值进行比较判断是否需要限流，一旦到了时间临界点，将计数器清零
优点：简单
缺点：很难处理单位时间内的临界问题
demo代码示例：
public class CountLimiter implements Limiter {
//时间窗口
private long timeStamp= System.currentTimeMillis();
//请求次数
private int reqCount;
//时间间隔
private long interval=1000;
//限流次数
private long limitNum=100;
/**
* （单机限流，分布式限流用 redis）
* 返回 true 代表限流， false 代表通过
* @return
*/
@Override
public synchronized Boolean limit(){
long now = System.currentTimeMillis();
//判断当前时
if(now<timeStamp+interval){
//判断档期窗口内请求次数是否超过每秒限流的最大请求次数
if(reqCount+1>limitNum){
//限流了
return true;
}
reqCount++;
return false;
}else {
//开启新的时间窗口
timeStamp=now;
//重置计数器
reqCount=1;
return false;
}
}
}
|
2. 滑动窗口
把固定时间片进行划分，并且随着时间的流逝，进行移动，固定数量的可以移动的格子，进行计数并判断阀值
优点：将固定时间段分块，时间比“计数器”复杂，适用于稍微精准的场景
缺点：格子的数量影响着滑动窗口算法的精度，依然有时间片的概念，无法根本解决临界点问题
demo代码示例
package com.example.limit;
import java.util.LinkedList;
public class SlideTimeWindowLimiter implements Limiter {
private int reqCount;
//记录滑动的窗口的10个格子
private LinkedList<Integer> slots = new LinkedList<>();
//每秒限流的最大请求次数
private int limitNum = 100;
//滑动时间窗口里的每个格子的时间长度，单位 ms
private long windowLength = 100L;
//滑动时间窗口里的格子数量
private int windowNum = 10;
@Override
public synchronized Boolean limit() {
if ((reqCount + 1) > limitNum) {
return true;
}
slots.set(slots.size() - 1, slots.peekLast() + 1);
reqCount++;
return false;
}
//滑动窗口实现
public SlideTimeWindowLimiter(){
slots.addLast(0);
new Thread(()->{
while (true){
try {
Thread.sleep(windowLength);
}catch (InterruptedException e){
e.printStackTrace();
}
synchronized (this){
slots.addLast(0);
if(slots.size()>windowNum){
//滑动窗口，删除第一个格子，
reqCount=reqCount-slots.peekFirst();
slots.removeFirst();
}
}
}
}).start();
}
}
|
3. 漏桶算法
一个固定容量的漏桶，按照固定速率流出水滴
特点：
1.以任意速率往桶中放入水滴。
2.以固定速率从桶中流出水滴。
3.如果流入水滴超出了桶的容量，则流入的水滴溢出（新请求被拒绝）
优点：可以很好的控制消费频率
缺点：限制的是常量流出速率（即流出速率是一个固定常量值），所以最大的速率就是出水的速率，不能出现突发流量
demo代码示例
package com.example.limit;
public class LeakyBucketLimiter implements Limiter {
private long timeStamp=System.currentTimeMillis();
private long capacity=100;//桶的容量
private long rate=10; //水漏出的速度（每秒系统能处理的请求数）
private long water=20; //当前水量（当前累计的请求数）
@Override
public synchronized Boolean limit() {
long now = System.currentTimeMillis();
water = Math.max(0, water - ((now - timeStamp) / 1000) * rate);
timeStamp = now;
if ((water + 1) <= capacity) {
//加水
water++;
return false;
} else {
//水满拒绝加水；
return true;
}
}
}
|
4. 令牌桶算法
一个固定的桶，桶里存放着令牌（token）。一开始桶是空的，系统按固定的时间（rate）往桶里添加令牌，直到桶里的令牌数满，多余的请求会被丢弃。当请求来的时候，从桶里移除一个令牌，如果桶是空的则拒绝请求或者阻塞。
特点：
1. 流入桶的速率一定
2.请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务
3.能够应对突发流量
demo代码示例
package com.example.limit;
public class TokenBucketLimiter implements Limiter {
private long timeStamp=System.currentTimeMillis();
private long capacity=100;//桶的容量
private long rate=10; // 令牌放入速度
private long tokens=20; // 当前令牌数量
@Override
public Boolean limit() {
long now = System.currentTimeMillis();
//添加令牌
tokens = Math.min(capacity, tokens + (now - timeStamp) / 1000 * rate);
timeStamp = now;
if (tokens < 1) {
return true;
} else {
//还有令牌，领取令牌
tokens--;
return false;
}
}
}
|