本文转载自：
https://blog.csdn.net/weixin_41846320/article/details/95941361
1
、计数器（固定窗口）算法
计数器算法是使用计数器在周期内累加访问次数，当达到设定的限流值时，触发限流策略。下一个周期开始时，进行清零，重新计数。
此算法在单机还是分布式环境下实现都非常简单，使用redis的incr原子自增性和线程安全即可轻松实现。
这个算法通常用于QPS限流和统计总访问量，对于秒级以上的时间周期来说，会存在一个非常严重的问题，那就是临界问题，如下图：
假设1min内服务器的负载能力为100，因此一个周期的访问量限制在100，然而在第一个周期的最后5秒和下一个周期的开始5秒时间段内，分别涌入100的访问量，虽然没有超过每个周期的限制量，但是整体上10秒内已达到200的访问量，已远远超过服务器的负载能力，由此可见，计数器算法方式限流对于周期比较长的限流，存在很大的弊端。
2
、滑动窗口算法
滑动窗口算法是将时间周期分为N个小周期，分别记录每个小周期内访问次数，并且根据时间滑动删除过期的小周期。
如下图，假设时间周期为1min，将1min再分为2个小周期，统计每个小周期的访问数量，则可以看到，第一个时间周期内，访问数量为75，第二个时间周期内，访问数量为100，超过100的访问则被限流掉了
由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。
此算法可以很好的解决固定窗口算法的临界问题。
3
、漏桶算法
漏桶算法是访问请求到达时直接放入漏桶，如当前容量已达到上限（限流值），则进行丢弃（触发限流策略）。漏桶以固定的速率进行释放访问请求（即请求通过），直到漏桶为空。
4
、令牌桶算法
令牌桶算法是程序以r（r=时间周期/限流值）的速度向令牌桶中增加令牌，直到令牌桶满，请求到达时向令牌桶请求令牌，如获取到令牌则通过请求，否则触发限流策略
各个算法比较
|
算法 |
确定参数 |
空间复杂度 |
时间复杂度 |
限制突发流量 |
平滑限流 |
分布式环境下实现难度 |
|
固定窗口 |
计数周期T、 周期内最大访问数N |
低O(1) （记录周期内访问次数及周期开始时间） |
低O(1) |
否 |
否 |
低 |
|
滑动窗口 |
计数周期T、 周期内最大访问数N |
高O(N) （记录每个小周期中的访问数量） |
中O(N) |
是 |
相对实现。滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑 |
中 |
|
漏桶 |
漏桶流出速度r、漏桶容量N |
低O(1) （记录当前漏桶中容量） |
高O(N) |
是 |
是 |
高 |
|
令牌桶 |
令牌产生速度r、令牌桶容量N |
低O(1) （记录当前令牌桶中令牌数） |
高O(N) |
是 |
是 |
高 |
漏桶算法与令牌桶算法的区别在于
（1）漏桶是设定最大值，从小开始计数，做加法，直到超过最大值，则触发限流；
（2）令牌桶按一定速率生成令牌放入桶中，请求过来时从桶中获取令牌，做减法，如果获取不到令牌则触发限流。