应用场景
-
清理日志
-
延时消费
-
锁续期
-
数据对比
-
数据刷新
定时任务实现
阶段一
每隔一小时清理日志
main(){
Thread t = new Thread(()->{
while(true){
sleep(一小时);
清理日志------
}
})
}
优点：简单容易实现
缺点：单一，不能实现多个定时任务
阶段二
class Task implements Runnable{
void run(){
清理日志;
}
}
class TimeOut{
private Date timeout;//执行的日志
}
class Timer extends Thread{
private Task task;
private TimeOut timeOut;
void run(){
while(true){
sleep(一分钟);
if(timeOut到期){
task.run();
}
}
}
}
main(){
for(一堆任务){
new Timer(task,timeOut).start();
}
}
优点：简单，能实现多个定时任务
缺点：线程资源有限，管理定时任务不方便
参考实现：linux的cron原理类似：busybox/crond.c at fc7868602ecf0d761a9a877141add4a9b6918d02 · mirror/busybox · GitHub
定时任务数据结构
class TimeTask implements Comparable<TimeTask>{
private Long nextExeTime;
private Runnable job;
}
单链表
单链表
main(){
while(true){
sleep(一分钟){
for(TimeTask : list){
if(timeTask不需要执行){
list.remove(timetask);
}
if(TimeTask是否到期){
timetask.run();
timetask.nextExeTime = 计算下一个执行时间;
}
}
}
}
}
优点：简单，适用于处理少量任务
缺点：时间复杂度高，O(n)；
小顶堆
小顶堆.jpg
main(){
while(true){
TimeTask = heep.peek();
long sleepTime;
while((sleepTime = timeTask.getNextExeTime - now) > 0 ){
timeTask.run();
}
heep.remove();
计算下一次 timeTask.nextExeTime
if（还需要执行){
heep.add(timeTask);
}
}
}
优点：使用小顶堆时间复杂度: log(n)，减少不必要的空轮询。
缺点：不适用于任务多，任务间隔比较短的任务，比如秒级，毫秒级的大量定时任务的执行。性能损耗严重
参考实现：jdk的Timer
时间轮
- 一级时间轮
class TimeOut{
TimeOut pre;
TimeOut next;
TimeTask task;
}
class Bucket{
TimeOut head;
TimeOut tail;
}
class WheelTimer{
Bucket[] buckets;
TimeUnit timeUnit;
Long tickDuration;
main(){
int tick = 0;
//不断轮询buckets，类似钟表的滴答
while(true){
//休眠一个tick,需要接口timeunit计算。
sleep(tickTime);
TimeOut current = bucket[tick];
while(current.next != null){
current.run();
current = current.next;
}
}
}
}
优点：简单，支持各种精度
缺点：对于任务多，时间跨度大的任务，需要很多的bucket，占用空间
- round时间轮
class TimeOut{
TimeOut pre;
TimeOut next;
TimeTask task;
Integer round;
}
class WheelTimer{
main(){
int tick = 0;
//不断轮询buckets，类似钟表的滴答
while(true){
//休眠一个tick,需要接口timeunit计算。
sleep(tickTime);
TimeOut current = bucket[tick];
while(current.next != null){
current.round--;
if(current.round<=0){
current.run();
}
current = current.next;
}
}
}
}
优点：简单，通过添加round来表示第几圈才执行任务减少空间消耗
缺点，对于时间间隔较大的任务会做很多次的空轮询
参考实现：netty/HashedWheelTimer.java at 4.1 · netty/netty · GitHub
-
分成时间轮
优点：承载更多的任务，满足各种精度
缺点：实现难度大
参考实现：kafka/core/src/main/scala/kafka/utils/timer at trunk · apache/kafka · GitHub
参考：时间轮算法
