Redis常見限流算法原理及實現(xiàn)
前言
在高并發(fā)系統(tǒng)中，我們通常需要通過各種手段來提供系統(tǒng)的可以用性，例如緩存、降級和限流等，本文將針對應用中常用的限流算法進行詳細的講解。
簡介
限流簡稱流量限速(Rate Limit)是指只允許指定的事件進入系統(tǒng)，超過的部分將被拒絕服務、排隊或等待、降級等處理.
常見的限流方案如下：
固定時間窗口
固定時間窗口是最常見的限流算法之一。其中窗口的概念，對應限流場景當中的限流時間單元。
原理
- 時間線劃分為多個獨立且固定大小窗口；
- 落在每一個時間窗口內的請求就將計數(shù)器加1；
- 如果計數(shù)器超過了限流閾值，則后續(xù)落在該窗口的請求都會被拒絕。但時間達到下一個時間窗口時，計數(shù)器會被重置為0。
示例說明
說明：如上圖場景是每秒鐘限流10次，窗口的大小為1秒，每個方塊代表一個請求，綠色的方塊代表正常的請求，紅色的方法代表被限流的請求，在每秒10次的場景中，從左往右當來看，當進入10個請求后，后面的請求都被會被限流。
優(yōu)缺點
優(yōu)點：
- 邏輯簡單、維護成本比較低；
缺點：
窗口切換時無法保證限流值。
相關實現(xiàn)
固定時間窗口的具體實現(xiàn)，可以采用Redis調用lua限流腳本來實現(xiàn)。
限流腳本
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)具體實現(xiàn)
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次，超過了次數(shù)會提示錯誤。
滑動時間窗口
滑動時間窗口算法是對固定時間窗口算法的一種改進，在滑動窗口的算法中，同樣需要針對當前的請求來動態(tài)查詢窗口。但窗口中的每一個元素，都是子窗口。子窗口的概念類似于方案一中的固定窗口，子窗口的大小是可以動態(tài)調整的。
實現(xiàn)原理
- 將單位時間劃分為多個區(qū)間，一般都是均分為多個小的時間段；
- 每一個區(qū)間內都有一個計數(shù)器，有一個請求落在該區(qū)間內，則該區(qū)間內的計數(shù)器就會加一；
- 每過一個時間段，時間窗口就會往右滑動一格，拋棄最老的一個區(qū)間，并納入新的一個區(qū)間；
- 計算整個時間窗口內的請求總數(shù)時會累加所有的時間片段內的計數(shù)器，計數(shù)總和超過了限制數(shù)量，則本窗口內所有的請求都被丟棄。
示例說明
說明：比如上圖中的場景是每分鐘限流100次。每一個子窗口的時間維度設置為1秒，那么一分鐘的窗口有60個子窗口。這樣每當一個請求來了之后，我們去動態(tài)計算這個窗口的時候，我們最多需找60次。時間復雜度,從線性變成常量級了，時間的復雜度相對來說也會更低了。
具體實現(xiàn)
關于滑動時間窗的實現(xiàn)，可以采用sentinel，關于sentinel的使用后續(xù)將詳細進行講解。
漏桶算法
漏桶算法是水先進入到漏桶里，漏桶再以一定的速率出水，當流入水的數(shù)量大于流出水時，多余的水直接溢出。把水換成請求來看，漏桶相當于服務器隊列，但請求量大于限流閾值時，多出來的請求就會被拒絕服務。漏桶算法使用隊列實現(xiàn)，可以以固定的速率控制流量的訪問速度，可以做到流量的平整化處理。
原理
說明：
- 將每個請求放入固定大小的隊列進行中
- 隊列以固定速率向外流出請求，如果隊列為空則停止流出。
- 如隊列滿了則多余的請求會被直接拒絕
具體實現(xiàn)
long timeStamp = System.currentTimeMillis(); //當前時間
long capacity = 1000;// 桶的容量
long rate = 1;//水漏出的速度
long water = 100;//當前水量
public boolean leakyBucket()
{
//先執(zhí)行漏水，因為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("請求頻繁");
}
}
});
}
}令牌桶算法
令牌桶算法是基于漏桶之上的一種改進版本，在令牌桶中，令牌代表當前系統(tǒng)允許的請求上限，令牌會勻速被放入桶中。當桶滿了之后，新的令牌就會被丟棄
原理
- 令牌以固定速率生成并放入到令牌桶中；
- 如果令牌桶滿了則多余的令牌會直接丟棄，當請求到達時，會嘗試從令牌桶中取令牌，取到了令牌的請求可以執(zhí)行；
- 如果桶空了,則拒絕該請求。
具體實現(xiàn)
@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("請求頻繁");
}
}
});
}
}執(zhí)行結果：
-[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個是請求頻繁的。
小結
- 固定窗口：實現(xiàn)簡單，適用于流量相對均勻分布，對限流準確度要求不嚴格的場景。
- 滑動窗口：適用于對準確性和性能有一定的要求場景，可以調整子窗口數(shù)量來權衡性能和準確度
- 漏桶：適用于流量絕對平滑的場景
- 令牌桶：適用于流量整體平滑的情況下，同時也可以滿足一定的突發(fā)流程場景
總結
到此這篇關于Redis常見限流算法原理及實現(xiàn)的文章就介紹到這了,更多相關Redis限流算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了Redis教程(十一)：虛擬內存介紹,本文講解了虛擬內存簡介、應用場景和配置方法等內容,需要的朋友可以參考下2015-04-04
本文主要介紹了Redis實現(xiàn)Session共享與單點登錄，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07
本文主要介紹了淺談Redis在秒殺場景的作用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-01-01
使用Redis命令操作數(shù)據(jù)庫的常見錯誤及解決方法
由于Redis是內存數(shù)據(jù)庫,因此可能會存在一些安全問題,下面這篇文章主要給大家介紹了關于使用Redis命令操作數(shù)據(jù)庫的常見錯誤及解決方法,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-02-02
從零搭建SpringBoot2.X整合Redis框架的詳細教程
這篇文章主要介紹了從零搭建SpringBoot2.X整合Redis框架的詳細教程,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12
關于使用IDEA的springboot框架往Redis里寫入數(shù)據(jù)亂碼問題
這篇文章主要介紹了用IDEA的springboot框架往Redis里寫入數(shù)據(jù)亂碼問題,本文給大家分享解決方法通過圖文示例相結合給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-10-10
這篇文章主要為大家詳細介紹了redis快照模式的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-08-08
redis發(fā)布和訂閱_動力節(jié)點Java學院整理
這篇文章主要為大家詳細介紹了redis發(fā)布和訂閱的相關資料，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-08-08
這篇文章主要介紹了Redis fork進程分配不到內存解決方案,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-11-11
這篇文章主要介紹了Redis慢查詢日志與監(jiān)視器問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12