多人在线游戏服务器构架.docx

当今的网页游戏也越来越强调及时性，Server的负载过重也会造成Server与Client之间的不同步而导致延迟的出现，因Server较晚回应给Client，玩家的动作会因此变慢，因此造成很多玩家感觉游戏本身的游戏性较差而造成大量流失玩家，下面就将次问题讨论Server负载与解决之道!
传统线上游戏系统架构
主要有四种：Client/Server、Peer2Peer、Hybrid Client/Server及Multi-Server，不同的游戏拥有不同的架构，具体情况具体分析。
一、 Client/Server架构
N个Client连接至一个Server，Client只负责将玩家输入的信息发送给Server，Server处理大部分运算并将处理结果发回给Client。
优势：设计简单，玩家作弊情形不容易发生
劣势：由于整个运算都是在Server端进行，所以Server的运算能力及网络的流量是真个系统的瓶颈，当Client没有收到Server的任何信息前，Client无法对玩家的输入做出任何反应，画面也无法及时更新，因此容易因Server运算延迟或网络延迟，造成游戏的不流畅，一旦Server达到上线或者Client增多时，则必须考虑使用功能强大的Server来取代。
二、 P2P架构
点对点构架最大的优势就是及时性，没有Server的介入，所有消息都是参与游戏的电脑之间的做资料的传送。
这种构架避免了不必要的传送延迟，但是要在网络环境上建立点对点的架构，那么每台电脑必须对所哟的电脑先建立连线并做出传输的处理，因此电脑的运算能与连线的频宽会造成不小的负担。
三、 Hybrid Client/Server构架
此构架的特点在于Client可以自行推测目标的状态，并且可以立即针对玩家的输入做出反应。这种构架把整个虚拟世界当成一个由所有玩家共同享的资料库，Client可分到部分资料库类容，并且可以依照资料对玩家的输入与玩家在游戏中的状态进行推测，兵即时的反应给玩家。因此如果Client尚未收到Server信息，则Client端依旧可以进行游戏，但是最终数据的决定全仍然掌握咋Server中，如果Client的自行计算结果与服务器的结果不相符合，则Server便会去修正Client的状态。此架构最大的问题在于网络延迟所带来的影响，若Client和Server之间传输延迟过大，则将会导致Client端所推测的资料库内容与Server端的资料库内容差距过大。
四、 Multi-Server架构
早起的mmorpg游戏是有单一的Server负责整个游戏的内容，由于是单一的Server，因此游戏中能够容纳的线上人数及玩家间的互动会受到限制。而在Multi-Server构架中，通过每一个Server负责一个部分的游戏的内容，但是在不同的Server上玩家长处于不同的游戏世界里，因此无法互动，为了要提高系统整体的效能有效利用系统的运算及频宽的资源，一半以空间切割的方式分配Server权限范围及适当划分Server负责的工作，是不同的Server负责不同区域间的玩家，因此能支持更多的线上玩家。
目前mmorpg逐渐采用Multi-Server方式来减少Server的负载以及减轻网络的频宽限制。目前使用的Multi-Server分工的技术，大多采用空间切割的上市将虚拟世界的地图切成跟Server同等数量的片段，再将地图的片段分配给每一台Server。当玩家靠近地图片段的边界时，玩家所在的Server会通知临近的地图片段的Server，那么在最佳的情况下网络流量在这两个Server之间为零流量，没有玩家通过这两个Server，而最差的情况为O（m^n），n为玩家的数量，m为Server的数量。
MMORPG负载均衡机制
1. 静态分布玩家到服务器
平均分配玩家给每个Server，使每个Server有相同数量的玩家。这种方法的优点是算法简单，但玩家在地图上移动，因此过一段时间，最差的情况下，Server之间可能有大量的网络流量，因为当玩家在完成一个动作后，所有的Server必须获得另一个Server的玩家数据，而其附近的玩家皆在不同的Server上，如此依赖，每个玩家的一个动作需要传送消息到不同的Server上，将造成communication的极大负担。
2. 静态分配地图片段到服务器
利用空间切割的方式将虚拟世界切割成和Server同等数量的地图片段，再将这些地图片段分配给每一个Server负责，然后再有一个Dispacher Server负责将每一个玩家分配到所对应的Server上去，但由于玩家会在地图上移动，因此时间一久，在最差情况下，玩家可能都到同一个Server的地图片段上，这样当初的负载平衡就完全被破坏了。
3. 动态分配地图片段到服务器
静态分配地图片段至每个Server虽然可以减少Server间网络的频宽和负载，但必须使玩家在正确的分布地图上，玩家的位置是由玩家所操作的，因此会发生不可预料的问题，为了克服这类问题，将地图分切成更小的片段，然后动态的分配地图片段至Server上是需要的。然而这种方法要有效率，其关键在于如何切割地图片段，要切成何种几何形状的，该切成多少片段？传统的方法大都是切成正方形方块，切割数根据实际情况或模拟后作适当的处理。
四、 MMORPG动态负载机制实现
在上一片段中我们讨论了目前MMORPG所采用的负载平衡机制的架构，这里我们将提出我们的负载平衡方法，并且讨论如何动态以动态负载机制来调整线上游戏Server负载不平衡的现象。
1、 负载定义
多人在线游戏中Server端必须完成一下三个工作：
A. 接受Client端玩家的状态、移动及交谈的讯息
B. 处理玩家和NPC（Server控制的角色，如怪物，任务角色等）间的互动。
C. 更新虚拟世界状态
D. 将虚拟世界更新后的信息传送回Client端
以上工作当玩家越来越多的时候将话费更多的时间处理，因此Server上玩家暴增时，可能无法将信息及时的传送给每一个玩家，在这里我们把这四个工作所需要的时间定义成一个Server的负载；很明显的，在一个Multi-Server的MMORPG系统中，每一个Server的负载和它所负责的玩家个数成正比，因此，我们将每一个Server所负责的玩家的个数当成其负载的重要指标。
2、 负载平衡机制
在虚拟世界中，在非常多玩家的情况下，单一的Server必定会导致负载过重的现象，因此Multi-Server的架构无疑是必须采用的解决方式，但是前面我们已经讨论了Multi-Server负载平衡机制的优缺点，其中较为有效的是动态的分配地图至服务器，下面我们讨论如何实现这种机制。
首先我们必须解决如何切割游戏地图的问题，以及切成多少等分，因为这些将影响到在此机制下实现整个系统的效率。
我们考虑的原则有一下几点：
1. 尽量分散玩家到各个Server上。
2. 尽量较少玩家间的跨Server的信息传送。
3. 尽量避免玩家因为在地图上的位置移动而必须更换Server。
其中第一点是为了平均分摊Server的负载，第二点是为了减少Client间通讯的时间成本，第三点是为了减少Server间玩家资料的转移次数。
首先我们必须将地图切成跟Server个数相等的分数，使得每个Server至少有一份地图，然而因为玩家会在地图上移动，因此若每个Server负责一份地图，那么时间一久，必会导致负载开始不平衡。另一种方式是将地图切成若干个小等分，然后透过合理的方式将每个小等分分散到各个Server上。当然，和上述情况一样，时间一久仍会产生负载不平衡，然而这时候我们可以将负载太重的Server上的一部分地图片段再转移给其他负载较轻的Server上去，以达到负载平衡的目的。转移的时机是以Server的负载是否超过某一临界值，而转移的对象是可采用random polling的方式，也就是询问相邻的Server负载情况如何，是否可以接受额外的负载。
其次目前Multi-Server MMORPG大多采用将地图切割成正方形，然而应为正方形区域共有东、西、南、北、东南、东北、西北、西南等八个相邻的区域，如此会正佳玩家因为移动而转换区域的机会，因此另有系统采用正六角形切割，然而这种切割虽然相邻的区域减少到六个，但是其切割方式较为复杂，并且判断玩家位于哪个区域也较为耗时。另一可行方式是采用正三角形的切割，此方式的优点是切割方法和判断位置区域的演算法均较正六角形简单。
但是以上切割方式都有一共同的缺点，就是他们都为考虑到游戏地图的内容，也就是说不论地图的任何角落皆采用同样的切割方式，因此会很容易造成某个区域内没有任何的NPC，而另外一个区域内却包含数个NPC，而拥有NPC的区域通常是玩家驻足停留的地方，因此包含数个NPC的区域意味这其高负载的可能性较高，未包含任何NPC的区域意味着玩家不会长时间停留，大多属于路过性质，因此玩家转换Server的可能性便会较高。
为了解决上述切割的缺点，我们试图使用与地图内容相关的切割方式，我们以每个NPC为中心来切割地图区域，是的每个区域仅含有一个NPC，并且为避免玩家因暂时移动而跨出区域，我们希望每个区域中的NPC和其他的NPC要有适当的距离。
这里提供参考的分割方式如下:首先定出所有NPC的所在位置，然后对于每一个NPC和其他各个NPC间各画出一条垂直平分线，最后整理这些分割线而成的一个包围一个NPC的区域。该区域所形成的多边形中的一个边，即是该NPC和他的临近NPC间的等距离分割线。事实上，这些多边形区域的所有形成的图形是计算几何中的所有的Voronoi diagram，而各个区域称为Voronoi polygon。Voronoi diagram的正式定义如下：
我们给定一个N个点的集合S ，对所有属于S中的任意连个点Pi和Pj，PiPj线段的中央垂直分割线将平面分割成连个半平面，包含Pi的半平面我们以H（Pi,Pj）表示之，则所有在平面上靠经Pi的所有点所形成的区域V(i) = ∩i≠jH(pi,pj)，我们称V(i)为关于Pi的Voronoi diagram，表示成Vor（S）。如图

