隨著多核處理器的普及,如何充分利用多核并行工作就成為高性能程序設(shè)計的一個重點。本系列文章將圍繞高性能網(wǎng)游服務(wù)器的實現(xiàn),探討這方面的技術(shù)。

網(wǎng)游服務(wù)器的特點是:

具有大量客戶端連接(數(shù)百至數(shù)千個),每個客戶端都以一定的速率不斷發(fā)送和接收數(shù)據(jù);
服務(wù)器端的數(shù)據(jù)流量通常在幾個至幾十個Mbps之間;
數(shù)據(jù)需要實時處理;
數(shù)據(jù)包具有時序關(guān)系,往往需要按照嚴格的先后順序予以處理。

網(wǎng)游服務(wù)器實際上代表了一類典型的新興流數(shù)據(jù)處理服務(wù)器。這里只是為了討論方便而限定于網(wǎng)游服務(wù)器,但是所討論的原理和技術(shù)應(yīng)該是普適的。

同步多線程技術(shù)肯定是無法滿足要求的。由于每個客戶端都在持續(xù)和服務(wù)器交換數(shù)據(jù),系統(tǒng)將無法有效管理太多的線程;即使使用線程池技術(shù),所能服務(wù)的客戶連接也是很有限的。至于數(shù)據(jù)處理的實時性和數(shù)據(jù)的時序都無法顧及。

異步技術(shù)有好幾種方式,這里只討論IOCP和輪詢模式。IOCP是微軟推動的技術(shù)。對非常大量的連接(數(shù)千至數(shù)萬)很有效。但是由于使用了多線程,這些線程需要把所需讀寫的數(shù)據(jù)通過共享的FIFO與主線程解耦(否則無法保持時序)。這就造成頻繁的線程切換,無法滿足大數(shù)據(jù)量的實時處理要求。另外,由于網(wǎng)卡只有一塊(就一個網(wǎng)絡(luò)地址而言),多線程并不能增加讀寫的速率。在另外一些時序要求不那么嚴格的場合,這些線程可以各自獨立完成所有的處理任務(wù),只需要在線程內(nèi)部保持數(shù)據(jù)的時序。這就是向同步多線程技術(shù)退化了。

輪詢是常用的模式。程序員把需要處理的Socket連接注冊到一個數(shù)據(jù)結(jié)構(gòu)中,然后提交給系統(tǒng)檢查它們的讀寫狀態(tài)。系統(tǒng)返回可供操作的Socket連接列表供程序員逐個處理。如果有數(shù)據(jù)可讀就讀入并處理,如果可寫則把相應(yīng)的數(shù)據(jù)寫出去。為了提高效率和程序結(jié)構(gòu)的清晰起見,Socket服務(wù)器通常單獨使用一個線程,并且通過FIFO數(shù)據(jù)結(jié)構(gòu)和主線程解耦。

在單核處理器上,上面這種輪詢的模式是沒有問題的。但是在多核平臺上,用于解耦的FIFO將會變成并發(fā)瓶頸。這是因為傳統(tǒng)的實現(xiàn)技術(shù)必須對FIFO加鎖。雖然網(wǎng)絡(luò)線程和主線程分別跑在不同的核上,理論上可以物理同時地運行(如果分別操作不同的數(shù)據(jù)項),但是同步鎖卻強行迫使其中的一個線程必須等待另外一個線程退出臨界段,即使另外一個核空閑著。

這時候就需要一種支持并發(fā)的數(shù)據(jù)結(jié)構(gòu),下面稱之為ConcurrentFIFO。

public interface ConcurrentFIFO {
    public Object remove();
    public void put(Object o);
}

put方法把一個數(shù)據(jù)對象推進FIFO,而remove方法從FIFO刪除并返回一個數(shù)據(jù)對象。通過精心設(shè)計,ConcurrentFIFO的實現(xiàn)是線程安全的,兩個線程可以安全而同時地訪問FIFO。這樣在多核平臺上就能達到極高的性能。

通用的ConcurrentFIFO是非常難于實現(xiàn)的。基本的技術(shù)是使用原子的CAS操作來實現(xiàn)。CAS即CompareAndSet?，F(xiàn)代處理器基本上都能支持這一類指令。但是這種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)的一個很大的障礙就是垃圾回收。在多線程并發(fā)運行的情況下,被原子替換下來的數(shù)據(jù)無法得知其是否是其它線程所需要的,也就無法決定是否回收這塊內(nèi)存。除非有垃圾回收器,否則ConcurrentFIFO是很難實現(xiàn)的。(鼓吹手工管理內(nèi)存效率最高的朋友們請瞪大眼睛看清楚)

其實,即使是對于有垃圾回收和內(nèi)建線程支持的Java語言,要想構(gòu)造一個支持并發(fā)的數(shù)據(jù)結(jié)構(gòu),也是極端困難的。java.util.concurrent包是經(jīng)過并發(fā)領(lǐng)域的專家(Doug Lea,同時也是早期lig++的主要作者,以及DLmalloc的作者。我后面討論內(nèi)存管理的時候還要提到他)精心編寫,并且由java社區(qū)的許多專家仔細評審測試之后才發(fā)布的。

