Redis常見限流演算法原理是什麼及如何實現

簡介

限流簡稱流量限速(Rate Limit)是指只允許指定的事件進入系統，超過的部分將被拒絕服務、排隊或等待、降級等處理.

常見的限流方案如下：

固定時間視窗

固定時間視窗是最常見的限流演算法之一。其中視窗的概念，對應限流場景當中的限流時間單元。

原理

• 時間軸分割成多個獨立且固定大小視窗；

• 落在每一個時間視窗內的請求就將計數器加1；

• 如果計數器超過了限流閾值，則後續落在該視窗的請求都會被拒絕。但當時間達到下一個時間視窗時，計數器會被重設為0。

範例說明

#說明：如上圖場景是每秒鐘限流10次，窗口的大小為1秒，每個方塊代表一個請求，綠色的方塊代表正常的請求，紅色的方法代表被限流的請求，在每秒10次的場景中，從左往右當來看，當進入10個請求後，後面的請求都會被限流。

優缺點

優點：

• #邏輯簡單、維護成本比較低;

#缺點：

視窗切換時無法保證限流值。

相關實作

固定時間視窗的具體實現，可以採用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次，超過了次數會提示錯誤。

滑動時間視窗

滑動時間視窗演算法是對固定時間視窗演算法的一種改進，在滑動視窗的演算法中，同樣需要針對目前的請求來動態查詢視窗。但視窗中的每一個元素，都是子視窗。子窗口的概念類似方案一中的固定窗口，子窗口的大小是可以動態調整的。

實作原理

• 將單位時間分成多個區間，一般都是皆分為多個小的時間段；

• 每一個區間內都有一個計數器，有一個請求落在該區間內，則該區間內的計數器就會加一；

• 每過一個時間段，時間窗口就會往右滑動一格，拋棄最老的一個區間，並納入新的一個區間；

• 計算整個時間窗口內的請求總數時會累加所有的時間片段內的計數器，計數總和超過了限制數量，則本視窗內所有的請求都被丟棄。

範例說明

#說明：例如上圖中的場景是每分鐘限流100次。每一個子視窗的時間維度設定為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中文網其他相關文章！