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