问题
面试官： 定时任务是怎么执行的？
我： 啊 ，这么简单的问题你还问我，当然是到了时间执行就可以了呀。
面试官： 那怎么判断是到时间了呀？
我: 啊 这这这 。。。。。。。
定时任务
定时任务这在开发当中看起来就是一件司空见惯的事情，在我经历的项目当中有两种实现方式
- 使用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中有实现，时间轮就是计算机世界对现实世界中时钟的映射
评论区