« October 2012 | Main | December 2012 »

November 23, 2012

相位技术的实现

魔兽世界从巫妖王之怒那个版本开始完善了他的 相位 (Phasing) 技术。简单说,就是在场景的相同区域,不同的玩家根据一些条件(一般是任务进度)的不同,会感受到不同的环境:场景可以不同、能交互的 NPC 不同等等。

这个技术可以给玩家在 MMO 中带来许多以往在单机游戏中才能体验的融入感。在 wow 之前,许多游戏策划都曾经想过让玩家可以通过完成剧情改变游戏的环境,但苦于找不到好的表现方式。这或许是因为大部分游戏策划都在以现实世界为参考去考虑技术能够实现的可能性,而在这个微创新年代,没有摹本可以参考就没有了思路。但我有些奇怪的是,在 wow 把相位技术展现给世界已经超过 4 年了,为啥山寨大国还没有全力跟进呢?

莫非是因为这里面还真有什么技术难点?

以前没有认真思考过相位技术如何简单的实现。我们在这期里程碑里还没有把这个提上案子,但读到我们的策划已经编写了大量剧情,似乎没有相位技术或类似的东西就无法实现啊。许多情节写的跟小说一样,动不动就天亮了、环境变了、NPC 死了、人群散了、BOSS 复活了 …… 说起来好像 wow 里某个任务就是这样做的,我们以后天然就要支持相位技术没啥问题似的。

昨天晚上就这个问题跟 mike 同学讨论了一下,初步定了个方案。

据说原来在网易的一些同学还真认真讨论过相位技术如何实现,道听途说,我也不了解细节。大致说是希望放在 AOI 模块中解决一部分问题。就是让每个玩家的可见对象受底层模块的一些参数控制,他只能看到他能看到的景物。

也就是说,不同位面的 NPC 实际上全部存在于一个场景,只是被位面约束,可能不可见而已。

我们就这个可能的解决方案做了讨论,一致认为过于复杂了。相位技术不仅仅是要解决可见性问题,还需要解决互动问题。用这个方案的难点在于,即使我们可以在玩家对象上做一个可见性过滤(这倒是在我们现在的架构上,很容易实现),也很难去处理交互问题。比如释放一个 AOE 法术攻击一个区域内的对象,就需要给法术本身也设置位面影响。而玩家可以独立在一个服务内计算,将法术对象也独立出来就不太现实。这样做的结果会带来不可控的复杂性,以及很多性能问题。

所以我们觉得采用更纯粹的方案可能更好。不一定要完全和 wow 的一致,但能满足剧情任务表现的要求即可。

简单的方案是,如果一个场景因为上面的任务线的不同,而可能有不同的位面。那么、我们就实际去制作多个不同的场景(指服务器的配置)然后全部位面都独立启动起来。

指定一个主位面,它是覆盖全地图的。其它位面都有一定的影响区域。也就是说,次位面在地图大小上和主位面一样,只是布置的 NPC 对象不同,但一般只在一个较小区域上布置。

玩家会因为任务进度的关系进入次位面,但在次位面上移动超过影响区域就自动切回主位面。玩家处于不同位面实际上是处于不同的场景服务中。但这个切换的代价是相当之小的。首先客户端并不需要移动位置,也不需要加载场景。玩家不会感觉到停顿。服务器那边,相同地图的不同位面一定是在同一进程中,只是把绑定在玩家上的 agent 切换了交互 map 而已。

第一步我们暂时实现任务链对位面切换的影响,这样策划通过配置任务表格就可以切换到他们专门为任务配置的次位面中。区分主次位面,而不是等同对待,是为了配置规则简单,而非实现上的区别。

之后,我们需要制定一些基本规则,防止在相位穿帮时有一个明确的处理规范。当然策划在应用这个技术时也需要积累一些经验,考虑对一些 PvP 玩法的影响。

这次先写这么多记录一下想法,估计要到一个月后才会开始实现。

November 21, 2012

开发笔记(29) : agent 跨机 id 同步问题

我们的大部分设计是围绕单个进程进行的,所有的数据在进程内都可以方便的共享。只需要这些数据结构是线程安全的即可。

但最终,我们不会在单台机器上运营整个游戏服务器,所以还是要考虑玩家在不同物理机器间移动的问题。

虽然我们还没有开始进行跨机方面的开发,但是不少服务已经要开始考虑这个问题了。目前、每个玩家接入游戏服务器并认证完毕后,都会有一个 lua 虚拟机伴随他。也就是我称之为 agent 的东西。

agent 和场景服务 map 间会有高频率的互动,所以,我们必须要求 agent 和玩家所在 map 在同一个进程内。当玩家跳转到不在同一进程内的 map 上时,需要把 agent 迁移到对应的进程内。

