Java时间轮详解

一、时间轮概述

时间轮是一种机制，用来以定期的方式执行任务。它可以以非常高效的方式进行任务分发和调度。时间轮首先出现在论文《Hashed and Hierarchical Timing Wheels》中，简化了分布式定时器的实现。

时间轮由很多格子组成，每个格子对应着一个时间点。一个指针以定期的方式指向时间轮上的格子。当指针指向某一个格子时，时间轮会查找这个格子上维护的任务并执行。执行完成后，时间轮会指向下一个格子并重复这个过程。

时间轮通常用于实现批量任务的延迟执行，例如，批量发送消息、数据分发、定时任务等场景。

二、时间轮的实现

1. 时间轮的结构

时间轮由很多格子（bucket）组成，每个格子对应着一个时间点。每个格子保存了一个任务链表。

// 时间轮格子结构体
public class TimeWheelBucket {
    // 任务链表头
    private TimeWheelTask head;
    // 任务链表尾
    private TimeWheelTask tail;

    // 添加任务
    public void addTask(TimeWheelTask task) {
        if (head == null) {
            head = tail = task;
        } else {
            tail.next = task;
            task.prev = tail;
            tail = task;
        }
    }

    // 删除任务
    public void removeTask(TimeWheelTask task) {
        if (task == null) {
            return;
        }
        if (task == head && task == tail) {
            head = tail = null;
        } else if (task == head) {
            head = head.next;
            head.prev = null;
        } else if (task == tail) {
            tail = tail.prev;
            tail.next = null;
        } else {
            task.prev.next = task.next;
            task.next.prev = task.prev;
        }
    }
}

// 时间轮任务结构体
public class TimeWheelTask {
    // 任务执行器
    private Runnable task;
    // 下一个任务节点
    TimeWheelTask next;
    // 上一个任务节点
    TimeWheelTask prev;

    // 构造函数
    public TimeWheelTask(Runnable task) {
        this.task = task;
    }

    // 执行任务
    void execute() {
        task.run();
    }
}

这个结构体中，TimeWheelBucket表示时间轮的格子，每个格子保存一个任务链表。TimeWheelTask表示任务节点，保存了要执行的任务和下一个节点、上一个节点的信息。

2. 时间轮的核心算法

时间轮的核心算法是任务的添加和查找。任务的添加可以通过将任务插入对应格子的任务链表实现。任务查找则需要根据当前指针的位置，找到对应格子的任务链表，并依次执行其中的任务。具体的实现过程被称为“时间轮的转动”。

// 时间轮类
public class TimeWheel {
    // 时间轮大小
    private int wheelSize;
    // 时间轮指针
    private int pointer = 0;
    // 时间轮格子数组
    private TimeWheelBucket[] buckets;
    // 时间轮定时器线程
    private Thread thread;
    // 时间轮状态锁
    private final Object lock = new Object();

    // 构造函数
    public TimeWheel(int wheelSize) {
        this.wheelSize = wheelSize;
        buckets = new TimeWheelBucket[wheelSize];
        for (int i = 0; i  {
            while (true) {
                try {
                    Thread.sleep(1000);
                    pointer = (pointer + 1) % wheelSize;
                    synchronized (lock) {
                        TimeWheelBucket bucket = buckets[pointer];
                        TimeWheelTask task = bucket.head;
                        while (task != null) {
                            bucket.removeTask(task);
                            task.execute();
                            task = bucket.head;
                        }
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        });
        thread.start();
    }

    // 停止时间轮
    public void stop() {
        thread.interrupt();
    }

    // 添加任务
    public void addTask(Runnable task, int delaySecond) {
        synchronized (lock) {
            int index = (pointer + delaySecond) % wheelSize;
            TimeWheelBucket bucket = buckets[index];
            bucket.addTask(new TimeWheelTask(task));
        }
    }
}

这个类中有三个核心信息：时间轮大小、指针位置和格子数组。在构造函数中，我们创建了大小为wheelSize的时间轮。每个轮盘上的格子由一个TimeWheelBucket实例来表示，格子中维护一个任务链表。我们可以通过指针不断地指向下一个格子来模拟时间的不断流逝。

在添加任务时，我们将任务添加到距离当前时间delaySecond秒的任务链表中。比如，如果当前指针指向了第0个格子，我们添加一个延迟执行5秒的任务，那么我们就将这个任务添加到第5个格子的任务链表中。

三、时间轮的使用场景

时间轮可以用于任务调度的场景，例如：

1. 消息发送

在批量消息发送的系统中，我们可以使用时间轮来实现延时消息的发送。例如，我们需要向大量的用户发送提醒消息，在用户提交数据后，我们需要将消息放置到时间轮的对应位置，以实现定时发送消息的功能。

2. 数据分发

在分布式系统中，我们常常需要实现数据的定时分发。

例如，我们需要将一个文件分发给n个机器节点，我们可以使用时间轮实现每隔m秒向每个节点分发一部分数据。

3. 定时任务

时间轮也可以用于定时任务的场景。例如，我们需要实现一个周期性的任务（例如每隔30s执行一次）。我们可以使用时间轮来进行任务调度，将任务添加到对应的时间轮格子中。

注意：时间轮的设计可以灵活的适用于不同的场景。在具体的应用中，我们可以添加一些自定义的信息来支持更高效的任务调度。