请你讲讲分布式系统中的限流器一般如何实现？

今天药忘吃喽~ 2022-10-25 14:09 12阅读 0赞

### 限流器相关算法 ###

一般限流器有五种算法，分别是：令牌桶，漏斗桶，固定窗口，滑动日志（指的其实是广义上的滑动窗口），滑动窗口（**这里指的是滑动日志+固定窗口结合的一种算法**）。

#### 1. 令牌桶（Token bucket） ####

令牌桶算法用来控制一段时间内发送到网络上的数据的数目，并允许突发数据的发送。

![image][]

**算法大概是：** 假设允许的请求速率为`r`次每秒，那么每过`1/r`秒就会向桶里面添加一个令牌。桶的最大大小是`b`。当一个大小为`n`的请求到来时，检查桶内令牌数是否足够，如果足够，令牌数减少`n`，请求通过。不够的话就会触发拒绝策略。

令牌桶有一个固定大小，假设每一个请求也有一个大小，当要检查请求是否符合定义的限制时，会检查桶，以确定它当时是否包含足够的令牌。如果有，那么会移除掉这些令牌，请求通过。否则，会采取其他操作，一般是拒绝。令牌桶中的令牌会以一定速率恢复，这个速率就是允许请求的速率（当然，根据大小的配置，可能实际会超过这个速率，但是随着令牌桶的消耗会被调整回这个恢复速率）。

如果令牌不被消耗，或者被消耗的速度小于产生的速度，令牌就会不断地增多，直到把桶填满。可以看出，令牌桶在保持整体上的请求速率的同时，允许某种程度的突发传输。

**分布式环境下的令牌桶的实现需要考虑如下几个问题：**

1.  令牌桶当前大小究竟如何存储？是只存储一个当前令牌桶的大小（例如通过 redis 的一个键值对存储），还是存放每个通过的请求到来的时间戳（例如通过 redis 的 zset 实现，zset 的大小就是桶的最大大小）？
2.  令牌桶的令牌补充是由谁补充？对于存储一个当前令牌桶的大小的实现方式，需要一个进程以速率`r`不断地往里面添加令牌，**那么如何在分布式的环境下保证有且只有一个这样的进程，这个进程挂了怎么办**？对于存放每个通过的请求到来的时间戳的这种实现方式实现，**那么怎么控制记录请求的个数，肯定不能每个都记录**，并且**每次怎么通过目前的请求以及时间戳来判断剩余令牌数量**

#### 2. 漏斗桶（Leaky bucket） ####

漏斗桶控制请求必须在最大某个速率被消费，就像一个漏斗一样，入水量可大可小，但是最大速率只能到某一量值，不会像令牌桶一样，会有小的尖峰。

![image][image 1]

**算法大概是：** 主要实现方式是通过一个 FIFO （First in first out）的队列实现，这个队列是一个有界队列，大小为`b`，如果请求堆积满了队列，就会触发丢弃策略。假设允许的请求速率为`r`次每秒，那么这个队列中的请求，就会以这个速率进行消费。

**分布式环境下的漏桶的实现需要考虑如下几个问题：**

\*\*1. 漏桶的队列，怎么存放？\*\*这个队列需要存放每个通过的请求以及对应的消费的时间戳，保证消费的平稳。同时，这个队列最好是无锁队列，因为会有分布式锁征用。并且，这个队列大小应该设置为`b`，并每次有请求到来时，放入队列的同时清理队列。  
\*\*2. 消费如何实现？\*\*也就是存入队列的请求，如何消费呢？可以请求到来时，通过队列中的请求来判断当前这个请求的执行时间应该是多久以后，之后入队列，延迟这么久再执行这个请求。也可以利用本身带延迟时间实现的队列来实现。

#### 3. 固定时间窗口（Fixed window） ####

固定时间窗口比较简单，就是将时间切分成若干个时间片，每个时间片内固定处理若干个请求。这种实现不是非常严谨，但是由于实现简单，适用于一些要求不严格的场景。  
![image][image 2]  
**算法大概是：** 假设`n`秒内最多处理`b`个请求，那么每隔`n`秒将计数器重置为`b`。请求到来时，如果计数器值足够，则扣除并请求通过，不够则触发拒绝策略。

