RedisのRate Limit Pattern 3種類

いくつかの Redis の Rate Limit パターンを書き記す。
ここでは例として、IP アドレス(以下 ip )ごとに Rate Limit をかける前提とする。

※全パターン、 Redis Cluster 対応です。

1. Single Counter パターン

Redis の Key 設計

※ % で囲んだ部分は変数。

(String型) ratelimit:%ip%
ex)
ratelimit:127.0.0.1

疑似アプリケーションコード

• ip ごとに Key を分ける
• Key が 10 カウントを超えていたら ERROR
• Key は 1 秒ごとに消えていく
• INCR&EXPIRE は LuaScript で Atomic に実行

script = """
             local current
             current = redis.call("incr",KEYS[1])
             if tonumber(current) == 1 then
                 redis.call("expire",KEYS[1],1)
             end
         """
ip = IP_ADDRESS()
keyname = "ratelimit:"+ip
current = redis.GET(keyname)
IF current != NULL AND current > 10 THEN
    ERROR "too many requests per second"
ELSE
    redis.EVAL(script,1,keyname)
END

Single Counter な Rate Limit 実装。
LuaScript を実行する EVAL で、 INCR&EXPIRE を実装。
LuaScript 化しないと、 EXPIRE 実行前にアプリケーションが死んだ際 Redis にキーが残り続ける。
TTL を 1 秒から変更することで任意の期間で Rate Limit が出来る。

2. RateLimit に任意のメタ情報を保管するパターン

Redis の Key 設計

※ % で囲んだ部分は変数。

(List型) ratelimit:%ip%
ex)
ratelimit:127.0.0.1

疑似アプリケーションコード

• ip ごとに Key を分ける
• List の value に任意のメタ情報を保管していく
• List の長さが 10 を超えていたら ERROR
• Key(=List) は 1 秒ごとに消えていく
• INCR&EXPIRE は LuaScript で Atomic に実行

script = """
             redis.call("rpush",KEYS[1],VALUE[1])
             redis.call("expire",KEYS[1],1)
         """
userid = USER_ID()
ip = IP_ADDRESS()
keyname = "ratelimit:"+ip
current = redis.LLEN(keyname)
IF current != NULL AND current > 10 THEN
    ERROR "too many requests per second"
ELSE
    IF redis.EXISTS(keyname) == FALSE
        redis.EVAL(script,1,keyname,userid)
    ELSE
        redis.RPUSHX(keyname,userId)
    END
END

List 型のリスト長取得コマンドの LLEN が O(1) であることを利用したもの。
List の value は Rate Limit に利用されないため、ユーザー ID などの任意のメタ情報を埋め込むことが可能です。
そのため、今回の例では IP アドレスの Rate Limit に達した時、その List の value を見ることでどのユーザーからのアクセスが原因か？を即座に知ることが出来ます。

なおこのコードは、レースコンディションで EXISTS が false になり、複数のクライアントで無意味に LuaScript が実行されてしまうことがあります。
しかしそれは Rate Limit の文脈では問題がありません。※無駄に EXPIRE をセットしなおしてしまうだけです。

デメリットは、メタ情報の大きさとアクセス頻度に比例したメモリを消費する点です。

3. Sliding Window の集計が可能なパターン

Redis の Key 設計

※ % で囲んだ部分は変数。

(String型) {ratelimit:%ip%:}%timestamp%
ex)
{ratelimit:127.0.0.1:}1605054195

疑似アプリケーションコード

• ip * timestamp ごとに Key を分ける
• current timestamp を INCR する
• mget コマンドの 1 回の Round Trip で過去分もまとめて取得する
• Key に hash tagを設定して、 Redis Cluster でも mget できるようにする
• 古い Key は Redis の EXPIRE で消えていく

script = """
             redis.call("incr",KEYS[1])
             redis.call("expire",KEYS[1],16)
         """
timestamp = CURRENT_UNIX_TIME()
ip = IP_ADDRESS()
keyname = "{ratelimit:"+ip+":}"+timestamp
redis.EVAL(script,1,keyname)
keynames = []
FOR(i=0; i<15; i++)
    keynames[0] = "{ratelimit:"+ip+":}"+timestamp-i
END
counts = []
counts = redis.MGET(keynames)
sum = 0
FOR(i=0;i<15;i++)
    sum += counts[i]
    IF i == 0 && sum > 1000 THEN // 1秒間で1000リクエストまで許可(バースト許可)
        ERROR "too many requests per second"
    END
    
    IF i == 9 && sum > 5000 THEN // 10秒間で5000リクエストまで許可
        ERROR "too many requests per 10 seconds"
    END
    
    IF i == 14 && sum > 7000 THEN // 15秒間で7000リクエストまで許可
        ERROR "too many requests per 15 seconds"
    END
END

直近 1 秒のバーストアクセスは許可したいが、 10 秒続く場合は弾きたい場合などに使う Sliding Window な方法です。
atomic が必要な部分のみ LuaScript にしているため、 mget を LuaScript に含めていません。
mget も含めることで Redis への問い合わせは 1 回の Round Trip に収めることも可能で、そこまでコードの見通し ( LuaScript の保守性) も悪くはなりません。
また Key が分かれることから、 Redis Cluster では Multi Command である mget はそのままでは使えないため、 hash tags 機能 { } を使っています。
mget コマンドは取得する要素数 n に比例する O(n) なため、 Sliding する長さには注意が必要です。

まとめ

パターン名	特徴
シングルカウンタ	Current のアクセス数のみ記録するため最小の利用メモリ。瞬間的な負荷を抑えるために利用する
メタ情報付与	List 長を利用するためメモリは消費する。任意のメタ情報も一緒に記録できるため、ドメインに依存した高度な処理を含める余地がある
Sliding Window	Sliding させる長さに比例したメモリと計算量が必要。一瞬のバーストは許可するが、定常的にそのアクセスは不許可したい場合などの高度なユースケースで利用する。