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

網游服務器的特點是:

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

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

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

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

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

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

這時候就需要一種支持并發的數據結構,下面稱之為ConcurrentFIFO。

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

現在來討論游戲消息的傳送。在一個網游的運營成本中,帶寬費用應該是很大的一塊。因此如何高效編碼以及收發消息就成為節省運營成本的關鍵。這里面能做很多文章。

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

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

這意味著,每一條消息必須有明確的邊界。也就是說,收到一條消息之后,接收方必須能夠明確這條消息有多少個字節。這是一條顯而易見的要求。但是大概是出于慣性,在實踐中它常常變為消息編碼中的長度字段。

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

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