Java での古典的な電流制限アルゴリズムの分析例

レート制限とは何ですか?

Wikipedia の概念は次のとおりです:

コンピュータ ネットワークでは、レート制限は、ネットワークによって送受信されるリクエストのレートを制御するために使用されます。ネットワーク インターフェイス コントローラー。DoS 攻撃を防止し、Web スクレイピングを制限するために使用できます。

簡単に訳すと、コンピューター ネットワークでは、電流制限とは、ネットワーク インターフェイスがリクエストを送信または受信する速度を制御することです。 DoS 攻撃を防止し、Web クローラーを制限できます。

電流制限。フロー制御とも呼ばれます。これは、システムが高い同時実行性または 大規模なトラフィック リクエスト に直面した場合、システムへの新しいリクエストのアクセスを制限することで、 システムの安定性を確保することを意味します 。電流制限により、一部のユーザー リクエストが期限内に処理されたり拒否されたりするため、ユーザー エクスペリエンスに影響します。したがって、一般的には、システムの安定性とユーザー エクスペリエンスの間で バランス をとる必要があります。日常生活の例を挙げると、次のようになります。

## 一部の人気の観光スポットでは、通常、1 日の入場者数に制限が設けられています。チケットは毎日5,000枚などの固定枚数のみ販売されます。メーデーや国慶節の連休中に遅れて到着すると、当日券が売り切れて入場できなくなる場合があります。たとえ入場できたとしても、命を疑うほどの行列だ。

''

一般的な電流制限アルゴリズム

固定ウィンドウ電流制限アルゴリズム

最初にカウンターを維持し、単位期間をウィンドウとして扱い、カウンターはこのウィンドウの受信リクエスト数

• 数値が現在の制限しきい値未満の場合、アクセスを許可し、カウンタ 1

# #数値が現在の制限バルブ値より大きい場合、アクセスは拒否されます。
現在の時間ウィンドウが経過すると、カウンターはクリアされます。
単位時間を 1 秒とすると、現在の制限値は 3 です。単位時間 1 秒以内に、リクエストが来るたびにカウンターが 1 ずつインクリメントされます。カウンタが現在の制限しきい値 3 を超えると、後続のリクエストはすべて拒否されます。1 秒が経過すると、カウンタは 0 にクリアされ、再開されます。カウントを開始します。以下に示すように:

疑似コードは次のとおりです。

    /**
     * 固定窗口时间算法
     * @return
     */
    boolean fixedWindowsTryAcquire() {
        long currentTime = System.currentTimeMillis();  //获取系统当前时间
        if (currentTime - lastRequestTime > windowUnit) {  //检查是否在时间窗口内
            counter = 0;  // 计数器清0
            lastRequestTime = currentTime;  //开启新的时间窗口
        }
        if (counter < threshold) {  // 小于阀值
            counter++;  //计数器加1
            return true;
        }

        return false;
    }

ただし、このアルゴリズムには明らかな

重大な問題があります

: 現在の制限しきい値が 5 リクエストで、単位時間ウィンドウが 1 秒であると仮定します。単位時間の最初の 0.8 ～ 1 秒と 1 ～ 1.2 秒の間に 5 つのリクエストを同時に送信した場合、しきい値を超えませんが、0.8 ～ 1.2 秒で計算すると、同時実行数は 10 にもなります。 ## 単位時間 1 秒あたり 5 を超えないというしきい値 の定義を超えました。

スライディング ウィンドウ電流制限アルゴリズム

スライディング ウィンドウ電流制限固定ウィンドウ臨界値の問題を解決するもので、単位期間を n 個の小期間に分割し、小期間ごとにインターフェイスへのアクセス数を記録し、小期間の時間スライドに応じて期限切れのものを削除します。 #次の図は、スライディング ウィンドウ アルゴリズムを説明しています:

単位時間が 1 秒のままであると仮定すると、スライディング ウィンドウ アルゴリズムはそれを 5 つの小さな期間に分割します。つまり、スライディング ウィンドウ (単位時間) は 5 つの小さなグリッドに分割されます。各グリッドは 0.2 秒を表します。0.2 秒ごとに、時間ウィンドウは 1 グリッド右にスライドします。その後、各小さな期間には独自の独立したカウンターがあります。リクエストは 0.83 秒で到着し、0.8 ～ 1.0 秒に対応するカウンタは 1 ずつ増加します。

スライディング ウィンドウが重要な問題をどのように解決するかを見てみましょう?

前提条件現在の制限しきい値は次のとおりです。 1 秒以内にまだ 5 つのリクエストがあった 0.8 ～ 1.0 秒 (たとえば、0.9 秒) 以内に 5 つのリクエストが来て、黄色のグリッドに収まりました 1.0 秒の時点で、さらに 5 つのリクエストが来ました リクエストは紫色のグリッドに収まりました

は固定ウィンドウ アルゴリズムであり、現在の制限はありません

しかし、

がスライディング ウィンドウの場合は、小さな期間ごとに 1 つの小さなグリッドを右に移動します

。1.0 秒を通過した後ポイントすると、小さな正方形が右に移動します。現在の単位時間は 0.2 ～ 1.2 秒です。この領域のリクエストは 5 の制限を超えており、現在の制限がトリガーされています。実際には、紫色のすべてのグリッド リクエストが表示されます

TIPS: スライディング ウィンドウのグリッド期間をさらに分割すると、スライディング ウィンドウのローリングがよりスムーズになり、電流制限統計がより正確になります。 . .

