令牌桶算法和漏桶算法之间的那些事

令牌桶算法和漏桶算法之间的那些事

引用

CSDN

1.

https://blog.csdn.net/ver_mouth__/article/details/126123340

目录
一：限流
二：令牌桶算法
三：漏桶算法
四：令牌桶和漏桶区别
4.1按照不同的速率
4.2限制的对象不同
4.3主要区别

一：限流

在了解令牌桶算法和漏桶算法之前，我们先大致了解一下限流。限流是对某一时间窗口内的请求数进行限制，保持系统的可用性和稳定性，防止因流量暴增而导致的系统运行缓慢或宕机。常用的限流算法有令牌桶和漏桶，而Google开源项目Guava中的RateLimiter使用的就是令牌桶控制算法。

在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流。

• 缓存： 缓存的目的是提升系统访问速度和增大系统处理容量。
• 降级： 降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略的降级，以此释放服务器资源以保证核心任务的正常运行。
• 限流： 限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理。

二：令牌桶算法

令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

工作过程：

1. key是否存在。因为流程图是基于分布式缓存做的集群限流，需要根据不同key做统计，第一次访问初始化key。
2. 如果key不存在，初始化令牌桶，防止初始令牌数量，并且设置key过期时间为interval2。这里的初始令牌数量一般可以设置成限流阈值，比如限流10qps，初始值可以设置成10，来应对一开始的流量。interval是间隔时间，比如限流阈值10qps，interval设置为1s。过期时间是缓存中key的时间，interval2是为了防止key过期无法拦截流量。
3. 如果key存在，将当前请求时间和当前key的最后放置令牌时间做比较。如果间隔超过interval，进入第4步，间隔未超过interval，进入第5步。
4. 间隔已经超过1s，直接放置令牌到最大数量。
5. 间隔没有超过1s，定义delta为时间差，放置令牌数=delta/(1/qps)。放入令牌时保证令牌数不超过桶的容量。同时，重置放入令牌的时间。
6. 从桶中获取令牌，获取令牌成功，执行请求；获取令牌时间，拒绝请求。

三：漏桶算法

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

漏桶可以看作是一个带有常量服务时间的单服务器队列，如果漏桶（包缓存）溢出，那么数据包会被丢弃。 在网络中，漏桶算法可以控制端口的流量输出速率，平滑网络上的突发流量，实现流量整形，从而为网络提供一个稳定的流量。

漏桶算法思路很简单，请求先进入到漏桶里，漏桶以固定的速度出水，也就是处理请求，当水加的过快，则会直接溢出，也就是拒绝请求，可以看出漏桶算法能强行限制数据的传输速率。

从原理上看，令牌桶算法和漏桶算法是相反的，一个“进水”，一个是“漏水”。

工作过程：

1. 一个固定容量的漏桶，按照常量固定速率流出水滴；
2. 如果桶是空的，则不需流出水滴；
3. 可以以任意速率流入水滴到漏桶；
4. 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

四：令牌桶和漏桶区别

4.1按照不同的速率

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

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

4.2限制的对象不同

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

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

4.3主要区别

这两种算法的主要区别在于“漏桶算法”能够强行限制数据的传输速率，而“令牌桶算法”在能够限制数据的平均传输数据外，还允许某种程度的突发传输。在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的门限，因此它适合于具有突发特性的流量。

需要注意的是，因为漏桶算法不支持突发特性的流量，主要目的为平滑流入速率，而令牌痛可以支持一定的突发流量，其限制的实际上为平均速率。根据实际的流量特性，选择不同算法，通常，漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制。