現(xiàn)在來討論上次提到的并發(fā)FIFO,其實現(xiàn)需要一些特殊的技巧。我上次說要實現(xiàn)單線程讀單線程寫的FIFO,但是這里我們先來討論一般的并發(fā)FIFO。

我們知道,傳統(tǒng)的生產(chǎn)者——消費者問題,通常是使用一個共享的緩沖區(qū)來交換數(shù)據(jù)的,生產(chǎn)者和消費者各自有對應(yīng)的指針,在生產(chǎn)或者消費的時候相應(yīng)地移動。如果達到了緩沖區(qū)的邊界則回繞。如果生產(chǎn)者指針追上消費者指針,則表明緩沖區(qū)滿了;如果消費者指針追上生產(chǎn)者指針,則表明緩沖區(qū)空了。問題在于,為了防止在緩沖區(qū)滿的時候插入數(shù)據(jù),或者在緩沖區(qū)空的時候刪除數(shù)據(jù),生產(chǎn)者或者消費者的每一次插入或者刪除數(shù)據(jù)操作,都必須同時訪問這兩個指針,這就帶來了不必要的同步。

在單核處理器上,共享緩沖區(qū)方式非常高效,并且具有固定的空間開銷(有時候你需要保守地估計一個比較大的數(shù)值)。但是在多核處理器上(或者SMP系統(tǒng)中),如果要實現(xiàn)并發(fā)的FIFO,就必須摒棄這種方式。使用單鏈表而不是共享緩沖區(qū)就可以避開這個問題,這是第一個技巧。

第二個技巧關(guān)系到鏈表的使用方向。一般使用鏈表,其插入或者刪除節(jié)點的位置是任意的。但是把鏈表作為FIFO使用,則只能也只需要在兩端操作。需要注意的是這時候必須從尾部TAIL插入新的節(jié)點,而從頭部HEAD刪除節(jié)點。否則從尾部刪除節(jié)點之后,無從得知新的尾部在哪里,除非從頭部遍歷。這樣做的好處是,插入或者刪除都只涉及到一個節(jié)點。插入的時候,只要讓新創(chuàng)建的節(jié)點包含所需要插入的數(shù)據(jù),并且其后繼(下一個節(jié)點)為NULL;再讓當前尾部的節(jié)點的后繼從NULL變成這個新節(jié)點,這個新節(jié)點也就變成了新的尾部節(jié)點(這里的操作順序很關(guān)鍵)。刪除的時候,則檢查當前頭部節(jié)點的后繼NEXT是否NULL。若是,表明FIFO是空的;否則,取NEXT所包含的數(shù)據(jù)來使用(是的,是NEXT而不是當前頭部節(jié)點所包含的數(shù)據(jù),參看下一個技巧和不變式),并把該數(shù)據(jù)從NEXT中刪除,而NEXT也成為新的頭部節(jié)點。(沒有配圖,各位請自己想象一下)

最后一個技巧:為了隔離對頭部和尾部的訪問,我們需要一個空節(jié)點N(不包含數(shù)據(jù)的有效節(jié)點),其下一個節(jié)點為NULL;并且引入HEAD和TAIL。在開始的時候,HEAD和TAIL都等于N。插入和刪除數(shù)據(jù)的過程上面已經(jīng)講過了,這里講一下不變式。

第一個不變式:頭部節(jié)點總是空的(不包含數(shù)據(jù))。在FIFO初始化的時候這是成立的。之后的插入操作不改變頭部節(jié)點,因此對不變式?jīng)]有影響。而對于刪除操作,則每一個新頭部節(jié)點的數(shù)據(jù)都已經(jīng)在它成為新的頭部節(jié)點的時候被刪除(取用)了。

第二個不變式:插入和刪除操作沒有數(shù)據(jù)沖突,也就是說,插入線程和刪除線程不會同時讀寫同一項數(shù)據(jù)(不是節(jié)點)。我們只需要考慮FIFO為空,即相當于剛剛完成初始化之后的情況。對于空節(jié)點N,插入操作改變其后繼,刪除操作則檢查其后繼。只要插入線程保證先讓新節(jié)點包含數(shù)據(jù)再把新節(jié)點插入鏈表(也就是不能先插入空節(jié)點,再往節(jié)點中填入數(shù)據(jù)),那么刪除線程就不會拿到空的節(jié)點。我們看到,唯一可能發(fā)生爭用的地方就是N的后繼指針,插入線程只要在更新N的后繼指針之前準備好其它相關(guān)數(shù)據(jù)和設(shè)置即可。

