层级时间轮系统 / Hierarchical Time Wheel System
笔者平时的开发经常与定时任务打交道，不管是重复执行定时任务，还是一次性定时任务。由于系统存在数量级极大的定时任务，简单得通过timer来完成定时任务的需求显然是不合理的，笔者平时的项目开发会对RusselLuo的timingwheel库进行二次封装使用。不满足只是使用，正好笔者最近闲时较多，就抽空看了看timingwheel的源码，写篇博客记录我的学习和发现。
定时任务系统的发展历程
想到定时任务，绝大部分人可能会想到timer，就是在指定时间点系统会发送一个信号，通知应用程序，应用程序可以在收到该信号后执行相应的回调。假设你的系统以定时任务为驱动，比如游戏服务器或者时间敏感系统，产生几百万个定时任务，那对每个任务都使用一个timer来追踪是不可能的，cpu吃不消，效率也极低。
那如果将所有的定时任务放在一个任务队列中，然后维护一个每个tick触发一次的timer，触发时遍历任务队列，执行到期的任务。思想可以，但是是1对N的模型，效率仍然低下。
再将思维发散，可不可以设计一个N对M的模型，存在N个时间段，每个时间段内存放多个定时任务。这里其实就引出时间轮的概念，我们设置一个环形队列，队列里的slot表示一个时间戳t1，t1 + tick 就是下一个slot的时间戳t2。再维护个指针，指针指向的slot表示当前被调度的slot，slot内的task需要被执行。tick时间后，指针再向前移动一个slot，指向下一个slot。当指到最后一个slot时，时间轮到期。
但是这种单层的时间轮能处理的时间周期非常有限，比如我们希望slot的总数是1000，tick的精度是1秒，那么时间轮的总周期就是1000秒，超过1000秒的定时任务就无法处理了。同时定时任务的触发时间精度也只能是tick的精度，无法做到更高精度的定时任务。
所以层级时间轮就产生了，也是本篇介绍的重点。多层时间轮的概念也非常清晰,将时间轮分为多个,每两个轮之间是进位的关系,例如最普遍的秒,分,时。下面的介绍参考kafka内的purgatory中的层级时间轮的实现。
- 每层的时间轮的slot数都固定为n，第一层时间轮的时间单位为u，那么第二层的时间单位（称之为第一层时间轮的溢出时间轮 Overflow Wheel）的时间单位就是 n * u, 以此类推。
- 第一层时间轮是固定创建的，其他层的时间轮是动态创建的，只有当到来的task的触发时间超过当前时间轮的最大时间戳时，才会创建。
- 原先插入到高层时间轮的task，会随着时间的流逝，被降级到低层的时间轮。也就是n层时间轮每轮完一轮，n+1层指针会向前移动一位，指向下一个slot，并且将slot内的task降级到n层时间轮的slot中。
到这里仍然存在问题，指针前进的驱动是通过系统timer，如果设置的tick时间过小，会导致大部分timer唤醒的回调没有执行具体的任务，导致cpu资源的浪费。这里的解决方案参考kafka的delayqueue。采用delayqueue来替代timer的定期触发。
在原来的设计中，每层时间轮的指针的前进都是通过一个timer来驱动，现在我们在每层时间轮中放置一个delayqueue，将包含定时任务队列的bucket放入到delayqueue，并将bucket的到期时间动态设置为队列中最小的任务的触发时间。这样delayqueue就会在到期时唤醒，执行对应的bucket中的所有任务，并将指针前进1步。