Node.js打造实时多人游戏框架

Node.js 中的 BUG

[js] view plaincopy

1. while (r != 0 && loop->stop_flag == 0) {  
2.     /* 更新全局时间 */  
3.     uv_update_time(loop);  
4.     /* 检查计时器是否到期，并执行对应计时器回调 */  
5.     uv_process_timers(loop);  
6.   
7.     /* Call idle callbacks if nothing to do. */  
8.     if (loop->pending_reqs_tail == NULL &&  
9.         loop->endgame_handles == NULL) {  
10.       /* 防止event loop退出 */  
11.       uv_idle_invoke(loop);  
12.     }  
13.   
14.     uv_process_reqs(loop);  
15.     uv_process_endgames(loop);  
16.   
17.     uv_prepare_invoke(loop);  
18.   
19.     /* 收集 IO 事件 */  
20.     (*poll)(loop, loop->idle_handles == NULL &&  
21.                   loop->pending_reqs_tail == NULL &&  
22.                   loop->endgame_handles == NULL &&  
23.                   !loop->stop_flag &&  
24.                   (loop->active_handles > 0 ||  
25.                    !ngx_queue_empty(&loop->active_reqs)) &&  
26.                   !(mode & UV_RUN_NOWAIT));  
27.     /* setImmediate() 等 */  
28.     uv_check_invoke(loop);  
29.     r = uv__loop_alive(loop);  
30.     if (mode & (UV_RUN_ONCE | UV_RUN_NOWAIT))  
31.       break;  
32.   }  

[js] view plaincopy

1. void uv_update_time(uv_loop_t* loop) {  
2.   /* 获取当前系统时间 */  
3.   DWORD ticks = GetTickCount();  
4.   
5.   /* The assumption is made that LARGE_INTEGER.QuadPart has the same type */  
6.   /* loop->time, which happens to be. Is there any way to assert this? */  
7.   LARGE_INTEGER* time = (LARGE_INTEGER*) &loop->time;  
8.   
9.   /* If the timer has wrapped, add 1 to it's high-order dword. */  
10.   /* uv_poll must make sure that the timer can never overflow more than */  
11.   /* once between two subsequent uv_update_time calls. */  
12.   if (ticks < time->LowPart) {  
13.     time->HighPart += 1;  
14.   }  
15.   time->LowPart = ticks;  
16. }  

该函数的内部实现，使用了 Windows 的 GetTickCount() 函数来设置当前时间。简单地来说，在调用setTimeout 函数之后，经过一系列的挣扎，内部的 timer->due 会被设置为当前 loop 的时间 + timeout。在 event loop 中，先通过 uv_update_time 更新当前 loop 的时间，然后在uv_process_timers 中检查是否有计时器到期，如果有就进入 JavaScript 的世界。通篇读下来，event loop大概是这样一个流程：

1. 更新全局时间
2. 检查定时器，如果有定时器过期，执行回调
3. 检查 reqs 队列，执行正在等待的请求
4. 进入 poll 函数，收集 IO 事件，如果有 IO 事件到来，将相应的处理函数添加到 reqs 队列中，以便在下一次 event loop 中执行。在 poll 函数内部，调用了一个系统方法来收集 IO 事件。这个方法会使得进程阻塞，直到有 IO 事件到来或者到达设定好的超时时间。调用这个方法时，超时时间设定为最近的一个 timer 到期的时间。意思就是阻塞收集 IO 事件，最大阻塞时间为 下一个 timer 的到底时间。

Windows下 poll 函数之一的源码：

[js] view plaincopy

1. static void uv_poll(uv_loop_t* loop, int block) {  
2.   DWORD bytes, timeout;  
3.   ULONG_PTR key;  
4.   OVERLAPPED* overlapped;  
5.   uv_req_t* req;  
6.   
7.   if (block) {  
8.     /* 取出最近的一个计时器的过期时间 */  
9.     timeout = uv_get_poll_timeout(loop);  
10.   } else {  
11.     timeout = 0;  
12.   }  
13.   
14.   GetQueuedCompletionStatus(loop->iocp,  
15.                             &bytes,  
16.                             &key,  
17.                             &overlapped,  
18.                             /* 最多阻塞到下个计时器到期 */  
19.                             timeout);  
20.   
21.   if (overlapped) {  
22.     /* Package was dequeued */  
23.     req = uv_overlapped_to_req(overlapped);  
24.     /* 把 IO 事件插入队列里 */  
25.     uv_insert_pending_req(loop, req);  
26.   } else if (GetLastError() != WAIT_TIMEOUT) {  
27.     /* Serious error */  
28.     uv_fatal_error(GetLastError(), "GetQueuedCompletionStatus");  
29.   }  
30. }  

