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

简介:

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

分析之前

  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的限流算法有哪些?
88 3
|
4月前
|
存储 算法 Java
高并发架构设计三大利器:缓存、限流和降级问题之滑动日志算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之滑动日志算法问题如何解决
|
4月前
|
算法 Java 调度
高并发架构设计三大利器:缓存、限流和降级问题之使用Java代码实现令牌桶算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之使用Java代码实现令牌桶算法问题如何解决
|
4月前
|
缓存 算法 Java
高并发架构设计三大利器:缓存、限流和降级问题之使用代码实现漏桶算法问题如何解决
高并发架构设计三大利器:缓存、限流和降级问题之使用代码实现漏桶算法问题如何解决
|
4月前
|
算法 UED 缓存
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法适用于哪些场景
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法适用于哪些场景
|
4月前
|
存储 算法 缓存
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法的原理是什么
高并发架构设计三大利器:缓存、限流和降级问题之滑动窗口算法的原理是什么
|
4月前
|
算法 API 缓存
高并发架构设计三大利器:缓存、限流和降级问题之固定窗口限流算法的原理是什么
高并发架构设计三大利器:缓存、限流和降级问题之固定窗口限流算法的原理是什么
|
1月前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
9天前
|
算法 数据安全/隐私保护 索引
OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度
本项目展示了在MATLAB 2022a环境下,通过选择映射(SLM)与相位截断星座图(PTS)技术有效降低OFDM系统中PAPR的算法实现。包括无水印的算法运行效果预览、核心程序及详尽的中文注释,附带操作步骤视频,适合研究与教学使用。
|
17天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
下一篇
无影云桌面