Skip to content

Instantly share code, notes, and snippets.

@maiha
Last active July 3, 2024 16:15
Show Gist options
  • Save maiha/91b1cfda314d75db589b3c2879e3a69c to your computer and use it in GitHub Desktop.
Save maiha/91b1cfda314d75db589b3c2879e3a69c to your computer and use it in GitHub Desktop.
RateLimitアルゴリズムまとめまとめ (→ Sliding window countersでOK)

TL;DR

  • Leaky bucket : キューイングして出力量(consume)で調節 (アルゴリズムというかキューを使って調節)
  • Token bucket : 定期的に資源を追加し平均値を調節。バーストに強い (ソシャゲのスタミナ回復)
  • Fixed window counters : 単位時間あたりの上限値を指定。キューを使わないLeaky bucket。境界の2倍問題あり
  • Sliding window log : 総数(counters)でなくアクセス時刻(log)で管理。境界問題を解消する一方、消費増加がぱない(IntArray(Time))
  • Sliding window counters : countersのままで、単位時間の割合計算によって境界問題を解消。これにしておけば間違いない

参考: 様々なrate limitアルゴリズム

  • https://christina04.hatenablog.com/entry/rate-limiting-algorithm
  • 日本語。メリットとデメリットも解説されており、デメリットを克服する形で次のアルゴリズムの説明に入るので、全体がわかりやすい
  • Leaky bucket
  • Token bucket
  • Fixed window counters
  • Sliding window log
  • Sliding window counters

参考: Kong: RateLimitの解説

参考: An alternative approach to rate limiting

参考: An alternative approach to building a simple API Rate limiter using NodeJS and Redis

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment