后端服务的接口都是有访问上限的，如果外部QPS或并发量超过了访问上限会导致应用瘫痪。所以一般都会对接口调用加上限流保护，防止超出预期的请求导致系统故障。
从限流类型来说一般来说分为两种:并发数限流和qps限流，并发数限流就是限制同一时刻的最大并发请求数量，qps限流指的是限制一段时间内发生的请求个数。
从作用范围的层次上来看分单机限流和分布式限流，前者是针对单机的，后者是针对集群的，他们的思想都是一样的，只不过是范围不一样，本文分析的都是单机限流。
接下来我们看看并发数限流和QPS限流。
更多文章见个人博客：https://github.com/farmerjohngit/myblog
并发数限流
并发数限流限制的是同一时刻的并发数，所以不考虑线程安全的话，我们只要用一个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
本文介绍了后端系统中常用的限流算法，对于每种算法都有对应的伪代码，结合伪代码理解起来应该不难。但伪代码中只是描述了大致思想，对于一些细节和效率问题并没有关注，所以下篇文章将会分析常用限流API：guava的RateLimiter的源码实现，让读者对于限流有个更清晰的认识。
参考文章
http://blog.zhuxingsheng.com/blog/counter-algorithm.html
