带你快速了解：限流中的漏桶和令牌桶算法

本文转载自微信公众号「脑子进煎鱼了」，作者陈煎鱼 。转载本文请联系脑子进煎鱼了公众号。   

前言

理论上每一个对外/内提供功能的资源点，都需要进行一定的流量控制，否则在业务的持续迭代中，是有可能出现突发性流量的场景(就像年初所带来的一些行业突发转变，导致业务流量突然暴增)：

突发流量

若没有进行限流，就会出现一些奇奇怪怪的问题点，实则就是系统无法承受这波流量，逐渐崩溃，走向系统假死。

现实场景

最常见的现实场景就是日常随处可见的排插、插座，其内置的保险丝，也被称为电流保险丝，其主要是起过载保护作用，保险丝会在电流异常升高到一定的高度和热度的时候，自身熔断切断电流，从而起到保护电路安全运行的作用。

因此真实世界中有许多与软件工程中的限流熔断的场景有异曲同工之处，也是为了控制量，超量就切断。你也可以想想现实生活中是否有遇到其他类似的例子呢?

保险丝(图来自网络)

漏桶算法(Leaky Bucket)

漏桶算法(Leaky Bucket)是网络中流量整形(Traffic Shaping)或速率限制(Rate Limiting)时常用的一种算法，它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。

漏桶算法通过其算法调控了流量访问，使得突发流量可以被整形，去毛刺，变成一个相对缓和，以便为网络提供一个稳定的流量。

漏桶算法的存储桶主要由三个参数定义，分别是：桶的容量、水从桶中流出的速率、桶的初始充满度。

其核心理念就如字面意思：一个会漏水的桶。

图片来自 geeksforgeeks

Bursty Flow

在上图中，水龙头代表着突发流量(Bursty Flow)。当网络中存在突发流量，且无任何调控时，就会出现像 Bursty Data 处类似的场景。主机以 12 Mbps 的速率发送数据，时间持续 2s，总计 24 Mbits 数据。随后主机暂停发送 5s，然后再以 2 Mbps 的速率发送数据 3s，最终总共发送了 6 Mbits 的数据。

因此主机在 10s 内总共发送了 30 Mbits 的数据。但这里存在一个问题，就是数据的发送并不是平滑的，存在一个较大的波峰。若所有流量都是如此的传输方式，将会 “旱的旱死涝的涝死”，对系统并不是特别的友好。

Fixed Flow

为了解决 Bursty Flow 场景的问题。漏桶(Leaky Bucket)出现了，漏桶具有固定的流出速率、固定的容量大小。

在上图中，漏桶在相同的 10s 内以 3 Mbps 的速率持续发送数据来平滑流量。若水(流量)来的过猛，但水流(漏水)不够快时，其最终结果就是导致水直接溢出，呈现出来就是拒绝请求/排队等待的表现。另外当 Buckets 空时，是会出现一次性倒入达到 Bucket 容量限制的水的可能性，此时也可能会出现波峰。

简单来讲就是，一个漏桶，水流进来，但漏桶只有固定的流速来流出水，若容量满即拒绝，否则将持续保持流量流出。

令牌桶算法

令牌桶算法也是网络中流量整形或速率限制时常用的一种算法，它的主要目的是控制发送到网络上的数据的数目，并允许突发数据的发送。

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

图片来自 gateoverflow

1. 每 1/r 秒新增一个 token 到 buckets 中。
2. buckets 中最多可容纳 b 个令牌。如果桶已满，将丢弃这个新增的 token(也就是不需要新的 token)。
3. 当主机传输 n bytes packets r，buckets 中如果有 n 个令牌，则取到所需令牌，成功传输 n bytes。
4. 当可用的 token 小于 n bytes 时，不会从 buckets 中取到任何 token，本次请求将被拒绝/排队等待。

漏桶 vs 令牌桶

漏桶算法和令牌桶算法本质上都是为了做流量整形(Traffic Shaping)或速率限制(Rate Limiting)，避免系统因为大流量而被打崩，但两者核心差异在于限流的方向是相反的。

令牌桶限制的是流量的平均流入速率，并且允许一定程度的突然性流量，最大速率为桶的容量和生成 token 的速率。而漏桶限制的是流量的流出速率，是相对固定的。

因此也会相对的带来一个问题，在某些场景中，漏桶算法并不能有效的使用网络资源，因为漏桶的漏出速率是相对固定的，所以在网络情况比较好，没有拥塞的状态下，漏桶依然是限制住的，并没有办法放开量。而令牌桶算法则不同，其能够是限制平均速率的同时支持一定程度的突发流量。

总结