Was ist das Prinzip des gemeinsamen Strombegrenzungsalgorithmus von Redis und wie wird er implementiert?

Einführung

Ratenlimit bezieht sich darauf, nur bestimmten Ereignissen den Zugang zum System zu erlauben. Der Überschuss wird verweigert, in die Warteschlange gestellt oder abgewartet, herabgestuft usw.# 🎜🎜#

Übliche Strombegrenzungsschemata sind wie folgt:

Festes Zeitfenster

# 🎜🎜#Festes Zeitfenster ist einer der gebräuchlichsten Strombegrenzungsalgorithmen. Das Konzept des Fensters entspricht der Strombegrenzungszeiteinheit im Strombegrenzungsszenario.

Prinzip

Die Zeitleiste ist in mehrere unabhängige Fenster mit fester Größe unterteilt; # 🎜🎜#Der Zähler wird für jede Anfrage, die in das Zeitfenster fällt, um 1 erhöht;
Wenn der Zähler den aktuellen Grenzwert überschreitet, fallen nachfolgende Anfragen in diesen Zeitfenster Fenster wird abgelehnt. Wenn die Zeit jedoch das nächste Zeitfenster erreicht, wird der Zähler auf 0 zurückgesetzt. #🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜##Beispiel Beschreibung#🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜##Anweisungen:
• Wie gezeigt Das obige Szenario besteht darin, den aktuellen Fluss 10 Mal pro Sekunde zu begrenzen, die Fenstergröße beträgt 1 Sekunde, jedes Quadrat stellt eine Anforderung dar, das grüne Quadrat stellt eine normale Anforderung dar und die rote Methode stellt eine begrenzte Anforderung dar 10 Mal pro Sekunde, von links nach rechts gesehen, nachdem 10 Anfragen eingegeben wurden, werden alle nachfolgenden Anfragen durchflussbegrenzt.
  Vor- und Nachteile

• Vorteile:

Einfache Logik und vergleichende Wartung Kosten Niedrig;

Nachteile:

Der aktuelle Grenzwert kann beim Umschalten des Fensters nicht garantiert werden.

Verwandte ImplementierungDie spezifische Implementierung des festen Zeitfensters kann implementiert werden, indem Redis verwendet wird, um das Lua-Strombegrenzungsskript aufzurufen.

Ratenbegrenzungsskript

• local key = KEYS[1]
  local count = tonumber(ARGV[1])
  local time = tonumber(ARGV[2])
  local current = redis.call('get', key)
  if current and tonumber(current) > count then
      return tonumber(current)
  end
  current = redis.call('incr', key)
  if tonumber(current) == 1 then
      redis.call('expire', key, time)
  end
  return tonumber(current)

  Spezifische Implementierung

     public Long ratelimiter(String key ,int time,int count) throws IOException
     {
         Resource resource = new ClassPathResource("ratelimiter.lua");
         String redisScript = IOUtils.toString(resource.getInputStream(), StandardCharsets.UTF_8);
         List<String> keys = Collections.singletonList(key);
         List<String> args = new ArrayList<>();
         args.add(Integer.toString(count));
         args.add(Integer.toString(time));
  
         long result = redisTemplate.execute(new RedisCallback<Long>() {
             @Override
             public Long doInRedis(RedisConnection connection) throws DataAccessException {
                 Object nativeConnection = connection.getNativeConnection();
                 if (nativeConnection instanceof Jedis) 
                 {
                     return (Long) ((Jedis) nativeConnection).eval(redisScript, keys, args);
                 }
                 return -1l;
             }
         });
         return result;
     }

Test

 @RequestMapping(value = "/RateLimiter", method = RequestMethod.GET)
    public String RateLimiter() throws IOException 
    {
         int time=3;
         int count=1;
         String key="redis:ratelimiter";
         Long number=redisLockUtil.ratelimiter(key, time, count);
         logger.info("count:{}",number);
         Map<String, Object> map =new HashMap<>();
         if(number==null || number.intValue()>count)
         {
             map.put("code", "-1");
             map.put("msg", "访问过于频繁，请稍候再试");
         }else{
             map.put("code", "200");
             map.put("msg", "访问成功");
         }
         return JSON.toJSONString(map);
    }

