Redis+Lua分步式限流方案

1. 背景

对于微服务这种分步式架构体系，虽然天生就具有高并发、高可用等特性，但现实条件下仍然会受各种条件制约而存在访问瓶颈，比如经费、硬件、软件等资源的限制，因此为了保证我们服务不被大流量（正常业务增长、突发流量等）所冲垮，我们不光要在各层添加集群的支持，同时还要为系统制定有效的限流策略来保护我们的系统。

另外，限流不光局限于对大流量的访问控制，还渗透在我们许多业务场景中，比如根据不同用户制定不同的访问策略（如：用户下载，不同身份的用户拥有不同的下载次数），可以说只要涉及到访问控制，大部分会伴随着限流。

2. 常用的限流算法

目前业界比较流行的限流算法为令牌桶算法与漏桶算法。

2.1 漏桶算法

漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.示意图如下:

可见这里有两个变量,一个是桶的大小,支持流量突发增多时可以存多少的水(burst),另一个是水桶漏洞的大小(rate)。

因为漏桶的漏出速率是固定的参数,所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使流突发(burst)到端口速率.因此,漏桶算法对于存在突发特性的流量来说缺乏效率.

2.2令牌桶算法

令牌桶算法(Token Bucket)和 Leaky Bucket 效果一样但方向相反的算法,更加容易理解.随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务。

令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量.

3. 算法实现

3.1实现思路

因为要在分步式下进行限流，我们的各个服务都会以集群方式部署，所以我们同一服务间的不同节点必须是无状态的。因此我们不能将我们限流信息保存在服务的内存当中。一般我们会选用独立于服务之外的存储媒介，比如数据库、缓存服务（redis、memcachet等），对于传统的数据库明显不合适，因为涉及大量的IO操作，且数据库往往会成为服务的性能瓶颈。因此我们一般采用缓存系统，因为是纯内存操作，性能比较好，且不容易出现瓶颈（只要内存能扛着即可）。这里我们采用redis作为我们的存储媒介。

上段解决了访问信息存储的问题，可以保证限流服务集群下各服务节点能进行统一的访问，但存在明显的弊端，因为不管是令牌桶算法还是漏桶算法，都需要通过代码访问限流信息，然后在代码中进行判断是否超限，然后再来操作缓存中的信息。问题是不能保存原子性，那就会存在并发问题（比如：多条流量同时到达，都从缓存取到的令牌为1，都认为自己可以访问，然后同时改令牌为1-1=0，但明显让限流失效了）。因此我们想方设法来保证操作的原子性，下边是常常会想到的方案：

3.2 算法实现

3.2.1 令牌桶

基于spring boot+redis+lua（关于lua脚本，大家可自行学习）

3.2.1.1 准备lua脚本

①初始化令牌桶缓存脚本(即当请求第一次进来时，需要将令牌信息存储到缓存中）

②令牌桶限流脚本

3.2.1.2 程序加载lua脚本（本例中脚本放在resources/lua下）

3.2.1.3 程序限流(为了节省篇幅部分属于伪代码）

3.2.2 漏桶算法

漏桶算法相对逻辑比较简单，当每次访问时对访问次数加1，如果超限则直接拦截即可。当过了时间周期，重新以新的时间为开始，将桶清空，继续接受请求。可以采用redis过期时间策略+incr操作实现。

3.2.2.1 准备lua脚本

leakBucketRateLimit.lua

3.2.2.2 程序加载lua

参考3.2.1.2章节，此处不作赘述。

3.2.2.3 程序限流

参考3.2.1.3章节，此处不作赘述。

3.3 算法适用场景

4.总结

到此为止，已经给大家介绍了限流的必要性以及常用限流手段与程序实现。相信大家对分步式限流有了一个初步的了解，此文算是一篇入门文章，如果大家比较感兴趣，下去可以找文章深入研究。

（Tx）