在 Node.js 如火如荼發(fā)展的今天，我們已經(jīng)可以用它來做各種各樣的事情。前段時(shí)間UP主參加了極客松活動(dòng)，在這次活動(dòng)中我們意在做出一款讓“低頭族”能夠更多交流的游戲，核心功能便是 Lan Party 概念的實(shí)時(shí)多人互動(dòng)。極客松比賽只有短得可憐的36個(gè)小時(shí)，要求一切都敏捷迅速。在這樣的前提下初期的準(zhǔn)備顯得有些“水到渠成”?？缙脚_(tái)應(yīng)用的 solution 我們選擇了node-webkit，它足夠簡單且符合我們的要求。

按照需求，我們的開發(fā)可以按照模塊分開進(jìn)行。本文具體講述了開發(fā) Spaceroom（我們的實(shí)時(shí)多人游戲框架）的過程，包括一系列的探索與嘗試，以及對(duì) Node.js、WebKit 平臺(tái)本身的一些限制的解決，和解決方案的提出。

Getting started
Spaceroom 一瞥
在最開始，Spaceroom 的設(shè)計(jì)肯定是需求驅(qū)動(dòng)的。我們希望這個(gè)框架可以提供以下的基礎(chǔ)功能：

能夠以 房間(或者說頻道) 為單位，區(qū)分一組用戶
能夠接收收集組內(nèi)用戶發(fā)來的指令
在各個(gè)客戶端之間對(duì)時(shí)，能夠按照規(guī)定的 interval 精確廣播游戲數(shù)據(jù)
能夠盡量消除由網(wǎng)絡(luò)延遲帶來的影響
當(dāng)然，在 coding 的后期，我們?yōu)?Spaceroom 提供了更多的功能，包括暫停游戲、在各個(gè)客戶端之間生成一致的隨機(jī)數(shù)等（當(dāng)然根據(jù)需求這些都可以在游戲邏輯框架里自己實(shí)現(xiàn)，并非一定需要用到 Spaceroom 這個(gè)更多在通信層面上工作的框架）。

APIs
Spaceroom 分為前后端兩個(gè)部分。服務(wù)器端所需要做的工作包括維護(hù)房間列表，提供創(chuàng)建房間、加入房間的功能。我們的客戶端 APIs 看起來像這樣:

spaceroom.connect(address, callback) – 連接服務(wù)器
spaceroom.createRoom(callback) – 創(chuàng)建一個(gè)房間
spaceroom.joinRoom(roomId) – 加入一個(gè)房間
spaceroom.on(event, callback) – 監(jiān)聽事件
……
客戶端連接到服務(wù)器后，會(huì)收到各種各樣的事件。例如一個(gè)在一間房間中的用戶，可能收到新玩家加入的事件，或者游戲開始的事件。我們給客戶端賦予了“生命周期”，他在任何時(shí)候都會(huì)處于以下狀態(tài)的一種：

你可以通過 spaceroom.state 獲取客戶端的當(dāng)前狀態(tài)。

使用服務(wù)器端的框架相對(duì)來說簡單很多，如果使用默認(rèn)的配置文件，那么直接運(yùn)行服務(wù)器端框架就可以了。我們有一個(gè)基本的需求：服務(wù)器代碼 可以直接運(yùn)行在客戶端中，而不需要一個(gè)單獨(dú)的服務(wù)器。玩過 PS 或者 PSP 的玩家應(yīng)該清楚我在說什么。當(dāng)然，可以跑在專門的服務(wù)器里，自然也是極好的。

邏輯代碼的實(shí)現(xiàn)這里簡略了。初代的 Spaceroom 完成了一個(gè) Socket 服務(wù)器的功能，它維護(hù)房間列表，包括房間的狀態(tài)，以及每一個(gè)房間對(duì)應(yīng)的游戲時(shí)通信（指令收集，bucket 廣播等）。具體實(shí)現(xiàn)可以參看源碼。

同步算法

那么，要怎么才能使得各個(gè)客戶端之間顯示的東西都是實(shí)時(shí)一致的呢？