スライディング ウィンドウ アルゴリズム

疑似コードの実装は次のとおりです:

 /**
     * 单位时间划分的小周期（单位时间是1分钟，10s一个小格子窗口，一共6个格子）
     */
    private int SUB_CYCLE = 10;

    /**
     * 每分钟限流请求数
     */
    private int thresholdPerMin = 100;

    /**
     * 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数
     */
    private final TreeMap<Long, Integer> counters = new TreeMap<>();

   /**
     * 滑动窗口时间算法实现
     */
    boolean slidingWindowsTryAcquire() {
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //获取当前时间在哪个小周期窗口
        int currentWindowNum = countCurrentWindow(currentWindowTime); //当前窗口总请求数

        //超过阀值限流
        if (currentWindowNum >= thresholdPerMin) {
            return false;
        }

        //计数器+1
        counters.get(currentWindowTime)++;
        return true;
    }

   /**
    * 统计当前窗口的请求数
    */
    private int countCurrentWindow(long currentWindowTime) {
        //计算窗口开始位置
        long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1);
        int count = 0;

        //遍历存储的计数器
        Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Long, Integer> entry = iterator.next();
            // 删除无效过期的子窗口计数器
            if (entry.getKey() < startTime) {
                iterator.remove();
            } else {
                //累加当前窗口的所有计数器之和
                count =count + entry.getValue();
            }
        }
        return count;
    }

スライディング ウィンドウ アルゴリズムは

固定ウィンドウの重大な問題を解決しますが、現在の制限に達すると、リクエストは直接かつ暴力的に拒否されます。 Jiangzi、リクエストの一部は失われますが、これは実際には製品にとってあまり親切ではありません。

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

リーキー バケット アルゴリズムは、現在の制限に直面した場合により柔軟であり、直接的で暴力的な拒否はありません。

その原理は非常に単純で、

水の注入と漏水のプロセスと考えることができます。漏れのあるバケツにはどのような速度でも水が流入し、一定の速度で水が流出します。水がバケツの容量を超えると、水はオーバーフロー、つまり廃棄されます。バケット容量が変わらないため、全体的な速度が保証されます。

水滴の流入はシステムへのアクセス要求とみなせますが、流入量は不確かです。

桶的容量一般表示系统所能处理的请求数。

如果桶的容量满了，就达到限流的阀值，就会丢弃水滴（拒绝请求）

流出的水滴，是恒定过滤的，对应服务按照固定的速率处理请求。

漏桶算法伪代码实现如下：

 /**
     * 每秒处理数（出水率）
     */
    private long rate;

    /**
     *  当前剩余水量
     */
    private long currentWater;

    /**
     * 最后刷新时间
     */
    private long refreshTime;

    /**
     * 桶容量
     */
    private long capacity;

    /**
     * 漏桶算法
     * @return
     */
    boolean leakybucketLimitTryAcquire() {
        long currentTime = System.currentTimeMillis();  //获取系统当前时间
        long outWater = (currentTime - refreshTime) / 1000 * rate; //流出的水量 =(当前时间-上次刷新时间)* 出水率
        long currentWater = Math.max(0, currentWater - outWater); // 当前水量 = 之前的桶内水量-流出的水量
        refreshTime = currentTime; // 刷新时间

        // 当前剩余水量还是小于桶的容量，则请求放行
        if (currentWater < capacity) {
            currentWater++;
            return true;
        }
        
        // 当前剩余水量大于等于桶的容量，限流
        return false;
    }

在正常流量的时候，系统按照固定的速率处理请求，是我们想要的。但是面对突发流量的时候，漏桶算法还是循规蹈矩地处理请求，这就不是我们想看到的啦。流量变突发时，我们肯定希望系统尽量快点处理请求，提升用户体验嘛。

令牌桶算法

面对突发流量的时候，我们可以使用令牌桶算法限流。

令牌桶算法原理：

• 有一个令牌管理员，根据限流大小，定速往令牌桶里放令牌。

• 如果令牌数量满了，超过令牌桶容量的限制，那就丢弃。

• 系统在接受到一个用户请求时，都会先去令牌桶要一个令牌。如果拿到令牌，那么就处理这个请求的业务逻辑；

• 如果拿不到令牌，就直接拒绝这个请求。

漏桶算法伪代码实现如下：

    /**
     * 每秒处理数（放入令牌数量）
     */
    private long putTokenRate;
    
    /**
     * 最后刷新时间
     */
    private long refreshTime;

    /**
     * 令牌桶容量
     */
    private long capacity;
    
    /**
     * 当前桶内令牌数
     */
    private long currentToken = 0L;

    /**
     * 漏桶算法
     * @return
     */
    boolean tokenBucketTryAcquire() {

        long currentTime = System.currentTimeMillis();  //获取系统当前时间
        long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate; //生成的令牌 =(当前时间-上次刷新时间)* 放入令牌的速率
        currentToken = Math.min(capacity, generateToken + currentToken); // 当前令牌数量 = 之前的桶内令牌数量+放入的令牌数量
        refreshTime = currentTime; // 刷新时间
        
        //桶里面还有令牌，请求正常处理
        if (currentToken > 0) {
            currentToken--; //令牌数量-1
            return true;
        }
        
        return false;
    }

如果令牌发放的策略正确，这个系统即不会被拖垮，也能提高机器的利用率。Guava的RateLimiter限流组件，就是基于令牌桶算法实现的。

以上がJava での古典的な電流制限アルゴリズムの分析例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。