如何高效触发超时

2018-04-17 11:46 By "Powerless" 2789 0 1

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

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

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

【一】轮询扫描法

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

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

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

【二】多timer触发法

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

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

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

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

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

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

【三】环形队列法

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

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

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

同时：

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中应该都没有元素。

【四】总结

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

HashedWheelTimer也是类似的原理，有兴趣的同学可以谷歌一下这个数据结构，Netty中的一个工具类，希望大家有收获。

邮箱

验证码

邮件验证码

获取邮箱验证码