Beispielanalyse des klassischen Strombegrenzungsalgorithmus in Java

Was ist Ratenbegrenzung?

Das Konzept von Wikipedia ist wie folgt:

In Computernetzwerken wird Ratenbegrenzung verwendet, um die Rate zu steuern Von einem Netzwerkschnittstellen-Controller gesendete oder empfangene Anfragen können verwendet werden, um DoS-Angriffe zu verhindern und Web Scraping zu begrenzen zum Senden oder Empfangen Die Rate der Anfragen, die DoS-Angriffe verhindert und Webcrawler einschränkt.

Strombegrenzung, auch Flusskontrolle genannt. Dies bedeutet, dass, wenn das System mit hoher Parallelität oder

großen Datenverkehrsanfragen

konfrontiert ist, es

neue Anfragen für den Zugriff auf das System einschränkt und dadurch die Stabilität des Systems gewährleistet Sex . Die aktuelle Beschränkung führt dazu, dass einige Benutzeranfragen nicht rechtzeitig verarbeitet oder abgelehnt werden, was sich auf die Benutzererfahrung auswirkt. Daher ist es im Allgemeinen notwendig, eine Balance zwischen Systemstabilität und Benutzererfahrung zu finden. Um ein Beispiel aus dem täglichen Leben zu nennen: ★ Einige beliebte Touristenattraktionen haben generell Beschränkungen hinsichtlich der Anzahl der täglichen Besucher. Es wird täglich nur eine festgelegte Anzahl an Tickets verkauft, beispielsweise 5.000. Wenn Sie während der Feiertage zum 1. Mai oder zum Nationalfeiertag verspätet anreisen, sind die Tickets für diesen Tag möglicherweise ausverkauft und Sie können nicht vor Ort sein und spielen. Selbst wenn Sie einsteigen, wird die Warteschlange Sie an Ihrem Leben zweifeln lassen.

”

Gemeinsamer Strombegrenzungsalgorithmus

Strombegrenzungsalgorithmus mit festem Fenster

Behalten Sie zunächst einen Zähler bei und behandeln Sie den Einheitszeitraum als Fenster, der Zähler zeichnet auf, wie oft dieses Fenster Anfragen empfängt 1

#🎜 🎜#

Wenn die Anzahl größer als der aktuelle Grenzwert ist, wird der Zugriff verweigert

• Nach dem Strom Das Zeitfenster ist abgelaufen, der Zähler wird gelöscht. Jedes Mal, wenn eine Anfrage eingeht, erhöht sich der Zähler um 1. Wenn der Zähler den aktuellen Grenzwert von 3 überschreitet, werden alle nachfolgenden Anfragen abgelehnt. Nach Ablauf von 1 Sekunde wird der Zähler auf 0 zurückgesetzt und beginnt zu zählen noch einmal:

• Der Pseudocode lautet wie folgt:

    /**
     * 固定窗口时间算法
     * @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;
    }

• Dieser Algorithmus hat jedoch einen offensichtlichen

  kritischen Wert Problem

  : Angenommen, der aktuelle Grenzschwellenwert beträgt 5 Anfragen und das Einheitszeitfenster beträgt 1 Sekunde, wenn wir in den ersten 0,8-1 Sekunden und 1-1,2 Sekunden der Zeiteinheit gleichzeitig 5 Anfragen senden, obwohl diese nicht überschritten werden Wenn wir den Schwellenwert von 0,8 bis 1,2 Sekunden zählen, liegt die Anzahl der gleichzeitigen Anforderungen bei
. Die Zeiteinheit 1s überschreitet nicht den Schwellenwert von 5

, der die Fensterstrombegrenzung löst Das Problem fester Fensterschwellenwerte unterteilt den Einheitszeitraum in n kleine Zeiträume, zeichnet die Anzahl der Zugriffe auf die Schnittstelle in jedem kleinen Zeitraum auf und löscht abgelaufene kleine Zeiträume basierend auf der Zeitverschiebung 🎜🎜#Ein Bild erklärt das Schiebefenster Algorithmus wie folgt:

Unter der Annahme, dass die Einheitszeit immer noch 1s beträgt, teilt der Schiebefensteralgorithmus sie in 5 kleine Perioden, das heißt das Schieben Das Fenster (Einheitszeit) ist in 5 kleine Raster unterteilt. Nach jeweils 0,2 Sekunden verschiebt sich das Zeitfenster um ein Raster nach rechts. Wenn die Anforderung in 0,83 Sekunden eintrifft s wird der Zähler, der 0,8 bis 1,0 s entspricht, um 1 erhöht.

Sehen wir uns an, wie das Schiebefenster das kritische Problem löst? , und 5 Anfragen kommen innerhalb von 0,8 bis 1,0 Sekunden (z. B. 0,9 Sekunden) und fallen nach dem 1,0-Sekunden-Punkt in das violette Raster. Wenn

ein fester Fensteralgorithmus ist , es wird nicht begrenzt , aber wenn ein Schiebefenster ist, wird es in jedem kleinen Zeitraum begrenzt Nach dem Passieren des 1,0s-Punkts Die aktuelle Zeitspanne beträgt 0,2 bis 1,2 Sekunden. Die Anzahl der Anfragen in diesem Bereich wurde überschritten. Leider wurden alle Anfragen für violette Gitter abgelehnt.

TIPPS: Je mehr Rasterperioden das Schiebefenster unterteilt ist, desto glatter wird das Rollfenster und desto genauer ist die Strombegrenzungsstatistik.

Schiebefensteralgorithmus

Pseudocode-Implementierung

lautet wie folgt:

 /**
     * 单位时间划分的小周期（单位时间是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;
    }

Obwohl der Schiebefensteralgorithmus das kritische Problem von

behoben löst window#🎜 🎜#, aber sobald das aktuelle Limit erreicht ist, wird die Anfrage direkt und gewaltsam abgelehnt. Jiangzi, wir werden einen Teil der Anfragen verlieren, was eigentlich nicht sehr produktfreundlich ist.

Leaky-Bucket-Algorithmus

Der Leaky-Bucket-Algorithmus ist angesichts der Strombegrenzung flexibler und es gibt keine direkte grobe Ablehnung.

Das Prinzip ist sehr einfach, man kann es sich als den Prozess der

Wassereinspritzung und -leckage

vorstellen. Wasser fließt auf jeden Fall in den undichten Eimer und das Wasser fließt mit einer festen Geschwindigkeit wieder heraus. Wenn das Wasser das Fassungsvermögen des Eimers überschreitet, läuft es über, das heißt, es wird entsorgt. Da die Schaufelkapazität unverändert bleibt, ist die Gesamtgeschwindigkeit gewährleistet.

Die einströmenden Wassertropfen können als Anfragen zum Zugang zum System angesehen werden.

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

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

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

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

 /**
     * 每秒处理数（出水率）
     */
    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限流组件，就是基于令牌桶算法实现的。

Das obige ist der detaillierte Inhalt vonBeispielanalyse des klassischen Strombegrenzungsalgorithmus in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!