[整理] Rate limit関連アルゴリズム

Rate Limitが必要な背景

このテクニックは、主にapigatewayで使用されます。
Rate limiting（レートリミティング）は、サーバーやネットワーク資源の過負荷を防止し、サービスの安定性を維持するために重要な技術です。以下のような状況で特に必要とされます:

1. DDoS攻撃の防止: 悪意のあるユーザーが大量のリクエストを一度に送信し、サーバーをダウンさせるのを防ぎます。
2. 資源の保護: サーバーのCPU、メモリ、ネットワーク帯域幅などの限られた資源を保護し、過度なトラフィックによるパフォーマンス低下を防止します。
3. 公平な資源配分: 多くのユーザーが同時にサービスを利用する際、特定のユーザーに過剰なリソースが割り当てられないようにし、すべてのユーザーに公平なリソース使用の機会を提供します。
4. APIの乱用防止: APIを呼び出すクライアントが許容範囲を超えてリクエストを送信することを防ぎます。
5. サービス品質の維持: 過度なトラフィックによってサービスが遅くなったり停止したりするのを防ぎ、全体的なユーザーエクスペリエンスを向上させます。

Leaky Bucket Rate Limiting

Leaky Bucketアルゴリズム

Leaky Bucket（リーキーバケット）アルゴリズムは、サーバーがリクエストを一定の速度で処理できるように制限する方法であり、水が一定の速度で漏れていくバケツのようにリクエストがバケツに蓄えられ、一定の速度で処理されます。バケツが満杯になると、それ以上のリクエストは拒否されます。

Javaによる6つのリクエストを一括で処理する実装

以下のコードは、Leaky Bucketアルゴリズムを使用して、6つのリクエストを一度にまとめて処理する方法を示しています。

import java.util.LinkedList;
import java.util.Queue;

public class LeakyBucket {
    private final int bucketCapacity;
    private final int leakRate;
    private int currentSize;
    private final Queue<Long> bucket;

    public LeakyBucket(int capacity, int rate) {
        this.bucketCapacity = capacity; // バケツの最大容量
        this.leakRate = rate; // 1秒あたりに処理するリクエスト数
        this.currentSize = 0; // 現在のバケツのサイズ
        this.bucket = new LinkedList<>();
    }

    // リクエストを一括で追加するメソッド
    public synchronized boolean addRequestBatch(long[] requestTimes) {
        leak(); // バケツ内のリクエストを一定速度で処理

        for (long requestTime : requestTimes) {
            if (currentSize >= bucketCapacity) {
                System.out.println("Request rejected: Bucket is full.");
                return false; // バケツが満杯の場合、リクエストは拒否される
            }
            bucket.add(requestTime);
            currentSize++;
            System.out.println("Request added: Current bucket size = " + currentSize);
        }
        return true;
    }

    // 一定時間ごとにバケツからリクエストを処理するメソッド
    private synchronized void leak() {
        long currentTime = System.currentTimeMillis();

        while (!bucket.isEmpty() && (currentTime - bucket.peek()) / 1000 >= 1) {
            bucket.poll(); // 最も古いリクエストを削除
            currentSize--;
            System.out.println("Processed request: Current bucket size = " + currentSize);
        }
    }

    public static void main(String[] args) throws InterruptedException {
        LeakyBucket bucket = new LeakyBucket(5, 1); // バケツ容量5、1秒あたり1リクエストを処理

        // 6つのリクエストをまとめて送信
        long[] requestBatch = new long[6];
        for (int i = 0; i < 6; i++) {
            requestBatch[i] = System.currentTimeMillis();
        }

        // 6つのリクエストを一度に処理
        System.out.println("Sending batch of 6 requests...");
        bucket.addRequestBatch(requestBatch);

        // バケツがリクエストを処理する時間を与える
        Thread.sleep(3000);

        // 追加のリクエストを送信
        System.out.println("Sending additional request...");
        long additionalRequestTime = System.currentTimeMillis();
        bucket.addRequestBatch(new long[]{additionalRequestTime});
    }
}

コードの説明:

1. addRequestBatch: 複数のリクエストを一度にまとめて処理するバッチメソッド。リクエストが一度に送信され、バケツの容量を超えると追加のリクエストは拒否されます。
2. leak: 一定の速度でバケツ内のリクエストを処理するメソッドです。
3. 同時リクエスト処理: 6つのリクエストがまとめて送信され、その後、追加のリクエストが処理されます。

サンプルコードの結果

許容量を超えるリクエストの場合は、リクエストが拒否されるログを確認できます。

Rate Limiting適用の効果

この実装は、サーバーやネットワークリソースが同時に大量のリクエストを受けた場合でも安定した処理を保証し、パフォーマンスを保護しつつ、ユーザーエクスペリエンスを維持するのに役立ちます。