定时任务学习

一.理论基础

前置复习：什么是完全二叉树：

除了最后一层外其他层都达到最大节点数，且最后一层节点都靠左排列

1.小顶堆

小顶堆(Min-Heap)是一种特殊的完全二叉树结构,核心原则只有一条:

堆序性质:任意一个父节点的值,都小于或等于它的子节点的值。

也就是说,根节点永远是整棵树里最小的元素。

关键特征

1. 完全二叉树
除了最后一层,其他层都是满的,最后一层的节点从左往右依次填充,不能有空隙。这个性质保证了堆可以用数组来紧凑存储,不需要用链表/指针存左右子节点。

2. 数组存储的下标关系
如果用数组存储,下标从 0 开始,对于下标为i的节点:

• 父节点下标:(i - 1) / 2
• 左子节点下标:2i + 1
• 右子节点下标:2i + 2

3. 只保证父子关系,不保证兄弟节点大小
左子节点和右子节点之间没有大小约束,只要求父节点 ≤ 两个子节点即可。所以小顶堆不是完全有序的,只有根节点能保证是最小值,其他位置的相对顺序是不确定的。

两个核心操作

插入(Push)—— 上浮(Sift Up / Bubble Up)

1. 把新元素放到数组末尾(树的最后一个位置)
2. 和父节点比较,如果比父节点小,就交换位置
3. 重复这个过程,一路"往上冒泡",直到满足堆序性质或到达根节点

删除堆顶(Pop)—— 下沉(Sift Down / Bubble Down)

1. 把根节点(最小值)取出,同时把数组最后一个元素挪到根节点位置
2. 从根开始,和左右子节点中较小的那个比较,如果比子节点大就交换
3. 重复这个过程,一路"往下沉",直到满足堆序性质或到达叶子节点

2.时间轮算法

1️⃣ 数组/链表 + while-true-sleep

- 原理:用一个数组(或链表数组),每个下标代表一个时间刻度(比如每秒一个格子),格子里挂一个链表存放这个时刻要执行的任务。一个死循环线程不断遍历数组,走到哪个下标,就把那个链表里的任务取出来执行。

特点:

• 实现最简单,直观
• 缺点:如果时间跨度很大(比如要支持"1年后执行"),数组就要开得很大,内存浪费严重

- 性能：

每次 tick 的成本:O(1) 定位到当前格子,但格子里如果堆积了很多任务,遍历这个链表是 O(m)(m = 该格任务数)

主要损耗:

• 死循环空转:线程一直while(true) { sleep(); check(); },即使没任务也在消耗 CPU 做无意义的唤醒检查
• 内存浪费:要支持多长的延迟,数组就要开多大。比如要支持"1小时后执行",按秒精度就要开 3600 个格子,大部分格子常年是空的

2️⃣ round 型时间轮

- 原理:数组大小固定(比如只做 60 格,代表 60 秒一圈),但每个任务额外记一个round值,表示"还要转几圈才轮到它"。指针走到对应格子时,先把 round 减一,减到 0 才真正取出执行。

特点:

• ✅ 用固定大小的数组就能支持任意长的延迟时间(不用开一个超大数组)
• ❌遍历到某个格子时,要检查这个格子链表里所有任务的 round 值,任务多的时候效率较低,而且转一圈的时间粒度受限(比如 60 秒一圈,精度就只能到秒级)

-性能

每次 tick 的成本:仍然要遍历当前格子链表里所有任务,逐个检查 round 是否为 0——这是它最大的性能瓶颈

主要损耗:

• 如果一个格子里同时挂了 1000 个不同 round 值的任务(比如有的转1圈就到,有的要转100圈),每次指针扫过这个格子,都要把这 1000 个任务全部检查一遍 round 值,即使其中 999 个这一轮根本不需要处理
• 相当于用"固定内存"换来了"重复扫描的 CPU 开销",典型的空间换时间失败案例——省了内存,但没省计算

3️⃣ 分层时间轮

-原理:不只一个轮子,而是多个不同粒度的轮子叠在一起,比如:

• 秒轮:管理"多少秒后执行"
• 天轮:记录"几点执行"
• 月轮:记录"几号执行"

月轮转到某一格,就把里面的任务"降级"丢进天轮;天轮转到某一格,再看是否到执行时间。类似钟表的时针、分针、秒针分层联动。

特点:

• ✅ 效率最高,不需要遍历大量任务,每层只处理少量的降级操作
• ✅ 能优雅支持"几号几点执行"这种长跨度、高精度的场景
• ❌ 实现复杂度最高

-性能

每次 tick 的成本:均摊下来接近 O(1)

为什么损耗更低:

• 秒轮/天轮每次只处理"当前这一格"的任务,不需要检查 round(因为压根没有 round 这个概念)
• 只有当某一层"转完一圈"时,才会触发一次"降级"操作(把上层的一批任务搬到下层),这个操作不是每个 tick 都发生,而是被摊薄到很多次 tick 里
• 类似"时针不动,分针每转一圈才拨一下时针"——大部分时候只有最细粒度的那个轮子在真正工作,粗粒度的轮子几乎不动

一张表总结损耗来源