四大经典限流算法
Python涨薪研究所
共 11502字,需浏览 24分钟
· 2021-07-06
源 / 顶级程序员 文/
公众号:捡田螺的小男孩
限流是什么?
In computer networks, rate limiting is used to control the rate of requests sent or
received by a network interface controller. It can be used to prevent DoS attacks
and limit web scraping
常见的限流算法
固定窗口限流算法
当次数少于限流阀值,就允许访问,并且计数器+1 当次数大于限流阀值,就拒绝访问。 当前的时间窗口过去之后,计数器清零。
/**
* 固定窗口时间算法
* @return
*/
boolean fixedWindowsTryAcquire() {
long currentTime = System.currentTimeMillis(); //获取系统当前时间
if (currentTime - lastRequestTime > windowUnit) { //检查是否在时间窗口内
counter = 0; // 计数器清0
lastRequestTime = currentTime; //开启新的时间窗口
}
if (counter < threshold) { // 小于阀值
counter++; //计数器加1
return true;
}
return false;
}
滑动窗口限流算法
/**
* 单位时间划分的小周期(单位时间是1分钟,10s一个小格子窗口,一共6个格子)
*/
private int SUB_CYCLE = 10;
/**
* 每分钟限流请求数
*/
private int thresholdPerMin = 100;
/**
* 计数器, k-为当前窗口的开始时间值秒,value为当前窗口的计数
*/
private final TreeMap<Long, Integer> counters = new TreeMap<>();
/**
* 滑动窗口时间算法实现
*/
boolean slidingWindowsTryAcquire() {
long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //获取当前时间在哪个小周期窗口
int currentWindowNum = countCurrentWindow(currentWindowTime); //当前窗口总请求数
//超过阀值限流
if (currentWindowNum >= thresholdPerMin) {
return false;
}
//计数器+1
counters.get(currentWindowTime)++;
return true;
}
/**
* 统计当前窗口的请求数
*/
private int countCurrentWindow(long currentWindowTime) {
//计算窗口开始位置
long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1);
int count = 0;
//遍历存储的计数器
Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Long, Integer> entry = iterator.next();
// 删除无效过期的子窗口计数器
if (entry.getKey() < startTime) {
iterator.remove();
} else {
//累加当前窗口的所有计数器之和
count =count + entry.getValue();
}
}
return count;
}
漏桶算法
流入的水滴,可以看作是访问系统的请求,这个流入速率是不确定的。 桶的容量一般表示系统所能处理的请求数。 如果桶的容量满了,就达到限流的阀值,就会丢弃水滴(拒绝请求) 流出的水滴,是恒定过滤的,对应服务按照固定的速率处理请求。
/**
* 每秒处理数(出水率)
*/
private long rate;
/**
* 当前剩余水量
*/
private long currentWater;
/**
* 最后刷新时间
*/
private long refreshTime;
/**
* 桶容量
*/
private long capacity;
/**
* 漏桶算法
* @return
*/
boolean leakybucketLimitTryAcquire() {
long currentTime = System.currentTimeMillis(); //获取系统当前时间
long outWater = (currentTime - refreshTime) / 1000 * rate; //流出的水量 =(当前时间-上次刷新时间)* 出水率
long currentWater = Math.max(0, currentWater - outWater); // 当前水量 = 之前的桶内水量-流出的水量
refreshTime = currentTime; // 刷新时间
// 当前剩余水量还是小于桶的容量,则请求放行
if (currentWater < capacity) {
currentWater++;
return true;
}
// 当前剩余水量大于等于桶的容量,限流
return false;
}
令牌桶算法
有一个令牌管理员,根据限流大小,定速往令牌桶里放令牌。 如果令牌数量满了,超过令牌桶容量的限制,那就丢弃。 系统在接受到一个用户请求时,都会先去令牌桶要一个令牌。如果拿到令牌,那么就处理这个请求的业务逻辑; 如果拿不到令牌,就直接拒绝这个请求。
/**
* 每秒处理数(放入令牌数量)
*/
private long putTokenRate;
/**
* 最后刷新时间
*/
private long refreshTime;
/**
* 令牌桶容量
*/
private long capacity;
/**
* 当前桶内令牌数
*/
private long currentToken = 0L;
/**
* 漏桶算法
* @return
*/
boolean tokenBucketTryAcquire() {
long currentTime = System.currentTimeMillis(); //获取系统当前时间
long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate; //生成的令牌 =(当前时间-上次刷新时间)* 放入令牌的速率
currentToken = Math.min(capacity, generateToken + currentToken); // 当前令牌数量 = 之前的桶内令牌数量+放入的令牌数量
refreshTime = currentTime; // 刷新时间
//桶里面还有令牌,请求正常处理
if (currentToken > 0) {
currentToken--; //令牌数量-1
return true;
}
return false;
}
好文推荐
排名第一的安全软件,为啥会变成流氓软件?
爆网视频!西班牙男子自称时空穿越者,说:人类2027灭绝,自己是唯一幸存者!
985 研究生组团诈骗,一个中招就关 App,涉案金额超 1 亿,受害人遍布全国
一键三连「分享」、「点赞」和「在看」
技术干货与你天天见~
评论
屏论丨“重温经典”频道走红背后的危与机
屏论今年2月1日,“重温经典”频道正式开播,作为免费向观众提供应看爱看、脍炙人口的经典内容的公益性频道,“重温经典”频道对于“双治理”背景下正在进行电视公共服务属性与商业属性新一轮沉淀的电视大屏而言,意义重要而特殊。从频道开播以来的实际表现来看,的确亮眼。比如春节期间,“重温经典”频道在21个地区收
流媒体网
0
面试官:限流的常见算法有哪些?
限流的实现算法有很多,但常见的限流算法有三种:计数器算法、漏桶算法和令牌桶算法。1.计数器算法计数器算法是在一定的时间间隔里,记录请求次数,当请求次数超过该时间限制时,就把计数器清零,然后重新计算。当请求次数超过间隔内的最大次数时,拒绝访问。计数器算法的实现比较简单,但存在“突刺现象”。突刺现象是指
Stephen
0
985 本硕,秋招上岸阿里算法岗!
↓推荐关注↓节前,我们星球举办了技术&面试交流会,邀请了一些互联网大厂好友以及今年参加社招和校招面试的同学。会上探讨了一系列热门话题,包括大模型发展趋势、算法落地实践、面经总结,以及如何做好面试准备和应对常见考点。基于经验交流与实战经验,我们总结如下:《机器学习算法面试宝典》1.0 发布!今
Python学习与数据挖掘
0
Java版【数据结构与算法】的天花板,收藏好,慢慢看
Java 版数据结构与算法来了,堪称 java 版数据结构与算法的天花板,需要学数据结构与算法的,刷这套就可以了,目录如下,文末附教程地址。基础数据结构-001-二分查找-算法描述基础数据结构-002-二分查找-算法实现基础数据结构-003-二分查找-问题1-循环条件基础数据结构-004-二分查找-
路人甲Java
0
算法工程师的核心竞争力是什么?
点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达链接:https://www.zhihu.com/question/527696166编辑:深度学习与计算机视觉声明:仅做学术分享,侵删作者:赵俊博 Jakehttps://www.zhihu.com/question/52769
小白学视觉
10
我想知道,高德和百度,谁的算法更准?
点击上方牲产力关注我在线提问,平常导航你是用高德还是百度呢?我个人喜欢用百度地图,媳妇儿是用高德,但而且她打车也会直接用高德,我还会再用滴滴来单独打车。总感觉导航嘛,不同软件应该大差不差,没想到一番搜罗还真有些奇奇怪怪的对比。01 大路vs小路江湖传闻,当百度还在大路上给你规划地图时,高德已经给你寻
TTTEED
2
一天肝600多篇文章,用数量对抗算法的不确定性
我写公众号七八年,总原创文章数量也只不过是650多篇。写爆文的一天就干出600多篇,多少有点震惊。背后是公众号平台进行功能调整后,从一天只能发一次文章,变改成了一天可以无限制发任意数量的文章。做公众号爆文写作变现的底层逻辑是基于公众号算法调整,从订阅规则改成了推荐机制,人人都有机会获得系统的推荐流量
python之禅
0
Nat. Commun. | gLM:基于宏基因组预训练语言模型的基因和蛋白调控及功能预测算法
2024年4月3日,Peter R. Girguis、Sergey Ovchinnikov、Yunha Hwang、Andre L. Cornman和Elizabeth H. Kellogg几人在Nature Communications上发表了一篇题为“Genomic language model
生信宝典
0