Redis常見限流算法原理及實現

Posted on by

前言

在高並發系統中，我們通常需要通過各種手段來提供系統的可以用性，例如緩存、降級和限流等，本文將針對應用中常用的限流算法進行詳細的講解。

簡介

限流簡稱流量限速(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常見限流算法原理及實現的文章就介紹到這瞭,更多相關Redis限流算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：