So implementieren Sie gängige Strombegrenzungsalgorithmen in Java

Warum den Zustrom einschränken?

Erhöhen Sie die Anzahl der eintretenden Personen so weit wie möglich und stellen Sie gleichzeitig die Verfügbarkeit sicher. Der Rest der Personen steht in der Schlange oder gibt freundliche Aufforderungen zurück, um sicherzustellen, dass die Benutzer des Das System im Inneren kann normal verwendet werden, um eine Systemlawine zu verhindern.

Strombegrenzungsalgorithmus

Es gibt viele Strombegrenzungsalgorithmen, und es gibt drei gemeinsame Kategorien, nämlich Zähleralgorithmus, Leaky-Bucket-Algorithmus und Token-Bucket-Algorithmus.

(1) Zähler:

Innerhalb eines Zeitraums wird die maximale Anzahl der zu verarbeitenden Anfragen festgelegt und der Überschuss wird nicht bearbeitet.

(2) Leaky-Bucket:

Die Größe des Leaky-Buckets ist festgelegt und die Verarbeitungsgeschwindigkeit ist festgelegt, aber die Anforderungseingabegeschwindigkeit ist nicht festgelegt (wenn zu viele Anforderungen vorhanden sind). im Notfall werden zu viele Anfragen verworfen).

(3) Token-Bucket:

Die Größe des Token-Buckets ist festgelegt, die Geschwindigkeit der Token-Generierung ist festgelegt, aber die Geschwindigkeit des Token-Verbrauchs (dh der Anforderung) ist nicht festgelegt (kann Um mit Situationen umzugehen, in denen zu bestimmten Zeiten zu viele Anfragen eingehen); jede Anfrage nimmt ein Token aus dem Token-Bucket, und wenn kein Token vorhanden ist, wird die Anfrage verworfen.

Gegenstromlimit

Innerhalb eines bestimmten Zeitraums wird die maximale Anzahl der zu bearbeitenden Anfragen festgelegt und der Überschuss wird nicht bearbeitet.

Zum Beispiel legen wir fest, dass wir für Schnittstelle A nicht mehr als 100 Mal in 1 Minute zugreifen dürfen.

Dann können wir Folgendes tun:

Zu Beginn können wir einen Zählerzähler festlegen, der um 1 erhöht wird. Wenn counter Der Wert ist größer als 100 und das Intervall zwischen dieser Anfrage und der ersten Anfrage immer noch innerhalb von 1 Minute liegt, bedeutet dies, dass zu viele Anfragen vorliegen und der Zugriff verweigert wird; Anfrage: Wenn die Zeit länger als 1 Minute ist und der Wert des Zählers immer noch innerhalb des aktuellen Grenzbereichs liegt, dann setzen Sie den Zähler zurück. So einfach und grob ist das.

Code-Implementierung:

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

//计数器 限流
public class CounterLimiter {

    //起始时间
    private static long startTime = System.currentTimeMillis();

    //时间间隔1000ms
    private static long interval = 1000;

    //每个时间间隔内，限制数量
    private static long limit = 3;

    //累加器
    private static AtomicLong accumulator = new AtomicLong();

    /**
     * true 代表放行，请求可已通过
     * false 代表限制，不让请求通过
     */
    public static boolean tryAcquire() {
        long nowTime = System.currentTimeMillis();
        //判断是否在上一个时间间隔内
        if (nowTime < startTime + interval) {
            //如果还在上个时间间隔内
            long count = accumulator.incrementAndGet();
            if (count <= limit) {
                return true;
            } else {
                return false;
            }
        } else {
            //如果不在上一个时间间隔内
            synchronized (CounterLimiter.class) {
                //防止重复初始化
                if (nowTime > startTime + interval) {
                    startTime = nowTime;
                    accumulator.set(0);
                }
            }
            //再次进行判断
            long count = accumulator.incrementAndGet();
            if (count <= limit) {
                return true;
            } else {
                return false;
            }
        }
    }