按照上述步骤，假设我们设置了一个 timeout = 1ms 的计时器，poll 函数会最多阻塞 1ms 之后恢复（如果期间没有任何 IO 事件）。在继续进入 event loop 循环的时候， uv_update_time 就会更新时间，然后uv_process_timers 发现我们的计时器到期，执行回调。所以初步的分析是，要么是uv_update_time 出了问题（没有正确地更新当前时间），要么是 poll 函数等待 1ms 之后恢复，这个 1ms 的等待出了问题。

查阅 MSDN，我们惊人地发现对 GetTickCount 函数的描述：

The resolution of the GetTickCount function is limited to the resolution of the system timer, which is typically in the range of 10 milliseconds to 16 milliseconds.

GetTickCount 的精度是如此的粗糙！假设 poll 函数正确地阻塞了 1ms 的时间，然而下一次执行uv_update_time 的时候并没有正确地更新当前 loop 的时间！所以我们的定时器没有被判定为过期，于是 poll 又等待了 1ms，又进入了下一次 event loop。直到终于 GetTickCount 正确地更新了（所谓15.625ms更新一次），loop 的当前时间被更新，我们的计时器才在 uv_process_timers 里被判定过期。

向 WebKit 求助

Node.js 的这段源码看得人很无助：他使用了一个精度低下的时间函数，而且没有做任何处理。不过我们立刻想到了既然我们使用 Node-WebKit，那么除了 Node.js 的 setTimeout，我们还有 Chromium 的 setTimeout。写一段测试代码，用我们的浏览器或者 Node-WebKit 跑一下：http://marks.lrednight.com/test.html#1 (#后面跟的数字表示需要测定的间隔)，结果如下图：

