大型网站限流算法的实现和改造

简介:

最近写了一个限流的插件,所以避免不了的接触到了一些限流算法。本篇文章就来分析一下这几种常见的限流算法

分析之前

  1. 依我个人的理解来说限流的话应该灵活到可以针对每一个接口来做。比如说一个类里面有5个接口,那么我的限流插件就应该能针对每一个接口就行不同的限流方案。所以呢,既然针对的每个接口所以就需要一个可以唯一标示这个接口的key(我取的是类名+方法名+入参)。
  2. 分布式限流强烈推荐使用redis+lua或者nginx+lua来实现。
  3. 这里用2个限流条件来做示例讲一下常见的限流算法:
    1. 接口1它10秒钟最大允许访问100次
    2. 接口2它10秒钟最大允许每个人访问100次。

计数器算法

这个算法可以说是限流算法中最简单的一种算法了。

核心思想

计数器算法的意思呢就是当接口在一个时间单位中被访问时,我就记下来访问次数,直到它访问的次数到达上限。

涉及变量
  1. 接口(key)
  2. 时间单位(expire)
  3. 允许访问多少次(limit)
  4. 访问次数(value)
条件一

当一个请求过来时,我们就会得到这个key。

1
2
3
4
5
6
7
8
9
if(存在key){
value++;
if(value>=limit){
不能访问
}
}else{
添加key,value为1
设置key过期时间为expire
}
条件二

既然条件一已经实现了,那条件二会复杂么 ?

相比于条件一来说就是同一个key对应了多个用户。那么我们只需要把key加上用户的信息就可以了。比如说 key_用户1、key_用户2。

漏桶算法

核心思想

漏桶算法的意思呢就是一个接口在一个时间单位中允许被访问次数是动态变化的(假如一分钟允许访问60次,那么从开始计时时不管有没有被访问第59秒只允许访问59次,30秒只允许30次)。为什么这样呢,因为有另外一个线程在进行递减操作

涉及变量
  1. 接口(key)
  2. 时间单位(expire)
  3. 允许访问多少次(limit)
  4. 递减间隔时间(interval)
  5. 递减步长(step)
  6. 剩余可访问次数(value)
  7. key的访问时间(lastUpdateTime)
  8. 当前时间(nowTime)(注意nowTime的取值应为应用取得的时间而不是redis或者nginx取得的时间)
条件一

线程一:

1
2
3
4
5
6
7
8
if(存在key){
value--;
if(value<=0){
不能访问
}
}else{
添加key,设置value为limit
}

线程二:

1
2
3
while(过去interval时间){
所有key的value-step
}
条件二

参考计数器算法条件二实现。

算法升级

可以看到实现漏桶算法的话需要每隔interval时间都要另外一条线程去遍历所key的value去做递减操作,那么有没有什么办法可以省略这一步呢。答案是肯定有。

1
2
3
4
5
6
7
8
9
10
11
12
13
if(存在key){
value--;
if((nowTime-lastUpdateTime)>interval){
value=value-(nowTime-lastUpdateTime)/interval*step;
lastUpdateTime=nowTime;
}
if(value<=0){
不能访问
}
}else{
添加key,设置value为limit;
lastUpdateTime=nowTime;
}

令牌桶算法

核心思想

令牌桶算法呢,恰恰是和漏桶算法相反的一个算法,不过还是推荐你使用这个。这个算法的原理我不讲,我觉得聪明的你看了伪代码就明白了。

涉及变量
  1. 接口(key)
  2. 时间单位(expire)
  3. 允许访问多少次(limit)
  4. 递增间隔时间(interval)
  5. 递增步长(step)
  6. 当前可访问次数(value)
  7. key的访问时间(lastUpdateTime)
  8. 当前时间(nowTime)(参照漏桶算法需要注意的点)
条件一

线程一:

1
2
3
4
5
6
7
8
if(存在key){
value++;
if(value>=limit){
不能访问
}
}else{
添加key,设置value为limit
}

线程二:

1
2
3
while(过去interval时间){
所有key的value+step
}
条件二

参考计算器算法条件二实现。

算法升级

参考漏桶算法升级实现。

代码

代码实现请参考我的限流框架https://github.com/2388386839/syj-ratelimit

本文出自http://zhixiang.org.cn,转载请保留。

相关文章
|
3月前
|
算法 NoSQL Java
spring cloud的限流算法有哪些?
【8月更文挑战第18天】spring cloud的限流算法有哪些?
83 3
|
4月前
|
存储 算法 Java
高并发架构设计三大利器:缓存、限流和降级问题之滑动日志算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之滑动日志算法问题如何解决
|
4月前
|
算法 Java 调度
高并发架构设计三大利器:缓存、限流和降级问题之使用Java代码实现令牌桶算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之使用Java代码实现令牌桶算法问题如何解决
|
4月前
|
缓存 算法 Java
高并发架构设计三大利器:缓存、限流和降级问题之使用代码实现漏桶算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之使用代码实现漏桶算法问题如何解决
|
4月前
|
算法 UED 缓存
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法适用于哪些场景
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法适用于哪些场景
|
4月前
|
存储 算法 缓存
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法的原理是什么
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法的原理是什么
|
4月前
|
算法 API 缓存
高并发架构设计三大利器:缓存、限流和降级问题之固定窗口限流算法的原理是什么
高并发架构设计三大利器:缓存、限流和降级问题之固定窗口限流算法的原理是什么
|
16天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
2天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。