スライディングウィンドウ vs 固定ウィンドウのレート制限

スライディングウィンドウ vs 固定ウィンドウのレート制限

スライディングウィンドウと固定ウィンドウのアルゴリズムの選択は、ウィンドウの境界でレートリミッターがトラフィックをどのように処理するかに影響します。

固定ウィンドウ

固定ウィンドウアルゴリズムは、時間を固定間隔に分割し、各間隔内のリクエストをカウントします。

ウィンドウ1: 12:00:00 - 12:00:59  → 最大100リクエスト
ウィンドウ2: 12:01:00 - 12:01:59  → 最大100リクエスト

境界問題：

クライアントは12:00:59に100リクエスト、12:01:00にさらに100リクエストを送信でき、技術的には制限を超えずに2秒間で200リクエストを送信できてしまいます。

スライディングウィンドウログ

スライディングウィンドウログアルゴリズムは、すべてのリクエストタイムスタンプを追跡し、ローリングウィンドウ内のリクエストをカウントします。

12:01:30の時点で、12:00:30から12:01:30までのすべてのリクエストをカウント

利点: 完璧な精度、境界バーストなし 欠点: ユーザーあたりO(n)メモリ（すべてのタイムスタンプを保存）

スライディングウィンドウカウンター

スライディングウィンドウカウンターは妥協案です。2つの固定ウィンドウを使用して加重カウントを計算します：

推定カウント = (前のウィンドウカウント x オーバーラップ%) + 現在のウィンドウカウント

12:01:15の例（現在のウィンドウの25%時点）：
= (前のウィンドウ: 80 x 0.75) + (現在のウィンドウ: 30)
= 60 + 30 = 90（制限100以下）

アルゴリズム比較

特徴	固定ウィンドウ	スライディングログ	スライディングカウンター
精度	低 (2倍バースト)	完璧	高 (約98%)
メモリ	O(1)	O(n)	O(1)
複雑さ	低	高	中
最適な用途	シンプルなAPI	セキュリティ重要	ほとんどのAPI