按照 HTML5 的规范，理论结果应该是前5次结果是1ms，以后的结果是4ms。测试用例中显示的结果是从第3次开始的，也就是说表上的数据理论上应该是前3次都是1ms，之后的结果都是4ms。结果有一定的误差，而且根据规定，我们能拿到的最小的理论结果是4ms。虽然我们不满足，但显然这比 node.js 的结果让我们满意多了。强大的好奇心趋势我们看看 Chromium 的源码，看看他是如何实现的。(https://chromium.googlesource.com/chromium/src.git/+/38.0.2125.101/base/time/time_win.cc)

首先，在确定 loop 的当前时间方面，Chromium 使用了 timeGetTime() 函数。查阅 MSDN 可以发现这个函数的精度受系统当前 timer interval 影响。在我们的测试机上，理论上也就是上文中提到过的 1.001ms。然而 Windows 系统默认情况下，timer interval 是其最大值（测试机上也就是 15.625ms），除非应用程序修改了全局 timer interval。

如果你关注 IT界的新闻，你一定看过这样的一条新闻。看起来我们的 Chromium 把计时器间隔设定得很小了嘛！看来我们不用担心系统计时器间隔的问题了？不要开心得太早，这样的一条修复给了我们当头一棒。事实上，这个问题在 Chrome 38 中已经得到了修复。难道我们要使用修复以前的 Node-WebKit？这显然不够优雅，而且阻止了我们使用性能更高的 Chromium 版本。

进一步查看 Chromium 源码我们可以发现，在有计时器，且计时器的 timeout < 32ms 时，Chromium 会更改系统的全局定时器间隔以实现小于 15.625ms 精度的计时器。(查看源码) 启动计时器时，一个叫HighResolutionTimerManager 的东西会被启用，这个类会根据当前设备的电源类型，调用EnableHighResolutionTimer 函数。具体来说，当前设备用电池时，他会调用EnableHighResolutionTimer(false)，而使用电源时会传入 true。EnableHighResolutionTimer 函数的实现如下:

[js] view plaincopy

1. void Time::EnableHighResolutionTimer(bool enable) {  
2.   base::AutoLock lock(g_high_res_lock.Get());  
3.   if (g_high_res_timer_enabled == enable)  
4.     return;  
5.   g_high_res_timer_enabled = enable;  
6.   if (!g_high_res_timer_count)  
7.     return;  
8.   // Since g_high_res_timer_count != 0, an ActivateHighResolutionTimer(true)  
9.   // was called which called timeBeginPeriod with g_high_res_timer_enabled  
10.   // with a value which is the opposite of |enable|. With that information we  
11.   // call timeEndPeriod with the same value used in timeBeginPeriod and  
12.   // therefore undo the period effect.  
13.   if (enable) {  
14.     timeEndPeriod(kMinTimerIntervalLowResMs);  
15.     timeBeginPeriod(kMinTimerIntervalHighResMs);  
16.   } else {  
17.     timeEndPeriod(kMinTimerIntervalHighResMs);  
18.     timeBeginPeriod(kMinTimerIntervalLowResMs);  
19.   }  
20. }  

又一个精度问题

回到开头，我们发现测试结果显示，setTimeout 的间隔并不是稳定在 4ms 的，而是在不断地波动。而http://marks.lrednight.com/test.html#48 测试结果也显示，间隔在 48ms 和 49ms 之间跳动。原因是，在 Chromium 和 Node.js 的 event loop 中，等待 IO 事件的那个 Windows 函数调用的精度，受当前系统的计时器影响。游戏逻辑的实现需要用到 requestAnimationFrame 函数（不停更新画布），这个函数可以帮我们将计时器间隔至少设置为 kMinTimerIntervalLowResMs（因为他需要一个16ms的计时器，触发了高精度计时器的要求）。测试机使用电源的时候，系统的 timer interval 是 1ms，所以测试结果有 ±1ms 的误差。如果你的电脑没有被更改系统计时器间隔，运行上面那个#48的测试，max可能会到达48+16=64ms。

使用 Chromium 的 setTimeout 实现，我们可以将 setTimeout(fn, 1) 的误差控制在 4ms 左右，而 setTimeout(fn, 48) 的误差可以控制在 1ms 左右。于是，我们的心中有了一幅新的蓝图，它让我们的代码看起来像是这样：

[js] view plaincopy

1. /* Get the max interval deviation */  
2. var deviation = getMaxIntervalDeviation(bucketSize); // bucketSsize = 48, deviation = 2;  
3. function gameLoop() {  
4.   var now = Date.now();  
5.   if (previousBucket + bucketSize <= now) {  
6.     previousBucket = now;  
7.   
8.     doLogic();  
9.   }  
10.   
11.   if (previousBucket + bucketSize - Date.now() > deviation) {  
12.     // Wait 46ms. The actual delay is less than 48ms.  
13.     setTimeout(gameLoop, bucketSize - deviation);  
14.   } else {  
15.     // Busy waiting. Use setImmediate instead of process.nextTick because the former does not block IO events.  
16.     setImmediate(gameLoop);  
17.   }  
18. }  

上面的代码让我们等待一个误差小于 bucket_size( bucket_size – deviation) 的时间而不是直接等于一个 bucket_size，46ms 的 delay 即便发生了最大的误差，根据上文的理论，实际间隔也是小于48ms的。剩下的时间我们使用忙等待的方法，确保我们的 gameLoop 在足够精确的 interval 下执行。

虽然我们利用 Chromium 在一定程度上解决了问题，但这显然不够优雅。

还记得我们最初的要求吗？我们的服务器端代码是应该可以脱离 Node-Webkit 客户端的，直接在一台有 Node.js 环境的电脑中运行。如果直接跑上面的代码，deviation 的值至少是16ms，也就是说在每一个48ms中，我们要忙等待16ms的时间。CPU使用率蹭蹭蹭就上去了。

意想不到的惊喜

真是气人啊，Node.js 里这么大的一个BUG，没有人注意到吗？答案真是让我们喜出望外。这个BUG在 v.0.11.3 版本里已经得到了修复。直接查看 libuv 代码的 master 分支也能看到修改后的结果。具体的做法是，在 poll 函数等待完成之后，把 loop 的当前时间，加上一个 timeout。这样即便 GetTickCount 没有反应过来，在经过poll的等待之后，我们还是加上了这段等待的时间。于是计时器就能够顺利地到期了。

也就是说，辛苦半天的问题，在 v.0.11.3 里已经得到了解决。不过，我们的努力不是白费的。因为即便消除了 GetTickCount 函数的影响，poll 函数本身也受到系统定时器的影响。解决方案之一，便是编写 Node.js 插件，更改系统定时器的间隔。

不过我们这次的游戏，初步设定是没有服务器的。客户端建立房间之后，就成为了一个服务器。服务器代码可以跑在 Node-WebKit 的环境中，所以 Windows 系统下计时器的问题的优先级并不是最高的。按照上文中我们给出的解决方案，结果已经足够让我们满意。

收尾

解决了计时器的问题，我们的框架实现也就基本上再没什么阻碍了。我们提供了 WebSocket 的支持（在纯 HTML5 环境下），也自定义了通信协议实现了性能更高的 Socket 支持（Node-WebKit 环境下）。当然，Spaceroom 的功能在最初是比较简陋的，但随着需求的提出和时间的增加，我们也在逐渐地完善这个框架。

例如我们发现在我们的游戏里需要生成一致的随机数的时候，我们就为 Spaceroom 加上了这样的功能。在游戏开始的时候 Spaceroom 会分发随机数种子，客户端的 Spaceroom 提供了利用 md5 的随机性，借助随机数种子生成随机数的方法。

看起来还是蛮欣慰的。在编写这样一个框架的过程当中，也学到了很多的东西。如果你对 Spaceroom 有点兴趣，也可以参与到它当中来。相信，Spaceroom 会在更多的地方施展它的拳脚。

来自：阿里巴巴用户体验部有一点