定时任务之时间轮算法
初识时间轮
我们先来考虑一个简单的情况,目前有三个任务A、B、C,分别需要在3点钟,4点钟和9点钟执行,可以把时间想象成一个钟表。

如上图中所示,我只需要把任务放到它需要被执行的时刻,然后等着时针转到这个时刻时,取出该时刻放置的任务,执行就可以了。 这就是时间轮算法最核心的思想了。 时针怎么转呢? while-true-sleep ,也可以使用空的阻塞队列加上超时时间进行睡眠。
在大多数情况中同一时刻可能需要执行多个任务,比如每天上午九点除了生成报表之外,还需要执行发送邮件的任务,需要执行创建文件的任务等等。
时间轮的数据结构。首先,时间轮的刻度可以用数组或者链表表示,每个刻度就是一个槽,槽用来存放该刻度需要执行的任务,如果有多个任务需要执行呢?每个槽里面放一个链表就可以了,就像下面图中这样:

同一时刻存在多个任务时,只要把该刻度对应的链表全部遍历一遍,执行(扔到线程池中异步执行)其中的任务即可。
简单时间轮的实现
由一个 hash table和链表实现,HashTable 的 key 值为时间单位,value 为链表的 root 节点。
时间刻度不够用怎么办?
上述时间轮表示一天的时间,但如果任务不只限定在一天之内呢?比如我有个任务,需要每周一上午1点执行,我还有另一个任务,需要每月的第十二天的上午四点执行。一种很容易想到的解决办法是:
1.增大时间轮的刻度
一天24个小时,一周168个小时,一月720个小时,为了解决上面的问题,我可以把时间轮的刻度(槽)从12个增加到168个,所以每周一上午1点就是时间轮的第1个刻度,每周五上午4点就是时间轮的第100个刻度,示意图如下:

仔细思考一下,会发现这种方式存在几个缺陷:
1.时间刻度太多会导致时间轮走到的多数刻度没有任务执行,比如一个月就2个任务,按照一个月30天算,需要移动720次,其中718次是无用的。
2.时间刻度太多会导致存储空间变大,利用率变低。
这种方式直接导致空间复杂度变大。
2.增加圈数
为每个任务增加一个圈数round标识,每次遍历到这个任务时,圈数减1,当圈数为0时,执行该任务,示意图如下:

但这种,每次时间轮转动,都需要对整个任务链表进行计算,增加了时间复杂度。最完美的实现就是转到对应刻度时,执行该刻度下所有的任务。
分层时间轮
分层时间轮是这样一种思想:每个时间粒度对应一个时间轮,多个时间轮之间进行级联协作。基于这个思想,我们可以设置三个时间轮:月轮、周轮、天轮。
比如有一个任务三每个月12号上午九点。
月轮的刻度为30天,周轮的刻度为7天,天轮为24小时。
这个任务需要月轮的时间刻度转动到12号这一天,然后才需要关注其更细一级的时间单位:上午9点。

