用GCRA（通用蜂窝速率算法）对API请求进行速率限制的讨论

2 年 ago
文, 翔
2 minutes

本文是富士通云技术2019年“降临节日历”的第21天文章。
第20天是由@foobaron先生开始提供“连接私人局域网”的私人桥接功能！

首先

一开始

开头

在开始时

起初

你好！我是在NIFCLOUD开发IaaS API的 @kzmake。

请问大家是如何处理API请求的瞬间爆发的情况呢？

为了最小化由请求突发引起的服务影响，在公开WebAPI时可能需要一些机制，如速率限制等。

今年因为这样那样的事情,

    • WebAPIのレート制御のアルゴリズムとして、GCRAの解説

GCRA + Redisを利用したWebAPIのレート制限

我想用简略的方式来写这个故事！

?简而言之

GCRAはシンプルで高速なレート制限を実現する

GCRA + Redisで好きなパラメータをKeyとしてレート制限できる

GCRA + Redisで複数のサービス間でレート制限を共有できる

?GCRA（通用信道速率算法）是什么？

这是一种表示Leaky buket算法的方法，无需滴漏过程。它通过称为“单元”的固定大小的小包的单位来实现速率限制和调度。

Leaky bucket是指…… (Please provide the complete sentence or context for a more accurate paraphrase.)

具有一定数量的“漏斗”（受限的吞吐量）的桶。无法容纳超过其容量的桶。通过滴水的过程，可以表达平滑地恢复桶容量。

这种滴漏过程和存储容量也可以应用于API请求的速率限制等方面。

leaky_bucket

GCRA 是什么意思？

这是一个算法，根据从数据包排出被理论上插入的单元的时刻到达时间（TAT），来模拟Leaky bucket滴漏过程。

GCRA所使用的参数和公式。

    • $t_a$

セルをパケットに挿入しようとした時刻

$TAT$

挿入されるセルがバケットから排出されるまでの時刻

$T$

パケットが1つのセルを排出する時間

$\tau$

バケットの時間的な最大容量

$バケットのセル最大容量 \times T$

$\tau + T$

パケットの排出感覚を含めて許容できる最大時間

当桶中的单元数为$n$时，理论到达时间$TAT$可以表示为：

TAT_{n+1} = \begin{cases}
  t_a + T & (n=0) \\
  TAT_{n} + T & (otherwise)
\end{cases}

這被表示為。

当尝试插入单元格时，应如何进行评估？

真正的地根据意思用中文翻译这段话：当尝试插入一个单元格时，若桶中已有$n$个单元格，则判断能否将单元格插入桶中。

TAT_{n+1} - (\tau + T) \geq t_a

我们会进行评估。将其整理一下，

TAT_{n} - \tau \geq t_a

邻居就住在旁边。

在GCRA中，使用到TAT来简单地表示了Leaky bucket中的滴水过程。

作为速度控制的功能

我们将考虑使用Redis以使其能够在多个服务中共享利用。

在GCRA中需要使用的Redis命令

GCRA可以通过软件方式将TAT永久化，并在TAT的时刻到期来实现（其中，ta是速率限制时确定的，τ和T是由速率限制系统决定的）。

如果想要从多个服务统一实施速率限制，可以使用Redis等工具，在不同服务之间共享这个$TAT$。

这次算法中使用的Redis命令是，

    • SET

 

    EXPIRE

这只有两个选项，非常简单对吧。
(顺便提一下，虽然成本相同，但使用SETEX命令可以一次性设置多个配置。)

尽管这个算法很简单，我个人实现了它。

    • github.com/brandur/redis-cell

 

    github.com/throttled/throttled

我会介绍两个利率限制。

使用brandur/redis-cell库

在github.com/brandur/redis-cell上发布了一个利用SETEX的Redis模块。只需将github.com/brandur/redis-cell作为Redis的一个模块引入，即可使用这个功能。

