[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6,"_7":8},"actionData","errors","root",{"_11":-5},"routes/user.$name.replies",{"_9":10,"_11":12,"_13":14,"_15":16,"_17":18,"_19":16},"replies",[35],"user",{"_20":21,"_13":14,"_22":23,"_24":25,"_26":27,"_28":29,"_30":31,"_32":16,"_33":34},"loginname","herodot","page",1,"limit",50,"total","id","6315","avatar_url","http://www.gravatar.com/avatar/ff53fafe7f53f9af3305c2aaf1a65796?size=48","githubUsername","","create_at","2013-01-18 03:16:38.811","score",5,"topic_count",0,"reply_count","is_star",false,{"_20":36,"_37":38,"_39":-5,"_40":41,"_42":43,"_44":45,"_46":47,"_48":34,"_32":49,"_50":51,"_26":52,"_53":54},"71","author_id","135","tab","content","此文主要分析libev 的设计架构与算法实现，阅读这篇文章之前，你需要对libev 的使用有大致的了解;libev 提供了很多watcher 供开发者使用，以下仅对最重要最常用的几个watcher 机制进行分析，从中我们可掌握整个libev的设计思想，如果你想了解更多，可查阅libev的相关代码或文档。\r\n
\r\n
ev_io_watcher\r\n
\r\n
如我们所知，新的fd总是系统可用的最小fd ，所以这个长度可以进行大小限制的，我们用一个连续的数组来存储fd/watch 信息，如下图所示，我们用anfd[fd] 就可以找到对应的fd/watcher 信息，当然可能遇到anfd超出我们的buffer长度情形，这是我们用类似relloc 的函数来做数组迁移、扩大容量，但这种概率是很小的，所以其对系统性能的影响可以忽略不计（这种分配技巧不局限于io watcher，其他的数组也会用到这个技巧）\r\n
$\"\"$ \r\n
\r\n
我们用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维数组，此时仅考虑普通模式)\r\n

