一般限流器有五种算法，分别是：tokenbucket，funnelbucket，fixedwindow，slidinglog（广义指滑动窗口），slidingWindow（这里指滑动日志+固定窗口相结合的算法）。令牌桶（Tokenbucket）令牌桶算法用于控制一段时间内向网络发送数据的数量，并允许突发数据的发送。算法大致是：假设允许的请求速率为每秒r次，则每1/r秒向桶中添加一个token。桶的最大尺寸为b。当大小为n的请求到来时，检查桶中的令牌数量是否足够，如果足够，则减少令牌数量n，请求通过。如果不够，就会触发拒绝策略。令牌桶有一个固定的大小，假设每个请求也有一个大小，当需要检查请求是否符合定义的限制时，将检查桶以查看当时是否包含足够的令牌。如果有，则这些令牌将被删除，请求将通过。否则，将采取其他行动，通常是拒绝。令牌桶中的令牌会按照一定的速率回收，也就是允许请求的速率（当然根据size的配置，实际上可能会超过这个速率，但是会随着令牌桶被消耗）。如果令牌没有被消耗，或者消耗的速率低于它们生成的速率，则令牌将继续增加，直到桶满为止。可以看出，令牌桶允许一定程度的突发传输，同时保持整体请求速率。令牌桶在分布式环境下的实现需要考虑以下问题：如何存储当前令牌桶的大小？是只存储当前一个令牌桶的大小（比如通过redis的键值对），还是存储每一个经过的请求到达的时间戳（比如通过redis的zset实现，大小）zset是桶的最大尺寸）？谁来补充令牌桶的令牌？对于存储当前令牌桶大小的实现方式，需要一个进程以r的速率不断地向其添加令牌，那么如何保证在分布式环境中只有一个这样的进程呢？这个进程挂了怎么办？用于存储每次通过的请求到达时间如何控制记录请求的个数，不能每一个都记录，如何通过当前请求和每次时间戳来判断剩余token个数。漏斗桶（Leakybucket）漏斗桶控制请求必须以一定的最大速率消耗，就像漏斗一样，进入的水量可大可小，但最大速率只能达到一定的值，并且会有没有像令牌桶那样的小尖峰。算法大致如下：主要实现方式是通过一个FIFO（Firstinfirstout）队列。这个队列是一个大小为b的有界队列。如果队列已满请求，则触发丢弃策略。假设允许的请求速率是每秒r次，那么这个队列中的请求就会按照这个速率被消费。在分布式环境中实现漏桶需要考虑以下问题：如何存储漏桶的队列？这个队列需要存储每一个通过的请求和对应的消费时间戳，以保证消费的稳定性。同时这个队列最好是无锁队列，因为会有分布式的锁申请。而且，这个队列的大小要设置为b，每次有请求过来，同时放入队列中，同时进行清理。如何实现消费？即如何消费存储在队列中的请求？当请求到来时，可以根据队列中的请求判断当前请求应该执行多长时间，然后进入队列，延迟这么久后执行请求。也可以使用本身带有延迟时间的队列来实现。固定时间窗口（Fixedwindow）固定时间窗口比较简单，就是把时间分成几个时间片，每个时间片固定处理几个请求。这种实现方式不是很严谨，但是由于实现方式简单，适合一些要求不那么严格的场景。算法大致是：假设最多有b个请求在n秒内被处理，那么每n秒将计数器重置为b。当请求到来时，如果计数器值足够，则扣除并通过请求，如果不够，则触发拒绝策略。固定时间窗口是最容易实现的算法，但它也有明显的缺陷：即在很多情况下，尤其是拒绝策略在请求限流后排队时，请求在时间窗口开始时很快被消耗掉，而剩下的下一次没有请求被处理，这是不太可取的。并且，在某些极端情况下，实际流速可能达到极限值的2倍。比如限制1秒内最多100次请求。假设100个请求在0.99秒到达，然后另外100个请求在1.01秒到达。在这种情况下，在0.99秒到1.01秒的时间段内实际上有200个请求，并不是严格意义上的每一秒只处理100个请求。为了实现严格的请求限流，还有后两种算法。滑动日志（SlidingLog）滑动日志是根据缓存之前接受的请求对应的时间戳计算，和当前请求的时间戳来控制速率。这严重限制了请求率。网上说的一般的滑动窗口算法也是指这里的滑动日志（SlidingLog）算法，但是我们这里的滑动窗口是另一种优化的算法，后面会提到。算法大概是：假设n秒内最多处理b个请求。那么至多b个经过的请求，对应的时间戳会被缓存，假设缓存集合为B。每当有请求过来，从B中删除n秒前的所有请求，看集合是否满，如果没有，则将请求放过去将其放入集合中，如果已满则触发拒绝策略。分布式环境下滑动日志的实现需要考虑以下几个问题：我们的算法其实已经简化了存储，但是对于高并发的场景，可能需要缓存的请求很多（比如限制每秒10万个请求，那么这个缓存的大小应该能存储10万个请求吗？），这个缓存应该怎么实现呢？在高并发场景下，对这个集合删除n秒前所有请求的操作需要非常快。如果你的缓存集合实现按照时间戳删除比较慢，你可以缓存更多的请求，定时清理删除n秒前的所有请求，而不是每次有请求来就删除。当请求到达时，检查前b次请求是否存在且时间差小于n秒。如果时间差小于n秒，则触发限流策略。滑动窗口（滑动日志+固定窗口）在滑动日志前面，我们提到了一个问题——可能有很多请求需要缓存。也许在我们的架构中无法使用合适的缓存，我们可以使用滑动窗口的方法来减少要存储的请求数，并减小集合大小以减少同一个集合上的并发。算法大概是：假设n秒内最多处理b个请求。我们可以将n秒分成时间片，每个时间片的大小为m毫秒。只有最新的时间片缓存请求和时间戳，前一个时间片只保留一个请求量。这样可以大大优化存储，稍微增加计算量。对于临界状态，之前有过n/m个时间片。在计算n秒内的请求量时，可以计算出当前时间片中经过的时间百分比。假设是25%，那么在开始的时候取第一个时间片计算请求量的75%。
