《枪神纪》负载均衡问题、策略与优化
一 审视现状(优化前)
图1枪神纪简化架构图(简化版)
背景介绍: 枪神纪是一款第三人称炫酷射击游戏，服务器采用分区分服的方式，目前规划一个大区承载20w人。客户端使用虚幻3，服务器的单局进程使用虚幻3专属服务器[1]。
公司内诸多ACG类游戏都采用了Lobby + DBSvr + 单局进程的方式。例如CF, LOL,逆战[2], 枪神纪等。这类架构的游戏的瓶颈往往在承载主要游戏逻辑的单局进程上(基本上都是CPU Bound)。 据了解，承载单局进程的单物理机承载人数较低，均不超过1000人。如何管理这些负载较高的单局服务器成为关键。这里对我在枪神纪所做的负载均衡工作进行介绍。
1、优化前负载均衡策略
架构: 如图1所示，枪神纪采用的是很典型的星型拓扑的结构，优点很明显：架构清晰，消息流程简单健壮。缺点也很明显，proxy本身不理解消息，不适宜做复杂的负载均衡策略，不能及早拒绝。同时为了做高可用，存在多个proxy进程，负载视图不唯一。
均衡方式: DSA上报负载，proxy根据负载进行排序，在负载较低的50%以内的DSA中随机选取一个服务器。
2、优化前的问题
1） 外网玩家经常喊卡，CPU有抖动现象。
2） 对有问题玩家不能有效跟踪，DS机器太多，单局太多，很难跟踪。
3） 不能有效启动stat工具，为客户端优化提供方向和指引。
4） 负载收敛慢，不同步，从图2可以看到CPU使用率走势不同。
图2 优化前两台单局服务器CPU使用率走势
分析: 目前架构不适宜做较为复杂的均衡策略，没有做到尽早拒绝。在50%以内的服务器中随机选取忽略了两个因素: 1）拉起DS间隔对服务质量的影响 2) 以随机对随机的方式一般情况下可以获得均衡的结果。负载最小的DSA是以同等几率被选中，例如在新增加一台或少量DSA这样的情形下，不能快速的将整个体系进行均衡化。
二、优化方案
图3 优化后架构图(简化版)
2.1、架构调整
前面分析了在proxy上做负载均衡的问题，很自然的很想到增加专门的负载均衡服务器，在枪神纪，称之为DSCenter, 不仅解决负载不均衡的问题， 同时解耦GameSvr和DSAgent的复杂关系(后续的双线服以及跨IDC部署)。
接下来介绍在做DSC过程中的几个挑战:
1) 性能: 为了适应单大区更多人数负载(甚至是全区全服的需求)，在大量后端单局服务器DSAgent秒级上报负载的情形下，以高效的数据结构等方式来管理分配负载。
2) 单点问题: 依赖Proxy服务器使用Master-Slave的路由方式进行高可用。后面会有专门的文章[3]来介绍。
3) 负载指数的选择， 仅仅靠CPU使用率可以吗？
4) 负载策略的选择， 公司内部有多种负载策略， 可它们适合枪神纪的应用场景吗?
2.2、如何进行O(1)的管理
前面提到要管理诸多的后端单局服务器的秒级上报，那么怎么进行高效管理成为一个问题，依靠单据服务器的服务器ID（非连续），使用红黑树最好的时间复杂度也只能是O(nlgn),既然比较排序不行，就考虑类似基数排序的方式，这就要求排序子连续且紧凑。这里采用挑战-响应的方式分配连续ID，进行了O(1)管理，分配时序如图4所示:
图4 挑战响应分配Nonce及上报负载时序
2.3、负载指数的选择
负载均衡公司内部讨论的比较多，但是负载指数选择讨论的比较少。通过调查L5[4], CMLB[5], 即通中转系统[6]的负载指数选择，发现互联网应用采用较多的是连接数和响应时间，成功率等。那么具体到游戏应用更进一步枪神纪的应用场景应该采用什么作为负载指数？既然是CPU Bound的应用，那么使用CPU使用率作为负载指数可以吗？答案是否。因为CPU Bound和Load Bound是可以转化的，例如枪神纪7.17当天玩家因为引导，开启了大量一个人的单局，CPU使用率很低，但是Load极高，直接转化为Load Bound。通过阅读文献【7】和【8】，并做实验验证，使用CPU Running Queue Length作为指数优于使用CPU使用率。
同时，可用内存也是一个重要监控内容，内存目前不是瓶颈，但是一旦消耗到一定阀值，就会出现Page Cache下降，继而出现Swap，导致进程启动时间过长，系统反应慢。
目前，采用CPU QL作为主要指标，兼顾使用率以及可用内存，当后两者超过一定阀值时，负载指数直接置为最大。同时为了减少某些突发情形，负载指数采用了平缓化操作。
2.4、负载策略的选择
负载策略有多种，目前用的比较多的有以下几种：
1) Round-robin. 轮转方式，这种方式假定所有服务器能力相同，应用的单次服务负载接近，显然不适合。
2) Weighted round-robin. 加权轮转的方式解决1)的缺陷，公司的L5[4]即采用了这种方式，在枪神纪的应用场景中需要考虑另外的因素，在1秒内不允许同时选择同一台后端服务器多次[9]，这种方式不适合。
3) Weighted random. 加权随机轮转（即通中转系统[6]），最早枪神纪采用这种方式，同样没有考虑2)中提及的场景。此外，这种方式负载收敛的比较慢，当系统中加入新的服务器时，会较为缓慢的达到负载均衡。这里需要指出的是L5的同事考虑过3）的方式，得出了等价的结论。
通过分析三种策略，并结合枪神纪的场景，提出了Least Load + Last Serve Time的负载方式，即为选取目前系统中1s内未服务过的负载最小服务器的方式，较好的解决了负载均衡的问题。
2.5、建立沙箱及染色
沙箱[10]: 为了对某些单局和地图进行剖析(非常消耗资源)，同时不影响外网玩家的正常体验，在DSCenter上设置沙箱服务器，在负载允许的情况下，路由指定模式和地图到沙箱服务器上，解决了性能剖析的问题。
染色: 外网经常会出现玩家连接不上单局服务器、断连，结算错误等等一系列的问题，为了快速追踪玩家，对关键路径上的行为对玩家进行染色，解决了追踪的问题。
2.6、优化后的效果
外网单局服务器的使用率走势基本相同，也就是负载基本均衡了。同时因为兼顾了进程启动等因素，因为服务器因素喊卡的现象减少了。
2.7、不足和未来的工作
不足:
1） 评价机制: 对负载是否均衡只是通过TNM2平台的走势和论坛反馈等情形，进行了定性分析，后续需要通过响应时间等进行定量分析。
2） 吞吐考量: 目前考虑单服承载较多，考虑玩家体验较少，没有考虑系统负载和玩家体验(主要是响应时间)之间的拐点[8]什么点出现。后端服务器在何时，可以得到负载和玩家体验的最佳折衷。
【1】 daemonhu 枪神纪后台UE3 DS优化小结
【2】 jiantang GDOC -稳定重于泰山—TGame服务器分享交流
【3】 daemonhu 基于Proxy的Master-Slave高可用方案.
【4】 lipingcheng L5开发背景以及算法说明
【5】 CMLB http://pub.code.oa.com/project/sourcecode?projectName=CMLB
【6】 Roxwang 即通中转系统
【7】 Load Indices – Past, Present and Future
【8】 Cary Millsap Thinking Clearly about Performance
【9】 Daemonhu虚幻3 DS进程启动时间优化总结
【10】Sandbox http://en.wikipedia.org/wiki/Sandbox_%28computer_security%29