1. 时间窗口限流

固定时间窗口

所谓时间窗口限流,是指在一定的时间内,维护一个访问总量的数值,当其超过阈值时,拒绝后续所有的请求,直到进入下一个时间窗口。
限流算法 - 图1
上图横轴的每个时间节点都是一个时间窗口,我们可以看到,当请求没有超过阈值以前,请求为蓝色,可以正常进行,超过阈值的请求会被抛弃。
但是,这种算法有一个很明显的临界问题:假设限流阀值为 5 个请求,单位时间窗口是 1s,如果我们在单位时间内的前 0.8-1s 和 1-1.2s,分别并发 5 个请求。虽然都没有超过阀值,但是如果算 0.8-1.2s,则并发数高达 10,已经超过单位时间 1s 不超过 5 阀值的定义了。

滑动时间窗口

滑动窗口限流可以解决固定窗口临界值的问题。它将单位时间周期分为n个小周期,分别记录每个小周期内接口的访问次数,并且根据时间滑动删除过期的小周期。
限流算法 - 图2
滑动窗口的格子周期划分的越多,那么滑动窗口的滚动就越平滑,限流的统计就会越精确,但是相对的,维护成本也就越高。

2. 令牌桶算法

我们想象有一个虚拟的桶,桶里面放有一定数量的Token,请求访问资源之前,需要从桶里拿到令牌,拿不到令牌的请求会被拒绝掉,这就是令牌桶的思想。
限流算法 - 图3
令牌桶算法的实现很轻量级,我们并不需要一个真正的桶,只需要维护以下几个数值,就能在请求到来时计算出是否有足够的Token分配给请求:

  • 上一次发出令牌的时间
  • 令牌的生产速度
  • 上次剩下的令牌数
  • 桶的容量

根据以上的数据,我们就可以计算出是否有足够的令牌分配给当前的请求,来完成限流操作。
限流算法 - 图4

3. 漏桶算法

漏桶算法的算法原理是,设置一个漏桶,每次请求都将请求放入到漏桶当中,若漏桶已满则拒绝请求,漏桶按照一定速率将已放入漏桶的请求流出,流出的请求将被正常处理。
漏桶算法面对限流时,可以缓存一定的请求,不用直接粗暴拒绝(消息队列的限流本质上就是漏桶算法)。
限流算法 - 图5
令牌桶与漏桶相比,本质的区别是没有一个队列来缓存请求,在更轻量级的同时也只能粗暴的直接舍弃请求。
当然,我们也可以因地制宜的综合使用两种算法,比如在等待获得令牌前设置一个缓存队列,这些就留给大家在实践的过程中深入的探索了。