单节点限流算法

csdn ty1972，路玄。转载请注明原创出处，谢谢！如果读完觉得有收获的话，欢迎点赞加关注。

在实际项目中，某个功能或一组接口可能曾经遭遇过线上5W+QPS的峰值，或者也会在压测状态下经历过10W+QPS的大流量请求。一个高并发系统中对流量的把控非常重要，当巨大的流量直接请求到某一个服务器上没多久就可能造成接口不可用，不处理的话甚至会造成整个应用不可用。

大流量场景

比如经常会遇到这样的业务场景，作为客户端要向kafka生产数据，而kafka的消费者则在源源不断的消费数据，并将消费的数据全部请求到web服务器，虽说做了负载(如多台web服务器)但业务数据的量也是巨大的，每秒钟可能有上万条数据产生。如果生产者直接生产数据的话极有可能把web服务器拖垮。对此就必须要做限流处理，每秒钟生产一定限额的数据到kafka，这样就能极大程度的保证web的正常运转。

其实不管处理何种场景，本质都是降低流量保证应用的高可用。

大流量场景的处理

缓存：就是让数据尽早进入缓存，离程序近一点，不要大量频繁的访问DB。

低业务降级：如果不是核心链路，那么就把这个服务降级掉。打个比喻，现在的APP都讲究千人千面，拿到数据后，做个性化排序展示，如果在大流量下，这个排序就可以降级掉！

限流：就是想在一定时间内把请求限制在一定范围内，保证系统不被冲垮，同时尽可能提升系统的吞吐量。

注意到，有些时候，缓存和降级是解决不了问题的，比如，电商的双十一，用户的购买，下单等行为，是涉及到大量写操作，而且是核心链路，无法降级的，这个时候，限流就比较重要了。

常用限流算法

计数器算法

滑动窗口算法

漏桶算法

令牌桶算法

Guava RateLimiter

计数器算法

计数器是一种简单的限流算法，用途比较广泛，在接口层面，很多地方使用这种方式限流。在一段时间内，进行计数，与阈值进行比较，次数高于阈值时，不让请求处理业务。到了时间临界点，将计数器清0。计数器算法是规定在一个时间段内，通过计数器的方式限制请求上线(比如1s内，最多只能处理10000个请求)，一旦请求数达到上线，就限制请求，算法如下图:

每到时间点，计数器自动清0，这里需要注意的是，计数器算法通常存在时间临界点的问题。如在13:00秒到13:01秒这段时间内没有用户请求，然后在13:01这一瞬时发出10000个请求，然后在13:02秒这一瞬时又发出了10000个请求。在这个临界点可能会承受同时20000个大量请求，超出系统预期的承受。

滑动窗口算法

由于计数器存在临界点缺陷，后来出现了滑动窗口算法来解决。滑动窗口的意思是把固定时间片，进行划分，并且随着时间的流逝，进行移动，这样就能避开计数器算法的临界点问题。这些固定数量的可以移动的格子，将会自动进行计数判断阀值，因此格子的数量影响着滑动窗口算法的精度。与计数器算法的本质点是没有自动清除计数器的操作，计数器由窗口根据当前情况判断，总之比较复杂，而且设涉及到2个窗口之间的请求数量判断。

漏桶算法

滑动窗口有效避免了时间临界点的问题，但是依然有时间片的概念，而漏桶算法在这方面比滑动窗口而言，更加先进。漏桶算法比较简单，就是将流量放入桶中，漏桶同时也按照一定的速率流出，如果流量过快的话就会溢出(漏桶并不会提高流出速率)。溢出的流量则直接丢弃。

有一个固定的桶，进水的速率是不确定的，但是出水的速率是恒定的，当水满的时候是会溢出的。注意到，漏桶的出水速度是恒定的，那么意味着如果瞬时大流量的话，将有大部分请求被丢弃掉（也就是所谓的溢出）。为了解决这个问题，令牌桶进行了算法改进。

令牌桶算法

令牌桶会以一个恒定的速率向固定容量大小桶中放入令牌，当有流量来时则取走一个或多个令牌。当桶中没有令牌则将当前请求丢弃或阻塞。

相比之下令牌桶可以应对一定的突发流量: 生成令牌的速度是恒定的，而请求去拿令牌是没有速度限制的。这意味，面对瞬时大流量，该算法可以在短时间内请求拿到大量令牌，而且拿令牌的过程并不是消耗很大的事情。（有一点生产令牌，消费令牌的意味）

不论是对于令牌桶拿不到令牌被拒绝，还是漏桶的水满了溢出，都是为了保证大部分流量的正常使用，而牺牲掉了少部分流量，这是合理的，如果因为极少部分流量需要保证的话，那么就可能导致系统达到极限而挂掉，得不偿失。

Guava RateLimiter

Google开源工具包Guava提供了限流工具类RateLimiter，该类基于令牌桶算法实现流量限制，使用十分方便。因此对于令牌桶的代码实现，可以直接使用Guava包中的RateLimiter。Guava不仅仅在集合、缓存、异步回调等方面功能强大，而且还给我们封装好了限流的API！我们只需要告诉RateLimiter系统限制的QPS是多少，那么RateLimiter将以这个速度往桶里面放入令牌，然后请求的时候，通过tryAcquire()方法向RateLimiter获取许可（令牌）。

结束语

上面所说的限流算法，都是针对单节点的，而对于分布式下限流的手段常常需要单节点算法与多种技术相结合，如redis、一些开源中间件等，后期我们再讲分布式的限流内容。