迁移 agent 并不算难做:只需要把 agent 的数据持久化,然后在新的进程内启动起来即可。难点在于,新的 agent 的通讯 handle 变化了。为了性能考虑,我并不想实现一套跨机器的唯一 id 系统。那么,就需要解决一个问题:如果 handle 发生变化,如何通知持有这个 handle 的服务模块。

map 这样的服务是不需要持有远程 handle 的,所有它处理的 agent 一定和它同属一个进程内。但其它一些对通讯延迟要求不高的服务就不是这样了。比如队伍管理、聊天室等等。简单的做法是启用一套独立的 id 系统,但这套 id 系统不用放在底层去破坏底层的简洁性。但如果利用 skynet 固有提供的字符串名字机制,又觉得效率低下。( skynet 在设计服务别名系统的时候,没有打算为上千个名字去服务)

一个线程安全的 hash 表就可以达到目的。我开启了一个有 64K 个 slot 的 hash 表,以玩家 id 做索引,映射 agent 的 handle 。这是一个 C 模块,所以可以共享由不同的 lua 模块查询和更新。对于跨机服务,还是和跨机组播那样的老方法,在每台机器上启动一个代理服务,而系统中有一个唯一的中心管理服务。每当对应表更新后,就通知所有的机器上的 hash 表同步更新。

这个 hash 表在实现线程安全时,我曾经考虑做无锁的数据结构,但很难回避释放空闲节点的问题。没有 GC 的语言实现无锁 hash 表是很困难的。但从另一个角度优化锁却很简单:只需要给每个 slot 单独上锁,实际上冲突的可能性极低。


在考虑这个部分的实现时,我曾经考虑过另一个方案:不引入新的 id 系统,而是在 hash 表中记住所有 handle 的关联关系。比如 handle 1 迁移走变成 handle 2 后,就在 hash 表中记住 1 和 2 都映射为 2 。无论 agent 迁移几次,都可以从任何一个历史版本查询到现在的最新 handle 。做一个简单的估算,这个方案在空间消耗上也是可行的。查询速度应该在一个数量级。

不过我们的游戏在事实上已经有了一套玩家 id 系统,所以用额外的 id 系统做映射也是很自然的事情了。(后一种方案的好处是不必引入新的 id )

November 09, 2012

Lua 字节码与字符串的共享

我们的系统的应用场合比较特殊,在同一个进程内存在数千个 lua_State

Lua 的虚拟机占用的内存已经足够小了,但还是抗不住数量多啊。所以我希望有版本节约一些内存。

最想做的一件事情是把不同 lua_State 中相同的函数字节码合并起来共用一块内存。要做到这一点并不复杂。而且可以提高一些内存访问的效率。(因为大部分 lua 程序在并行执行相同的逻辑)

首先我们需要准备一个用来共享数据块的模块,它必须是线程安全的。因为既然分到了不同的 lua_State 就是想利用并发的优势。针对这个特定需求定制这样一个模块可以做到 lock-free 。

进程开始时初始化一个足够大的 hash 表,不要管 hash 冲突的问题,每个节点只需要初始化一次,这样可以最大可能的简化逻辑。就不必用锁了。

对每个可能需要共享的内存块,我们可以先计算 hash 值,然后比对 hash 表中是否有相同 hash 值的节点,然后做一次全文比较。如果相同,就可以直接引用以前的数据块。

如果已经存在相同 hash 值但内容不同的数据块,那么不要替换掉旧数据块(用 CAS 指令可以做到这点)。

在数据块上做一个标记区分这两种数据块,当释放数据块的时候,在 hash 表中的永远不要释放,不在 hash 表中的没有多个引用就可以释放了。

由于 hash 表中的值只可能为空,或是一个有唯一意义的值。且一旦被赋值后,就不可能更改(引用的内存也永不释放)。这个机制就不需要锁来保证并发安全了。由于 hash 表的大小有限,这套机制所占用的总内存也不可能无限增加,所以是可控的。


剩下个工作就是修改 lua 的虚拟机实现。我在 lobject.h 中给 Proto 结构增加了一个域标记其 opcode 是否被共享化。然后在 lparser.c 中,找到 close_func 这个函数,再构造完 opcode 的 buffer 后(可以同样处理的还有 lineinfo 这组调试信息),把指针传入前面的模块,并从 Lua 管理的内存中释放掉。最后设置标记表示 opcode 已经被复制到全局共享区。

在 lfunc.c 中的 luaF_freeproto 可以找到释放代码。当检查到共享标记时,改为通知共享模块去处理。

如果 lua 代码不是通过 parser 加载,那么还需要修改 lundump.c


