【开发日志补全计划】更加平衡的宇宙

原作者：CCP Prism X
原文：http://community.eveonline.com/news/dev-blogs/building-a-balanced-universe/

 

    大家好，我是CCP Prism X，天秤座。

 

   《奥德赛》版本上线后许多新玩家涌入了EVE宇宙追寻梦想，这其实是一件很值得高兴的事，我们理应大肆庆祝才对。不过呢，这次新玩家的流入如此迅猛，几乎塞爆了整个帝国领地，让我们开始有点担心起来。新伊甸中的居民如此之多，每时每刻都在做着许许多多不同的事情，让我们的CPU核心（下文会称为“节点”）压力山大，帝国的多个星系中都出现了时间膨胀现象。如果你在0.0地区生活那时间膨胀没什么要紧，但如果你独自一人在某个星系做任务时突然发现周围的一切都像进入了子弹时间一般慢吞吞，那你不会高兴的。

 

    帝国星系按理说应该对高负载事先留有余地，不应该出现时间膨胀才是，一旦发生了膨胀，我们的静态服务器集群重构机制最起码应该阻止问题再次发生。我们会按照预估的负载情况在服务器启动时将星系分配到不同节点，如果预估正确的话重构机制应该会正常发挥作用。但如果同一星系反复被分配到一个承载了太多星系的节点上，它的运作就开始不正常了，具体原因我们也不十分清楚。

 

    第一步：找出问题所在

    刚才我没有提到星系重构机制的一个重要特征：同一星座内的星系往往被分配到同一节点上，完全不顾这是否是目前最佳的负载分配方式，这导致了不同节点间负载差异巨大，而重构机制应该是尽可能均分负载才对。另外，这一行为并不会超出星座范畴，所以一个节点可以承载两个完整的星座，但很可能一个在最南边一个在最北边。所以在南边那个星座发生的大规模会战也会让北边那个星座遭遇严重的时间膨胀，生活在当地的玩家一定很不高兴。

 

    这是一幅旧系统中星系节点分布的虚拟化视图（这是3D转印2D图像所以有点歪歪扭扭的就不要在意啦），同一颜色的星系位于同一节点上。你一定会发现这和一块擦颜料的破布差不多，各种颜色之间基本没什么关联。我标出的两个红圈中的星系其实位于同一节点上，你看看这有多远：

 

 

    下图进一步说明了过去这种负载分配有多糟糕，节点之间的负载差异令人惊讶，你可以看看图中的差异值有多大：

 

 

 

    那么我们为什么当初以星座为划分节点的基础单位呢？那是因为很久以前我们预计由于网络延迟的存在，跨节点的星门跳跃要比节点内的占用更多资源。现在我们发现这种假设完全不对，跨节点跳跃其实比节点内跳跃还省资源。星门跳跃这一过程需要将玩家从一个星系中移除，然后再放到另一个星系中，而将这一过程均分给两个节点要比在同一节点内发生负载低。

 

    认识到这一点之后，我们决定首先要打破星系抱团分布的现状，星系应该只按照节点的负载情况来分布，这会使服务器负载均衡许多。不过尽管我们重新分布了服务器，时间膨胀情况却比之前更严重了。这些星系基本处于半随机分布状态，全不顾地缘因素，所以还是会出现“南方打仗，北方遭殃”的情况。所以我们还得从头再来！

 

    第二步：解决问题

    我们得想个办法既能均衡节点负载，又能保证同一节点上的星系彼此临近。我们不想因为后一点原因使得服务器重构的时间延长，所以干脆趁此机会将旧的T-SQL代码用Python重新编写。而这一举动意外地成为了整个工作的关键点，因为这样一种拥有众多支持工具的程序化语言非常适合解决这种程序化的问题，比之前那种限制繁多的关系式语言强得多。

 

    Python的使用让解决问题变得容易起来。我们尝试将一片星系按照设定好的坐标来划分，这样分成的部分比重相似，而且互相临近。如果你将任意坐标星系一分为二，两部分将会紧密相连，这就解决了上面说过的地缘性问题。这也同时保证了两部分的负载基本相当，所以剩下的问题就只是如何调整这条分割线在哪里了。这并不困难，只需要将分割线向负载较重的那一半移动一定距离，然后下一次移动距离减半，以此类推。理论上我们会在最佳分割处左右摇摆直到最终找到确切地点。当然这只是理论上，我们也并没有想找出最最准确的解决方案，只要在最短时间内找到足够好的方案就可以了。

 

    下图可以帮你理解这个过程。圆圈代表了一大片星系，我并没有将它们一个个标出来，只要最后的划分使负载尽可能均衡就行了。

 

 

 

    我们首先要将整个宇宙划分为两大块，然后挑负载高的那个再分一次，然后在三个中选负载高的再来一次，这样一次次重复，直到数量与我们现有的服务器节点数量相等，然后就可以向数据库中写入节点分布并启动服务器了。

 

    为了便于理解我准备了几张图，不过头三步只是对帝国领地的划分，是用来帮助你理解概念的，不要在意细节。最后一幅图是最终的宇宙节点划分，你可以和之前那幅图比较一下。

 

    帝国初始状态：

 

 

 

    第一次划分后，两部分不一样大小是因为实际上并不是所有的服务器都负载平均的：

 

 

 

    第七次划分后：

 

 

 

    最终结果，看看现在颜色统一多了吧：

 

 

 

    第三步：最终解决问题

    这就是我们原计划在《绝地反击》更新前几周对服务器集群进行的重构。如果你对计算机知识有一定了解就应该能看出来，要想让服务器负载均衡，节点的数量必须是偶数，否则就会不平衡。要想达到完美平衡就需要足够多的节点，不然上一层的节点负载就会是下一层节点负载的两倍。

 

    这幅图直观地说明了4个节点比3个节点好在哪里。当然这只是理想状况，我们并不指望所有节点负载达到完美平衡。

 

 

 

    这样做的结果是划分更不均衡了。下图中0.0地区的数据看起来好些了，但是帝国节点的差异仍然很大。不过至少CPU最低使用率不是0了。内存占用的数据比之前更糟，不过CPU使用确实已做到了均衡。

 

 

 

    很明显看起来这里的最佳分配方式应该是每个节点负载的33%，但是你也看到了上面所说的漂亮算法在这里完全不起效。不过既然知道了只要节点数量是偶数就没错，那就坚持推行下去！我们当然可以强制星系节点的数量为偶数，但这是人为限制，尤其是任何十进制数字都可以用二进制数字来表示，那就把上面的二进制树换为偶数节点然后再次计算。

 

    下图是一种比三个节点更复杂些的例子：

 

 

 

    这个方法足够简单，可以尽量少修改初始方案的代码。那个方案已经使用了将坐标星系划分为两个负载均衡部分的方法，那让它划分为两个X/Y部分也不是什么大问题。

 

    用这种新方法重新划分前面使用的数据，我们得到了下面的结果，看起来相当均衡了：

 

 

 

    CPU占用的差异也有极大改观！我们会马上实施这一计划。

 

 

 

    第四步：写篇日志

    一个更加均衡的宇宙就这样诞生了。

 

    就这么多了，感谢收看！