TimeWheel一种实现方式 作者: nbboy 时间: 2022-02-23 分类: 默认分类,软件架构,Golang > 时间轮是一种应用于定时器的有效数据结构,只需要一个系统时钟定时器就搞定非常多的定时策略,常常应用于**延时任务**等场景 现在实现上主要有两种时间轮,Hash时间轮和分层时间轮,Hash时间轮又有可以实现为排序和非排序的,但是主要原理基本一致。 ### Hash时间轮 hash时间轮可以用hash加上双向链表来实现,当然双向链表可以替换成其他类似的数据结构,比如数组,有序列表等等。其大致结构如下图所示: 每个系统时钟周期内都走动一个hash槽,在这个槽内task都是以双链表形式构建,并且每个task中有代表第几轮的circle和代表在第几个hash槽中的slot。如果circle是0,那就意味着当前可以调度,反之就该把circle减去1。具体看代码可能比较清楚。 ```go for e := slot.Front(); e != nil; e = e.Next() { tasker := e.Value.(*task) if tasker.circle > 0 { tasker.circle -= 1 continue } else { tw.removeTime(&removingTasker{key: tasker.key}) go func() { defer func() { if err := recover(); err != nil { log.Printf("tasker error: %v\n", err) } }() tasker.fn() }() } } ``` ### 分层时间轮 分层时间轮是hash时间轮的一种优化,在原来论文里写得也比较清楚,假如说定时时间跨度很大,则采用hash时间轮就不是很理想。分层时间轮基于相当于十进制中的进位理念一样,或者类似现实中的时钟工作机制。结构如下图所示。 hierarchical-timing-wheel.pn ###### 设置定时时间 先计算出,给定的定时时间需要用几个轮子来表示,当前轮子不能表示就再加入一个。 ###### 周期调度 每个系统时钟周期都是调度低位的轮子,走动一个时间槽,当走完当前轮的所有时间槽,则在比其高一级的轮子中走动一个时间槽。走动的时间槽里包含设定的定时时间,则把该时间移动到下一级轮子中,其位置很容易计算,和最开始设定定时时间的计算方式是一样的。当然,如果当前级别的轮子是最后一级,则需要去调度了。 ### 总结 实现上,可以采用很多的实现方式,可以参考kafka,libevent,nginx等等源码都有实现,看具体需求做trade-off,我实现了简单的hash时间轮体验了一把,它存放在:https://github.com/x-debug/tw 标签: timewheel, 时间轮, 延时任务
评论已关闭