網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
一、限流算法
在高并發(fā)系統(tǒng)中,有三把利器用來(lái)保護(hù)系統(tǒng):緩存、降級(jí)和限流。
本文主要是介紹限流,限流算法主要有以下三種:
1.計(jì)數(shù)器算法
- 固定窗口
- 滑動(dòng)窗口
2.令牌桶算法
3.漏桶算法
1.計(jì)數(shù)器算法
1.1 固定窗口算法
計(jì)數(shù)器算法是限流算法里最簡(jiǎn)單也是最容易實(shí)現(xiàn)的一種算法。比如我們規(guī)定,對(duì)于A接口來(lái)說(shuō),我們1分鐘的訪問(wèn)次數(shù)不能超過(guò)100個(gè)。那么我們可以這么做:在一開(kāi) 始的時(shí)候,我們可以設(shè)置一個(gè)計(jì)數(shù)器counter,每當(dāng)一個(gè)請(qǐng)求過(guò)來(lái)的時(shí)候,counter就加1,如果counter的值大于100并且該請(qǐng)求與第一個(gè) 請(qǐng)求的間隔時(shí)間還在1分鐘之內(nèi),那么說(shuō)明請(qǐng)求數(shù)過(guò)多;如果該請(qǐng)求與第一個(gè)請(qǐng)求的間隔時(shí)間大于1分鐘,且counter的值還在限流范圍內(nèi),那么就重置 counter。
java中的具體實(shí)現(xiàn)如下:
public class CounterTest { public long timeStamp = getNowTime(); public int reqCount = 0; public final int limit = 100; // 時(shí)間窗口內(nèi)最大請(qǐng)求數(shù) public final long interval = 1000; // 時(shí)間窗口ms public boolean grant() { long now = getNowTime(); if (now < timeStamp + interval) { // 在時(shí)間窗口內(nèi) reqCount++; // 判斷當(dāng)前時(shí)間窗口內(nèi)是否超過(guò)最大請(qǐng)求控制數(shù) return reqCount <= limit; } else { timeStamp = now; // 超時(shí)后重置 reqCount = 1; return true; } } public long getNowTime() { return System.currentTimeMillis(); } }
.NET Core中的具體實(shí)現(xiàn)如下:
AspNetCoreRateLimit是目前ASP.NET Core下最常用的限流解決方案,AspNetCoreRateLimit的源碼實(shí)現(xiàn)是固定窗口算法如下:
var entry = await _counterStore.GetAsync(counterId, cancellationToken); if (entry.HasValue) { // entry has not expired if (entry.Value.Timestamp + rule.PeriodTimespan.Value >= DateTime.UtcNow) { // increment request count var totalCount = entry.Value.Count + _config.RateIncrementer?.Invoke() ?? 1; // deep copy counter = new RateLimitCounter { Timestamp = entry.Value.Timestamp, Count = totalCount }; } }
固定窗口算法缺點(diǎn)
從上圖中我們可以看到,假設(shè)有一個(gè)惡意用戶(hù),他在0:59時(shí),瞬間發(fā)送了100個(gè)請(qǐng)求,并且1:00又瞬間發(fā)送了100個(gè)請(qǐng)求,那么其實(shí)這個(gè)用戶(hù)在 1秒里面,瞬間發(fā)送了200個(gè)請(qǐng)求。我們剛才規(guī)定的是1分鐘最多100個(gè)請(qǐng)求,也就是每秒鐘最多1.7個(gè)請(qǐng)求,用戶(hù)通過(guò)在時(shí)間窗口的重置節(jié)點(diǎn)處突發(fā)請(qǐng)求, 可以瞬間超過(guò)我們的速率限制。用戶(hù)有可能通過(guò)算法的這個(gè)漏洞,瞬間壓垮我們的應(yīng)用。
1.2 滑動(dòng)窗口算法
滑動(dòng)窗口類(lèi)似于固定窗口算法,但它通過(guò)將前一個(gè)窗口中的加權(quán)計(jì)數(shù)添加到當(dāng)前窗口中的計(jì)數(shù)來(lái)計(jì)算估計(jì)數(shù),如果估計(jì)數(shù)超過(guò)計(jì)數(shù)限制,則請(qǐng)求將被阻止。
具體公式如下:
估計(jì)數(shù) = 前一窗口計(jì)數(shù) * (1 - 當(dāng)前窗口經(jīng)過(guò)時(shí)間 / 單位時(shí)間) + 當(dāng)前窗口計(jì)數(shù)
窗口[00:00, 00:01)中有9個(gè)請(qǐng)求,窗口[00:01, 00:02)中有5個(gè)請(qǐng)求。對(duì)于01:15到達(dá)的請(qǐng)求,即窗口[00:01, 00:02)的25%位置,通過(guò)公式計(jì)算請(qǐng)求計(jì)數(shù):9 x (1 - 25%) + 5 = 11.75 > 10. 因此我們拒絕此請(qǐng)求。
即使兩個(gè)窗口都沒(méi)有超過(guò)限制,請(qǐng)求也會(huì)被拒絕,因?yàn)榍耙粋€(gè)和當(dāng)前窗口的加權(quán)和確實(shí)超過(guò)了限制。
2.令牌桶算法
令牌桶算法是比較常見(jiàn)的限流算法之一,大概描述如下:
1)所有的請(qǐng)求在處理之前都需要拿到一個(gè)可用的令牌才會(huì)被處理;
2)根據(jù)限流大小,設(shè)置按照一定的速率往桶里添加令牌;
3)桶設(shè)置最大的放置令牌限制,當(dāng)桶滿(mǎn)時(shí)、新添加的令牌就被丟棄或者拒絕;
4)請(qǐng)求達(dá)到后首先要獲取令牌桶中的令牌,拿著令牌才可以進(jìn)行其他的業(yè)務(wù)邏輯,處理完業(yè)務(wù)邏輯之后,將令牌直接刪除;
5)令牌桶有最低限額,當(dāng)桶中的令牌達(dá)到最低限額的時(shí)候,請(qǐng)求處理完之后將不會(huì)刪除令牌,以此保證足夠的限流;
3.漏桶算法
漏桶算法其實(shí)很簡(jiǎn)單,可以粗略的認(rèn)為就是注水漏水過(guò)程,往桶中以一定速率流出水,以任意速率流入水,當(dāng)水超過(guò)桶流量則丟棄,因?yàn)橥叭萘渴遣蛔兊?,保證了整體的速率。
二、ASP.NET Core中間件實(shí)現(xiàn)限流
1.中間件代碼
public class SlidingWindow { private readonly object _syncObject = new object(); private readonly int _requestIntervalSeconds; private readonly int _requestLimit; private DateTime _windowStartTime; private int _prevRequestCount; private int _requestCount; public SlidingWindow(int requestLimit, int requestIntervalSeconds) { _windowStartTime = DateTime.Now; _requestLimit = requestLimit; _requestIntervalSeconds = requestIntervalSeconds; } public bool PassRequest() lock (_syncObject) { var currentTime = DateTime.Now; var elapsedSeconds = (currentTime - _windowStartTime).TotalSeconds; if (elapsedSeconds >= _requestIntervalSeconds * 2) { _windowStartTime = currentTime; _prevRequestCount = 0; _requestCount = 0; elapsedSeconds = 0; } else if (elapsedSeconds >= _requestIntervalSeconds) _windowStartTime = _windowStartTime.AddSeconds(_requestIntervalSeconds); _prevRequestCount = _requestCount; elapsedSeconds = (currentTime - _windowStartTime).TotalSeconds; } var requestCount = _prevRequestCount * (1 - elapsedSeconds / _requestIntervalSeconds) + _requestCount + 1; if (requestCount <= _requestLimit) _requestCount++; return true; } return false; }
如果最近的2次請(qǐng)求相距2個(gè)窗口時(shí)間,則可以認(rèn)為前一窗口計(jì)數(shù)為0,重新開(kāi)始計(jì)數(shù)。
public class RateLimitMiddleware : IMiddleware { private readonly SlidingWindow _window; public RateLimitMiddleware() { _window = new SlidingWindow(10, 60); } public async Task InvokeAsync(HttpContext context, RequestDelegate next) { if (!_window.PassRequest()) { context.SetEndpoint(new Endpoint((context) => { context.Response.StatusCode = StatusCodes.Status403Forbidden; return Task.CompletedTask; }, EndpointMetadataCollection.Empty, "限流")); } await next(context); } }
2.在管道中的使用
需要注意的是,我們注冊(cè)Middleware時(shí),必須使用單例模式,保證所有請(qǐng)求通過(guò)同一SlidingWindow計(jì)數(shù):
services.AddSingleton();
原文鏈接:https://blog.csdn.net/aa2528877987/article/details/123197556
相關(guān)推薦
- 2023-06-16 Qt6實(shí)現(xiàn)調(diào)用攝像頭并顯示畫(huà)面_C 語(yǔ)言
- 2022-06-29 徹底掌握C語(yǔ)言strcpy函數(shù)的用法_C 語(yǔ)言
- 2022-12-01 SQL?Server主鍵與外鍵設(shè)置以及相關(guān)理解_MsSql
- 2022-10-26 C++消息隊(duì)列(定義,結(jié)構(gòu),如何創(chuàng)建,發(fā)送與接收)_C 語(yǔ)言
- 2022-10-13 Android繪制簡(jiǎn)單條形圖_Android
- 2022-09-24 python實(shí)現(xiàn)字母閃爍效果的示例代碼_python
- 2022-12-24 fetch()函數(shù)說(shuō)明與使用方法詳解_基礎(chǔ)知識(shí)
- 2023-10-26 解決問(wèn)題:NODE_ENV 不是內(nèi)部或外部命令,也不是可運(yùn)行的程序,或者批處理文件
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版(
- Linux 中運(yùn)行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符,流程控制 Flo
- 1. Int 和Integer 的區(qū)別,Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過(guò)濾器
- Spring Security概述快速入門(mén)
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤:Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串(SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列,發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支