常用 4 种限流算法介绍及比较
点击上方“芋道源码”，选择“设为星标”
管她前浪，还是后浪？
能浪的浪，才是好浪！
每天 10:33 更新文章，每天掉亿点点头发...
源码精品专栏
- 原创 | Java 2021 超神之路，很肝~
- 中文详细注释的开源项目
- RPC 框架 Dubbo 源码解析
- 网络应用框架 Netty 源码解析
- 消息中间件 RocketMQ 源码解析
- 数据库中间件 Sharding-JDBC 和 MyCAT 源码解析
- 作业调度中间件 Elastic-Job 源码解析
- 分布式事务中间件 TCC-Transaction 源码解析
- Eureka 和 Hystrix 源码解析
- Java 并发源码
来源：blog.csdn.net/weixin_41846320/
01、计数器（固定窗口）算法
计数器算法是使用计数器在周期内累加访问次数，当达到设定的限流值时，触发限流策略。下一个周期开始时，进行清零，重新计数。
此算法在单机还是分布式环境下实现都非常简单，使用redis的incr原子自增性和线程安全即可轻松实现。
这个算法通常用于QPS限流和统计总访问量，对于秒级以上的时间周期来说，会存在一个非常严重的问题，那就是临界问题，如下图：
假设1min内服务器的负载能力为100，因此一个周期的访问量限制在100，然而在第一个周期的最后5秒和下一个周期的开始5秒时间段内，分别涌入100的访问量，虽然没有超过每个周期的限制量，但是整体上10秒内已达到200的访问量，已远远超过服务器的负载能力，由此可见，计数器算法方式限流对于周期比较长的限流，存在很大的弊端。
基于 Spring Boot + MyBatis Plus + Vue & Element 实现的后台管理系统 + 用户小程序，支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能。 项目地址：https://github.com/YunaiV/ruoyi-vue-pro
02、滑动窗口算法
滑动窗口算法是将时间周期分为N个小周期，分别记录每个小周期内访问次数，并且根据时间滑动删除过期的小周期。
如下图，假设时间周期为1min，将1min再分为2个小周期，统计每个小周期的访问数量，则可以看到，第一个时间周期内，访问数量为75，第二个时间周期内，访问数量为100，超过100的访问则被限流掉了
由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。
此算法可以很好的解决固定窗口算法的临界问题。
基于微服务的思想，构建在 B2C 电商场景下的项目实战。核心技术栈，是 Spring Boot + Dubbo 。未来，会重构成 Spring Cloud Alibaba 。 项目地址：https://github.com/YunaiV/onemall
03、漏桶算法
漏桶算法是访问请求到达时直接放入漏桶，如当前容量已达到上限（限流值），则进行丢弃（触发限流策略）。漏桶以固定的速率进行释放访问请求（即请求通过），直到漏桶为空。
04、令牌桶算法
令牌桶算法是程序以r（r=时间周期/限流值）的速度向令牌桶中增加令牌，直到令牌桶满，请求到达时向令牌桶请求令牌，如获取到令牌则通过请求，否则触发限流策略
05、各个算法比较
算法 | 确定参数 | 空间复杂度 | 时间复杂度 | 限制突发流量 | 平滑限流 | 分布式环境下实现难度 |
|---|---|---|---|---|---|---|
固定窗口 | 计数周期T、周期内最大访问数N | 低O(1)（记录周期内访问次数及周期开始时间） | 低O(1) | 否 | 否 | 低 |
滑动窗口 | 计数周期T、周期内最大访问数N | 高O(N)（记录每个小周期中的访问数量） | 中O(N) | 是 | 相对实现。滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑 | 中 |
漏桶 | 漏桶流出速度r、漏桶容量N | 低O(1)（记录当前漏桶中容量） | 高O(N) | 是 | 是 | 高 |
令牌桶 | 令牌产生速度r、令牌桶容量N | 低O(1)（记录当前令牌桶中令牌数） | 高O(N) | 是 | 是 | 高 |
欢迎加入我的知识星球，一起探讨架构，交流源码。加入方式，长按下方二维码噢：
已在知识星球更新源码解析如下：
最近更新《芋道 SpringBoot 2.X 入门》系列，已经 101 余篇，覆盖了 MyBatis、Redis、MongoDB、ES、分库分表、读写分离、SpringMVC、Webflux、权限、WebSocket、Dubbo、RabbitMQ、RocketMQ、Kafka、性能测试等等内容。
提供近 3W 行代码的 SpringBoot 示例，以及超 4W 行代码的电商微服务项目。
获取方式：点“在看”，关注公众号并回复 666 领取，更多内容陆续奉上。
文章有帮助的话，在看，转发吧。谢谢支持哟 (*^__^*）