[Go]GO实现滑动窗口限流算法-单机版
本代码基于原博客java版本的GO实现 , 原文解释也比较详细 , 这里也放上原文链接:https://www.cnblogs.com/dijia478/p/13807826.html
具体解释如下 , 代码在最下面
1.10秒内通过5次 , 这条线就是队列list,当第一个事件进来,队列大小是0,时间是第1秒:
2.因为size=0,小于5,都没有到限制的次数,完全不用考虑时间窗口,直接把这次事件的时间戳放到0的位置:
3.第2.8秒的时候,第二个事件来了。因为此时size=1,还是小于5,把这次事件的时间戳放到0的位置,原来第1秒来的事件时间戳会往后移动一格:
4.陆续的又来了3个事件,队列大小变成了5,先来的时间戳依次向后移动。此时,第6个事件来了,时间是第8秒:
5.因为size=5,不小于5,此时已经达到限制次数,以后都需要考虑时间窗口了。所以取出位置4的时间(离现在最远的时间),和第6个事件的时间戳做比较:
6.得到的差是7秒,小于时间窗口10秒,说明在10秒内,来的事件个数大于5了,所以本次不允许通过:
7.接下来即便来上100个事件,只要时间差小于等于10秒,都同上,拒绝通过:
8.第11.1秒,第101次事件过来了。因为size=5,不小于5,所以取出位置4的时间(离现在最远的时间),和第101个事件的时间戳做比较:
9.得到的差是10.1秒,大于时间窗口10秒,说明在10秒内,来的事件个数小于等于5了,所以本次允许通过:
10.删除位置4的时间(离现在最远的时间),把这次事件的时间戳放到0的位置,后面的时间戳依次向后移动:
往后再来其他事件,就是重复4-10的步骤,即可实现,在任意滑动时间窗口内,限制通过的次数
其本质思想是转换概念,将原本问题的确定时间大小,进行次数限制。转换成确定次数大小,进行时间限制。
package utils import "time" var LimitQueue map[string][]int64 var ok bool //单机时间滑动窗口限流法 func LimitFreqSingle(queueName string, count uint, timeWindow int64) bool { currTime := time.Now().Unix() if LimitQueue == nil { LimitQueue = make(map[string][]int64) } if _, ok = LimitQueue[queueName]; !ok { LimitQueue[queueName] = make([]int64, 0) } //队列未满 if uint(len(LimitQueue[queueName])) < count { LimitQueue[queueName] = append(LimitQueue[queueName], currTime) return true } //队列满了,取出最早访问的时间 earlyTime := LimitQueue[queueName][0] //说明最早期的时间还在时间窗口内,还没过期,所以不允许通过 if currTime-earlyTime <= timeWindow { return false } else { //说明最早期的访问应该过期了,去掉最早期的 LimitQueue[queueName] = LimitQueue[queueName][1:] LimitQueue[queueName] = append(LimitQueue[queueName], currTime) } return true }
使用的案例:
func limitIpFreq(c *gin.Context, timeWindow int64, count uint) bool { ip := c.ClientIP() key := "limit:" + ip if !utils.LimitFreqSingle(key, count, timeWindow) { c.JSON(200, gin.H{ "code": 400, "msg": "error Current IP frequently visited", }) return false } return true }
相关文章
- 我的go+初体验——大一从c++到go+的快速上手
- 蓝桥杯2020c++B组省赛
- Power BI 基于门店位置的产品销售排行
- Power BI基于门店位置的业绩达成表现
- Power BI模拟麦肯锡客流转化漏斗图
- Linux系列(31) - rpm命令管理之升级与卸载命令(3)
- Linux系列(30) - rpm命令管理之安装命令(2)
- Linux系列(29) - rpm包命名规则(1)
- Linux系列(28) - 软件包简介
- Linux系列(27) - 三剑客grep、awk、sed
- Linux系列(26) - 强制杀死进程
- Linux系列(25) - 常用快捷键(未更新完)
- 说说Golang goroutine并发那些事儿
- Linux系列(24) - chmod
- Linux系列(23) - echo
- Linux系列(22) - 用户登录查看命令
- Linux系列(21) - 光盘、U盘挂载
- Linux系列(20) - shutdown
- Linux系列(19) - 常用压缩命令(2)
- Linux系列(18) - 常用压缩命令(1)