在Node.js 如火如荼發展的今天，我們已經可以用它來做各種各樣的事情。前段時間UP主參加了極客鬆活動，在這次活動中我們意在做出一款讓“低頭族”能夠更多交流的遊戲，核心功能便是Lan Party 概念的實時多人互動。極客鬆比賽只有短得可憐的36個小時，要求一切都敏捷迅速。在這樣的前提下初期的準備顯得有些“水到渠成”。跨平台應用的solution 我們選擇了node-webkit，它足夠簡單且符合我們的要求。
按照需求，我們的開發可以按照模塊分開進行。本文具體講述了開發Spaceroom（我們的實時多人遊戲框架）的過程，包括一系列的探索與嘗試，以及對Node.js、WebKit 平臺本身的一些限制的解決，和解決方案的提出。
Getting started
Spaceroom 一瞥
在最開始，Spaceroom 的設計肯定是需求驅動的。我們希望這個框架可以提供以下的基礎功能：
能夠以房間(或者說頻道) 為單位，區分一組用戶
能夠接收收集組內用戶發來的指令
在各個客戶端之間對時，能夠按照規定的interval 精確廣播遊戲數據
能夠盡量消除由網絡延遲帶來的影響
當然，在coding 的後期，我們為Spaceroom 提供了更多的功能，包括暫停遊戲、在各個客戶端之間生成一致的隨機數等（當然根據需求這些都可以在遊戲邏輯框架裡自己實現，並非一定需要用到Spaceroom 這個更多在通信層面上工作的框架）。
APIs
Spaceroom 分為前後端兩個部分。服務器端所需要做的工作包括維護房間列表，提供創建房間、加入房間的功能。我們的客戶端APIs 看起來像這樣:
spaceroom.connect(address, callback) 連接服務器
spaceroom.createRoom(callback) 創建一個房間
spaceroom.joinRoom(roomId) 加入一個房間
spaceroom.on(event, callback) 監聽事件
……
客戶端連接到服務器後，會收到各種各樣的事件。例如一個在一間房間中的用戶，可能收到新玩家加入的事件，或者遊戲開始的事件。我們給客戶端賦予了“生命週期”，他在任何時候都會處於以下狀態的一種：
你可以通過spaceroom.state 獲取客戶端的當前狀態。
使用服務器端的框架相對來說簡單很多，如果使用默認的配置文件，那麼直接運行服務器端框架就可以了。我們有一個基本的需求：服務器代碼可以直接運行在客戶端中，而不需要一個單獨的服務器。玩過PS 或者PSP 的玩家應該清楚我在說什麼。當然，可以跑在專門的服務器裡，自然也是極好的。
邏輯代碼的實現這裡簡略了。初代的Spaceroom 完成了一個Socket 服務器的功能，它維護房間列表，包括房間的狀態，以及每一個房間對應的遊戲時通信（指令收集，bucket 廣播等）。具體實現可以參看源碼。
同步算法
那麼，要怎麼才能使得各個客戶端之間顯示的東西都是實時一致的呢？
這個東西聽起來很有意思。仔細想想，我們需要服務器幫我們傳遞什麼東西？自然就會想到是什麼可能造成各個客戶端之間邏輯的不一致：用戶指令。既然處理遊戲邏輯的代碼都是相同的，那麼給定同樣的條件，代碼的運行結果也是相同的。唯一不同的就是在遊戲過程當中，接收到的各種玩家指令。理所當然的，我們需要一種方式來同步這些指令。如果所有的客戶端都能拿到同樣的指令，那麼所有的客戶端從理論上講就能有一樣的運行結果了。
網絡遊戲的同步算法千奇百怪，適用的場景也各不相同。 Spaceroom 採用的同步算法類似於幀鎖定的概念。我們把時間軸分成了一個一個的區間，每一個區間稱為一個bucket。 Bucket 是用來裝載指令的，由服務器端維護。在每一個bucket 時間段的末尾，服務器把bucket 廣播給所有客戶端，客戶端拿到bucket 之後從中取出指令，驗證之後執行。
為了降低網絡延遲造成的影響，服務器接到的來自客戶端的指令每一個都會按照一定的算法投遞到對應的bucket 中，具體按照以下步驟：
設order_start 為指令攜帶的指令發生時間， t 為order_start 所在bucket 的起始時間
如果t + delay_time <= 當前正在收集指令的bucket 的起始時間，將指令投遞到當前正在收集指令的bucket 中，否則繼續step 3
將指令投遞到t + delay_time 對應的bucket 中
其中delay_time 為約定的服務器延遲時間，可以取為客戶端之間的平均延遲，Spaceroom 裡默認取值80，以及bucket 長度默認取值48. 在每個bucket 時間段的末尾，服務器將此bucket 廣播給所有客戶端，並開始接收下一個bucket 的指令。客戶端根據收到的bucket 間隔，在邏輯中自動進行對時，將時間誤差控制在一個可以接受的範圍內。
這個意思是，正常情況下，客戶端每隔48ms 會收到從服務器端發來的一個bucket，當到達需要處理這個bucket 的時間時，客戶端會進行相應處理。假設客戶端FPS=60，每隔3幀左右的時間，會收到一次bucket，根據這個bucket 來更新邏輯。如果因為網絡波動，超出時間後還沒有收到bucket，客戶端暫停遊戲邏輯並等待。在一個bucket 之內的時間，邏輯的更新可以使用lerp 的方法。
在delay_time = 80, bucket_size = 48 的情況下，任一指令最少會被延遲96ms 執行。更改這兩個參數，例如在delay_time = 60, bucket_size = 32 的情況下，任一指令最少會被延遲64ms 執行。
計時器引發的血案
整個看下來，我們的框架在運行的時候需要有一個精確的計時器。在固定的interval 下執行bucket 的廣播。理所當然地，我們首先想到了使用setInterval()，然而下一秒我們就意識到這個想法有多麼的不靠譜：調皮的setInterval() 似乎有非常嚴重的誤差。而且要命的是，每一次的誤差都會累計起來，造成越來越嚴重的後果。
於是我們馬上又想到了使用setTimeout()，通過動態地修正下一次到時的時間來讓我們的邏輯大致穩定在規定的interval 左右。例如此次setTimeout()比預期少了5ms, 那麼我們下一次就讓他提前5ms. 不過測試結果不盡人意，而且這怎麼看都不夠優雅。
所以我們又要換一個思路。是否可以讓setTimeout() 盡可能快地到期，然後我們檢查當前的時間是否到達目標時間。例如在我們的循環中，使用setTimeout(callback, 1) 來不停地檢查時間，這看起來像是一個不錯的主意。
令人失望的計時器
我們立即寫了一段代碼來測試我們的想法，結果令人失望。在目前最新的node.js 穩定版(v0.10.32)以及Windows 平台下，運行這樣一段代碼：
複製代碼代碼如下:
var sum = 0, count = 0;
function test() {
var now = Date.now();
setTimeout(function () {
var diff = Date.now() - now;
sum += diff;
count++;
test();
});
}
test();
一段時間之後在控制台裡輸入sum/count，可以看到一個結果，類似於：
複製代碼代碼如下:
> sum / count
15.624555160142348
什麼?!!我要1ms 的間隔時間，你卻告訴我實際的平均間隔為15.625ms！這個畫面簡直是太美。我們在mac 上做同樣的測試，得到的結果是1.4ms。於是我們心生疑惑：這到底是什麼鬼？如果我是一個果粉，我可能就要得出Windows 太垃圾然後放棄Windows 的結論了，不過好在我是一名嚴謹的前端工程師，於是我開始繼續思索起這個數字來。
等等，這個數字為什麼那麼眼熟？ 15.625ms 這個數字會不會太像Windows 下的最大計時器間隔了？立即下載了一個ClockRes 進行測試，控制台一跑果然得到瞭如下結果：
複製代碼代碼如下:
Maximum timer interval: 15.625 ms
Minimum timer interval: 0.500 ms
Current timer interval: 1.001 ms
果不其然！查閱node.js 的手冊我們能看到這樣一段對setTimeout 的描述：
The actual delay depends on external factors like OS timer granularity and system load.
然而測試結果顯示，這個實際延遲是最大計時器間隔(注意此時系統的當前計時器間隔只有1.001ms)，無論如何讓人無法接受，強大的好奇心驅使我們翻翻看node.js 的源碼來一窺究竟。
Node.js 中的BUG
相信大部分你我都對Node.js 的even loop 機制有一定的了解，查看timer 實現的源碼我們可以大致了解到timer 的實現原理，讓我們從event loop 的主循環講起：
複製代碼代碼如下:
while (r != 0 && loop->stop_flag == 0) {
/* 更新全局時間*/
uv_update_time(loop);
/* 檢查計時器是否到期，並執行對應計時器回調*/
uv_process_timers(loop);
/* Call idle callbacks if nothing to do. */
if (loop->pending_reqs_tail == NULL &&
loop->endgame_handles == NULL) {
/* 防止event loop退出*/
uv_idle_invoke(loop);
}
uv_process_reqs(loop);
uv_process_endgames(loop);
uv_prepare_invoke(loop);
/* 收集IO 事件*/
(*poll)(loop, loop->idle_handles == NULL &&
loop->pending_reqs_tail == NULL &&
loop->endgame_handles == NULL &&
!loop->stop_flag &&
(loop->active_handles > 0 ||
!ngx_queue_empty(&loop->active_reqs)) &&
!(mode & UV_RUN_NOWAIT));
/* setImmediate() 等*/
uv_check_invoke(loop);
r = uv__loop_alive(loop);
if (mode & (UV_RUN_ONCE | UV_RUN_NOWAIT))
break;
}
其中uv_update_time 函數的源碼如下：（https://github.com/joyent/libuv/blob/v0.10/src/win/timer.c））
複製代碼代碼如下:
void uv_update_time(uv_loop_t* loop) {
/* 獲取當前系統時間*/
DWORD ticks = GetTickCount();
/* The assumption is made that LARGE_INTEGER.QuadPart has the same type */
/* loop->time, which happens to be. Is there any way to assert this? */
LARGE_INTEGER* time = (LARGE_INTEGER*) &loop->time;
/* If the timer has wrapped, add 1 to it's high-order dword. */
/* uv_poll must make sure that the timer can never overflow more than */
/* once between two subsequent uv_update_time calls. */
if (ticks < time->LowPart) {
time->HighPart += 1;
}
time->LowPart = ticks;
}
該函數的內部實現，使用了Windows 的GetTickCount() 函數來設置當前時間。簡單地來說，在調用setTimeout 函數之後，經過一系列的掙扎，內部的timer->due 會被設置為當前loop 的時間+ timeout。在event loop 中，先通過uv_update_time 更新當前loop 的時間，然後在uv_process_timers 中檢查是否有計時器到期，如果有就進入JavaScript 的世界。通篇讀下來，event loop大概是這樣一個流程：
更新全局時間
檢查定時器，如果有定時器過期，執行回調
檢查reqs 隊列，執行正在等待的請求
進入poll 函數，收集IO 事件，如果有IO 事件到來，將相應的處理函數添加到reqs 隊列中，以便在下一次event loop 中執行。在poll 函數內部，調用了一個系統方法來收集IO 事件。這個方法會使得進程阻塞，直到有IO 事件到來或者到達設定好的超時時間。調用這個方法時，超時時間設定為最近的一個timer 到期的時間。意思就是阻塞收集IO 事件，最大阻塞時間為下一個timer 的到底時間。
Windows下poll 函數之一的源碼：
複製代碼代碼如下:
static void uv_poll(uv_loop_t* loop, int block) {
DWORD bytes, timeout;
ULONG_PTR key;
OVERLAPPED* overlapped;
uv_req_t* req;
if (block) {
/* 取出最近的一個計時器的過期時間*/
timeout = uv_get_poll_timeout(loop);
} else {
timeout = 0;
}
GetQueuedCompletionStatus(loop->iocp,
&bytes,
&key,
&overlapped,
/* 最多阻塞到下個計時器到期*/
timeout);
if (overlapped) {
/* Package was dequeued */
req = uv_overlapped_to_req(overlapped);
/* 把IO 事件插入隊列裡*/
uv_insert_pending_req(loop, req);
} else if (GetLastError() != WAIT_TIMEOUT) {
/* Serious error */
uv_fatal_error(GetLastError(), "GetQueuedCompletionStatus");
}
}
按照上述步驟，假設我們設置了一個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 函數的實現如下:
複製代碼代碼如下:
void Time::EnableHighResolutionTimer(bool enable) {
base::AutoLock lock(g_high_res_lock.Get());
if (g_high_res_timer_enabled == enable)
return;
g_high_res_timer_enabled = enable;
if (!g_high_res_timer_count)
return;
// Since g_high_res_timer_count != 0, an ActivateHighResolutionTimer(true)
// was called which called timeBeginPeriod with g_high_res_timer_enabled
// with a value which is the opposite of |enable|. With that information we
// call timeEndPeriod with the same value used in timeBeginPeriod and
// therefore undo the period effect.
if (enable) {
timeEndPeriod(kMinTimerIntervalLowResMs);
timeBeginPeriod(kMinTimerIntervalHighResMs);
} else {
timeEndPeriod(kMinTimerIntervalHighResMs);
timeBeginPeriod(kMinTimerIntervalLowResMs);
}
}
其中，kMinTimerIntervalLowResMs = 4，kMinTimerIntervalHighResMs = 1。 timeBeginPeriod 以及timeEndPeriod 是Windows 提供的用來修改系統timer interval 的函數。也就是說在接電源時，我們能拿到的最小的timer interval 是1ms，而使用電池時，是4ms。由於我們的循環不斷地調用了setTimeout，根據W3C 規範，最小的間隔也是4ms，所以鬆口氣，這個對我們的影響不大。
又一個精度問題
回到開頭，我們發現測試結果顯示，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 左右。於是，我們的心中有了一幅新的藍圖，它讓我們的代碼看起來像是這樣：
複製代碼代碼如下:
/* Get the max interval deviation */
var deviation = getMaxIntervalDeviation(bucketSize); // bucketSsize = 48, deviation = 2;
function gameLoop() {
var now = Date.now();
if (previousBucket + bucketSize <= now) {
previousBucket = now;
doLogic();
}
if (previousBucket + bucketSize - Date.now() > deviation) {
// Wait 46ms. The actual delay is less than 48ms.
setTimeout(gameLoop, bucketSize - deviation);
} else {
// Busy waiting. Use setImmediate instead of process.nextTick because the former does not block IO events.
setImmediate(gameLoop);
}
}
上面的代碼讓我們等待一個誤差小於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 會在更多的地方施展它的拳腳。