限流器相关算法
一般限流器有五种算法，分别是：令牌桶，漏斗桶，固定窗口，滑动日志（指的其实是广义上的滑动窗口），滑动窗口（这里指的是滑动日志+固定窗口结合的一种算法）。
1. 令牌桶（Token bucket）
令牌桶算法用来控制一段时间内发送到网络上的数据的数目，并允许突发数据的发送。
算法大概是： 假设允许的请求速率为r次每秒，那么每过1/r秒就会向桶里面添加一个令牌。桶的最大大小是b。当一个大小为n的请求到来时，检查桶内令牌数是否足够，如果足够，令牌数减少n，请求通过。不够的话就会触发拒绝策略。
令牌桶有一个固定大小，假设每一个请求也有一个大小，当要检查请求是否符合定义的限制时，会检查桶，以确定它当时是否包含足够的令牌。如果有，那么会移除掉这些令牌，请求通过。否则，会采取其他操作，一般是拒绝。令牌桶中的令牌会以一定速率恢复，这个速率就是允许请求的速率（当然，根据大小的配置，可能实际会超过这个速率，但是随着令牌桶的消耗会被调整回这个恢复速率）。
如果令牌不被消耗，或者被消耗的速度小于产生的速度，令牌就会不断地增多，直到把桶填满。可以看出，令牌桶在保持整体上的请求速率的同时，允许某种程度的突发传输。
分布式环境下的令牌桶的实现需要考虑如下几个问题：
- 令牌桶当前大小究竟如何存储？是只存储一个当前令牌桶的大小（例如通过 redis 的一个键值对存储），还是存放每个通过的请求到来的时间戳（例如通过 redis 的 zset 实现，zset 的大小就是桶的最大大小）？
- 令牌桶的令牌补充是由谁补充？对于存储一个当前令牌桶的大小的实现方式，需要一个进程以速率
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秒前的所有请求，查看集合是否满了，如果没满，则通过请求，并放入集合，如果满了就触发拒绝策略。
分布式环境下的滑动日志的实现需要考虑如下几个问题：
- 我们的算法其实已经简化了存储，但是对于高并发的场景，要缓存的请求可能会很多（例如限制每秒十万的请求，那么这个缓存的大小是否就应该能存储十万个请求？），这个缓存应该如何实现？
- 高并发场景下，对于这个集合的删除掉
n秒前的所有请求的这个操作，需要速度非常快。如果你的缓存集合实现对于按照时间戳删除这个操作比较慢，可以缓存多一点请求，定时清理删除n秒前的所有请求而不是每次请求到来都删除。请求到来的时候，查看b个之前的请求是否存在并且时间差小于n秒，存在并且小于代表应该触发限流策略。
5. 滑动窗口（滑动日志 + 固定窗口）
前面的滑动日志，我们提到了一个问题 – 要缓存的请求可能会很多。也许在我们的架构内不能使用一个恰当的缓存来实现，我们可以通过滑动窗口这个方法来减少要存储的请求数量，并减少集合大小减少同一个集合上面的并发。
算法大概是： 假设n秒内最多处理b个请求。我们可以将n秒切分成每个大小为m毫秒得时间片，只有最新的时间片内缓存请求和时间戳，之前的时间片内只保留一个请求量的数字。这样可以大大优化存储，小幅度增加计算量。对于临界条件，就是之前已经有了n/m个时间片，计算n秒内请求量时可以计算当前时间片内经过时间的百分比，假设是 25%，那么就取开头的第一个时间片的请求量的 75% 进行计算。
每日一刷，轻松提升技术，斩获各种offer：
