漏桶算法和令牌桶算法

https://dbwu.tech/posts/golang_ratelimit/

概述

限流的目的 是通过对并发请求进行限速来保护系统，请求一旦达到限制速率，就可以选择性地拒绝服务，例如下面的几种方案:

提示用户系统繁忙，请稍后重试

提示用户进入排队等待

跳转到指定页面

….

漏桶 算法和 令牌桶 算法是 接口限流设计 中常用的两种算法，本文通过两个常用的开源组件，研究下两者的区别和具体代码实现。

漏桶

漏桶 算法将 服务的请求量限额 比喻为一个一直装满水的桶，每隔固定时间向外漏 N 滴水。如果请求方接到了这滴水，就可以继续请求服务，如果没有接到，就需要等待下一滴水。也就是说，不管请求量有多少，单位时间内请求额度 (漏水流出的容量) 是固定的。

算法实现

笔者选择的组件是由 Uber 开源的 uber-go/ratelimit 作为研究 漏桶 算法代码实现，版本为 v0.2.0。

示例代码

接口

Limiter 用来进行限流，可能存在多个 goroutine 并发的情况。

Clock 通过时间来计算请求速率限制 (内部实现是在标准库的 time 包上面封装了一层，便于在测试中 Mock)。

两种实现

对于 Limiter 接口，ratelimit 组件的内部通过实现了两种方案，分别基于 互斥锁 和基于 atomic (无锁编程)，本文主要基于 互斥锁 方案的代码进行分析，对 无锁 方案感兴趣的读者可以自行阅读源代码，如果对 无锁 概念比较模糊，建议阅读扩展列表的文章。

除此之外，还有一个表示不限流的 unlimited 也实现了 Limiter 接口。

限流器配置对象

限流器对象

newMutexBased 通过 FUNCTIONAL OPTIONS 模式创建一个 限流器。

实现 Limiter 接口

Take 方法可能会在并发调用时阻塞，保证每个请求的时间片均为 config.per / rate (也就是 perRequst)。

小结

漏桶 的不足之处在于其速率限制是固定的，即使请求容量允许的情况下，仍然无法处理流量突增的场景。例如 漏桶 请求容量为 10W, 速率限制为 1W，某一个时刻流量突增，有 10W 个用户请求，但是只能有 1W 用户正常请求，剩余用户只能等待，此时就需要 令牌桶 算法来解决。

令牌桶

令牌桶 算法定期向桶中添加令牌，令牌的数目可以按照需要消耗的资源进行相应的调整，请求服务时需要从桶中获取令牌，如果获取到令牌，可以正常访问，如果没有获取到令牌，可以选择等待，或者放弃。

算法实现

笔者选择的组件是 juju/ratelimit 作为研究 令牌桶 算法代码实现，版本为 v1.0.2。

示例代码

运行代码

从代码的输出结果中可以看到，初始化时 令牌桶 的容量为 10，取走 5 个令牌之后，可用的剩下 5 个，然后程序休眠 3 秒，因为每秒放入一个令牌，所以最终 令牌桶 的可用令牌数量为 8 个。

接口

Clock 通过时间来计算请求速率限制。

realClock 内部实现是在标准库的 time 包上面封装了一层。

令牌桶对象

创建令牌桶

创建新的 令牌桶 时，会初始化 startTime 字段为当前时间，latestTick 时间片为 0, availableTokens 字段和 capacity 字段一致。

获取令牌桶容量

因为 令牌桶 的容量在创建时就初始化完成且不可修改，所以直接返回 capacity 字段即可。

获取令牌桶添加速率

Rate 方法返回 每秒 向 令牌桶 添加令牌的个数，计算时会将秒转换为纳秒单位。

currentTick 方法返回从 令牌桶 开始计时到当前的时间片。

获取桶内可用令牌数量

Available 方法返回 令牌桶 内可用的的令牌个数，因为存在并发的情况，所以 函数返回值不可作为调用获取令牌方法时的参数。

获取令牌

TakeAvailable 方法从 令牌桶 内获取指定数量的令牌 (无阻塞)，返回获取到的令牌数量，如果返回 0, 说明没有可用的令牌。

takeAvailable 方法是获取令牌的具体实现，新增了一个便于测试的 time.Time 参数。

adjustavailableTokens 方法根据时间片调整桶内可用令牌数量。

小结

通过对源代码的实现分析，可以看到 juju/ratelimit 的功能实现非常简洁，最重要的是，没有使用额外的 goroutine 去完成 定期向桶内添加令牌 这个操作，而是在获取时去实时计算，简化了内部实现逻辑的同时，非常便于扩展和测试。

总结

本文通过对两个高质量 (Github starts > 2500) 的开源组件的源代码进行分析，认识并理解了 漏桶 和 令牌桶 的差别以及具体实现。 从算法的实现角度来讲，两个算法的核心都基于 时间片，漏桶 算法中的 时间片 作为单个请求的时间间隔，而 令牌桶 算法中的 时间片 作为定期向桶内添加令牌的时间基准。

漏桶 算法和 令牌桶 算法看起来很像，不过还是有一定区别。漏桶 流出的速率固定，而 令牌桶 只要在桶中有令牌，那就可以获取并请求服务。也就是说，令牌桶 允许一定程度的并发超过其速率限制，例如某一个时刻流量突增，有 10W 个用户请求，只要令牌桶中有 10W 个令牌，那么这 10W 个请求全都会放过去，但是 漏桶 不能超过其速率限制。令牌桶 在桶中没有令牌的情况下会退化为 漏桶 算法 (只能定期添加，速率变成了固定的)。