\r\n
\r\n
所以我们可以看到，这个操作是非常非常快。\r\n
\r\n
$\"\"$ 再看添加 watch 的场景，把watch 插入到相应的链表中，这个操作也是直接定位，然后在fdchange队列中，加入对应的fd（如果这个fd已经被添加过，则不会发生这一步，我们通过anfd[fd] 中一个boll 值来判断）\r\n
\r\n
$\"\"$ \r\n
\r\n
注意，假如我们在某个fd 上已经有个 watch 注册了 read 事件，这时我们又再添加一个watch，还是read 事件，但是不同的回调函数，在此种情况下，我们不应该调用epoll_ctrl 之类的系统调用，因为我们的events 集合是没有改变的，所以为了达到这个目的anfd[fd] 结构体中，还有一个events事件，它是原先的所有watcher 的事件的 ”|“ 操作，向系统的epoll 从新添加描述符的操作是在下次事件迭代开始前进行的，当我们依次扫描fdchangs，找到对应的anfd 结构，如果发现先前的events 与当前所有的watcher 的”|“ 操作结果不等，则表示我们需要调用epoll_ctrl 之类的函数来进行更改，反之不做操作\r\n
\r\n
即，作为一条原则，在调用系统调用前，我们已经做了充分的检查，确保不进行多余的系统调用！\r\n
\r\n
再来看删除/更新一个watcher 造作，基于以上分析，这个操作也是近乎O(1) 的，当然，如果events事件更改，可能会发生一次系统调用。\r\n
\r\n
所以我们对io watcher 的操作，在我们的用户层面上，几乎总是是O（1）的复杂度，当然如果牵涉到epoll 文件结构的更新，我们的系统调用 epoll_ctrl 在内核中还是 O （lgn）的复杂度，但我们已经在我们所能掌控的范围内做到最好了！\r\n
\r\n
ev_timer \r\n
\r\n
在libev 中所有的ev_timer 被放到一个2-heap 或 4-heap 结构中，此时我们仅考虑2-heap 的场景\r\n
\r\n
$\"\"$ \r\n
这个heap结构式存储在数组中的（可以参看静态二叉树、最小堆等概念）\r\n
对任一节点，其父节点的位置为 floor(k/2) , 任一节点的子节点位置为 2*k 和 2*k + 1,\r\n
\r\n
它是一个最小堆，权值为 ”即将触发的时刻“，所以其根节点总是最近要触发的timer！\r\n
\r\n
对此堆有两个基本操作： upheap/downheap (没用到floyd 堆调整)\r\n
当对某一节点就行upheap 时，就是与其父节点进行比较，如果其值比父节点小，则交换，然后在对这个父节点重复upheap …\r\n
downheap 时，与其两个子节点比较（也可能一个）,如果两个子节点中有一个是小于当前节点的权，则交换并重复以上操作，如果两个子节点都小于当前节点的权，则选择最小的那个交换并重复，如果2个子节点都大于等于当前的权，当然不用做任何操作了。\r\n
\r\n
当我们更新一个timer的时，由以上调整算法可知，其复杂责度为 O(lgn)\r\n
\r\n
当我们添加一个timer时，我们直接在数组末尾位置添加，然后执行upheap 操作，其复杂度也是O(lgn)\r\n
\r\n
当我们删除任一节点时（出堆，即取走根节点是这种情形的一种特例），我们采用以下方法：\r\n
\r\n
$\"\"$ \r\n
\r\n
用最后一个timer替换待删除的timer ，然后对那个新交换的timer进行堆调整，同时timer_cnt减一，所以当一次事件循环中，我们用当前时间与根节点时间比较，超时则加入到待处理队列中，然后进行堆调整，再次与根节点比较... 所以其负责度为 k x O(lgn) ，k 为超时的timer数组，n为总得timer数目.\r\n
\r\n
基于以上操作，我们保证了二叉树的平衡性，对timer 的添加、删除、更新操作都是O(lgn) 复杂度（实际上，在nodejs层面，还实现了一个更高效的机制，可以做到O(1) 复杂度，此为后话...）\r\n
\r\n
async_watcher & signal watcher\r\n
\r\n
在libev 中，虽然支持多个事件循环，但一般我们用默认事件循环就足够了，在一个事件循环中，只有一个阻塞的轮询，即要么selelct，要么poll，要么kequeue ,epoll 等，libev 库会按照以下方式优先级进行检测、选择：\r\n
IOCP > PORT > KQUEUE > EPOLL > POLL > SELECT\r\n
\r\n
在linux 下当然会选择epoll ，但epoll 还是存在一些问题的，比如 ”伪信号“ 的处理，即返回的事件其实不是当前句柄的事件，libev 中用一个随机值伴随fd传入epoll结构中，当epoll_wait 事件返回时，我们拿 anfd[fd] 中的这个随机值与返回的值进行比较，如果不一致则忽略（ nginx 也是采用类似的机制进行处理的）\r\n
\r\n
async_watcher 通常作为辅助类使用，一般使用数量会比较少，signal 信号我们用到的更是只有那么几个而已，他们都是依托于pipe 机制来实现的(linux 2.6.22+ 上会使用eventfd)\r\n
\r\n
$\"\"$ \r\n
如上图所示，创建一对管道，pipe_r 作为一个io watcher 加入到监控集合中，当我们想要激活一个async 时，我们把watcher 的 sent 置为 \"1\" 表示为待处理事件，同时向pipe_w 写入数据，想象以下，在一次事件循环中，可能有多个watcher 被激活，假如每次都写一次pipe，显然是不必要的，所以我们用async_pending 这个flag来标记是否已经向pipe_w 写入数据。\r\n
\r\n
所以，当下次事件循环开始时，pipe_r 会随着epoll_wait 返回，在pipe_r 的回调函数中，会对async watcher 数组进行检查，如果发现 sent 这个flag 为1 ，则加入到待处理队列中去！\r\n
\r\n
prepare & check watcher\r\n
\r\n
这两类watcher 分别会在事件轮询前和轮循后发生，它们和async watcher 一样，通常充当一些辅助性的角色，比如nodejs 中用它们来进行 nextTick 函数的回调、v8的gc collection 监测等，因为libev 的事件轮询机制为：直到没有活动的、可供监测的watcher ，事件循环就不会退出，所以以pipe_r 这个watcher 为例，它仅仅是个辅助性的东西，所以当只有它一个是活着的时候，事件循环应该认为：没有实质性的watcher了，可以退出进程了，为了达到这个目的，这类辅助性的watcher 通常都会在ev_start_async 等函数之后调用\r\n
\r\n

\r\n

ev_unref (EV_P)\r\n
{\r\n
   --activecnt;\r\n
}

\r\n
来对此全局变量减一，这样就不会影响事件循环的正常退出\r\n
\r\n
idle watcher\r\n
\r\n
也是一个很有用的辅助类，它表示程序当前是空闲的，我们可以启用一个idle watcher 来做一些事情，比如进行 v8 的垃圾回收，v8 是 stop the world 停车检查回收机制，所以我们尽量选择空闲事件进行垃圾回收，再比如，某一次事件循环中，我们的异步文件请求回调太多了，我们可以只执行一部分，然后启动一个idle watcher ，在适当的时候接着执行...\r\n
\r\n
小节：\r\n
在高性能的服务器设计中，甚至可以说事件库决定了系统的整体性能，libev 饱受赞誉，除了上述所列，他还支持其他的一些watcher，同时支持一些复杂的功能，如优先级事件排队，绝对事件定时器 periodic ,多个事件循环、事件循环的嵌套、支持安全的进程fork..., 支持多个系统的底层操作, 所有这些，都让代码变得晦涩复杂，作者本人对此也表示无奈，称已尽量考虑到代码的可读性, 不过从我们以上分析来看，它的的设计思想和算法优化臻于郅治，不可多得，实至名归...\r\n
\r\n

","title","libev 设计分析","last_reply_at","2013-01-18 03:46:06.602","good",true,"top",4,"visit_count",49060,"2011-09-09 11:20:56","author",{"_13":55,"_22":56},"windyrobin","http://www.gravatar.com/avatar/e9e2e24aa3ed291923d223924ec694ba?s=48"]