目錄
- 一、引言
- 二、固定時間窗口算法
- 三、滑動時間窗口算法
- 四、漏桶算法
- 五、令牌桶算法
一、引言
- 在web開發(fā)中功能是基石，除了功能以外運維和防護就是重頭菜了。因為在網(wǎng)站運行期間可能會因為突然的訪問量導致業(yè)務(wù)異常、也有可能遭受別人惡意攻擊
- 所以我們的接口需要對流量進行限制。俗稱的QPS也是對流量的一種描述
- 針對限流現(xiàn)在大多應(yīng)該是令牌桶算法，因為它能保證更多的吞吐量。除了令牌桶算法還有他的前身漏桶算法和簡單的計數(shù)算法
- 下面我們來看看這四種算法
二、固定時間窗口算法
- 固定時間窗口算法也可以叫做簡單計數(shù)算法。網(wǎng)上有很多都將計數(shù)算法單獨抽離出來。但是筆者認為計數(shù)算法是一種思想，而固定時間窗口算法是他的一種實現(xiàn)
- 包括下面滑動時間窗口算法也是計數(shù)算法的一種實現(xiàn)。因為計數(shù)如果不和時間進行綁定的話那么失去了限流的本質(zhì)了。就變成了拒絕了
優(yōu)點：
- 在固定的時間內(nèi)出現(xiàn)流量溢出可以立即做出限流。每個時間窗口不會相互影響
- 在時間單元內(nèi)保障系統(tǒng)的穩(wěn)定。保障的時間單元內(nèi)系統(tǒng)的吞吐量上限
缺點：
- 正如圖示一樣，他的最大問題就是臨界狀態(tài)。在臨界狀態(tài)最壞情況會受到兩倍流量請求
- 除了臨界的情況，還有一種是在一個單元時間窗內(nèi)前期如果很快的消耗完請求閾值。那么剩下的時間將會無法請求。這樣就會因為一瞬間的流量導致一段時間內(nèi)系統(tǒng)不可用。這在互聯(lián)網(wǎng)高可用的系統(tǒng)中是不能接受的。
實現(xiàn)：
- 好了，關(guān)于原理介紹及優(yōu)缺點我們已經(jīng)了解了。下面我們動手實現(xiàn)它
- 首先我們在實現(xiàn)這種計數(shù)時，采用redis是非常好的選擇。這里我們通過redis實現(xiàn)
controller
@RequestMapping(value = "/start",method = RequestMethod.GET)
public Mapstring,object> start(@RequestParam Mapstring, object=""> paramMap) {
return testService.startQps(paramMap);
}
service
@Override
public Mapstring, object=""> startQps(Mapstring, object=""> paramMap) {
//根據(jù)前端傳遞的qps上線
Integer times = 100;
if (paramMap.containsKey("times")) {
times = Integer.valueOf(paramMap.get("times").toString());
}
String redisKey = "redisQps";
RedisAtomicInteger redisAtomicInteger = new RedisAtomicInteger(redisKey, redisTemplate.getConnectionFactory());
int no = redisAtomicInteger.getAndIncrement();
//設(shè)置時間固定時間窗口長度 1S
if (no == 0) {
redisAtomicInteger.expire(1, TimeUnit.SECONDS);
}
//判斷是否超限 time=2 表示qps=3
if (no > times) {
throw new RuntimeException("qps refuse request");
}
//返回成功告知
Mapstring, object=""> map = new HashMap>();
map.put("success", "success");
return map;
}
結(jié)果測試：
我們設(shè)置的qps=3 ， 我們可以看到五個并發(fā)進來后前三個正常訪問，后面兩個就失敗了。稍等一段時間我們在并發(fā)訪問，前三個又可以正常訪問。說明到了下一個時間窗口
三、滑動時間窗口算法
- 針對固定時間窗口的缺點--臨界值出現(xiàn)雙倍流量問題。 我們的滑動時間窗口就產(chǎn)生了。
- 其實很好理解，就是針對固定時間窗口，將時間窗口統(tǒng)計從原來的固定間隔變成更加細度化的單元了。
- 在上面我們固定時間窗口演示中我們設(shè)置的時間單元是1S 。 針對1S我們將1S拆成時間戳。
- 固定時間窗口是統(tǒng)計單元隨著時間的推移不斷向后進行。而滑動時間窗口是我們認為的想象出一個時間單元按照相對論的思想將時間固定，我們的抽象時間單元自己移動。抽象的時間單元比實際的時間單元更小。
- 讀者可以看下下面的動圖，就可以理解了。
優(yōu)點：
- 實質(zhì)上就是固定時間窗口算法的改進。所以固定時間窗口的缺點就是他的優(yōu)點。
- 內(nèi)部抽象一個滑動的時間窗，將時間更加小化。存在邊界的問題更加小。客戶感知更弱了。
缺點：
- 不管是固定時間窗口算法還是滑動時間窗口算法，他們都是基于計數(shù)器算法進行優(yōu)化，但是他們對待限流的策略太粗暴了。
- 為什么說粗暴呢，未限流他們正常放行。一旦達到限流后就會直接拒絕。這樣我們會損失一部分請求。這對于一個產(chǎn)品來說不太友好
實現(xiàn)：
- 滑動時間窗口是將時間更加細化，上面我們是通過redis#setnx實現(xiàn)的。這里我們就無法通過他統(tǒng)一記錄了。我們應(yīng)該加上更小的時間單元存儲到一個集合匯總。然后根據(jù)集合的總量計算限流。redis的zsett數(shù)據(jù)結(jié)構(gòu)就和符合我們的需求。
- 為什么選擇zset呢，因為redis的zset中除了值以外還有一個權(quán)重。會根據(jù)這個權(quán)重進行排序。如果我們將我們的時間單元及時間戳作為我們的權(quán)重，那么我們獲取統(tǒng)計的時候只需要按照一個時間戳范圍就可以了。
- 因為zset內(nèi)元素是唯一的，所以我們的值采用uuid或者雪花算法一類的id生成器
controller
@RequestMapping(value = "/startList",method = RequestMethod.GET)
public Mapstring,object> startList(@RequestParam Mapstring, object=""> paramMap) {
return testService.startList(paramMap);
}
service
String redisKey = "qpsZset";
Integer times = 100;
if (paramMap.containsKey("times")) {
times = Integer.valueOf(paramMap.get("times").toString());
}
long currentTimeMillis = System.currentTimeMillis();
long interMills = inter * 1000L;
Long count = redisTemplate.opsForZSet().count(redisKey, currentTimeMillis - interMills, currentTimeMillis);
if (count > times) {
throw new RuntimeException("qps refuse request");
}
redisTemplate.opsForZSet().add(redisKey, UUID.randomUUID().toString(), currentTimeMillis);
Mapstring, object=""> map = new HashMap>();
map.put("success", "success");
return map;
結(jié)果測試：
- 和固定時間窗口采用相同的并發(fā)。為什么上面也會出現(xiàn)臨界狀況呢。因為在代碼里時間單元間隔比固定時間間隔采用還要大 。 上面演示固定時間窗口時間單元是1S出現(xiàn)了最壞情況。而滑動時間窗口設(shè)計上就應(yīng)該間隔更短。而我設(shè)置成10S 也沒有出現(xiàn)壞的情況
- 這里就說明滑動比固定的優(yōu)處了。如果我們調(diào)更小應(yīng)該更加不會出現(xiàn)臨界問題，不過說到底他還是避免不了臨界出現(xiàn)的問題
四、漏桶算法
- 滑動時間窗口雖然可以極大程度的規(guī)避臨界值問題，但是始終還是避免不了
- 另外時間算法還有個致命的問題，他無法面對突如其來的大量流量，因為他在達到限流后直接就拒絕了其他額外流量
- 針對這個問題我們繼續(xù)優(yōu)化我們的限流算法。 漏桶算法應(yīng)運而生
優(yōu)點：
- 面對限流更加的柔性，不在粗暴的拒絕。
- 增加了接口的接收性
- 保證下流服務(wù)接收的穩(wěn)定性。均勻下發(fā)
缺點：
- 我覺得沒有缺點。非要雞蛋里挑骨頭那我只能說漏桶容量是個短板
實現(xiàn)：
controller
@RequestMapping(value = "/startLoutong",method = RequestMethod.GET)
public Mapstring,object> startLoutong(@RequestParam Mapstring, object=""> paramMap) {
return testService.startLoutong(paramMap);
}
service在service中我們通過redis的list的功能模擬出桶的效果。這里代碼是實驗室性質(zhì)的。在真實使用中我們還需要考慮并發(fā)的問題
@Override
public Mapstring, object=""> startLoutong(Mapstring, object=""> paramMap) {
String redisKey = "qpsList";
Integer times = 100;
if (paramMap.containsKey("times")) {
times = Integer.valueOf(paramMap.get("times").toString());
}
Long size = redisTemplate.opsForList().size(redisKey);
if (size >= times) {
throw new RuntimeException("qps refuse request");
}
Long aLong = redisTemplate.opsForList().rightPush(redisKey, paramMap);
if (aLong > times) {
//為了防止并發(fā)場景。這里添加完成之后也要驗證。 即使這樣本段代碼在高并發(fā)也有問題。此處演示作用
redisTemplate.opsForList().trim(redisKey, 0, times-1);
throw new RuntimeException("qps refuse request");
}
Mapstring, object=""> map = new HashMap>();
map.put("success", "success");
return map;
}
下游消費
@Component
public class SchedulerTask {
@Autowired
RedisTemplate redisTemplate;
private String redisKey="qpsList";
@Scheduled(cron="*/1 * * * * ?")
private void process(){
//一次性消費兩個
System.out.println("正在消費。。。。。。");
redisTemplate.opsForList().trim(redisKey, 2, -1);
}
}
測試：
- 我們還是通過50并發(fā)循環(huán)10次訪問。我們可以發(fā)現(xiàn)只有在一開始能達到比較高的吞吐量。在隨后桶的容量滿了之后。而下游水滴速率比上游請求速率慢的情況下。只能以下游恒定的速度接收訪問。
- 他的問題也暴露的很明顯。針對時間窗口的不足漏桶進行的不足，但是仍是不足。無法徹底避免請求溢出的問題。
- 請求溢出本身就是一種災(zāi)難性的問題。所有的算法目前都沒有解決這個問題。只是在減緩他帶來的問題
五、令牌桶算法
- 令牌桶和漏桶法是一樣的。只不過將桶的作用方向改變了一下。
- 漏桶的出水速度是恒定的，如果流量突然增加的話我們就只能拒絕入池
- 但是令牌桶是將令牌放入桶中，我們知道正常情況下令牌就是一串字符當桶滿了就拒絕令牌的入池，但是面對高流量的時候正常加上我們的超時時間就留下足夠長的時間生產(chǎn)及消費令牌了。這樣就盡可能的不會造成請求的拒絕
- 最后，不論是對于令牌桶拿不到令牌被拒絕，還是漏桶的水滿了溢出，都是為了保證大部分流量的正常使用，而犧牲掉了少部分流量
public Mapstring, object=""> startLingpaitong(Mapstring, object=""> paramMap) {
String redisKey = "lingpaitong";
String token = redisTemplate.opsForList().leftPop(redisKey).toString();
//正常情況需要驗證是否合法，防止篡改
if (StringUtils.isEmpty(token)) {
throw new RuntimeException("令牌桶拒絕");
}
Mapstring, object=""> map = new HashMap>();
map.put("success", "success");
return map;
}
@Scheduled(cron="*/1 * * * * ?")
private void process(){
//一次性生產(chǎn)兩個
System.out.println("正在消費。。。。。。");
for (int i = 0; i 2; i++) {
redisTemplate.opsForList().rightPush(redisKey, i);
}
}
以上就是詳解基于redis實現(xiàn)的四種常見的限流策略的詳細內(nèi)容，更多關(guān)于redis限流策略的資料請關(guān)注腳本之家其它相關(guān)文章！
您可能感興趣的文章:- redis實現(xiàn)的四種常見限流策略
- springboot+redis 實現(xiàn)分布式限流令牌桶的示例代碼
- 詳解Redis實現(xiàn)限流的三種方式
- Python+redis通過限流保護高并發(fā)系統(tǒng)
- Springboot使用redis進行api防刷限流過程詳解
- Redis和Lua實現(xiàn)分布式限流器的方法詳解
- php使用lua+redis實現(xiàn)限流，計數(shù)器模式，令牌桶模式
- 基于Redis的限流器的實現(xiàn)(示例講解)
- 基于Redis實現(xiàn)分布式應(yīng)用限流的方法
