Clever Geek Handbook

PythonとRedisのレート制限



この記事では、最も単純な実装から高度なGeneric Cell Rate Algorithm（GCRA）まで、PythonおよびRedisベースのレート制限アルゴリズムについて説明します。redis-py



をpip install redis使用してRedis（）と対話します。クエリの制約を試すために、リポジトリのクローンを作成することをお勧めします。



制限時間



期間ごとのリクエスト数を制限する最初のアプローチは、時間制限アルゴリズムを使用することです。制限キー（レートキー、ニックネームやIPアドレスなどの一意のもの）ごとに、カウンター（最初に制限値を設定）と有効期限が別々に保存されます。 （期間）。リクエストを受信すると減少します。



PythonとRedisを使用すると、このアルゴリズムを次のように実装できます。



  1. 制約キーの存在を確認します。
  2. 存在する場合は、制限値（Redis SETNX）と有効期限（Redis EXPIRE）で初期化します。
  3. 後続のリクエストごとにこの値を減らします（Redis DECRBY）。
  4. クエリは、値がゼロを下回った場合にのみ停止します。
  5. 指定した時間が経過すると、キーは自動的に削除されます。


from datetime import timedelta
from redis import Redis

def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
    if r.setnx(key, limit):
        r.expire(key, int(period.total_seconds()))
    bucket_val = r.get(key)
    if bucket_val and int(bucket_val) > 0:
        r.decrby(key, 1)
        return False
    return True


30秒で20リクエストの制限をエミュレートすると、このコードの動作を確認できます（明確にするために、関数をモジュールに配置します）。 



import redis
from datetime import timedelta
from ratelimit import time_bucketed

r = redis.Redis(host='localhost', port=6379, db=0)
requests = 25

for i in range(requests):
    if time_bucketed.request_is_limited(r, 'admin', 20, timedelta(seconds=30)):
        print ('Request is limited')
    else:
        print ('Request is allowed')


最初の20件のリクエストのみが制限されません。その後、新しいリクエストを再度送信できるように30秒待つ必要があります。



このアプローチの欠点は、頻度を制限するのではなく、特定の期間にユーザーが行う要求の数を制限することです。制限全体がすぐに使い果たされた場合は、期間の終了を待つ必要があります。



リークバケットアルゴリズム



頻度を非常に注意深く制限できるアプローチがあります。これは現在のバケットアルゴリズムです。操作の原理は、実際に漏れているバケットの場合と同じです。バケットの端まで水（リクエスト）を注ぎ、水の一部は常に底の穴から流出します（通常はバックグラウンドプロセスを使用して実装されます）。バケットに注がれる水の量が注がれる水の量よりも多い場合、バケットはいっぱいになり、いっぱいになると、新しいリクエストは受け付けられなくなります。



アルゴリズムのしくみ



このアプローチをスキップして、リークをエミュレートするための個別のプロセスを必要としない、より洗練されたソリューションであるGeneric Cell RateAlgorithmを使用できます。



一般化されたセルレート制御アルゴリズム



GCRAは、非同期転送モード（ATM）と呼ばれる通信業界で作成されました。これは、ATMネットワークマネージャーが、指定された制限よりも高いレートで到着したセル（固定サイズの小さなデータパケット）を遅延またはドロップするために使用されました。



GCRAは、各リクエストのいわゆる理論的到着時間（TAT）を使用して、残りの制限を追跡します。 



tat = current_time + period


到着時間が現在のTATより短い場合、次のリクエストを制限します。これは、頻度が1リクエスト/期間で、リクエストが期間に分割されている場合にうまく機能します。しかし実際には、周波数は通常、制限/期間として計算されます。たとえば、頻度が10リクエスト/ 60秒の場合、ユーザーは最初の6秒間に10リクエストを行うことができます。そして、1リクエスト/ 6秒の頻度で、彼はリクエストの間に6秒待たなければなりません。



リクエストのグループを短期間で送信し、制限が1を超える期間、その数の制限を維持できるようにするには、各リクエストを期間/制限の比率で割る必要があります。そうすると、次の理論上の到着時間（new_tat）が異なる方法で計算されます。リクエストの到着時刻を次のように示しますt。



  • new_tat = tat + period / limitリクエストがグループ化されている場合（t <= tat）
  • new_tat = t + period / limitリクエストがグループ化されていない場合（t > tat）


したがって： 



new_tat = max(tat, t) + period / limit


new_tat現在の時間と期間の合計よりも大きい場合 、リクエストは制限されますnew_tat > t + period。new_tat = tat + period / limit取得しtat + period / limit > t + periodたとき。したがって、クエリを制限する必要があるのは、の場合のみtat - t > period - period / limitです。 



      period — period / limit
      <----------------------->
--|----------------------------|--->
  t                           TAT


この場合、限られたリクエストには理論上の到着時間がないため、TATを更新する必要はありません。



それでは、コードの最終バージョンを作成しましょう。 



from datetime import timedelta
from redis import Redis

def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
    period_in_seconds = int(period.total_seconds())
    t = r.time()[0]
    separation = round(period_in_seconds / limit)
    r.setnx(key, 0)
    tat = max(int(r.get(key)), t)
    if tat - t <= period_in_seconds - separation:
        new_tat = max(tat, t) + separation
        r.set(key, new_tat)
        return False
    return True


GCRAは時間に依存するため、Redis TIME を使用しました。また、現在の時刻が複数の展開で一貫していることを確認する必要があります（異なるマシン間のクロックの不一致は誤検知につながる可能性があります）。



このコードは、10リクエスト/ 60秒でのGCRAパフォーマンスを示しています。 



import redis
from datetime import timedelta
from ratelimit import gcra

r = redis.Redis(host='localhost', port=6379, db=0)
requests = 10

for i in range(requests):
    if gcra.request_is_limited(r, 'admin', 10, timedelta(minutes=1)):
        print ('Request is limited')
    else:
        print ('Request is allowed')


アルゴリズムは最初の10リクエストを制限しませんが、次のリクエストを行うには少なくとも6秒待つ必要があります。しばらく後にスクリプトを実行しようとリミットの値と期間を変更（例えば、limit = 1およびperiod=timedelta(seconds=6)）。



実装をクリーンに保つために、呼び出しの受信と送信の間にロックを追加しませんでした。ただし、同じキーを使用して同時に複数のリクエストを行う場合に必要です。Luaを使用すると、コンテキストマネージャーとしてロックを追加できます。 



def request_is_limited(r: Redis, key: str, limit: int, period: timedelta):
    period_in_seconds = int(period.total_seconds())
    t = r.time()[0]
    separation = round(period_in_seconds / limit)
    r.setnx(key, 0)
    try:
        with r.lock('lock:' + key, blocking_timeout=5) as lock:
            tat = max(int(r.get(key)), t)
            if tat - t <= period_in_seconds - separation:
                new_tat = max(tat, t) + separation
                r.set(key, new_tat)
                return False
            return True
    except LockError:
        return True


完全なコードはGitHubにあります。


More articles:


All Articles