background
When it comes to scheduled tasks, the author has contacted crontable and spirng-schedule. Quartz has many implementation methods, but the bottom layer depends on the interruption of the operating system. Today, we are going to introduce a practical scheduled task time wheel, which can add points to the interview. The time-wheel algorithm was published in a paper “Hashed and Hierarchical Timing Wheels”. Of course, it has also been introduced in Java frameworks, such as Netty, Dubbo, etc.
design
Let’s talk about his design first, which is very similar to the clock in real life. The minute pointer moves from 0 to 12 at a constant speed, which is an hour. Then let’s think about hashmap. Let’s implement a simpler approach.
The design
Task manager: MyHashedWheelTimer is a container for task submission and execution,Task queue: HashedWheelBucket is a task assembly container in the same Hash slot. HashedWheelTimeout packs each task extension Pre, next, task execution time, etc., which contains the task of the smallest atomTimerTask, the length of time for the pointer to jump once in a cycle istickDuration.
The code
Let’s build several class models according to the design on the diagram.
public class MyHashedWheelTimer {
// Invoke the execution object of the scheduled task
private final Worker worker = new Worker();
/** * The millisecond when the scheduled task manager starts */
private volatile long startTime;
// The number of points that the pointer passes in a circle
private final int mask;
private final HashedWheelBucket[] wheel;
/** * The smallest unit of clock rotation */
private final long tickDuration;
// Initialize the task manager according to the time when the pointer jumps once
public MyHashedWheelTimer(long tickDuration) {}
// Add the timeout task 'task' to the task manager for subsequent triggering
public HashedWheelTimeout newTimeout(Runnable task, long delay, TimeUnit unit){}}private static final class HashedWheelBucket {
private HashedWheelTimeout head;/ / queue head
private HashedWheelTimeout tail;/ / queue tail
// Add the timeout task to the hash slot queue
void addTimeout(HashedWheelTimeout timeout) {}
// Execute the timeout task
void doTimeouts(long deadline, long tick) {}
// Remove the task after executing the task
public HashedWheelTimeout remove(HashedWheelTimeout timeout) {}}private final class Worker implements Runnable {
private long tick;// The number of pointer jumps continues to stack as the task manager starts
@Override
public void run(a) {
do {
final long deadline = waitForNextTick();// The time after each hop
/ /... Find the corresponding task and execute it
} while (true);
}
private long waitForNextTick(a) {
// The pointer jumps once}}// Wrap the task and its execution time
private static final class HashedWheelTimeout {
long remainingRounds;// The task will be executed after how many times the clock has been turned from start to end
HashedWheelTimeout next;
HashedWheelTimeout prev;
HashedWheelBucket bucket;
long deadline;
Runnable task;
HashedWheelTimeout(Runnable task, long deadline) {
this.task = task;
this.deadline = deadline; }}Copy the codeThe above four classes provide the most basic functionality, but we will supplement the implementation below
public MyHashedWheelTimer(long tickDuration) {
wheel = createWheel(64);// 64 cells per cycle by default
mask = wheel.length - 1;// Find the hash ring where the task is located, for example, a & mask = idx
this.tickDuration = TimeUnit.MILLISECONDS.toMillis(tickDuration);// The jump time
startTime = System.currentTimeMillis();// Task manager start event
new Thread(worker).start();// Start the task calling thread
}
// Create a HashedWheelBucket object on each hash slot
private static HashedWheelBucket[] createWheel(int ticksPerWheel) {
HashedWheelBucket[] wheel = new HashedWheelBucket[ticksPerWheel];
for (int i = 0; i < wheel.length; i++) {
wheel[i] = new HashedWheelBucket();
}
return wheel;
}
public HashedWheelTimeout newTimeout(Runnable task, long delay, TimeUnit unit) {
// Which millisecond in the future will the task be executed
long deadline = System.currentTimeMillis() + unit.toMillis(delay) - startTime;
HashedWheelTimeout timeout = new HashedWheelTimeout(task, deadline);
// Task execution time from the number of cycles required to start the task manager
timeout.remainingRounds = (deadline / tickDuration);
// What position index will the task fall on in the hash slot
int stopIndex = (int) ((deadline / tickDuration) & mask);
HashedWheelBucket bucket = wheel[stopIndex];
bucket.addTimeout(timeout);// Add tasks to the list of hash slots
return timeout;
}
private final class Worker implements Runnable {
public void run(a) {
do {
final long deadline = waitForNextTick();
if (deadline > 0) {
int idx = (int) (tick & mask); // & 64
HashedWheelBucket bucket =
wheel[idx];
bucket.doTimeouts(deadline, tick);// Executes scheduled tasks that meet the conditions in the hash slottick++; }}while (true); }}void addTimeout(HashedWheelTimeout timeout) {
// Add nodes to bidirectional lists
}
public HashedWheelTimeout remove(HashedWheelTimeout timeout) {
// Delete a node from the list
}
// Iterate through all tasks in the list
void doTimeouts(long deadline, long tick) {
HashedWheelTimeout timeout = head;
while(timeout ! =null) {
HashedWheelTimeout next = timeout.next;
// If remainingRounds(number of pointer jumps required)-tick(number of jumps already) <=0 is met, task execution is triggered
if (timeout.remainingRounds - tick <= 0) {
next = remove(timeout);
if (timeout.deadline <= deadline) {
timeout.task.run();// Call the task's run() method, similar to a thread pool
} else {
throw newIllegalStateException(); } } timeout = next; }}Copy the codeAnalysis of the
The code is just the implementation of basic functions, specific we can see and Dubbo or Netty implementation difference, such as task management does not start and stop, task submission can not be cancelled, thread is not safe, input is not rich enough, the number of tasks is not controllable and so on.
thinking
- The task executed by a time wheel pair will be processed only once. How to implement a periodic task?
- What if the task has to wait a long time to execute?
- If you have a lot of tasks that are very intensive how do you get the task closest to the theoretical execution time?
conclusion
The code is not complete, if you need complete code can leave a message.