博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
管理大量定时任务,如果高效触发超时?
阅读量:5859 次
发布时间:2019-06-19

本文共 2134 字,大约阅读时间需要 7 分钟。

1. 背景

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

例如:对每个用户会维护一个APP到服务器的TCP连接,用来实时收发信息,对这个TCP连接,如果连续30s没有请求包,服务端就要将这个连接断开。

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

2. 一般思路

2.1 轮询扫描法

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

(2)当某个用户uid有请求包来到,实时更新这个Map;

(3)启动一个timer,当Map中不为空时,轮询扫描这个Map,检查每个uid的last_packet_time是否超过30s,如果超过则进行超时处理

2.2 多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触发法:不需要轮询,但每个请求包要启动一个timer,比较耗资源

特别在同时在线量很大时,很容易CPU100%。

3. 环形队列法

三个数据结构:

(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是一个最简单的举例。

4. Netty - HashedWheelTimer

George Varghese 和 Tony Lauck 1996 年的论文:提出了一种定时轮的方式来管理和维护大量的Timer调度算法.Linux 内核中的定时器采用的就是这个方案。

4.1 原理

一个Hash Wheel Timer是一个环形结构,可以想象成时钟,分为很多格子,一个格子代表一段时间(越短Timer精度越高),并用一个List保存在该格子上到期的所有任务,同时一个指针随着时间流逝一格一格转动,并执行对应List中所有到期的任务,任务通过取模决定应该放入哪个格子。

环形结构可以根据超时时间的hash值(这个hash值实际上就是ticks&mask)将task分布到不同的槽位中,当tick到那个槽位时,只需要遍历那个槽位的task即可知道哪些任务会超时(而使用线性结构,你每次tick都需要遍历所有task)。所以,我们任务量大的时候,相应的增加wheel的ticksPerWheel值,可以减少tick时遍历任务的个数。

以上图为例,假设一个格子是1秒,则整个wheel能表示的时间段为8s,假如当前指针指向2,此时需要调度一个3s后执行的任务,显然应该加入到(2 + 3 = 5)的方格中,指针再走3次就可以执行了;如果任务要在10s后执行,应该等指针走完一个round零2格再执行,因此应该放入4,同时将round(1)保存到任务中。检查到期任务时应当只执行round为0的,格子上其他任务的round应减1。

效率:

(1)添加任务:O(1)

(2)删除/取消任务:O(1)

(3)过期/执行任务:最差情况为O(n),也就是当HashMap里面的元素全部hash冲突,退化为一条链表的情况。平均O(1)

槽位越多,每个槽位上的链表就越短,这里需要权衡时间与空间。

转载于:https://www.cnblogs.com/lujiango/p/9378669.html

你可能感兴趣的文章
UITableview中cell重用引起的内容重复的问题
查看>>
stm32 ADC使用 单通道 多通道
查看>>
Windows7操作系统安装教程(图文)
查看>>
IOS Core Animation Advanced Techniques的学习笔记(三)
查看>>
除了模拟手术教学,VR在医疗领域如何应用?
查看>>
盘点5款Ubuntu监控工具解决CPU暴增问题
查看>>
java 测试IP
查看>>
用CSS做导航菜单的4个理由
查看>>
NOIP2015 运输计划 二分答案+Tarjan LCA+树上差分
查看>>
构建之法读后感
查看>>
基本信息项目目标文档
查看>>
移动开发Html 5前端性能优化指南
查看>>
UGUI 分页渐变居中效果
查看>>
silverlight style和template 使用之tip
查看>>
Eclipse配置python环境
查看>>
第十二周总结
查看>>
Import declarations are not supported by current JavaScript version--JavaScript版本不支持导入声明...
查看>>
js兼容性大全
查看>>
晶振不起振的原因及其解决方法
查看>>
学习目标
查看>>