可以被共享的数据必须符合的原则是,一旦够构造出来,就不会被修改。符合这个原则的数据还有 lua 中的字符串 TString 。

但我们需要先的 TString 做一点小改造。lua 直接把字符串内存附加在 TString 这样一个 GCObject 的内存后面。这会使得不同 lua_State 中的字符串继续完全相同,结构也会有差异。

简单的改法是给 TString 加一个指针,指向独立的内存块存放字符串内容。只需要修改 lobject.h 中的 getstr(ts) 宏就可以改变 lua 代码中所有访问字符串体的方式。注:这会损失一丁点性能。

然后修改 lstring.c 中的 createstrobj 函数,lstring.h 中的sizestring(s) 宏,以及 lgc.c 中的 freeobj 函数就大功告成了。


我在我们的系统上做了对比测试,平均每个 lua_State 可以节省下 500K 左右的内存,大部分是在 opcode 上节约下来的。这也和我们每个 lua 虚拟机中加载的代码量接近,证明这个方法是有效且被正确实现了。

我们每个 'lua_State` 占用 5 到 10 M 内存。所以大约节约了 10% 左右的内存,不算特别可观。以后还要在实际环境中评测。

考虑到日后一台主机上会有至少 2000 个 lua 虚拟机在运行,我认为省下 1G 的内存应该还是有意义的。尤其是这些是运行 lua 字节码最常访问到的部分,对 CPU cache 的利用很有好处。当然在现阶段只是臆测,过段时间再做细致的测试比较。


对有耐心读完的读者,这里放一个彩蛋 :)

最近有一点闲情,所以继续写了那本书两章。对,就是那本传说中的《Lua 源码欣赏》。上次提到它都是今年一月份的事情了。

依旧不保证它不会太监掉。我写起来才发现工程巨大啊,感觉至少还有 80% 的内容要写。为了让书中的细节不出错,需要反复校对源代码,比之前几次阅读 lua 的代码累多了。

开始动笔时,lua 还是 5.2.0 版,现在已经是 5.2.1 了,改动的位置不少。相比最初完整阅读 Lua 代码时的 Lua 5.0 以及后来再读时的 Lua 5.1 ,每次阅读都是新体验。

希望在 Lua 5.3 发布前能够完成。

November 01, 2012

开发笔记(28) : 重构优化

正如上一篇笔记 记载的,我们第 2 里程碑按计划在 9 月 30 日完成,但因为赶进度,有许多 bug 。性能方面也有很大问题,大家都认为需要重构许多模块。所以,在最后几天修补 bug 时,许多补丁是临时对付的(因为整个模块都需要重写了)。为此,我们留下了一个月专门重构代码、修改 bug 、并对最后的结果再做一次评测。

这项工作,终于如期完成了。

半个多月前在白板上留下的工作计划还没擦掉。我列出了 12 点需要改进或重写的地方,考虑到内容较多,又去掉了 3 项。在大家的通力合作下,完成的很顺利。

之前我曾经提到 ,我们的老系统处理 80 人同一战场混战就让服务器支撑不住了。当时我们的服务器 CPU 达到了 790% 。虽然我们的服务器硬件比较老,配置的是两块 Intel Xeon E5310 @ 1.60GHz ,更新硬件可以有所改善。但这个结果绝对是不能满意的。从那个时候起,我从重写最底层框架开始一步步起着手优化。

昨天的测试结果基本让人满意,在同一台机器上,200 个机器人的混战 CPU 占用率平均仅 130% 左右,而机器人 client 边数据包延迟只有 1 秒,完全可以实用。这离我们的设计目标 ( 500 人同战场流畅战斗)还有一些距离,但考虑到今年新配置两块 Intel Xeon E5-2620 @ 2.00GHz 的话,按其性能指标,应当再有至少一倍的性能提升。

ps. 参考这份报告 ,我们计划采购的 [Dual CPU] Intel Xeon E5-2620 @ 2.00GHz Benchmark 16707 分,而目前使用的 [Dual CPU] Intel Xeon E5310 @ 1.60GHz 仅 4160 分。即使仅考虑单线程分数,也在两倍以上。


这个月的改进最重要的在四大点上,目前还没有准确评测到底是那处改进带来的收益最大。

其一,我们改进了 AOI 模块 ,由于接口和用法改变,需要重新做整合工作。

其二,组播部分做了优化。(见 skynet Skynet 设计综述 的组播一节)。

其三,把公式计算模块 抽象出来,用 C 语言重写。

其四,之前,我们在 agent 上计算和玩家有关的技能伤害,通过共享状态的方式同步给 map 服务。目前把计算全部挪到了 map 里计算。关于这点改动,是这次耗时最长的部分,也利弊共存,下面详细这一点。

