服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - 编程技术 - 分布式系统中的限流器实现算法

分布式系统中的限流器实现算法

2021-05-17 23:45掘金干货满满张哈希 编程技术

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

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

令牌桶(Token bucket)

 

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

分布式系统中的限流器实现算法

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

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

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

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

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

漏斗桶(Leaky bucket)

 

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

分布式系统中的限流器实现算法

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

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

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

固定时间窗口(Fixed window)

 

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

分布式系统中的限流器实现算法

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

滑动日志(Sliding Log)

 

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

分布式系统中的限流器实现算法

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

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

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

滑动窗口(滑动日志 + 固定窗口)

 

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

分布式系统中的限流器实现算法

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

分布式系统中的限流器实现算法

原文地址:https://juejin.cn/post/6924084069462441991

延伸 · 阅读

精彩推荐