レートリミットアルゴリズムの世界
0
以下の文章は執筆者のEthiraj Srinivasan さんからの許可を得て翻訳したものです。
レートリミットアルゴリズムとは、システムやサービスによって送受信されるリクエストやメッセージなどの頻度を制御するメカニズムです。リクエストやメッセージの数が増えすぎることで、システムやサービスに負荷がかかることを防ぐために使用され、システム障害やパフォーマンスの低下を防止することができます。
レートリミットにより、システムは制御された形でリクエストやメッセージを処理できるようになり、リソースを効率的かつ効果的に使用できるようになります。
クライアントからサーバーへのバッチリクエストは、レートリミッターによって制限されます。
利用例
- API：多くのAPIは、悪用を防止し公正利用を保証するためにレートリミットを使用しています。ユーザーごとまたはAPIキーごとにリクエスト数を制限することで、スパムやDoS攻撃などを防止することができます。
- ストリーミングサービス：ストリーミングサービスでは、クライアントとの間で送受信されるデータ量を制御するためにレートリミットが使用されます。ビットレートやユーザーごとの同時再生数を制限することでサーバーへの過負荷を防止し、すべてのユーザーにスムーズなストリーミング体験を提供します。
- メールサービス：メールサービスは、スパムを防止し配信性を確保するためにレートリミットを使用します。ユーザーごとまたはIPアドレスごとの送信メール数を制限することで、スパムを防止し、メールプロバイダーとしての評判を向上させることができます。
- SNS：SNSは、スパムや悪用を防止し、ユーザーエクスペリエンスを向上させるためにレートリミットを使用します。ユーザーごとまたはIPアドレスごとのリクエスト数を制限することで自動化されたアクションやボットによる乱用を防止し、すべてのユーザーに公平で信頼性のあるサービスを提供することができます。
- 分散システム：分散システムは、個々のノードやサービスへの過負荷を防止するためにレートリミットを使用します。ノード間またはサービス間のリクエスト、メッセージを制限することで、ボトルネックを回避し、システム全体のスムーズな動作を確保できます。
レートリミットアルゴリズムは、さまざまなシステムやサービスにおける信頼性、セキュリティ、拡張性を確保する上で重要なものです。適切なレートリミットアルゴリズムを使用し、適切なパラメータを設定することで、システム管理者は悪用を防止し、公正利用を保証し、ユーザーに高品質のサービスを提供することが可能となります。
レートリミットアルゴリズムには次のようなさまざまな種類があります。
- 固定ウィンドウ：固定された時間ウィンドウ内で送信または受信できるリクエストやメッセージ数を制限します。たとえば、1分間に100リクエストまで許可しているサービスの場合、リクエストの数が100に達すると、それ以上のリクエストは次の時間ウィンドウが始まるまで遅延されるか、拒否されます。
- スライディングウィンドウ：スライディング時間ウィンドウ内で送信または受信できるリクエストやメッセージの可変変数を設定します。たとえば、1秒あたり10リクエストを許可する場合もありますが、リクエスト数の上限は最後の60秒のスライディングウィンドウに対して計算されます。このアルゴリズムはトラフィックバーストに対処することができ、トラフィックの急激な上昇をなだらかにすることができます。
- トークンバケット：固定された速度でバケツにトークンを追加します。リクエストがくると、バケツからトークンが削除されます。バケツが空の場合、リクエストは拒否または遅延されます。このアルゴリズムは、バケツのサイズまでのトラフィックを受け入れます。
- リーキーバケット：固定された速度で持続的にバケツから水（トークン）を漏らす形で動作します。リクエストがあると、バケツに追加されますが、バケツが溢れた場合はリクエストが拒否または遅延されます。このアルゴリズムはトラフィックのバースト性を平準化することができますが、持続的な高トラフィックには対応できません。
- 適応型：システムまたはサービスの現在の負荷や容量に基づいてレートリミットを調整します。たとえば、オーバーロードを防ぐためにトラフィックのピーク時にレートリミットを減らす場合などです。このアルゴリズムは効率的なリソースの活用を可能にし、システム障害を防止できます。
レートリミットアルゴリズムのフローチャート
固定ウィンドウレートリミットアルゴリズム：
- 固定された時間ウィンドウを設定（例：1分）。
- 時間ウィンドウ内で処理されるリクエストやメッセージの数のカウンターを初期化。
- リクエストまたはメッセージが到着した場合：
a.カウンターが時間ウィンドウ内の最大許容数よりも小さい場合、リクエストやメッセージを処理し、カウンターを増やす。
b.カウンターが時間ウィンドウ内の最大許容数に等しい場合、リクエストやメッセージを拒否または遅延。
４.時間ウィンドウが終了したら、カウンターをゼロにリセット。
[開始]
|
v
[時間ウィンドウを設定]
|
v
[カウンターを初期化]
|
v
[リクエストやメッセージが到着]
|
v
[カウンター < 最大許容数?]
/ \
/ \
[はい] [いいえ]
| |
v v
[リクエストを処理] [リクエストを拒否または遅延]
|
v
[時間ウインドウが経過]
|
v
[カウンターをリセット]
|
v
[終了]
以下は、アルゴリズムが実際にどのように動作するかの例です：
例えば、ユーザーがAPIリクエストを行うことを許可するWebサービスがあるとしましょう。ウィンドウの時間を10秒に固定し、ウィンドウごとの最大リクエスト数を5に設定しているとします。
- 最初の10秒間で、4つのリクエストが行われた場合、リクエスト数は最大限度を下回るため許可されます。
- 次の10秒間で、7つのリクエストが行われた場合、最初の5つのリクエストは許可されますが、残りの2つは最大限度を超えるため拒否されます。
- 10秒が経過したとき、新しいウィンドウが開始され、同じプロセスが繰り返されます。
スライディングウィンドウレートリミットアルゴリズム：
- 時間ウィンドウを設定（例：1分）。
- スライディング時間ウィンドウ内で処理されたリクエストやメッセージの数のカウンターを初期化。
- リクエストまたはメッセージが到着した場合：
- リクエストやメッセージをキューに追加。
- スライディング時間ウィンドウの外にあるリクエストやメッセージをキューから削除。
- キューのサイズがスライディング時間ウィンドウ内の最大許容数以下の場合、リクエストやメッセージを処理し、カウンターを増やす。
- キューのサイズがスライディング時間ウィンドウ内の最大許容数よりも大きい場合、リクエストやメッセージを拒否または遅延。
- 各時間間隔の後、時間ウィンドウをインターバルの長さだけスライドさせる。
- スライディング時間ウィンドウ内のリクエストやメッセージ数でカウンターをリセット。
[開始]
|
v
[時間ウィンドウを設定]
|
v
[カウンターを初期化]
|
v
[リクエストやメッセージが到着]
|
v
[リクエストをキューに追加]
|
v
[古くなったリクエストを削除]
|
v
[キューのサイズ <= 最大許容数?]
/ \
/ \
[はい] [いいえ]
| |
v v
[リクエストを処理] [リクエストを拒否または遅延]
|
v
[時間ウィンドウをスライド]
|
v
[カウンターをリセット]
|
v
[終了]
トークンバケットレートリミットアルゴリズム：
- バケツ内の最大トークン数とトークンが追加される速度を設定。
- バケツ内のトークン数を最大許容数に初期化。
- リクエストまたはメッセージが到着した場合：
- バケツ内のトークン数がリクエストまたはメッセージに必要なトークン数以上の場合、バケツからトークンを削除し、リクエストやメッセージを処理。
- バケツ内のトークン数がリクエストまたはメッセージに必要なトークン数よりも少ない場合、リクエストやメッセージを拒否または遅延。
- 固定速度でバケツにトークンを追加。
- バケツ内のトークン数が最大許容数を超える場合は、最大許容数に設定。
[開始]
|
v
[最大トークン数およびレートを設定]
|
v
[バケツを初期化]
|
v
[リクエストまたはメッセージが到着]
|
v
[トークン >= 必要なトークン数?]
/ \
/ \
[はい] [いいえ]
| |
v v
[トークンを削除してリクエストを処理] [リクエストまたはメッセージを拒否または遅延させる]
|
v
[トークンを追加]
|
v
[トークン <= 最大許容数?]
/ \
/ \
[はい] [いいえ]
| |
v v
[何もしない] [トークンを最大許容数に設定]
|
v
[終了]
リーキーバケット（穴あきバケツ）レートリミットアルゴリズム：
-
バケツが保持できる最大トークン数とバケツから漏れるトークンの速度を設定。
-
バケツ内のトークン数をゼロに初期化。
-
リクエストまたはメッセージが到着した場合：
a. バケツ内のトークン数とリクエストまたはメッセージに必要なトークン数を合算した値が、バケツで許容される最大トークン数以下の場合、必要なトークン数をバケツに追加し、リクエストやメッセージを処理。
b. バケツ内のトークン数とリクエストまたはメッセージに必要なトークン数を合算した値が、バケツで許容される最大トークン数を超える場合、リクエストやメッセージを拒否または遅延。
-
固定された速度でバケツからトークンを漏らす。
-
漏れたトークン数がバケツ内のトークン数を超える場合、バケツ内のトークン数をゼロに設定。
[開始]
|
v
[最大トークン数およびレートを設定]
|
v
[バケツを初期化]
|
v
[リクエストまたはメッセージが到着]
|
v
[トークン + 必要 <= 最大許容数?]
/ \
/ \
[はい] [いいえ]
| |
v v
[トークンを追加] [リクエストまたはメッセージを拒否または遅延]
|
v
[トークンを漏らす]
|
v
[トークン >= 漏れたトークン数?]
/ \
/ \
[はい] [いいえ]
| |
v v
[何もしない] [トークンをゼロに設定]
|
v
[終了]
適応型レートリミットアルゴリズム：
-
単位時間あたりに許可されるリクエスト数を初期化。
-
リクエストまたはメッセージが到着した場合：
a. 現在の時間ウィンドウで受信したリクエストの数が単位時間あたりに許可されるリクエスト数以下の場合、リクエストやメッセージを処理。
b. 現在の時間ウィンドウで受信したリクエストの数が単位時間あたりに許可されるリクエスト数よりも大きい場合、時間ウィンドウを増やし、単位時間あたりに許可されるリクエスト数を減らす。
-
一定の時間が経過した後、単位時間あたりに許可されるリクエスト数を元の値にリセットし、時間ウィンドウをリセット。
-
時間ウィンドウが一定の最大値に達した場合、時間ウィンドウがリセットされるまでの間、さらなるリクエストを拒否または遅延。
-
単位時間あたりに許可されるリクエスト数が一定の最小値に達した場合、時間ウィンドウがリセットされるまでの間、さらなるリクエストを拒否または遅延。
[開始]
|
v
[単位時間あたりのリクエストを初期化]
|
v
[リクエストまたはメッセージが到着]
|
v
[リクエスト <= 最大許容数?]
/ \
/ \
[はい] [いいえ]
| |
v v
[処理] [時間ウィンドウ増, リクエスト数減]
|
v
[時間ウィンドウは最大に達したか?]
/ \
/ \
[はい] [いいえ]
| |
v v
[拒否または遅延] [時間とリクエストをリセット]
|
v
[リクエストが最小に達したか?]
/ \
/ \
[はい] [いいえ]
| |
v v
[拒否または遅延] [処理を続行]
|
v
[終了]
Pythonによるレートリミットアルゴリズムの実装
固定ウィンドウレートリミットアルゴリズム：
import time
class RateLimiter:
def __init__(self, max_requests, window_duration):
self.max_requests = max_requests
self.window_duration = window_duration
self.window_start_time = time.time()
self.requests_made = 0
def allow_request(self):
current_time = time.time()
time_since_window_start = current_time - self.window_start_time
if time_since_window_start > self.window_duration:
self.window_start_time = current_time
self.requests_made = 0
if self.requests_made < self.max_requests:
self.requests_made += 1
return True
else:
return False
RateLimiterクラスは、max_requestsとwindow_durationの2つの引数を取ります。max_requestsはウィンドウ内で許可される最大リクエスト数であり、window_durationはウィンドウの実行時間（秒単位）です。
allow_requestメソッドは新しいリクエストが行われるたびに呼び出されます。このメソッドでは、現在の時間がまだ現在のウィンドウ内であるかどうかをチェックします。ウィンドウ外である場合は新しいウィンドウを開始してリクエストの数をリセットします。
ウィンドウ内で許可されているリクエスト数よりもリクエストが少ない場合、リクエストが許可され、Trueで返されます。ウィンドウ内で許可されるリクエスト数に達している場合、リクエストを拒否または遅延させ、Falseで返されます。
limiter = RateLimiter(5, 10)
for i in range(20):
if limiter.allow_request():
print(f"Request {i + 1} allowed")
else:
print(f"Request {i + 1} blocked")
time.sleep(1)
この例では、レートリミットが1分あたり5リクエストに設定されています。ループは20回実行され、各反復でallow_requestメソッドが呼び出されます。ループ内ではtime.sleep(1)が呼び出され、リクエスト間に1秒の休止が挿入されます。ループの出力は、レートリミットに基づいて許可されたリクエストとブロックされたリクエストを示しています。
スライディングウィンドウレートリミットアルゴリズム：
import time
class RateLimiter:
def __init__(self, rate, window_size):
self.rate = rate
self.window_size = window_size
self.requests = []
def allow_request(self):
# Get the current time
now = time.time()
# Remove any requests from the queue that are outside the current window
self.requests = [request for request in self.requests if request >= now - self.window_size]
# Check if the number of requests is less than the rate limit
if len(self.requests) < self.rate:
# Add the current request to the queue
self.requests.append(now)
return True
# The rate limit has been reached
return False
この例では、RateLimiterクラスがrate（ウィンドウサイズ内で許可される最大リクエスト数）とwindow_size（ウィンドウサイズの期間）の2つの引数を取ります。allow_requestメソッドでは、現在のリクエスト時刻をキューに追加し、キュー内のリクエストが許可される最大数を超えていないかチェックします。ウィンドウサイズを超えたリクエストはキューから削除されます。もしリクエストが許可される最大数未満であれば、リクエストを許可し、キューに追加します。それ以外の場合、レート制限に達したことを示すFalseを返します。
limiter = RateLimiter(rate=5, window_size=10)
for i in range(10):
if limiter.allow_request():
print(f"Request {i+1} allowed")
else:
print(f"Request {i+1} blocked")
time.sleep(1)
この例では、レートリミットが10秒のウィンドウサイズ内で5リクエストに設定されています。ループは20回実行され、各反復でallow_requestメソッドが呼び出されます。ループ内ではtime.sleep(1)が呼び出され、リクエスト間に1秒の休止が挿入されます。ループの出力は、レートリミットに基づいて許可されたリクエストとブロックされたリクエストを示しています。
トークンバケットレートリミットアルゴリズム：
import time
class TokenBucketRateLimiter:
def __init__(self, rate, capacity):
self.rate = rate
self.capacity = capacity
self.timestamp = time.time()
self.tokens = capacity
def _refill(self):
now = time.time()
elapsed_time = now - self.timestamp
self.tokens += elapsed_time * self.rate
self.timestamp = now
if self.tokens > self.capacity:
self.tokens = self.capacity
def allow_request(self):
self._refill()
if self.tokens >= 1:
self.tokens -= 1
return True
else:
return False
この例では、RateLimiterクラスがmax_tokens（バケツが保持できる最大トークン数）とrefill_rate（バケツに追加されるトークンの速度）の2つの引数を取ります。refill_tokensメソッドでは、前回のリフィル時刻からの経過時間を計算し、その時間に対応する新しいトークン数を計算します。計算された新しいトークン数とバケツ内のトークン数の合計が、max_tokensを超えないようにします。定期的に（refill_rateで指定された速度で）、トークンをバケツに補充します。
allow_requestメソッドは、リクエストに必要なトークン数を引数として取ります。まず、refill_tokensメソッドを呼び出してバケツを補充し、バケツ内のトークンがリクエストに必要なトークン数を超える場合はリクエストを許可します。それ以外の場合、リクエストを拒否します。
limiter = TokenBucketRateLimiter(rate=0.5, capacity=10)
for i in range(20):
if limiter.allow_request():
print(f"Request {i+1} allowed")
else:
print(f"Request {i+1} blocked")
time.sleep(1)
この例では、レートリミットが1秒あたりに1リクエストに設定されています。ループは10回実行され、各反復でallow_requestメソッドが呼び出されます。ループ内ではtime.sleep(1)が呼び出され、リクエスト間に1秒の休止が挿入されます。ループの出力は、レートリミットに基づいて許可されたリクエストとブロックされたリクエストを示しています。
リーキーバケットレートリミットアルゴリズム：
import time
class RateLimiter:
def __init__(self, rate, capacity):
self.rate = rate
self.capacity = capacity
self.last_leak_time = time.time()
self.water_level = 0
def allow_request(self,tokens):
current_time = time.time()
time_since_last_leak = current_time - self.last_leak_time
# Calculate how much water should have leaked out since the last leak
leaked_water = time_since_last_leak * self.rate
self.water_level = max(0, self.water_level - leaked_water)
# Add the new tokens to the bucket
self.water_level = min(self.capacity, self.water_level + tokens)
# Update the last leak time
self.last_leak_time = current_time
# Check if there are enough tokens in the bucket
if self.water_level >= tokens:
self.water_level -= tokens
return True
else:
return False
RateLimiterクラスは、2つの引数rateと capacity を受け取ります。rate はバケツにトークンが追加される最大速度を示し、capacity はバケツが保持できる最大トークン数です。
allow_request メソッドは、新しいリクエストが行われるたびに呼び出されます。前回の漏れからの経過時間とレートに基づき、バケツからどれだけ水（トークン）が漏れているかを計算し、それを現在の水位から差し引きます。その後、新しいトークンをバケツに追加し、最後の漏れ時間（リークタイム）を更新します。
バケツ内にリクエストを満たすのに十分なトークンがある場合、water_level はトークンの数だけ減少し、True が返されます。そうでない場合、False が返されます。
この RateLimiter クラスは、必要なレートと容量でインスタンスを作成し、新しいリクエストが行われるたびに呼び出し、必要なトークンの数を渡すことでコード内で使用できます。例えば：
# Create a rate limiter with a rate of 1 token per second and a capacity of 10 tokens
limiter = RateLimiter(1, 10)
for i in range(10):
if limiter.allow_request(1):
print(f"Request {i+1} allowed")
else:
print(f"Request {i+1} blocked")
この例では、Limiter オブジェクトは、１トークン/秒のレート、最大容量は10トークンで作成されます。新しいリクエストが行われると、limiterは必要なトークンの数（この場合、1）で呼び出されます。バケツ内にリクエストを満たすのに十分なトークンがある場合、Trueが返され、リクエストが許可されます。それ以外の場合、Falseが返され、リクエストは拒否されます。
適応型レートリミットアルゴリズム
import time
class AdaptiveRateLimiter:
def __init__(self, initial_rate, max_rate, min_rate, window_size):
self.initial_rate = initial_rate
self.max_rate = max_rate
self.min_rate = min_rate
self.window_size = window_size
self.history = []
self.last_request_time = time.time()
self.current_rate = initial_rate
def __call__(self):
current_time = time.time()
elapsed_time = current_time - self.last_request_time
self.history.append(elapsed_time)
if len(self.history) > self.window_size:
self.history.pop(0)
average_time = sum(self.history) / len(self.history)
if average_time > 1 / self.current_rate:
self.current_rate = max(self.min_rate, self.current_rate / 2)
else:
self.current_rate = min(self.max_rate, self.current_rate * 2)
self.last_request_time = current_time
return self.current_rate
AdaptiveRateLimiterクラスは、initial_rate、max_rate、min_rate、およびwindow_sizeの4つの引数を受け取ります。initial_rateはリクエストが許可される初期レートであり、max_rateはリクエストが許可される最大レート、min_rateはリクエストが許可される最小レート、そしてwindow_sizeは平均リクエスト時間を計算するために使用されるスライディングウィンドウのサイズです。
__call__メソッドは、新しいリクエストが行われるたびに呼び出され、リクエストが許可される現在のレートを返します。このメソッドは、前回のリクエストから経過した時間を計算し、スライディングウィンドウの履歴に追加します。もし履歴がウィンドウサイズよりも長い場合、最も古いエントリが削除されます。
次に、スライディングウィンドウの履歴を用いて平均リクエスト時間を計算します。もし平均リクエスト時間が現在のレートの逆数（1秒あたりのリクエスト数）よりも長い場合、現在のレートは半分に減少、もしくは場合によっては最小レートになります。それ以外の場合は、現在のレートが倍増され、最大レートに達している場合はそこに留まります。
最後に、現在の時間が最後のリクエスト時間として保存され、現在のレートが返されます。
このAdaptiveRateLimiterクラスは、コード内で初期レート、最大レート、最小レート、およびウィンドウサイズを指定してインスタンスを作成し、新しいリクエストが行われるたびにそのインスタンスを呼び出すことで、リクエストが許可される現在のレートを取得するために使用できます。例えば：
# Create an adaptive rate limiter with an initial rate of 10 requests per second,
# a maximum rate of 100 requests per second, a minimum rate of 1 request per second,
# and a window size of 10 seconds
limiter = AdaptiveRateLimiter(10, 100, 1, 10)
# Make a new request
rate = limiter()
if some_condition:
# Do something if the request is allowed
else:
# Do something if the request is not allowed
この例では、limiterオブジェクトは初期レートが1秒あたり10リクエスト、最大レートが1秒あたり100リクエスト、最小レートが1秒あたり1リクエスト、ウィンドウサイズが10秒で作成されています。新しいリクエストが行われる際には、limiterが呼び出されてリクエストが許可される現在のレートを取得します。ある条件が満たされた場合（リクエストが許可されたレートの制限内である場合など）、リクエストは許可されます。そうでない場合は拒否されます。
記事執筆者より:
レートリミットアルゴリズムとその使用例、フローチャート、実装について理解いただけましたか？記事をお読みいただき、誠にありがとうございます。もしこのコンテンツがお役に立った場合、Mediumでのフォローをお考えいただけると嬉しいです。皆様のサポートは、今後も有益な情報やアイデアを提供し続ける励みとなります。どうぞよろしくお願いいたします！
