本文次要介绍目前存在的定时工作解决解决方案。业务零碎中存在泛滥的工作须要定时或定期执行,并且针对不同的零碎架构也须要提供不同的解决方案。京东外部也提供了泛滥定时工作中间件来反对,总结以后各种定时工作原理,从定时工作根底原理、单机定时工作(单线程、多线程)、分布式定时工作介绍目前支流的定时工作的基本原理组成、优缺点等。心愿能帮忙读者深刻了解定时工作具体的算法和实现计划。
一、背景概述
定时工作,顾名思义,就是指定工夫点进行执行相应的工作。业务场景中包含:
- 每天晚上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提供了Timer
Timer位于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 来实现提早工作。
该工具类采纳的是工夫轮的原理来实现的,HashedWheelTimer是一个基于hash的环形数组。
图8 HashedWheelTimer实现的工夫轮
1. 长处: 能高效的解决少量定时工作,实用于对时效性不高的,可疾速执行的,大量这样的“小”工作,可能做到高性能,低消耗。把大批量的调度工作全副都绑定到同一个的调度器下面,应用这一个调度器来进行所有工作的治理(manager),触发(trigger)以及运行(runnable)。可能高效的治理各种延时工作,周期工作,告诉工作等等。
2. 毛病: 对内存要求较高,占用较高的内存。工夫精度要求不高:工夫轮调度器的工夫精度可能不是很高,对于精度要求特地高的调度工作可能不太适宜。因为工夫轮算法的精度取决于,时间段“指针”单元的最小粒度大小,比方工夫轮的格子是一秒跳一次,那么调度精度小于一秒的工作就无奈被工夫轮所调度。
3.1.5 MQ 实现提早工作
- 订单在十分钟之内未领取则主动勾销。
- 新创建的店铺,如果在十天内都没有上传过商品,则主动发送音讯揭示。
- 账单在一周内未领取,则主动结算。
- 用户注册胜利后,如果三天内没有登陆则进行短信揭示。
- 用户发动退款,如果三天内没有失去解决则告诉相干经营人员。
- 预约会议后,须要在预约的工夫点前十分钟告诉各个与会人员加入会议。
以上这些场景都有一个特点,须要在某个事件产生之后或者之前的指定工夫点实现某一项工作。
RabbitMQ 实现提早队列的形式有两种:
- 通过音讯过期后进入死信交换器,再由交换器转发到提早生产队列,实现提早性能;
<!---->
- 应用 rabbitmq-delayed-message-exchange 插件实现提早性能。
同样咱们也能够利用京东自研jmq的延时生产来做到以上的场景。
3.2 多线程定时工作
上述计划都是基于单线程的任务调度,如何引入多线程进步延时工作的并发解决能力?
3.2.1 ScheduledExecutorService
JDK1.5之后 推出了线程池(ScheduledExecutorService),现阶段定时工作与 JUC 包中的周期性线程池密不可分。JUC 包中的 Executor 架构带来了线程的创立与执行的拆散。Executor 的继承者 ExecutorService 上面衍生出了两个重要的实现类,他们别离是:
- ThreadPoolExecutor 线程池
- ScheduledThreadPoolExecutor 反对周期性工作的线程池
图9 ScheduledExecutorService实现类图
通过 ThreadPoolExecutor 能够实现各式各样的自定义线程池,而 ScheduledThreadPoolExecutor 类则在自定义线程池的根底上减少了周期性执行工作的性能。
- 最大线程数为Integer.MAX\_VALUE;表明线程池内线程数不受限制:即这是因为提早队列内用数组寄存工作,数组初始长度为16,但数组长度会随着工作数的减少而动静扩容,直到数组长度为Integer.MAX\_VALUE;既然队列能寄存Integer.MAX\_VALUE个工作,又因为工作是提早工作,因而保障工作不被摈弃,最多须要Integer.MAX\_VALUE个线程。
- 闲暇线程的等待时间都为0纳秒,表明池内不存在闲暇线程,除了外围线程:采纳leader-follwer,这里期待的线程都为闲暇线程,为了防止过多的线程浪费资源,所以ScheduledThreadPool线程池内更多的存活的是外围线程。
- 工作期待队列为DelayedWorkQueue。
图10 ScheduledThreadPoolExecutor中的延时队列DelayedWorkQueue
总结: ScheduledThreadPoolExecutor中定义外部类ScheduledFutureTask、DelayedWorkQueue;ScheduledFutureTask记录工作定时信息,DelayedWorkQueue来排序工作定时执行。ScheduledExecutorService自定义了阻塞队列DelayedWorkQueue给线程池应用,它能够依据ScheduledFutureTask的下次执行工夫来阻塞take办法,并且新进来的ScheduledFutureTask会依据这个工夫来进行排序,最小的最后面。
- DelayedWorkQueue:其中DelayedWorkQueue是定义的延时队列,能够看做是一个用延时工夫长短作为排序的优先级队列,来实现退出工作,DelayedWorkQueue原理见3.1.3;
- ScheduledFutureTask是用作实现Run办法,使得工作可能提早执行,甚至周期执行,并且记录每个工作进入延时队列的序列号sequenceNumber。工作类ScheduledFutureTask继承FutureTask并扩大了一些属性来记录工作下次执行工夫和每次执行距离。同时重写了run办法从新计算工作下次执行工夫,并把工作放到线程池队列中。
run()在解决工作时,会依据工作是否是周期工作走不通的流程:
- 非周期工作,则采纳futureTask类的run()办法,不存储优先队列;
- 周期工作,首先确定工作的延迟时间,而后把提早工作插入优先队列;
ScheduledFutureTask的reExecutePeriodic(outerTask)办法:把周期工作插入优先队列的过程。
3.2.2 实现SchedulingConfigurer接口
Spring Boot 提供了一个 SchedulingConfigurer 配置接口。咱们通过 ScheduleConfig 配置文件实现 ScheduleConfiguration 接口,并重写 configureTasks() 办法,向 ScheduledTaskRegistrar 注册一个 ThreadPoolTaskScheduler 工作线程对象即可。
图11 任务调度配置接口
3.2.3 Java任务调度框架Quartz
图12 Quartz任务调度框架
- Job:定义须要执行的工作,该类是一个接口,只定义了一个办法execute(JobExecutionContext context),在实现类的execute办法中编写所须要定时执行的Job(工作),Job运行时的信息保留在JobDataMap实例中。
- Trigger:负责设置调度策略。该类是一个接口,形容触发job执行的工夫触发规定。次要有SimpleTrigger和CronTrigger这两个子类。当且仅当需调度一次或者以固定工夫距离周期执行调度,SimpleTrigger 是最适宜的抉择;而CronTrigger则能够通过Cron表达式定义出各种简单工夫规定的调度计划:如在周一到周五的15:00 ~ 16:00 执行调度等。
- Scheduler:调度器就相当于一个容器,装载着工作和触发器。该类是一个接口。代表一个Quartz的独立运行容器。Trigger和JobDetail能够注册到Scheduler中,两者在Scheduler中领有各自的组及名称,组及名称是Scheduler查找定位容器中某一对象的根据。
- JobDetail:形容Job的实现类及其它相干的动态信息,如:Job名字、形容、关联监听器等信息。Quartz每次调度Job时,都从新创立一个Job实例,它承受一个Job实现类,以便运行时通过newInstance()的反射机制实例化Job。
- ThreadPool Scheduler应用一个线程池作为工作运行的基础设施,工作通过共享线程池中的线程进步运行效率。
- Listener:Quartz领有欠缺的事件和监听体系,大部分组件都领有事件,如:JobListener监听工作执行前事件、工作执行后事件;TriggerListener监听触发前事件,登程后事件;TriggerListener监听调度开始事件,敞开事件等等,能够注册响应的监听器解决感兴趣的事件。
针对Quartz 反复调度问题:
在通常的状况下,乐观锁能保障不产生反复调度,然而不免产生ABA问题。
配置文件加上:org.quartz.jobStore.acquireTriggersWithinLock=true
3.2.4 应用 Spring-Task
如果应用的是 Spring 或 Spring Boot 框架,Spring 作为一站式框架,为开发者提供了异步执行和任务调度的形象接口TaskExecutor 和TaskScheduler。
- Spring TaskExecutor:次要用来创立线程池用来治理异步定时工作开启的线程。(避免建设线程过多导致资源节约)。
- Spring TaskScheduler:创立定时工作
其中Spring自带的定时工作工具,spring task,能够将它比作一个轻量级的Quartz,而且应用起来很简略,除spring相干的包外不须要额定的包,而且反对注解和配置文件两种:
应用办法:
- 申明开启 Scheduled:通过注解 @EnableScheduling或者配置文件
- 工作办法增加@Scheduled注解
- 将工作的类交结 Spring 治理 (例如应用 @Component)
图13 定时工作配置文件和cron表达式
图14 @Scheduled注解拦挡类ScheduledAnnotationBeanPostProcessor的实现类图
类图简要介绍:
- 实现感知接口:EmbeddedValueResolverAware, BeanNameAware, BeanFactoryAware, ApplicationContextAware;
- 在spring启动实现单例bean注入,利用接口MergedBeanDefinitionPostProcessor实现扫描,利用BeanPostProcessor接口中的postProcessAfterInitialization扫描被@Scheduled注解示意的办法;
- 利用ScheduledTaskRegistrar作为注册核心,监听到所有bean注入实现之后,而后开始注册全副工作;
- 自定义任务调度器TaskScheduler,默认应用接口ScheduledExecutorService的实现类ScheduledThreadPoolExecutor定义单线程的线程池。
@Scheduler注解源码:
【Java】@Target({ElementType.METHOD, ElementType.ANNOTATION_TYPE})@Retention(RetentionPolicy.RUNTIME)@Documented@Repeatable(Schedules.class)public @interface Scheduled { //这个变量在ScheduledAnnotationBeanPostProcessor中会用作开启cron的判断条件 String cron() default ""; //用于设置类cron表达式 来形容人物的运行机会 String zone() default ""; //用于设置工作的上一次调用完结后到下一次调用开始前的工夫距离,单位:毫秒 long fixedDelay() default -1L; //参数 fixedDelay 的字符串参数模式,与fixedDelay只能二选一应用 String fixedDelayString() default ""; //用于设置工作的两次调用之间的固定的工夫距离,单位:毫秒 long fixedRate() default -1L; //参数 fixedRate 的字符串参数模式,与fixedRate只能二选一应用 String fixedRateString() default ""; //用于设置在首次执行fixedDelay或fixedRate工作之前要提早的毫秒数 long initialDelay() default -1L; //参数 initialDelay 的字符串参数模式,与initialDelay只能二选一应用 String initialDelayString() default "";}
我的项目启动时,在初始化 bean 后,带 @Scheduled 注解的办法会被拦挡,而后顺次:构建执行线程,解析参数,退出线程池。其中作为拦挡注解的类就是ScheduledAnnotationBeanPostProcessor。
ScheduledAnnotationBeanPostProcessor拦挡类中外围注解解决办法:
【Java】protected void processScheduled(Scheduled scheduled, Method method, Object bean) { try { //校验此注解的办法必领是无参的办法 //包装返回一个Runnable线程 Runnable runnable = this.createRunnable(bean, method); //定义一个校验注册工作最终是否执行的标识 boolean processedSchedule = false; //裝载工作,定义为4,次要波及的注解也就3个 String errorMessage = "Exactly one of the 'cron', 'fixedDelay(String)', or 'fixedRate(String)' attributes is required"; Set<ScheduledTask> tasks = new LinkedHashSet(4); //long和string二者取其一 long initialDelay = scheduled.initialDelay(); String initialDelayString = scheduled.initialDelayString(); if (StringUtils.hasText(initialDelayString)) { Assert.isTrue(initialDelay < 0L, "Specify 'initialDelay' or 'initialDelayString', not both"); if (this.embeddedValueResolver != null) { initialDelayString = this.embeddedValueResolver.resolveStringValue(initialDelayString); } if (StringUtils.hasLength(initialDelayString)) { try { initialDelay = parseDelayAsLong(initialDelayString); } catch (RuntimeException var24) { throw new IllegalArgumentException("Invalid initialDelayString value "" + initialDelayString + "" - cannot parse into long"); } } } // Check cron expression // 解析cron // cron也能够应用占位符。把它配置子啊配置文件里就成 String cron = scheduled.cron(); if (StringUtils.hasText(cron)) { String zone = scheduled.zone(); if (this.embeddedValueResolver != null) { cron = this.embeddedValueResolver.resolveStringValue(cron); zone = this.embeddedValueResolver.resolveStringValue(zone); } if (StringUtils.hasLength(cron)) { Assert.isTrue(initialDelay == -1L, "'initialDelay' not supported for cron triggers"); processedSchedule = true; if (!"-".equals(cron)) { TimeZone timeZone; if (StringUtils.hasText(zone)) { timeZone = StringUtils.parseTimeZoneString(zone); } else { timeZone = TimeZone.getDefault(); } //如果配置了cron,那么就能够看作是一个task了,就能够把工作注册进registrar外面 tasks.add(this.registrar.scheduleCronTask(new CronTask(runnable, new CronTrigger(cron, timeZone)))); } } } if (initialDelay < 0L) { initialDelay = 0L; } long fixedDelay = scheduled.fixedDelay(); ...... ...... ...... long fixedRate = scheduled.fixedRate(); ...... ...... ...... //校验注册工作最终是否胜利 Assert.isTrue(processedSchedule, errorMessage); //最初把这些工作都放在全局属性外面保存起来 //getScheduledTasks()办法是会把所有的工作都返回进来 synchronized(this.scheduledTasks) { Set<ScheduledTask> regTasks = (Set)this.scheduledTasks.computeIfAbsent(bean, (key) -> { return new LinkedHashSet(4); }); regTasks.addAll(tasks); } } catch (IllegalArgumentException var25) { throw new IllegalStateException("Encountered invalid @Scheduled method '" + method.getName() + "': " + var25.getMessage()); }
返回所有的工作,该注册类实现了ScheduledTaskHolder的办法。
返回所有的实现ScheduledTaskHolder的工作:
【Java】 public Set<ScheduledTask> getScheduledTasks() { Set<ScheduledTask> result = new LinkedHashSet(); synchronized(this.scheduledTasks) { Collection<Set<ScheduledTask>> allTasks = this.scheduledTasks.values(); Iterator var4 = allTasks.iterator(); while(true) { if (!var4.hasNext()) { break; } Set<ScheduledTask> tasks = (Set)var4.next(); result.addAll(tasks); } } result.addAll(this.registrar.getScheduledTasks()); return result; }
ScheduledTaskRegistrar
ScheduledTask注册核心,ScheduledTaskHolder接口的一个重要的实现类,保护了程序中所有配置的ScheduledTask。指定TaskScheduler或者ScheduledExecutorService都是ok的,ConcurrentTaskScheduler也是一个TaskScheduler的实现类。它是ScheduledAnnotationBeanPostProcessor的一个重要角色。
指定任务调度taskScheduler:
【Java】//这里,如果你指定的是一个TaskScheduler、ScheduledExecutorService皆可 //ConcurrentTaskScheduler也是一个TaskScheduler的实现类 public void setScheduler(@Nullable Object scheduler) { if (scheduler == null) { this.taskScheduler = null; } else if (scheduler instanceof TaskScheduler) { this.taskScheduler = (TaskScheduler)scheduler; } else { if (!(scheduler instanceof ScheduledExecutorService)) { throw new IllegalArgumentException("Unsupported scheduler type: " + scheduler.getClass()); } this.taskScheduler = new ConcurrentTaskScheduler((ScheduledExecutorService)scheduler); }}
重要的一步:如果没有指定taskScheduler ,这外面会new一个newSingleThreadScheduledExecutor,但它并不是一个正当的线程池,所以所有的工作还须要One by One程序执行,其中默认为:Executors.newSingleThreadScheduledExecutor(),所以必定单线程串行执行。
触发执行定时工作:
【Java】protected void scheduleTasks() { //这一步十分重要:如果咱们没有指定taskScheduler,这里会new一个newSingleThreadScheduledExecutor //显然他并不是一个真的线程池,所以他所有的工作还是得一个一个的执行 //默认是Executors.newSingleThreadScheduledExecutor(),所以必然是串行执行 if (this.taskScheduler == null) { this.localExecutor = Executors.newSingleThreadScheduledExecutor(); this.taskScheduler = new ConcurrentTaskScheduler(this.localExecutor); } //上面就是借助TaskScheduler来启动每一个工作 //并且把启动了的工作最终保留到scheduleTasks中 Iterator var1; if (this.triggerTasks != null) { var1 = this.triggerTasks.iterator(); while(var1.hasNext()) { TriggerTask task = (TriggerTask)var1.next(); this.addScheduledTask(this.scheduleTriggerTask(task)); } } ...... ...... ......}
四、分布式定时工作
下面的办法都是对于单机定时工作的实现,如果是分布式环境能够应用 Redis 来实现定时工作。
应用 Redis 实现提早工作的办法大体可分为两类:通过 ZSet 的形式和键空间告诉的形式。
4.1 通过 ZSet 的形式、Redis 的键空间告诉
上述计划都是基于单线程的任务调度,如何引入多线程进步延时工作的并发解决能力?
- 通过 ZSet 实现定时工作的思路是,将定时工作寄存到 ZSet 汇合中,并且将过期工夫存储到 ZSet 的 Score 字段中,而后通过一个无线循环来判断以后工夫内是否有须要执行的定时工作,如果有则进行执行。
- 能够通过 Redis 的键空间告诉来实现定时工作,它的实现思路是给所有的定时工作设置一个过期工夫,等到过期之后通过订阅过期音讯就能感知到定时工作须要被执行了,此时执行定时工作即可。
- 默认状况下 Redis 是不开启键空间告诉的,须要通过 config set notify-keyspace-events Ex 的命令手动开启。
4.2 Elastic-job、xxl-job
- elastic-job:是由当当网基于quartz 二次开发之后的散布式调度解决方案 , 由两个绝对独立的子项目Elastic-Job-Lite和Elastic-Job-Cloud组成 。elastic-job次要的设计理念是无中心化的分布式定时调度框架,思路来源于Quartz的基于数据库的高可用计划。但数据库没有分布式协调性能,所以在高可用计划的根底上减少了弹性扩容和数据分片的思路,以便于更大限度的利用分布式服务器的资源。
- XXL-JOB:是一个轻量级分布式任务调度框架,它的外围设计理念是把任务调度分为两个外围局部:调度核心(xxl-admin),和执行器。隔离成两个局部。这是一种中心化的设计,由调度核心来对立治理和调度各个接入的业务模块(也叫执行器),接入的业务模块(执行器)只须要接管调度信号,而后去执行具体的业务逻辑,两者能够各自的进行扩容。
五、总结
定时工作作为业务场景中不可或缺的一种通用能力,使用适宜的定时工作可能疾速解决业务问题,同时又能防止适度设计带来的资源节约。本文旨在梳理目前定时工作的支流方案设计和原理,心愿在读者在技术选型和计划重构时有所帮忙,唯有落地推动业务的技术才有价值。技术永远不停改革,思考不能止步不前。
作者:京东物流 肖明睿
起源:京东云开发者社区