環形隊列高效觸發大量超時任務的算法實現

基于環形隊列的超時觸發算法只需要一個timer即可實現批量超時任務的觸發，CPU消耗低，效率高。原理介紹，下面是此算法的簡單實現。

1，TaskHolder.java

package com.zws.timer;
/**
 * 
 * @author wensh.zhu
 * @date 2018-04-22
 */
public class TaskHolder {
	
	/** 任務所需等待的圈數，即任務需要走幾圈**/
	private int cycles;
	private int delays;
	private Runnable task;
	
	public TaskHolder() {}

	public TaskHolder(int cycles, int delays, Runnable task) {
		this.cycles = cycles;
		this.delays = delays;
		this.task = task;
	}
	
	public boolean isTimeOut() {
		return cycles <= 0;
	}
	
	public void cutDown() {
		cycles --;
	}

	public int getCycles() {
		return cycles;
	}

	public void setCycles(int cycles) {
		this.cycles = cycles;
	}

	public int getDelays() {
		return delays;
	}

	public void setDelays(int delays) {
		this.delays = delays;
	}

	public Runnable getTask() {
		return task;
	}

	public void setTask(Runnable task) {
		this.task = task;
	}

	@Override
	public String toString() {
		return "TaskHolder[cycles=" + cycles + ", delays=" + delays + "]";
	}
	
}

2，TimerContext.java

package com.zws.timer;

import java.util.Map;
import java.util.Queue;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
/**
 * 
 * @author wensh.zhu
 * @date 2018-04-22
 */
public class TimerContext {

	public static final int DEFAULT_TICKS = 60;
	public static final int DEFAULT_TICK_DURATION = 1;
	
	private Map<Integer, Queue<TaskHolder>> taskHolders;
	private volatile int currentTick = 0;
	
	/** tick一圈的長度 **/
	private int ticks = DEFAULT_TICKS;
	
	/** 每tick一次的時間間隔，單位：秒**/
	private int tickDuration = DEFAULT_TICK_DURATION;
	
	public TimerContext() {
		init();
	}

	public TimerContext(int ticks, int tickDuration) {
		if (ticks <= 0)
			throw new IllegalArgumentException("ticks must be greater than 0");
		
		if (tickDuration <= 0)
			throw new IllegalArgumentException("tickDuration must be greater than 0");
		
		this.ticks = ticks;
		this.tickDuration = tickDuration;
		init();
	}
	
	private void init() {
		taskHolders = new ConcurrentHashMap<Integer, Queue<TaskHolder>>();
		for (int i = 0; i < ticks; i ++)
			taskHolders.put(i, new ConcurrentLinkedQueue<TaskHolder>());
	}
	
	/**
	 * 添加一個定時任務并計算需要走的圈數和落腳的index
	 * @param task
	 * @param delays
	 */
	public void addTask(Runnable task, int delays) {
		if (task == null) 
			throw new NullPointerException("task must not be null");
		
		if (delays <=0) 
			throw new IllegalArgumentException("delays must be greater than 0");
		
		int allSeconds = ticks * tickDuration;
		int cycles = delays / allSeconds;
		int index = ((delays % allSeconds) / tickDuration) + currentTick;
		TaskHolder metaData = new TaskHolder(cycles, delays, task);
		Queue<TaskHolder> tasks = taskHolders.get(index);
		synchronized (tasks) {
			tasks.add(metaData);
		}
	}
	
	public int tick() {
		currentTick = (currentTick + 1) % ticks;
		return currentTick;
	}
	
	public Queue<TaskHolder> getCurrentTasks() {
		return taskHolders.get(currentTick);
	}

	public int getCurrentTick() {
		return currentTick;
	}

	public int getTicks() {
		return ticks;
	}

	public int getTickDuration() {
		return tickDuration;
	}
	
	@Override
	public String toString() {
		return "TimerContext [timers=" + taskHolders + ", ticks=" + ticks + ", tickDuration=" + tickDuration
				+ ", currentTick=" + currentTick + "]";
	}
}

3，TimerScheduler.java

package com.zws.timer;

import java.io.IOException;
import java.util.Iterator;
import java.util.Queue;
import java.util.Timer;
import java.util.TimerTask;
/**
 * 用于判斷定時器是否到時、執行任務、維護定時器狀態。
 * @author wensh.zhu
 * @date 2018-04-22
 */
public class TimerScheduler extends TimerTask {
	
	private TimerContext timerContext;
	
	public TimerScheduler() {}

	public TimerScheduler(TimerContext timerContext) {
		this.timerContext = timerContext;
	}
	
	/**
	 * 定時檢測，如果定時器觸發時間到了就從集合中刪除并執行任務，否則圈數減一。
	 */
	@Override
	public void run() {
		if (timerContext == null) 
			return;
		
		Queue<TaskHolder> tasks = timerContext.getCurrentTasks();
		synchronized (tasks) {
			Iterator<TaskHolder> itor = tasks.iterator();
			while (itor.hasNext()) {
				TaskHolder timer = itor.next();
				if (timer.isTimeOut()) {
					itor.remove();
					new Thread(timer.getTask()).start();
				} else {
					timer.cutDown();
				}
			}
			
		}
		
		timerContext.tick();
	}
	
	public void addTask(Runnable task, int delays) {
		timerContext.addTask(task, delays);
	}

	public TimerContext getTimerContext() {
		return timerContext;
	}

	public void setTimerContext(TimerContext timerContext) {
		this.timerContext = timerContext;
	}
	
	public static void main(String[] args) throws IOException {
		TimerContext context = new TimerContext(60, 1);
		TimerScheduler sheduler = new TimerScheduler(context);
		sheduler.addTask(new Runnable() {
			
			public void run() {
				System.out.println(DateUtils.now());
			}
		}, 60);
		System.out.println(DateUtils.now());
		
		Timer timer = new Timer();
		timer.scheduleAtFixedRate(sheduler, 0, context.getTickDuration() * 1000L);
		
		System.in.read();
	}
	
}

4，DateUtils.java

package com.zws.timer;

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
/**
 * 
 * @author wensh.zhu
 * @date 2018-04-22
 */
public class DateUtils {
	public static final String DEFAULT_PATTERN = "yyyy-MM-dd HH:mm:ss";

	public static String now() {
		LocalDateTime time = LocalDateTime.now();
		return time.format(DateTimeFormatter.ofPattern(DEFAULT_PATTERN));
	}
	
	public static String plusSeconds(int seconds) {
		LocalDateTime time = LocalDateTime.now();
		time.plusSeconds(seconds);
		return time.format(DateTimeFormatter.ofPattern(DEFAULT_PATTERN));
	}
}