RateLimitアルゴリズムまとめまとめ (→ Sliding window countersでOK)

RateLimit.md

TL;DR

• Leaky bucket : キューイングして出力量(consume)で調節 (アルゴリズムというかキューを使って調節)
• Token bucket : 定期的に資源を追加し平均値を調節。バーストに強い (ソシャゲのスタミナ回復)
• Fixed window counters : 単位時間あたりの上限値を指定。キューを使わないLeaky bucket。境界の2倍問題あり
• Sliding window log : 総数(counters)でなくアクセス時刻(log)で管理。境界問題を解消する一方、消費増加がぱない(Int → Array(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の解説

• https://konghq.com/blog/how-to-design-a-scalable-rate-limiting-algorithm/
• 各アルゴリズムを図入りで解説。楽に使うならKongをどうぞ、という流れ
• Leaky Bucket
• Fixed Window
• Sliding Log
• Sliding Window

参考: An alternative approach to rate limiting

• https://www.figma.com/blog/an-alternative-approach-to-rate-limiting/
• 図入りで、各アルゴリズムをステップ実行する丁寧な解説
• Token bucket
• Fixed window counters
• Sliding window log
• Sliding window counters
• (Practical considerations)

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

• https://blog.atulr.com/rate-limiter/
• Redisを使ったシンプルなアルゴリズム例
• 恐らく、起点時刻をSlidingさせたFixed window counters