Pythonでユーザーのレート制限チェックに対応したデータ構造を実装する方法

問題の概要

今回は、「有効期限（expire）」を持つデータ構造を作り、ユーザーIDとタイムスタンプを受け取って、そのリクエストを許可するか拒否するかを判定する機能を実装します。リクエストが拒否されるのは、対象ユーザーの直近の成功リクエストから経過した時間が、設定された有効期限以内である場合のみです。

例えば、expire = 6 としてオブジェクト obj を生成し、次の順番でメソッドを呼び出した場合の出力を見てみましょう。

• obj.limit(0, 10) → False：ユーザー0の初回リクエストであり、履歴がないため許可される
• obj.limit(0, 16) → False：前回のリクエスト（時刻10）からの経過時間が6で、有効期限以内のため許可される
• obj.limit(0, 17) → True：前回（時刻10）からの経過時間が7となり、有効期限6を超えたため拒否される
• obj.limit(1, 20) → False：ユーザー1の初回リクエストのため許可される

解決のアプローチ

この問題は、各ユーザーの「直近の成功リクエスト時刻」を記録しておくことで解決できます。具体的には以下の手順で実装します。

• コンストラクタ __init__() を定義し、有効期限 expire を受け取る
• lastCall := デフォルト値が -1 の辞書を作成する（まだリクエストしていないユーザーの初期値として使う）
• limit() 関数を定義し、引数として uid と timestamp を受け取る
• last := lastCall[uid]（該当ユーザーの前回リクエスト時刻）を取得する
• もし last が -1（初回リクエスト）または (last + expire) <= timestamp（有効期限が切れている）の場合：
    ・lastCall[uid] := timestamp を更新する
    ・False を返す（リクエスト許可）
• それ以外は True を返す（リクエスト拒否＝レート制限発動）

ここでポイントになるのが defaultdict(lambda: -1) の使い方です。通常の辞書では存在しないキーへのアクセスでエラーが発生しますが、defaultdict を使えば未登録のユーザーに対しても自動的に初期値 -1 が返るため、コードをシンプルに保てます。

実装例

それでは、実際のコードを見てみましょう。

from collections import defaultdict
class RateLimit:
   def __init__(self, expire):
      self.expire = expire
      self.lastCall = defaultdict(lambda: -1)
   def limit(self, uid, timestamp):
      last = self.lastCall[uid]
      if last == -1 or last + self.expire <= timestamp:
         self.lastCall[uid] = timestamp
         return False
      return True

expire = 6
obj = RateLimit(expire)
print(obj.limit(0,10))
print(obj.limit(0,16))
print(obj.limit(0,17))
print(obj.limit(1,20))

入力

RateLimit(6)
obj.limit(0,10)
obj.limit(0,16)
obj.limit(0,17)
obj.limit(1,20)

出力

False
False
True
False

まとめ

この実装では、辞書による記録管理により、リクエストごとの判定処理を O(1) の計算量で実現しています。また、成功したリクエスト時だけタイムスタンプを更新する仕組みになっているため、「拒否されたリクエストは直近の成功時刻に影響しない」という要件も正しく満たしています。APIのアクセス制御やスパム対策など、実務におけるレートリミット処理の基礎として応用できるパターンです。