10w定时任务，如何高效触发超时学习笔记

微信公共号 [架构师之路] 上看到一篇文章 10w定时任务，如何高效触发超时，学习了下，一些笔记。

业务需求

APP实时消息通道系统，对每个用户会维护一个 APP 到服务器的 TCP 连接，用来实时收发消息，对这个 TCP 连接，有这样一个需求：
如果连续 30s 没有请求包（例如登录，消息，keepalive 包），服务端就要将这个用户的状态置为离线

轮询扫描法 VS 多 Timer 触发法

方案一轮询扫描法：

用一个 Map<uid, last_packet_time> 来记录每一个 uid 最近一次请求时间 last_packet_time

当某个用户 uid 有请求包来到，实时更新对应的 last_packet_time
启动一个 Timer，当 Map 中不为空时，轮询扫描这个 Map，看每个 uid 的 last_packet_time 是否超过 30s，如果超过则进行超时处理

方案二多Timer触发法：

用一个 Map<uid, last_packet_time> 来记录每一个 uid 最近一次请求时间 last_packet_time

当某个用户 uid 有请求包来到，实时更新对应的 last_packet_time。
并同时对这个 uid 请求包启动一个 Timer，30s 之后触发
当每个 uid 请求包对应的 Timer 触发后，查看对应的 last_packet_time 是否超过 30s，如果超过则进行超时处理

方案一：只启动一个 Timer，但需要轮询，效率较低
方案二：每个请求包要启动一个 Timer，不需要轮询，但比较耗资源

环形队列法

三个重要的数据结构：

30s 超时，就创建一个 index 从 0 到 30 的环形队列（本质是个数组）

环上每一个 slot 是一个任务集合 Set<uid>
同时还有一个 Map<uid, index>，记录 uid 落在环上的哪个 slot 里

环形队列法

同时：

启动一个 Timer，每隔 1s，在上述环形队列中移动一格，0->1->2->3…->29->30->0…

有一个 Current Index 指针来标识刚检测过的 slot

当有某用户 uid 有请求包到达时：

从 Map 结构中，查找出这个 uid 存储在哪一个 slot 里

从这个 slot 的 Set 结构中，删除这个 uid
将 uid 重新加入到新的 slot 中，具体是哪一个 slot 呢? Current Index 指针所指向的上一个 slot，因为这个 slot，会被 Timer 在 30s 之后扫描到
更新 Map，这个 uid 对应 slot 的 index 值

哪些元素会被超时掉呢？
Current Index 每秒种移动一个 slot，这个 slot 对应的 Set<uid> 中所有 uid 都应该被集体超时！
如果最近 30s 有请求包来到，一定被放到 Current Index 的前一个 slot 了，Current Index 所在的 slot 对应 Set 中所有元素，都是最近 30s 没有请求包来到的。
所以，当没有超时时，Current Index 扫到的每一个 slot 的 Set 中应该都没有元素。

优势：

只需要1个 Timer

Timer 每 1s 只需要一次触发，消耗 CPU 很低
批量超时，Current Index 扫到的 slot，Set 中所有元素都应该被超时掉

总结

这个环形队列法是一个通用的方法，Set 和 Map 中可以是任何 task，本文的 uid 是一个最简单的举例。

引用：
10w定时任务，如何高效触发超时