限流的方式-几种限流算法的介绍与对比

简述

java限流大体可以分为3个方面。

• 合法性
  • 验证码
  • 黑名单
• 容器限流
  • tomcat
  • nginx
• 算法限流
  • 固定时间窗口算法
  • 滑动时间窗口算法
  • 漏桶算法
  • 令牌桶算法

算法限流

固定时间窗口

这是限流算法中最简单也是最暴力的一种朴素算法。既然我们的目标是让APP在一分钟内只能被调用N次。那么我们便可以统计这一分钟内接口被调用的次数，一旦调用的次数超过我们设置的阈值，则拒绝提供服务。这种算法的优势是逻辑容易理解，实现也很容易。劣势则是由于时间窗口是固定的，可能在某些时间段服务器会承受超过设定阈值的请求。

如图所示，比如我们设置一分钟只能提供100次访问服务，如果某个应用在某一分钟后半部访问了100次，在下一分钟前半步访问了100次，看似符合窗口限制条件，实际上，服务器在0 :30~1:30这个时间区间上提供了200次服务（已经超出了服务器的设置的阈值）。并且，这个用户在瞬间耗光了两个时间窗口区间的服务定额，导致其他用户均不能访问了，这在业务上也是不能接受的。

滑动时间窗口算法

滑动时间窗口算法可以认为是对固定时间窗口的改进。也可被称为精度不够，时间来凑。

如图所示，将一分钟分为10个更加小的时间区间，每个小时间区间都有其自己的计数器，对其自身小时间区间进行控制。除此以外，若干个小时间区间组成一个时间窗口，并且随着时间的推移，时间窗口也随之右移。每个一段时间删除最左端的小区间，在最右端添加小区间，对整个时间窗口的总流量也进行控制。如果恶意用户分时间窗口进行大量请求，也能被检测出来。最后，我们也可以得出结论，时间区块分配的越精细，流量控制也会随之更加精细。

dubbo有使用

漏桶算法

漏桶算法(Leaky Bucket)是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。这是漏桶算法的基本定义。

形象一点的解释的话：

漏桶可以看作是一个队列，将客户端的请求依次放入队列中，服务端以一定的速率从队列中获取请求进行处理，如果某一时刻收到了客户端发起的大量请求，队列放不下了，则丢弃数据包。可以用来平滑网络上的突发流量。有点类似于消息队列的作用。

如图所示，请求好比水流，出水速度好比服务端处理请求的速率，一旦大量水流冲击过来，当桶装不下时水变回溢出，体现为直接拒绝客户端的请求。

令牌桶算法

令牌桶是一种用于分组交换计算机网络和电信网络的算法。它可用于检查数据包形式的数据传输是否符合定义的带宽和突发性限制（流量不均匀或变化的度量）。

其原理就是，以一定的速率将令牌放入池子中，当请求到来时，就从池子中获取令牌，持有令牌才能进行后续的访问，获取不到令牌则直接拒绝访问。

• 当请求的速率等于令牌生成速率时，每一个请求能无延迟的通过令牌池
• 当请求的速率小于令牌生成速率时，每一个请求能无延迟的通过令牌池，并且多余的令牌会在池子中积累起来，供后续的突发流量使用
• 当请求的速率大于令牌生成速率时，当前面请求消耗完池子中的令牌后，后续请求获取不到令牌，不能获得服务

特点总结

• 漏桶能强制以一定的速率消费请求

• 令牌桶既能限制请求的平均速率，也能应对突发流量情况

• 固定时间窗口不能实现高精度的控制