主要有3种方案：数据库扫表；小顶堆；时间轮。
数据库扫表
延迟比较大
小顶堆
首先维持一个小顶堆，即最快需要执行的任务排在优先队列的第一个，根据堆的特性我们知道插入和删除的时间复杂度都是 O(logn)，然后TimerThread不断地拿排在第一个任务的执行时间和当前时间做对比，如果时间到了先看看这个任务是不是周期性执行的任务？如果是则修改当前任务时间为下次执行的时间，如果不是周期性任务则将任务从优先队列中移除，最后执行任务。如果时间还未到则调用 wait() 等待。
增加模板和删除模板的时间复杂度是O(logN)。个人觉得在时间复杂度上存在较大的性能风险，插入删除时间复杂度是O(logn)，如果面对大数量级的任务频繁的插入、删除，这种实现方式性能问题会比较严重。
时间轮
时间轮用 环形 数组实现，数组的每个元素可以称为槽，槽的内部用双向链表存着待执行的任务，添加和删除的链表操作时间复杂度都是 O(1)，槽位本身也指代时间精度，比如一秒扫一个槽，那么这个时间轮的最高精度就是 1 秒。也就是说延迟 1.2 秒的任务和 1.5 秒的任务会被加入到同一个槽中，然后在 1 秒的时候遍历这个槽中的链表执行任务。
针对槽不够的情况，有两种方式：
一种是通过增加轮次的概念；另一种是通过多层次的时间轮。
多层次时间轮还会有降级的操作，假设一个任务延迟500秒执行，那么刚开始加进来肯定是放在第三层的，当时间过了 436 秒后，此时还需要 64 秒就会触发任务的执行，而此时相对而言它就是个延迟64秒后的任务，因此它会被降低放在第二层中，第一层还放不下它。再过个 56 秒，相对而言它就是个延迟8秒后执行的任务，因此它会再被降级放在第一层中，等待执行。
降级是为了保证时间精度一致性,Kafka内部用的就是多层次的时间轮算法。
不足之处：
时间轮的推进是根据时间精度TickDuration来固定推进的，如果槽位中无任务，也需要移动指针，会造成无效的时间轮推进，比如TickDuration为1秒，此时就一个延迟500秒的任务，那就是有499次无用的推进。
任务的执行都是同一个工作线程处理的，并且工作线程的除了处理执行到时的任务还做了其他操作，因此任务不一定会被精准的执行，而且任务的执行如果不是新起一个线程执行，那么耗时的任务会阻塞下个任务的执行。
优势就是时间精度可控，并且增删任务的时间复杂度都是O(1)
kafka对于时间轮最核心的实现部分，包含时间轮的数据结构、添加任务、时间溢出(添加上一级时间轮)、时间轮推进四个核心部分。大的逻辑是添加任务-》是否时间溢出？-》溢出时添加上一级时间轮，并调用上一级时间轮的添加任务方法 -》未溢出，直接添加到槽位 -》递归处理。所以时间轮的数据结构、时间溢出都通过添加任务的逻辑串联了起来。而时间轮推进方法主要由工作线程SystemTimer调用。
参考：https://blog.csdn.net/weixin_42522400/article/details/112783846
网友评论