    // 测试
    public static void main(String[] args) {

        //线程池，用于多线程模拟测试
        ExecutorService pool = Executors.newFixedThreadPool(10);
        // 被限制的次数
        AtomicInteger limited = new AtomicInteger(0);
        // 线程数
        final int threads = 2;
        // 每条线程的执行轮数
        final int turns = 20;
        // 同步器
        CountDownLatch countDownLatch = new CountDownLatch(threads);
        long start = System.currentTimeMillis();
        for (int i = 0; i < threads; i++) {
            pool.submit(() ->
            {
                try {

                    for (int j = 0; j < turns; j++) {

                        boolean flag = tryAcquire();
                        if (!flag) {
                            // 被限制的次数累积
                            limited.getAndIncrement();
                        }
                        Thread.sleep(200);
                    }

                } catch (Exception e) {
                    e.printStackTrace();
                }
                //等待所有线程结束
                countDownLatch.countDown();
            });
        }
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        float time = (System.currentTimeMillis() - start) / 1000F;
        //输出统计结果
        System.out.println("限制的次数为：" + limited.get() +
                ",通过的次数为：" + (threads * turns - limited.get()));
        System.out.println("限制的比例为：" + (float) limited.get() / (float) (threads * turns));
        System.out.println("运行的时长为：" + time + "s");
    }

}

Die Mängel der Gegenstrombegrenzung:

Obwohl dieser Algorithmus ist einfach, aber es gibt ein kritisches Problem. Schauen wir uns das Bild unten an:

Anhand des obigen Bildes können wir erkennen, dass davon ausgegangen wird, dass ein böswilliger Fehler vorliegt Benutzer, er ist bei 0: Um 59:00 Uhr wurden sofort 100 Anfragen gesendet, und um 1:00 Uhr wurden sofort 100 Anfragen gesendet. Tatsächlich hat dieser Benutzer in 1 Sekunde sofort 200 Anfragen gesendet.

Was wir gerade festgelegt haben, ist ein Maximum von 100 Anfragen pro Minute (geplanter Durchsatz), was einem Maximum von 1,7 Anfragen pro Sekunde am Reset-Knoten des Zeitfensters entspricht Ratengrenzen können sofort überschritten werden.

Benutzer können unsere Anwendung durch diese Lücke im Algorithmus sofort zerstören.

Strombegrenzung für undichte Eimer

Das Grundprinzip der Strombegrenzung für undichte Eimer lautet: Wasser (entsprechend der Anforderung) gelangt über den Wassereinlass in den undichten Eimer und der undichte Der Eimer bewegt sich mit einer bestimmten Geschwindigkeit. Wasseraustritt (Freigabe anfordern). Wenn die Wasserzuflussgeschwindigkeit zu hoch ist, ist das Gesamtwasservolumen im Eimer größer als die Eimerkapazität, er läuft direkt über und die Anforderung wird abgelehnt.

Die ungefähren Strombegrenzungsregeln für undichte Eimer lauten wie folgt:

(1) Der Wasserzulauf (entsprechend der Kundenanforderung) fließt auf jeden Fall in den undichten Eimer.

(2) Das Fassungsvermögen des undichten Eimers ist festgelegt, und die Wasseraustrittsrate (Freisetzungsrate) ist ebenfalls festgelegt.

(3) Das Fassungsvermögen des undichten Eimers bleibt unverändert. Wenn die Verarbeitungsgeschwindigkeit zu langsam ist, übersteigt die Wassermenge im Eimer das Fassungsvermögen des Eimers und die Wassertropfen fließen später ein wird überlaufen, was darauf hinweist, dass die Anfrage abgelehnt wurde.

#⭐Der Leaky-Bucket-Algorithmus ist eigentlich sehr einfach, man kann ihn sich auf jeden Fall als den Wasseraustrittsprozess vorstellen und fließt mit einer bestimmten Geschwindigkeit ab, wenn es die Eimerkapazität überschreitet, da die Eimerkapazität unverändert bleibt und die Gesamtgeschwindigkeit gewährleistet ist.

Wasser fließt mit einer bestimmten Geschwindigkeit ab,

Peak Clipping: Wenn eine große Menge an Verkehr eindringt, kommt es zu einem Überlauf , wodurch der Fluss eingeschränkt wird. Schutzdienst ist verfügbar.

Pufferung: Es wird nicht direkt an den Server angefordert, Pufferdruck. Die Mängel des undichten Eimers: #🎜🎜 #

Die Wasseraustrittsgeschwindigkeit des undichten Eimers ist festgelegt, d. h. die angeforderte Freigabegeschwindigkeit ist festgelegt.

