设计一个限流器

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 令牌桶

令牌桶使用广泛,原理简单。awsstripe 都使用这个算法限制 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 记录滑动时间窗口的时间、当前窗口内已处理数据量、上一个窗口处理的数据量等信息。增减数据使用 INCRDECR ,这是为了解决多个限流请求一个记录的一致性问题。

red.png


By .