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

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

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

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

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

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

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

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

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

同步算法

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

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

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

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

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

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

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

計時器引發(fā)的血案

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

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

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

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

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

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

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

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

Node.js 中的 BUG

相信大部分你我都對 Node.js 的 even loop 機制有一定的了解，查看 timer 實現(xiàn)的源碼我們可以大致了解到 timer 的實現(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)部實現(xiàn)，使用了 Windows 的 GetTickCount() 函數(shù)來設置當前時間。簡單地來說，在調(diào)用setTimeout 函數(shù)之后，經(jīng)過一系列的掙扎，內(nèi)部的 timer->due 會被設置為當前 loop 的時間 + timeout。在 event loop 中，先通過 uv_update_time 更新當前 loop 的時間，然后在uv_process_timers 中檢查是否有計時器到期，如果有就進入 JavaScript 的世界。通篇讀下來，event loop大概是這樣一個流程：

更新全局時間

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

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

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

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

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

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

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

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

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

又一個精度問題

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

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

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

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

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

意想不到的驚喜

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

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

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

收尾

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

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

看起來還是蠻欣慰的。在編寫這樣一個框架的過程當中，也學到了很多的東西。如果你對 Spaceroom 有點興趣，也可以參與到它當中來。相信，Spaceroom 會在更多的地方施展它的拳腳。

最新評論