前言

所有技术都有它要解决的痛点。所以在介绍限流算法和具体场景之前我们要先得明确什么是限流，为什么要限流？然后从最简单的计数法到令牌桶说明几种限流算法的实现。

1、限流是什么

在开发的过程中，由于系统会面临高并发场景，或者也会遭遇一些恶意请求。为了保护我们的系统，保持系统的稳定性，我们要对请求进行限流。总结下来，限流就是：因为资源的稀缺或出于安全防范的目的，采取的自我保护的措施。限流是出于自我保护的目的，所以难以避免对用户体验造成影响。因此限流算法的目的就是在保持系统稳定性的同时，也尽量让用户有更好的体验。

一般来说，系统的吞吐量是有一个阈值的，如果请求量达到了这个阈值，我们就要对流量进行限制。

2、限流算法计数限流

最简单的限流算法，思想很简单，直接计数。设置一个阈值，再设置一个计数器。当请求来的时候计数器加一，判断有没有超过阈值，请求处理过后，计数器减一。

java

复制代码

public class CounterLimiter { private int size; //阈值 private AtomicInteger counter;//当前窗口的计数器 public boolean tryAcquire(){ if(counter.get() < size){ counter.incrementAndGet(); return true; }else{ return false; } } public boolean tryRelease(){ if(counter.get()>0){ counter.decrementAndGet(); return true; }else{ return false; } } }

缺点：

没有考虑时间问题。

固定窗口限流

相对于计数法，考虑了时间问题，引入了时间窗口的概念

在时间窗口内：

请求次数小于阈值，允许访问并且计数器 +1；请求次数大于阈值，拒绝访问；

时间窗口过了之后，计数器清零；重新计数。

java

复制代码

public class CounterLimiter { private int timeWindow; //窗口大小 private int limit; //阈值 private long lastTime=System.currentTimeMillis();//上一次窗口时间 private int counter;//当前窗口的计数器 public boolean tryAcquire(){ long now=System.currentTimeMillis(); if(now-lastTime>timeWindow){ //是否过了时间窗口 counter=0; lastTime=now; } if(counter<limit){ //是否超过阈值 counter++; return true; } return false; } }

缺点

没有考虑临界问题。

若不在时间窗口内的单位时间内请求量过大，固定的窗口没法处理。

滑动窗口限流

解决固定窗口临界值的问题，保证在任意时间窗口内都不会超过阈值。

限流规则：

记录每次请求的时间统计每次请求的时间向前固定一段时间内的请求数统计的请求数小于阈值就记录这个请求的时间，并允许通过，反之拒绝。

java

复制代码

public class CounterLimiter { private int timeWindow; //窗口大小 private int limit; //阈值 private long lastTime=System.currentTimeMillis();//上一次窗口时间 private final TreeMap<Long, Integer> counters = new TreeMap<>();//以时间为起点的计数器 public boolean tryAcquire(){ long now=System.currentTimeMillis(); int counter=getCountTimeWindow(now); if(counter<limit){ //是否超过阈值 counters.get(now)++; return true; } return false; } private int getCountTimeWindow(long currentTime) { //当前时间向前时间窗口内的请求数量 } }

缺点

固定窗口和滑动窗口都无法解决一个问题：

当窗口中流量到达阈值时，流量会瞬间切断

我们所希望的是：

当大量请求同时访问时，请求是均匀访问，而不是一次性的全打过来。

于是便有了漏桶算法限流。

漏桶限流

请求像水滴一样匀速的滴入桶中，服务端匀速的从桶中滴出请求进行处理。超过桶中阈值的请求会被拒绝。

限流规则：

流入水滴代表请求，桶的容量系统所能处理请求数量的阈值。如果桶的容量满了，就达到限流的阀值，就会拒绝请求服务端匀速从桶内滴出请求进行处理

java

复制代码

public class BucketLimiter { private long rate;//滴入速率 private long currentWater;//水桶内的水量 private long lastTime;//上次注水时间 private long capacity;//容量（阈值） public boolean tryAcquire(){ long now=System.currentTimeMillis(); long outWater=(now-lastTime)*rate;//流出的水量 =(当前时间-上次时间)* 滴入速率 long currentWater=Math.max(0,currentWater-outWater);// 当前水量 = 桶内水量-流出的水量 int counter=getCountTimeWindow(now); if (currentWater+1 <= capacity) { lastTime=now;//更新时间 currentWater++; //水量+1 return true; } return false; } }

特点

主要是用来平滑突发的流量，请求访问的速率是不确定的，但是请求处理是匀速的。

缺点：对流量的控制过于严格，不能充分使用系统资源。漏桶算法对请求的处理过于死板，导致可能会浪费系统资源。明明可以更快的处理请求，但是只能匀速的去处理。

令牌桶限流算法

与漏桶算法不同的是：漏桶算法是匀速滴出，令牌桶算法是匀速的向桶内放令牌，由请求去申请令牌，申请到令牌的请求才可以被处理，否则会被拒绝。

限流规则：

匀速向令牌桶内放入令牌若令牌数量超过阈值则抛弃令牌请求来了要向令牌桶申请获取令牌，若成功才可以被处理，否则被拒绝。

java

复制代码

public class BucketLimiter { private long rate;//令牌发放速率 private long capacity;//令牌桶的容量 private long counter;//令牌数量 private long lastAcquireTime;//上次取令牌时间 public boolean tryAcquire(){ long now=System.currentTimeMillis(); long newPermits=(now-lastAcquireTime)*rate; //这段时间放入的令牌数 counter = Math.min(counter+newPermits,capacity);//当前令牌数 if (counter > 0) { //令牌数够用，可以获取 lastAcquireTime=now; counter--; return true; } return false; } }

令牌桶算法特点

不像漏桶那样匀速处理请求，在应对突发流量的时候表现的更佳。

小结

对五种滑动窗口算法做了简单的介绍和分析。从最简单的计数器法，到令牌桶限流算法。当然每种算法都有它存在的意义，不是说令牌桶算法最好我们就只用它。简单的对各种限流算法做个小结。

固定窗口实现简单。和漏斗算法相比，新来的请求也能够被马上处理到。但是流量曲线可能不够平滑。滑动窗口算法作为固定窗口算法的一种改进，有效解决了窗口临界值的问题。漏桶算法实现了对请求的匀速处理，让随机不稳定的流量以固定的速率流出。令牌桶算法改进了漏桶算法对资源的浪费，同时可以用来解决流量突发的问题。