Redis の一般的な電流制限アルゴリズムの原理とその実装方法は何ですか?

はじめに

レート制限とは、指定されたイベントのみがシステムに入るようにすることを指します。超過したイベントは、サービスが拒否されたり、キューに入れられたり待機されたり、ダウングレードされたりします。

一般的な電流制限スキームは次のとおりです。

固定時間ウィンドウ

固定時間ウィンドウは、最も一般的な電流制限アルゴリズムの 1 つです。ウィンドウの概念は、電流制限シナリオにおける電流制限時間単位に対応します。

原則

• タイムラインは複数の独立した固定サイズのウィンドウに分割され、

• は各時間ウィンドウ内に収まります。リクエストが発生すると、カウンタは 1 ずつ増分されます。

• カウンタが現在の制限しきい値を超えると、このウィンドウ内にある後続のリクエストは拒否されます。ただし、時間が次の時間枠に達すると、カウンターは 0 にリセットされます。

例の説明

手順: 上記のシナリオでは、フローを 1 回あたり 10 回に制限します。サイズは 1 秒で、各四角形はリクエストを表し、緑色の四角形は通常のリクエストを表し、赤色のメソッドは電流制限されたリクエストを表します。1 秒あたり 10 回のシナリオでは、左から順に見ると、右、「After 10 requests」と入力すると、後続のリクエストは抑制されます。

利点と欠点

利点:

• ##シンプルなロジックと比較的低いメンテナンスコスト;

欠点:

ウィンドウ切り替え時の電流制限値は保証されません。

関連実装

固定時間ウィンドウの特定の実装は、Redis を使用して Lua 電流制限スクリプトを呼び出すことで実装できます。

電流制限スクリプト

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)

特定の実装

   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;
   }

テスト

 @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);
    }

説明: テストは 3 秒ごとにアクセスされます。この数を超えると、エラーが表示されます。

スライディング タイム ウィンドウ

スライディング タイム ウィンドウ アルゴリズムは、固定タイム ウィンドウ アルゴリズムを改良したもので、スライディング ウィンドウ アルゴリズムでは、現在のリクエストについてウィンドウを動的にクエリする必要もあります。ただし、ウィンドウ内のすべての要素は子ウィンドウです。サブウィンドウの概念は解決策 1 の固定ウィンドウに似ており、サブウィンドウのサイズは動的に調整できます。

実装原則

• 単位時間を複数の間隔に分割し、通常は複数の短い期間に均等に分割します。

• ありは各間隔のカウンタです。リクエストがその間隔内にある場合、その間隔のカウンタは 1 つ増加します。

• 期間が経過するたびに、時間ウィンドウは 1 スペースずつスライドします。右側に、最も古い間隔を破棄し、新しい間隔を含めます。

• 時間ウィンドウ全体のリクエストの合計数を計算する場合、すべてのリクエストが累積されます。時間セグメント内のカウンターの数が制限を超えると、このウィンドウ内のすべてのリクエストが破棄されます。

例の説明

手順: たとえば、上の図のシナリオでは、毎分100回まで流します。各サブウィンドウの時間ディメンションは 1 秒に設定されているため、1 分のウィンドウには 60 個のサブウィンドウがあります。このように、リクエストが来るたびにこのウィンドウを動的に計算する場合、最大 60 回見つける必要があります。時間計算量は線形から一定レベルに変化し、時間計算量は比較的低くなります。

具体的な実装方法

スライディングタイムウィンドウの実装については、sentinelを利用することができますが、sentinelの使い方については後ほど詳しく説明します。

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

漏斗アルゴリズムでは、まず漏斗を水で満たし、その後一定の速度で流出します。流入する水の量が流出する水の量を超えると、過剰な水は捨てられる。リクエスト量が現在の制限しきい値を超えると、サーバー キューはリーキー バケットのように動作します。したがって、追加のリクエストはサービスを拒否されます。リーキーバケットアルゴリズムはキューを利用して実装されており、トラフィックのアクセス速度を一定に制御し、トラフィックの平滑化を実現します。

原則

説明:

• 各リクエストを固定サイズに入れるキューは進行中です

• キューはリクエストを一定の速度で流出させ、キューが空になると流出を停止します。

#キューがいっぱいの場合、冗長なリクエストは直接拒否されます
特定の実装

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("请求频繁");
                    }
                }
            });
        }
    }

トークン バケット アルゴリズム

トークンバケットアルゴリズムはリーキーバケットをベースに改良したもので、トークンバケットでは現在のシステムで許可されるリクエストの上限をトークンが表しており、一定の速度でトークンがバケットに投入されます。バケットがいっぱいになると、新しいトークンは破棄されます。

原則

トークンは生成され、固定レートでバケットに配置されます。トークンバケット;

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

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

具体实现

@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个是请求频繁的。

小结

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

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

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

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

以上がRedis の一般的な電流制限アルゴリズムの原理とその実装方法は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。