常见限流算法解读
原创
前言
在现在的互联网系统中有很多业务场景，比如商品秒杀、下单、数据查询详情，其最大特点就是高并发，但是我们的系统通常不能承受这么大的流量，继而产生了很多的应对措施：消息队列、多级缓存、异地多活。但是无论如何优化，由于硬件的物理特性决定了我们系统性能的上限，如果强行接收所有请求，往往造成服务雪崩，导致服务的不可用，这个时候服务限流就成为我们必不可少的一个手段了。
服务限流，是指通过控制请求的速率或次数来达到保护服务的目的，在微服务中，我们通常会将它和熔断、降级搭配在一起使用，来避免瞬时的大量请求对系统造成负荷，来达到保护服务平稳运行的目的，常见的熔断组件有Hystrix，Nginx跟阿里的Sentinel，以及Gateway采用的基于Redis实现的令牌桶算法。
QPS（TPS）：每秒钟request/事务 数量
下面我会介绍常见的四种限流算法：
- 固定窗口（计算器法）
- 滑动窗口
- 漏桶算法
- 令牌桶算法
固定窗口（计算器法）
计算器法算法是使用计数器在周期内累加访问次数，当达到设定的限流值时，触发限流策略。下一个周期开始时，进行清零，重新计数。
比如限流设定为1s内3次，那么每次收到请求就计数加一，并判断这1s内计数是否大于上限3，没超过上限就返回成功，否则返回失败。
这个算法的缺点就是在时间临界点如果会有较大瞬间流量，不能达到我们预期的限流算法
假设1s内服务器的负载能力为3，因此一个周期的访问量限制在3，然而在第一个周期的最后0.5秒和下一个周期的开始0.5秒时间段内，分别涌入2个访问量，虽然没有超过每个周期的限制量，但是整体上1秒内已达到4个访问量，已远远超过服务器的负载能力，由此可见，计数器算法方式限流对于周期比较长的限流，存在很大的弊端，如下图所示：
滑动窗口
滑动窗口算法解决固定窗口临界值的问题。它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期。
我们将时间间隔均匀分隔，比如将1S分为个0.5秒，每一个0.5秒内单独计数，总的数量限制为这2个0.5秒的总和，我们把这2个0.5秒成为“窗口”。
那么每过0.5秒，窗口往前滑动一步，数量限制变为新的2个0.5秒的总和，如图所示：
那么如果在临界时，收到4个请求，就会进行限流
接着窗口进行滑动
当滑动窗口的格子划分地越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。
漏桶算法
漏桶算法其实很简单，可以粗略的认为就是注水漏水过程，往桶中以一定速率流出水，以任意速率流入水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。
假设桶的容量为4，现在每秒有5个请求进来 ，而桶的流速为1s流出2个请求。
第一秒的情况如下
第二秒时也就会有4个请求会被丢弃
假设你的漏桶出口固定了每秒钟只能通过100个请求，如果此时有150个请求，无论你后方的系统能不能抗住这150个请求，通过漏桶算法都会将另外50个请求进行拦截，只能等前面的100个请求结束后才能继续放行剩下的50个请求，无法应对突发流量的来袭。
在算法实现方面，可以准备一个队列，用来保存请求，另外通过一个线程池定期从队列中获取请求并执行，可以一次性获取多个并发执行。
这种算法，在使用过后也存在弊端：无法应对短时间的突发流量。
漏桶可以看作是一个带有常量服务时间的单服务器队列，如果漏桶（包缓存）溢出，那么数据包会被丢弃。 在网络中，漏桶算法可以控制端口的流量输出速率，平滑网络上的突发流量，实现流量整形，从而为网络提供一个稳定的流量。
漏桶算法是一个匀速的执行，令牌桶支持突发以及预热，具体的需求看自己的需求吧。同时漏桶算法需要做溢出处理，而令牌桶不需要。
令牌桶算法
令牌桶算法维护一个固定容量的令牌桶，每秒钟会向令牌桶放入一定数量的令牌。当有请求到来时，如果令牌桶中有足够的令牌，则请求被允许通过并从令牌桶中消耗一个令牌，如果令牌桶中没有令牌则会请求被拒绝。
令牌桶中没有令牌，请求进来则会被拒绝即起到了限流。
令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。
与漏桶算法相比，有可能导致短时间内的请求数上升（因为拿到令牌后，就可以访问接口，存在一瞬间将所有令牌拿走的情况），但不会有计数算法那样高的峰值（因为令牌数量是匀速增加的）。所以在应对突发流量的时候令牌桶表现的更佳。
总结
- 令牌桶、漏桶算法更适合阻塞式限流的场景，即后台任务类的限流。
- 而基于时间窗口的限流则更适合互联网实施业务限流的场景，即能处理快速处理，不能处理及时响应调用方，避免请求出现过长的等待时间。
Gateway则采用了基于Redis实现的令牌桶算法，而Sentinel内部却比较复杂：
- 默认限流模式是基于滑动时间窗口算法 - 排队等待的限流模式则基于漏桶算法 - 而热点参数限流则是基于令牌桶算法
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
