限流算法：漏桶算法和令牌桶算法

0. 限流的目的

限流的目的是通过对并发访问/请求进行限速或者一个时间窗口内的的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务（定向到错误页或告知资源没有了）排队或等待（比如秒杀、评论、下单）、降级（返回兜底数据或默认数据）。简单讲，就是通过限流，防止流量过载，造成系统崩溃不可用，起到系统“保险丝”的作用。

1. 漏桶算法

1.1 简述

漏桶算法：水（请求）先进入到漏桶里，漏桶以一定的速度出水（处理请求），当流出速度远远小于流入速度时，达到桶的容量（桶满了），就会溢出桶（放弃的请求）。 可以看出漏桶算法能强行限制数据的传输速率。

漏桶算法

流程：

1. 当请求来了的时候，将请求放入到桶中

2. 恒定的速度，消费同种的请求

3. 桶满的状态下，就丢弃请求

2. 令牌桶算法

令牌桶算法：会以一个恒定的速率向桶里放入令牌，如果有新的请求进来希望进行处理，则必须要先从桶内拿到一个可用的令牌，才能继续被处理。若桶内无令牌可取时，则拒绝请求/排队等待。

令牌捅算法

过程：

1. 系统以恒定的速度产生令牌，然后将令牌放入令牌桶中

2. 零牌桶有一个容量，当令牌同满了的时候，再向其中放入的令牌就会丢弃

3. 每次一个请求过来，需要从令牌桶中获取一个令牌，令牌获取成功，则处理请求，提供服务；没有令牌，拒绝提供服务

3. 两种算法的对比

在漏桶算法中，总量控制，桶容量的大小设置是关键，即不能设置过大，服务不可能了桶还没满，或是服务还有很大的冗余，桶已经满了，这两种情况下，桶的意义就已经不存在了。而且动态调整桶的容量比较困难，也无法精确控制流的速度，突发流量时，可能丢弃的请求数量较多。

在令牌桶的算法中，令牌的产生速度是一个关键因素，可以控制令牌的产生速度，从而控制请求的处理速度。相对于对于漏桶算法，实现相对复杂。

在某些情况下，漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的，所以即使网络中没有发生拥塞，漏桶算法也不能使某一个单独的数据流达到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。

看一个实际场景，为什么令牌桶算法可以防止一定程度的突发流量呢？可以这么理解，假设我们想要的速率是2000Qps，那么往桶中放令牌的速度就是2000个/s，桶的容量为2000。假设第1秒只有1800个请求，那么意味着第2秒可以容许2200个请求，这就是一定程度突发流量的意思，反之我们看漏桶算法，第1秒只要1800个请求，那么全部放过，第2秒这2200个请求将会被打回200个。

4. 总结：

如果要让自己的系统不被流量打垮，使用令牌桶。如果要保证别人的系统不被打垮，用漏桶算法。