限流的三種算法
https://www.cnblogs.com/forezp/p/10140316.html
概述
限流要解決的問題
防止QPS過高導致的服務器崩潰，特別是一些耗時、耗資源的操作,限流可以保護服務器負載可控
基于業(yè)務上考慮（比如IP限流扬霜、用戶限流 ）曙强，限流可以避免業(yè)務上的異常運行
- 防止用戶異常的操作莉恼，例如開掛搶商品囚枪、搶火車票
- 防止攻擊服務器发笔，導致正常的請求沒法及時處理缸榛，DDOS攻擊
典型限流的應用場景：
- 秒殺 防止刷單
- 耗資源的一些操作（比如微信token的限流吝羞，因為是 1對多，不限流 容易崩)
如何限流内颗？
一般網(wǎng)關都有這種功能脆贵。 gateway、nginx起暮、zuul等
限流：一定時間內卖氨，只允許N次請求。
從計算機友好的角度出發(fā)负懦，是希望能在單位時間內均攤掉請求筒捺，使用漏斗算法可以達到這種效果。
但是漏斗算法有個弊端纸厉，就是先快后慢的這種請求系吭，那么峰值的請求也只能排隊等待被消費。實際上計算機是具備一定的高并發(fā)處理能力的颗品，只要不是一直處于高并發(fā)下即可肯尺。所以 計數(shù)器限流和 漏洞限流折中的算法，令牌限流成為現(xiàn)在最主流的算法躯枢。
方案一：計數(shù)器限流
（Redis 結合expire方案可以實現(xiàn))
第一次請求開始計時则吟，例如1s以內，達到100次請求就拒絕訪問了锄蹂，直到1s過后氓仲，重新開始計數(shù)。
優(yōu)點：
- 實現(xiàn)簡單
- 可以保證一定時間內，一定能處理完限流次數(shù)的請求敬扛。比如1s限流1000次請求晰洒，那么無論是先快后慢，還是先慢后快啥箭，都可以完成1000次請求谍珊。
缺點：短暫的峰值過高對服務器不友好。服務器希望能把請求盡量的均攤開來急侥，這樣可以充分利用計算機資源抬驴。
- 先到先得，可能1ms就有1000次請求打滿了缆巧，999ms里面都是空閑布持，對服務器而言，這樣并不友好陕悬。
- 而且1s的最后1ms有1000次請求题暖，下一秒開始頭1ms又有1000次請求，會導致連續(xù)的峰值過高捉超，對服務器特別不友好胧卤。
方案二：漏洞限流
消費的速度是恒定的，對于服務器而言是最友好的拼岳。
在算法實現(xiàn)方面枝誊，可以準備一個隊列，用來保存請求惜纸，另外通過一個線程池（ScheduledExecutorService）來定期從隊列中獲取請求并執(zhí)行叶撒，可以一次性獲取多個并發(fā)執(zhí)行。
參數(shù)：消費速度耐版、桶容量（超過就拋棄祠够，可以避免內存過大，有過多的等待的任務)
優(yōu)點：
- 實現(xiàn)限流的功能的同時粪牲，又可以充分利用計算機資源古瓤，非常友好的一種方案
- 不會因為開始計數(shù)時間導致異常的峰值
缺點：
- 并不能保證規(guī)定時間內消費預期的流量，比如1s內限流1000次腺阳，1ms1個請求的模型落君，如果前面沒有請求，第900ms時有大量的請求亭引，那么1s之內的處理速度時100個绎速。
- 先快后慢的時候，比如前100ms有500個請求痛侍，后900ms有500個請求朝氓。1s也是1000個請求魔市，但是前500個請求只能排隊主届，1ms處理一個赵哲，實際上計算機是有一定的高并發(fā)能力的，只要不是長期處于高并發(fā)的模式都行的君丁。這樣前面快的請求不需要盲目等待枫夺。
方案三：令牌限流
令牌桶算法是比較常見的限流算法之一，大概描述如下：
1）所有的請求在處理之前都需要拿到一個可用的令牌才會被處理绘闷；
2）根據(jù)限流大小橡庞，設置按照一定的速率往桶里添加令牌；
3）桶設置最大的放置令牌限制印蔗，當桶滿時扒最、新添加的令牌就被丟棄活著拒絕；
4）請求達到后首先要獲取令牌桶中的令牌华嘹，拿著令牌才可以進行其他的業(yè)務邏輯吧趣，處理完業(yè)務邏輯之后，將令牌直接刪除耙厚；
5）令牌桶有最低限額强挫，當桶中的令牌達到最低限額的時候，請求處理完之后將不會刪除令牌薛躬，以此保證足夠的限流俯渤；
這種算法，既可以保證系統(tǒng)由一定的高并發(fā)能力型宝，比如當前令牌桶容量是100八匠，一開始直接消費掉100個請求。有保證服務器不會因為短暫的爆發(fā)趴酣，而導致server端空閑臀叙，因為令牌桶還會持續(xù)的生產令牌。
既有一定的并發(fā)能力价卤，又不至于完全失去控制劝萤，可控的兼具并發(fā)力和流量控制的限流算法.是計數(shù)器算法（一定的并發(fā)處理能力）和漏洞限流（高峰過后仍然會持續(xù)的產生令牌）的折中算法。
Gateway的限流
- 針對用戶限流
- 針對url限流
- 針對IP限流
@Bean
KeyResolver userKeyResolver() {
return exchange -> Mono.just(exchange.getRequest().getQueryParams().getFirst("user"));
}
@Bean
public KeyResolver ipKeyResolver() {
return exchange -> Mono.just(exchange.getRequest().getRemoteAddress().getHostName());
}
@Override
public Mono<String> resolve(ServerWebExchange exchange) {
return Mono.just(exchange.getRequest().getURI().getPath());
}