redis-cell命令的添加方式

以下是在github.com/brandur/redis-cell#Usage中介绍的命令。

CL.THROTTLE <key> <max_burst> <count per period> <period> [<quantity>]

Redis-cell命令与GCRA相关

CL.THROTTLE user123 15 30 60 1
               ▲     ▲  ▲  ▲ ▲
               |     |  |  | └───── apply 1 token (default if omitted)
               |     |  └──┴─────── 30 tokens / 60 seconds
               |     └───────────── 15 max_burst
               └─────────────────── key "user123"

创建一个名为user123的桶，最大容量为15个单元格。
如果我们将”执行命令”这个动作解释为”向桶中插入一个单元格”，那么

    • 挿入されるセル数

1

$\tau$

15 * T

$T$

60/30

$\tau + T$

(15 + 1) * T

$t_a$

コマンドを叩いた時刻

与此有关。

redis-cell的响应

如果考虑将其用作API请求的速率限制时，

127.0.0.1:6379> CL.THROTTLE user123 15 30 60
1) (integer) 0
2) (integer) 16
3) (integer) 15
4) (integer) -1
5) (integer) 2
    1. 0：未被阻止

 

    1. 1：已被阻止

阻止的上限值+ 1

常见的X-RateLimit-Limit值

剩余阻止值

常见的X-RateLimit-Remaining值

用户需要等待重新发送请求的秒数[秒]

常见的重试时间值

在被允许期间为-1

距离重置上限值的秒数[秒]

常见的X-RateLimit-Reset值

看起来好像可以这样。

接下来只需要在各自的程序中准备好Redis客户端，并执行相应的命令即可。

被限制/被限制的使用

github.com/throttled/throttled也作为Golang包发布了。它作为一个存储器，可以对请求进行限制和调度。

    • goredisstore

 

    • memstore

 

    redigostore

由于支持这一点，似乎可以灵活使用。

使用throttled的程序示例

github.com/brandur/redis-cellと同等の機能を持っているので一例で紹介するのみとします。APIリクエストをレート制限するのであれば、とっても簡単に導入できますね。

mux := http.NewServeMux()
mux.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
    w.WriteHeader(http.StatusOK)
    fmt.Fprintf(w, "Hello World")
})

store, err := memstore.New(65536)
if err != nil {
    log.Fatal(err)
}

rateLimiter, err := throttled.NewGCRARateLimiter(store, throttled.RateQuota{MaxRate: throttled.PerMin(30), MaxBurst: 15})
if err != nil {
    log.Fatal(err)
}

// Custom: func(r *http.Request) string { ... } により好きなキーを設定可能
varyBy := &throttled.VaryBy{Path: true}

httpRateLimiter := throttled.HTTPRateLimiter{
    RateLimiter: rateLimiter,
    VaryBy:      varyBy, 
}

http.ListenAndServe(":3000", httpRateLimiter.RateLimit(mux))

?最后

GCRA是一种高速且简单的算法，提供了精细的速率限制。通过使用github.com/brandur/redis-cell或github.com/throttled/throttled等工具，可以轻松地将速率限制功能添加到WebAPI中。

汇率限制

    • 有限のリソースへのアクセスを抑制する

 

    • パスワード試行回数のセキュリティ強化

 

    レート制限の解除や上限数の緩和などのマネタイズ

如果您有这样的目的，请一定考虑使用GCRA，因为它是可用的要素。

据说明天 @hunter9x 会写点什么！敬请期待！

? 仅需要一种选择，原文的中文释义如下：

? 参考 -> 以……作为参考

    • Rate Limiting, Cells, and GCRA

 

    • Generic cell rate algorithm – Wikipedia

 

    • brandur/redis-cell: A Redis module that provides rate limiting in Redis as a single command.

 

    throttled/throttled: Package throttled implements rate limiting access to resources such as HTTP endpoints.
bannerAds