什么是限流？
限流，限流，就是限制流量。
在日常生活中，我们经常能看到一些限流场景，比如旅游景点限流、餐厅排队等号、交通限流等，目的就是为了确保可以正常运转。
同样，在我们进行应用开发时，也需要把应用系统的限流做好，避免突发流量、恶意攻击等大量请求的冲击带来不必要的影响，确保业务系统的正常运行。
如何限流？
首先我们需要知道限流的基本思路，其次需要知道限流的几种实现方式（这里我们叫限流算法）。
限流的基本思路就是：在一个单位时间内流量超过某个阈值后被拒绝或限制。
目前常见的限流算法有4个：
-
计数器，也叫固定时间窗口算法。 -
滑动时间窗口算法。 -
漏斗算法。 -
令牌算法。
下面分别对这4种限流算法进行介绍，并通过Java代码实现简单的限流功能。
计数器（固定时间窗口）算法
原理
计数器（固定时间窗口）算法是最简单的限流算法。
简单来讲就是：在固定时间内累计访问次数，当次数达到阈值后，触发限流（拒绝访问或者排队等待）。
如下图，在0～1s内，如果counter>=100，那么在这个时间内就不会再接受新的请求，一直到1s后将counter进行重置。
代码实现
代码实现也相对简单：
通过维护一个单位时间内的计数值，每当一个请求通过时，就将计数值加1，当计数值超过预先设定的阈值时，就拒绝单位时间内的其他请求。如果单位时间已经结束，则将计数器清零，开启下一轮的计数。
临界值问题
但是固定时间窗口算法会存在一个问题，举个例子:
假设设定1s内允许通过的请求阈值是100，如果在时间窗口的最后几毫秒发送了99个请求，紧接着又在下一个时间窗口开始时发送了99个请求，这样显然在一秒超过了阈值。如下图
但又因为时间窗口原因，这99个请求不会被限流，就可能会对系统造成影响。
这就是临界值问题，那么临界值问题要怎么解决呢？
很简单：当请求来临时，往前推1s的时间范围内，如请求数超过100，就进行限流。
于是就有了滑动时间窗口算法。
滑动时间窗口算法
原理
滑动时间窗口算法是这样的：将一个大的时间窗口分割成多个小的时间窗口，当请求到达当前的时间窗口时，聚合前面的时间窗口的计数值是否超过设定的阈值。
假设设定1秒内允许通过的请求是200个，这里把1秒的时间分成多格，假设分成5格（格数越多，流量过渡越平滑），每格窗口的时间大小是200毫秒，每过200毫秒，就将窗口向前移动一格。通过观察下图，可以得知在当前窗口只要超过110就会被限流。
代码实现
代码实现要关注几个点：
-
要存储每个小窗口的计数值。 -
超出时间范围的窗口要被移除，同时添加新的窗口。
这里我用了 LinkedList 作为分割窗口，可以快速的实现功能。
临界值问题
那么滑动窗口限流法是完美的吗？细心观察应该能马上发现问题，如下图：
没错，滑动时间窗口限流法依然存在临界值的问题。流量的过渡是否平滑依赖于我们设置的窗口格数，格数越多，统计越精确。但是具体要分多少格呢？
于是乎，就有了漏桶算法。
漏桶算法
原理
漏桶算法就是一个拥有固定容量的容器，用以承载流量。
当流量超出桶的容量时，多余的流量就会被丢弃，确保不会过载。而在桶内的流量，则以恒定的速率平稳流出，从而实现了对流量访问的平滑控制。
代码实现
在进行漏桶算法实现时，要关注几个点：
-
需要一个容器作为漏桶。 -
以固定速率对容器进行移除。
这里我用了 ArrayBlockingQueue 作为漏桶，可以快速的实现功能。
不支持突发流量
因为漏桶算法的流出速率是固定的，所以漏桶算法不支持突发流量。但是在实际情况下，流量往往是突发的。
那如何改进呢？
于是乎，就有了令牌桶算法。
令牌桶算法
原理
令牌桶算法是如何支持突发流量的呢？
与漏桶算法不同，令牌桶的漏桶中存放的是令牌而不是流量。
最开始，令牌桶是空的，我们以恒定速率往令牌桶里加入令牌，当桶被装满时，多余的令牌会被丢弃。
当请求到来时，会从令牌桶获取令牌，获取成功则请求被放行，获取失败则阻塞或拒绝请求。那么当突发流量来临时，只要令牌桶有足够的令牌，就不会被限流。
代码实现
令牌桶算法的实现与漏桶算法类似
限流算法应用场景
无论哪个限流算法，都有各自的适用场景和优缺点，具体选择哪种算法需要根据实际的业务需求和系统环境进行考虑。
例如，对于需要平滑处理流量的场景，可以选择滑动窗口算法或漏桶算法。而对于需要应对突发大流量的场景，令牌桶算法可能更合适。
总结
在工作中，我们可能会使用现成的限流组件，如Spring Cloud的Hystrix、Spring Cloud Alibaba的Sentinel，或者是Google的Guava限流器。
但是，无论哪个组件，背后的实现原理都离不开这四种限流算法。作为开发人员，我们不仅要会用这些工具，还要做到知其然，知其所以然。
原文始发于微信公众号（Hi程序员）：就这么几个限流算法，总是记了又忘。。。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/282527.html
