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, 时间轮, 延时任务
评论已关闭