任务调度之调度算法 _调度算法

在任务调度的场景中，经常遇到以下需求：

1、某个操作失败后，每隔1、2、5、10、20秒去重试
2、一篇公众号文章发布之后，要在5分钟之后推送到粉丝终端

这种场景当然可以通过 RocketMQ 这类支持延迟消息的中间件来做，如果从任务调度的角度该怎么做，任务队列怎么选择呢？从题干可知以下三要素：触发条件，延迟任务存储，时间到达之后的操作。这是一个非常典型的生产者消费者模型，生产者往任务队列放任务，消费者从队列中消费任务。先抛开生产者、消费者不讲，以下只讨论任务队列的选择。
JAVA DelayQueue、redis Sorted Set 都是延迟任务很好的选择，除此之外时间轮队列也是一种非常好，也非常适合的设计。本文对 DelayQueue 和时间轮做特点分析和对比。
01. DelayQueue 延时队列DelayQueue 本质是一个无界的优先级阻塞队列，内部封装了 PriorityQueue，提供了 put 接口放入任务，take 接口获取任务。添加元素时需要设置一个延迟时间，在有任务到达执行时间前，take 接口是阻塞的。所以 DelayQueue 实现延时，核心功能有：

1. 有序性，延时短的先出列2. put、take 后依然有序3. 没有元素到达时间，take被阻塞4. 线程安全

第1、2点是 PriorityQueue 实现的，第 3、4 点是 DelayQueue 自己实现的。

文章插图
【任务调度之调度算法】

有序性

PriorityQueue 内部使用小顶堆来维持顺序，最小堆并没有通过二叉树实现，而是使用了数组存储 Object[] queue 。每次取出最小元素的时间复杂度是 O(1)，使用数组寻址非常快，但是增删元素时需要重排序，时间复杂度是O(logN)，最终其每次存取时间复杂度是 O(logN) 。

文章插图

take 元素取第 0 个
每次 put 时，需要排序达到新平衡。比较下标通过 int parent = (k - 1) >>> 1; 计算，take 也是类似的计算。

文章插图

阻塞 && 线程安全

文章插图

OK，明白了，当队列为空或者到达时间之前，通过 ReentrantLock + condition 配合使用实现 take 时线程安全和阻塞，put 时同样使用同一把 ReentrantLock，进而 condition signal 缓存等待的线程，和AQS基本类似。

文章插图

存在的问题

DelayQueue 是一个很优秀的设计，精巧、漂亮，使用小顶堆 O(logN) 时间复杂度维持队列有序，ReentrantLock + condition 组合保证线程安全、阻塞，高效而也没有队列空轮询。这样优秀的设计存在什么问题？小任务量是没有问题，当任务非常多，且高频时就不太好了，为什么？
i. 锁
put、take 共用一把锁，在 take lock 生效时，是不能 put 的。什么是take lock 生效呢？在 take 过程中，有几处 await ，一旦调用了 condition.await() 即便没有调用 lock.unlock()，也会暂时释放锁，等待唤醒。此时是不会阻塞put操作的，但是，当有需要出列的元素时，put、take就会产生互斥，任务量大时，这俩就会产生性能问题。
ii. 数据结构
PriorityQueue 使用数组来存储元素，这是一种高效的结构，但是要求连续空间，任务量很大时是否一定有足够大的连续空间？如果没有就需要 GC，或者进入老年代了。
iii. 不支持去重
同一个时间点的同一个任务，不应该在队列出现两次。

微信平台上有多少公众号不清楚，应该是一个很大的数字，每天早上和晚上都会产生大量的公众号推送，如果使用 DelayQueue 能否满足需要呢？恐怕很难。
02. TimeWheel 时间轮时间轮也被广泛用于延时任务调度，比如Kafka、Netty，同样 XXL-JOB 也使用时间轮做任务调度。时间轮是一种非常巧妙的思想，没有查到其出处，个人感觉应该跟「CPU 时间片轮转调度算法」有关。基本结构如下