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