這個(gè)東西聽起來很有意思。仔細(xì)想想，我們需要服務(wù)器幫我們傳遞什么東西？自然就會(huì)想到是什么可能造成各個(gè)客戶端之間邏輯的不一致：用戶指令。既然處理游戲邏輯的代碼都是相同的，那么給定同樣的條件，代碼的運(yùn)行結(jié)果也是相同的。唯一不同的就是在游戲過程當(dāng)中，接收到的各種玩家指令。理所當(dāng)然的，我們需要一種方式來同步這些指令。如果所有的客戶端都能拿到同樣的指令，那么所有的客戶端從理論上講就能有一樣的運(yùn)行結(jié)果了。

網(wǎng)絡(luò)游戲的同步算法千奇百怪，適用的場(chǎng)景也各不相同。Spaceroom 采用的同步算法類似于幀鎖定的概念。我們把時(shí)間軸分成了一個(gè)一個(gè)的區(qū)間，每一個(gè)區(qū)間稱為一個(gè) bucket。Bucket 是用來裝載指令的，由服務(wù)器端維護(hù)。在每一個(gè) bucket 時(shí)間段的末尾，服務(wù)器把 bucket 廣播給所有客戶端，客戶端拿到 bucket 之后從中取出指令，驗(yàn)證之后執(zhí)行。

為了降低網(wǎng)絡(luò)延遲造成的影響，服務(wù)器接到的來自客戶端的指令每一個(gè)都會(huì)按照一定的算法投遞到對(duì)應(yīng)的 bucket 中，具體按照以下步驟：

設(shè) order_start 為指令攜帶的指令發(fā)生時(shí)間， t 為 order_start 所在 bucket 的起始時(shí)間
如果 t + delay_time <= 當(dāng)前正在收集指令的 bucket 的起始時(shí)間，將指令投遞到 當(dāng)前正在收集指令的 bucket 中，否則繼續(xù) step 3
將指令投遞到 t + delay_time 對(duì)應(yīng)的 bucket 中
其中 delay_time 為約定的服務(wù)器延遲時(shí)間，可以取為客戶端之間的平均延遲，Spaceroom 里默認(rèn)取值80，以及 bucket 長度默認(rèn)取值48. 在每個(gè) bucket 時(shí)間段的末尾，服務(wù)器將此 bucket 廣播給所有客戶端，并開始接收下一個(gè) bucket 的指令?？蛻舳烁鶕?jù)收到的 bucket 間隔，在邏輯中自動(dòng)進(jìn)行對(duì)時(shí)，將時(shí)間誤差控制在一個(gè)可以接受的范圍內(nèi)。

這個(gè)意思是，正常情況下，客戶端每隔 48ms 會(huì)收到從服務(wù)器端發(fā)來的一個(gè) bucket，當(dāng)?shù)竭_(dá)需要處理這個(gè) bucket 的時(shí)間時(shí)，客戶端會(huì)進(jìn)行相應(yīng)處理。假設(shè)客戶端 FPS=60，每隔 3幀 左右的時(shí)間，會(huì)收到一次 bucket，根據(jù)這個(gè) bucket 來更新邏輯。如果因?yàn)榫W(wǎng)絡(luò)波動(dòng)，超出時(shí)間后還沒有收到 bucket，客戶端暫停游戲邏輯并等待。在一個(gè) bucket 之內(nèi)的時(shí)間，邏輯的更新可以使用 lerp 的方法。

在 delay_time = 80, bucket_size = 48 的情況下，任一指令最少會(huì)被延遲 96ms 執(zhí)行。更改這兩個(gè)參數(shù)，例如在 delay_time = 60, bucket_size = 32 的情況下，任一指令最少會(huì)被延遲 64ms 執(zhí)行。

計(jì)時(shí)器引發(fā)的血案

整個(gè)看下來，我們的框架在運(yùn)行的時(shí)候需要有一個(gè)精確的計(jì)時(shí)器。在固定的 interval 下執(zhí)行 bucket 的廣播。理所當(dāng)然地，我們首先想到了使用setInterval()，然而下一秒我們就意識(shí)到這個(gè)想法有多么的不靠譜：調(diào)皮的setInterval() 似乎有非常嚴(yán)重的誤差。而且要命的是，每一次的誤差都會(huì)累計(jì)起來，造成越來越嚴(yán)重的后果。

