引言

在开发中，往往会遇到一些关于延时任务的需求。例如

  • 生成订单30分钟未支付，则自动取消
  • 生成订单60秒后,给用户发短信

对上述的任务，我们给一个专业的名字来形容，那就是延时任务。那么这里就会产生一个问题，这个延时任务和定时任务的区别究竟在哪里呢？一共有如下几点区别

  1. 定时任务有明确的触发时间，延时任务没有

  2. 定时任务有执行周期，而延时任务在某事件触发后一段时间内执行，没有执行周期

  3. 定时任务一般执行的是批处理操作是多个任务，而延时任务一般是单个任务

下面，我们以判断订单是否超时为例，进行方案分析

方案分析

数据库轮询

思路:

对于实现一个定时任务，一般的做法是将定时任务写入数据库，通过一个线程定时查询出将要到期的任务，再执行任务相关逻辑。该方案的优点是实现简单，尤其适合单机或者业务量比较小的场景。

优点:

  • 简单易行，支持集群操作

缺点:

  • 对服务器内存消耗大,由于某些场景定时任务时间集中在某个时间点，导致集群单节点压力过大。
  • 存在延迟，比如你每隔3分钟扫描一次，那最坏的延迟时间就是3分钟
  • 在分布式且业务量较大的场景中会引入很多复杂性。首先，需要设计一套合理的分库分表逻辑，以及集群任务负载逻辑。
  • 如果数据量比较大，千万级甚至更多，插入频率很高的话，上面的方式在性能上会出现一些问题，查找和更新对会占用很多时间，轮询频率高的话甚至会影响数据入库。
  • 需要合理的预估容量，否则后续线性存储扩容将会非常复杂。

时间堆

思路:

最常见的时间堆一般用小顶堆实现，小顶堆其实就是一种特殊的二叉树

小顶堆的好处是什么呢？对于定时器来说，如果堆顶元素比当前的时间还要大，那么说明堆内所有元素都比当前时间大。进而说明这个时刻我们还没有必要对时间堆进行任何处理。定时检查的时间复杂度是O(1)。

当我们发现堆顶的元素小于当前时间时，那么说明可能已经有一批事件已经开始过期了，这时进行正常的弹出和堆调整操作就好。每一次堆调整的时间复杂度都是O(LgN)。

优缺点:

优点:

  • 效率高,任务触发时间延迟低。

缺点:

  • 服务器重启后，数据全部消失，怕宕机
  • 集群扩展相当麻烦
  • 因为内存条件限制的原因，比如下单未付款的订单数太多，那么很容易就出现OOM异常
  • 代码复杂度较高

时间轮

思路:

时间轮是一种非常惊艳的数据结构。其在Linux内核中使用广泛，是Linux内核定时器的实现方法和基础之一。按使用场景，大致可以分为两种时间轮：原始时间轮和分层时间轮。分层时间轮是原始时间轮的升级版本，来应对时间“槽”数量比较大的情况，对内存和精度都有很高要求的情况。我们延迟任务的场景一般只需要用到原始时间轮就可以了。

先上一张时间轮的图

时间轮算法可以类比于时钟，如上图箭头（指针）按某一个方向按固定频率轮动，每一次跳动称为一个 tick。这样可以看出定时轮由个3个重要的属性参数，ticksPerWheel（一轮的tick数），tickDuration（一个tick的持续时间）以及 timeUnit（时间单位），例如当ticksPerWheel=60，tickDuration=1，timeUnit=秒，这就和现实中的始终的秒针走动完全类似了。

如果当前指针指在1上面，我有一个任务需要4秒以后执行，那么这个执行的线程回调或者消息将会被放在5上。那如果需要在20秒之后执行怎么办，由于这个环形结构槽数只到8，如果要20秒，指针需要多转2圈。位置是在2圈之后的5上面（20 % 8 + 1）

相比的数据结构，时间轮在算法复杂度上有一定优势。时间堆由于涉及到排序，需要调堆，插入和移除的复杂度是O(lgn)，而时间轮在插入和移除的复杂度都是O(1)。

优点:

  • 效率高,任务触发时间延迟时间比延迟队列低，代码复杂度比延迟队列低。

缺点:

  • 服务器重启后，数据全部消失，怕宕机
  • 集群扩展相当麻烦
  • 因为内存条件限制的原因，比如下单未付款的订单数太多，那么很容易就出现OOM异常

redis

思路一

Redis中的ZSet是一个有序的Set，内部使用HashMap和跳表(SkipList)来保证数据的存储和有序，HashMap里放的是成员到score的映射，而跳跃表里存放的是所有的成员，排序依据是HashMap里存的score,使用跳跃表的结构可以获得比较高的查找效率，并且在实现上比较简单。

插入和删除的时间复杂度是O(logn)，当达到了一定的数据规模之后，它的效率与红黑树差不多

