Exemple d'analyse de l'algorithme classique de limitation de courant en Java

Qu'est-ce que la limitation de débit ?

Le concept de Wikipédia est le suivant :

Dans les réseaux informatiques, la limitation de débit est utilisée pour contrôler le débit de requêtes envoyées ou reçues par un contrôleur d'interface réseau. Elle peut être utilisée pour empêcher les attaques DoS. et limiter le Web scraping

Une traduction simple : dans les réseaux informatiques, la limitation de flux consiste à contrôler la vitesse à laquelle l'interface réseau envoie ou reçoit des requêtes. Elle peut empêcher les attaques DoS et limiter les robots d'exploration Web.

Limitation de courant, également appelée contrôle de débit. Cela signifie que lorsque le système est confronté à une concurrence élevée ou à des demandes de trafic importantes, il limite l'accès des nouvelles requêtes au système, assurant ainsi la stabilité du système. La limitation actuelle entraînera le traitement intempestif ou le rejet de certaines demandes d'utilisateurs, ce qui affectera l'expérience utilisateur. Par conséquent, il est généralement nécessaire de trouver un équilibre entre la stabilité du système et l’expérience utilisateur. Pour donner un exemple tiré de la vie quotidienne : ★

Certaines attractions touristiques populaires ont généralement des restrictions sur le nombre de visiteurs quotidiens. Seul un nombre fixe de billets sera vendu chaque jour, par exemple 5 000. Si vous arrivez en retard pendant les vacances du 1er mai ou de la fête nationale, les billets pour la journée risquent d'être épuisés et vous ne pourrez pas entrer et jouer. Même si vous entrez, la file d'attente vous fera douter de votre vie.

”

Algorithme de limitation de courant commun

Algorithme de limitation de courant à fenêtre fixe

Maintenez d'abord un compteur, traitez la période de temps de l'unité comme une fenêtre, et le compteur enregistre le nombre de demandes reçues dans cette fenêtre.

Lorsque le le nombre est inférieur au seuil limite actuel, l'accès est autorisé et le compteur +1
Lorsque le nombre est supérieur au seuil limite actuel, l'accès est refusé
Une fois la fenêtre horaire actuelle écoulée, le compteur est effacé.
Supposons que le temps unitaire soit de 1 seconde, le seuil de limitation actuel est de 3. Dans le temps unitaire de 1 seconde, chaque fois qu'une demande arrive, le compteur augmente de 1. Si le nombre accumulé de compteurs est atteint. dépasse le seuil limite actuel de 3, toutes les demandes ultérieures seront rejetées après 1 seconde. Le compteur est remis à 0 et le comptage recommence comme indiqué ci-dessous :

Le pseudo-code est le suivant :

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

Cependant, cet algorithme a un

problème critique

évident : supposons que le seuil limite actuel est de 5 requêtes par unité de temps. Si nous envoyons simultanément 5 requêtes dans les premières 0,8-1 s et 1-1,2 s du temps unitaire, bien qu'elles ne dépassent pas le seuil, si l'on compte 0,8 à 1,2 s, le nombre de requêtes simultanées atteint 10, ce qui est déjà La définition de dépassant le seuil de 5

. Algorithme de limitation de courant par fenêtre coulissante

La limitation de courant par fenêtre coulissante résout le problème de la valeur critique de fenêtre fixe. Elle divise la période de temps unitaire en n petites périodes. Enregistrez le nombre d'accès à l'interface dans chaque petite période et supprimez les petites périodes expirées en fonction. sur le glissement du temps.

Une image explique l'algorithme de la fenêtre glissante, comme suit :

En supposant que l'unité de temps est toujours de 1 seconde, l'algorithme de la fenêtre glissante la prend. Elle est divisée en 5 petites périodes, c'est-à-dire le temps. la fenêtre glissante (unité de temps) est divisée en 5 petites grilles. Chaque grille représente 0,2s, et la fenêtre temporelle glissera d'une grille vers la droite. Chaque cycle a son propre compteur indépendant. Si la demande arrive en 0,83s, le compteur correspondant. à 0,8~1,0s sera incrémenté de 1.

Voyons comment la fenêtre coulissante résout le problème critique

Supposons que nous ayons 1 seconde, le seuil de limitation actuel est toujours de 5 requêtes dans un délai de 0,8~1,0s. à 0,9 s), 5 requêtes sont venues et sont tombées dans la grille jaune. Après le point de 1,0 s, 5 autres requêtes sont venues et sont tombées dans la grille violette. Si

est un algorithme de fenêtre fixe, il ne sera pas limité en courant

, mais. si est une fenêtre coulissante, elle se déplacera d'une petite grille vers la droite après chaque petite période Elle se déplacera d'un petit carré vers la droite. La période de temps unitaire actuelle est de 0,2 à 1,2 s. la limite de 5, et la limite actuelle a été déclenchée. En fait, toutes les demandes dans la grille violette ont été rejetées

CONSEILS :

Plus les périodes de grille de la fenêtre glissante sont divisées, plus le déroulement de la fenêtre glissante est fluide. La fenêtre coulissante sera, et plus les statistiques de la limite actuelle seront précises. L'implémentation du pseudo-code de l'algorithme de fenêtre glissante est la suivante :

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

Algorithme de fenêtre coulissante Bien que le problème critique de la fenêtre fixe. est résolu, une fois la limite actuelle atteinte, la demande sera directement et violemment rejetée. Jiangzi perdra certaines des demandes, ce qui n'est en fait pas très favorable au produit.

Algorithme de seau qui fuitL'algorithme de seau qui fuit est plus flexible face à la limite actuelle, et il n'y a pas de rejet direct et grossier.

Le principe est très simple, il peut être considéré comme le processus d'injection d'eau et de fuite d'eau

. L'eau s'écoule dans le seau qui fuit à tout moment et l'eau s'écoule à un débit fixe. Lorsque l’eau dépasse la capacité du seau, celui-ci débordera, c’est-à-dire sera jeté. La capacité du godet restant inchangée, la vitesse globale est garantie.

Les gouttelettes d'eau entrantes peuvent être considérées comme des demandes d'accès au système. Ce débit d'entrée est incertain.

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

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

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

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

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!