Voronoi diagram of NPCs
利用Voronoi diagram来分割游戏地图可以使得定义一个NPC区域的边界与其相邻的NPC间为相等距离，因而令玩家与该NPC互动时不会不经意的离开边界而到了另一个地图区域中，因此答复的降低了玩家在Server间转换的可能次数。
Voronoi diagram的建立并不如想象中的那么复杂费时，利用以上提供的演算法可以建立出Voronoi diagram，利用该演算法我们可以在给定N个借点的图形中以O（NlogN）的时间复杂度求的包含该节点的Voronoi diagram。在下一段中我们将模拟我们的负载分配方法，并且规划如何与其他传统的方法作效能的分析比较，最后将其实现在open source的Arriane server game server上。
五、 模拟环境和比较分析
在本节实验中我们与micro-cell切割方式做比较，所谓micro-cell是将游戏地图切割成小方格，之后再将这些小方格动态分配到各个server上。实验条件如下：
1. 地图坐标解析度：1000*1000
2. 模式：Voronoi切割，micro-cell切割（10*10，20*20格，配合NPC个数）
3.
4. 玩家移动模式：NPC-oriented（朝最近的NPC移动，停留500steps后离开）
5. Total number of steps：50000
6. Number of servers ：2，4，8，16
7. Number of players： 1000， 5000， 10000，15000，20000
8. Number of NPCs：100，400
计算超过临界值（threshold）需要做的负载分配(reallocation)的次数(note：每移动一次即检查是否需要做reallocation，负载分配下限为player平均数)

