RedisとLua scriptを使用したSpring BootのRate Limiting

1. 概要

Rate limitingは、クライアントが一定期間内にAPI呼び出しを行い過ぎるのを防ぎ、システムの過負荷やabuse を回避するのに役立ちます。この記事では、Redisを集中管理されたカウンターとして使用し、Lua scriptと組み合わせることで、複数のアプリケーションインスタンスが同時にアクセスする場合の原子性を確保する方法を紹介します。この記事の終わりに、fixed window及びsliding window アルゴリズムを使用したRateLimiterを自分で書き、Spring Boot にinterceptor経由で統合し、動作を検証するテストを書くことができるようになります。

2. Rate Limitingに対するRedisの選択理由

アプリケーションが複数のインスタンス（水平スケーリング）で実行されている場合、各インスタンスのメモリに保存されたカウンター（例えばAtomicInteger）は同期できません。Redisはこの問題を次の理由で解決します：

• 集中管理されたデータストアであり、すべてのインスタンスが同じ場所から読み書きします。
• TTL（EXPIRE）をサポートしており、古いキーを自動的にクリーンアップできるため、cronジョブは不要です。
• Lua scriptをサーバー上で原子的に実行することをサポートしており、カウンターをインクリメントしてしきい値をチェックする際のrace conditionを回避します。

注意： システムに単一インスタンスのみがあり、状態共有が必要ない場合、インメモリlimiter（例えば Guava RateLimiter）の方が高速でシンプルです。分散rate limitが必要な場合のみ、Redisを使用してください。

3. 依存関係の設定

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

spring.data.redis.host=localhost
spring.data.redis.port=6379

Spring Bootはこれらのプロパティに基づいて、RedisConnectionFactoryとStringRedisTemplateを自動的に設定します。

4. Fixed Windowアルゴリズム

Fixed windowは時間を固定フレーム（例えば60秒ごと）に分割し、そのフレーム内のリクエスト数をカウントします。しきい値を超える場合は、リクエストを拒否します。

4.1. 原子的なLua script

Lua scriptを使用してINCRとEXPIREを1つの原子的なコマンドに結合し、2つのステップの間に別のリクエストが干渉する状況を防ぎます。

public class FixedWindowRateLimiter {

    private static final String SCRIPT = """
        local current = redis.call('INCR', KEYS[1])
        if current == 1 then
            redis.call('EXPIRE', KEYS[1], ARGV[1])
        end
        return current
        """;

    private final StringRedisTemplate redisTemplate;
    private final RedisScript<Long> redisScript;

    public FixedWindowRateLimiter(StringRedisTemplate redisTemplate) {
        this.redisTemplate = redisTemplate;
        this.redisScript = RedisScript.of(SCRIPT, Long.class);
    }

    public boolean isAllowed(String clientId, int limit, int windowSeconds) {
        String key = "rate:fixed:" + clientId;
        Long current = redisTemplate.execute(
                redisScript,
                List.of(key),
                String.valueOf(windowSeconds));
        return current != null && current <= limit;
    }
}

説明：

• INCR KEYS[1]はキーのカウンターをインクリメントして、新しい値を返します。
• current == 1（キーの最初の作成）の場合、TTLをwindowSeconds秒に設定します。
• スクリプト全体がRedisサーバー上で原子的に実行され、マルチスレッドまたはマルチインスタンスで実行されている場合でも、他のリクエストに割り込まれることはありません。
• isAllowedは、現在のリクエスト数がlimitを超えていない場合にtrueを返します。

4.2. Spring Boot interceptorでの使用

@Component
public class RateLimitInterceptor implements HandlerInterceptor {

    private final FixedWindowRateLimiter rateLimiter;

    public RateLimitInterceptor(FixedWindowRateLimiter rateLimiter) {
        this.rateLimiter = rateLimiter;
    }

    @Override
    public boolean preHandle(HttpServletRequest request,
                              HttpServletResponse response,
                              Object handler) throws IOException {
        String clientId = request.getRemoteAddr();
        boolean allowed = rateLimiter.isAllowed(clientId, 100, 60);
        if (!allowed) {
            response.setStatus(429);
            response.getWriter().write("Too many requests");
            return false;
        }
        return true;
    }
}

Interceptorはクライアントの IP をクライアント ID として取得し、60秒ごとに100リクエストに制限します。しきい値を超える場合、HTTP 429を返してリクエストがコントローラーに進まないようにします。

注意： Fixed windowには「端でのburst」という欠点があります。クライアントが59秒の終わりに100リクエストを送信し、60秒の最初に100リクエストをさらに送信する場合、各ウィンドウが有効であっても、1秒以内に実際には200リクエストがあります。より正確にする必要がある場合は、sliding windowを使用してください。

5. Sliding Window Logアルゴリズム

Sliding window logは、各リクエストのタイムスタンプをSorted Setに保存し、確認するたびに古いタイムスタンプを削除します。Fixed windowより正確ですが、各リクエストを保存するためにメモリを使用します。

public class SlidingWindowRateLimiter {

    private static final String SCRIPT = """
        local key = KEYS[1]
        local now = tonumber(ARGV[1])
        local windowMs = tonumber(ARGV[2])
        local limit = tonumber(ARGV[3])

        redis.call('ZREMRANGEBYSCORE', key, 0, now - windowMs)
        local count = redis.call('ZCARD', key)
        if count < limit then
            redis.call('ZADD', key, now, now)
            redis.call('PEXPIRE', key, windowMs)
            return 1
        end
        return 0
        """;