利用redis的zset,zset是一个有序集合，每一个元素(member)都关联了一个score,通过score排序来取集合中的值

zset常用命令

  • 添加元素:ZADD key score member [[score member] [score member] ...]
  • 按顺序查询元素:ZRANGE key start stop [WITHSCORES]
  • 查询元素score:ZSCORE key member
  • 移除元素:ZREM key member [member ...]

在用作延迟任务的时候，可以在添加数据的时候，使用zadd把score写成未来某个时刻的unix时间戳。消费者使用zrangeWithScores获取优先级最高的（最早开始的的）任务。注意，zrangeWithScores并不是取出来，只是看一下并不删除.程序对最早的这个消息进行验证，是否到达要运行的时间，如果是则执行，然后删除zset中的数据。如果不是，则继续等待。

那么如何实现呢？我们将订单超时时间戳与订单号分别设置为score和member,系统扫描第一个元素判断是否超时，具体如下图所示

如果是多个线程去轮询这个Sorted Set，还有考虑并发问题，假如说一个任务到期了，也被多个线程拿到了，这个时候必须保证只有一个线程能执行这个任务，这可以通过zrem命令来实现，只有删除成功了，才能执行任务，这样就能保证任务不被多个任务重复执行了。

思路二

该方案使用redis的Keyspace Notifications，中文翻译就是键空间机制，就是利用该机制可以在key失效之后，提供一个回调，实际上是redis会给客户端发送一个消息。是需要redis版本2.8以上。

但是redis的pub/sub机制存在一个硬伤，Redis的发布/订阅目前是即发即弃(fire and forget)模式的，因此无法实现事件的可靠通知。也就是说，如果发布/订阅的客户端断链之后又重连，则在客户端断链期间的所有事件都丢失了。

因此，方案二不是太推荐。当然，如果你对可靠性要求不高，可以使用。

优点:

  • 解耦：把任务、任务发起者、任务执行者的三者分开，逻辑更加清晰，程序强壮性提升，有利于任务发起者和执行者各自迭代，适合多人协作。

  • 异常恢复：由于使用Redis作为消息通道，消息都存储在Redis中。如果发送程序或者任务处理程序挂了，重启之后，还有重新处理数据的可能性。

  • 分布式：如果数据量较大，程序执行时间比较长，我们可以针对任务发起者和任务执行者进行分布式部署。特别注意任务的执行者，也就是Redis的接收方需要考虑分布式锁的问题。

缺点:

  • 需要额外进行redis维护

使用消息队列

AMQP和RabbitMQ本身没有直接支持延迟队列功能，但是可以通过以下特性模拟出延迟队列的功能。

但是我们可以通过RabbitMQ的两个特性来曲线实现延迟队列：

  • Time To Live(TTL):

    RabbitMQ可以针对Queue和Message设置 x-message-tt，来控制消息的生存时间，如果超时，则消息变为dead letter

    RabbitMQ针对队列中的消息过期时间有两种方法可以设置。

    1. 通过队列属性设置，队列中所有消息都有相同的过期时间。
    2. 对消息进行单独设置，每条消息TTL可以不同。

    如果同时使用，则消息的过期时间以两者之间TTL较小的那个数值为准。消息在队列的生存时间一旦超过设置的TTL值，就成为dead letter

  • Dead Letter Exchanges（DLX）:

    RabbitMQ的Queue可以配置x-dead-letter-exchange 和x-dead-letter-routing-key（可选）两个参数，如果队列内出现了dead letter，则按照这两个参数重新路由。

    • x-dead-letter-exchange：出现dead letter之后将dead letter重新发送到指定exchange

    • x-dead-letter-routing-key：指定routing-key发送

      队列出现dead letter的情况有：

    • 消息或者队列的TTL过期

    • 队列达到最大长度

    • 消息被消费端拒绝（basic.reject or basic.nack）并且requeue=false

      利用DLX，当消息在一个队列中变成死信后，它能被重新publish到另一个Exchange。这时候消息就可以重新被消费。

结合以上两个特性，就可以模拟出延迟消息的功能.

优点:

  • 高效，可以利用RabbitMQ的分布式特性轻易进行横向扩展，且支持持久化

缺点：

  • 不支持对已发送的消息进行管理
  • 一个消息比在同一队列中的其他消息提前过期，提前过期的消息也不会优先进入死信队列。需要确保业务上每个任务的延迟时间是一致的。如果有不同延时的任务，需要为每种不同延迟的任务单独创建消息队列，缺乏灵活性。

参考: https://www.cnblogs.com/rjzheng/p/8972725.html https://chai2010.cn/advanced-go-programming-book/ch6-cloud/ch6-03-delay-job.html https://www.jianshu.com/p/a8c1458998aa