libev 设计分析
发布于 3年前 作者 windyrobin 18185 次浏览

此文主要分析libev 的设计架构与算法实现,阅读这篇文章之前,你需要对libev 的使用有大致的了解;libev 提供了很多watcher 供开发者使用 ,以下仅对最重要最常用的几个watcher 机制进行分析,从中我们可掌握整个libev的设计思想,如果你想了解更多,可查阅libev的相关代码或文档。

ev_io_watcher

如我们所知,新的fd总是系统可用的最小fd ,所以这个长度可以进行大小限制的,我们用一个连续的数组来存储fd/watch 信息,如下图所示,我们用anfd[fd] 就可以找到对应的fd/watcher 信息,当然可能遇到anfd超出我们的buffer长度情形,这是我们用类似relloc 的函数来做数组迁移、扩大容量,但这种概率是很小的,所以其对系统性能的影响可以忽略不计(这种分配技巧不局限于io watcher,其他的数组也会用到这个技巧 )


我们用anfd[fd] 找到的结构体中,有一个指向 io watch list 的 头指针,以epoll 为例,当epoll_wait 返回一个fd_event 时 ,我们就可以直接定位到对应fd 的 watch list ,这个watch list 的长度一般不会超过3 ,fd_event 会有一个导致触发的事件 ,我们用这个事件依次和各个watch 注册的 event 做 “&” 操作, 如果不为0 ,则把对应的watch 加入到 待处理队列pendings中(当我们启用watcher 优先级模式时,pendings 是个2维数组,此时仅考虑普通模式)



所以我们可以看到,这个操作是非常非常快。

再看添加 watch 的 场景,把watch 插入到相应的链表中,这个操作也是直接定位,然后在fdchange队列中 ,加入对应的fd(如果这个fd已经被添加过,则不会发生这一步,我们通过anfd[fd] 中一个boll 值来判断)



注意,假如我们在某个fd 上已经有个 watch 注册 了 read 事件,这时我们又再添加一个watch,还是read 事件,但是不同的回调函数,在此种情况下,我们不应该调用epoll_ctrl 之类的系统调用,因为我们的events 集合是没有改变的,所以为了达到这个目的anfd[fd] 结构体中,还有一个events事件,它是原先的所有watcher 的事件的 ”|“ 操作,向系统的epoll 从新添加描述符的操作 是在下次事件迭代开始前进行的,当我们依次扫描fdchangs,找到对应的anfd 结构,如果发现先前的events 与 当前所有的watcher 的”|“ 操作结果不等,则表示我们需要调用epoll_ctrl 之类的函数来进行更改,反之不做操作

即,作为一条原则,在调用系统调用前,我们已经做了充分的检查,确保不进行多余的系统调用!

再来看删除/更新 一个watcher 造作,基于以上分析,这个操作也是近乎O(1) 的,当然,如果events事件更改,可能会发生一次系统调用。

所以我们对io watcher 的操作,在我们的用户层面上,几乎总是是O(1)的复杂度,当然如果牵涉到epoll 文件结构的更新,我们的系统调用 epoll_ctrl 在内核中还是 O (lgn)的复杂度 ,但我们已经在我们所能掌控的范围内做到最好了!

ev_timer  

在libev 中所有的ev_timer 被放到一个2-heap 或 4-heap 结构中,此时我们仅考虑2-heap 的场景


这个heap结构式存储在数组中的(可以参看静态二叉树、最小堆等概念)
对任一节点,其父节点的位置 为  floor(k/2) , 任一节点的子节点位置为  2k 和 2k + 1,

它是一个最小堆,权值为 ”即将触发的时刻“,所以其根节点总是最近要触发的timer!

对此堆有两个基本操作 : upheap/downheap (没用到floyd 堆调整)
当对某一节点就行upheap 时,就是与其父节点进行比较,如果其值比父节点小,则交换,然后在对这个父节点重复upheap …
downheap 时,与其两个子节点比较(也可能一个),如果两个子节点中有一个是小于当前节点的权,则交换并重复以上操作,如果两个子节点都小于当前节点的权,则选择最小的那个交换并重复,如果2个子节点都大于等于当前的权,当然不用做任何操作了 。

当我们更新一个timer的时,由以上调整算法可知,其复杂责度为 O(lgn)

当我们添加一个timer时,我们直接在数组末尾位置添加,然后执行upheap 操作,其复杂度也是O(lgn)

当我们删除任一节点时(出堆,即取走根节点是这种情形的一种特例),我们采用以下方法:



