中联网站建设,南昌网站排名推广,网站建设任务执行书,三河网站seo初识时间轮
我们先来考虑一个简单的情况#xff0c;目前有三个任务A、B、C#xff0c;分别需要在3点钟#xff0c;4点钟和9点钟执行#xff0c;可以把时间想象成一个钟表。 如上图中所示#xff0c;我只需要把任务放到它需要被执行的时刻#xff0c;然后等着时针转到这个…
初识时间轮
我们先来考虑一个简单的情况目前有三个任务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时间轮 - 腾讯云开发者社区-腾讯云