于是我們馬上又想到了使用 setTimeout()，通過動(dòng)態(tài)地修正下一次到時(shí)的時(shí)間來讓我們的邏輯大致穩(wěn)定在規(guī)定的 interval 左右。例如此次setTimeout()比預(yù)期少了5ms, 那么我們下一次就讓他提前5ms. 不過測(cè)試結(jié)果不盡人意，而且這怎么看都不夠優(yōu)雅。

所以我們又要換一個(gè)思路。是否可以讓 setTimeout() 盡可能快地到期，然后我們檢查當(dāng)前的時(shí)間是否到達(dá)目標(biāo)時(shí)間。例如在我們的循環(huán)中，使用setTimeout(callback, 1) 來不停地檢查時(shí)間，這看起來像是一個(gè)不錯(cuò)的主意。

令人失望的計(jì)時(shí)器
我們立即寫了一段代碼來測(cè)試我們的想法，結(jié)果令人失望。在目前最新的node.js 穩(wěn)定版(v0.10.32)以及 Windows 平臺(tái)下，運(yùn)行這樣一段代碼：

一段時(shí)間之后在控制臺(tái)里輸入 sum/count，可以看到一個(gè)結(jié)果，類似于：

什么?!!我要 1ms 的間隔時(shí)間，你卻告訴我實(shí)際的平均間隔為 15.625ms！這個(gè)畫面簡直是太美。我們?cè)?mac 上做同樣的測(cè)試，得到的結(jié)果是 1.4ms。于是我們心生疑惑：這到底是什么鬼？如果我是一個(gè)果粉，我可能就要得出 Windows 太垃圾然后放棄 Windows 的結(jié)論了，不過好在我是一名嚴(yán)謹(jǐn)?shù)那岸斯こ處煟谑俏议_始繼續(xù)思索起這個(gè)數(shù)字來。

等等，這個(gè)數(shù)字為什么那么眼熟？15.625ms 這個(gè)數(shù)字會(huì)不會(huì)太像 Windows 下的最大計(jì)時(shí)器間隔了？立即下載了一個(gè) ClockRes 進(jìn)行測(cè)試，控制臺(tái)一跑果然得到了如下結(jié)果：

果不其然！查閱 node.js 的手冊(cè)我們能看到這樣一段對(duì) setTimeout 的描述：
 
The actual delay depends on external factors like OS timer granularity and system load.
然而測(cè)試結(jié)果顯示，這個(gè)實(shí)際延遲是最大計(jì)時(shí)器間隔(注意此時(shí)系統(tǒng)的當(dāng)前計(jì)時(shí)器間隔只有 1.001ms)，無論如何讓人無法接受，強(qiáng)大的好奇心驅(qū)使我們翻翻看 node.js 的源碼來一窺究竟。

Node.js 中的 BUG

相信大部分你我都對(duì) Node.js 的 even loop 機(jī)制有一定的了解，查看 timer 實(shí)現(xiàn)的源碼我們可以大致了解到 timer 的實(shí)現(xiàn)原理，讓我們從 event loop 的主循環(huán)講起：
 

其中 uv_update_time 函數(shù)的源碼如下：（https://github.com/joyent/libuv/blob/v0.10/src/win/timer.c））

該函數(shù)的內(nèi)部實(shí)現(xiàn)，使用了 Windows 的 GetTickCount() 函數(shù)來設(shè)置當(dāng)前時(shí)間。簡單地來說，在調(diào)用setTimeout 函數(shù)之后，經(jīng)過一系列的掙扎，內(nèi)部的 timer->due 會(huì)被設(shè)置為當(dāng)前 loop 的時(shí)間 + timeout。在 event loop 中，先通過 uv_update_time 更新當(dāng)前 loop 的時(shí)間，然后在uv_process_timers 中檢查是否有計(jì)時(shí)器到期，如果有就進(jìn)入 JavaScript 的世界。通篇讀下來，event loop大概是這樣一個(gè)流程：

更新全局時(shí)間

