高并发系统的限流方案研究，其实限流实现也不复杂

目录

概要

相关概念

限流的算法

计数器算法

漏桶算法(Leaky Bucket)

令牌桶算法(Token Bucket)

---

概要

在高并发系统中可以通过至少三种技术来保护系统：缓存、降级、限流。这里主要介绍限流算法。

随着网站用户规模的增加，业务的扩张，我们网站所承受的流量规模和并发数也会不断增加。到了一定阶段我们就会希望可以对网站的流量进行一定程度的控制。因为我们的业务处理能力是有限的，我们需要优先保证关键业务的正常运转。技术人员一直以来都在致力于可以彻底的解决高并发问题，但是到目前为止也没有一种可以彻底解决的方案。我们只能尽量的提升业务处理的性能，做业务拆分，分布式，进行错峰处理等手段。其实我们可以从一整个用户请求的过程中的每个阶段进行分析，在不同的阶段采用不同的方案。

缓存

缓存比较好理解，在大型高并发系统中，如果没有缓存数据库将分分钟被爆，系统也会瞬间瘫痪。使用缓存不单单能够提升系统访问速度、提高并发访问量，也是保护数据库、保护系统的有效方式。大型网站一般主要是“读”，缓存的使用很容易被想到。在大型“写”系统中，缓存也常常扮演者非常重要的角色。比如累积一些数据批量写入，内存里面的缓存队列（生产消费），以及HBase写数据的机制等等也都是通过缓存提升系统的吞吐量或者实现系统的保护措施。甚至消息中间件，你也可以认为是一种分布式的数据缓存。

降级

服务降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略的降级，以此释放服务器资源以保证核心任务的正常运行。降级往往会指定不同的级别，面临不同的异常等级执行不同的处理。根据服务方式：可以拒接服务，可以延迟服务，也有时候可以随机服务。根据服务范围：可以砍掉某个功能，也可以砍掉某些模块。总之服务降级需要根据不同的业务需求采用不同的降级策略。主要的目的就是服务虽然有损但是总比没有好。

限流

限流可以认为服务降级的一种，限流就是限制系统的输入和输出流量已达到保护系统的目的。一般来说系统的吞吐量是可以被测算的，为了保证系统的稳定运行，一旦达到的需要限制的阈值，就需要限制流量并采取一些措施以完成限制流量的目的。比如：延迟处理，拒绝处理，或者部分拒绝处理等等。

限流的核心思想就是人为的丢弃一部分用户请求，不作处理，这样相当于从最根源处就避免的用户后续的操作，虽然对用户体验来说影响非常大，但是只要采用合适的丢弃策略，就能在有效保护系统的同时，尽量减少对用户体验的影响。

限流会导致用户在短时间内（这个时间段是毫秒级的）系统不可用，一般我们衡量系统处理能力的指标是每秒的QPS或者TPS，假设系统每秒的流量阈值是1000，理论上一秒内有第1001个请求进来时，那么这个请求就会被限流。

相关概念

PV(Page View)访问量

即页面浏览量或点击量，用户每次刷新即被计算一次

UV(Unique View)独立访客量

访问网站的一台电脑客户端为一个访客。00:00-24:00内相同的客户端只被计算一次

IP(Internet Protocol)独立IP数

00:00-24:00内相同IP地址之被计算一次

TPS(Transactions Per Second)每秒事务处理量

它是软件测试结果的测量单位。一个事务是指一个客户机向服务器发送请求然后服务器做出反应的过程。客户机在发送请求时开始计时，收到服务器响应后结束计时，以此来计算使用的时间和完成的事务个数。

QPS(Query Per Second)每秒访问量

是一台服务器每秒能够相应的查询次数，是对一个特定的查询服务器在规定时间内所处理流量多少的衡量标准。

QPS基本类似于TPS，但是不同的是，对于一个页面的一次访问，形成一个TPS；但一次页面请求，可能产生多次对服务器的请求，服务器对这些请求，就可计入QPS之中。例如访问一个页面会请求服务器3次，那用户的一次访问页面将会产生1个“T”，产生3个“Q”。 

QPS很大程度上代表了系统的繁忙度，每次请求可能存在多次的磁盘IO，网络请求，多个CPU时间片，一旦QPS超过了预先设置的阀值，可以考量扩容增加服务器，避免访问量过大导致的宕机。

