设计一个限流器

Table of Contents

网络服务中，限流器用于控制一个客户端的请求频率或数据速率。速率限制器常见的场景如下：

限流器主要是用来：

所有 HTTP 网关，都有现成限流器，有些网络库也配备了限流器功能。

限流器可以基于源IP、用户ID、设备ID 或其他属性，根据实际需求选择。这些开源的限流器能满足大多需求，如果能用的话，就不必写代码了。我们这里讨论的，是TCP长连接的限流器，常在物联网领域使用，它限制每个设备只能在一定速率内上传数据。

为什么不直接用开源现成的基于源IP地址的限流器？因为公平。有的用户一个厂区上千设备但是只有一个出口IP地址，有的用户是4G接入一个设备一个IP地址，不能一律基于源IP来限制，不然单个出口IP的用户太亏了。

1 如何处理超限连接

如果是 HTTP 请求，可以直接返回 429: Too many requests 。但设备的 TCP 长连接如果关闭了，就会反复重连，浪费流量。好在 TCP 有 拥塞控制，只要你停止接收，客户端就暂缓发送。

如果你忘记了，让我们把 Stevens 上的灰掸一掸。这里不妨做个实验，客户端建立连接直接发数据；服务端接收连接但应用端不接收数据，等一会后在接收。 

;; 客户端

;; load packages
(ql:quickload "usocket")
(ql:quickload "str")
;; generate a large string
(defvar large-string (str:repeat 50000 "hello"))
;; connect to 127.0.0.1:9876
(usocket:with-client-socket (socket stream "127.0.0.1" 9876 :element-type 'character)
  ;; send string to remote
  (write-string large-string stream))

;; 服务端

;; load packages
(ql:quickload "usocket")
;; listen
(defvar socket (usocket:socket-listen "127.0.0.1" 9876))
;; accept
(defvar connection (usocket:socket-accept socket :element-type 'character))
;; but not receive data from connection until 5 seconds later
(sleep 5)
;; after 5 seconds waiting, read from connection
(read-line (usocket:socket-stream connection))

tcpdump1.png

网络抓包可以看到，客户端发送几个数据(PSH)后，服务端返回了 TCP ZeroWindow ，随后客户端就不再发送数据，而是发送心跳 TCP Keep-Alive ，服务端返回 TCP ZeroWindow 。过了一会这时候服务端处理了数据，发了 TCP Window Update ，客户端就可以继续发送数据了。

2 速率限制相关算法

有几个简单的算法可以用于限流器，这些算法包括

  • 令牌桶
  • 漏桶
  • 时间窗口
  • 时间队列
  • 滑动时间窗口

如果想更深入研究这些算法，可以先了解排队系统。下面简单介绍这些算法。

2.1 令牌桶

令牌桶使用广泛，原理简单。aws 和 stripe 都使用这个算法限制 API 请求频率。

token-bucket.png

图示是限制客户端发送数据在 2k/s ，并允许临时突发 4k/s 的令牌桶。

令牌桶按照下面的规则工作：

  1. 令牌桶有预定容量，令牌按照一定频率填满桶，如果桶满了，新的令牌就丢弃。
  2. 每个请求从桶里拿走一个令牌，如果桶里令牌没了，就等着。

这个算法的有点是简单容易实现，不占太多内存，短时间内允许突发请求。缺点可能有也是允许突发请求。

2.2 漏桶

漏桶是个队列，生产者往队列里填请求，如果队列满了请求就丢掉；消费者以一定频率从队列里拿请求。nginx 使用漏桶算法实现速率限制。

leak.png

算法有点是消耗内存少，请求处理的频率固定。缺点是要设定两个参数，以及不能请求突发处理，只能固定频率处理。

2.3 时间窗口

固定时间窗口计数，是我在草台班子团队中见过最多的。简单地说，如果要限制每秒2k数据，那么就将时间划分为1秒的窗口，这个窗口已经发了2k了，那么就不能再发，等到下一个窗口才能继续发。简单易懂有效，甲方也能理解，缺点就是请求常常再窗口边缘处理。

time-win-c.png

2.4 时间队列

如果要限制每秒2次请求，就记录之前1秒内的请求，最多能记录2个请求。新请求来的时候，删掉1秒之外的超时请求时间；如果记录满了，就丢弃这个请求；如果记录没满，就写入请求时间戳，然后处理这个请求。

tlog.png

优点是最终速率准确，缺点是耗内存。

2.5 滑动时间窗口

这是时间窗口的一点优化。例如，要限制每秒4k数据，我们划分时间窗口为每个窗口1秒；上一个串口处理了3k数据，现在时间来到当前这个窗口的 \( \frac{1}{4} \) 时间处，那么这个当前窗口开始到现在，可以接受 \( 4-\left( 3\times \frac{3}{4} \right)=1.75 \) k数据。

slct.png

解决了固定时间窗口边缘突发请求的问题，也省内存，缺点是基于统计，并不十分准确。cloudflare 用这个算法。

3 实现细节

我们在物联网设备平台上使用速率限制，需求是要求每个设备只能以设定速率上传数据。最终选用的算法是滑动时间窗口算法，因为它相对准确，并且内存消耗不大。每个设备可以创建多个连接上传数据，这些连接可能不在一个服务程序里面，所以我们使用 redis 记录滑动时间窗口的时间、当前窗口内已处理数据量、上一个窗口处理的数据量等信息。增减数据使用 INCR 和 DECR ，这是为了解决多个限流请求一个记录的一致性问题。

red.png

By .