基于 golang 从零到一实现时间轮算法 (一)

前言

时间轮是用来解决海量百万级定时器(或延时)任务的最佳方案,linux 的内核定时器就是采用该数据结构实现。


应用场景

  1. 自动删除缓存中过期的 Key:缓存中设置了 TTL 的 kv,通过把该 key 对应的 TTL 以及回调方法注册到 timewheel,到期直接删除
  2. 延时任务,将任务注册到 timewheel,过期自动触发执行
  3. 在 TcpServer 中,用来管理海量 Tcp 连接的超时定时器,如 zinx 的定时器 实现

简单时间轮

在这里插入图片描述
如上图,一个普通的时间轮,类似于时钟表盘,指针(pointer)每隔一段时间前进一格(interval,tick 一次),一圈代表一个周期(circle),定时任务以链表(双向)方式置放在表盘的刻度处,当指针前进到当前位置时,遍历任务链表,执行相应的任务。

基本模型构成

  1. tickMs(基本时间跨度):时间轮由多个时间格组成,每个时间格代表当前时间轮的基本时间跨度(tickMs)。
  2. wheelSize(时间单位个数):时间轮的时间格个数是固定的,可用(wheelSize)来表示,那么整个时间轮的总体时间跨度(interval)可以通过公式tickMs × wheelSize计算得出。
  3. currentTime(当前所处时间):时间轮还有一个表盘指针(currentTime),用来表示时间轮当前所处的时间,currentTime是 tickMs 的整数倍。currentTime 可以将整个时间轮划分为到期部分和未到期部分,currentTime当前指向的时间格也属于到期部分,表示刚好到期,需要处理此时间格所对应的 TimerTaskList 的所有任务。

从开发角度而言,实现一个时间轮:

  1. 时间轮是一个由固定长度 length 的数组(本例子中就是 [1,12])构造而成的环形队列
  2. 时间轮的长度决定了延时任务的刻度,假设上面的刻度为 1s(即时间轮 1s 前进一格),那么该时间轮只能表达延时任务在 1s 至 12s内的任务;时间轮的长度也即时间轮的周期(12s)
  3. 注册任务按照 当前刻度 + 延时时长 % 时间轮周期 计算得出,假设当前指针在 5s的位置,此时添加一个延时周期为 5s 的任务,那么该任务需要注册到刻度为 10s 的格子对应的任务链表中
  4. 数组中的每个元素都指向一个双向链表,用于存储对应的延时任务
  5. 时间轮的插入复杂度是 O(1),删除指定节点的复杂度是O(n),因为需要遍历双向链表以查找到要删除的节点
  6. 当时间轮指针转动到对应的单元格时,顺序执行双向链表中存储的任务基础时间轮的缺点是无法注册延时超过时间轮周期的任务,如何解决呢?

基础时间轮的缺点是无法注册延时超过时间轮周期的任务,如何解决呢?

解决方法 1:加 circle 计数器

此方法相当于给双向链表中存储的任务加多一个 “圈数” 的维度
在这里插入图片描述
• 假设时间轮有8个刻度
• 计时器值 = 17
• 走两圈时间轮+多走1个刻度
• 在"0"这个桶中设置计时器
• 与计时器一同保留#圈数
• 在到期处理时,如果#圈数 > 0,则重新插入计时器

注意,此策略中,时间轮指针每前进一格,需要把此格对应的任务链表中,所有的任务的 circle 计数器都减 1,如果 circle==0,那么说明,任务时间已到期,执行该任务

解决方法 2:层级时间轮

这是一种典型的 “空间换时间” 的思路,按照时间轮周期的倍数进行合理分层,有两个优点:

  1. 避免任务堆积在某个 slot 上
  2. 支持任意长时间的延时任务注册
    在这里插入图片描述
    复用之前的案例,第一层的时间轮 tickMs=1ms, wheelSize=20, interval=20ms。第二层的时间轮的 tickMs 为第一层时间轮的 interval,即为 20ms。每一层时间轮的 wheelSize 是固定的,都是 20,那么第二层的时间轮的总体时间跨度 interval 为 400ms。以此类推,这个 400ms 也是第三层的 tickMs 的大小,第三层的时间轮的总体时间跨度为 8000ms。