Beschreibung: #🎜 🎜 #Der Test besteht darin, alle 3 Sekunden einmal zuzugreifen. Wenn die Anzahl überschritten wird, wird ein Fehler angezeigt.

Sliding Time Window

Der Sliding Time Window-Algorithmus ist eine Verbesserung gegenüber dem Fixed Time Window-Algorithmus. Beim Sliding Time Window-Algorithmus sind auch dynamische Abfragen für die aktuelle Anfrage erforderlich. Fenster. Aber jedes Element im Fenster ist ein untergeordnetes Fenster. Das Konzept des Unterfensters ähnelt dem festen Fenster in Lösung 1 und die Größe des Unterfensters kann dynamisch angepasst werden.

Implementierungsprinzip

Teilen Sie die Zeiteinheit in mehrere Intervalle auf, im Allgemeinen in mehrere kleine Zeiträume unterteilt;#🎜 🎜#

In jedem Intervall gibt es einen Zähler. Wenn eine Anfrage in das Intervall fällt, wird der Zähler im Intervall um eins erhöht #Jedes Mal, wenn ein Zeitraum vergeht, verschiebt sich das Zeitfenster um eine Stelle nach rechts, wobei das älteste Intervall verworfen und ein neues Intervall einbezogen wird Anzahl der Anfragen im gesamten Zeitfenster werden die Zähler in allen Zeitsegmenten akkumuliert. Wenn die Gesamtzahl das Limit überschreitet, werden alle Anfragen in diesem Fenster verworfen.

Beispielbeschreibung

Anleitung:

Zum Beispiel , oben Das Szenario im Bild besteht darin, den Durchfluss auf 100 Mal pro Minute zu begrenzen. Die Zeitdimension jedes Unterfensters ist auf 1 Sekunde festgelegt, sodass ein einminütiges Fenster 60 Unterfenster hat. Auf diese Weise müssen wir jedes Mal, wenn eine Anfrage eingeht und dieses Fenster dynamisch berechnet, bis zu 60 Mal finden. Die Zeitkomplexität hat sich von einem linearen zu einem konstanten Niveau geändert, und die Zeitkomplexität wird relativ geringer sein.

• Spezifische Implementierung
  Bezüglich der Implementierung des gleitenden Zeitfensters können Sie Sentinel verwenden. Die Verwendung von Sentinel wird später ausführlich erläutert.
• Leaky-Bucket-Algorithmus
  Der Trichteralgorithmus besteht darin, den Trichter zuerst mit Wasser zu füllen und dann mit einer festen Rate auszufließen, wenn die Menge des einströmenden Wassers die ausströmende Wassermenge übersteigt , das überschüssige Wasser wird weggeworfen. Wenn das Anforderungsvolumen den aktuellen Grenzwert überschreitet, verhält sich die Serverwarteschlange wie ein Leaky Bucket. Daher wird die Bearbeitung zusätzlicher Anfragen verweigert. Der Leaky-Bucket-Algorithmus wird mithilfe von Warteschlangen implementiert, die die Zugriffsgeschwindigkeit des Datenverkehrs mit einer festen Rate steuern und eine Glättung des Datenverkehrs erreichen können. #🎜🎜 ## 🎜🎜#Prinzip#🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜#Beschreibung:#🎜🎜 ## 🎜🎜 ## 🎜🎜 ## 🎜🎜 🎜🎜 #
Stellen Sie jede Anfrage in eine Warteschlange mit fester Größe ist leer.
Wenn die Warteschlange voll ist, werden redundante Anfragen direkt abgelehnt
Spezifische Implementierung

