延时消息实现--从数据结构到落地实现

延时消息

指定延时后可以消费该消息或者说被执行

数据结构

有序表
1）有序数组（二分）
2）二叉搜索树（红黑树）
3）跳表
小根堆
1）Java的DelayQueue，优先级队列
跳表
1）查询时间复杂度logn

这3种数据结构的思想都是根据延时消息的执行时间升序排序，最小的就是最先执行的，添加消息的时候维护大小关系；

落地实现

1）定时扫描MySQL
创建一个延时消息表delay_msg，有一个delivery_time字段，表示执行时间，那么执行SQL select * from delay_msg where delivery_time<=now();,需要为delivery_time字段创建普通索引，提高搜索效率，底层的B+树可以看作是一个有序表；
2）定时扫描RocksDB（LSM树）
思想同上，不同在于LSM支持高并发写入；
3）定时扫描Redis
利用Redis有序集合zset，value是消息，score是执行时间。执行命令zrangebyscore获取可以执行的消息。zset底层是跳表；

定时扫描可以通过阻塞唤醒机制避免大量无用扫描

4）RocketMQ延时消息
缺点是不支持任意时间延时，可以改造；
5）Pulsar
学习中
6）QMQ
时间轮实现