关于层级时间轮,可以参考普通的时间。多层时间轮的概念也非常清晰,将时间轮分为多个,每两个轮之间是进位的关系,例如最普遍的秒,分,时.即:

  • 秒级时间轮上,设有60个槽, 每两个槽之间的时间为1s.
  • 分钟级时间轮上,设有60s个槽,每两个槽之间的时间为1min
  • 小时级时间轮上,设有24个槽,每两个槽之间的时间为1h
    在这里插入图片描述
    这样,秒级每走60个槽,时间过去一分钟,秒级时间轮归零,分级时间轮走一个槽; 分级时间轮每走过60个槽,时间过去一小时,分级时间轮归零,小时级时间轮走一个槽.

通过三级时间轮,只需要遍历60+60+60 =180个槽,就可以成为一个精度为1s, 周期为60x60x60 = 216000s的定时调度器.


参考

https://zhuanlan.zhihu.com/p/658079556,
https://pandaychen.github.io/2022/05/28/A-TIMEWHEEL-ANALYSIS/
https://juejin.cn/post/7083795682313633822

属于在以上博客基础上记录的个人笔记。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/179660.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

第六讲:VBA与ACCESS的ADO连接中,所涉及的对象

《VBA数据库解决方案》教程(10090845)是我推出的第二套教程,目前已经是第二版修订了。这套教程定位于中级,是学完字典后的另一个专题讲解。数据库是数据处理的利器,教程中详细介绍了利用ADO连接ACCDB和EXCEL的方法和实…

vue 获取上一周和获取下一周的日期时间

效果图&#xff1a; 代码&#xff1a; <template><div><div style"padding: 20px 0;"><div style"margin-left: 10px; border-left: 5px solid #0079fe; font-size: 22px; font-weight: 600; padding-left: 10px">工作计划</…

uni-app离线打包在android studio创建的.jks证书,签名文件获取MD5问题

获取证书信息 keytool -list -v -keystore test.keystore 获取的信息中没有md5信息 可以使用以下方式获取md5. 先创建签名文件&#xff0c;放到项目目录下 配置build.gradle文件 在android studio 打开终端输入以下命令 ./gradlew signingReport 等待生成签名。 生成的内容…

uniapp subNvue 写的视频播放

文件下载地址 https://download.csdn.net/download/weixin_47517731/88500016https://download.csdn.net/download/weixin_47517731/88500016 1:在pages.json中配置视频播放页面 {/* 视频详情页面 */"path": "pages/detail-video/detail","style&q…

Android ConstraintLayout分组堆叠圆角ShapeableImageView

Android ConstraintLayout分组堆叠圆角ShapeableImageView <?xml version"1.0" encoding"utf-8"?> <androidx.constraintlayout.widget.ConstraintLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:app"…

【凡人修仙传】定档曝光,最新更新时间有所调整,期待值暴涨

Hello,小伙伴们&#xff0c;我是小郑继续为大家深度解析国漫资讯。 深度爆料&#xff0c;备受瞩目的动漫作品《凡人修仙传》终于在新年之际宣布定档了&#xff01;这个消息让广大动漫爱好者们激动不已。在某知名视频网站上&#xff0c;这部作品的官方发布了一个名为“新年番定…

Shell变量

Shell变量 本地变量变量定义取出变量值 特殊参数变量⾯试题分享 特殊状态变量脚本控制返回值获取上⼀次后台进程的PID再来分享一道面试题&#xff1a; 获取当前脚本的PID获取上次命令的最后一个参数 本地变量 定义Shell变量&#xff0c;变量名不需要加美元符 $ 本地变量只在⽤…

JS异常处理——throw和try、catch以及debugger

让我为大家介绍一下异常处理吧&#xff01; 异常处理是指预估代码执行过程中可能发生的错误&#xff0c;然后最大程度的避免错误的发生导致整个程序无法继续运行 throw 抛异常 第一种写法 function fun(x, y) {// undefined是false 但取反就是trueif (!x || !y) {// 第一种写…

【ChatGPT瀑布到水母】AI 在驱动软件研发的革新与实践

这里写目录标题 前言内容简介作者简介专家推荐读者对象目录直播预告 前言 计算机技术的发展和互联网的普及&#xff0c;使信息处理和传输变得更加高效&#xff0c;极大地改变了金融、商业、教育、娱乐等领域的运作方式。数据分析、人工智能和云计算等新兴技术&#xff0c;也在不…

VM虚拟机逆向 --- [NCTF 2018]wcyvm 复现

