微服务系统架构设计系列 - RateLimiter - 1. 限流器简介与一般算法

Key TakeAways

限流器是一种防御性的编程实现方式，防止一个大型的分布式系统在不可预知的大流量到来的时候导致系统大规模故障。

限流器可以设置在服务端，主要为了限制资源的使用。放在客户端主要考虑调用压力更加均匀。

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

什么是限流器？

限流器是一种限制某种操作在一定时间内的执行次数（例如每秒钟5次）或者执行量（例如每秒钟1G大小的数据）的机制。

哪里会用到限流器？

限流器是一种防御性的编程实现方式，在大数据量高并发访问时，经常会出现服务或接口面对暴涨的请求而不可用的情况，甚至引发连锁反映导致整个系统崩溃。此时你需要使用的技术手段之一就是限流，当请求达到一定的并发数或速率，就进行等待、排队、降级、拒绝服务等。

在一个大型的分布式系统，系统设计要考虑很多很多方面：

1. 系统动态扩容缩容，总会有滞后性。业务总会有高峰有低谷。集群大小不会一直按照高峰的时候的规模运行，这样成本太高了，一般会有动态扩容策略。但是这种动态扩容，一般是有滞后性的，不能保证瞬时高流量处理的很好。通过限流器，保证某个业务流量到来时，不会以为这个业务导致其他业务也无法正常工作。
2. 级联故障（cascading failure）：分布式系统一般会有健康检查，也一般会有断路降级机制，流量高峰到来的时候，当某个节点过载，导致这个节点健康检查失败下线，或者断路器打开，导致这个节点的流量打入了其他节点导致其他节点也过载。
3. 对于一个公共服务，不同租户或者不同用户都需要限流防止某个用户将所有的资源都抢光。
4. 流控：为了防止某一个节点负载特别高，但是其他节点负载较低。除了通过负载均衡控制外，还需要限流器保证某个节点不会压力过高。

举一个简单的例子：假设一个商城，有下单和查看自己的订单这两个业务。限量秒杀的时候，用户下单量在某一时候突然飚高。系统目前容量可能不够承担这么大的并发下单量，导致请求阻塞，排队，并进而导致所有的资源都被下单请求吃掉，用户查看自己订单的请求也无法执行或者很慢。同时，用户请求刷不出来就会不断地刷，导致进一步请求堆积。

限流器的相关策略设计

如果完全不采用限流器，一般需要通过设置适当的请求超时，尽量小的同步等待队列和合适的断路策略，来防止过载。但是，这种方式并不能避免上面说的4个问题。

在目前的微服务体系中，一般一个进程既是服务提供方，又是服务调用方。在服务网格下更是如此。对于服务提供方，限流主要是控制外部流量防止压力过大。对于服务调用的时候限流，主要是考虑压力均匀（虽然服务调用一般有负载均衡算法，但是一般的负载均衡算法没法保证真正的负载完全均衡，客户端限流器可以进一步帮助防止压力全部打到了某一个实例）。

对于服务端限流，当触发限流的时候，服务端一般会拒绝请求，并且可能返回 429 这个 HTTP 状态码。客户端是这个请求直接异常，还是缓存起来之后继续重试，取决于客户端的策略。

限流器相关算法

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

1. 令牌桶（Token bucket）

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

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

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

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

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

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

2. 漏斗桶（Leaky bucket）

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

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

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

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

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

固定时间窗口比较简单，就是将时间切分成若干个时间片，每个时间片内固定处理若干个请求。这种实现不是非常严谨，但是由于实现简单，适用于一些要求不严格的场景。

算法大概是： 假设n秒内最多处理b个请求，那么每隔n秒将计数器重置为b。请求到来时，如果计数器值足够，则扣除并请求通过，不够则触发拒绝策略。

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

4. 滑动日志（Sliding Log）

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

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

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

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

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

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

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