当初发现的一个热点是对玩家属性的共享读写。倒不是因为数据共享需要加锁的代价。而是,lua 在读取 userdata 中的数据需要代用外部的 C Function ,其开销远大于 Lua 对内建的 table 的读写。(大约有 4 倍的差距)而公式计算则需要大量读写这些属性域。

我改写了公式计算部分,这个改动也使得不再想把战斗相关属性放在一个复杂的共享结构中了。

这样,我们需要把玩家的属性计算从 agent 中挪到 map 中去。这是违背最初的设计的。因为,我希望整个系统中对一组数据的写操作仅存在一处,而其它地方都只是对它的读操作。这样比较干净,也不必用复杂的锁。在理解数据流时也相对清晰。

说服我做这个改动的理由是,战斗系统全部存在于 map 中,map 负责了玩家和玩家、玩家和 npc 、npc 和 npc 间的战斗计算。这些过程是一致的,不因为参战方是玩家还是 npc 有所区别。但我们无法将 npc 也如玩家那样用一个 agent 代理独立出去,所以,就一个服务处理一类操作这个角度而言,把玩家的战斗计算放到 map 中处理是合理的。而在数据上,我们应当把玩家的战斗相关属性于玩家身上的背包以及他自身的非战斗属性(比如名字),看成是两类东西。这样就能很好的解释为什么可以让玩家的战斗属性由一个服务去写,而背包这样的数据却由另一个服务改写。

但这样的修改并不是没有弊端的。最大的问题就是,之前 agent 和 map 分离,agent 可以承担一部分战斗计算工作。这是可以和 map 上的计算工作并行的。不同 agent 间,如果完全没有相关性,他们的战斗计算也是完全并行的。现在在同一 map 中,就失去了并行的好处。

所以,之前固然性能不佳,但可以撑满所有可以用的 CPU 资源,并可以预期增加 CPU 数量还有提升空间。目前,我们 CPU 占用率仅仅 130% ,用 top 查看,8 个核,每个都平均在 20% 左右,但超过 240 人后,client 的包延迟就明显增加了。这应当是 map 处理能力不够造成的。目前的设计中,单个 map 以轮询的方式处理每处战斗,战斗数量增多后,延迟必然增加。

mike 同学认为许多代码还有优化的余地,还有一定的提升空间。我也相信,即使不再优化代码,更新硬件后也还可以轻松把性能翻倍。目前,CPU 的整体资源还有相当大的余量,大约同台机器同时开 6 个以上这样的场景也能轻松胜任。那么,就目前的硬件配置,单机 1200 活跃在线玩家应该不成问题的。我相信在明年上线时的硬件水平下,单台机器应当可以支持到 5000 同时在线用户。


最后谈谈 LuaJIT 的问题。

我一直觉得 Luajit 是我们可以预支的一张性能提升的支票,但总有些小问题迟迟没有兑现。

之前我认为最大的问题是内存限制。Luajit 在 64 位平台下,只能使用 1G 内存。即使在同一进程内开辟多个 lua state 也不例外。查看代码可以知道,luajit 为了结合更高效的 gc ,使用了自己的内存管理器。这需要用一个 32 位的伪指针工作。为了适应 64 位平台,它强制让分配器分配出来的内存的高位都必须是 0 。所以,多个 lua state 也需要满足这个条件,而不可能突破 4G 的限制。

我们现在单个 agent 的内存消耗已经接近 10M (我认为有优化空间,可以下降到 2M 左右),那么 1000 个 agent 的内存总量是很难低于 1G 的。

昨天我想了个办法来突破这个限制。那就是在 lua state 创建时,预先分配好 32M 内存(假定我们单个 state 这些内存足够使用了)。保证这块内存的高 32 位是一致的。那么就可以改动一下 luajit 的源代码,增加少许成本,让 32 位伪指针正常工作。

ps. 这个想法 在 2009 年时有人提到过.

再构思这部分该怎么修改的过程中,我突然发现另一个问题。

luajit 居然使用了 NaN Trick ,这导致 lightuserdata 仅有 48 位有效值(可见 luajit 的源代码 lj_obj.h)。这和我们 在 lua 中使用 64bit 整数 的方式是有所冲突的。而后者对我们相当重要。我们不可能用 luajit 中推荐的 boxed cdata 的方式使用 64bit 整数。这是因为,我们在很多代码中,使用了 64bit id 做 table 的 key ,而那种方式表示 64 位整数,相同的数值可能呈现成不同的 key 。

从代码中去掉 NaN Trick 也是挺复杂的了。相对于 Lua 5.2 ,NaN Trick 是可配置的,且默认并不开启。