c++定时器的原理与实现

1. 定时器解决了什么问题？

在项目中，通常有诸如心跳机制、KEY到期机制等等，这种任务周期性执行或者延迟执行的场景。

所以 就需要定时器来实现这种周期任务或者延迟任务的执行。

2. 如何实现定时器？

要实现定时器首先需要进行2个抉择

1. 用什么容器/数据结构 来存储延迟任务
2. 用什么机制来等待任务到期

2.1 定时任务的存储结构

可以用最小堆、红黑树、时间轮来存储定时任务

如果用最小堆或者红黑树来存储定时任务的话，就直接用epoch time作为key，然后value就是定时任务。

最小堆

对应stl中的priority_queue容器，但是不支持重复key以及随机删除，一般用vector容器自己实现

1. 插入任务：将任务放到数组的最末尾，然后进行上浮操作，堆大小++
2. 弹出最近的任务：将根节点弹出，然后用末尾元素覆盖根节点元素，然后进行下沉操作，堆大小–
3. 删除任务：如果想要支持删除最小堆中的任务，需要维护一个hashmap，记录任务id和数组下标的映射关系，找到下标后，用末尾元素覆盖下标对于元素，然后进行下沉并上浮操作，堆大小–

最小堆的优点：因为是数组，所以cache友好。

红黑树

对应stl中的map/multimap容器，一般用multimap，因为支持重复的key

红黑树的优点：支持任意节点删除，支持范围查询

红黑树的缺点：cache不友好，而且需要存储父子节点和颜色信息。

时间轮

模拟时间转盘，每一个槽位代表一个时间刻度(如1ms)，插入任务时，根据当前时间计算出任务多少时间后会触发，直接将任务插入对应的槽位。

时间轮的优点：插入删除都是O(1)O(1)O(1)的复杂度，性能好。

时间轮的缺点：如果刻度太大会导致精度损失，如果刻度太小会导致占用太多内存，如果实现多层时间轮的话比较复杂。

2.2 等待定时任务到期的机制

因为定时任务其实也是一个事件，就需要和异步事件模型进行抽象统一，所以可以用以下的机制来等待任务到期。

1. timerfd
2. select/poll/epoll的超时参数
3. iouring的io_uring_prep_timeout

等待流程是：

1. 计算距离当前时间 和 最快的定时任务的时间 的差值diff
2. 将diff填入上面几种机制的等待时间
3. 事件触发或者等待时间结束，执行所有的过期任务