Note

3年後の自分のために書いています

Redis での Rate limit 実装

〇〇 req/sec という rate limit を実装する例。 どちらも Fixed window counters を前提に説明する。

結論

  • Rate limit 機能はカウンター（INCR）の要不要によって、最適な実装が変わる
  • カウンターが必要な場合は timestamp 入り key を window に、不要な場合は ttl を window にするのが良さそう

カウンターが必要な場合

5req/sec、10req/sec などに制限するような場合 Redis の公式ドキュメントに記載されていた rate limit 実装を 丸パクり 参考にするのが良さそう

See. https://redis.io/commands/INCR#pattern-rate-limiter-1

# 公式ドキュメントの擬似コード
FUNCTION LIMIT_API_CALL(ip)
ts = CURRENT_UNIX_TIME()
keyname = ip+":"+ts
MULTI
    INCR(keyname)
    EXPIRE(keyname,10)
EXEC
current = RESPONSE_OF_INCR_WITHIN_MULTI
IF current > 10 THEN
    ERROR "too many requests per second"
ELSE
    PERFORM_API_CALL()
END

処理の流れ

  • key に何らかの識別子（例では IP アドレス） & 秒ごと（unixtime）の timestamp 付与
  • INCR と EXPIRE を atomic に実行
  • INCR の戻り値の値で rate limit を超えているか判定し、API コールするかどうか決める

感想 & メモ

  • key に timestamp が入ってるので実行秒ごとの rate limit counter が生成されて、不要になったら expire で設定した秒数後に消えるイメージ
  • INCR の「key が存在しない場合は指定された key に 0 をセットしてから increment する」という挙動がミソ
  • ちなみに 〇〇req/min の場合の実装例は https://redis.com/redis-best-practices/basic-rate-limiting/ に載ってる
  • 後述の通り、カウンターが必要なケースで ttl を window に使ってしまうとレースコンディションが発生しうる、かつそれを回避しようとすると実装が複雑になるので、現時点ではこの実装が最適解と考えている

単一のカウンターで ttl を window に使うのはダメなの？

何らかの理由で INCR 後の EXPIRE のセットが失敗すると rate limit が機能しなくなる。 Redis ドキュメントにもレースコンディションが発生しうる、かつこれを回避するには複雑な実装が必要との記載あり。

See. https://redis.io/commands/INCR#pattern-rate-limiter-2

カウンターが不要な場合

1req/sec に制限するような場合

処理の流れ

  • SETEX で ttl を 1 にして key にしてセット
  • key の有無によって API コールするかどうか決める

感想 & メモ

  • SETEX は atomic な処理でこちらは確実に ttl のセットが保証される
  • カウントが不要な場合はこのやり方がシンプルで良い、やはり INCR を混ぜると一気に難しくなるのだと思う

20230717更新

いや、この場合もマルチスレッド環境にて同じタイミングで GET が走ると複数回 API リクエスト実行されるから競合状態は起きうる。（典型的な check-then-act 処理）

参考