最近システム設計の面接関連の書籍や記事を読んでいます。 その中で参考文献的に紹介されていたものを深ぼったのでその記録です。
ちなみに書籍についてはこちら。
オンラインコースについてはこちらです。
API を運用していると、あるユーザーの過剰アクセスや、重いエンドポイントへの同時実行が全体の安定性を崩すことがあります。これを防ぐ代表的な仕組みがレートリミッターです。
ただし、レートリミッターは単に Redis にカウンタを置けば終わりではありません。実装を誤ると、同時アクセス時にレースコンディションが起き、想定より多くのリクエストを通してしまいます。
この記事では、Redis を使ったレートリミッターの基本と、Lua Script によるレースコンディション対策を整理します。
レートリミッターで起きる典型的な問題
たとえば「同時実行中のリクエストは 20 件まで」という制限を考えます。
素朴に実装すると、アプリケーションは次のように動きます。
ZCARDで現在件数を確認する- 上限未満なら
ZADDで自分のリクエストを登録する
一見問題なさそうですが、同時に 2 リクエストが来ると壊れます。
- A が
ZCARDを見る - B が
ZCARDを見る - A が
ZADDする - B も
ZADDする
上限直前では、A と B がどちらも「まだ空きがある」と判断してしまい、上限超過が起きます。 これがレースコンディションです。
Redis の Lua Script が効く理由
この問題は、確認 と 更新 が別コマンドになっていることが原因です。
対策は、確認して、条件を満たせば更新する までを 1 つの atomic な処理にすることです。
Redis では Lua Script を EVAL で実行できます。Lua Script は Redis 上で atomic に実行されるため、スクリプト実行中は他の command や他の script が途中に割り込めません。
つまり、
- A の script が
ZCARDして判定し、必要ならZADDする - その script が終わってから B の script が動く
という順序になります。
これは「ロックを取っている」というより、Redis が script 全体を不可分な処理として実行してくれる、という理解が正確です。
sorted set を使う理由
同時実行数の管理では sorted set が便利です。
score: リクエスト開始時刻member: 一意な request id
この構造にすると、現在進行中のリクエストを 1 要素ずつ表現できます。
ZCARD で件数を数えられますし、古すぎる要素を ZREMRANGEBYSCORE で掃除できます。
ここで重要なのは次の 2 点です。
scoreは重複してよいmemberは同じ sorted set 内で一意である必要がある
同じミリ秒に複数リクエストが来ると、score は同値になり得ます。一方で member が重複すると、新規追加ではなく既存要素の更新になってしまうため、件数が増えません。
古い要素の掃除も忘れない
実運用では、リクエスト終了時の ZREM が必ず成功するとは限りません。
- アプリケーションが落ちる
- タイムアウトする
- 後処理が走らない
この場合、Redis に「もう終わっているのに残っている要素」が溜まります。
そのため、concurrent limiter ではリクエスト開始時に ZREMRANGEBYSCORE で古い要素を掃除しておくことがあります。
ここは sliding window 型の rate limiter と少し意味が違います。
sliding window では、指定したウィンドウ幅より前のリクエストを削除すること自体がアルゴリズムの本体です。つまり「期限切れになった過去リクエストを落とす」のは正常系の処理です。
一方 concurrent limiter では、本来はリクエスト終了時の ZREM で要素が消える前提です。それでも障害やタイムアウトで残留することがあるので、ZREMRANGEBYSCORE は stale entry を回収するための保険として入れます。
実装時の注意点
Redis でレートリミッターを実装するときは、次を押さえておくと堅くなります。
check -> updateを分離しない- 判定と更新は Lua Script で atomic に実行する
memberは必ず一意にする- 古い要素の掃除を入れる
ZREMRANGEBYSCOREの意味が、sliding window と concurrent limiter で違うことを意識する- Lua Script は短く保つ
- Redis 障害時に fail-open にするか fail-closed にするか設計で決める
特に Lua Script は強力ですが、Redis 全体をブロックするので長い処理を入れるものではありません。あくまで短い整合性確保用のロジックに留めるべきです。
また、Redis 障害時の挙動も先に決めておく必要があります。Redis に接続できないときにレートリミッターを一時的に無効化してリクエストを通すなら fail-open、逆に安全側に倒して拒否するなら fail-closed です。
可用性を優先したい API では fail-open が合うことがあります。一方で、認証や課金のように制限が外れること自体が危険な API では fail-closed を選ぶ余地があります。どちらが正しいというより、エンドポイントの性質に応じて選ぶべき設計項目です。
まとめ
Redis を使ったレートリミッターでは、レースコンディションが本質的な問題になります。
単純に ZCARD して ZADD するだけでは、同時アクセス時に上限超過が起こります。
この問題に対しては、
sorted setで現在進行中のリクエストを管理しLua Scriptで確認 -> 判定 -> 更新を atomic に実行する
という設計が有効です。
Redis の Lua Script はロックそのものではありませんが、結果としてクリティカルセクションのように振る舞います。レートリミッターのように「複数操作を矛盾なくまとめたい」場面では、非常に相性のよい手段です。