RT(Response Time)每次请求的响应时间

直接决定用户体验性

限流的算法

常见的限流算法有：计数器、漏桶和令牌桶算法。

计数器算法

计数器是最简单粗暴的算法。先给定一个接口在指定时间段内可访问次数，接口在这个时间段中被访问时记下其被访问次数，当访问次数到达其可访问上限则限制后续的访问。当然要记得在每个时间段结束时候清空其访问次数并重新计数。

比如某个服务每秒钟最多只能处理100个请求。我们可以设置一个1秒钟的滑动窗口，窗口中有10个格子，每个格子100毫秒，每100毫秒移动一次，每次移动都需要记录当前服务请求的次数，内存中需要保存10次的次数。

示例代码如下：

/*
接口（key）
时间单位（expire）
允许访问多少次（limit）
访问次数（value）
*/
if(缓存中存在key){
   value++;
   if(value >= limit){
        不能访问
    }
}else{
    向缓存中添加key，value为1
    设置key过期时间为expire
}

漏桶算法(Leaky Bucket)

漏桶算法是一种非常常用的限流算法，可以用来实现流量整形（Traffic Shaping）和流量控制（Traffic Policing）。

漏桶算法的主要概念如下：

1. 一个固定容量的漏桶，按照常量固定速率流出水滴；
2. 如果桶是空的，则不需流出水滴；
3. 可以以任意速率流入水滴到漏桶；
4. 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

举个例子：假如某接口一分钟允许访问60次，那么从开始计时时不管有没有被访问第59秒只允许访问59次，30秒只允许访问30次，10秒只允许访问10次。

示例代码如下：

/*
接口（key）
时间单位（expire）
允许访问多少次（limit）
递减间隔时间（interval）
递减步长（step）
剩余可访问次数（value）
key的访问时间（lastUpdateTime）
当前时间（nowTime）（注意nowTime的取值应为应用取得的时间而不是redis或者nginx取得的时间）
*/
if(缓存中存在key){
   value--；
   if（（nowTime-lastUpdateTime）>interval）{
    value=value-（nowTime-lastUpdateTime）/interval*step;
       lastUpdateTime=nowTime;
   }
   if(value<=0){
        不能访问
    }
}else{
   向缓存中添加key，设置value为limit；
   lastUpdateTime=nowTime；
}

令牌桶算法(Token Bucket)

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务，令牌桶算法通过发放令牌，根据令牌的发放频率做请求频率限制，容量限制等。

令牌桶算法的主要概念如下：

1. 一个存放固定容量令牌的桶，按照固定速率往桶里添加令牌；
2. 假设限制2r/s，则按照500毫秒的固定速率往桶中添加令牌；
3. 桶中最多存放b 个令牌，当桶满时，新添加的令牌被丢弃或拒绝；
4. 当一个n 个字节大小的数据包到达，将从桶中删除n 个令牌，接着数据包被发送到网络上；
5. 如果桶中的令牌不足n 个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么在缓冲区等待）。

如下图：

令牌算法是根据放令牌的速率去控制输出的速率，也就是上图的Departure的速率。Departure我们可以理解为消息的处理程序，执行某段业务或者调用某个RPC。

示例代码如下：

/*
接口（key）
时间单位（expire）
允许访问多少次（limit）
递减间隔时间（interval）
递减步长（step）
剩余可访问次数（value）
key的访问时间（lastUpdateTime）
当前时间（nowTime）（注意nowTime的取值应为应用取得的时间而不是redis或者nginx取得的时间）
*/

线程一（用户请求该接口）：
if(缓存中存在key){
   value++；
   if(value>=limit){
        不能访问
    }
}else{
   向缓存中添加key，设置value为limit
}

线程一（后台定时任务）：
while(过去interval时间){
   所有key的value+step
}

相比漏桶算法，令牌桶算法可以在运行时控制和调整数据处理的速率，处理某时的突发流量。放令牌的频率增加可以提升整体数据处理的速度，而通过每次获取令牌的个数增加或者放慢令牌的发放速度和降低整体数据处理速度。而漏桶算法不行，因为它的流出速率是固定的，程序处理速度也是固定的。

整体而言，令牌桶算法更优，但是实现更为复杂一些。