并发数限流

并发数限流限制的是同一时刻的并发数，所以不考虑线程安全的话，我们只要用一个int变量就能实现，伪代码如下：

int maxRequest=100;

int nowRequest=0;

public void request(){

if(nowRequest>=maxRequest){ return ;}nowRequest++;//调用接口try{ invokeXXX(); }finally{ nowRequest--;}}显然，上述实现会有线程安全的问题，最直接的做法是加锁：

int maxRequest=100;

int nowRequest=0;

public void request(){

if(nowRequest>=maxRequest){ return ;}synchronized(this){ if(nowRequest>=maxRequest){ return ;}nowRequest++;}

//调用接口try{     invokeXXX();    }finally{    synchronized(this){        nowRequest--;    }}

}

当然也可以用AtomicInteger实现：

int maxRequest=100;

AtomicInteger nowRequest=new AtomicInteger(0);

public void request(){

for(;;){ int currentReq=nowRequest.get();if(currentReq>=maxRequest){ return;}if(nowRequest.compareAndSet(currentReq,currentReq+1)){ break;}}

//调用接口try{     invokeXXX();    }finally{    nowRequest.decrementAndGet();}

}

熟悉JDK并发包的同学会说干嘛这么麻烦，这不就是信号量（Semaphore）做的事情吗？ 对的，其实最简单的方法就是用信号量来实现：

int maxRequest=100;

Semaphore reqSemaphore = new Semaphore(maxRequest);

public void request(){

if(!reqSemaphore.tryAcquire()){ return ;}

//调用接口try{     invokeXXX();    }finally{   reqSemaphore.release();}

}

条条大路通罗马，并发数限流比较简单，一般来说用信号量就好。

QPS限流

QPS限流限制的是一段时间内（一般指1秒）的请求个数。

计数器法

最简单的做法用一个int型的count变量做计数器：请求前计数器+1，如超过阈值并且与第一个请求的间隔还在1s内，则限流。

伪代码如下：

int maxQps=100;

int count;long timeStamp=System.currentTimeMillis();long interval=1000;

public synchronized boolean grant(){

long now=System.currentTimeMillis();if(now<timeStamp+interval){ count++;return count<maxQps;}else{ timeStamp=now;count=1;return true;}}该种方法实现起来很简单，但其实是有临界问题的，假如在第一秒的后500ms来了100个请求，第2秒的前500ms来了100个请求，那在这1秒内其实最大QPS为200。如下图：

计数器法会有临界问题，主要还是统计的精度太低，这点可以通过滑动窗口算法解决

滑动窗口

我们用一个长度为10的数组表示1秒内的QPS请求，数组每个元素对应了相应100ms内的请求数。用一个 sum 变量代码当前1s的请求数。同时每隔100ms将淘汰过期的值。

伪代码如下：

int maxQps=100;

AtomicInteger[] count=new AtomicInteger[10];long timeStamp=System.currentTimeMillis();long interval=1000;AtomicInteger sum;volatile int index;

public void init(){

for(int i=0;i<count.length;i++){ count[i]=new AtomicInteger(0);}sum=new AtomicInteger(0);}

public synchronized boolean grant(){

count[index].incrementAndGet();return sum.incrementAndGet()<maxQps;}

//每100ms执行一次

public void run(){ index=(index+1)%count.length;int val=count[index].getAndSet(0);sum.addAndGet(-val);}滑动窗口的窗口越小，则精度越高，相应的资源消耗也更高。

漏桶算法

漏桶算法思路是，有一个固定大小的桶，水（请求）忽快忽慢的进入到漏桶里，漏桶以一定的速度出水。当桶满了之后会发生溢出。

在 维基百科 上可以看到，漏桶算法有两种实现，一种是 as a meter ，另一种是 as a queue 。 网上大多数文章都没有提到其有两种实现，且对这两种概念混乱。

As a meter

第一种实现是和令牌桶等价的，只是表述角度不同。

伪代码如下：

long timeStamp=System.currentTimeMillis();//上一次调用grant的时间

int bucketSize=100;//桶大小int rate=10;//每ms流出多少请求int count;//目前的水量

public synchronized boolean grant(){

long now = System.currentTimeMillis();if(now>timeStamp){ count = Math.max(0,count-(now-timeStamp)*rate); timeStamp = now;}

if(count+1<=bucketSize){    count++;    return true;}else{    return false;}

}

该种实现允许一段时间内的突发流量，比如初始时桶中没有水，这时1ms内来了100个请求，这100个请求是不会被限流的，但之后每ms最多只能接受10个请求（比如下1ms又来了100个请求，那其中90个请求是会被限流的）。

其达到的效果和令牌桶一样。

As a queue第二种实现是用一个队列实现，当请求到来时如果队列没满则加入到队列中，否则拒绝掉新的请求。同时会以恒定的速率从队列中取出请求执行。

伪代码如下：

Queue<Request> queue=new LinkedBlockingQueue(100);

int gap;int rate;

public synchronized boolean grant(Request req){

if(!queue.offer(req)){return false;}}

// 单独线程执行

void consume(){ while(true){ for(int i=0;i<rate;i++){ //执行请求Request req=queue.poll();if(req==null){break;}req.doRequest();}Thread.sleep(gap);}}对于该种算法，固定的限定了请求的速度，不允许流量突发的情况。

比如初始时桶是空的，这时1ms内来了100个请求，那只有前10个会被接受，其他的会被拒绝掉。注意与上文中 as a meter 实现的区别。

不过，当桶的大小等于每个ticket流出的水大小时，第二种漏桶算法和第一种漏桶算法是等价的。也就是说, as a queue 是 as a meter 的一种特殊实现。如果你没有理解这句话，你可以再看看上面 as a meter 的伪代码，当 bucketSize==rate 时，请求速度就是恒定的，不允许突发流量。

令牌桶算法

令牌桶算法的思想就是，桶中最多有N个令牌，会以一定速率往桶中加令牌，每个请求都需要从令牌桶中取出相应的令牌才能放行，如果桶中没有令牌则被限流。

令牌桶算法与上文的漏桶算法 as a meter 实现是等价的，能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。伪代码：

int token;

int bucketSize;int rate;long timeStamp=System.currentTimeMillis();

public synchronized boolean grant(){

long now=System.currentTimeMillis();if(now>timeStamp){ token=Math.max(bucketSize,token+(timeStamp-now)*rate);timeStamp=now;}if(token>0){ token--;return true;}else{ return false;}

}

漏桶算法两种实现和令牌桶算法的对比as a meter 的漏桶算法和令牌桶算法是一样的，只是思想角度有所不同。

as a queue 的漏桶算法能强行限制数据的传输速率，而令牌桶和 as a meter 漏桶则 能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。

一般业界用的比较多的是令牌桶算法，像guava中的 RateLimiter 就是基于令牌桶算法实现的。当然不同的业务场景会有不同的需要，具体的选择还是要结合场景。

End

本文介绍了后端系统中常用的限流算法，对于每种算法都有对应的伪代码，结合伪代码理解起来应该不难。