多人在线游戏服务器构架

当今的网页游戏也越来越强调及时性，Server的负载过重也会造成Server与Client之间的不同步而导致延迟的出现，因Server较晚回应给Client，玩家的动作会因此变慢，因此造成很多玩家感觉游戏本身的游戏性较差而造成大量流失玩家，下面就将次问题讨论Server负载与解决之道!传统线上游戏系统架构主要有四种：Client/Server、Peer2Peer、HybridClient/Server及Multi-Server，不同的游戏拥有不同的架构，具体情况具体分析。一、Client/Server架构N个Client连接至一个Server，Client只负责将玩家输入的信息发送给Server，Server处理大部分运算并将处理结果发回给Client。优势：设计简单，玩家作弊情形不容易发生劣势：由于整个运算都是在Server端进行，所以Server的运算能力及网络的流量是真个系统的瓶颈，当Client没有收到Server的任何信息前，Client无法对玩家的输入做出任何反应，画面也无法及时更新，因此容易因Server运算延迟或网络延迟，造成游戏的不流畅，一旦Server达到上线或者Client增多时，则必须考虑使用功能强大的Server来取代。二、P2P架构点对点构架最大的优势就是及时性，没有Server的介入，所有消息都是参与游戏的电脑之间的做资料的传送。这种构架避免了不必要的传送延迟，但是要在网络环境上建立点对点的架构，那么每台电脑必须对所哟的电脑先建立连线并做出传输的处理，因此电脑的运算能与连线的频宽会造成不小的负担。三、HybridClient/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负责，然后再有一个DispacherServer负责将每一个玩家分配到所对应的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的负载是否超过某一临界值，而转移的对象是可采用randompolling的方式，也就是询问相邻的Server负载情况如何，是否可以接受额外的负载。其次目前Multi-ServerMMORPG大多采用将地图切割成正方形，然而应为正方形区域共有东、西、南、北、东南、东北、西北、西南等八个相邻的区域，如此会正佳玩家因为移动而转换区域的机会，因此另有系统采用正六角形切割，然而这种切割虽然相邻的区域减少到六个，但是其切割方式较为复杂，并且判断玩家位于哪个区域也较为耗时。另一可行方式是采用正三角形的切割，此方式的优点是切割方法和判断位置区域的演算法均较正六角形简单。但是以上切割方式都有一共同的缺点，就是他们都为考虑到游戏地图的内容，也就是说不论地图的任何角落皆采用同样的切割方式，因此会很容易造成某个区域内没有任何的NPC，而另外一个区域内却包含数个NPC，而拥有NPC的区域通常是玩家驻足停留的地方，因此包含数个NPC的区域意味这其高负载的可能性较高，未包含任何NPC的区域意味着玩家不会长时间停留，大多属于路过性质，因此玩家转换Server的可能性便会较高。为了解决上述切割的缺点，我们试图使用与地图内容相关的切割方式，我们以每个NPC为中心来切割地图区域，是的每个区域仅含有一个NPC，并且为避免玩家因暂时移动而跨出区域，我们希望每个区域中的NPC和其他的NPC要有适当的距离。这里提供参考的分割方式如下:首先定出所有NPC的所在位置，然后对于每一个NPC和其他各个NPC间各画出一条垂直平分线，最后整理这些分割线而成的一个包围一个NPC的区域。该区域所形成的多边形中的一个边，即是该NPC和他的临近NPC间的等距离分割线。事实上，这些多边形区域的所有形成的图形是计算几何中的所有的Voronoidiagram，而各个区域称为Voronoipolygon。Voronoidiagram的正式定义如下：我们给定一个N个点的集合S，对所有属于S中的任意连个点Pi和Pj，PiPj线段的中央垂直分割线将平面分割成连个半平面，包含Pi的半平面我们以H（Pi,Pj）表示之，则所有在平面上靠经Pi的所有点所形成的区域V(i)=∩i≠jH(pi,pj)，我们称V(i)为关于Pi的VoronoiVoronoidiagram，表示成Vor（S）。如图VoronoidiagramofNPCs利用Voronoidiagram来分割游戏地图可以使得定义一个NPC区域的边界与其相邻的NPC间为相等距离，因而令玩家与该NPC互动时不会不经意的离开边界而到了另一个地图区域中，因此答复的降低了玩家在Server间转换的可能次数。Voronoidiagram的建立并不如想象中的那么复杂费时，利用以上提供的演算法可以建立出Voronoidiagram，利用该演算法我们可以在给定N个借点的图形中以O（NlogN）的时间复杂度求的包含该节点的Voronoidiagram。在下一段中我们将模拟我们的负载分配方法，并且规划如何与其他传统的方法作效能的分析比较，最后将其实现在opensource的Arrianeservergameserver上。五、模拟环境和比较分析在本节实验中我们与micro-cell切割方式做比较，所谓micro-cell是将游戏地图切割成小方格，之后再将这些小方格动态分配到各个server上。实验条件如下：1.地图坐标解析度：1000*10002.模式：Voronoi切割，micro-cell切割（10*10，20*20格，配合NPC个数）3.4.玩家移动模式：NPC-oriented（朝最近的NPC移动，停留500steps后离开）5.Totalnumberofsteps：500006.Numberofservers：2，4，8，167.Numberofplayers：1000，5000，10000，15000，200008.NumberofNPCs：100，400计算超过临界值（threshold）需要做的负载分配(reallocation)的次数(note：每移动一次即检查是否需要做reallocation，负载分配下限为player平均数)实验结果分析：我们分别比较NPC个数为100和400时，Voronoi切割法和micro-cell切割法在player移动50000次中，所发生的负载中心分配的次数。如表1，表2