限流中的漏桶和令牌桶算法理论剖析

在前文 《限流熔断是什么，怎么做，不做行不行？》中针对 “限流” 动作，有提到流量控制其内部对应着两种常用的限流算法。

其分别对应漏桶算法和令牌桶算法。因此会有的读者会好奇，这都是些啥？

为了更进一步的了解 WHY，本文来快速探索一下，看看限流下的一些 “算法” 们到底有何作用，是为何成为流量控制的基石的？

前言

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

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

现实场景

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

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

漏桶算法（Leaky Bucket）

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

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

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

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

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 容量限制的水的可能性，此时也可能会出现波峰。

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

令牌桶算法

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

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

1. 每 1/r 秒新增一个 token 到 buckets 中。

2. buckets 中最多可容纳 b 个令牌。如果桶已满，将丢弃这个新增的 token（也就是不需要新的 token）。

3. 当主机传输 n bytes packets 時，buckets 中如果有 n 个令牌，则取到所需令牌，成功传输 n bytes。

4. 当可用的 token 小于 n bytes 时，不会从 buckets 中取到任何 token，本次请求将被拒绝/排队等待。

漏桶 vs 令牌桶

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

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

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

总结

在软件系统中，限流常常所代表的就是流量整形、速率限制，是一个非常常见的调控手段。一般我们会将其在初期集成到统一框架、网关、Mesh 中去。因此建议接触业务的同学，都要对这一块进行考量，便于后续的快速使用/接入，毕竟业务的流量爆发总是来的比较突然，甚至可能是恶意攻击。

而本文所提到的漏桶，令牌桶都是非常常见的手段，虽然两者独立出来分析了。但从软件开发的角度来讲，你认为两者是否可以融合，结合其优势呢？