微信公共号 [架构师之路] 上看到一篇文章 10w定时任务，如何高效触发超时，学习了下，一些笔记。
关于 Java 定时任务，参见 Java 定时任务 & 任务调度。
业务需求
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定时任务，如何高效触发超时
