时间轮算法[通俗易懂]

时间轮算法[通俗易懂]时间轮算法最近工作中使用了Xxl-Job框架来做分布式调度,内部采用了时间轮做整体调度,顺便学习并总结一下。概述绝对时间和相对时间定时任务一般有两种:1.约定一段时间后执行。2.约定某个时间点执行。​ 其实这两者是可以互相转换的,比如现在有一个定时任务是12点执行,当前时间是9点,那就可以认为这个任务是3小时后执行。同样,现在又有一个任务,是3小时后执行,那也可以认为这个任务12点执行。​ 假设我们现在有3个定时任务A、B、C,分别需要在3点、4点和9点执行,我们把

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

时间轮算法

最近工作中使用了Xxl-Job框架来做分布式调度,内部采用了时间轮做整体调度,顺便学习并总结一下。

绝对时间和相对时间

定时任务一般有两种:

1. 约定一段时间后执行。
2. 约定某个时间点执行。      

​ 其实这两者是可以互相转换的,比如现在有一个定时任务是12点执行,当前时间是9点,那就可以认为这个任务是3小时后执行。同样,现在又有一个任务,是3小时后执行,那也可以认为这个任务12点执行。

​ 假设我们现在有3个定时任务A、B、C,分别需要在3点、4点和9点执行,我们把它们都转换成绝对时间。
在这里插入图片描述
​ 只需要把任务放到它需要被执行的时刻,然后等到时针转到相应的位置时,取出该时刻放置的任务,执行就可以了。这就是时间轮算法的核心思想。

重复执行

​ 多数定时任务是需要重复执行,比如每天上午9点执行生成报表的任务。对于重复执行的任务,其实我们需要关心的只是下次执行时间,并不关心这个任务需要循环多少次,还是那每天上午9点的这个任务来说。

  1. 比如现在是下午4点钟,我把这个任务加入到时间轮,并设定当时针转到明天上午九点(该任务下次执行的时间)时执行。
  2. 时间来到了第二天上午九点,时间轮也转到了9点钟的位置,发现该位置有一个生成报表的任务,拿出来执行。
  3. 同时时间轮发现这是一个循环执行的任务,于是把该任务重新放回到9点钟的位置。
  4. 重复步骤2和步骤3。

​ 如果哪一天这个任务不需要再执行了,那么直接通知时间轮,找到这个任务的位置删除掉就可以了。由上面的过程我们可以看到,时间轮至少需要提供4个功能:

  1. 加入任务
  2. 执行任务
  3. 删除任务
  4. 沿着时间刻度前进

时间轮的数据结构

​ 时钟可以使用数组来表示,那么时钟的每一个刻度就是一个槽,槽用来存在该刻度需要被执行的定时任务。正常业务中,同一时刻中是会存在多个定时任务的,所以每个槽中放一个链表或者队列就可以了,执行的时候遍历一遍即可。
在这里插入图片描述

时间刻度不够用

增加时间轮的刻度

​ 现在有我有2个定时任务,一个任务每周一上午9点执行,另一个任务每周三上午9点执行。最简单的办法就是增大时间轮的长度,可以从12个加到168 (一天24小时,一周就是168小时),那么下周一上午九点就是时间轮的第9个刻度,这周三上午九点就是时间轮的第57个刻度。
在这里插入图片描述

这样做的缺点:

  1. 时间刻度太多会导致时间轮走到的多数刻度没有任务执行,比如一个月就2个任务,我得移动720次,其中718次是无用功。

2. 时间刻度太多会导致存储空间变大,利用率变低,比如一个月就2个任务,我得需要大小是720的数组,如果我的执行时间的粒度精确到秒,那就更恐怖了。

任务增加round属性

​ 现在时间轮的刻度还沿用24,但是槽中的每个任务增加一个round属性,代表时钟转过第几圈之后再次转到这个槽的时候执行。

在这里插入图片描述

