浅探Node中定时模块构造的JS链表
发布于 1 年前 作者 hyj1991 1611 次浏览 来自 分享

I. 定时模块由JS构造的链表概览

Node的核心模块中的linklist模块,使用纯js实现了一个双向循环链表,将插入、删除元素的时间复杂度降低到O(1), 详细代码位于在lib/_linklist.js中,该链表提供了

  1. init函数:初始化
  2. peek函数:获取当前链表首个元素,如果为空,则返回null
  3. shift函数:获取当前链表首个元素,并且删除该首元素
  4. remove函数:移除当前链表的某个元素
  5. append函数:挂载元素到当前链表的尾部
  6. isEmpty函数:判断当前链表是否为空 由于是纯JS实现的一个双向循环链表,所以其具体表现形式与c/c++中实现的稍有不同,具体链表结构图如下所示: alt text

结合上图,我们可以比较直观的得到如下信息:

  1. LIST对象相当于链表的head,其_idleNext属性指向L3(链表尾部的对象元素),其_idlePrev属性指向L1(链表的第一个对象元素)
  2. 链表中间的元素L1和L2的_idleNext属性均指向链表的前一个元素,_idlePrev属性均指向链表的后一个元素
  3. 链表的最后一个元素L3,其_idleNext属性和2中的中间元素一样,指向链表的前一个元素,此处为L2;其_idlePrev属性指向链表的head,此处为LIST。

综合上面的三点信息,一个纯JS构造的双向循环链表已经构造完成,我们从链表中的任意一个节点,都能访问前一个元素和后一个元素。该链表插入和删除节点的操作时间复杂度均为O(1),结合上图来理解这一点的话就相当容易。 比如我们要删除节点L2,只需要如下即可完成:

  1. 将节点L1的_idlePrev属性指向节点L3
  2. 将节点L1的_idlePrev属性指向节点L3

同样的,我们要插入一个节点L4到L2和L3之间,同样只需要:

  1. 将节点L2的_idlePrev属性指向节点L4
  2. 将节点L2的_idlePrev属性指向节点L4
  3. 将节点L4的_idlePrev属性指向节点L3,_idleNext属性指向节点L2

下一节我们结合代码来详细看看这个双向循环链表的具体实现细节。

II. 链表函数详解

本节主要是对上节概览中展示的处理链表的方法,结合源代码和示例图进行解析。 具体见下

init函数

首先是源代码:

function init(list) { 
	list._idleNext = list; 
	list._idlePrev = list; 
}

init函数相当简单,仅仅是对传入的list对象进行初始化,添加了_idleNext和_idlePrev属性,并且指向自身。 需要注意的是,这里的init函数,初始化的其实是链表的head。

peek函数

源码如下:

function peek(list) { 
	if (list._idlePrev == list) return null; 
	return list._idlePrev; 
}

这个函数返回的是链表的第一个对象元素,但是如果该链表为空(即仅有head,由list._idlePrev == list条件进行控制),则返回null 此函数用在循环遍历处理链表元素(并且处理完的元素删除掉)时的退出条件,如:

while(first = peek(list)){ 
	//… 
	//对first元素进行逻辑处理 
	//删除first元素 
	remove(first); 
}

Remove函数

源码:

function remove(item) { 
	//如果当前元素存在_idleNext属性,即存在指向的前一个元素, 
	//则将前一个元素的_idlePrev属性指向当前元素的_idlePrev 
	//其实就是将当前元素的前一个元素的_idlePrev指向了当前元素的后一个元素 
	if (item._idleNext) { 
    	item._idleNext._idlePrev = item._idlePrev; 
	} 
	//同上,将当前元素的后一个元素的_idleNext指向了当前元素的前一个元素 
	if (item._idlePrev) { 
    	item._idlePrev._idleNext = item._idleNext; 
	} 
	//完成上述两个步骤后,链表实质上已经删除了当前元素 
	//此时将当前元素的_idleNext和_idlePrev属相均置为null,方便下一次GC将当前元素GC掉 
	item._idleNext = null; 
	item._idlePrev = null; 
}

具体注释可以见上面的源码处,这个函数主要作用就是将链表中的某一个元素删除,可以看到,由于构造的是双向循环链表,所以链表中任意一个元素均能访问到前/后的元素。 结合第一节中的图,假如我们需要删除L2,仅仅做了两步操作:

  1. 将L1的_idlePrev属性指向L3,将L3的_idlePrev属性指向L1
  2. 将被删除元素L2的_idleNext和_idlePrev属性置为null,以便GC掉

shift函数

源码:

function shift(list) { 
	var first = list._idlePrev; 
	remove(first); 
	return first; 
}

这个函数做了两件事:

  1. 返回了链表的第一个元素
  2. 删除了链表的第一个元素 shift函数和peek函数的区别就是shift函数除了会返回链表的第一个元素,还会删除,用法和Array.shift一致;并且shift函数不会判断链表是否为空。

append函数

源码:

function append(list, item) { 
	//如果需要挂载的元素item在别的链表中存在 
	//则清除item的原始链表关系,即元素A不能同时存在于链表L1和链表L2中 
	remove(item); 
	//以下两步完成了item元素挂载到当前双向链表的过程 
	//将需要挂载的元素item的_idleNext属性指向当前链表的最后一个元素 
	item._idleNext = list._idleNext; 
	//将当前链表的最后一个元素的_idlePrev属性指向挂载的元素
	item list._idleNext._idlePrev = item; 
	//以下两步完成了双向链表的循环构造过程 
	//将挂载元素item的_idlePrev属性指向链表的head 
	item._idlePrev = list; 
	//将链表的head的_idleNext属性指向被挂在的元素item 
	list._idleNext = item; 
}

