大厂面试必备--分布式限流，一篇文章搞定
一、限流
高并发系统中有三把利器用来保护系统：缓存、降级、限流
缓存
缓存比较好理解，在大型高并发系统中，如果没有缓存数据库将分分钟被爆，系统也会瞬间瘫痪。使用缓存不单单能够提升系统访问速度、提高并发访问量，也是保护数据库、保护系统的有效方式。大型网站一般主要是“读”，缓存的使用很容易被想到。在大型“写”系统中，缓存也常常扮演者非常重要的角色。比如累积一些数据批量写入，内存里面的缓存队列（生产消费），以及HBase写数据的机制等等也都是通过缓存提升系统的吞吐量或者实现系统的保护措施。甚至消息中间件，你也可以认为是一种分布式的数据缓存。
降级
服务降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略的降级，以此释放服务器资源以保证核心任务的正常运行。降级往往会指定不同的级别，面临不同的异常等级执行不同的处理。根据服务方式：可以拒接服务，可以延迟服务，也有时候可以随机服务。根据服务范围：可以砍掉某个功能，也可以砍掉某些模块。总之服务降级需要根据不同的业务需求采用不同的降级策略。主要的目的就是服务虽然有损但是总比没有好。
限流
限流可以认为服务降级的一种，限流就是限制系统的输入和输出流量已达到保护系统的目的。一般来说系统的吞吐量是可以被测算的，为了保证系统的稳定运行，一旦达到的需要限制的阈值，就需要限制流量并采取一些措施以完成限制流量的目的。比如：延迟处理，拒绝处理，或者部分拒绝处理等等。
生活中限流的栗子实在太多，比如：
- 很多公众号一般喜欢在下午六点发文（当然也包括我们），一般都会提前写好文章，然后设置一个定时发送的任务。但是一般在六点的时候，文章都是发不出去的，需要等待10-20分钟左右，因为那个时候要发文的公众号实在是太多太多了。腾讯当然不会放任我们轰炸他的服务，然后就限流慢慢处理了。所以一般都是不会准时收到推文的，好惨。。。
- 逢年过节或者做活动，我们是不是经常收到一大堆各大平台或者各种厂家促销活动的短信？就比如某东的会员有1000W，要同时给这1000W会员发送消息，某东能够发送，但是联通移动运营商肯定不干。所以要么排队慢慢发，要么就是拒绝某东后台发来的请求。
- 我公司在外的设备，每秒钟都会往kafka里面发送数据，最大的时候每秒有上万条几十万条数据产生，虽然用了5台web服务，但是万一又增加设备了，总是会吃不消的。由于数据不需要实时分析处理，所以就稍微做了一下限流。
二、限流算法
限流方法：两窗两桶（固定窗口、滑动窗口，漏桶、令牌桶）
01固定窗口
（1）划分时间为多个窗口：固定一个时间周期，如10秒或者30秒
（2）在每个窗口期内，每有一个请求，计数器加一
（3）如果计数器超过了限制数量，则本窗口内所有的请求都被丢弃
（4）下一个时间窗口时，计数器重置
实现是很简单的：
int totalCount = 0;
if(totalCount > 限流阈值) {
return;
}
totalCount++;
// do something...
固定窗口计数器是最为简单的算法，但这个算法有时会让通过请求量允许为限制的两倍。考虑如下情况：限制1秒内最多通过5个请求，在第一个窗口的最后半秒内通过了5个请求，第二个窗口的前半秒内又通过了5个请求。这样看来就是在1秒内通过了10个请求。
假如请求的进入非常集中，那么所设定的「限流阈值」等同于你需要承受的最大并发数。所以，如果需要顾忌到并发问题，那么这里的「固定周期」设定的要尽可能的短，这样的话「限流阈值」的数值就可以相应的减小。甚至限流阈值就可以直接用并发数来指定。考虑到上段的描述，会有请求量超过的情况，往往限流阈值要小于所能承受的最大并发。
不过不管怎么设定，固定窗口永远存在的缺点是：由于流量的进入往往都不是一个恒定的值，所以一旦流量进入速度有所波动，要么计数器会被提前计满，导致这个周期内剩下时间段的请求被“限制”。要么就是计数器计不满，也就是「限流阈值」设定的过大，导致资源无法充分利用。
02滑动窗口
滑动窗口是固定窗口的改善，大致的概念如下：
（1）将时间划分为更小的多个时间区间
（2）一个时间窗口占用固定的多个时间区间，每有一次请求，就给一个时间区间计数
（3）每经过一个时间区间，就抛弃最老的一个时间区间，加入一个最新的时间区间
（4）如果当前窗口内区间的请求计数总和超过了限制数量，则本窗口内所有请求都会被丢弃
滑动窗口计数器是通过将窗口再细分，并且按照时间"滑动"，这种算法避免了固定窗口计数器带来的双倍突发请求，但时间区间的精度越高，算法所需的空间容量就越大。所以，如果固定区间已经很小了，使用滑动窗口也没有意义了。比如固定区间的周期是1秒，再切分到毫秒，会造成更大的性能和资源损失。
滑动窗口本质上是预先划定时间片的方式，属于一种“预测”，意味着几乎肯定无法100%的物尽其用。
03漏桶
（1）将每个请求视为“水滴”放入漏桶进行存储
（2）漏桶以固定速率漏出水滴（处理请求）
（3）漏桶满了，多余的水滴就丢弃
简单说来就是：如果当前速率小于阈值则直接处理请求，否则不直接处理请求，进入缓冲区，并增加当前水位
漏桶算法多使用队列实现，服务的请求会存到队列中，服务的提供方则按照固定的速率从队列中取出请求并执行，过多的请求则放在队列中排队或直接拒绝。
漏桶算法的缺陷也很明显，当短时间内有大量的突发请求时，即便此时服务器没有任何负载，每个请求也都得在队列中等待一段时间才能被响应。
04令牌桶
（1）令牌以固定速率生成
（2）生成的令牌放入令牌桶中存放，如果令牌桶满了则多余的令牌直接丢弃，当请求到达时，会尝试从令牌桶中取令牌，得到令牌的请求可以执行
（3）如果桶空了，则丢弃取令牌的请求
令牌桶的容量大小理论上就是程序需要支撑的最大并发数。令牌桶算法既能够将所有的请求平均分布到时间区间内，又能接受服务器能够承受范围内的突发请求，因此是目前使用较为广泛的一种限流算法。
对于令牌桶的代码实现，可以直接使用Guava包中的RateLimiter
@Override
public BaseResponse<UserResVO> getUserByFeignBatch(@RequestBody UserReqVO userReqVO) {
//调用远程服务
OrderNoReqVO vo = new OrderNoReqVO() ;
vo.setReqNo(userReqVO.getReqNo());
RateLimiter limiter = RateLimiter.create(2.0) ;
//批量调用
for (int i = 0 ;i< 10 ; i++){
double acquire = limiter.acquire();
logger.debug("获取令牌成功!,消耗=" + acquire);
BaseResponse<OrderNoResVO> orderNo = orderServiceClient.getOrderNo(vo);
logger.debug("远程返回:"+JSON.toJSONString(orderNo));
}
UserRes userRes = new UserRes() ;
userRes.setUserId(123);
userRes.setUserName("张三");
userRes.setReqNo(userReqVO.getReqNo());
userRes.setCode(StatusEnum.SUCCESS.getCode());
userRes.setMessage("成功");
return userRes ;
}
使用RateLimiter有几个值得注意的地方:允许先消费，后付款，意思就是它可以来一个请求的时候一次性取走几个或者是剩下所有的令牌甚至多取，但是后面的请求就得为上一次请求买单，它需要等待桶中的令牌补齐之后才能继续获取令牌。
三、分布式场景
单节点模式下，使用RateLimiter进行限流一点问题都没有。但线上是分布式系统，布署了多个节点，而且多个节点最终调用的是同一个API/服务商接口。虽然我们对单个节点能做到将QPS限制在N/s，但是多节点条件下，如果每个节点均是N/s，那么到服务商那边的总请求就是节点数乘以N/s，于是限流效果失效。使用该方案对单节点的阈值控制是难以适应分布式环境的。
我们来看一下最简单的流量模型：
用户的请求从网关转发到后台服务，后台服务承接流量，调用缓存获取数据，缓存中的数据和数据库交互。这个模型就像一个漏斗一样，流量自上而下递减。
解决方案一：网关限流
服务网关，作为整个分布式链路中的第一关卡，承接了所有用户的访问请求，所以从这里限流肯定是大头。目前主流的网关层有以软件为代表的Nginx，Spring Cloud中的Gateway和Zuul这类的组件，当然也有硬件的网关限流。
1.Nginx限流：思想就是漏桶算法，即能够强行保证请求实时处理的速度不会超过设置的阈值
- 基于IP地址和基于服务器的访问请求限流
- 并发量（连接数）限流
- 下行带宽速率限制
Nginx限制IP连接和并发分别有两个模块：
limit_req_zone：用来限制单位时间内的请求数，即速率限制,采用的漏桶算法 "leaky bucket"。
limit_req_conn：用来限制同一时间连接数，即并发限制。
limit_req_zone参数配置
Syntax: limit_req zone=name [burst=number] [nodelay]; Default: — Context: http, server, location
limit_req_zone $binary_remote_addr zone=one:10m rate=1r/s;
- 第一个参数：$binary_remote_addr 表示通过remote_addr这个标识来做限制，“binary_”的目的是缩写内存占用量，是限制同一客户端ip地址。
- 第二个参数：zone=one:10m表示生成一个大小为10M，名字为one的内存区域，用来存储访问的频次信息。
- 第三个参数：rate=1r/s表示允许相同标识的客户端的访问频次，这里限制的是每秒1次，还可以有比如30r/m的。
limit_req zone=one burst=5 nodelay;
- 第一个参数：zone=one 设置使用哪个配置区域来做限制，与上面limit_req_zone 里的name对应。
- 第二个参数：burst=5，重点说明一下这个配置，burst爆发的意思，这个配置的意思是设置一个大小为5的缓冲区当有大量请求（爆发）过来时，超过了访问频次限制的请求可以先放到这个缓冲区内。
- 第三个参数：nodelay，如果设置，超过访问频次而且缓冲区也满了的时候就会直接返回503，如果没有设置，则所有请求会等待排队。
ngx_http_limit_conn_module参数配置
这个模块用来限制单个IP的请求数。并非所有的连接都被计数。只有在服务器处理了请求并且已经读取了整个请求头时，连接才被计数。
Syntax: limit_conn zone number; Default: — Context: http, server, location
举个栗子：比如下方的配置，一次只允许每个IP地址的一个连接
limit_conn_zone $binary_remote_addr zone=addr:10m; server { location /download/ { limit_conn addr 1; }
又或者以下这样配置：限制每个客户端IP连接到服务器的数量，同时限制连接到虚拟服务器的总数：
limit_conn_zone $binary_remote_addr zone=perip:10m; limit_conn_zone $server_name zone=perserver:10m; server { ... limit_conn perip 10; limit_conn perserver 100;}
解决方案二：服务限流Redis 的 RateLimiter
@GetMapping("/")
public void index(HttpServletResponse response) throws IOException {
Jedis jedis = jedisPool.getResource();
String token = RedisRateLimiter.acquireTokenFromBucket(jedis, LIMIT, TIMEOUT);
if (token == null) {
response.sendError(500);
}else{
//TODO 你的业务逻辑
}
jedisPool.returnResource(jedis);
}
解决方案三： Reids+Lua脚本 （可保证操作的原子性）
local key = "rate.limit:" .. KEYS[1]
local limit = tonumber(ARGV[1])
local expire_time = ARGV[2]
local is_exists = redis.call("EXISTS", key)
if is_exists == 1 then
if redis.call("INCR", key) > limit then
return 0
else
return 1
end
else
redis.call("SET", key, 1)
redis.call("EXPIRE", key, expire_time)
return 1
end
在真实的大型项目里，不会只使用一种限流手段，往往是几种方式搭配使用，让限流策略有一种层次感，达到资源的最大利用。
本文参考：
https://blog.csdn.net/icangfeng/article/details/81202007
http://www.imooc.com/article/298330
https://www.cnblogs.com/the-fool/p/11054072.html
https://www.jianshu.com/p/52dc87011109