分分布式限流的概念、主流解决方案和常用算法分享

1、分布式限流的概念

讲到“限流”，我想大家都经历过“被限流”的情况，只是大家浑然不觉，举个例子，春运作为人类历史上最大的迁徙活动，抢火车票一直是每年跨年的热点话题，说到抢火车票就不得不提12306了，下面这个图片我想大家应该很熟悉了：

不错这个就是当年整哭我们的“验证码图片”，当我们春运抢票的时候，就算运用毕生所学选出正确答案，提交后仍然被告知选错了，这些连鬼都认不出的图片，一度整的我们怀疑智商，但其实这就是网站的一种限流措施，在拷问用户智商的同时，通过这种故意“刁难”的手段，光明正大的进行限制流量访问，从而大幅度的降低系统的访问压力，产品经理的智（良）慧（心）真的是nice！
什么是分布式限流
在大数据高并发访问时，经常会出现服务或接口面对暴涨的请求而出现不可用的情况，甚至引发连锁反应导致整个系统不可用，此时需要的技术技术手段就是限流，限流就是在某个时间窗口对资源访问做限制，当请求达到一定的并发数或者速率，就进行等待、排队、降级、拒绝服务等。
分布式限流的几种维度
对于一般限流场景来说，它具有两个维度的信息：
时间限流基于某段时间范围或者某个时间点，也就是我们常说的“时间窗口”，比如对每分钟、每秒钟的时间窗口做限定。
资源基于可用资源的限制，比如设定最大的访问次数，或最高可用连接数。
分布式限流的规则

QPS和连接数控制
Qps(query per second)和连接数限流来说，主要可以设备IP的限流，也可以设定基于单个服务器的限流，在真正的应用环境中，通常会设置多个维度的限流规则，比如同一个ip每秒钟的访问频率小于10，连接数小于5，再设定每台机器Qps最高1000，连接数最大保持200。更进一步，我们可以把某个服务器组或者整个机房的服务器当做一个整体，设置更high-level的限流规则。
传输速率
传输速率大家不陌生，百度网盘会员传输速率可达10M/s，普通用户10k/s，背后的逻辑是基于用户组或者用户标签的限流规则。
黑白名单
黑白名单是各个大型企业应用里很常见的限流和放行手段，而且黑白名单往往是动态变化的，举个例子，如果某个IP在一段时间的访问次数过于频繁，被系统识别为机器人用户或者流量攻击，那么这个IP就会被加入到黑名单，从而限制对系统资源的访问，称为“封IP”。白名单很好理解，相当于御赐金牌在手，可以自由的穿梭在各种限流规则里，畅行无阻。
分布式环境中的限流
所谓的分布式限流，道理其实很简单，一句话可以解释清楚，区别于单机限流场景，它把整个分布式环境当做一个整体来考量，比如针对IP的限流，我们限制了1个IP每秒最多10个访问，不管来自这个IP的请求落到哪个请求上，只要是访问了集群中的访问节点，那么就会受到限流规则的制约。从上面的例子不难看出，我们必须将限流限流信息保存到一个“中心化”的组件上，这样就可以获取到集群中所有机器的访问状态，目前的两个主流方案：

网关层限流将限流规则应用在所有流量的入口处
中间件限流将限流信息存储在分布式环境中某个中间件里（比如Redis缓存），每个组件都可以从这里获取到当前时刻的流量统计，从而决定是拒绝服务还是放行流量。

2、分布式限流的主流方案

分布式限流方案众多，本次只介绍三个主流的方案：

Guava客户端组件 讲到Guava,大家都不陌生，它是Google出品的一款工具包（com.google.guava）,在开发中我们经常能用到的就是Lists,newArrayList（）等，它最早源于2007年的“Google Collections Library”
项目，除了我们常见的Collections，Guava在反射工具、函数式编程、安全验证、数***算等方面也做出了很大的贡献，在限流领域，Guava也插了一脚，在其多线程模块下，提供了RateLimiter为为首的几个限流支持类，Guava是一个客户端组件，也就是说它的作用范围仅限于“当前”的服务器，不能对集群以内的其他服务器增加流量控制。

从上图中我们可以看出，当我们分布式中有两台服务器时【Server1 Server2】,这两台服务器都部署了一个登陆服务，如果我们想对这两台机器进行流量控制，如果将两台机器中的访问量总和控制在每秒100内，如果用Guava来做，那么只能独立控制每台机器的访问总量<=50。
网关层限流 网关层作为分布式链路的第一道关卡，承接了所有的用户请求。系统的流量分布层次可以简单的抽象为以下这种简单的漏斗模式来看：

上述是一个普通的流量模型，从上到下的路径依次是：
①、用户流量从网关层转发到后台服务。
②、后台服务承接流量，调用缓存获取数据。
③、缓存中无数据，则访问数据库。
提到分布式网关层，我们会自然而然的想到Nginx,其中Nginx可以通过以下方式实现限流
1）基于IP地址和基于服务器的访问请求限流。
2）开发量（连接数）限流。
3）下行带宽速率限流。
3. 中间件限流
上述提到的网关层限流，对于开发团队来说不好控制，那能不能将限流下沉到业务层，让开发团队去控制呢？当然可以，我们可以借助中间件Redis去打造一个服务端限流的利器，利用Redis的过期时间特性，我们可以轻松的设置限流的时间跨度（比如每秒10个请求）。同时Redis有一个特殊的技能-脚本编程，我们可以将限流逻辑编写成一段脚本植入到Redis中，将限流的重任从服务层完全剥离出来，同时Redis强大的并发量特征以及高可用集群架构也可以很好地支持庞大的集群限流访问。
4.限流组件
目前一些开源组件也实现了限流的功能，比如阿里的Sentinel就是一个不错的选择。

3、分布式限流的常用算法

1. 令牌桶算法
令牌桶（Token Bucket）算法是目前应用最广泛的限流算法，顾名思义，他有两个关键角***r> 1）令牌获取到令牌的Request才会被处理，其他Request要么排队，要么被丢弃。
2）桶用来装令牌的地方，所有Request都从这个桶中获取令牌。

令牌生成
这个过程涉及到令牌生成器和令牌桶，令牌桶就是一个装令牌的地方，而桶有一个容量，也就是说令牌桶所能容纳的令牌数量是一个固定的数值。对于令牌生成来说，它会以一个预定的速率向桶中增加令牌，当然这个速度可以是匀速的，也可是非匀速的。
令牌获取
每个访问请求过来，必须获取到一个令牌才能执行后面的逻辑，如果访问请求过多，一部分请求自然无法获取到令牌，我们可以设置一个“缓冲队列”来暂存这些多余的令牌。
2. 漏桶算法
漏桶算法（Leaky Bucket）是将请求的数据包放到桶里，如果桶满了，那么后面新来的数据包将被丢弃。

3. 滑动窗口
滑动窗口（Rolling Window）下图中的黑色框就是我们设定的时间窗口，设定时间窗口为5秒，会随着时间的推移向后推移，每个格子代表一秒钟，，同时每个格子还包含一个计数器，用来计算在当前时间内访问数据的总量。那么这个时间窗口内的总访问量就是所有格子计数器累计后的数值。

滑动窗口也是一种计数器的算法，它有一个显著特点，当时间窗口的跨度足够长时，限流的效果越平滑，例如，如果当前时间窗口只有2秒，而访问请求全部集中在第一秒的时候，当时间向后滑动一秒，当前窗口的计数量将发生较大的变化，拉长时间概率可以降低这种情况的发生概率。