檢查定時(shí)器，如果有定時(shí)器過期，執(zhí)行回調(diào)
檢查 reqs 隊(duì)列，執(zhí)行正在等待的請(qǐng)求
進(jìn)入 poll 函數(shù)，收集 IO 事件，如果有 IO 事件到來，將相應(yīng)的處理函數(shù)添加到 reqs 隊(duì)列中，以便在下一次 event loop 中執(zhí)行。在 poll 函數(shù)內(nèi)部，調(diào)用了一個(gè)系統(tǒng)方法來收集 IO 事件。這個(gè)方法會(huì)使得進(jìn)程阻塞，直到有 IO 事件到來或者到達(dá)設(shè)定好的超時(shí)時(shí)間。調(diào)用這個(gè)方法時(shí)，超時(shí)時(shí)間設(shè)定為最近的一個(gè) timer 到期的時(shí)間。意思就是阻塞收集 IO 事件，最大阻塞時(shí)間為 下一個(gè) timer 的到底時(shí)間。
Windows下 poll 函數(shù)之一的源碼：

按照上述步驟，假設(shè)我們?cè)O(shè)置了一個(gè) timeout = 1ms 的計(jì)時(shí)器，poll 函數(shù)會(huì)最多阻塞 1ms 之后恢復(fù)（如果期間沒有任何 IO 事件）。在繼續(xù)進(jìn)入 event loop 循環(huán)的時(shí)候， uv_update_time 就會(huì)更新時(shí)間，然后uv_process_timers 發(fā)現(xiàn)我們的計(jì)時(shí)器到期，執(zhí)行回調(diào)。所以初步的分析是，要么是uv_update_time 出了問題（沒有正確地更新當(dāng)前時(shí)間），要么是 poll 函數(shù)等待 1ms 之后恢復(fù)，這個(gè) 1ms 的等待出了問題。

查閱 MSDN，我們驚人地發(fā)現(xiàn)對(duì) GetTickCount 函數(shù)的描述：

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 的精度是如此的粗糙！假設(shè) poll 函數(shù)正確地阻塞了 1ms 的時(shí)間，然而下一次執(zhí)行uv_update_time 的時(shí)候并沒有正確地更新當(dāng)前 loop 的時(shí)間！所以我們的定時(shí)器沒有被判定為過期，于是 poll 又等待了 1ms，又進(jìn)入了下一次 event loop。直到終于 GetTickCount 正確地更新了（所謂15.625ms更新一次），loop 的當(dāng)前時(shí)間被更新，我們的計(jì)時(shí)器才在 uv_process_timers 里被判定過期。

向 WebKit 求助
Node.js 的這段源碼看得人很無助：他使用了一個(gè)精度低下的時(shí)間函數(shù)，而且沒有做任何處理。不過我們立刻想到了既然我們使用 Node-WebKit，那么除了 Node.js 的 setTimeout，我們還有 Chromium 的 setTimeout。寫一段測(cè)試代碼，用我們的瀏覽器或者 Node-WebKit 跑一下：http://marks.lrednight.com/test.html#1 (#后面跟的數(shù)字表示需要測(cè)定的間隔)，結(jié)果如下圖：