实验结果分析：
我们分别比较NPC个数为100和400时，Voronoi切割法和micro-cell切割法在player移动50000次中，所发生的负载中心分配的次数。如表1，表2

很明显的可以看出来，我们所提供的Voronoi分割方法是优于micro-cell的方法。我们另外将其中四个图标化成图形供比较：

我们特别指出的是，除了我们采用Voronoi切割方式之外，当在player移动的过程中，超过负载的情况发生时，我们首先是选取未超过负载的servers中负载比较低者，在将超过负载的server中的Voronoi区域依附负载人物大小，依序重新分配给低负载者，直到负载降低到players的平均数以下为止。
至于为什么玩家人数越多超过负载的次数反而减少呢？其原因是在于我们所选定的负载上限值，该值是依玩家人数的不同而不同，我们采用的负载上线值是，因此我们认为若服务器可以提供更多人上线时，其单机的功能应该是更强，否则不应该容许太多人同时上线，因此而调高其负载时的上线，换句话说，我们模拟中不同玩家人数所使用的伺服器的能力是不同的。人数越多，伺服器的能力应越强，否则可能无法负载过多的玩家上线。
六． 实战分析
1. 硬件架构
硬件设备方面，我们将尝试以6台PentiumIV PC搭配256Mb RAM，作为操作系统Windows XP，当成Server；每台Server间以10/100Mbps以太网路相连接，Client端硬件不受限制，所有Client经由路由器连接到Dispacher Server，再由Dispacher Server咨询World Database Server后，将该Client上的玩家依其所在的地图分配到负责该地图区域的Server上。如图：实验Multi-user系统构架图

