[架构师之路]10w定时任务，如何高效触发超时 2017-03-09

时间：2021-12-23 21:51:25
本系列转载自 【架构师之路】公众号 By 58沈剑。
沈老师擅长用简单的文字把常见原理讲的很透彻，推荐。


一、缘起
很多时候，业务有定时任务或者定时超时的需求，当任务量很大时，可能需要维护大量的timer，或者进行低效的扫描。
 
例如：58到家APP实时消息通道系统，对每个用户会维护一个APP到服务器的TCP连接，用来实时收发消息，对这个TCP连接，有这样一个需求：“如果连续30s没有请求包（例如登录，消息，keepalive包），服务端就要将这个用户的状态置为离线”。
 
其中，单机TCP同时在线量约在10w级别，keepalive请求包大概30s一次，吞吐量约在3000qps。
 
一般来说怎么实现这类需求呢？
  • “轮询扫描法”
1）用一个Map来记录每一个uid最近一次请求时间last_packet_time
2）当某个用户uid有请求包来到，实时更新这个Map
3）启动一个timer，当Map中不为空时，轮询扫描这个Map，看每个uid的last_packet_time是否超过30s，如果超过则进行超时处理
 
  • “多timer触发法”
1）用一个Map来记录每一个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，任务集合
    3）同时还有一个Map，记录uid落在环上的哪个slot里
[架构师之路]10w定时任务，如何高效触发超时 2017-03-09
 同时：
     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都应该被集体超时！如果最近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（ https://segmentfault.com/a/1190000010987765 ）也是类似的原理，有兴趣的同学可以百度一下这个数据结构，Netty中的一个工具类，希望大家有收获，帮忙转发一下哈。 


补：
    Netty中增加了要给round的概念，这样可以实现任意时间之后开始。
[架构师之路]10w定时任务，如何高效触发超时 2017-03-09
    以上图为例，假设一个格子是1秒，则整个wheel能表示的时间段为8s，假如当前指针指向2，此时需要调度一个3s后执行的任务，显然应该加入到(2+3=5)的方格中，指针再走3次就可以执行了；如果任务要在10s后执行，应该等指针走完一个round零2格再执行，因此应放入4，同时将round（1）保存到任务中。检查到期任务时应当只执行round为0的。每次执行之后，格子上其他任务的round应减1。
效率
  • 添加任务：O(1)
  • 删除/取消任务：O(1)
  • 过期/执行任务：最差情况为O(n)->也就是当HashMap里面的元素全部hash冲突，退化为一条链表的情况。平均O(1)

标签：

相关文章