和架构师》 IBM PowerAI人工智能马拉

定时任务高效触发

标签：算法定时任务高效触发 JavaScript js定时2017-06-04 15:44 151人阅读评论(0)收藏举报本文章已收录于：

分类： JavaScript设计模式及算法（12）

作者同类文章X

目录(?)[+]

圆通处事，方能达到目的!

开发中我们经常会遇到一些需要定时来解决的业务场景。比如，有这样一个需求：“如果连续30s没有请求包（例如登录，消息，keepalive包），服务端就要将这个用户的状态置为离线”。

轮询处理

将所有任务都添加到某集合中，定时轮询扫描，如果达到条件则进行相关处理；

let map = new Map();
function doAction(uid) {
    map.set(uid, new Date().getTime());
}

setInterval(function(){
for(let uid of map.keys()) {
if(+new Date() - map.get(uid) > 30000) {
            map.delete(uid);
            console.log(`${uid}超过30s未做任何操作，设置为离线！`);
        }
    }
}, 10000);

方案的不足：

效率低下。已经被执行过记录，仍然会被扫描（只是不会出现在结果集中），存在大量的重复计算；
时效性差。时间误差取决于轮询的间隔；如果间隔过小，重复被扫描的次数更高，效率会变得更低下。

定时处理

每来一个任务，启动一个定时器，达到定时器时间，执行相关处理；

function doAction(uid) {
    map.set(uid, new Date().getTime());
    setTimeout(function() {
        console.log(`${uid}超过30s未做任何操作，设置为离线！`);
    }, 30000);
}

方案的不足：

定时数过多，导致内存使用率过高，容易导致崩溃。

环形队列处理

数据结构：

环形队列ListLoop，例如可以创建一个包含0-30的slot**环形队列**（本质是个数组）；
每个环上的任务集合Slot，环上每一个slot是一个Set；
记录每个Task对应落到Slot的Map集合；

执行过程：
第一步：启动一个timer，每隔1s，在上述环形队列中移动一格，0->1->2->3…->29->30->0…有一个CurrentSlotIndex指针来标识刚检测过的slot ；
第二步：当有某用户uid有请求包到达时，从Map结构中，查找出这个uid存储在哪一个slot里；
第三步：如果存在，从这个slot的Set结构中，删除这个uid，否则跳过该步骤；
第四步：将uid重新加入到新的slot中（CurrentSlotIndex指针所指向的上一个slot）因为这个slot，会被timer在30s之后扫描到
第五步：更新Map，重新设置该uid对应slot的index值

定时任务高效触发

// new Array(31).fill(new Set())
// No，数组中所有Set集合为同一个

let listLoop = new Array(31),
    map = new Map(),  // 记录每个uid的slotIndex
    currentSlotIndex = 1; // 当前要检测的slot

function doAction(uid) {
// 如果循环队列中已存在该uid，需要先干掉，重新计时
let slotIndex = map.get(uid);
    slotIndex && listLoop[slotIndex].delete(uid);
// 将该uid重现添加到循环队列中
// 周期31，新插入的置入当前的后一个（即，30s后可以扫描到它）
// 更新map中这个uid的最新slotIndex
    slotIndex = currentSlotIndex - 1;
    listLoop[slotIndex] = listLoop[slotIndex] ? 
        listLoop[slotIndex].add(uid) : new Set().add(uid);
    map.set(uid, slotIndex);
}

// 每秒钟移动一个slot，这个slot对应的set集合中所有uid都为超时
// 如果所有slot对应的set集合都为空，则表示没有uid超时
setInterval(function() {
var slotSet = listLoop[currentSlotIndex];
if(slotSet && slotSet.size > 0) {
for(let uid of slotSet.values()) {
// 执行完的uid从map集合中剔除
            map.delete(uid);
            console.log(`<${uid}>超过30s未做任何操作，设置为离线！`);
        }
// 置空该集合
        slotSet.clear();
    }
// 指标继续+1
    currentSlotIndex = (++currentSlotIndex) % 31;
}, 1000);

// 思路、注意Map集合的内心移除情况。

方案的优点：

无需再轮询全部订单，效率高
无重复执行，一个订单，任务只执行一次
效性好，精确到秒（控制timer移动频率可以控制精度）

参照文章：10w定时任务，如何高效触发超时、1分钟实现“延迟消息”功能

举一反三

上述展示描述了一种业务场景，通过环形队列的方式我们还可以处理很多类似场景。

某打车软件订单完成后，如果用户一直不评价，48小时后会将自动评价为5星；
某数据产品用户修改设置，1小时后生效；
…

秒客网

定时任务高效触发

定时任务高效触发

轮询处理

定时处理

环形队列处理

举一反三

相关文章