Rate Limiting

Table of Contents

1. 定义

In computer networks, rate limiting is used to control the rate of requests sent or received by a network interface controller. It can be used to prevent DoS attacks and limit web scraping.

via: https://en.wikipedia.org/wiki/Rate_limiting

rate limiting,通常叫做“速率限制”,“流量限制”。用于控制到达服务端的请求量,避免出现爆发式的增长,导致服务不可用。把“异常” 的请求丢掉(比如 DDos 攻击,爆破登录),“正常”的用户请求得到处理。另外,在“正常”流量也比较高的情况下,控制请求的速率(延迟), 让服务端可以在自己的承受范围内把请求平滑的处理掉。

在哪里做限流?

一般会放在客户端,代理层(gateway/proxy),服务器三块。

  1. 客户端:在请求时做流量控制,这样实现最简单。但前提假设是认为这些都是“正常”的流量。 自己的服务一般不会用这种方法,第三方的 APIs,为了避免出现被 block,可以在调用时做限流;
  2. 代理层:比如入口(公司/集群) nginx;waf 也是常见的流量控制(从安全层面)器;当然更常见的是微服务网关,限流熔断基本是 微服务网关的标配。通常限流会放在代理层实现,好处是下游的服务们不需要关心限流的事情(否则每个服务都自己实现一遍成本太高);
  3. 服务层:服务自身当然也可以实现限流,灵活性很高。但通常适用于与业务逻辑强相关的事情,通用的比如 IP,API 的限制放在代理层更好;

2. 限流算法

有 5 种限流算法,各有优劣势。

2.1. 令牌桶(Token bucket)

Rate limiting using the Token Bucket algorithm 这篇文章讲的比较清晰,我直接搬过来了。

上图中包含一个桶,桶中放着令牌(token),令牌就是请求的运行资格。

  1. 上方以稳定的速率向桶中放入令牌
  2. 当有流量进入时,判断桶中是否有足够的令牌
    1. 如果有剩余令牌,流量通过,自动扣除
    2. 如果没有令牌,则把流量丢掉(注意:流量是否丢掉,还是阻塞等待新的令牌生成,视具体的业务场景而定)

2.2. 漏桶法(Leaky bucket)

想象有一个桶,桶中放着所有要处理的请求。水滴的速度用来控制请求什么时候被处理。

  1. 桶可以类比成一个 FIFO 的队列
  2. 新的流量进来之后,先入队
  3. 以固定的“流速”来控制出队

2.3. 固定窗口(Fixed Window)

Rate limiting using the Fixed Window algorithm 这篇文章讲的比较清晰,我直接搬过来了。

固定窗口是指将时间改成固定宽度的段(比如 1 分钟),对每一段中的流量进行计数,超过 limit 则丢弃或者等待下一个时间段。

2.4. 滑动日志(Sliding log)

滑动日志将以日志的方式记录每一个请求的时间戳。通过历史的请求日志量来判断当前请求是否放行,超过阈值则丢弃。

2.5. 滑动窗口(Sliding Window)

滑动窗口是固定窗口的一种改进,为了解决固定窗口在窗口边缘突发流量是无法检测的问题。

解决的思路是如果没到达当前窗口的结束,则按照差的比例,从前一个窗口的加权补充到当前窗口。讲起来有点绕,但其实很好理解。

如上图,假设一分钟消耗为 50,当前时间为 01:20 ,已经计数了 20 。

  1. 当前时间未到达 2:00 占了当前 2 分钟窗口的 20/60 = 1/3
  2. 从前一分钟补偿 2/3 的时间,凑够 1 分钟。也就是 50 * (2/3)
  3. 滑动窗口的总计数为 50 * (2/3) + 20 结果是小于 50 的,所以放行。

3. 算法的开源实现

主要选取基于 go 的实现:

4. 我自己的实现

https://github.com/zhangjie2012/yo-ratelimit

分别实现了 token-bucket 和 sliding-window 两种算法。我的场景是需要针对单个 IP 或者用户请求进行限流, 所以额外加了一个 RateLimitPool 的实现。

5. 总评

  • 漏桶的好处是任何时候流量都是非常均匀的,问题是无法处理流量不均匀或者突发(burst)情况(会被阻塞),特定场景才会使用;
  • 令牌桶解决了漏桶无法处理突发流量的问题,能够处理上游的不均匀流量;
  • 固定窗口在窗口边界的前后赶上流量高峰是没办法的检测到的,误差较大,所以一般不用于生产;
  • 滑动日志解决了固定窗口的问题,当流量大时,缺点也很明显:无论是存储空间,还是计算成本都比较昂贵,一般也不会使用;
  • 滑动窗口方法是固定窗口的改进,可以处理流量突发场景。

以上 5 种算法实现都不复杂,各有优劣。令牌桶和滑动窗口都可以处理流量不够均匀的情况,建议使用。不过这几种算法都是针对单机的实现,不适合分布式场景下。

6. 扩展资料

First created: 2022-11-22 14:17:55
Last updated: 2022-12-01 Thu 14:04
Power by Emacs 27.1 (Org mode 9.4.4)