最近写了一个限流的插件,所以避免不了的接触到了一些限流算法。本篇文章就来分析一下这几种常见的限流算法
1
◆
分析之前
◆
2
◆
◆
这个算法可以说是限流算法中最简单的一种算法了。
计数器算法的意思呢就是当接口在一个时间单位中被访问时,我就记下来访问次数,直到它访问的次数到达上限。
当一个请求过来时,我们就会得到这个key。
if(存在key){ value++; if(value>=limit){ 不能访问 } }else{ 添加key,value为1 设置key过期时间为expire }
既然条件一已经实现了,那条件二会复杂么 ?
相比于条件一来说就是同一个key对应了多个用户。那么我们只需要把key加上用户的信息就可以了。比如说 key_用户1、key_用户2。
3
◆
◆
漏桶算法的意思呢就是一个接口在一个时间单位中允许被访问次数是动态变化的(假如一分钟允许访问60次,那么从开始计时时不管有没有被访问第59秒只允许访问59次,30秒只允许30次)。为什么这样呢,因为有另外一个线程在进行递减操作
线程一:
if(存在key){ value--; if(value<=0){ 不能访问 } }else{ 添加key,设置value为limit }
线程二:
while(过去interval时间){ 所有key的value-step }
参考计数器算法条件二实现。
可以看到实现漏桶算法的话需要每隔interval时间都要另外一条线程去遍历所key的value去做递减操作,那么有没有什么办法可以省略这一步呢。答案是肯定有。
if(存在key){ value--; if((nowTime-lastUpdateTime)>interval){ value=value-(nowTime-lastUpdateTime)/interval*step; lastUpdateTime=nowTime; } if(value<=0){ 不能访问 } }else{ 添加key,设置value为limit; lastUpdateTime=nowTime; }
4
◆
◆
令牌桶算法呢,恰恰是和漏桶算法相反的一个算法,不过还是推荐你使用这个。这个算法的原理我不讲,我觉得聪明的你看了伪代码就明白了。
线程一:
if(存在key){ value++; if(value>=limit){ 不能访问 } }else{ 添加key,设置value为limit }
线程二:
while(过去interval时间){ 所有key的value+step }
参考计算器算法条件二实现。
参考漏桶算法升级实现。