高可用之限流-01-入门介绍
限流系列
高可用之限流-06-slide window 滑动窗口 sentinel 源码
高可用之限流 09-guava RateLimiter 入门使用简介 & 源码分析
背景
在如今的互联网已经作为社会基础设施的大环境下，上面的这个场景其实离我们并不是那么远，同时也会显得没那么极端。
例如，层出不穷的营销玩法，一个接着一个的社会热点，以及互联网冰山之下的黑产、刷子的蓬勃发展，更加使得这个场景变的那么的需要去考虑、去顾忌。
因为随时都有可能会涌入超出你预期的流量，然后压垮你的系统。
那么限流的作用就很显而易见了：只要系统没宕机，系统只是因为资源不够，而无法应对大量的请求，为了保证有限的系统资源能够提供最大化的服务能力，因而对系统按照预设的规则进行流量（输出或输入）限制的一种方法，确保被接收的流量不会超过系统所能承载的上限。
限流
服务治理本身的概念比较大，包括鉴权、限流、降级、熔断、监控告警等等。
场景需求
比如限制微服务集群单台机器每秒请求次数，我们还需要针对不同调用方甚至不同接口进行更加细粒度限流：
比如限制 A 调用方对某个服务的某个的接口的每秒最大请求次数。
流
限流中的“流”字该如何解读呢？要限制的指标到底是什么？
不同的场景对“流”的定义也是不同的，可以是网络流量，带宽，每秒处理的事务数 (TPS)，每秒请求数 (hits per second)，并发请求数，
甚至还可能是业务上的某个指标，比如用户在某段时间内允许的最多请求短信验证码次数。
从保证系统稳定可用的角度考量，对于微服务系统来说，最好的一个限流指标是：并发请求数。
通过限制并发处理的请求数目，可以限制任何时刻都不会有过多的请求在消耗资源
，比如：我们通过配置 web 容器中 servlet worker 线程数目为 200，则任何时刻最多都只有 200 个请求在处理，超过的请求都会被阻塞排队。
对比 TPS 和 hits per second 的两个指标，我们选择使用 hits per second 作为限流指标。
因为，对 TPS 的限流实际上是无法做的，TPS 表示每秒处理事务数，事务的开始是接收到接口请求，事务的结束是处理完成返回，所以有一定的时间跨度，如果事务开始限流计数器加一，事务结束限流计数器减一，则就等同于并发限流。
而如果把事务请求接收作为计数时间点，则就退化为按照 hits per second 来做限流，而如果把事务结束作为计数时间点，则计数器的数值并不能代表系统当下以及接下来的系统访问压力。
对 hits per second 的限流是否是一个有效的限流指标呢？答案是肯定的，这个值是可观察可统计的，所以方便配置限流规则，而且这个值在一定程度上反应系统当前和接下来的性能压力，对于这一指标的限流确实也可以达到限制对系统资源的使用。
有了流的定义之后，我们接下来看几种常用的限流算法：固定时间窗口，滑动时间窗口，令牌桶算法，漏桶算法以及他们的改进版本。
常见算法
固定时间窗口
- 算法思想
首先需要选定一个时间起点，之后每次接口请求到来都累加计数器，如果在当前时间窗口内，根据限流规则（比如每秒钟最大允许 100 次接口请求），
累加访问次数超过限流值，则限流熔断拒绝接口请求。
当进入下一个时间窗口之后，计数器清零重新计数。
- 缺点
限流策略过于粗略，无法应对两个时间窗口临界时间内的突发流量。
我们举一个例子：假设我们限流规则为每秒钟不超过 100 次接口请求，第一个 1s 时间窗口内，100 次接口请求都集中在最后的 10ms 内，
在第二个 1s 的时间窗口内，100 次接口请求都集中在最开始的 10ms 内，虽然两个时间窗口内流量都符合限流要求 (<=100 个请求)，
但在两个时间窗口临界的 20ms 内会集中有 200 次接口请求，如果不做限流，集中在这 20ms 内的 200 次请求就有可能压垮系统。
滑动时间窗口
滑动时间窗口算法是对固定时间窗口算法的一种改进，流量经过滑动时间窗口算法整形之后，可以保证任意时间窗口内，都不会超过最大允许的限流值，从流量曲线上来看会更加平滑，可以部分解决上面提到的临界突发流量问题。
对比固定时间窗口限流算法，滑动时间窗口限流算法的时间窗口是持续滑动的，并且除了需要一个计数器来记录时间窗口内接口请求次数之外，还需要记录在时间窗口内每个接口请求到达的时间点，对内存的占用会比较多。
- 算法模型
滑动时间窗口的算法模型如下：
滑动窗口记录的时间点 list = (t_1, t_2, …t_k)，时间窗口大小为 1 秒，起点是 list 中最小的时间点。
当 t_m 时刻新的请求到来时，我们通过以下步骤来更新滑动时间窗口并判断是否限流熔断：
STEP 1: 检查接口请求的时间 t_m 是否在当前的时间窗口 [t_start, t_start+1 秒) 内。如果是，则跳转到 STEP 3，否则跳转到 STEP 2.
STEP 2: 向后滑动时间窗口，将时间窗口的起点 t_start 更新为 list 中的第二小时间点，并将最小的时间点从 list 中删除。然后，跳转到 STEP 1。
STEP 3: 判断当前时间窗口内的接口请求数是否小于最大允许的接口请求限流值，即判断: list.size < max_hits_limit，如果小于，则说明没有超过限流值，允许接口请求，并将此接口请求的访问时间放入到时间窗口内，否则直接执行限流熔断。
- 缺陷
即便滑动时间窗口限流算法可以保证任意时间窗口内接口请求次数都不会超过最大限流值，但是仍然不能防止在细时间粒度上面访问过于集中的问题。
比如上面举的例子，第一个 1s 的时间窗口内 100 次请求都集中在最后 10ms 中。
也就是说，基于时间窗口的限流算法，不管是固定时间窗口还是滑动时间窗口，只能在选定的时间粒度上限流，对选定时间粒度内的更加细粒度的访问频率不做限制。
- 改进版本
多层次限流，我们可以对同一个接口设置多条限流规则，除了 1 秒不超过 100 次之外，我们还可以设置 100ms 不超过 20 次 (这里需要设置的比 10 次大一些)，
两条规则同时限制，流量会更加平滑。
除此之外，还有针对滑动时间窗口限流算法空间复杂度大的改进算法，限于篇幅，这里就不展开详说了。
令牌桶算法
令牌桶和漏桶算法的算法思想大体类似，可以把漏桶算法作为令牌桶限流算法的改进版本，所以我们以介绍令牌桶算法为主。
- 核心算法
我们先来看下最基础未经过改进的令牌桶算法：
-
接口限制 t 秒内最大访问次数为 n，则每隔 t/n 秒会放一个 token 到桶中；
-
桶中最多可以存放 b 个 token，如果 token 到达时令牌桶已经满了，那么这个 token 会被丢弃；
-
接口请求会先从令牌桶中取 token，拿到 token 则处理接口请求，拿不到 token 则执行限流。
令牌桶算法看似比较复杂，每间隔固定时间都要放 token 到桶中，但并不需要专门起一个线程来做这件事情。
每次在取 token 之前，根据上次放入 token 的时间戳和现在的时间戳，计算出这段时间需要放多少 token 进去，一次性放进去，所以在实现上面也并没有太大难度。
漏桶算法
漏桶算法稍微不同与令牌桶算法的一点是：对于取令牌的频率也有限制。
要按照 t/n 固定的速度来取令牌，所以可以看出漏桶算法对流量的整形效果更加好，流量更加平滑，任何突发流量都会被限流。
因为令牌桶大小为 b，所以是可以应对突发流量的。
- 其他改进算法
当然，对于令牌桶算法，还有很多其他改进算法，比如：
-
预热桶
-
一次性放入多个令牌
-
支持一次性取多个令牌
- 使用场景
令牌桶和漏桶算法比较适合阻塞式限流。
比如一些后台 job 类的限流，超过了最大访问频率之后，请求并不会被拒绝，而是会被阻塞到有令牌后再继续执行。
对于像微服务接口这种对响应时间比较敏感的限流场景，会比较适合选择基于时间窗口的否决式限流算法，其中滑动时间窗口限流算法空间复杂度较高，
内存占用会比较多，所以对比来看，尽管固定时间窗口算法处理临界突发流量的能力较差，但实现简单，而简单带来了好的性能和不容易出错，
所以固定时间窗口算法也不失是一个好的微服务接口限流算法。
guava 实现
http://ifeve.com/guava-ratelimiter/
可参考 guava 的实现。