2. 软件架构
采用Arianne这款游戏开发系统，Arianne是一套开放程序源码的的哦人线上角色扮演游戏引擎，目前Arranne可以支援Linux、MacOS以及Win32系统，它是以C、C++、Java、Python编制而成，我们可以修改该游戏所放出的源码，加入动态负载平衡的机制来达到我们实验的目的。Arranne主要包括两大模块程式，分别为Client及Server，如下图构架：Arianne架构图

当玩家产生事件时，时间会被传至GUI，GUI在获得命令之后再将此命令送至Black Box，再经由路由来改变虚拟世界，之后会回传讯息给其他相关的玩家。
3. 实验方法
在本文中我们在Arriane上实验我们提出的负载分配方法，实验中除了我们所提供的以Voronoi diagram方好似切割地图做动态分配外，另外加入两种传统方式以作比较，分别是与正方形切割发，切成四等份后，做静态分配给四台Server主机；另外一种是将游戏地图切成死的倍数个小正方形格子，然后动态方式分配给各个主机。
在灯座警惕啊分配多边形（第一种实验的Voronoi polygon）或小正方形（第三种实验）单位地图时，我们以该主机上所停留的玩家总数为负载标准，若某Server上玩家个数超过某以临界值时，即以random polling方式询问其他主机是否接受该主机上的单位多边形或小方格。
实验效绩分析将以各个玩家对于Server的回应时间之总和来衡量，我们将在后续的计划中分析在不同的负载量下，这三种实验的技校差异性，我们预计当时间增长和负载量增大时，动态分配方式优于静态分配，而同时我们将观察Voronoi diagram的分割方式在何种情况下会显示出他的有点。
4. 结论
大部分线上游戏采用单机Client/Server架构，在这样的架构下会有一些优势但是也存在一些限制，当有新地图、新消息欲在呢国家至游戏中的时候，只需要在一台Server上做修改即可，也因为是有一台Server控制管理，玩家的资料及游戏的公平行维持较为容易，但是另一方面当线上玩家数目逐渐增多时，Server端所需要运算能力小雨需求，便会有人数上的限制，若Server超过负荷则会导致延迟甚至宕机的现象产生。由于所有资料需要先送至Server做完处理后再送出，Server对外的频宽在不足的情况且多人连线时便会有延迟现象。若以空间分割的方式分配Server的权限范围与适当分配每一个Server负责的工作，那么便能减少Server的负载并支持更多的线上人数。
目前有许多机制被用来直言多人线上角色扮演游戏，在本文中我们详细讨论了我们所提出的Voronoi切割方式的有点，并且透过模拟的方式，对于我们提出的切割方法和其他的切割方法做多种指标的技校比较，并且以实验证明我们所提出的方法的却由于传统的方法。最后我们尝试透过修改开放源码的Arianne游戏引擎来实战我们提出的负载均衡方法。

七． 参考文献
[1] Christophe Diot, SPRINT ATL, Laurent Gautier, INRIA, “A Distributed Architecture
for Multiplayer Interactive Applications on the Internet”, 1999.
[2] Eric Cronin, Burton Filstrup, Anthony R. Kurc, Sugih Jamin, “An Efficient
Synchronization Mechanism for Mirrored Game Architectures, 2002
[3] 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 for
Supporting Interactive Games on the Internet”. Parallel and Distributed Simulation, 2002.
pp. 54-61.
[5] L. Gautier and C. Diot. “Distributed Synchronization for Multiplayer Interactive
Applications on the Internet”. Submitted for publication, October 1998.
[6] Age of King,
[7] Arrianne, http://www.arianne.cx/
[8] Hlaf-life,
[9] Ultima Online,
[10] 􀛦􀽆􀪝􀝾- Terazona􀌬,
[11] 􁈼􁛤 SDK, .tw/sdk/index.html
[12] DFC Intelligence,
[13] Franco P. Preparata and Michael lan Shamos, “Computational Geometry”,
Springer-Verlag, 1985
[14] Arrianne, , 2004
[15] Bart De Vleeschauwer, Bruno Van Den Bossche, Tom Verdickt, Filip De Turck, Bart
Dhoedt, Piet Demeester , “Multiplayer game architectures Dynamic microcell assignment
for massively multiplayer online gaming”, Proceedings of 4th ACM SIGCOMM workshop
on Network and system support for games NetGames, 2005