常见限流算法探究

前言

限流，顾名思义就是对请求应用的流量进行限制，对于超过限流阈值的流量进行丢弃，用于保护系统处于一个合理的流量压力之下，不会因为突发的不可预知的大量请求打死。

限流常见的应用场景是秒杀、下单和评论等 突发性 并发问题。

典型的限流算法有漏桶（leaky bucket）算法和令牌桶（token bucket）算法。

漏桶（leaky bucket）算法

漏桶算法

具体算法：

·一个固定容量的漏桶，按照常量固定速率流出水滴；

·如果桶是空的，则不需流出水滴；

·可以以任意速率流入水滴到漏桶；

·如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

令牌桶（Leaky Bucket）算法

令牌桶算法基本思路是按照恒定的速率向桶中放入令牌，每当请求经过时则消耗一个或多个令牌。当桶中的令牌为 0 时，请求则会被阻塞。

令牌桶算法

具体算法：

·假设限制2r/s，则按照500毫秒的固定速率往桶中添加令牌；

·桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝；

·当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上；

·如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）。

备注：令牌桶算法支持先消费后付款，比如一个请求可以获取多个甚至全部的令牌，但是需要后面的请求付费。也就是说后面的请求需要等到桶中的令牌补齐之后才能继续获取。

漏桶算法 VS令牌桶算法

·令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求；

·漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝；

·令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量；

·漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率；

开源限流组件对比

·Hystrix是Netflix的一款开源限流组件，目前已停止开发了，目前官方并没有给出原因。

·resilience4j 是一个比较轻量的熔断降级库，Hystrix官方推荐使用。

·Sentinel是阿里开源的一个包含流量控制、熔断降级、系统负载保护功能的组件。

最后

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

参考

·常用限流方案的设计和实现

·限流熔断技术选型：从Hystrix到Sentinel