固定时间窗口是最容易实现的算法，但是也是有明显的缺陷：那就是在很多情况下，尤其是请求限流后拒绝策略为排队的情况下，请求都在时间窗口的开头被迅速消耗，剩下的时间不处理任何请求，这是不太可取的。并且，在一些极限情况下，实际上的流量速度可能达到限流的 2 倍。例如限制 1 秒内最多 100 个请求。假设 0.99 秒的时候 100 个请求到了，之后 1.01 秒的时候又有 100 个请求到了，这样的话其实在 0.99 秒 ~ 1.01 秒这一段时间内有 200 个请求，并不是严格意义上的每一秒都只处理 100 个请求。为了能实现严格意义上的请求限流，则有了后面两种算法。

#### 4. 滑动日志（Sliding Log） ####

滑动日志根据缓存之前接受请求对应的时间戳，与当前请求的时间戳进行计算，控制速率。这样可以严格限制请求速率。一般的网上提到的滑动窗口算法也指的是这里的滑动日志（Sliding Log）算法，**但是我们这里的滑动窗口是另一种优化的算法，待会会提到**。

![image][image 3]

**算法大概是：** 假设`n`秒内最多处理`b`个请求。那么会最多缓存 `b` 个通过的请求与对应的时间戳，假设这个缓存集合为`B`。每当有请求到来时，从`B`中删除掉`n`秒前的所有请求，查看集合是否满了，如果没满，则通过请求，并放入集合，如果满了就触发拒绝策略。

**分布式环境下的滑动日志的实现需要考虑如下几个问题：**

1.  我们的算法其实已经简化了存储，但是对于高并发的场景，要缓存的请求可能会很多（例如限制每秒十万的请求，那么这个缓存的大小是否就应该能存储十万个请求？），这个缓存应该如何实现？
2.  高并发场景下，对于这个集合的删除掉`n`秒前的所有请求的这个操作，需要速度非常快。如果你的缓存集合实现对于按照时间戳删除这个操作比较慢，可以缓存多一点请求，定时清理删除`n`秒前的所有请求而不是每次请求到来都删除。请求到来的时候，查看`b`个之前的请求是否存在并且时间差小于`n`秒，存在并且小于代表应该触发限流策略。

#### 5. 滑动窗口（滑动日志 + 固定窗口） ####

前面的滑动日志，我们提到了一个问题 - 要缓存的请求可能会很多。也许在我们的架构内不能使用一个恰当的缓存来实现，我们可以通过滑动窗口这个方法来减少要存储的请求数量，并减少集合大小减少同一个集合上面的并发。

![image][image 4]

**算法大概是：** 假设`n`秒内最多处理`b`个请求。我们可以将`n`秒切分成每个大小为`m`毫秒得时间片，只有最新的时间片内缓存请求和时间戳，之前的时间片内只保留一个请求量的数字。这样可以大大优化存储，小幅度增加计算量。对于临界条件，就是之前已经有了`n/m`个时间片，计算`n`秒内请求量时可以计算当前时间片内经过时间的百分比，假设是 25%，那么就取开头的第一个时间片的请求量的 75% 进行计算。

![image][image 5]

**每日一刷，轻松提升技术，斩获各种offer：**

![image][image 6]

[image]: /images/20221024/d65101fd944f439d8861bb7a161c76a1.png
[image 1]: /images/20221024/a53e1cd8a479471089cbe262ceadcf3e.png
[image 2]: /images/20221024/4fa1aaf73fe64ea189a4c44a1fd58807.png
[image 3]: /images/20221024/f0c63341c00740be9d06eb651bf52469.png
[image 4]: /images/20221024/044bb0312fca4b05af9c76e018b600c1.png
[image 5]: /images/20221024/51c7e753a5964b698f27f43969ed4b7c.png
[image 6]: /images/20221024/36374f8e2a1a41c79b210909912f3143.png