当前位置: 首页 > news >正文

滑动时间窗口的思想和实现,环形数组,golang

固定时间窗口

在开发限流组件的时候,我们需要统计一个时间区间内的请求数,比如以分钟为单位。所谓固定时间窗口,就是根据时间函数得到当前请求落在哪个分钟之内,我们在统计的时候只关注当前分钟之内的数量,即 [0s, 60s],因为流量并不是均匀的,所以就会出现,在两个分钟之间超过阈值,1分50秒时来了150个请求,在2分10秒时来了150个请求,如果我们设置的阈值是200,这就超过了阈值,这会对系统造成隐患。

固定时间窗口的主要特征是:取样窗口直接从当前分钟跳到下一分钟。

滑动时间窗口

如果一个请求到达,我们根据请求的时间,倒推一分钟,然后统计此区间的请求数,来判断是否超过阈值,这就是滑动窗口,即,窗口是缓慢滑动的。显然这种方式效率不高,每次都要统计。

做一个折中,将一分钟分成10个小窗口,每个请求都落到其中一个小窗口上,每次以小窗口为单位移动,并且请求数实时统计到小窗口中,这样只需要将10个窗口加起来和阈值比较。

实现原理

此处可以参考环形队列的设计思想,采样长度为10的数组作为小窗口,一个游标指向最新的窗口(时间最新),如果窗口发生了滑动,就将游标移动到特定位置。

在这里插入图片描述

由于请求的到来不是连续的,所以Front的移动可能是跳跃式的。

每向前滑动一个小窗口,就意味着头部增加一个,尾部舍弃一个,如果发生了跳跃,那么尾部要舍弃多个,同时中间要补0。即,从第二圈开始,Front 划过的地方都要被置为0。

简单模拟如下,第一行值为9的地方为Front,向右滑动,来到第二行,依次类推。在第四行时出现了跳跃。

0123456789
123456789x
23456789xy
56789xy00z
整理
0123456789
x123456789
xy23456789
xy00z56789

算法与测试

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

固定时间窗口 在开发限流组件的时候&#xff0c;我们需要统计一个时间区间内的请求数&#xff0c;比如以分钟为单位。所谓固定时间窗口&#xff0c;就是根据时间函数得到当前请求落在哪个分钟之内&#xff0c;我们在统计的时候只关注当前分钟之内的数量&#xff0c;即 [0s, 60…...

SpringBoot 使用异步方法

SpringBoot 使用异步方法 在pom文件引入相关依赖&#xff1a; <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter</artifactId></dependency><dependency><groupId>org.springframe…...

Django框架学习大纲

对于使用 Python 的 Django 框架进行 web 开发的程序员来说&#xff0c;以下几点是必须了解的。 环境配置与项目初始化 命令&#xff1a; pip install django django-admin startproject myproject解析&#xff1a; 使用 pip 安装 Django。使用 django-admin startproject …...

基于matlab实现的电力系统稳定性分析摆幅曲线代码

完整程序&#xff1a; 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开源项目&#xff0c;是一个支持动态Sql语句的持久层框架。Mybatis可以将Sql语句配置在XML文件中&#xff0c;避免将Sql语句硬编…...

c++23中的新功能之十四输入输出指针

一、介绍 在c的发展过程中&#xff0c;无论如何发展&#xff0c;c都尽量保持着与C语言的兼容&#xff0c;当然这也是它的一个特点。在实际的应用中&#xff0c;开发者经常遇到的一个问题是&#xff0c;如何把一个指针的值给传出来&#xff1f;有人会说&#xff0c;简单啊&…...

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」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

超简单,几行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》算例&#xff0c;实现了C&CG和benders算法两部分内容&#xff0c;通过…...

二进制安全虚拟机Protostar靶场(4)写入shellcode,基础知识讲解 Stack Five

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

【Flink实战】玩转Flink里面核心的Source Operator实战

&#x1f680; 作者 &#xff1a;“大数据小禅” &#x1f680; 文章简介 &#xff1a;【Flink实战】玩转Flink里面核心的Source Operator实战 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 目录导航 Flink 的API层级介绍Source Operator速览Flin…...

[2023-09-12]Oracle备库查询报ORA-01187

一个多表关联的语句在备库执行查询时提示ORA-01187: cannot read from file because it failed verification tests&#xff0c;单独对某一个表查询则正常返回&#xff08;因为不需要排序等&#xff0c;没有用到临时表空间&#xff09;。 查看报错信息发现是提示的临时数据文件…...

leetcode 16.最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数&#xff0c;使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。 示例 1&#xff1a; 输入&#xff1a;nums [-1,2,1,-4], target 1 输出&#xff1a;…...

antd table 自定义排序图标

要在Ant Design的Table组件中自定义排序图标&#xff0c;可以使用sorter和sortDirections属性来实现自定义排序逻辑和图标。以下是一个示例&#xff0c;演示如何在Ant Design的Table中自定义排序图标&#xff1a; import React, { useState } from react; import { Table, Spa…...

第十九章、【Linux】开机流程、模块管理与Loader

19.1.1 开机流程一览 以个人计算机架设的 Linux 主机为例&#xff0c;当你按下电源按键后计算机硬件会主动的读取 BIOS 或 UEFI BIOS 来载入硬件信息及进行硬件系统的自我测试&#xff0c; 之后系统会主动的去读取第一个可开机的设备 &#xff08;由 BIOS 设置的&#xff09; …...

GMAC PHY介绍

1.1PHY接口发展 &#xff08;1&#xff09;MII支持10M/100Mbps&#xff0c;一个接口由14根线组成&#xff0c;它的支持还是比较灵活的&#xff0c;但是有一个缺点是因为它一个端口用的信号线太多。参考芯片&#xff1a;DP83848 、DM900A&#xff08;该芯片内部集成了MAC和PHY接…...

华为OD机考算法题:最远足迹

目录 题目部分 解读与分析 代码实现 题目部分 题目最远足迹难度易题目说明某探险队负责对地下洞穴进行探险。 探险队成员在进行探险任务时&#xff0c;随身携带的记录器会不定期地记录自身的坐标&#xff0c;但在记录的间隙中也会记录其他数据。探索工作结束后&#xff0c;…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

数学建模-滑翔伞伞翼面积的设计,运动状态计算和优化 !

我们考虑滑翔伞的伞翼面积设计问题以及运动状态描述。滑翔伞的性能主要取决于伞翼面积、气动特性以及飞行员的重量。我们的目标是建立数学模型来描述滑翔伞的运动状态,并优化伞翼面积的设计。 一、问题分析 滑翔伞在飞行过程中受到重力、升力和阻力的作用。升力和阻力与伞翼面…...

数据结构:递归的种类(Types of Recursion)

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...