这个函数主要作用就是将元素挂载到当前的链表上,具体注释见上述源码部分。这里面其实主要分了两部分:

  1. 挂载元素和当前链表最后一个元素的双向连接
  2. 挂载完成后,挂载元素实质上成为了链表的尾部元素,故需要和链表的head同样进行双向连接,完成循环双向链表的构造。

isEmpty函数

源码:

function isEmpty(list) { 
	return list._idleNext === list; 
}

这个函数比较简单,通过链表head的_idleNext属性是否指向自身,来判断当前的链表是否已经为空。 其实这里通过list._idlePrev === list来判断是一样的。

III. 为什么不提供元素查询?

我们可以看到,整个_linklist.js提供的针对链表的操作函数中,都没有看到和查询元素有关的方法,这涉及到链表这种数据结构查询时间复杂度。 链表中的元素由于都仅和前/后元素关联,没有全文索引,所以查询链表中的元素势必要对链表进行遍历,所以其查询元素的事件复杂度为O(n),n为链表长度。这种情况下,如果有大量查询元素的操作,使用链表其实性能是相对低下的。所以由使用场景决定了,链表适合用在有大量插入/删除操作的应用场景中,所以此处就索性不提供查询的函数。

IV. 等等,还少一个插入

链表插入的时间复杂度也是O(1),但是这个核心模块中却没有提供insert方法。这里也是因为该模块的链表基本只提供给timer模块使用,而timer中没有insert的场景。但是理清了这个链表实现的逻辑,我们可以很容易写一个insert方法:

function insert(prevList, nextList, insertList) { 
	remove(insertList); 
	prevList._idlePrev = insertList; 
	nextList._idleNext = insertList; 
	insertList._idlePrev = nextList; 
	insertList._idleNext = prevList; 
}

这个函数将insertList元素插入到prevList和nextList之间。

V. 适用的场景——Timer

在Node中,恰好有一类场景,没有查询,但是却有大量的插入和删除,这就是Timer模块。 几乎所有的网络I/O请求,都会提供timeout操作控制socket的超时状况,这里就会大量使用到setTimeout,并且这些timeout定时器,绝大部分都是用不到的(数据按时正常响应),那么又会有响应的大量clearTimeout操作,这种场景下,就是最契合链表的应用场景。 正是由于timer的大量使用,Node在核心模块Timer中做了大量的性能优化。这里不具体展开,但是可以看下我们上面的纯JS链表在其中的位置:

1. timer_wrap.cc中封装了start/stop方法,对应的调用libuv中的uv_timer_start和uv_timer_stop,并且暴露给 JS一个class Timer。这里是真正的底层定时器超时触发的控制处,uv_timer_start向Event Loop注册了一个timer观察 者,和对应的超时时间以及超时后的回调函数。

2. JS层将所有超时时长一样的定时器放到同一个链表中,这个链表的head就是1中暴露给JS的Timer类的实例。同时将该 链表以mesc为key(超时时长),存储于全局的lists中。

3. Event Loop每一次循环中的uv_run方法中,执行的uv_run_timer判断有定时器超时到达后,执行1中注册的回调 函数OnTimeout,该函数会调用JS层的回调函数listOnTimeout,在这个函数中,由于在C++层面传入了对应Timer的实例, 也就是2中的链表head,所以可以使用peak方法对链表进行遍历,取出链表中每一个元素,执行每一个元素的_onTimeout 回调函数(即由开发者编写的回调函数)。

从上述的流程,我们可以清晰的看到,Node中所有超时时长一样的定时器,在底层共享同一个由libuv封装提供的timer,这个timer也是真正检测和触发超时的定时器。 当这个定时器触发超时后,再回到JS层对这些JS编写的定时器封装成的链表进行统一处理,节省了cpu资源,同时可以得到一个结论,超时时间一样的定时器,遵循先注册先执行回调的原则。

VI. 结语

Node在这里实现的链表,保证了JS层面大量的插入删除定时器时服务器的性能; 并且同样超时时间的定时器映射到底层libuv的同一个uv_timer_start,这样复用+数据结构性能最大化的做法十分值得我们的学习。在详细学习Node的定时器源码之前,确实没想到JS也可以实现链表。本次学习感觉自己收获很大,服务器整体性能的提高正是这种细微的优化累积起来的。阅读学习优秀的源代码,确实能开阔自己的眼界和提升自己的能力。

8 回复

干货,先收藏

干货,先收藏

水平不到看源码程度,看到up主撸的很酸爽,等到猴年马月自己撸到了,再来up主这提问

感觉分分钟上了一节数据结构课- -

@DevinXian 哈哈,其实也没你想的那么复杂,我在看这一块之前,对链表的印象也只有大学数据结构学过的一点 现在工作由于和JS接触比较多,正好在Node中又有这样的实现,就仔细研究了下,其实完全没有当时学的时候感觉的那么复杂~

@hyj1991 链表不算复杂了,涉及到树和图感觉就比较消耗脑筋…

@DevinXian 额,之前看错了

回到顶部