定时器

本文次要介绍目前存在的定时工作解决解决方案。业务零碎中存在泛滥的工作须要定时或定期执行，并且针对不同的零碎架构也须要提供不同的解决方案。京东外部也提供了泛滥定时工作中间件来反对，总结以后各种定时工作原理，从定时工作根底原理、单机定时工作（单线程、多线程）、分布式定时工作介绍目前支流的定时工作的基本原理组成、优缺点等。心愿能帮忙读者深刻了解定时工作具体的算法和实现计划。 一、背景概述定时工作，顾名思义，就是指定工夫点进行执行相应的工作。业务场景中包含： 每天晚上12点，将当日的销售数据发送给各个VP；订单下单十分钟未付款将主动勾销订单；用户下单后发短信；定时的清理零碎中生效的数据；心跳检测、session、申请是否timeout。二、定时工作根底原理2.1 小顶堆算法每个节点是对应的定时工作，定时工作的执行程序通过利用堆化进行排序，循环判断每秒是否堆顶的工作是否应该执行，每次插入工作、删除工作须要从新堆化； 图1 利用小顶堆来获取须要最新执行的工作 为什么用优先队列（小顶堆）而不是有序的数组或者链表？ 因为优先队列只须要确保部分有序，它的插入、删除操作的复杂度都是O(log n)；而有序数组的插入和删除复杂度为O(n)；链表的插入复杂度为O(n)，删除复杂度为O(1)。总体而言优先队列性能最好。 2.2 工夫轮算法链表或者数组实现工夫轮： 图2 利用链表+数组实现工夫轮算法 round工夫轮： 工夫轮其实就是一种环型的数据结构，能够把它设想成一个时钟，分成了许多格子，每个格子代表肯定的工夫，在这个格子上用一个链表来保留要执行的超时工作，同时有一个指针一格一格的走，走到那个格子时就执行格子对应的提早工作。 图3 环形数据结构的round工夫轮 2.3 分层工夫轮就是将月、周、天分成不同的工夫轮层级，各自的工夫轮进行定义： 图4 按工夫维度分层的工夫轮 三、单机定时工作3.1 单线程任务调度3.1.1 有限循环创立thread，在while中始终执行，通过sleep来达到定时工作的成果。 3.1.2 JDK提供了TimerTimer位于java.util包下，其外部蕴含且仅蕴含一个后盾线程（TimeThread）对多个业务工作（TimeTask）进行定时定频率的调度。 图5 JDK中Timer反对的调度办法 每个Timer中蕴含一个TaskQueue对象，这个队列存储了所有将被调度的task， 该队列是一个依据task下一次运行工夫排序造成的最小优先队列，该最小优先队列的是一个二叉堆，所以能够在log(n)的工夫内实现减少task，删除task等操作，并且能够在常数工夫内取得下次运行工夫最小的task对象。 原理： TimerTask是按nextExecutionTime进行堆排序的。每次取堆中nextExecutionTime和以后零碎工夫进行比拟，如果以后工夫大于nextExecutionTime则执行，如果是单次工作，会将工作从最小堆，移除。否则，更新nextExecutionTime的值。 图6 TimerTask中依照工夫的堆排序 工作追赶个性： schedule在执行的时候，如果Date过了，也就是Date是小于当初工夫，那么会立刻执行一次，而后从这个执行工夫开始每隔间隔时间执行一次； scheduleAtFixedRate在执行的时候，如果Date过了。还会执行，而后才是每隔一段时间执行。 Timer问题： 工作执行工夫长影响其余工作：如果TimerTask抛出未查看的异样，Timer将会产生无奈意料的行为。Timer线程并不捕捉异样，所以 TimerTask抛出的未查看的异样会终止timer线程。此时，曾经被安顿但尚未执行的TimerTask永远不会再执行了，新的工作也不能被调度了。工作异样影响其余工作：Timer外面的工作如果执行工夫太长，会独占Timer对象，使得前面的工作无奈几时的执行 ，ScheduledExecutorService不会呈现Timer的问题(除非你只搞一个单线程池的任务区)。3.1.3 DelayQueue DelayQueue 是一个反对延时获取元素的无界阻塞队列，DelayQueue 其实就是在每次往优先级队列中增加元素，而后以元素的delay过期值作为排序的因素，以此来达到先过期的元素会拍在队首，每次从队列里取出来都是最先要过期的元素。 delayed是一个具备过期工夫的元素PriorityQueue是一个依据队列里元素某些属性排列先后的程序队列（外围还是基于小顶堆）队列中的元素必须实现 Delayed 接口，并重写 getDelay(TimeUnit) 和 compareTo(Delayed) 办法。 CompareTo(Delayed o)：Delayed接口继承了Comparable接口，因而有了这个办法。getDelay(TimeUnit unit):这个办法返回到激活日期的剩余时间，工夫单位由单位参数指定。队列入队出队办法： offer()：入队的逻辑综合了PriorityBlockingQueue的均衡二叉堆冒泡插入以及DelayQueue的生产线程唤醒与leader领导权剥夺take()：出队的逻辑一样综合了PriorityBlockingQueue的均衡二叉堆向下降级以及DelayQueue的Leader-Follower线程期待唤醒模式在ScheduledExecutorService中推出了DelayedWorkQueue，DelayQueue队列元素必须是实现了Delayed接口的实例，而DelayedWorkQueue寄存的是线程运行时代码RunnableScheduledFuture，该延时队列灵便的退出定时工作特有的办法调用。 图7 定时工作中的延时队列类图 leader follower模式： 所有线程会有三种身份中的一种：leader和follower，以及一个工作中的状态：proccesser。它的根本准则就是，永远最多只有一个leader。而所有follower都在期待成为leader。线程池启动时会主动产生一个Leader负责期待网络IO事件，当有一个事件产生时，Leader线程首先告诉一个Follower线程将其提拔为新的Leader，而后本人就去干活了，去解决这个网络事件，处理完毕后退出Follower线程期待队列，期待下次成为Leader。这种办法能够加强CPU高速缓存相似性，及打消动态内存调配和线程间的数据交换。 3.1.4 Netty 实现提早工作-HashedWheel能够应用 Netty 提供的工具类 HashedWheelTimer 来实现提早工作。 ...