long timeStamp = System.currentTimeMillis(); //当前时间
    long  capacity = 1000;// 桶的容量
    long  rate = 1;//水漏出的速度
    long  water = 100;//当前水量
    public boolean leakyBucket()
    {
        //先执行漏水，因为rate是固定的，所以可以认为“时间间隔*rate”即为漏出的水量
        long  now = System.currentTimeMillis();
        water = Math.max(0, water -(now-timeStamp) * rate);
        timeStamp = now;
        // 水还未满，加水
        if (water < capacity)
        {
            water=water+100;
            return true;
        }
        //水满，拒绝加水
        else
        {
          return false;
        }
    }
    @RequestMapping(value="/leakyBucketLimit",method = RequestMethod.GET)
    public void leakyBucketLimit() 
    {
        for(int i=0;i<20;i++) {
            fixedThreadPool.execute(new Runnable() 
            {
                @Override
                public void run() 
                {
                    if(leakyBucket()) 
                    {
                        logger.info("thread name:"+Thread.currentThread().getName()+" "+sdf.format(new Date()));
                    }
                    else 
                    {
                       logger.error("请求频繁");
                    }
                }
            });
        }
    }

Token-Bucket-Algorithmus

Der Token-Bucket-Algorithmus ist eine verbesserte Version, die auf dem Leaky-Bucket basiert. Im Token-Bucket stellt der Token die Obergrenze der vom aktuellen System zugelassenen Anforderungen dar Die Karten werden mit konstanter Geschwindigkeit in den Eimer gelegt. Wenn der Bucket voll ist, werden neue Token verworfen. #Token werden mit einer festen Rate generiert und in den Token-Bucket gelegt ;

如果令牌桶满了则多余的令牌会直接丢弃，当请求到达时，会尝试从令牌桶中取令牌，取到了令牌的请求可以执行；

如果桶空了,则拒绝该请求。

具体实现

@RequestMapping(value="/ratelimit",method = RequestMethod.GET)
    public void ratelimit()
    {
        //每1s产生0.5个令牌，也就是说接口2s只允许调用1次
        RateLimiter rateLimiter=RateLimiter.create(0.5,1,TimeUnit.SECONDS);

        for(int i=0;i<10;i++) {
            fixedThreadPool.execute(new Runnable() 
            {
                @Override
                public void run() 
                {
                    //获取令牌最大等待10秒
                    if(rateLimiter.tryAcquire(1,10,TimeUnit.SECONDS)) 
                    {
                        logger.info("thread name:"+Thread.currentThread().getName()+" "+sdf.format(new Date()));
                    }
                    else 
                    {
                       logger.error("请求频繁");
                    }
                }
            });
        }
    }

执行结果：

-[pool-1-thread-3] ERROR 请求频繁
[pool-1-thread-2] ERROR  请求频繁
[pool-1-thread-1] INFO   thread name:pool-1-thread-1 2022-08-07 15:44:00
[pool-1-thread-8] ERROR []  - 请求频繁
[pool-1-thread-9] ERROR []  - 请求频繁
[pool-1-thread-10] ERROR [] - 请求频繁
[pool-1-thread-7] INFO  []  - thread name:pool-1-thread-7 2022-08-07 15:44:03
 [pool-1-thread-6] INFO  [] - thread name:pool-1-thread-6 2022-08-07 15:44:05
[pool-1-thread-5] INFO  []  - thread name:pool-1-thread-5 2022-08-07 15:44:07
[pool-1-thread-4] INFO  []  - thread name:pool-1-thread-4 2022-08-07 15:44:09

说明：接口限制为每2秒请求一次，10个线程需要20s才能处理完，但是rateLimiter.tryAcquire限制了10s内没有获取到令牌就抛出异常，所以结果中会有5个是请求频繁的。

小结

• 固定窗口：实现简单，适用于流量相对均匀分布，对限流准确度要求不严格的场景。

• 滑动窗口：适用于对准确性和性能有一定的要求场景，可以调整子窗口数量来权衡性能和准确度

• 漏桶：适用于流量绝对平滑的场景

• 令牌桶：适用于流量整体平滑的情况下，同时也可以满足一定的突发流程场景

Das obige ist der detaillierte Inhalt vonWas ist das Prinzip des gemeinsamen Strombegrenzungsalgorithmus von Redis und wie wird er implementiert?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!