共计 3549 个字符，预计需要花费 9 分钟才能阅读完成。
提早队列是这样一种队列：元素有一个过期工夫，元素在队列中程序是依照过期工夫排序的，只有达到过期工夫的元素能力出队，最先达到过期工夫的元素最先出队。
提早队列能够用到这样的场景：比方有一个工作须要 10 分钟后执行，那么就能够把这个工作存入提早队列，并且设置过期工夫为 10 分钟，队列的另一头有一个消费者去生产，没达到过期工夫时消费者是取不到这个工作的，达到过期工夫后消费者能力取到这个工作。
像这种多少分钟之后执行的工作特地适宜应用提早队列实现，如果不应用提早队列，把工作存入数据库定期扫描也能实现，然而会有一个问题：如果扫描时间距离长了，执行工夫不准，如果扫描间隔时间短了，那么对数据库压力比拟大。
DelayQueue
DelayQueue 是 JDK 中自带的提早队列实现，向该队列中提交的工作须要实现 Delayed 接口，这个接口只有一个办法 long getDelay(TimeUnit unit) 这个接口如果返回 0 或正数示意工作曾经达到了过期工夫，能够执行；否则示意还没有达到过期工夫，不能执行。
DelayQueue 应用示例
public class DelayedTask implements Delayed {
private String taskName;
private long avaibleTime;
public String getTaskName() {return taskName;}
public DelayedTask(String taskName, long delayTime) {
this.taskName = taskName;
this.avaibleTime = System.currentTimeMillis() + delayTime;}
@Override
public long getDelay(TimeUnit unit) {return unit.convert(avaibleTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
@Override
public int compareTo(Delayed o) {return (int)(this.avaibleTime - ((DelayedTask)o).avaibleTime);
}
}下面代码中咱们定义了 DelayedTask 工作并且实现了 Delayed 接口，在 DelayedTask 中保护了一个成员变量 avaibleTime 寄存工作到期工夫，在 getDelay 办法实现中用 avaibleTime 减去以后工夫戳，如果是一个正数或 0，示意工作曾经达到了到期工夫，能够执行了。
测试
DelayQueue<DelayedTask> queue = new DelayQueue<>();
new Thread(()->{
try {
//take 办法会阻塞，直到有工作到期
DelayedTask task = queue.take();
System.out.println(task.getTaskName());
} catch (InterruptedException e) {e.printStackTrace();
}
}).start();
queue.put(new DelayedTask("工作", 3000)); 三秒种后输入 工作
实现原理
次要属性
// 优先队列
private final PriorityQueue q = new PriorityQueue();
//leader 线程示意正在期待出队的线程
private Thread leader = null;
// 可用条件
private final Condition available = lock.newCondition();DelayQueue 的底层实现是优先队列
take 办法
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly(); ①
try {for (;;) {E first = q.peek();
if (first == null) ②
available.await();
else {long delay = first.getDelay(NANOSECONDS);
if (delay <= 0) ③
return q.poll();
first = null; // don't retain ref while waiting
if (leader != null) ④
available.await();
else {Thread thisThread = Thread.currentThread();
leader = thisThread; ⑤
try {available.awaitNanos(delay);
} finally {if (leader == thisThread)
leader = null;
}
}
}
}
} finally {if (leader == null && q.peek() != null)
available.signal(); ⑥
lock.unlock();}
}在 take 办法中，首先获取锁，而后查看队首元素
- 如果队首元素为 null，阐明队列是空的，调用 available.await() 期待 ②
-
如果队首元素不为 null，调用 getDelay 判断该工作是否到期
- 如果返回正数或 0，阐明工作曾经到期，间接获取队首元素返回 ③
-
如果不是正数或 0，阐明工作还没到期。这时判断 leader 是否为 null
-
- 如果 leader 不为 null，阐明以后有一个 leader 在期待队列头元素到期，调用 available.await() 将以后线程挂起 ④
- 如果 leader 为 null，将以后线程设置为 leader，并调用 available.await(delay) 挂起期待残余到期工夫。当线程被零碎唤醒后，将 leader 设置为 null，从新去获取元素，这时队首元素就曾经到期了，这个线程会在 ③ 处返回。
如图，当初有三个线程去生产这个队列，队列中的 TaskA 没到执行工夫，Thread1 是以后的 Leader 线程，它会期待提早纳秒数，而后拉取队列头节点生产并且调用 signal() 唤醒 Follower 节点。如下图，Thread3 节点被唤醒，它会先看一下头节点是否到期，如果没到期就期待到它到期。
工夫轮算法
如上图，在工夫轮算法中，有一个轮，这个轮由 n 个槽组成，有一个指针向钟表一样每隔一个工夫间走到下个槽位上，而后这个槽位上的工作就能够执行。假如当初有 8 个槽组成工夫轮，指针每秒挪动一个槽位，当初指针指向 1 这个槽，假如当初有一个工作要在 5 秒钟之后执行，那么把这个工作就放在 5 + 1 = 6 这个槽上，这样在 5 秒钟后指针就会挪动到这个槽，而后这个槽对应的工作就会被执行。
如果有工作要在 20 秒后执行，那么就须要指针多转两圈，将工作放在（20%8 + 1）= 5 这个槽上。
这个圈数须要记录在槽中的数据结构外面。这个数据结构最重要的是两个指针，一个是触发工作的函数指针，另外一个是触发的总第几圈数。工夫轮能够用简略的数组或者是环形链表来实现。
netty 的 HashedWheelTimer 就采纳了工夫轮算法。
相比 DelayQueue 的数据结构，工夫轮在算法复杂度上有肯定劣势。DelayQueue 因为波及到排序，须要调整数据的地位，插入和移除的复杂度是 O(lgn)，而工夫轮在插入和移除的复杂度都是 O(1)。
应用 zset 实现提早队列
音讯的生产者应用 zadd quque [以后工夫戳 + 延迟时间] [序列化成字符串的音讯] 将音讯插入音讯队列。
开启多个线程一直执行 zrangebyscore quque [0] [以后工夫戳] limit 0 1 命令，ZRANGEBYSCORE 这个命令示意获取队列中的成员，并按分数从小到大排列，limit 0 1 偏移量为 0，获取一条数据，所以返回的就是工夫戳最小的那条。
判断这条数据是否达到了执行工夫，如果达到了执行工夫，执行 zrem member，ZREM 执行这个命令有两个目标：
1. 从提早队列中删除这条音讯避免其它线程再次获取；
2. 可能存在多个线程同时获取到这条音讯，所以这里靠 zrem 只有返回 > 0，才阐明以后线程胜利获取到音讯，能够生产音讯，如果返回 = 0，阐明已有其它线程领先获取到音讯了，以后线程不能够生产音讯。
优化：
因为咱们是用多个线程去同时 zrangebyscore 而后再通过 zrem 是否胜利来确定是否争抢到音讯，没有抢到音讯的线程实际上就白白执行了一次 zrangebyscore，能够应用 Lua 脚本将 zrangebyscore 和 zrem 放到一起在服务端执行。
