四种限流算法
为什么要限流
限流是为了防止系统突然收到大量请求，后台面对大量并发请求对cpu和内存，网络io产生巨大压力，可能将一些服务如mysql，redis等打崩，引发系统故障，服务瘫痪。
固定窗口：Fixed Window Rate Limiting Algorithm
将时间分为固定窗口，将请求按时间顺序放入时间窗口，如果超过设置时间窗口的阈值就返回限流结果，但是在两个时间窗口替换间隙可能会有2n请求并发。
优点：实现简单，便于理解
缺点：存在明显的临界问题，切换间隙可产生产生2n请求：0.75秒-1.0秒产生n个请求，刷新，1.0-1.5s又产生n个请求，这n个请求各自窗口满足要求，但是再它门组成的窗口中并发量达到了2n
public class FixedWindow {
//窗口大小
private final static Integer timeUnit=1000;
//请求计数
private AtomicInteger count=new AtomicInteger();
private Long lastTime=0L;
private Integer threshold=10;
public boolean fixedWindow()
{
long currentTime=System.currentTimeMillis();
if(currentTime-lastTime>timeUnit)
{
count.set(0);
lastTime=currentTime;
}
if(count.get()>=threshold) //初始计数是0 ，所以是大于等于刚好执行十次
{
return false;
}
count.getAndIncrement();
return true;
}
public static void main(String[] args) {
FixedWindow fixedWindow=new FixedWindow();
for(int i=0;i<20;i++)
{
System.out.println(fixedWindow.fixedWindow());
}
}
}
滑动窗口：Sliding Windows Algorithm
将单位时间周期又划分成n个小周期，分别根据每个小周期内接口的访问次数，并根据时间滑动自动删除过期的小周期（tcp就是根据这个来实现对发送字节的大小控制）
优点： 简单易懂，精度高可以调整时间粒度来调节限流效果，可拓展性，可与和其他限流算法结合使用
缺点：无法应对突发请求，突发请求会被大量拒绝，会损失大量请求
public class SlidingWindow {
private final int maxRequests; // 最大请求数
private final long timeWindowMillis; // 时间窗口（毫秒）
private final Queue<Long> requests; // 请求队列
public SlidingWindow(int maxRequests, long timeWindowMillis) {
this.maxRequests = maxRequests;
this.timeWindowMillis = timeWindowMillis;
this.requests = new LinkedList<>();
}
public synchronized boolean tryAcquire() {
// 移除超出时间窗口的请求
while (!requests.isEmpty() && System.currentTimeMillis() - requests.peek() > timeWindowMillis) {
requests.poll();
}
// 判断当前窗口内的请求数量是否超过最大请求数
if (requests.size() < maxRequests) {
// 添加新请求到队列
requests.offer(System.currentTimeMillis());
return true;
} else {
return false;
}
}
public static void main(String[] args) throws InterruptedException {
SlidingWindow rateLimiter = new SlidingWindow(5, 1000); // 每秒最多5个请求
for (int i = 0; i < 20; i++) {
System.out.println("Request " + (i + 1) + ": " + (rateLimiter.tryAcquire() ? "Accepted" : "Rejected"));
}
}
}
漏桶算法：Leaky Bucket Algorithm
控制流入网络的速率速度，以防止网络堵塞。核心思想就是将请求比作小水滴，漏桶看作固定容量的水桶，数据包从顶部进入漏桶，漏桶底部以匀速形式流出数据包。水满则溢，拒绝请求。
优点：可以十分平滑的处理请求，对瞬间增加的请求有一定的承载能力
缺点：需要对请求进行缓存，会增加服务器的内存消耗。面对突发流量无法进行快速处理请求。
public class LeakyBucket {
private int capacity = 10;
private int rate = 1; //每ms多少个
private int total = 0;
private long lastTime = System.currentTimeMillis();
private synchronized boolean leakBucket(Integer water) throws InterruptedException {
long time=System.currentTimeMillis();
long escapeTime=time-lastTime;
long leakWater=escapeTime*rate;
if(leakWater>0)
{
total=(int) Math.max(0,total-leakWater);
lastTime=time;
}
if(total+water>capacity)
{
Thread.sleep(4);
return false;
}
total=total+water;
return true;
}
public static void main(String[] args) throws InterruptedException {
LeakyBucket leakyBucket=new LeakyBucket();
for (int i = 0; i < 20; i++) {
System.out.println(leakyBucket.leakBucket(2));
}
}
}
令牌桶算法：Token Bucket Algorithm
系统以一定的速率向令牌桶中添加令牌，请求到来时先去尝试获取令牌，拿到令牌就正常请求并消耗这个令牌，拿不到就拒绝服务。
优点：可以应对突发流量，具有弹性处理请求的特点，稳定性好。精度高：可以根据请求动态调节生成令牌桶的速率
缺点：实现复杂，时间精度控制要求比较高
public class TokenBucket {
private long capacity = 5;//令牌总数
private long lastTime=System.currentTimeMillis();
private long rate=5;//每毫秒发放令牌
private long total=capacity;
private synchronized boolean tokenBucket() throws InterruptedException {
long now=System.currentTimeMillis();
long gap=now-lastTime;
long add=gap*rate;
if(total<20)
{
total=Math.min(total+add,capacity);
lastTime=now;
}
if(total-1<0)
{
Thread.sleep(1);
return false;
}
total--;
return true;
}
public static void main(String[] args) throws InterruptedException {
TokenBucket tokenBucket=new TokenBucket();
for (int i = 0; i < 20; i++) {
System.out.println(tokenBucket.tokenBucket());
}
}
}
