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

谁践踏了优雅 2022-05-19 03:04 118阅读 0赞

**一、缘起**

很多时候，业务有定时任务或者定时超时的需求，当任务量很大时，可能需要维护大量的timer，或者进行低效的扫描。

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

其中，单机TCP同时在线量约在10w级别，keepalive请求包大概30s一次，吞吐量约在3000qps。

**一般来说怎么实现这类需求呢？**

**“轮询扫描法”**

1）用一个Map<uid, last\_packet\_time>来记录每一个uid最近一次请求时间last\_packet\_time

2）当某个用户uid有请求包来到，实时更新这个Map

3）启动一个timer，当Map中不为空时，轮询扫描这个Map，看每个uid的last\_packet\_time是否超过30s，如果超过则进行超时处理

**“多timer****触发法”**

1）用一个Map<uid, last\_packet\_time>来记录每一个uid最近一次请求时间last\_packet\_time

2）当某个用户uid有请求包来到，实时更新这个Map，并同时对这个uid请求包启动一个timer，30s之后触发

3）每个uid请求包对应的timer触发后，看Map中，查看这个uid的last\_packet\_time是否超过30s，如果超过则进行超时处理

**方案一**：只启动一个timer，但需要轮询，效率较低

**方案二**：不需要轮询，但每个请求包要启动一个timer，比较耗资源

特别在同时在线量很大时，很容易CPU100%，**如何高效维护和触发大量的定时/超时任务，是本文要讨论的问题**。

**二、环形队列法**

废话不多说，三个重要的数据结构：

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

2）环上每一个slot是一个**Set<uid>，任务集合**

3）同时还有一个**Map<uid, index>**，记录uid落在环上的哪个slot里

![640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1][]

**同时**：

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

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

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

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

2）从这个slot的Set结构中，删除这个uid

3）将uid重新加入到新的slot中，具体是哪一个slot呢 => Current Index指针所指向的**上一个**slot，因为这个slot，会被timer在30s之后扫描到

（4）更新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）只需要1个timer

（2）timer每1s只需要一次触发，消耗CPU很低

（3）批量超时，Current Index扫到的slot，Set中所有元素都应该被超时掉

**三、总结**

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

**HashedWheelTimer**也是类似的原理，有兴趣的同学可以百度一下这个数据结构，Netty中的一个工具类，希望大家有收获，帮忙转发一下哈。

==【完】==

相关推荐：

[究竟啥才是互联网架构“高可用”][Link 1]

[100亿数据1万属性数据架构设计][100_1]

[数据库秒级平滑扩容架构方案][Link 2]

[58到家数据库30条军规][58_30]

[业界难题-“跨库分页”的四种方案][-]

原文链接:

[https://mp.weixin.qq.com/s?\_\_biz=MjM5ODYxMDA5OQ==&mid=2651959957&idx=1&sn=a82bb7e8203b20b2a0cb5fc95b7936a5&chksm=bd2d07498a5a8e5f9f8e7b5aeaa5bd8585a0ee4bf470956e7fd0a2b36d132eb46553265f4eaf&scene=21\#wechat\_redirect][https_mp.weixin.qq.com_s_biz_MjM5ODYxMDA5OQ_mid_2651959957_idx_1_sn_a82bb7e8203b20b2a0cb5fc95b7936a5_chksm_bd2d07498a5a8e5f9f8e7b5aeaa5bd8585a0ee4bf470956e7fd0a2b36d132eb46553265f4eaf_scene_21_wechat_redirect]

[640_wx_fmt_png_tp_webp_wxfrom_5_wx_lazy_1]: /images/20220519/deb106363adb446bb5d6ef248162075d.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651959728&idx=1&sn=933227840ec8cdc35d3a33ae3fe97ec5&chksm=bd2d046c8a5a8d7a13551124af36bedf68f7a6e31f6f32828678d2adb108b86b7e08c678f22f&scene=21#wechat_redirect
[100_1]: http://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651959855&idx=1&sn=f33abe8ec598c273f29cebb9365ece59&chksm=bd2d07f38a5a8ee58a944507a134e1da1efc3ac9c4d1c4cff261137cd986e51f5fe7cee9de15&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651959883&idx=1&sn=e7df8510c7096a5b069e0f12eaaca010&chksm=bd2d07978a5a8e815c2ae41b16b6b4c579923502fb919008a22bb108a1e920109f25387f8903&scene=21#wechat_redirect
[58_30]: http://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651959906&idx=1&sn=2cbdc66cfb5b53cf4327a1e0d18d9b4a&chksm=bd2d07be8a5a8ea86dc3c04eced3f411ee5ec207f73d317245e1fefea1628feb037ad71531bc&scene=21#wechat_redirect
[-]: http://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651959942&idx=1&sn=e9d3fe111b8a1d44335f798bbb6b9eea&chksm=bd2d075a8a5a8e4cad985b847778aa83056e22931767bb835132c04571b66d5434020fd4147f&scene=21#wechat_redirect
[https_mp.weixin.qq.com_s_biz_MjM5ODYxMDA5OQ_mid_2651959957_idx_1_sn_a82bb7e8203b20b2a0cb5fc95b7936a5_chksm_bd2d07498a5a8e5f9f8e7b5aeaa5bd8585a0ee4bf470956e7fd0a2b36d132eb46553265f4eaf_scene_21_wechat_redirect]: https://mp.weixin.qq.com/s?__biz=MjM5ODYxMDA5OQ==&mid=2651959957&idx=1&sn=a82bb7e8203b20b2a0cb5fc95b7936a5&chksm=bd2d07498a5a8e5f9f8e7b5aeaa5bd8585a0ee4bf470956e7fd0a2b36d132eb46553265f4eaf&scene=21#wechat_redirect