计数限流

最简单的限流算法就是计数限流了,例如系统能同时处理100个请求,保存一个计数器,处理了一个请求,计数器加一,一个请求处理完毕之后计数器减一。

每次请求来的时候看看计数器的值,如果超过阈值便拒绝处理。

非常的简单粗暴,计数器的值要是存内存中就算单机限流算法。存中心存储里,例如 Redis 中,集群机器访问就算分布式限流算法。

优点就是:简单粗暴,单机在 Java 中可用 Atomic 等原子类、分布式就 Redis incr。

缺点就是:假设我们允许的阈值是1万,此时计数器的值为0, 当1万个请求在前1秒内一股脑儿的都涌进来,这突发的流量可是顶不住的。缓缓的增加处理和一下子涌入对于程序来说是不一样的。

固定窗口限流算法

首先维护一个计数器,将单位时间段当做一个窗口,计数器记录这个窗口接收请求的次数。

比如限qps 100/s,那我们通过一个计算器,如果该s内超过100个就不再处理,到达下一秒时,将计数清0,这种方式有多个弊端

  • 一段时间内(不超过时间窗口)系统服务不可用:比如窗口大小为1s,限流大小为100,然后恰好在某个窗口的第1ms来了100个请求,然后第2ms-999ms的请求就都会被拒绝,这段时间用户会感觉系统服务不可用。
  • 窗口切换时可能会产生两倍于阈值流量的请求: 假设限流阀值为5个请求,单位时间窗口是1s,如果我们在单位时间内的前0.8-1s和1-1.2s,分别并发5个请求。虽然都没有超过阀值,但是如果算0.8-1.2s,则并发数高达10,已经超过单位时间1s不超过5阀值的定义啦,通过的请求达到了阈值的两倍。

滑动窗口限流

滑动窗口限流解决固定窗口临界值的问题,可以保证在任意时间窗口内都不会超过阈值。

相对于固定窗口,滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点,因此对内存的占用会比较多。

规则如下,假设时间窗口为 1 秒:

  • 记录每次请求的时间
  • 统计每次请求的时间 至 往前推1秒这个时间窗口内请求数,并且 1 秒前的数据可以删除。
  • 统计的请求数小于阈值就记录这个请求的时间,并允许通过,反之拒绝。

滑动窗口算法就是固定窗口的升级版,但是滑动窗口和固定窗口都无法解决短时间之内集中流量的突击。

漏桶算法

整个算法其实十分简单。首先,我们有一个固定容量的桶,有水流(请求)进来,也有水流(处理请求)出去。对于流进来的水来说,我们无法预计一共有多少水会流进来,也无法预计水流的速度。但是对于流出去的水来说,这个桶可以固定水流出的速率。而且,当桶满了之后,多余的水将会溢出。当使用了漏桶算法,我们可以保证接口会以一个常速速率来处理请求

面对突发请求,服务的处理速度和平时是一样的,这其实不是我们想要的,在面对突发流量我们希望在系统平稳的同时,提升用户体验即能更快的处理请求,而不是和正常流量一样,循规蹈矩的处理

令牌桶算法

令牌以固定的速率添加到令牌桶中,假设限流的速率是 r/ 秒,则令牌每 1/r 秒会添加一个;假设令牌桶的容量是 b ,如果令牌桶已满,则新的令牌会被丢弃;请求能够通过限流器的前提是令牌桶中有令牌。

令牌桶的容量 b 其实是 burst 的简写,意义是限流器允许的最大突发流量。比如 b=10,而且令牌桶中的令牌已满,此时限流器允许 10 个请求同时通过限流器,当然只是突发流量而已,这 10 个请求会带走 10 个令牌,所以后续的流量只能按照速率 r 通过限流器。