token bucketは、長期的な平均request率を制限しながら、上限付きの瞬間的なburstを許可する方式です。容量Bのbucketに毎秒r個のtokenを補充し、各requestが必要数を消費します。不足すれば拒否するか、別のqueue方針を適用します。Redis rate limiterガイドはRedisによるtoken bucket例を示し、RFC 6585 §4はHTTP 429の意味を定義します。

容量と補充率を別々に読む

容量5、補充率が毎秒2個の例を考えます。十分な待ち時間の後なら、1tokenを使うrequestを最大5件まとめて通せます。空になった後は平均して0.5秒ごとに1tokenが戻ります。つまり「毎秒2件」は、どの瞬間にも必ず2件だけ許すという意味ではありません。即時burstの大きさは容量、持続できる平均は補充率で決まります。

前回token数をT、前回の計算時刻をt₀、現在をt₁とすると、request判定前にmin(B, T + (t₁−t₀)×r)を計算します。requestのcost cをまかなえれば許可してcを引き、不足すれば拒否します。request到着時に計算すれば、token補充のために毎秒storageを書き換えるtimerは不要です。

複数instanceで共有状態を原子的に更新

gatewayごとに別bucketを持つと、実効上限がinstance数に応じて増える場合があります。全体上限が必要なら、accountやAPI keyなどの識別子ごとに共有状態を持ち、補充計算と減算を競合なく一度に行います。Redisの例はLua scriptで原子的に処理しますが、これは一つの実装方法です。要件に合うatomic command、transaction、別のcoordination storeも選択肢になります。

識別子はtrafficに合わせます。認証済み利用にはaccount key、匿名requestにはIPなどが候補ですが、NATでは無関係の利用者が同じIPを共有し、分散clientは複数addressを使えます。一つの識別基準だけでabuse対策が完成すると考えないでください。重いreport生成を軽いlookupより多く消費するcost設定も検討できます。

token bucketとleaky queueの違い

token bucketは、静かな時間に蓄えたtokenでburstを通せます。queueを使うleaky-bucket型の設計は、一定速度で処理を送り出して下流負荷を平準化しますが、queue長と待ち時間が生じます。即時拒否と遅延処理は利用者に異なる挙動です。backendがburstを処理できるか、遅れても仕事が有効かで選びます。

429とRetry-Afterの扱い

requestが多すぎる場合、serverはHTTP 429を返せます。RFC 6585では状況説明を含めてもよく、Retry-Afterを含めることもMAYとされています。すべての429に必須ではありません。clientはheaderがあれば従い、なければAPI文書に沿った上限付きの指数backoffとjitterを使う方法があります。同じ処理を安全に再実行できるかも確認します。無計画なretryは過負荷を増やします。

参考資料