按照 HTML5 的規(guī)范，理論結(jié)果應(yīng)該是前5次結(jié)果是1ms，以后的結(jié)果是4ms。測(cè)試用例中顯示的結(jié)果是從第3次開始的，也就是說表上的數(shù)據(jù)理論上應(yīng)該是前3次都是1ms，之后的結(jié)果都是4ms。結(jié)果有一定的誤差，而且根據(jù)規(guī)定，我們能拿到的最小的理論結(jié)果是4ms。雖然我們不滿足，但顯然這比 node.js 的結(jié)果讓我們滿意多了。強(qiáng)大的好奇心趨勢(shì)我們看看 Chromium 的源碼，看看他是如何實(shí)現(xiàn)的。(https://chromium.googlesource.com/chromium/src.git/+/38.0.2125.101/base/time/time_win.cc)

首先，在確定 loop 的當(dāng)前時(shí)間方面，Chromium 使用了 timeGetTime() 函數(shù)。查閱 MSDN 可以發(fā)現(xiàn)這個(gè)函數(shù)的精度受系統(tǒng)當(dāng)前 timer interval 影響。在我們的測(cè)試機(jī)上，理論上也就是上文中提到過的 1.001ms。然而 Windows 系統(tǒng)默認(rèn)情況下，timer interval 是其最大值（測(cè)試機(jī)上也就是 15.625ms），除非應(yīng)用程序修改了全局 timer interval。

如果你關(guān)注 IT界的新聞，你一定看過這樣的一條新聞?？雌饋砦覀兊?Chromium 把計(jì)時(shí)器間隔設(shè)定得很小了嘛！看來我們不用擔(dān)心系統(tǒng)計(jì)時(shí)器間隔的問題了？不要開心得太早，這樣的一條修復(fù)給了我們當(dāng)頭一棒。事實(shí)上，這個(gè)問題在 Chrome 38 中已經(jīng)得到了修復(fù)。難道我們要使用修復(fù)以前的 Node-WebKit？這顯然不夠優(yōu)雅，而且阻止了我們使用性能更高的 Chromium 版本。

進(jìn)一步查看 Chromium 源碼我們可以發(fā)現(xiàn)，在有計(jì)時(shí)器，且計(jì)時(shí)器的 timeout < 32ms 時(shí)，Chromium 會(huì)更改系統(tǒng)的全局定時(shí)器間隔以實(shí)現(xiàn)小于 15.625ms 精度的計(jì)時(shí)器。(查看源碼) 啟動(dòng)計(jì)時(shí)器時(shí)，一個(gè)叫HighResolutionTimerManager 的東西會(huì)被啟用，這個(gè)類會(huì)根據(jù)當(dāng)前設(shè)備的電源類型，調(diào)用EnableHighResolutionTimer 函數(shù)。具體來說，當(dāng)前設(shè)備用電池時(shí)，他會(huì)調(diào)用EnableHighResolutionTimer(false)，而使用電源時(shí)會(huì)傳入 true。EnableHighResolutionTimer 函數(shù)的實(shí)現(xiàn)如下:

其中，kMinTimerIntervalLowResMs = 4，kMinTimerIntervalHighResMs = 1。timeBeginPeriod 以及timeEndPeriod 是 Windows 提供的用來修改系統(tǒng) timer interval 的函數(shù)。也就是說在接電源時(shí)，我們能拿到的最小的 timer interval 是1ms，而使用電池時(shí)，是4ms。由于我們的循環(huán)不斷地調(diào)用了 setTimeout，根據(jù) W3C 規(guī)范，最小的間隔也是 4ms，所以松口氣，這個(gè)對(duì)我們的影響不大。

又一個(gè)精度問題

回到開頭，我們發(fā)現(xiàn)測(cè)試結(jié)果顯示，setTimeout 的間隔并不是穩(wěn)定在 4ms 的，而是在不斷地波動(dòng)。而http://marks.lrednight.com/test.html#48 測(cè)試結(jié)果也顯示，間隔在 48ms 和 49ms 之間跳動(dòng)。原因是，在 Chromium 和 Node.js 的 event loop 中，等待 IO 事件的那個(gè) Windows 函數(shù)調(diào)用的精度，受當(dāng)前系統(tǒng)的計(jì)時(shí)器影響。游戲邏輯的實(shí)現(xiàn)需要用到 requestAnimationFrame 函數(shù)（不停更新畫布），這個(gè)函數(shù)可以幫我們將計(jì)時(shí)器間隔至少設(shè)置為 kMinTimerIntervalLowResMs（因?yàn)樗枰粋€(gè)16ms的計(jì)時(shí)器，觸發(fā)了高精度計(jì)時(shí)器的要求）。測(cè)試機(jī)使用電源的時(shí)候，系統(tǒng)的 timer interval 是 1ms，所以測(cè)試結(jié)果有 ±1ms 的誤差。如果你的電腦沒有被更改系統(tǒng)計(jì)時(shí)器間隔，運(yùn)行上面那個(gè)#48的測(cè)試，max可能會(huì)到達(dá)48+16=64ms。

使用 Chromium 的 setTimeout 實(shí)現(xiàn)，我們可以將 setTimeout(fn, 1) 的誤差控制在 4ms 左右，而 setTimeout(fn, 48) 的誤差可以控制在 1ms 左右。于是，我們的心中有了一幅新的藍(lán)圖，它讓我們的代碼看起來像是這樣：

上面的代碼讓我們等待一個(gè)誤差小于 bucket_size( bucket_size – deviation) 的時(shí)間而不是直接等于一個(gè) bucket_size，46ms 的 delay 即便發(fā)生了最大的誤差，根據(jù)上文的理論，實(shí)際間隔也是小于48ms的。剩下的時(shí)間我們使用忙等待的方法，確保我們的 gameLoop 在足夠精確的 interval 下執(zhí)行。

雖然我們利用 Chromium 在一定程度上解決了問題，但這顯然不夠優(yōu)雅。

還記得我們最初的要求嗎？我們的服務(wù)器端代碼是應(yīng)該可以脫離 Node-Webkit 客戶端的，直接在一臺(tái)有 Node.js 環(huán)境的電腦中運(yùn)行。如果直接跑上面的代碼，deviation 的值至少是16ms，也就是說在每一個(gè)48ms中，我們要忙等待16ms的時(shí)間。CPU使用率蹭蹭蹭就上去了。

意想不到的驚喜

真是氣人啊，Node.js 里這么大的一個(gè)BUG，沒有人注意到嗎？答案真是讓我們喜出望外。這個(gè)BUG在 v.0.11.3 版本里已經(jīng)得到了修復(fù)。直接查看 libuv 代碼的 master 分支也能看到修改后的結(jié)果。具體的做法是，在 poll 函數(shù)等待完成之后，把 loop 的當(dāng)前時(shí)間，加上一個(gè) timeout。這樣即便 GetTickCount 沒有反應(yīng)過來，在經(jīng)過poll的等待之后，我們還是加上了這段等待的時(shí)間。于是計(jì)時(shí)器就能夠順利地到期了。

也就是說，辛苦半天的問題，在 v.0.11.3 里已經(jīng)得到了解決。不過，我們的努力不是白費(fèi)的。因?yàn)榧幢阆?GetTickCount 函數(shù)的影響，poll 函數(shù)本身也受到系統(tǒng)定時(shí)器的影響。解決方案之一，便是編寫 Node.js 插件，更改系統(tǒng)定時(shí)器的間隔。

