时间轮算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了时间轮算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3127字，纯文字阅读大概需要5分钟。
内容图文
时间轮算法
最近工作中使用了Xxl-Job框架来做分布式调度，内部采用了时间轮做整体调度，顺便学习并总结一下。
绝对时间和相对时间
定时任务一般有两种：
1. 约定一段时间后执行。
2. 约定某个时间点执行。
? 其实这两者是可以互相转换的，比如现在有一个定时任务是12点执行，当前时间是9点，那就可以认为这个任务是3小时后执行。同样，现在又有一个任务，是3小时后执行，那也可以认为这个任务12点执行。
? 假设我们现在有3个定时任务A、B、C，分别需要在3点、4点和9点执行，我们把它们都转换成绝对时间。
? 只需要把任务放到它需要被执行的时刻，然后等到时针转到相应的位置时，取出该时刻放置的任务，执行就可以了。这就是时间轮算法的核心思想。
重复执行
? 多数定时任务是需要重复执行，比如每天上午9点执行生成报表的任务。对于重复执行的任务，其实我们需要关心的只是下次执行时间，并不关心这个任务需要循环多少次，还是那每天上午9点的这个任务来说。
- 比如现在是下午4点钟，我把这个任务加入到时间轮，并设定当时针转到明天上午九点(该任务下次执行的时间)时执行。
- 时间来到了第二天上午九点，时间轮也转到了9点钟的位置，发现该位置有一个生成报表的任务，拿出来执行。
- 同时时间轮发现这是一个循环执行的任务，于是把该任务重新放回到9点钟的位置。
- 重复步骤2和步骤3。
? 如果哪一天这个任务不需要再执行了，那么直接通知时间轮，找到这个任务的位置删除掉就可以了。由上面的过程我们可以看到，时间轮至少需要提供4个功能：
- 加入任务
- 执行任务
- 删除任务
- 沿着时间刻度前进
时间轮的数据结构
? 时钟可以使用数组来表示，那么时钟的每一个刻度就是一个槽，槽用来存在该刻度需要被执行的定时任务。正常业务中，同一时刻中是会存在多个定时任务的，所以每个槽中放一个链表或者队列就可以了，执行的时候遍历一遍即可。
时间刻度不够用
增加时间轮的刻度
? 现在有我有2个定时任务，一个任务每周一上午9点执行，另一个任务每周三上午9点执行。最简单的办法就是增大时间轮的长度，可以从12个加到168 (一天24小时，一周就是168小时)，那么下周一上午九点就是时间轮的第9个刻度，这周三上午九点就是时间轮的第57个刻度。
这样做的缺点:
- 时间刻度太多会导致时间轮走到的多数刻度没有任务执行，比如一个月就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时，取出任务三丢给月轮。以此类推。
内容总结
以上是互联网集市为您收集整理的时间轮算法全部内容，希望文章能够帮你解决时间轮算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。