多人在線游戲服務(wù)器構(gòu)架.doc

當(dāng)今的網(wǎng)頁游戲也越來越強(qiáng)調(diào)及時性，Server的負(fù)載過重也會造成Server與Client之間的不同步而導(dǎo)致延遲的出現(xiàn)，因Server較晚回應(yīng)給Client，玩家的動作會因此變慢，因此造成很多玩家感覺游戲本身的游戲性較差而造成大量流失玩家，下面就將次問題討論Server負(fù)載與解決之道!傳統(tǒng)線上游戲系統(tǒng)架構(gòu)主要有四種：Client/Server、Peer2Peer、Hybrid Client/Server及Multi-Server，不同的游戲擁有不同的架構(gòu)，具體情況具體分析。1、 Client/Server架構(gòu)N個Client連接至一個Server，Client只負(fù)責(zé)將玩家輸入的信息發(fā)送給Server，Server處理大部分運(yùn)算并將處理結(jié)果發(fā)回給Client。優(yōu)勢：設(shè)計簡單，玩家作弊情形不容易發(fā)生劣勢：由于整個運(yùn)算都是在Server端進(jìn)行，所以Server的運(yùn)算能力及網(wǎng)絡(luò)的流量是真?zhèn)€系統(tǒng)的瓶頸，當(dāng)Client沒有收到Server的任何信息前，Client無法對玩家的輸入做出任何反應(yīng)，畫面也無法及時更新，因此容易因Server運(yùn)算延遲或網(wǎng)絡(luò)延遲，造成游戲的不流暢，一旦Server達(dá)到上線或者Client增多時，則必須考慮使用功能強(qiáng)大的Server來取代。2、 P2P架構(gòu)點(diǎn)對點(diǎn)構(gòu)架最大的優(yōu)勢就是及時性，沒有Server的介入，所有消息都是參與游戲的電腦之間的做資料的傳送。這種構(gòu)架避免了不必要的傳送延遲，但是要在網(wǎng)絡(luò)環(huán)境上建立點(diǎn)對點(diǎn)的架構(gòu)，那么每臺電腦必須對所喲的電腦先建立連線并做出傳輸?shù)奶幚?，因此電腦的運(yùn)算能與連線的頻寬會造成不小的負(fù)擔(dān)。3、 Hybrid Client/Server構(gòu)架此構(gòu)架的特點(diǎn)在于Client可以自行推測目標(biāo)的狀態(tài)，并且可以立即針對玩家的輸入做出反應(yīng)。這種構(gòu)架把整個虛擬世界當(dāng)成一個由所有玩家共同享的資料庫，Client可分到部分資料庫類容，并且可以依照資料對玩家的輸入與玩家在游戲中的狀態(tài)進(jìn)行推測，兵即時的反應(yīng)給玩家。因此如果Client尚未收到Server信息，則Client端依舊可以進(jìn)行游戲，但是最終數(shù)據(jù)的決定全仍然掌握咋Server中，如果Client的自行計算結(jié)果與服務(wù)器的結(jié)果不相符合，則Server便會去修正Client的狀態(tài)。此架構(gòu)最大的問題在于網(wǎng)絡(luò)延遲所帶來的影響，若Client和Server之間傳輸延遲過大，則將會導(dǎo)致Client端所推測的資料庫內(nèi)容與Server端的資料庫內(nèi)容差距過大。4、 Multi-Server架構(gòu)早起的mmorpg游戲是有單一的Server負(fù)責(zé)整個游戲的內(nèi)容，由于是單一的Server，因此游戲中能夠容納的線上人數(shù)及玩家間的互動會受到限制。而在Multi-Server構(gòu)架中，通過每一個Server負(fù)責(zé)一個部分的游戲的內(nèi)容，但是在不同的Server上玩家長處于不同的游戲世界里，因此無法互動，為了要提高系統(tǒng)整體的效能有效利用系統(tǒng)的運(yùn)算及頻寬的資源，一半以空間切割的方式分配Server權(quán)限范圍及適當(dāng)劃分Server負(fù)責(zé)的工作，是不同的Server負(fù)責(zé)不同區(qū)域間的玩家，因此能支持更多的線上玩家。目前mmorpg逐漸采用Multi-Server方式來減少Server的負(fù)載以及減輕網(wǎng)絡(luò)的頻寬限制。目前使用的Multi-Server分工的技術(shù)，大多采用空間切割的上市將虛擬世界的地圖切成跟Server同等數(shù)量的片段，再將地圖的片段分配給每一臺Server。當(dāng)玩家靠近地圖片段的邊界時，玩家所在的Server會通知臨近的地圖片段的Server，那么在最佳的情況下網(wǎng)絡(luò)流量在這兩個Server之間為零流量，沒有玩家通過這兩個Server，而最差的情況為O（mn），n為玩家的數(shù)量，m為Server的數(shù)量。MMORPG負(fù)載均衡機(jī)制1. 靜態(tài)分布玩家到服務(wù)器平均分配玩家給每個Server，使每個Server有相同數(shù)量的玩家。這種方法的優(yōu)點(diǎn)是算法簡單，但玩家在地圖上移動，因此過一段時間，最差的情況下，Server之間可能有大量的網(wǎng)絡(luò)流量，因?yàn)楫?dāng)玩家在完成一個動作后，所有的Server必須獲得另一個Server的玩家數(shù)據(jù)，而其附近的玩家皆在不同的Server上，如此依賴，每個玩家的一個動作需要傳送消息到不同的Server上，將造成communication的極大負(fù)擔(dān)。2. 靜態(tài)分配地圖片段到服務(wù)器利用空間切割的方式將虛擬世界切割成和Server同等數(shù)量的地圖片段，再將這些地圖片段分配給每一個Server負(fù)責(zé)，然后再有一個Dispacher Server負(fù)責(zé)將每一個玩家分配到所對應(yīng)的Server上去，但由于玩家會在地圖上移動，因此時間一久，在最差情況下，玩家可能都到同一個Server的地圖片段上，這樣當(dāng)初的負(fù)載平衡就完全被破壞了。3. 動態(tài)分配地圖片段到服務(wù)器靜態(tài)分配地圖片段至每個Server雖然可以減少Server間網(wǎng)絡(luò)的頻寬和負(fù)載，但必須使玩家在正確的分布地圖上，玩家的位置是由玩家所操作的，因此會發(fā)生不可預(yù)料的問題，為了克服這類問題，將地圖分切成更小的片段，然后動態(tài)的分配地圖片段至Server上是需要的。然而這種方法要有效率，其關(guān)鍵在于如何切割地圖片段，要切成何種幾何形狀的，該切成多少片段？傳統(tǒng)的方法大都是切成正方形方塊，切割數(shù)根據(jù)實(shí)際情況或模擬后作適當(dāng)?shù)奶幚怼?、 MMORPG動態(tài)負(fù)載機(jī)制實(shí)現(xiàn)在上一片段中我們討論了目前MMORPG所采用的負(fù)載平衡機(jī)制的架構(gòu)，這里我們將提出我們的負(fù)載平衡方法，并且討論如何動態(tài)以動態(tài)負(fù)載機(jī)制來調(diào)整線上游戲Server負(fù)載不平衡的現(xiàn)象。1、 負(fù)載定義多人在線游戲中Server端必須完成一下三個工作：A. 接受Client端玩家的狀態(tài)、移動及交談的訊息B. 處理玩家和NPC（Server控制的角色，如怪物，任務(wù)角色等）間的互動。C. 更新虛擬世界狀態(tài)D. 將虛擬世界更新后的信息傳送回Client端以上工作當(dāng)玩家越來越多的時候?qū)⒃捹M(fèi)更多的時間處理，因此Server上玩家暴增時，可能無法將信息及時的傳送給每一個玩家，在這里我們把這四個工作所需要的時間定義成一個Server的負(fù)載；很明顯的，在一個Multi-Server的MMORPG系統(tǒng)中，每一個Server的負(fù)載和它所負(fù)責(zé)的玩家個數(shù)成正比，因此，我們將每一個Server所負(fù)責(zé)的玩家的個數(shù)當(dāng)成其負(fù)載的重要指標(biāo)。2、 負(fù)載平衡機(jī)制在虛擬世界中，在非常多玩家的情況下，單一的Server必定會導(dǎo)致負(fù)載過重的現(xiàn)象，因此Multi-Server的架構(gòu)無疑是必須采用的解決方式，但是前面我們已經(jīng)討論了Multi-Server負(fù)載平衡機(jī)制的優(yōu)缺點(diǎn)，其中較為有效的是動態(tài)的分配地圖至服務(wù)器，下面我們討論如何實(shí)現(xiàn)這種機(jī)制。首先我們必須解決如何切割游戲地圖的問題，以及切成多少等分，因?yàn)檫@些將影響到在此機(jī)制下實(shí)現(xiàn)整個系統(tǒng)的效率。我們考慮的原則有一下幾點(diǎn)：1. 盡量分散玩家到各個Server上。2. 盡量較少玩家間的跨Server的信息傳送。3. 盡量避免玩家因?yàn)樵诘貓D上的位置移動而必須更換Server。其中第一點(diǎn)是為了平均分?jǐn)係erver的負(fù)載，第二點(diǎn)是為了減少Client間通訊的時間成本，第三點(diǎn)是為了減少Server間玩家資料的轉(zhuǎn)移次數(shù)。首先我們必須將地圖切成跟Server個數(shù)相等的分?jǐn)?shù)，使得每個Server至少有一份地圖，然而因?yàn)橥婕視诘貓D上移動，因此若每個Server負(fù)責(zé)一份地圖，那么時間一久，必會導(dǎo)致負(fù)載開始不平衡。另一種方式是將地圖切成若干個小等分，然后透過合理的方式將每個小等分分散到各個Server上。當(dāng)然，和上述情況一樣，時間一久仍會產(chǎn)生負(fù)載不平衡，然而這時候我們可以將負(fù)載太重的Server上的一部分地圖片段再轉(zhuǎn)移給其他負(fù)載較輕的Server上去，以達(dá)到負(fù)載平衡的目的。轉(zhuǎn)移的時機(jī)是以Server的負(fù)載是否超過某一臨界值，而轉(zhuǎn)移的對象是可采用random polling的方式，也就是詢問相鄰的Server負(fù)載情況如何，是否可以接受額外的負(fù)載。其次目前Multi-Server MMORPG大多采用將地圖切割成正方形，然而應(yīng)為正方形區(qū)域共有東、西、南、北、東南、東北、西北、西南等八個相鄰的區(qū)域，如此會正佳玩家因?yàn)橐苿佣D(zhuǎn)換區(qū)域的機(jī)會，因此另有系統(tǒng)采用正六角形切割，然而這種切割雖然相鄰的區(qū)域減少到六個，但是其切割方式較為復(fù)雜，并且判斷玩家位于哪個區(qū)域也較為耗時。另一可行方式是采用正三角形的切割，此方式的優(yōu)點(diǎn)是切割方法和判斷位置區(qū)域的演算法均較正六角形簡單。但是以上切割方式都有一共同的缺點(diǎn)，就是他們都為考慮到游戲地圖的內(nèi)容，也就是說不論地圖的任何角落皆采用同樣的切割方式，因此會很容易造成某個區(qū)域內(nèi)沒有任何的NPC，而另外一個區(qū)域內(nèi)卻包含數(shù)個NPC，而擁有NPC的區(qū)域通常是玩家駐足停留的地方，因此包含數(shù)個NPC的區(qū)域意味這其高負(fù)載的可能性較高，未包含任何NPC的區(qū)域意味著玩家不會長時間停留，大多屬于路過性質(zhì)，因此玩家轉(zhuǎn)換Server的可能性便會較高。為了解決上述切割的缺點(diǎn)，我們試圖使用與地圖內(nèi)容相關(guān)的切割方式，我們以每個NPC為中心來切割地圖區(qū)域，是的每個區(qū)域僅含有一個NPC，并且為避免玩家因暫時移動而跨出區(qū)域，我們希望每個區(qū)域中的NPC和其他的NPC要有適當(dāng)?shù)木嚯x。這里提供參考的分割方式如下:首先定出所有NPC的所在位置，然后對于每一個NPC和其他各個NPC間各畫出一條垂直平分線，最后整理這些分割線而成的一個包圍一個NPC的區(qū)域。該區(qū)域所形成的多邊形中的一個邊，即是該NPC和他的臨近NPC間的等距離分割線。事實(shí)上，這些多邊形區(qū)域的所有形成的圖形是計算幾何中的所有的Voronoi diagram，而各個區(qū)域稱為Voronoi polygon。Voronoi diagram的正式定義如下：我們給定一個N個點(diǎn)的集合S ，對所有屬于S中的任意連個點(diǎn)Pi和Pj，PiPj線段的中央垂直分割線將平面分割成連個半平面，包含Pi的半平面我們以H（Pi,Pj）表示之，則所有在平面上靠經(jīng)Pi的所有點(diǎn)所形成的區(qū)域V(i) = ijH(pi,pj)，我們稱V(i)為關(guān)于Pi的Voronoi diagram，表示成Vor（S）。如圖Voronoi diagram of NPCs利用Voronoi diagram來分割游戲地圖可以使得定義一個NPC區(qū)域的邊界與其相鄰的NPC間為相等距離，因而令玩家與該NPC互動時不會不經(jīng)意的離開邊界而到了另一個地圖區(qū)域中，因此答復(fù)的降低了玩家在Server間轉(zhuǎn)換的可能次數(shù)。Voronoi diagram的建立并不如想象中的那么復(fù)雜費(fèi)時，利用以上提供的演算法可以建立出Voronoi diagram，利用該演算法我們可以在給定N個借點(diǎn)的圖形中以O(shè)（NlogN）的時間復(fù)雜度求的包含該節(jié)點(diǎn)的Voronoi diagram。在下一段中我們將模擬我們的負(fù)載分配方法，并且規(guī)劃如何與其他傳統(tǒng)的方法作效能的分析比較，最后將其實(shí)現(xiàn)在open source的Arriane server game server上。5、 模擬環(huán)境和比較分析在本節(jié)實(shí)驗(yàn)中我們與micro-cell切割方式做比較，所謂micro-cell是將游戲地圖切割成小方格，之后再將這些小方格動態(tài)分配到各個server上。實(shí)驗(yàn)條件如下：1. 地圖坐標(biāo)解析度：1000*10002. 模式：Voronoi切割，micro-cell切割（10*10，20*20格，配合NPC個數(shù)）3.4. 玩家移動模式：NPC-oriented（朝最近的NPC移動，停留500steps后離開）5. Total number of steps：500006. Number of servers ：2，4，8，167. Number of players： 1000， 5000， 10000，15000，200008. Number of NPCs：100，400計算超過臨界值（threshold）需要做的負(fù)載分配(reallocation)的次數(shù)(note：每移動一次即檢查是否需要做reallocation，負(fù)載分配下限為player平均數(shù))實(shí)驗(yàn)結(jié)果分析：我們分別比較NPC個數(shù)為100和400時，Voronoi切割法和micro-cell切割法在player移動50000次中，所發(fā)生的負(fù)載中心分配的次數(shù)。如表1，表2很明顯的可以看出來，我們所提供的Voronoi分割方法是優(yōu)于micro-cell的方法。我們另外將其中四個圖標(biāo)化成圖形供比較：我們特別指出的是，除了我們采用Voronoi切割方式之外，當(dāng)在player移動的過程中，超過負(fù)載的情況發(fā)生時，我們首先是選取未超過負(fù)載的servers中負(fù)載比較低者，在將超過負(fù)載的server中的Voronoi區(qū)域依附負(fù)載人物大小，依序重新分配給低負(fù)載者，直到負(fù)載降低到players的平均數(shù)以下為止。至于為什么玩家人數(shù)越多超過負(fù)載的次數(shù)反而減少呢？其原因是在于我們所選定的負(fù)載上限值，該值是依玩家人數(shù)的不同而不同，我們采用的負(fù)載上線值是，因此我們認(rèn)為若服務(wù)器可以提供更多人上線時，其單機(jī)的功能應(yīng)該是更強(qiáng)，否則不應(yīng)該容許太多人同時上線，因此而調(diào)高其負(fù)載時的上線，換句話說，我們模擬中不同玩家人數(shù)所使用的伺服器的能力是不同的。人數(shù)越多，伺服器的能力應(yīng)越強(qiáng)，否則可能無法負(fù)載過多的玩家上線。6 實(shí)戰(zhàn)分析1. 硬件架構(gòu)硬件設(shè)備方面，我們將嘗試以6臺PentiumIV PC搭配256Mb RAM，作為操作系統(tǒng)Windows XP，當(dāng)成Server；每臺Server間以10/100Mbps以太網(wǎng)路相連接，Client端硬件不受限制，所有Client經(jīng)由路由器連接到Dispacher Server，再由Dispacher Server咨詢World Database Server后，將該Client上的玩家依其所在的地圖分配到負(fù)責(zé)該地圖區(qū)域的Server上。如圖：實(shí)驗(yàn)Multi-user系統(tǒng)構(gòu)架圖2. 軟件架構(gòu)采用Arianne這款游戲開發(fā)系統(tǒng)，Arianne是一套開放程序源碼的的哦人線上角色扮演游戲引擎，目前Arranne可以支援Linux、MacOS以及Win32系統(tǒng)，它是以C、C+、Java、Python編制而成，我們可以修改該游戲所放出的源碼，加入動態(tài)負(fù)載平衡的機(jī)制來達(dá)到我們實(shí)驗(yàn)的目的。Arranne主要包括兩大模塊程式，分別為Client及Server，如下圖構(gòu)架：Arianne架構(gòu)圖當(dāng)玩家產(chǎn)生事件時，時間會被傳至GUI，GUI在獲得命令之后再將此命令送至Black Box，再經(jīng)由路由來改變虛擬世界，之后會回傳訊息給其他相關(guān)的玩家。3. 實(shí)驗(yàn)方法在本文中我們在Arriane上實(shí)驗(yàn)我們提出的負(fù)載分配方法，實(shí)驗(yàn)中除了我們所提供的以Voronoi diagram方好似切割地圖做動態(tài)分配外，另外加入兩種傳統(tǒng)方式以作比較，分別是與正方形切割發(fā)，切成四等份后，做靜態(tài)分配給四臺Server主機(jī)；另外一種是將游戲地圖切成死的倍數(shù)個小正方形格子，然后動態(tài)方式分配給各個主機(jī)。在燈座警惕啊分配多邊形（第一種實(shí)驗(yàn)的Voronoi polygon）或小正方形（第三種實(shí)驗(yàn)）單位地圖時，我們以該主機(jī)上所停留的玩家總數(shù)為負(fù)載標(biāo)準(zhǔn)，若某Server上玩家個數(shù)超過某以臨界值時，即以random polling方式詢問其他主機(jī)是否接受該主機(jī)上的單位多邊形或小方格。實(shí)驗(yàn)效績分析將以各個玩家對于Server的回應(yīng)時間之總和來衡量，我們將在后續(xù)的計劃中分析在不同的負(fù)載量下，這三種實(shí)驗(yàn)的技校差異性，我們預(yù)計當(dāng)時間增長和負(fù)載量增大時，動態(tài)分配方式優(yōu)于靜態(tài)分配，而同時我們將觀察Voronoi diagram的分割方式在何種情況下會顯示出他的有點(diǎn)。4. 結(jié)論大部分線上游戲采用單機(jī)Client/Server架構(gòu)，在這樣的架構(gòu)下會有一些優(yōu)勢但是也存在一些限制，當(dāng)有新地圖、新消息欲在呢國家至游戲中的時候，只需要在一臺Server上做修改即可，也因?yàn)槭怯幸慌_Server控制管理，玩家的資料及游戲的公平行維持較為容易，但是另一方面當(dāng)線上玩家數(shù)目逐漸增多時，Server端所需要運(yùn)算能力小雨需求，便會有人數(shù)上的限制，若Server超過負(fù)荷則會導(dǎo)致延遲甚至宕機(jī)的現(xiàn)象產(chǎn)生。由于所有資料需要先送至Server做完處理后再送出，Server對外的頻寬在不足的情況且多人連線時便會有延遲現(xiàn)象。若以空間分割的方式分配Server的權(quán)限范圍與適當(dāng)分配每一個Server負(fù)責(zé)的工作，那么便能減少Server的負(fù)載并支持更多的線上人數(shù)。目前有許多機(jī)制被用來直言多人線上角色扮演游戲，在本文中我們詳細(xì)討論了我們所提出的Voronoi切割方式的有點(diǎn)，并且透過模擬的方式，對于我們提出的切割方法和其他的切割方法做多種指標(biāo)的技校比較，并且以實(shí)驗(yàn)證明我們所提出的方法的卻由于傳統(tǒng)的方法。最后我們嘗試透過修改開放源碼的Arianne游戲引擎來實(shí)戰(zhàn)我們提出的負(fù)載均衡方法。7 參考文獻(xiàn)1 Christophe Diot, SPRINT ATL, Laurent Gautier, INRIA, “A Distributed Architecturefor Multiplayer Interactive Applications on the Internet”, 1999.2 Eric Cronin, Burton Filstrup, Anthony R. Kurc, Sugih Jamin, “An EfficientSynchronization Mechanism for Mirrored Game Architectures, 20023 E. Cronin, B. Filstrup, and A.R. Kurc, “A distributed multiplayer game server system”,UM EECS589 Course Project Report.4 Wentong Cai; Xavier, P.; Turner, S.J.; Bu-Sung Lee “A Scalable Architecture forSupporting Interactive Games on the Internet”. Parallel and Distributed Simulation, 2002.pp. 54-61.5 L. Gautier and C. Diot. “Distributed Synchronization for Multiplayer I