初始添加任务时,任务一每周二上午九点,任务二每周四上午九点,任务三每个月12号上午九点。为任务一添加到天轮上,任务二添加到周轮上,任务三添加到月轮上。三个时间轮以各自的时间刻度不停流转。
当周轮移动到刻度2(星期四)时,取出这个刻度下的任务,丢到天轮上,天轮接管该任务,到9点执行。
同理,当月轮移动到刻度12(12号)时,取出这个刻度下的任务,丢到天轮上,天轮接管该任务,到9点执行。
这样就可以做到既不浪费空间,有不浪费时间。
整体的示意图如下所示:
定时器一览
1.无序定时器列表
2.有序定时器列表
3. 定时器树
4. 简单的计时轮
5. 带有有序定时器列表的哈希轮
6. 带有无序定时器列表的哈希轮
7.分层时间轮
时间轮的应用
时间轮的思想应用范围非常广泛,各种操作系统的定时任务调度,Redisson、Crontab、Netty、Kafka、Caffeine等组件的时间任务调度均采用时间轮的思想。
在不同的场景下,选择合适的定时器。
参考资料
hashed-and-hierarchical-timeing-wheels论文:Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility | the morning paper
时间轮简介:时间轮timewheel算法_天涯泪小武的博客-CSDN博客
netty时间轮分析:Netty时间轮 - 腾讯云开发者社区-腾讯云
相关文章:
定时任务之时间轮算法
初识时间轮 我们先来考虑一个简单的情况,目前有三个任务A、B、C,分别需要在3点钟,4点钟和9点钟执行,可以把时间想象成一个钟表。 如上图中所示,我只需要把任务放到它需要被执行的时刻,然后等着时针转到这个…...
实验4 Matplotlib数据可视化
1. 实验目的 ①掌握Matplotlib绘图基础; ②运用Matplotlib,实现数据集的可视化; ③运用Pandas访问csv数据集。 2. 实验内容 ①绘制散点图、直方图和折线图,对数据进行可视化; ②下载波士顿数房价据集,并…...
【软件工程】为什么要选择软件工程专业?
个人主页:【😊个人主页】 文章目录 前言软件工程💻💻💻就业岗位👨💻👨💻👨💻就业前景🛩️🛩️🛩️工作环…...
5类“计算机”专业很吃香,人才缺口巨大,就业前景良好
说到目前最热门的专业,计算机绝对占有一席之地,是公认的发展前景好、人才缺口大的专业。有人称该专业人数如此众多,势必会导致人才饱和,但是从当前社会互联网发展的趋势来看,计算机专业在很长一段时间都是发展很好的专…...
数仓选型对比
1、数仓选型对比如下(先列举表格,后续逐个介绍) 数仓应用目标产品特点适用于 适用数据类型数据处理速度性能拓展 实施难度运维难度性能优化成本传统数仓(SQLServer、Oracle等关系型数据库)面向主题设计的,为 分析数据而设计基于Oracle、 SQLServer、MyS…...
二叉树的遍历(前序、中序、后序)Java详解与代码实现
递归遍历 前序,中序,后序 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, Tree…...
如何找出消耗CPU最多的线程?
如何找出消耗CPU最多的线程? 1.使用 top -c 找出所有当前进程的运行列表 top -c 2.按P(Shiftp)对所有进程按CPU使用率进行排序,找出消耗最高的线程PID 显示Java进程 PID 为 136 的java进程消耗最 3.使用 top -Hp PID,查出里面消…...
【论文笔记】Attention Augmented Convolutional Networks(ICCV 2019 入选文章)
目录 一、摘要 二、介绍 三、相关工作 卷积网络Convolutional networks: 网络中注意力机制Attention mechanisms in networks: 四、方法 1. 图像的自注意力Self-attention over images: 二维位置嵌入Two-dimensional Positional Enco…...
虚幻图文笔记:Character Creator 4角色通过AutoSetup For Unreal Engine插件导入UE5.1的过程笔记
在UE5端安装AutoSetup For Unreal Engine插件 AutoSetup For Unreal Engine是Reallusion官方提供的免费插件,官方下载地址,下载到的是一个可执行文件,点击安装,记住安装的位置⬇ 看装完毕后会打开一个文件夹,这里就是对…...
JAVAWeb04-DOM
1. DOM 1.1 概述 1.1.1 官方文档 地址: https://www.w3school.com.cn/js/js_htmldom.asp 1.1.2 DOM 介绍 DOM 全称是 Document Object Model 文档对象模型就是把文档中的标签,属性,文本,转换成为对象来管理 1.2 HTML DOM(文档…...
C++内存管理基础知识
C 内存管理 C内存管理是一个重要的主题,因为它涉及到程序运行时资源的分配和释放。它可以分为三种类型:静态内存、栈内存和堆内存。 静态内存 静态内存(Static Memory):静态内存用于存储全局变量、静态变量和常量。这…...
命令执行漏洞概述
命令执行漏洞概述 命令执行定义命令执行条件命令执行成因命令执行漏洞带来的危害远程命令执行漏洞相关函数assert()preg_replace()call_user_func() a ( a( a(b)可变函数远程命令执行漏洞的利用系统命令执行漏洞相关函数system()exec()shell_exec()passthru(&#x…...
【初试复试第一】脱产在家二战上岸——上交819考研经验
笔者来自通信考研小马哥23上交819全程班学员 先介绍一下自己,我今年初试426并列第一,加上复试之后总分600,电子系第一。 我本科上交,本科期间虽然没有挂科但是成绩排名处于中下游水平。参加过全国电子设计大赛,虽然拿…...
PTA:C课程设计(7)
山东大学(威海)2022级大一下C习题集(7) 函数题7-6-1 递增的整数序列链表的插入7-6-2 查找学生链表7-6-3 统计专业人数7-6-4 建立学生信息链表 编程题7-7-1 查找书籍7-7-2 找出总分最高的学生 函数题 7-6-1 递增的整数序列链表的插…...
POSTGRESQL LINUX 与 PG有关的内存参释义
开头还是介绍一下群,如果感兴趣polardb ,mongodb ,mysql ,postgresql ,redis 等有问题,有需求都可以加群群内有各大数据库行业大咖,CTO,可以解决你的问题。加群请联系 liuaustin3 ,在新加的朋友会分到2群(共…...
Docker的常见命令
前言:使用Docker得学会的几个常见命令 常见命令前置学习: docker --help这个命令必须得会因为,很多命令是记不住的,得使用他们的官方help下面是一些实例 docker load --help常见命令集合: 一: docker images #查看全部镜像 docker rmi #删除某个镜像(例如:docker rmi redis…...
详细介绍性能测试的方法(含文档)
性能测试是软件测试中的一个重要环节,其目的是评估系统在不同负荷下的性能表现,包括响应时间、吞吐量、并发数等指标。通常可以通过以下几种方法进行性能测试: 1、负载测试 负载测试是模拟多用户同时访问系统,测试系统在高并发、…...
深入剖析 Qt QHash :原理、应用与技巧
目录标题 引言QHash 基础用法基础用法示例基础用法综合示例 QHash 的高级用法迭代器:遍历 QHash 中的元素(Iterators: Traversing Elements in QHash )QHash和其他容器的对比QHash 和 std::unordered\_map QHash的底层原理和内存管理QHash 的…...
技术分享 | MySQL级联复制下进行大表的字段扩容
作者:雷文霆 爱可生华东交付服务部 DBA 成员,主要负责Mysql故障处理及相关技术支持。爱好看书,电影。座右铭,每一个不曾起舞的日子,都是对生命的辜负。 本文来源:原创投稿 *爱可生开源社区出品,…...
工业互联网业务知识
文章目录 背景第四次工业革命带动制造业产业升级主要工业大国不同路径 架构ISA95体系架构变革趋势基础通用架构数据采集平台 工业互联网应用软件工业互联网全要素连接产品视角:产销服务企业的业务流程企业数字化改造:车间级全要素连接 工业互联网的产品体…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
