GCRA(Generic cell rate algorithm)でAPIリクエストをレート制限する話

この記事は、 [富士通クラウドテクノロジーズ Advent Calendar 2019](https://qiita.com/advent-calendar/2019/fjct) の21日目の記事です。
20日目は @foobaron さんの [プライベートLAN同士を接続する機能 プライベートブリッジ の提供を開始しました](https://blog.pfs.nifcloud.com/20191220_private_bridge) でした！

## 🌞はじめに
こんにちは！NIFCLOUDでIaaS向けAPIの開発をしている @kzmake と申します。

みなさんは、**APIリクエストの瞬間的なバースト**、どのように対応していますか？

リクエストの瞬間的なバーストによるサービス影響を最小限にするため、WebAPIを公開するにあたり**レート制限**などの仕組みが必要な場面もあるかとおもいます。

そんなこんなで今年は、

* WebAPIのレート制御のアルゴリズムとして、[GCRA](Generic cell rate algorithm)の解説
* [GCRA] + Redisを利用したWebAPIのレート制限

の話をざっくりと書いていきたいとおもいます！

## 💡TL;DR
* [GCRA]はシンプルで高速なレート制限を実現する
* [GCRA] + Redisで好きなパラメータをKeyとしてレート制限できる
* [GCRA] + Redisで複数のサービス間でレート制限を共有できる

## 🤔Generic cell rate algorithm([GCRA])って？

ドリッププロセスなしでLeaky buketを表現するアルゴリズムです。「セル」と呼ばれる固定サイズの小さなパケット単位でレート制限やスケジューリングを行う仕組みです。

### Leaky bucketとは
一定量の「漏れ」(制限されたスループット)を持つバケットのこと。容量を超えて入れる事はできないバケット。ドリッププロセスを持つことで、滑らかなバケット容量の回復を表現できます。

このドリッププロセスとバケット容量は、APIリクエストのレート制限などにも応用されています。

![leaky_bucket](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/48903/b93fdd0e-d1ee-9b4c-cf51-1d0405f687c9.gif)


### GCRAとは

理論到着時刻($TAT$)として、理論的に挿入されるセルがパケットから排出されるまでの時刻をもとに[Leaky bucket]のドリッププロセスを再現するアルゴリズムです。

#### [GCRA]で利用されるパラメータと式
* $t_a$
    * セルをパケットに挿入しようとした時刻
* $TAT$
    * 挿入されるセルがバケットから排出されるまでの時刻
* $T$
    * パケットが1つのセルを排出する時間
* $\tau$
    * バケットの時間的な最大容量
        * $バケットのセル最大容量 \times T$
* $\tau + T$
    * パケットの排出感覚を含めて許容できる最大時間

バケットに挿入されているセル数を$n$としたとき、理論到着時刻$TAT$は、

```math
TAT_{n+1} = \begin{cases}
  t_a + T & (n=0) \\
  TAT_{n} + T & (otherwise)
\end{cases}
```
と表されます

#### セルを挿入しようとしたときはどのように評価するの？

１つのセルを挿入しようとしたとき、
バケットに挿入されているセル数を$n$である場合、セルをバケットに挿入できるかを

```math
TAT_{n+1} - (\tau + T) \geq t_a
```
で評価していきます。これを整理すると、

```math
TAT_{n} - \tau \geq t_a
```
となりますね。

GCRAでは、[Leaky bucket]のドリッププロセスを$TAT$を用いてシンプルに表現しています。

## ⚙️レート制限の機能として

複数のサービスから共通して利用できるようにRedisの利用を想定していきます。

### [GCRA]で必要となるRedisコマンド

[GCRA]は、ソフトウェア的に$TAT$を永続化し、$TAT$の時刻でexpireすることで実現できます。($t_a$はレート制限時に決まり、$\tau$と$T$はレート制限システム毎に決定しています。)

複数のサービスから共通してレート制限を行う場合は、[Redis]などを利用してこの$TAT$をサービス間で共有すればいいことになりますね。

今回のアルゴリズムで使用するRedisコマンドは、

- [SET](https://redis.io/commands/set)
- [EXPIRE](https://redis.io/commands/expire)

の２つのみです。とってもシンプルですね :tada: 
(ちなみにコストは同じですが、[SETEX](https://redis.io/commands/setex)のワンコマンドでまとめて設定も可能です。)

独自で実装しても簡単なアルゴリズムですが、この記事では、

- [github.com/brandur/redis-cell]
- [github.com/throttled/throttled]

の２つのレート制限を紹介していきます。

### brandur/redis-cellの利用

[github.com/brandur/redis-cell]で`SETEX`を利用したRedisモジュールが公開されています。これは、Redis側にモジュールとして [github.com/brandur/redis-cell]を導入することで利用可能となります。


#### redis-cellで追加されるコマンド

[github.com/brandur/redis-cell#Usage](https://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: ブロックされている
2. ブロックするまでの上限値 + 1
    * 一般的な `X-RateLimit-Limit` の値
3. ブロックされるまでの残りの値
    * 一般的な `X-RateLimit-Remaining` の値
4. ユーザーが再リクエストできるまでの秒数[sec]
    * 一般的な `Retry-After` の値
    * 許可されている間は `-1` 
5. 上限値までリセットされるまでの秒数[sec]
    * 一般的な `X-RateLimit-Reset` の値

と見てよさそうです。

あとはそれぞれのプログラムでRedis Clientを準備し、コマンドを実行していくのみとなります。


### throttled/throttledの利用

golang packageとして[github.com/throttled/throttled](https://github.com/throttled/throttled)というものも公開されています。こちらはstoreとして、

- goredisstore
- memstore
- redigostore

をサポートしているので柔軟に利用できそうですね。


#### throttled/throttledを使ったプログラムの例

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

```golang
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.]

[Leaky bucket]: #Leakybucketとは
[GCRA]: #GCRAとは

[Redis]: https://redis.io/
[github.com/brandur/redis-cell]: https://github.com/brandur/redis-cell
[github.com/throttled/throttled]: https://github.com/throttled/throttled

[Rate Limiting, Cells, and GCRA]: https://brandur.org/rate-limiting
[Generic cell rate algorithm - Wikipedia]: https://en.wikipedia.org/wiki/Generic_cell_rate_algorithm

[brandur/redis-cell: A Redis module that provides rate limiting in Redis as a single command.]: https://github.com/brandur/redis-cell
[throttled/throttled: Package throttled implements rate limiting access to resources such as HTTP endpoints.]: https://github.com/throttled/throttled