redis lua限流算法如何实现

本篇内容介绍了“redis lua限流算法如何实现”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

限流算法

常见的限流算法

• 计数器算法

• 漏桶算法

• 令牌桶算法

计数器算法

  顾名思义,计数器算法是指在一定的时间窗口内允许的固定数量的请求.比如,2s内允许10个请求,30s内允许100个请求等等.如果设置的时间粒度越细,那么相对而言限流就会越平滑,控制的粒度就会更细.

场景分析

试想,如果设置的粒度比较粗会出现什么样的问题呢?如下图设置一个 1000/3s 的限流计数统计.

图中的限流策略为3s内允许的最大请求量为1000,那么会出现2个极端:
 

极端情况1:

• 第1s请流量为10,  

• 第2s请流量为10,  

• 第3s请流量突然激增到980.这意味着在这一刻,有大量的请求蜂拥而至,假设服务每秒能处理的

上线为800/1s,但是此刻却有超过这个量级的请求量,那么后果是不堪设想的.

极端情况2:  

• 第1s请流量突然就达到990,

• 留给后续第2s,3s的可请求数量就非常少了,可能会出现大量的拒绝请求.

结论:

如果用统计计数算法,尽量保持粒度切割精细.

算法实现

Redis的ttl特性完美的满足了这一需求,将时间窗口设置为key的失效时间,然后将key的值每次请求+1即可.伪代码实现思路:

//1.判断是否存在该keyif(EXIT(key)){  // 1.1自增后判断是否大于最大值,并返回结果  if(INCR(key) > maxPermit){     return false;  } return true;}//2.不存在key,则设置key初始值为1,失效时间为3秒SET(KEY,1);EXPIRE(KEY,3);

漏铜算法

漏桶算法核心概念：

• 桶的容量是固定的,并且水流以一个固定的速率流出；

• 流入的水流可以是任意速率；

• 如果流入的水流超出了桶的容量，则后续流入的水流溢出(请求被丢弃)。

• 如果桶内没有水,则不需要流出

缺点:

不难想象漏桶算法并不能很好的应对突发的流量限制,在某一个时间段流量激增,则漏桶算法处理就比较无能为力.这个时候就需要用到和他相反设计的令牌桶算法

令牌桶算法:

如上图所示,整个请求流程一目了然.简单概括如下:

用户请求资源时首选从桶里获取令牌,如果有令牌则放行,如此同时桶里的令牌数量-1

于此同时,以一定的速率往桶里加入令牌,这个速度是可根据实际场景随意设置.

算法实现

var key;var maxPermit;//桶的容量,即最大请求限制var expire;//失效时间var bucketInterval;//每次向桶里添加令牌的时间间隔var bucketNum;//每次向桶里添加令牌的个数var lastTimeKey = key +"last";//标记上一次操作时间//判断是否存在该keyif(EXIT(key)){  var value = GET(key);  var diffTime = now() - lastTimeKey;  // 1.1判断是否超出时间间隔  if(diffTime  > bucketInterval){      // 1.2根据时间间隔,计算出应该向桶里添加令牌的个数      local maxValue = value+math.floor(diff/interval)*step;      if (maxValue > limit)         value = limit;      else         value = maxValue;     //设置key的值及操作时间     SET(key,value);     SET(lastTimeKey,now());       }  // 2.1在时间间隔内,判断桶里是否有值  if(value <= 0){     reurn false;  }else{    // 2.2 减1    DECR(key);  }reture true;}//2.不存在key,则设置key初始值为maxPermit-1SET(key,maxPermit-1);EXPIRE(lastTimeKey,now());

上面实现代码只是伪代码,提供的是一种思路而已. 仔细想来其中某个环节其实并不完美.大家可以参考Guava的ratelimit实现思路,他的限流就是基于令牌桶算法,但是比较遗憾的是在单机下的限流.

思考:  

就是时间间隔如果过长的话,一次性向桶里添加的令牌数量则是桶的最大容量!那么某个时间的瞬间请求过来,服务器的压力是非常大的.

所以此处增加令牌数可以设置的稍微合理些,哪怕间隔时间再长!

“redis lua限流算法如何实现”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站，小编将为大家输出更多高质量的实用文章！