    private final StringRedisTemplate redisTemplate;
    private final RedisScript<Long> redisScript;

    public SlidingWindowRateLimiter(StringRedisTemplate redisTemplate) {
        this.redisTemplate = redisTemplate;
        this.redisScript = RedisScript.of(SCRIPT, Long.class);
    }

    public boolean isAllowed(String clientId, int limit, int windowMs) {
        String key = "rate:sliding:" + clientId;
        long now = System.currentTimeMillis();
        Long result = redisTemplate.execute(
                redisScript,
                List.of(key),
                String.valueOf(now),
                String.valueOf(windowMs),
                String.valueOf(limit));
        return result != null && result == 1;
    }
}

Luaの各ステップの説明：

• ZREMRANGEBYSCOREは、スコア（タイムスタンプ）がnow - windowMsより小さいエントリを削除します。つまり、時間ウィンドウの外に出たリクエストを削除します。
• ZCARDはSorted Set内の残りのエントリの数をカウントします。これは現在のウィンドウ内のリクエスト数です。
• count < limitの場合、スコアがnowの新しいエントリを追加し、キーのTTLをwindowMs（トラフィックがなくなったときに自動的にクリーンアップするため）に設定して、1を返します（許可）。
• 満杯の場合は0を返します（拒否）。新しいエントリは追加しません。

結果として、ウィンドウはリアルタイムで継続的にスライドし、fixed windowのような端でのburstは発生しません。

6. 2つのアルゴリズムの比較

基準	Fixed Window	Sliding Window Log
精度	低い、端でのburst発生	高い
メモリ	O(1) per key	O(limit) per key
複雑さ	シンプル	より複雑
用途	粗い制限、高トラフィック	機密API、精度が必要

どのアルゴリズムを選ぶべきか確信がない場合は、fixed windowで始めてください。シンプル、パフォーマンスが優れており、ほとんどの内部APIに十分です。

7. Testcontainersを使用したテストの作成

テストがマシンにインストール済みのRedisに依存しないようにするには、Testcontainersを使用してDockerでRedisを起動します。

<dependency>
    <groupId>org.testcontainers</groupId>
    <artifactId>junit-jupiter</artifactId>
    <scope>test</scope>
</dependency>

@Testcontainers
class FixedWindowRateLimiterTest {

    @Container
    static GenericContainer<?> redis = new GenericContainer<>("redis:7-alpine")
            .withExposedPorts(6379);

    FixedWindowRateLimiter rateLimiter;

    @BeforeEach
    void setUp() {
        RedisStandaloneConfiguration config = new RedisStandaloneConfiguration(
                redis.getHost(), redis.getMappedPort(6379));
        LettuceConnectionFactory factory = new LettuceConnectionFactory(config);
        factory.afterPropertiesSet();

        StringRedisTemplate template = new StringRedisTemplate(factory);
        template.afterPropertiesSet();

        rateLimiter = new FixedWindowRateLimiter(template);
    }

    @Test
    void shouldBlockRequestsExceedingLimit() {
        String clientId = "client-A";
        int limit = 3;

        boolean r1 = rateLimiter.isAllowed(clientId, limit, 60);
        boolean r2 = rateLimiter.isAllowed(clientId, limit, 60);
        boolean r3 = rateLimiter.isAllowed(clientId, limit, 60);
        boolean r4 = rateLimiter.isAllowed(clientId, limit, 60);

        assertThat(r1).isTrue();
        assertThat(r2).isTrue();
        assertThat(r3).isTrue();
        assertThat(r4).isFalse();
    }
}

このテストはlimit = 3で4つの連続リクエストを送信します。最初の3つのリクエストは受け入れられ（isTrue）、4番目のリクエストは同じウィンドウ内のしきい値を超えたため拒否されます（isFalse）。Testcontainersは自動的にRedis containerを起動および削除し、テストがCI実行環境に依存しないようにします。

8. 一般的なエラー

• キーのTTLを設定しない：EXPIREを忘れると、キーはRedisに永遠に存在し、メモリリークが発生し、カウンターはリセットされません。
• カウンターをインクリメントしてしきい値をチェックする際に2つの別々のコマンドを使用（GETその後INCR）：複数のリクエストが同時に到着した場合にrace conditionを作成し、実際のしきい値超過につながります。常にLua scriptに統合するか、原子的なINCRを使用してください。
• クライアントを識別しないキーを使用：キーにclientIdを埋め込むのを忘れると、すべてのクライアントが同じカウンターを使用し、他のユーザーが誤ってブロックされます。
• トラフィックが非常に大きい場合のSliding window log：limitが大きく、多くのクライアントが同時にアクセスする場合、Sorted Setが肥大化する可能性があります。メモリを節約するために、sliding window counter（2つのfixed windowの組み合わせ）の使用を検討してください。

9. 結論

RedisとLua scriptの組み合わせは、分散rate limiterを構築するための一般的な選択肢です。シンプル、原子的、そしてアプリケーションインスタンスの数に応じてスケールしやすいです。Fixed windowはシンプルであるため、ほとんどの場合に適しており、sliding window logは時間的な境界での正確な制御が必要な場合に適しています。本番環境に展開する前に、しきい値の境界での動作を必ず徹底的にテストしてください。ここが論理エラーが最も発生しやすい場所です。