建议大家使用FireFox、Opera、Safri、IE8+等主流浏览器访问本站,否则可能会出现不兼容等问题!

Redis优先级队列的实现方式

Nodejs 凶恶的方块 3105次浏览 已收录 0个评论

前言:

今天有人谈到进程调度,可能要折腾,开脑洞想了想,不管如何都要用到优先级队列,然后自然想到Redis的列表。要想身体好,文档看到老。

前言:

实现优先级队列的方法  1.Sorted-Sets,2.LIST实现。

1.Sorted-Sets实现

科普:

Sorted-Sets和Sets类型极为相似,它们都是字符串的集合,都不允许重复的成员出现在一个Set中。它们之间的主要差别是Sorted-Sets中的每一个成员都会有一个分数(score)与之关联,Redis正是通过分数来为集合中的成员进行从小到大的排序。然而需要额外指出的是,尽管Sorted-Sets中的成员必须是唯一的,但是分数(score)却是可以重复的。
在Sorted-Set中添加、删除或更新一个成员都是非常快速的操作,其时间复杂度为集合中成员数量的对数。由于Sorted-Sets中的成员在集合中的位置是有序的,因此,即便是访问位于集合中部的成员也仍然是非常高效的。事实上,Redis所具有的这一特征在很多其它类型的数据库中是很难实现的,换句话说,在该点上要想达到和Redis同样的高效,在其它数据库中进行建模是非常困难的。

Sorted-Sets命令包含如下(列举实现相关方法)

ZADD KEY_NAME SCORE1 VALUE1.. SCOREN VALUEN2 //添加有序集元素
 ZRANGE key start stop [WITHSCORES] //获取区间范围内的有序值成员(由低到高) -ZREVRANGE(降序)

思路:ZADD dog 0 dogx 1 dogy  2dogz

ZREVRANGE dog 0 -1 WITHSCORES //获取第一个至最后一个的降序有序集合

Zrem dog dogx //移除dogx 返回移除数量

ps:由于上面涉及到的方法是非阻塞模式,所以需要不断轮询(当有序集合为空时),看了大神们的博客采用的是 BLPOP方法来实现的阻塞语意。

BLPOP: 该命令会按照给出的 key 顺序查看 list,并在找到的第一个非空 list 的头部弹出一个元素。

Redis优先级队列的实现方式

首先我们像LIST dog 压入 doge 使用BlPOP后返回了key 和 value 后移除元素。然后LIST dog为空,此时使用BLPOP dog 0 命令,阻塞监听dog。当另一个终端压入dog-newdog后监听结束返回时间&key-value。

此刻,大体思路以已经完成。使用sorted-Sets实现有序队列有序优先级队列,consumer实现:监听有序集,存在按优先级移除元素,返回元素。使用BRPOP阻塞helpLIST。producer实现:压入有序队列,压如helpList实现通知。具体方法:使用eval命令引入lua脚本,或者使用后端传递脚本信息分次调用命令,或者使用事物处理。

2.LIST实现

简单的LIST实现,列表两端分别压如高优先级,低优先级。高优先级总是比低优先级先出,当时相对之间的高优先级直接的出列顺序是不定的。(非常菜鸡)违背了先进先出的原则。

完善:

设置两个队列,一个高优先级一个低优先级队列。高优先级进入高队列,低优先级放在队列。

[low_queue]

[high_queue]

后端consumer采用不断轮询的方式阻塞住(BRPOP),同时读取高低优先级队列。BRPOP 后面跟多个LIST时,会从第一个不为空的LIST移出元素。

下面的例子终端执行:

lpush low_queue low001
lpush high_queue low003
lpush low_queue low003
lpush low_queue low003
lpush high_queue low001
lpush high_queue low004

 

Redis优先级队列的实现方式

由于在nodejs里异步不能使用阻塞操作,用while会导致爆栈(不等回调返回执行下一次轮询,内存直接炸了)。这里用setInterval非阻塞方法来进行监听,可以看到已经达到了FIFO的原则。

至于为什么不会出现while的情况,听尤里卡大神的话说是不是立即执行的,我感觉重点不是这个问题,于是我写了一段程序。

var c=0;
while(c<100){ 
 c++;
var i=0;
while(i<=100000000){
 i++;
 if(i==1){
 console.time('while');
 }
}

console.timeEnd('while');
 }
/*while: 1871.268ms
while: 1805.696ms
while: 1859.965ms
while: 1465.144ms
while: 1936.749ms
while: 1845.596ms
while: 1831.845ms
while: 1867.280ms
*/
//同样阻塞的情况下调用setInterval
setInterval(c,0)

function c() {
 var i=0;
while(i<=1000000000){
 if(i==1){
 console.time('this');
 }
 i++;
}
console.timeEnd('this');
}
/*
setInterval: 768.361ms
setInterval: 699.622ms
setInterval: 549.766ms
setInterval: 722.351ms
setInterval: 722.168ms
setInterval: 489.062ms
*/
//在nodejs核心模块timers.js中存在
 var timer = new Timeout(after);
 callback.call(timer,arguments[]);
//不断绑定timeout,按照参数绑定和触发 C++双向链表,当检测超时会从列表移除
这只能解释内存不炸的问题。时间的问题 = =。 妈的我掰不下去了。。。。

:evil:,希望有能解决的大神,评论区救场谢谢。

后记:

虽然关于setInterval的小插曲问题没有解决,但是还是比较正常的写了,实现Redis优先级队列的问题。

 


方块网络 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明Redis优先级队列的实现方式
喜欢 (0)or分享 (0)
avatar
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址