​ 上图代表任务三在指针下一圈移动时执行,整体流程就是时间轮没移动一个刻度的时候都要遍历槽中所有任务,对每个任务的round属性减1,并取出round为0的任务调度,这样可以解决增加时间轮带来的空间浪费。但是这样带来的问题时,每次移动刻度的耗时会增加,当时间刻度很小(秒级甚至毫秒级),任务列表有很长,这种方案是不能接受的。

分层时间轮

分层时间轮是这样一种思想:
  1. 针对时间复杂度的问题:不做遍历计算round,凡是任务列表中的都应该是应该被执行的,直接全部取出来执行。
  2. 针对空间复杂度的问题:分层,每个时间粒度对应一个时间轮,多个时间轮之间进行级联协作。

假设现在有3个定时任务:

1. 任务一每天上午9点执行
2. 任务二每周2上午9点执行
3. 任务三每月12号上午9点执行。

根据这三个任务的调度粒度,可以划分为3个时间轮,月轮、周轮和天轮,初始添加任务时,任务一被添加到天轮上,任务二被添加到周轮,任务三被添加到月轮上。三个时间轮按各自的刻度运转,当周轮移动到刻度2时,取出任务二丢到天轮上,当天轮移动到刻度9时执行。同样任务三在移动到刻度12时,取出任务三丢给月轮。以此类推。
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/187066.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 夜深人静写算法(十五)- 完全背包「建议收藏」

    夜深人静写算法(十五)- 完全背包「建议收藏」完全背包问题

  • 微信小程序不在以下 request 合法域名列表中「建议收藏」

    微信小程序不在以下 request 合法域名列表中「建议收藏」首先检查开发工具 设置 详情===》本地设置;取消以下勾选框查看异常问题;不在以下 request 合法域名列表中,请参考文查看是否配置域名信息,如果没有配置则去小程序后台设置即可多个已 “;” 分割即可。配置完毕后,在开发者工具刷新查看,然后 记得 【重启开发者工具】就解决啦~…

  • android 自定义控件的两种做法[通俗易懂]

    android 自定义控件的两种做法

  • 大数据时代来临,数据应用随处可见吗_随着大数据时代的来临

    大数据时代来临,数据应用随处可见吗_随着大数据时代的来临序:大数据之所以可能成为一个时代,在很多程度上是因为这是一个可以由社会各界广泛参与,八面出击,处处结果的社会运动,而不仅仅是少数专家学者的研究对象。数据产生于各行各业,这场变革也必将影响到各行各业,因此,机遇也蕴含于各行各业。致力于IT创业的人们紧紧盯着这个市场,洞察着每一个机遇。数据对于科学进步有推动的作用,而海量数据对数据的分析既带来了机遇,也构成了新的挑战。随着大数据的迅速发展,许多企业开始…

  • 思维导图——快速掌握子网划分(实例详解)

    思维导图——快速掌握子网划分(实例详解)目录一、子网划分的作用二、IP地址的组成三、IPV4地址四、IP地址的分类五、如何计算网络号六、地址规划6.1子网数概念6.2求地址网络可分为几段6.3CIDR:把若干网络合并成一个网段6.4例题实战七、思维导图及总结一、子网划分的作用作用一:计算网络号,通过网络号选择正确的网络设备连接终端设备1.清楚IP地址四段点分十进制数和子网掩码,对应的网络号是什么2.交换机是用来连接相同网段的设备,路由器是用来连接不同网段的设备。网络号一…

  • openwrt旁路由 ipv6上网配置[通俗易懂]

    openwrt旁路由 ipv6上网配置[通俗易懂]openwrt旁路由ipv6上网配置路由器:小米AX3600旁路由:openwrt配置路由端配置上网方式选择:路由器拨号选Native,光猫拨号选NAT6,校园网一般选NAT6打开成功后,上网信息会显示ipv6信息软路由配置DHCP/DNS配置:网络-接口配置:测试IPv6测试…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号