网站域名解析设置,泰兴住房和城乡建设厅网站,鞍山做网站公司,网站app生成器固定时间窗口
在开发限流组件的时候#xff0c;我们需要统计一个时间区间内的请求数#xff0c;比如以分钟为单位。所谓固定时间窗口#xff0c;就是根据时间函数得到当前请求落在哪个分钟之内#xff0c;我们在统计的时候只关注当前分钟之内的数量#xff0c;即 [0s, 60…固定时间窗口
在开发限流组件的时候我们需要统计一个时间区间内的请求数比如以分钟为单位。所谓固定时间窗口就是根据时间函数得到当前请求落在哪个分钟之内我们在统计的时候只关注当前分钟之内的数量即 [0s, 60s]因为流量并不是均匀的所以就会出现在两个分钟之间超过阈值1分50秒时来了150个请求在2分10秒时来了150个请求如果我们设置的阈值是200这就超过了阈值这会对系统造成隐患。
固定时间窗口的主要特征是取样窗口直接从当前分钟跳到下一分钟。
滑动时间窗口
如果一个请求到达我们根据请求的时间倒推一分钟然后统计此区间的请求数来判断是否超过阈值这就是滑动窗口即窗口是缓慢滑动的。显然这种方式效率不高每次都要统计。
做一个折中将一分钟分成10个小窗口每个请求都落到其中一个小窗口上每次以小窗口为单位移动并且请求数实时统计到小窗口中这样只需要将10个窗口加起来和阈值比较。
实现原理
此处可以参考环形队列的设计思想采样长度为10的数组作为小窗口一个游标指向最新的窗口时间最新如果窗口发生了滑动就将游标移动到特定位置。 由于请求的到来不是连续的所以Front的移动可能是跳跃式的。
每向前滑动一个小窗口就意味着头部增加一个尾部舍弃一个如果发生了跳跃那么尾部要舍弃多个同时中间要补0。即从第二圈开始Front 划过的地方都要被置为0。
简单模拟如下第一行值为9的地方为Front向右滑动来到第二行依次类推。在第四行时出现了跳跃。
0123456789123456789x23456789xy56789xy00z整理0123456789x123456789xy23456789xy00z56789
算法与测试
package pluginimport (logtime
)// 滑动窗口
type WindowLeapArray struct {Arr []int // 窗口数据Front int // 游标FrontTime int64 // 游标最新时间WindowStatus bool // 窗口状态true 为 拒绝访问
}func NewWindowLeapArray(windowNum int) *WindowLeapArray {return WindowLeapArray{Arr: make([]int, windowNum),}
}// Check 限流计算
func (w *WindowLeapArray) Check(threshold int) bool {timenow : time.Now()start : w.FrontTimefrontTimeLeft : timenow.UnixMilli() - timenow.UnixMilli()%100index : (timenow.UnixMilli() - 1000*timenow.Unix()) / 100if w.FrontTime 0 {// 记为小窗口的左侧时间 1694678187869 - 1694678187800w.FrontTime frontTimeLeftw.Front int(index)w.Arr[w.Front]log.Println(timenow.UnixMilli(), start, (timenow.UnixMilli()-start)/100, w.Arr)return true}// 时间差gaptime : (timenow.UnixMilli() - w.FrontTime)if gaptime 100 {// 同一小窗口if w.WindowStatus {log.Println(timenow.UnixMilli(), start, (timenow.UnixMilli()-start)/100, w.Arr)return false}// 统计var sum intfor _, v : range w.Arr {sum sum v}if sum threshold {w.WindowStatus truelog.Println(timenow.UnixMilli(), start, (timenow.UnixMilli()-start)/100, w.Arr)return false} else {w.Arr[w.Front]}} else {// 滑动采用环形数组// 可能存在跳跃w.WindowStatus falsew.FrontTime frontTimeLeftgap : gaptime / 100if gap 10 {for i : 0; i 10; i {w.Arr[i] 0}} else {for i : 1; i int(gap); i {tmp : w.Front iif tmp 10 {tmp tmp - 10}w.Arr[tmp] 0}}w.Front int(index)// 统计var sum intfor _, v : range w.Arr {sum sum v}if sum threshold {w.WindowStatus truelog.Println(timenow.UnixMilli(), start, (timenow.UnixMilli()-start)/100, w.Arr)return false} else {w.Arr[w.Front] 1}}log.Println(timenow.UnixMilli(), start, (timenow.UnixMilli()-start)/100, w.Arr)return true
}单元测试
func TestFun(t *testing.T) {w : plugin.NewWindowLeapArray(10)for i : 0; i 30; i {re : w.GlobalCheck()log.Println(re)n : util.RandInt(30, 3000)time.Sleep(time.Duration(n) * time.Millisecond)}
}输出
2023/09/15 11:48:09 1694749689568 0 16947496895 [0 0 0 0 0 1 0 0 0 0]
2023/09/15 11:48:09 true
2023/09/15 11:48:11 1694749691250 1694749689500 17 [0 0 1 0 0 0 0 0 0 0]
2023/09/15 11:48:11 true
2023/09/15 11:48:12 1694749692007 1694749691200 8 [1 0 1 0 0 0 0 0 0 0]
2023/09/15 11:48:12 true
2023/09/15 11:48:12 1694749692083 1694749692000 0 [2 0 1 0 0 0 0 0 0 0]
2023/09/15 11:48:12 true
2023/09/15 11:48:13 1694749693857 1694749692000 18 [0 0 0 0 0 0 0 0 1 0]
2023/09/15 11:48:13 true
2023/09/15 11:48:14 1694749694213 1694749693800 4 [0 0 1 0 0 0 0 0 1 0]
2023/09/15 11:48:14 true
2023/09/15 11:48:15 1694749695227 1694749694200 10 [0 0 1 0 0 0 0 0 0 0]
2023/09/15 11:48:15 true
2023/09/15 11:48:15 1694749695388 1694749695200 1 [0 0 1 1 0 0 0 0 0 0]
2023/09/15 11:48:15 true
2023/09/15 11:48:16 1694749696076 1694749695300 7 [1 0 1 1 0 0 0 0 0 0]
2023/09/15 11:48:16 true
2023/09/15 11:48:16 1694749696590 1694749696000 5 [1 0 0 0 0 1 0 0 0 0]
2023/09/15 11:48:16 true
2023/09/15 11:48:18 1694749698828 1694749696500 23 [0 0 0 0 0 0 0 0 1 0]
2023/09/15 11:48:18 true
2023/09/15 11:48:20 1694749700913 1694749698800 21 [0 0 0 0 0 0 0 0 0 1]
2023/09/15 11:48:20 true
2023/09/15 11:48:22 1694749702052 1694749700900 11 [1 0 0 0 0 0 0 0 0 0]
2023/09/15 11:48:22 true
2023/09/15 11:48:23 1694749703076 1694749702000 10 [1 0 0 0 0 0 0 0 0 0]
2023/09/15 11:48:23 true
2023/09/15 11:48:23 1694749703422 1694749703000 4 [1 0 0 0 1 0 0 0 0 0]
2023/09/15 11:48:23 true
2023/09/15 11:48:23 1694749703781 1694749703400 3 [1 0 0 0 1 0 0 1 0 0]
2023/09/15 11:48:23 true
2023/09/15 11:48:23 1694749703990 1694749703700 2 [1 0 0 0 1 0 0 1 0 1]
2023/09/15 11:48:23 true
2023/09/15 11:48:26 1694749706029 1694749703900 21 [1 0 0 0 0 0 0 0 0 0]
2023/09/15 11:48:26 true
2023/09/15 11:48:28 1694749708168 1694749706000 21 [0 1 0 0 0 0 0 0 0 0]
2023/09/15 11:48:28 true
2023/09/15 11:48:29 1694749709514 1694749708100 14 [0 0 0 0 0 1 0 0 0 0]
2023/09/15 11:48:29 true
2023/09/15 11:48:30 1694749710850 1694749709500 13 [0 0 0 0 0 0 0 0 1 0]
2023/09/15 11:48:30 true
......推理过程 网关既要支持全局限流也要支持IP限流完整代码
