问题

面试官：定时任务是怎么执行的？

我：啊，这么简单的问题你还问我，当然是到了时间执行就可以了呀。

面试官：那怎么判断是到时间了呀？

我: 啊这这这。。。。。。。

定时任务

定时任务这在开发当中看起来就是一件司空见惯的事情，在我经历的项目当中有两种实现方式

使用spring提供的注解 @Scheduled (cron表达式)
使用quartz框架

但是我竟然从来没有想过定时任务到底是怎么触发的，只是觉得到了时间就要执行了理所当然。

使用场景

思考一个技术的时候，我们首先就要思考他的使用场景是什么？

定时任务，顾名思义就是到了指定的时间执行一个任务。
指定时间，肯定是当前时间之后，比如我要每隔1分钟执行一下这个任务，那我要怎么去监测到这个一分钟到了那？直接一个线程sleep 1分钟之后再执行任务

sleep 底层实现：

挂起进程（或线程）并修改其运行状态

用sleep()提供的参数来设置一个定时器。

当时间结束，定时器会触发，内核收到中断后修改进程（或线程）的运行状态。例如线程会被标志为就绪而进入就绪队列等待调度

可变定时器(variable timer)一般在硬件层面是通过一个固定的时钟和计数器来实现的，每经过一个时钟周期将计数器递减，当计数器的值为0时产生中断。内核注册一个定时器后可以在一段时间后收到中断,所以我们不需要去关心硬件是如何实现的，只要知道有这么一个东西即可

那如果是多个任务设置不同的时间执行，就不能采用sleep的这种粗暴的方式了，由于我们肯定是要对定时任务做统一管理的，所以我们需要将这些任务放在一起，由于任务的执行时间是不一致的，所以最好是按照执行时间排序，不用每一次都去遍历所有的任务，符合这样的模型其实就是比如队列，最小堆等

实现方式

最小堆

Timer

jdk提供的定时器timer就是对上面思想的一个实现

思想：每当有新任务加入的时候，会把需要即将要执行的任务排到前面，同时会有一个线程不断的轮询判断，如果当前某个任务已经到达执行时间点，就会立即执行

缺点：

串行阻塞：调度线程只有一个，长任务会阻塞短任务的执行，例如，A任务跑了一分钟，B任务至少需要等1分钟才能跑
容错能力差：没有异常处理能力，一旦一个任务执行故障，后续任务都无法执行

ScheduledThreadPoolExecutor

鉴于 Timer 的上述缺陷，从 Java 5 开始，推出了基于线程池设计的 ScheduledThreadPoolExecutor 。

其设计思想是，每一个被调度的任务都会由线程池来管理执行，因此任务是并发执行的，相互之间不会受到干扰。需要注意的是，只有当任务的执行时间到来时，ScheduledThreadPoolExecutor 才会真正启动一个线程，其余时间 ScheduledThreadPoolExecutor 都是在轮询任务的状态。

ScheduledExecutorService 相比 Timer 定时器，完美的解决上面说到的 Timer 存在的两个缺点！

在单体应用里面，使用 ScheduledExecutorService 可以解决大部分需要使用定时任务的业务需求！

但是这是否意味着它是最佳的解决方案呢？

我们发现线程池中 ScheduledExecutorService 的排序容器跟 Timer 一样，都是采用最小堆的存储结构，新任务加入排序效率是O(log(n))，执行取任务是O(1)。

这里的写入排序效率其实是有空间可提升的，有可能优化到O(1)的时间复杂度，也就是我们下面要介绍的时间轮实现！

队列

时间轮

所谓时间轮（RingBuffer）实现，从数据结构上看，简单的说就是循环队列，从名称上看可能感觉很抽象。

它其实就是一个环形的数组，如图所示，假设我们创建了一个长度为 8 的时间轮。

插入、取值流程：

当我们需要新建一个 1s 延时任务的时候，则只需要将它放到下标为 1 的那个槽中，2、3、…、7也同样如此。
而如果是新建一个 10s 的延时任务，10对8取余就是2，,那么就需要将它放到下标为 2 的槽中，但同时需要记录它所对应的圈数，也就是 1 圈，不然就和 2 秒的延时消息重复了
当创建一个 21s 的延时任务时，它所在的位置就在下标为 5 的槽中，同样的需要为他加上圈数为 2，依次类推…
因此，总结起来有两个核心的变量：

数组下标：表示某个任务延迟时间，从数据操作上对执行时间点进行取余
圈数：表示需要循环圈数

其实这个方式有点像java当中的经典的hashmap，先取hash值，然后任务放在队列当中，按照执行时间来进行排序，优先执行的放在队头

缺点

当一个任务要执行的时间距离当前时间比较远的时候，如果按照8s这个是时间轮来看，就会转很多圈，让cpu白白空转了那么多次，那么如果解决这个问题那？

加大槽的数量，原来是8，我们可以16 32 那么转的圈数就会明显下降
增加每个槽的时间范围，上面举例的这个8s的时间轮，每个槽的时间范围都是1s，我们可以改为2s，或者3s，或者1分钟等等。但是这种方式会降低时间精度，每个槽就是相当于这个时间轮的时间精度了。

所以进一步的优化就是层级时间轮

层级时间轮

层级时间轮，分多个时间轮，以上图为例，第1层，每格的时间跨度为1s，那么第1层总的时间跨度为8s，第2层的每格时间跨度就为8s，第2层总的时间跨度就为8 * 8 = 64s，第3层的每格时间跨度就为64s，第3层总的时间跨度就为8 * 64 = 512s，第1层转完一圈，触发第2层转动一格，第2层转一圈触发第3层转一格，这个思想跟时钟是一模一样的，时钟有秒针、分针、时针，秒针的刻度为60格，每格1s，分针的刻度也是60格，每格60s，时针的刻度为12，每格3600s。

添加任务

先看第1层的时间跨度够不够，够的话就落在第1层，不够的话再判断第2层，第2层还不够的话再判断第3层，这是一个层级递升的过程

触发任务

在检测是否需要任务触发的过程跟上面刚好反过来，是一个降级的过程，假设现在所有指针都在0刻度，现在添加一个800s延迟的任务，那它肯定落在第3层，转1圈后还剩余288秒(800 - 512 * 1 = 288)，这个时候圈数为0了，但是又还没到触发的时间，那就往第2层放，在第2层转4圈后还剩余32秒(288 - 64 * 4 = 32)，这时，也还没到触发时间，继续往第1层放，在第1层转4圈后(32 - 8 * 4 = 0)，剩余圈数为0了，剩余时间也为0了，此时到达触发时间，取出来执行即可

层级时间轮在kafka中有实现，时间轮就是计算机世界对现实世界中时钟的映射

流殃的博客

问题