时间轮算法（TimingWheel）

前言

近期在维护公司的调度平台，其中有个关键功能那就是定时任务；定时任务大家平时肯定接触的不少，比如 JDK 中的 Timer、ScheduledExecutorService、调度框架 Quartz 等。

通常用于实现 XX 时间后的延时任务，或周期性任务；

比如在电商交易中，经常有这样的场景：下单后如果半个小时内没有支付，自动将订单取消。

实现这类需求通常有两种方式：

轮询定时任务：使用定时任务定期扫描订单状态表，如果半个小时后订单状态还未支付，则将订单取消。
延时消息：用户下单后，发送一个延时消息，指定半个小时后消息送达，那么消费者在半个小时后收到消息就查询消息状态，如果这个时候订单是未支付状态，则取消订单。

第一种属于常规做法，这类方式实现较为简单，只需要启动一个定时任务即可；但缺点同样也很明显，主要有以下几个缺点：

定时任务间隔的时间不好控制，给短了会造成很多无意义的扫描，增大数据库压力，给长了又会使得误差较大。
效率低下，随着订单增多耗时会呈线性增长，最差的情况甚至会出现上一波轮询还没有扫描完，下一波调度又来了。

时间轮用来解决什么问题？

如果一个系统中存在着大量的调度任务，而大量的调度任务如果每一个都使用自己的调度器来管理任务的生命周期的话，浪费cpu的资源并且很低效。

时间轮是一种高效来利用线程资源来进行批量化调度的一种调度模型。把大批量的调度任务全部都绑定到同一个的调度器上面，使用这一个调度器来进行所有任务的管理（manager），触发（trigger）以及运行（runnable）。能够高效的管理各种延时任务，周期任务，通知任务等等。

不过，时间轮调度器的时间精度可能不是很高，对于精度要求特别高的调度任务可能不太适合。因为时间轮算法的精度取决于，时间段“指针”单元的最小粒度大小，比如时间轮的格子是一秒跳一次，那么调度精度小于一秒的任务就无法被时间轮所调度。

应用场景

应用场景有很多，在 Netty、Akka、Quartz、ZooKeeper 、Kafka、JRaft 等组件中都存在时间轮的踪影。

时间轮结构

如图，JRaft中时间轮（HashedWheelTimer）是一个存储定时任务的环形队列，底层采用数组实现，数组中的每个元素可以存放一个定时任务列表（HashedWheelBucket），HashedWheelBucket是一个环形的双向链表，链表中的每一项表示的都是定时任务项（HashedWheelTimeout），其中封装了真正的定时任务（TimerTask）。

时间轮由多个时间格组成，每个时间格代表当前时间轮的基本时间跨度（tickDuration）。时间轮的时间格个数是固定的，可用 wheel.length 来表示。

时间轮还有一个表盘指针（tick），用来表示时间轮当前指针跳动的次数，可以用tickDuration * (tick + 1)来表示下一次到期的任务，需要处理此时间格所对应的 HashedWheelBucket 中的所有任务。

TFdream / blog