這意味著,如果能夠做到:1)一個線程對數(shù)據(jù)的更新能夠被另外一個線程即刻看到;2)對數(shù)據(jù)的讀或者寫(更新和讀取N的后繼指針)都是原子的;3)指令沒有被亂序執(zhí)行。那么在單線程讀單線程寫的情況下,甚至不需要使用鎖就可以安全地完成并發(fā)FIFO;如果有多個生產(chǎn)者線程,則增加一個生產(chǎn)者鎖;如果有多個消費者線程,則可以增加一個消費者鎖。也就是說,可以有四種組合。

但是實際情況遠非如此。對于2)是容易滿足的,因為現(xiàn)代通用處理器上32位數(shù)據(jù)的讀或者寫通常都是原子的。對于1),則取決于系統(tǒng)的內(nèi)存模型:在強內(nèi)存模型如C/C++中是滿足的,在弱內(nèi)存模型如Java中則不然。但是主要的問題還在于3)。由于指令的亂序執(zhí)行,第二個不變式所需要的保證很可能被破壞,即使代碼確實是那樣寫的。因此鎖是必不可少的,因為加鎖的同時還會插入內(nèi)存屏障。

這樣看來,上次說的SRSW并發(fā)FIFO就沒有特別的意義了。干脆就用兩個鎖分別對應(yīng)生產(chǎn)者和消費者,而并不限制生產(chǎn)者或者消費者的數(shù)量:T_LOCK和H_LOCK。在插入新建節(jié)點到鏈表尾部的時候使用T_LOCK,而在對頭部操作的時候使用H_LOCK。


具體的代碼這里先不給了。這里的算法不是我發(fā)明的,而是來自Maged M. Michael 和 Michael L. Scott的Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms。請參考其雙鎖算法的偽碼。

現(xiàn)在來討論游戲消息的傳送。在一個網(wǎng)游的運營成本中,帶寬費用應(yīng)該是很大的一塊。因此如何高效編碼以及收發(fā)消息就成為節(jié)省運營成本的關(guān)鍵。這里面能做很多文章。

首先是一個基本的判斷:隨著處理器的計算能力不斷提高,以及多核的日益普及,在消息的編碼以及收發(fā)環(huán)節(jié),CPU資源將不會成為瓶頸。相對的,應(yīng)該千方百計考慮如何在保證游戲正常運行的前提下,降低不必要的通信開銷。也就是說,可以對游戲中的消息進行一些比較復(fù)雜的編碼。

那么游戲中都有哪些消息?我們知道聊天和語音消息優(yōu)先級比較低,而且可以通過專門的服務(wù)器來處理。真正比較關(guān)鍵、能夠影響玩家的游戲體驗的,是那些狀態(tài)變更、動作、玩家之間或者玩家和服務(wù)器/NPC之間的實時交互的消息。尤其是,這些消息的傳送有嚴格的時序要求。如果一個玩家先看到自己的角色被砍死,然后才看到對方發(fā)出來的攻擊動作,甚至根本沒有看到對方有什么動作,他/她肯定會憤憤不平。因此,消息系統(tǒng)必須保證每一條消息的及時傳遞,并且不能打亂它們之間的順序。

這意味著,每一條消息必須有明確的邊界。也就是說,收到一條消息之后,接收方必須能夠明確這條消息有多少個字節(jié)。這是一條顯而易見的要求。但是大概是出于慣性,在實踐中它常常變?yōu)橄⒕幋a中的長度字段。

這無疑是一種浪費。很多消息的長度是固定的,僅僅靠檢查其消息類型就可以了解其邊界。變長消息的處理后面會討論。我這里并不是說要把具體的游戲邏輯與網(wǎng)絡(luò)代碼混在一起。通過使用元數(shù)據(jù)就可以有效的把網(wǎng)絡(luò)代碼跟具體的游戲邏輯有效隔離開來。關(guān)于元數(shù)據(jù)的使用后面也會詳加探討。今天時間不多了,下面討論消息類型的編碼作為結(jié)束。

通常一個字節(jié)會被用來編碼消息的類型,以方便接收方的解碼。但是我們知道,游戲中并不是每種類型的消息的傳送頻率都是一樣的。事實上,我們知道哪些消息會被大量發(fā)送,哪些消息的頻率會低很多,而另外一些消息,一天也不會有幾條。明乎此,就可以采用非對稱的編碼方式來編碼消息的類型。這就是Huffman編碼。對于占據(jù)了絕大部分通信量的狀態(tài)變更消息而言,即使每條消息節(jié)省下半個字節(jié),也是非常劃算的。以我的經(jīng)驗,一臺普通PC可以作為服務(wù)器支持2000人同時在線的實時動作類游戲,消息通量是每秒10000條;如果一個服務(wù)集群有5臺處理器,那么就相當于節(jié)省了200kbps的帶寬。這還僅僅是從消息類型編碼方面榨取的。當然,Huffman編碼的解碼是比較麻煩的,效率也會低一些。但是正如前面所指出的,這部分的運行開銷并不會造成性能瓶頸。