滑动时间窗口的思想和实现,环形数组,golang
固定时间窗口
在开发限流组件的时候,我们需要统计一个时间区间内的请求数,比如以分钟为单位。所谓固定时间窗口,就是根据时间函数得到当前请求落在哪个分钟之内,我们在统计的时候只关注当前分钟之内的数量,即 [0s, 60s],因为流量并不是均匀的,所以就会出现,在两个分钟之间超过阈值,1分50秒时来了150个请求,在2分10秒时来了150个请求,如果我们设置的阈值是200,这就超过了阈值,这会对系统造成隐患。
固定时间窗口的主要特征是:取样窗口直接从当前分钟跳到下一分钟。
滑动时间窗口
如果一个请求到达,我们根据请求的时间,倒推一分钟,然后统计此区间的请求数,来判断是否超过阈值,这就是滑动窗口,即,窗口是缓慢滑动的。显然这种方式效率不高,每次都要统计。
做一个折中,将一分钟分成10个小窗口,每个请求都落到其中一个小窗口上,每次以小窗口为单位移动,并且请求数实时统计到小窗口中,这样只需要将10个窗口加起来和阈值比较。
实现原理
此处可以参考环形队列的设计思想,采样长度为10的数组作为小窗口,一个游标指向最新的窗口(时间最新),如果窗口发生了滑动,就将游标移动到特定位置。
由于请求的到来不是连续的,所以Front
的移动可能是跳跃式的。
每向前滑动一个小窗口,就意味着头部增加一个,尾部舍弃一个,如果发生了跳跃,那么尾部要舍弃多个,同时中间要补0。即,从第二圈开始,Front 划过的地方都要被置为0。
简单模拟如下,第一行值为9
的地方为Front
,向右滑动,来到第二行,依次类推。在第四行时出现了跳跃。
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | x | |||||
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | x | y | |||||
5 | 6 | 7 | 8 | 9 | x | y | 0 | 0 | z | |||||
整理 | ||||||||||||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |||||
x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |||||
x | y | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |||||
x | y | 0 | 0 | z | 5 | 6 | 7 | 8 | 9 |
算法与测试
package pluginimport ("log""time"
)// 滑动窗口
type WindowLeapArray struct {Arr []int // 窗口数据WindowsNum int // 样本窗口个数,设置为10Front int // 游标FrontTime int64 // 游标最新时间RequestNumPerSecond int // 限制请求数WindowStatus bool // 窗口状态,true 为 拒绝访问
}func NewWindowLeapArray(requestNumPerSecond int) *WindowLeapArray {return &WindowLeapArray{Arr: make([]int, 10),WindowsNum: 10,RequestNumPerSecond: requestNumPerSecond,}
}// GlobalCheck 全局限流
func (w *WindowLeapArray) GlobalCheck() 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 >= w.RequestNumPerSecond {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 >= w.RequestNumPerSecond {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
......
推理过程
相关文章:

滑动时间窗口的思想和实现,环形数组,golang
固定时间窗口 在开发限流组件的时候,我们需要统计一个时间区间内的请求数,比如以分钟为单位。所谓固定时间窗口,就是根据时间函数得到当前请求落在哪个分钟之内,我们在统计的时候只关注当前分钟之内的数量,即 [0s, 60…...
SpringBoot 使用异步方法
SpringBoot 使用异步方法 在pom文件引入相关依赖: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter</artifactId></dependency><dependency><groupId>org.springframe…...
Django框架学习大纲
对于使用 Python 的 Django 框架进行 web 开发的程序员来说,以下几点是必须了解的。 环境配置与项目初始化 命令: pip install django django-admin startproject myproject解析: 使用 pip 安装 Django。使用 django-admin startproject …...

基于matlab实现的电力系统稳定性分析摆幅曲线代码
完整程序: clear; clc; t 0; tf 0; tfl 0.5; tc 0.5; % tc 0.05, 0.125, 0.5 sec for 2.5 cycles, 6.25 cycles & 25 cycles resp ts 0.05; m 2.52 / (180 * 50); i 2; dt 21.64 * pi / 180; ddt 0; time(1) 0; ang(1) 21.64; pm 0.9; pm1 2.44;…...

mybatis基本构成mybatis与hibernate的区别添加mybatis支持
目录 1. mybatis简介 2. mybatis基本构成 3. mybatis与hibernate的区别 4. 项目中添加mybatis支持 1. mybatis简介 Mybatis是Apache的一个Java开源项目,是一个支持动态Sql语句的持久层框架。Mybatis可以将Sql语句配置在XML文件中,避免将Sql语句硬编…...
c++23中的新功能之十四输入输出指针
一、介绍 在c的发展过程中,无论如何发展,c都尽量保持着与C语言的兼容,当然这也是它的一个特点。在实际的应用中,开发者经常遇到的一个问题是,如何把一个指针的值给传出来?有人会说,简单啊&…...

Day42:网易云项目,路由进阶
网易云项目 创建、启动项目并配置路由 npm init vite npm i npm i vue-router npm i sass -D 在main.js中 import router from ./router createApp(App).use(router).mount(#app) 在index中配置路由 import {createRouter,createWebHistory} from vue-router import H…...

Open3D(C++) 三维点云边界提取
目录 一、算法原理二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、算法原理 见:PCL 点云边界提取 二、代码实现 BoundaryEstimation.h #pragma...
AUTOSAR汽车电子嵌入式编程精讲300篇-经典 AUTOSAR 安全防御能力的分析及改善
目录 前言 研究现状 经典 AUTOSAR 概述 2.1 经典 AUTOSAR 架构 2.2 经典 AUTOSAR 应用层...

LeetCode 1584. 连接所有点的最小费用【最小生成树】
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...

超简单,几行js代码就实现一个 vue3 的数字滚动效果!
预览效果 1. 创建一个template <template><div class"num-warp"><template v-for"item in numStr"><div v-if"item ," class"dot">,</div><divv-elseclass"num-box":style"{transf…...

两阶段鲁棒优化matlab实现——CCG和benders
目录 1 主要内容 2 部分代码 3 程序结果 4 程序链接 1 主要内容 程序采用matlab复现经典论文《Solving two-stage robust optimization problems using a column-and-constraint generation method》算例,实现了C&CG和benders算法两部分内容,通过…...

二进制安全虚拟机Protostar靶场(4)写入shellcode,基础知识讲解 Stack Five
前言 这是一个系列文章,之前已经介绍过一些二进制安全的基础知识,这里就不过多重复提及,不熟悉的同学可以去看看我之前写的文章 二进制安全虚拟机Protostar靶场 安装,基础知识讲解,破解STACK ZERO https://blog.csdn.net/qq_45894840/artic…...

【Flink实战】玩转Flink里面核心的Source Operator实战
🚀 作者 :“大数据小禅” 🚀 文章简介 :【Flink实战】玩转Flink里面核心的Source Operator实战 🚀 欢迎小伙伴们 点赞👍、收藏⭐、留言💬 目录导航 Flink 的API层级介绍Source Operator速览Flin…...
[2023-09-12]Oracle备库查询报ORA-01187
一个多表关联的语句在备库执行查询时提示ORA-01187: cannot read from file because it failed verification tests,单独对某一个表查询则正常返回(因为不需要排序等,没有用到临时表空间)。 查看报错信息发现是提示的临时数据文件…...
leetcode 16.最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 示例 1: 输入:nums [-1,2,1,-4], target 1 输出:…...
antd table 自定义排序图标
要在Ant Design的Table组件中自定义排序图标,可以使用sorter和sortDirections属性来实现自定义排序逻辑和图标。以下是一个示例,演示如何在Ant Design的Table中自定义排序图标: import React, { useState } from react; import { Table, Spa…...

第十九章、【Linux】开机流程、模块管理与Loader
19.1.1 开机流程一览 以个人计算机架设的 Linux 主机为例,当你按下电源按键后计算机硬件会主动的读取 BIOS 或 UEFI BIOS 来载入硬件信息及进行硬件系统的自我测试, 之后系统会主动的去读取第一个可开机的设备 (由 BIOS 设置的) …...

GMAC PHY介绍
1.1PHY接口发展 (1)MII支持10M/100Mbps,一个接口由14根线组成,它的支持还是比较灵活的,但是有一个缺点是因为它一个端口用的信号线太多。参考芯片:DP83848 、DM900A(该芯片内部集成了MAC和PHY接…...
华为OD机考算法题:最远足迹
目录 题目部分 解读与分析 代码实现 题目部分 题目最远足迹难度易题目说明某探险队负责对地下洞穴进行探险。 探险队成员在进行探险任务时,随身携带的记录器会不定期地记录自身的坐标,但在记录的间隙中也会记录其他数据。探索工作结束后,…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...

如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...