用最后一个timer替换待删除的timer ,然后对那个新交换的timer进行堆调整,同时timer_cnt减一,所以当一次事件循环中,我们用当前时间与根节点时间比较,超时则加入到待处理队列中,然后进行堆调整,再次与根节点比较… 所以其负责度为 k x O(lgn) ,k 为超时的timer数组,n为总得timer数目.

基于以上操作,我们保证了二叉树的平衡性,对timer 的添加、删除、更新操作都是O(lgn) 复杂度(实际上,在nodejs层面,还实现了一个更高效的机制,可以做到O(1) 复杂度,此为后话…)

async_watcher & signal watcher

在libev 中,虽然支持多个事件循环,但一般我们用默认事件循环就足够了,在一个事件循环中,只有一个阻塞的轮询,即要么selelct,要么poll,要么kequeue ,epoll 等 ,libev 库会按照以下方式优先级进行检测、选择 :
IOCP > PORT > KQUEUE > EPOLL > POLL > SELECT

在linux 下当然会选择epoll ,但epoll 还是存在一些问题的,比如  ”伪信号“ 的处理,即返回的事件其实不是当前句柄的事件,libev 中用一个随机值伴随fd传入epoll结构中,当epoll_wait 事件返回时,我们拿 anfd[fd] 中的这个随机值与返回的值进行比较,如果不一致则忽略 ( nginx 也是采用类似的机制进行处理的)

async_watcher 通常作为辅助类使用,一般使用数量会比较少,signal 信号我们用到的更是只有那么几个而已,他们都是依托于pipe 机制来实现的(linux 2.6.22+ 上会使用eventfd)


如上图所示,创建一对管道,pipe_r 作为一个io watcher 加入到监控集合中,当我们想要激活一个async 时,我们把watcher 的 sent 置为 “1” 表示为待处理事件,同时向pipe_w 写入数据,想象以下,在一次事件循环中,可能有多个watcher 被激活,假如每次都写一次pipe,显然是不必要的,所以我们用async_pending 这个flag来标记是否已经向pipe_w 写入数据。

所以,当下次事件循环开始时,pipe_r 会随着epoll_wait 返回,在pipe_r 的回调函数中,会对async watcher 数组进行检查,如果发现 sent 这个flag 为1 ,则加入到待处理队列中去!

prepare & check watcher

这两类watcher 分别会在事件轮询前和轮循后发生,它们和async watcher 一样,通常充当一些辅助性的角色,比如nodejs 中用它们来进行 nextTick 函数的回调、v8的gc collection 监测等,因为libev 的事件轮询机制为:直到没有活动的、可供监测的watcher ,事件循环就不会退出,所以以pipe_r 这个watcher 为例,它仅仅是个辅助性的东西,所以当只有它一个是活着的时候,事件循环应该认为:没有实质性的watcher了,可以退出进程了,为了达到这个目的,这类辅助性的watcher 通常都会在ev_start_async 等函数之后调用



ev_unref (EV_P)

{
--activecnt;
}

来对此全局变量减一,这样就不会影响事件循环的正常退出

idle watcher

也是一个很有用的辅助类,它表示程序当前是空闲的,我们可以启用一个idle watcher 来做一些事情,比如 进行 v8 的垃圾回收 ,v8 是 stop the world 停车检查回收机制,所以我们尽量选择空闲事件进行垃圾回收,再比如,某一次事件循环中,我们的异步文件请求回调太多了,我们可以只执行一部分,然后启动一个idle watcher ,在适当的时候接着执行…

小节:
在高性能的服务器设计中 ,甚至可以说事件库决定了系统的整体性能,libev 饱受赞誉,除了上述所列,他还支持其他的一些watcher,同时支持一些复杂的功能,如优先级事件排队,绝对事件定时器 periodic ,多个事件循环、事件循环的嵌套、支持安全的进程fork…, 支持多个系统的底层操作, 所有这些,都让代码变得晦涩复杂,作者本人对此也表示无奈,称已尽量考虑到代码的可读性, 不过从我们以上分析来看 , 它的的设计思想和算法优化臻于郅治,不可多得,实至名归…

4 回复

图像看不到,从google doc引用的图片好像不能直接外连啊

图片问题已解决,不同IP 区段,docs 可访问性不一样…

@爱多 老兄的文章每次都很深入呀。不错,看着过瘾。为以后优化node.js开发提供了很好的基础。求老兄QQ

好文章,谢谢分享 正在看 libevent , 正好可参照对比 libev

另,“臻于郅治”这个成语,此处不合适

回到顶部