延时任务算法比较与源码分析

本是古典何须时尚 2022-12-02 10:50 87阅读 0赞

# 延时任务算法比较 #

## 主流工具包与算法 ##

*  小顶堆，时间排序算法
    
     *  JDK 的 Timer
     *  ScheduledThreadPool
     *  DelayQueue 配合线程池
 *  时间轮算法
    
     *  netty 实现
     *  kafka 实现

## 比较 ##

### 小顶堆算法 ###

优势：延时时间较精确，简单  
劣势：插入和修改复杂度 O(N)，存在排序开销  
适用场景：少量任务、延迟时间疏散的场景

### 时间轮算法 ###

优势：插入修改复杂度 O(1)，性能较好  
劣势：精确度固定，误差较大，不能很好的支持较长延时执行的任务，有固定的线程切换周期，容易导致无意义的线程唤醒（空推进），复杂  
适用场景：大量且密集任务，精确度不高，如平均每秒激活30个任务以上

--------------------

### Timer（不推荐使用） ###

内部维护一个优先队列，根据延迟时间排序，单线程执行。

##### 弊端 #####

*  优先队列的插入和删除的时间复杂度是O(logn)，当数据量大的时候，频繁的入堆出堆性能有待考虑。
 *  并且是单线程执行，那么如果一个任务执行的时间过久则会影响下一个任务的执行时间(当然你任务的run要是异步执行也行)。
 *  一个任务出错的时候会导致之后的任务都无法执行，使得整个延迟工具能力完全丧失。

### ScheduledThreadPool ###

大致的流程和 Timer 差不多，也是维护一个优先队列

*  增加了定时调度，通过重写 task 的 run 方法来实现周期性任务
 *  能多线程运行任务，不会单线程阻塞。
 *  且 Java 线程池的设定是 task 出错会把错误吃了，无声无息的。因此一个任务出错也不会影响之后的任务。

推荐任务数量少时使用，可以对其进行扩展

### DelayQueue 配合线程池 ###

DelayQueue 配合线程池或者继承 ScheduledThreadPool 在该方案的基础上进行一下数据统计、日志记录、错误处理等操作。  
用于代替单纯的 ScheduledThreadPool

--------------------

### 时间轮算法 ###

#### netty 中的实现 ####

实现较为简单，直接调用任务的 run 方法，有阻塞而影响后续任务调度的风险，任务少时存在大量无意义的线程唤醒

#### Kafka 中的优化 ####

*  多层时间轮
 *  按需创建
 *  增加了任务运行的绝对开始时间
 *

shoulder 中默认实现了`DelayQueue 配合线程池` 和时间轮的方式。[shoulder 框架地址][shoulder]

--------------------

参考

*  [时间轮算法][Link 1]
 *  [时间轮算法][Link 2]

[shoulder]: https://gitee.com/ChinaLym/shoulder-framework
[Link 1]: https://www.cnblogs.com/luozhiyun/p/12075326.html
[Link 2]: https://mp.weixin.qq.com/s?__biz=Mzg2MjEyNTk1Ng==&mid=2247484583&idx=1&sn=16eba3db3f70dfdbe6c37d51a22f5f12&chksm=ce0dee4cf97a675a806b43c3f45408ebf2e4971790547024a0fd8a81a2a9c3a0e217e3a02621&token=1972081544&lang=zh_CN&scene=21#wechat_redirect