文章目录 前言题目分析 前言 第四题了&#xff0c;搞定&#xff0c;算是独立完成比较多的一题&#xff0c;虽然在还原汇编的时候还是很多问题。 题目分析 代码很简单&#xff0c;就是指令很多。 opcode在unk_6021C0处&#xff0c;解密的数据在dword_6020A0处 opcode [0x08, …

众佰诚:新手如何在抖音电商中脱颖而出

在这个信息爆炸的时代&#xff0c;短视频平台抖音已经成为了人们获取信息、娱乐和购物的重要渠道。越来越多的商家开始在抖音上开设店铺&#xff0c;希望通过这个平台实现销售增长。然而&#xff0c;对于新手来说&#xff0c;如何在众多的竞争对手中脱颖而出&#xff0c;成为了…

人工智能与卫星:颠覆性技术融合开启太空新时代

人工智能与卫星&#xff1a;颠覆性技术融合开启太空新时代 摘要&#xff1a;本文将探讨人工智能与卫星技术的融合&#xff0c;并介绍其应用、发展和挑战。通过深入了解这一领域的前沿动态&#xff0c;我们将展望一个由智能卫星驱动的未来太空时代。 一、引言 近年来&#xf…

时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测

时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测 目录 时序预测 | Python实现ARIMA-CNN-LSTM差分自回归移动平均模型结合卷积长短期记忆神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 时序预测 …

汽车标定技术(一):XCP概述

目录 1.汽车标定概述 2.XCP协议由来及版本介绍 3.XCP技术通览 3.1 XCP上下机通信模型 3.2 XCP指令集 3.2.1 XCP帧结构定义 3.2.2 标准指令集 3.2.3 标定指令集 3.2.4 页切换指令集 3.2.5 数据采集指令集 3.2.6 刷写指令集 3.3 ECU描述文件(A2L)概述 3.3.1 标定上位…

无声的世界,精神科用药并结合临床的一些分析及笔记(十)

目录 回 “ 家 ” 克服恐惧 奥沙西泮 除夕 酒与药 警告 离别 回 “ 家 ” 她的锥切手术进行的很顺利&#xff0c;按计划继续返回安定医院调节心理状态&#xff0c;病友们都盼着我们回“家”。当我俩跨入病区&#xff0c;大家都涌过来帮我们大包小包的拎着行李&#xff0…

【实战Flask API项目指南】之七 用JWT进行用户认证与授权

实战Flask API项目指南之 用JWT进行用户认证与授权 本系列文章将带你深入探索实战Flask API项目指南&#xff0c;通过跟随小菜的学习之旅&#xff0c;你将逐步掌握 Flask 在实际项目中的应用。让我们一起踏上这个精彩的学习之旅吧&#xff01; 前言 当小菜踏入Flask后端开发…

[云原生1. ] 使用Docker-compose一键部署Wordpress平台

文章目录 1. Docker-compose概述1.1 简介1.2 docker-compose 的三大概念1.3 docker-compose配置模板文件常用的字段1.4 docker-compose 常用命令及格式 2. YAML 文件的详细介绍及编写注意事项2.1 简介2.2 yaml的特性2.2.1 语法特点2.2.2 数据结构2.2.3 引号的区别2.2.4 内置类型…

剑指JUC原理-9.Java无锁模型

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱吃芝士的土豆倪&#xff0c;24届校招生Java选手&#xff0c;很高兴认识大家&#x1f4d5;系列专栏&#xff1a;Spring源码、JUC源码&#x1f525;如果感觉博主的文章还不错的话&#xff0c;请&#x1f44d;三连支持&…

234. 回文链表、Leetcode的Python实现

博客主页&#xff1a;&#x1f3c6;看看是李XX还是李歘歘 &#x1f3c6; &#x1f33a;每天分享一些包括但不限于计算机基础、算法等相关的知识点&#x1f33a; &#x1f497;点关注不迷路&#xff0c;总有一些&#x1f4d6;知识点&#x1f4d6;是你想要的&#x1f497; ⛽️今…

Zookeeper安装及配置

Zookeeper官网:Apache ZooKeeper 一般作为服务注册中心 无论在Windows下还是Linux下,Zookeeper的安装步骤是一样的,用的包也是同一个包 Window下安装及配置Zookeeper 下载后解压 linux安装 window及Linux安装及配置zookeeper_访问windos上的zookeeper-CSDN博客