Der Auslass des undichten Eimers hat eine feste Geschwindigkeit und kann die Verbesserung der Back-End-Funktionen nicht flexibel bewältigen. Durch dynamische Erweiterung wird beispielsweise der Back-End-Verkehr von 1000 QPS auf 1 WQPS erhöht, und es gibt keine Lösung für Leaky Buckets.

Aktuelles Limit des Token-Buckets

Wenn im Token-Bucket-Algorithmus eine neue Anfrage eintrifft, wird ein Token aus dem Bucket entnommen, wenn kein Token im Bucket verfügbar ist , Denial-of-Service. Natürlich ist auch die Anzahl der Token begrenzt. Die Anzahl der Token hängt stark von der Zeit und der Ausgaberate ab. Je länger die Zeit vergeht, desto mehr Token werden dem Bucket hinzugefügt. Wenn die Token-Ausgabegeschwindigkeit schneller ist als die Anwendungsgeschwindigkeit, wird der Token-Bucket gefüllt. bis die Token den gesamten Token-Bucket belegen.

Die allgemeinen Regeln für die Strombegrenzung im Token-Eimer lauten wie folgt:

(1) Der Wassereinlass führt Token mit einer bestimmten Geschwindigkeit in den Eimer.

（2）令牌的容量是固定的，但是放行的速度不是固定的，只要桶中还有剩余令牌，一旦请求过来就能申请成功，然后放行。

（3）如果令牌的发放速度，慢于请求到来速度，桶内就无牌可领，请求就会被拒绝。

总之，令牌的发送速率可以设置，从而可以对突发的出口流量进行有效的应对。

代码实现： 

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

//令牌桶
public class TokenBucketLimiter {
    //桶的容量
    private static long capacity = 10;
    //放入令牌的速率,每秒2个
    private static long rate = 2;
    //上次放置令牌的时间
    private static long lastTime = System.currentTimeMillis();
    //桶中令牌的余量
    private static AtomicLong tokenNum = new AtomicLong();

    /**
     * true 代表放行，请求可已通过
     * false 代表限制，不让请求通过
     */
    public synchronized static boolean tryAcquire() {
        //更新桶中剩余令牌的数量
        long now = System.currentTimeMillis();
        tokenNum.addAndGet((now - lastTime) / 1000 * rate);
        tokenNum.set(Math.min(capacity, tokenNum.get()));
        //更新时间
        lastTime += (now - lastTime) / 1000 * 1000;
        //桶中还有令牌就放行
        if (tokenNum.get() > 0) {
            tokenNum.decrementAndGet();
            return true;
        } else {
            return false;
        }
    }


    //测试
    public static void main(String[] args) {

        //线程池，用于多线程模拟测试
        ExecutorService pool = Executors.newFixedThreadPool(10);
        // 被限制的次数
        AtomicInteger limited = new AtomicInteger(0);
        // 线程数
        final int threads = 2;
        // 每条线程的执行轮数
        final int turns = 20;
        // 同步器
        CountDownLatch countDownLatch = new CountDownLatch(threads);
        long start = System.currentTimeMillis();
        for (int i = 0; i < threads; i++) {
            pool.submit(() ->
            {
                try {

                    for (int j = 0; j < turns; j++) {

                        boolean flag = tryAcquire();
                        if (!flag) {
                            // 被限制的次数累积
                            limited.getAndIncrement();
                        }
                        Thread.sleep(200);
                    }

                } catch (Exception e) {
                    e.printStackTrace();
                }
                //等待所有线程结束
                countDownLatch.countDown();
            });
        }
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        float time = (System.currentTimeMillis() - start) / 1000F;
        //输出统计结果
        System.out.println("限制的次数为：" + limited.get() +
                ",通过的次数为：" + (threads * turns - limited.get()));
        System.out.println("限制的比例为：" + (float) limited.get() / (float) (threads * turns));
        System.out.println("运行的时长为：" + time + "s");
    }

}

令牌桶的好处： 

令牌桶的好处之一就是可以方便地应对 突发出口流量（后端能力的提升）。

比如，可以改变令牌的发放速度，算法能按照新的发送速率调大令牌的发放数量，使得出口突发流量能被处理。

Das obige ist der detaillierte Inhalt vonSo implementieren Sie gängige Strombegrenzungsalgorithmen in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!