不過我們這次的游戲，初步設(shè)定是沒有服務(wù)器的?？蛻舳私⒎块g之后，就成為了一個(gè)服務(wù)器。服務(wù)器代碼可以跑在 Node-WebKit 的環(huán)境中，所以 Windows 系統(tǒng)下計(jì)時(shí)器的問題的優(yōu)先級(jí)并不是最高的。按照上文中我們給出的解決方案，結(jié)果已經(jīng)足夠讓我們滿意。

收尾

解決了計(jì)時(shí)器的問題，我們的框架實(shí)現(xiàn)也就基本上再?zèng)]什么阻礙了。我們提供了 WebSocket 的支持（在純 HTML5 環(huán)境下），也自定義了通信協(xié)議實(shí)現(xiàn)了性能更高的 Socket 支持（Node-WebKit 環(huán)境下）。當(dāng)然，Spaceroom 的功能在最初是比較簡陋的，但隨著需求的提出和時(shí)間的增加，我們也在逐漸地完善這個(gè)框架。

例如我們發(fā)現(xiàn)在我們的游戲里需要生成一致的隨機(jī)數(shù)的時(shí)候，我們就為 Spaceroom 加上了這樣的功能。在游戲開始的時(shí)候 Spaceroom 會(huì)分發(fā)隨機(jī)數(shù)種子，客戶端的 Spaceroom 提供了利用 md5 的隨機(jī)性，借助隨機(jī)數(shù)種子生成隨機(jī)數(shù)的方法。

看起來還是蠻欣慰的。在編寫這樣一個(gè)框架的過程當(dāng)中，也學(xué)到了很多的東西。如果你對(duì) Spaceroom 有點(diǎn)興趣，也可以參與到它當(dāng)中來。相信，Spaceroom 會(huì)在更多的地方施展它的拳腳。