« May 2017 | Main

June 26, 2017

浅谈《守望先锋》中的 ECS 构架

今天读了一篇 《守望先锋》架构设计与网络同步 。这是根据 GDC 2017 上的演讲 Overwatch Gameplay Architecture and Netcode 视频翻译而来的,所以并没有原文。由于是个一小时的演讲,不可能讲得面面俱到,所以理解起来有些困难,我反复读了三遍,然后把英文视频找来(订阅 GDC Vault 可以看,有版权)看了一遍,大致理解了 ECS 这个框架。写这篇 Blog 记录一下我对 ECS 的理解,结合我自己这些年做游戏开发的经验,可能并非等价于原演讲中的思想。

Entity Component System (ECS) 是一个 gameplay 层面的框架,它是建立在渲染引擎、物理引擎之上的,主要解决的问题是如何建立一个模型来处理游戏对象 (Game Object) 的更新操作。

传统的很多游戏引擎是基于面向对象来设计的,游戏中的东西都是对象,每个对象有一个叫做 Update 的方法,框架遍历所有的对象,依次调用其 Update 方法。有些引擎甚至定义了多种 Update 方法,在同一帧的不同时机去调用。

这么做其实是有极大的缺陷的,我相信很多做过游戏开发的程序都会有这种体会。因为游戏对象其实是由很多部分聚合而成,引擎的功能模块很多,不同的模块关注的部分往往互不相关。比如渲染模块并不关心网络连接、游戏业务处理不关心玩家的名字、用的什么模型。从自然意义上说,把游戏对象的属性聚合在一起成为一个对象是很自然的事情,对于这个对象的生命期管理也是最合理的方式。但对于不同的业务模块来说,针对聚合在一起的对象做处理,把处理方法绑定在对象身上就不那么自然了。这会导致模块的内聚性很差、模块间也会出现不必要的耦合。

我觉得守望先锋之所以要设计一个新的框架来解决这个问题,是因为他们面对的问题复杂度可能到了一个更高的程度:比如如何用预测技术做更准确的网络同步。网络同步只关心很少的对象属性,没必要在设计同步模块时牵扯过多不必要的东西。为了准确,需要让客户端和服务器跑同一套代码,而服务器并不需要做显示,所以要比较容易的去掉显示系统;客户端和服务器也不完全是同样的逻辑,需要共享一部分系统,而在另一部分上根据分别实现……

总的来说、需要想一个办法拆分复杂问题,把问题聚焦到一个较小的集合,提高每个子任务的内聚性。

ECS 的 E ,也就是 Entity ,可以说就是传统引擎中的 Game Object 。但在这个系统下,它仅仅是 C/Component 的组合。它的意义在于生命期管理,这里是用 32bit ID 而不是指针来表示的,另外附着了渲染用到的资源 ID 。因为仅负责生命期管理,而不设计调用其上的方法,用整数 ID 更健壮。整数 ID 更容易指代一个无效的对象,而指针就很难做到。

C 和 S 是这个框架的核心。System 系统,也就是我上面提到的模块。对于游戏来说,每个模块应该专注于干好一件事,而每件事要么是作用于游戏世界里同类的一组对象的每单个个体的,要么是关心这类对象的某种特定的交互行为。比如碰撞系统,就只关心对象的体积和位置,不关心对象的名字,连接状态,音效、敌对关系等。它也不一定关心游戏世界中的所有对象,比如关心那些不参与碰撞的装饰物。所以对每个子系统来说,筛选出系统关心的对象子集以及只给它展示它所关心的数据就是框架的责任了。

在 ECS 框架中,把每个可能单独使用的对象属性归纳为一个个 Component ,比如对象的名字就是一个 Component ,对象的位置状态是另一个 Component 。每个 Entity 是由多个 Component 组合而成,共享一个生命期;而 Component 之间可以组合在一起作为 System 筛选的标准。我们在开发的时候,可以定义一个 System 关心某一个固定 Component 的组合;那么框架就会把游戏世界中满足有这个组合的 Entity 都筛选出来供这个 System 遍历,如果一个 Entity 只具备这组 Component 中的一部分,就不会进入这个筛选集合,也就不被这个 System 所关心了。

在演讲中,作者谈到了一个根据输入状态来决定是不是要把长期不产生输入的对象踢下线的例子,就是要对象同时具备连接组件、输入组件等,然后这个 AFK 处理系统遍历所有符合要求的对象,根据最近输入事件产生的时间,把长期没有输入事件的对象通知下线;他特别说到,AI 控制的机器人,由于没有连接组件,虽然具备状态组件,但不满足 AFK 系统要求的完整组件组的要求,就根本不会遍历到,也就不用在其上面浪费计算资源了。我认为这是 ECS 相对传统对象 Update 模型的一点优势;用传统方法的话,很可能需要写一个空的 Update 函数。

游戏的业务循环就是在调用很多不同的系统,每个系统自己遍历自己感兴趣的对象,只有预定义的组件部分可以被子系统感知到,这样每个系统就能具备很强的内聚性。注意、这和传统的面向对象或是 Actor 模型是截然不同的。OO 或 Actor 强调的是对象自身处理自身的业务,然后框架去管理对象的集合,负责用消息驱动它们。而在 ECS 中,每个系统关注的是不同的对象集合,它处理的对象中有共性的切片。这是很符合守望先锋这种 MOBA 类游戏的。这类游戏关注的是对象间的关系,比如 A 攻击了 B 对 B 造成了伤害,这件事情是在 A 和 B 之间发生的,在传统模型中,你会纠结于伤害计算到底在 A 对象的方法中完成还是在 B 的方法中完成。而在 ECS 中不需要纠结,因为它可以在伤害计算这个 System 中完成,这个 System 关注的是所有对象中,和伤害的产生有关的那一小部分数据的集合。

ECS 的设计就是为了管理复杂度,它提供的指导方案就是 Component 是纯数据组合,没有任何操作这个数据的方法;而 System 是纯方法组合,它自己没有内部状态。它要么做成无副作用的纯函数,根据它所能见到的对象 Component 组合计算出某种结果;要么用来更新特定 Component 的状态。System 之间也不需要相互调用(减少耦合),是由游戏世界(外部框架)来驱动若干 System 的。如果满足了这些前提条件,每个 System 都可以独立开发,它只需要遍历给框架提供给它的组件集合,做出正确的处理,更新组件状态就够了。编写 Gameplay 的人更像是在用胶水粘合这些 System ,他只要清楚每个 System 到底做了什么,操作本身对哪些 Component 造成了影响,正确的书写 System 的更新次序就可以了。一个 System 对大多数 Component 是只读的,只对少量 Component 是会改写的,这个可以预先定义清楚,有了这个知识,一是容易管理复杂度,二是给并行处理留下了优化空间。

在演讲中谈到了开发团队对 ECS 的设计认知也是逐步演进的。

比如在一开始,他们认为 Component 就是大量有某种同类 Entity 属性的集合的筛选器。ECS 框架辅助这个筛选过程,每个 System 模块都用 for each 的方式迭代相关的 Entity 中对象的组件。之后他们发现,其实对于每个游戏对象集合体来说,一类 Component 可以也应该只有一个。比如存放玩家键盘输入的 Component ,就没有多个。很多 System 都需要去读这个唯一的 Component 内的状态(哪些按钮被按下了),可以安排一个 System 来更新这个 Component 。原文把这种 Component 成为 Singleton Component ,我认为这个东西和一开始 ECS 想解决的问题还是有一些差别的:不同种类的 Entity 分别拥有同类的属性组,框架负责管理同类集合。我们的确还是可以创建一个叫做玩家键盘的 Entity 加到游戏世界中,这个 Entity 是由键盘组件构成。但是我们完全不必迭代玩家键盘这个 Entity 集合,因为它肯定只有一个,直接把这个对象放在游戏世界中即可。但把它放在 System 中就不是一个好设计了。因为它破坏了 System 无状态的设计原则,而且也不支持多个游戏世界:在原文中举了个例子,实际游戏和游戏回放就是两个不同的游戏世界,不同的游戏世界意味着不同的业务流程的组合,需要用不同的方式粘合已经开发好的 System 。把游戏键盘状态这种状态内置在特定的 System 中就是不合适的了。从这个角度来说 ECS 的本质还是数据 C 和操作 S 分离。而操作 S 并不局限于对同类组件集合的管理,也可是是针对单个组件。作者自己也说,最终有 40% 的组件就是单件。

单件本身其实就和传统面向对象模型差不多了。但是数据和方法分离还是很有意义。我们在用面向对象模式做开发的时候也会碰到一个对象有几个不同的方法,某些方法关注这部分状态、另一些方法关注另一部分状态,还有一些方法关注前面几组状态的集合。这里的方法就是 ECS 中的系统、状态就是组件。将数据和方法分离可以将不同的方法解耦。如果用传统的 C++ 的面向对象模式,很可能需要用多继承、组合转发等等复杂的语法手段。


演讲后面还提到了一些 ECS 模式下处理一些复杂问题的常见手法。

Component 没有方法,而 System 则没有状态,只是对定义好的 Component 状态的加工过程。而许多 System 中很可能会处理同一类问题,涉及的 Component 类型是相同的。如果这个有共性的问题只涉及一个 Entity ,那么直观的方法是设计一个 System ,迭代,逐个把结果计算出来,存为 Component 的状态,别的 System 可以在后续把这个结果作为一个状态读出来就可以了。

但如果这个行为涉及多个 Entity ,比如在不同的 System 中,都需要查询两个 Entity 的敌对关系。我们不可能用一个 System 计算出所有 Entity 间的敌对关系,这样必然产生了大量不必要的计算;又或者这个行为并不想额外修改 Component 的状态,希望对它保持无副作用,比如我想持续模拟一个对象随时间流逝的位置变化,就不能用一个 System 计算好,再从另一个 System 读出来。

这样,就引入了 Utility 函数的概念,来做上面这种类型的操作,再把 Utility 函数共享给不同的 System 调用。为了降低系统复杂度,就要求要么这种函数是无副作用的,随便怎么调用都没问题,比如上面查询敌对关系的例子;要么就限制调用这种函数的地方,仅在很少的地方调用,由调用者小心的保证副作用的影响,比如上面那个持续位置变化的过程。

如果产生状态改变这种副作用的行为必须存在时,又在很多 System 中都会触发,那么为了减少调用的地方,就需要把真正产生副作用的点集中在一处了。这个技巧就是推迟行为的发生时机。就是把行为发生时需要的状态保存起来,放在队列里,由一个单独的 System 在独立的环节集中处理它们。

例如不同的射击行为都可能创建出新的对象、破坏场景、影响已有对象的状态。在同一面墙上留下不同的弹孔,不需要堆叠在一起,而只需要保留最后一个,删除前面的。我们可以把让不同的 System 触发这些对象创建、删除的行为,但并不真正去做。集中在一起推迟到当前帧的末尾或下一帧的开头来做。这样就尽量保证了多数 System 工作的时候,对大多数组件来说是无副作用的,而把严重副作用的行为集中在单点小心处理。


ECS 要解决的最复杂,最核心的问题,或许还是网络同步。我认为这也是设计一个状态和行为严格分离的框架的主要动机。因为一个好的网络同步系统必须实现预测、有预测就有预测失败的情况,发生后要解决冲突,回滚状态是必须支持的。而状态回滚还包括了只回滚部分状态,而不能简单回滚整个世界。

我在去年其实在本 blog 中谈过这个问题 。我的观点是,状态的单独保存是非常重要的。在 ECS 模型中,C 是纯数据,所以非常方便做快照和回滚。Entity 的组件分离,也适合做关键状态的记录。去年和一个同事一起做了一个射击类的 MOBA demo ,最终的实现方案就是把游戏对象的位置(移动)状态,和射击状态专门抽出来实现预测同步,效果非常不错。

这个演讲其实并没有谈及预测和同步的具体技术,而是谈 ECS 怎么帮助降低利用这些技术的实现复杂度。同时也提及了一些有趣的细节。

比如说,ECS 规定每个需要根据输入表现的 System 都提供了一个 UpdateFixed 函数。守望先锋的同步逻辑是基于 60fps 的,所以这个 UpdateFixed 函数会每 16ms 调用一次,专门用于计算这个逻辑帧的状态。服务器会根据玩家延迟,稍微推迟一点时间,比客户端晚一些调用 UpdateFixed 。在我去年谈同步的 blog 中也说过,玩家其实不关心各个客户端和服务器是不是时刻上绝对一致(绝对一致是不可能做到的),而关心的是,不同客户端和服务器是不是展现了相同的过程。就像直播电影,不同的位置早点播放和晚点播放,大家看到的内容是一致的就够了,是不是同时在观看并不重要。

但是,游戏和电影不一样的地方是,玩家自己的操作影响了电影的情节。我们需要在服务器仲裁玩家的输入对世界的影响。玩家需要告知服务器的是,我这个操作是在电影开场的几分几秒下达的,服务器按这个时刻,把操作插入到世界的进程中。如果客户端等待服务器回传操作结果那就实在是太卡了,所以客户端要在操作下达后自己模拟后果。如果操作不被打断,其实客户端模拟的结果和服务器仲裁后的结果是一样的,这样服务器在回传后告之客户端过去某个时间点的对象的状态,其实和当初客户端模拟的其实就是一致的,这种情况下,客户端就开开心心继续往前跑就好了。

只有在预测操作时,比如玩家一直在向前跑,但是服务器那里感知到另一个玩家对他释放了一个冰冻,将他顶在原地。这样,服务器回传给玩家的位置数据:他在某时刻停留在某地就和当初他自己预测的那个时刻的位置不同。产生这种预测失败后,客户端就需要自己调节。有 ECS 的帮助,状态回滚到发生分歧的版本,考虑到服务器回传的结果和新了解到的世界变化,重新将之后一段时间的操作重新作用到那一刻的状态上,做起来就相对简单了。

对于服务器来说,它默认客户端会持续不断的以固定周期向它推送新的操作。正如前面所说,服务器的时刻是有意比客户端延后的,这样,它并非立刻处理客户端来的输入,而是把输入先放在一个缓冲区里,然后按和客户端固定的周期 ( 60fps ) 从缓冲区里取。由于有这个小的缓冲区的存在,轻微的网络波动(每个网络包送达的路程时间不完全一致)是完全没有影响的。但如果网络不稳定,就会出现到时间了客户端的操作还没有送到。这个时候,服务器也会尝试预测一下客户端发生了什么。等真的操作包到达后,比对一下和自己的预测值有什么不同,基于过去那个产生分歧的预测产生的状态和实际上传的操作计算出下一个状态。

同时,这个时候服务器会意识到网络状态不好,它主动通知客户端说,网络不太对劲,这个时候的大家遵循的协议就比较有趣了。那就是客户端得到这个消息就开始做时间压缩,用更高的频率来跑游戏,从 60fps 提高到 65fps ,玩家会在感受到轻微的加速,结果就是客户端用更高的频率产生新的输入:从 16 ms 一次变成了 15.2 ms 一次。也就是说,短时间内,客户端的时刻更加领先服务器了,且越领先越多。这样,服务器的预读队列就能更多的接收到未来将发生的操作,遇到到点却不知道客户端输入的可能性就变少了。但是总流量并没有增加,因为假设一局游戏由一万个 tick 组成,无论客户端怎么压缩时间,提前时刻,总的数据还是一万个 tick 产生的操作,并没有变化。

一旦度过了网络不稳定期,服务器会通知客户端已经正常了,这个时候客户端知道自己压缩时间导致的领先时长,对应的膨胀放慢时间(降低向服务器发送操作的频率)让状态回到原点即可。

btw, 守望先锋 是基于 UDP 通讯的,从演讲介绍看,对于 UDP 可能丢包的这个问题,他们处理的简单粗暴:客户端每次都将没有经过服务器确认的包打包在一起发送。由于每个逻辑帧的操作很少,打包在一起也不会超过 MTU 限制。

ECS 在这个过程中真正发生威力的地方是在预测错误后纠正错误的阶段。一旦需要纠正过去发生的错误,就需要回滚、重新执行指令。移动、射击这些都属于常规的设定,比较容易做回滚重新执行;技能本身是基于暴雪开发的 Statescript 的,通过它来达到同样的效果。ECS 的威力在于,把这些元素用 Component 分离了,可以单独处理。

比如说射击命中判定,就是一个单独的系统,它基于被判定对象都有一个叫做 ModifyHealthQueue 的组件。这个组件里记录的是 Entity 身上收到的所有伤害和治疗效果。这个组件可以用于 Entity 的筛选器,没有这个组件的对象不会受到伤害,也就不需要参与命中判定。真正影响命中判定的是 MovementState 组件,它也参与了命中判定这个系统的筛选,并真正参与了运算。命中判定在查询了敌对关系后从 MovementState 中获取应该比对的对象的位置,来预测它是否被命中(可能需要播放对应的动画)。但是伤害计算,也就是 ModifyHealthQueue 里的数据是只能在服务器填写并推送给客户端的。

MovementState 会因为需要纠正错误预测而被回退,同时还有一些非 MovementState 的状态也会回退,比如门的状态、平台的状态等等。这个回退是 Utility 函数的行为,它可能会影响受击的表现,而受伤则是另一种固定行为(服务器确定的推送)的后果。他们发生在 Entity 的不同组件切片上,就可以正交分离。

射击预测和纠正可以利用对象的活动区域来减少判定计算量。如果能总是计算保持当前对象在过去一段时间的最大移动范围(即过去一段时间的包围盒的并集),那么当需要做一个之前发生的射击命中判定时,就只需要把射击弹道和当前所有对象的检测区域比较,只有相交才做进一步检测:回退相关对象到射击发生的时刻,做严格的命中校验。如果当初预测的命中结果和现在核验的一致就无所谓了,不需要修正结果(如果命中了,具体打中在哪不重要;如果未命中,也不管子弹射到哪里去了)。

如果 ping 值很高,客户端做命中预测往往是没有什么意义的,徒增计算量。所以在 Ping 超过 220ms 后,客户端就不再提前预测命中事件,直接等服务器回传。

ECS 框架在这件事上可以做到只去回滚和重算相关的 Component ,一个 System 知道哪些 Entity 才是它真正关心的,该怎么回退它所关心的东西。这样开发的复杂度就减少了。游戏本身是复杂的,但是和网络同步相关的影响到游戏业务的 System 却很少,而且参与的 Component 几乎都是只读的。这样我们就尽可能的把这个复杂的问题和引擎其它部分解耦。


ECS 是个不错的框架,但是需要遵循一定的规范才能起到他应有的效果:减少大量系统间的耦合度。但并非所有的问题都适合遵循 ECS 的规范来开发,尤其是一些旧有的模块,很难做到把数据结构按 Component 得规范暴露出来,并把状态改变的方法集成到独立的 System 中去。这个时候就应该做一些封装的工作。比如说有些系统原本就利用了多线程模型作并行优化,所以我们需要把这些已经做好的工作隔离在 ECS 框架之外,仅仅暴露一些接口和 ECS 框架对接。

June 19, 2017

skynet 网络线程的一点优化

skynet 是一个注重并行业务处理的框架,设计它的初衷是可以充分利用多核 CPU 更好的处理那些比较消耗 CPU 的,天然可以并行的业务,比如网络游戏。网络 I/O 并不是优化重点。

基于这个设计动机,skynet 的网络层使用单线程实现。因为我认为,即使是代码量稍大一些的单线程程序,也会比代码量较小的多线程程序更容易理解,出 bug 的机会也更少。而且经典的网络服务程序,如 redis nginx 并没有因为单线程处理网络 IO 而变现得不堪,反而有不错的口碑。

所以,skynet 的 epoll 循环并不像 erlang 那样,只关注读写事件,而让每个 actor 自己去处理真正的 socket 读写。那样固然可以获得更高的网络处理能力,但势必让网络 API (由存在多个工作线程里的多个 actor 分别调用)依赖锁来保证正确性。这是我不太希望看到的。目前的设计是,所有网络请求,都通过把指令写到一个进程内的 pipe ,串行化到网络处理线程,依次处理,然后再把结果投递到 skynet 的其它服务中。

这个做法未必最好,但也恰恰能用,一般网络游戏服务器,根据我们的实际项目数据,在其它业务处理的 CPU 占用到极限时,单台机器网络带宽不大会超过 30MB 左右的上下行带宽。一个核每秒处理 60MB 的数据是绰绰有余的。

不过我一直有个想法,或许可以优化一下这部分,让 skynet 可以适应一些重 IO 而不仅仅是重业务处理的场合。前些年和一个使用 skynet 做流媒体广播的同学交流过,他们的生产环境上,一台机器会配置几块千兆网卡,skynet 在处理高带宽的 udp 广播时,跑不满硬件的带宽。

前几天,skynet 的 issue #646 又让我想到这件事情。就这个 issue 而言,我不认为达到网络线程处理极限,可能尚有未发现的其它因素影响,不过就这个机会,我试着实现了一下以前的想法。

我的想法是,可以把网络写操作从网络线程中拿出来。当每次要写数据时,先检查一下该 fd 中发送队列是否为空,如果为空的话,就尝试直接在当前工作线程发送(这往往是大多数情况)。发送成功就皆大欢喜,如果失败或部分发送,则把没发送的数据放在 socket 结构中,并开启 epoll 的可写事件。

网络线程每次发送待发队列前,需要先检查有没有直接发送剩下的部分,有则加到队列头,然后再依次发送。

当然 udp 会更简单一些,一是 udp 包没有部分发送的可能,二是 udp 不需要保证次序。所以 udp 立即发送失败后,可以直接按原流程扔到发送队列尾即可。


加上这个优化后,就必须在每个 socket 结构上增加一个 spinlock 。直接发送的逻辑可以用 try lock 尝试加锁,而不一定要获得锁;只在网络线程发送队列期间这一个地方才需要加锁。所以这个锁几乎不会竞争。

毕竟是多线程代码容易出 bug ,而且也不太容易做测试。所以我暂时把它放在一个独立分支上,希望感兴趣的同学可以帮助 review 一下,以后再考虑是否合并到主干。

June 18, 2017

支持部分共享的树结构

因为图形引擎中的对象天然适合用树 (n-ary tree) 表达,所以它在图形引擎中被广泛使用。通常,子节点会继承父节点的一些状态,比如变换矩阵,在渲染或更新的时候,可以通过先序遍历逐级相乘。

在 PC 内存充裕的条件下,我们通常不必考虑树结构储存的开销,所以大多数图形引擎通常会为每个渲染对象独立生成一个树结构,比如 Unity 中的 GameObject 就是这么一个东西。在 Ejoy2D 中,从节约内存的角度考虑,把树节点上的一部分可共享的状态信息(不变的矩阵、纹理坐标等)移到了资源数据块中,但是树结构的拓扑关系还是在新创建出每个 sprite 时复制了一份。

随着游戏制作的工艺提高,而大众使用的移动设备的内存增长有限,这部分的开销慢慢变得显著。在我们正在开发的几个项目中,渲染对象本身,而不算图形资源(贴图、模型等),也占据了以 M 为单位计算的可用内存。比如在一个项目中,某个巨型对象由多达 2000+ 个节点构成,创建速度和内存开销都成为一个不可忽视的问题。由于是于自研引擎,所以同事尝试过一些优化的尝试。

图形引擎处理的大多数的树结构对象,其实仅在编辑环境会对树的拓扑关系进行调整:增加、移动、复制节点。而运行环境下,树结构本身几乎是不变的。一般的树结构的实现是用指针来相互引用,编辑好的资源是树结构的序列化结果,而创建过程是一个反序列化过程,在内存中重建整棵树,并用指针重新建立节点间的联系。比如在 Unity 中,就把这种编辑好的树对象叫做 prefab 预制件。如果预制件比较复杂,加载预制件和从预制件中构建对象的时间成本都不算低。

一个优化方法是去掉运行时内存中的指针,改用 id 或资源数据块中的偏移量,这样,预制件可以直接从资源文件中成块读入,创建内存对象时也只需要用指针引用即可。可以节省大量在内存中重建的时间。Ejoy2D 现在就是这么做的。去掉指针的额外好处是在 64 位系统下,可以从 8 字节的引用开销减少到 4 字节(或更少)。Ejoy2D 当初做此修改,为一个项目一举减少了 10M+ 的运行期内存占用。而且资源文件可以在暂时不用的时候移出内存,等需要的时候再加载回来,而不用担心数据的内存地址发生了变化。


但是,如果想让游戏对象直接共享使用预制件,最核心需要解决的问题是:大部分对象并不能做到完全不修改树结构,且预制件中的树的拓扑关系并不直接对应到内存。

我们先来看对应关系的问题:

在 ejoy2d 中,资源(预制件)中的对象结构其实并不是树,而是一个有向无环图。例如:美术制作了一个房子,房子上挂着三个灯笼,在资源中,灯笼只有一个预置对象,是房子对它有三个引用。而在运行期,三个灯笼必须是三个独立对象;程序是有能力对它们分别修改属性的。比如改改颜色,摆动频率等等。也就是说,这个房子的预制件一但在内存中还原,原本共享的灯笼子物件,必须有三份可供修改的状态数据区。

再来看前一个问题:

对于制作好的预制件,运行期很可能对树上的某个节点做属性调整。比如、预制件制作了一个仓库,仓库中的货物就是由运行时决定的。我们在陌陌争霸中,为仓库的货物状态预设了数帧图片,在运行时可以设置显示第几帧,用来表示仓库的库存情况。如果仓库中的货物还可以根据运行情况实际表现出来,则还需要用到挂接的功能:把货物对象挂接到仓库预设的挂接点上。

由于这些实现上的复杂需求,ejoy2d 和大多数图形引擎一样,从预制件创建出游戏对象直接简单的重建树的过程。当你从资源中创建一个 sprite ,你会发现逐层创建出了 lua 对象。然而大多数情况下,运行期并不会修改其中的绝大多数对象的属性,而仅使用资源中预制好的那一份。这就造成了一些浪费。如果资源中的树不算复杂时,这个浪费是有限的;但是我们的一个使用 ejoy2d 开发的新项目,随着内部工具的完善,美术逐渐创作出越来越复杂的结构。使用 ejoy2d 做新项目开发的同学花了半年多精力想优化这个问题。


我最近也重新思考了一下,这个问题的本质是,如果已有一个层级复杂的树状数据结构(下面称它为蓝图),我们可不可以做到有很多基于它的副本,每个副本对其中的部分做修改,而共享那些没有修改的部分。

比较容易想到的方案有这些:

  1. 在蓝图的每个节点上预留一个指针,指向一个列表;如果有副本向修改这个节点,就把修改后的属性加到这个列表中。在遍历这个节点时,一旦发现这个节点有人修改过,就找到对应的修改数据。另外,蓝图中如果有重复引用的节点(例如上面提到的屋檐下挂的灯笼),在修改其属性时,需要拷贝分裂。

  2. 对 1 方案做一些修改,预留指针只保存一个槽位,副本修改属性记录在副本对象中,而在遍历蓝图前,将副本中修改过的属性填入蓝图,遍历完成后再清除;或是在填入的同时把副本指针也记录在节点上,遍历时忽略非自己修改的节点。

  3. 在副本中保留一个修改节点数据的 hash 表,遍历蓝图的时候查询 hash 表,找到可能修改的属性。

  4. 在修改蓝图的某个节点时,部分复制创建出一颗不完全树,只保留被修改属性的节点和它们的祖先;让那些没有修改的分支引用回蓝图。遍历的时候改遍历复制出来的不完全树。

这几个方案大同小异,我们实际在项目中采用的方案 1 ,数据结构比原先的 ejoy2d 复杂了很多,衍生出不少 bug ,目前还不够稳定。

我这几天的思考结果是,在方案 3 的基础上做改进,或许是更好的选择。

方案三的本质是:运行时的树由 蓝图 和 对蓝图的补丁 两个部分构成。这样从数据结构上来说,它们是独立的两块数据,相互引用关系比较简单。可能的额外开销是遍历每个节点时需要额外的一次 hash 表查询,虽然大多数情况下是 Hash 表查询是 O(1) 的操作,但实际上会因为冲突而 O(1) 高一些,尤其是这个方案的初衷之一就是节省内存,如果预留比较大的 hash 表池来减少冲突率的话,很可能剩下的内存又再次消耗掉了。另外 hash 表的 key 也不太好选择,不能直接用节点对象的指针,因为在蓝图中有大量的对象是被共享的。

怎么改进呢?

其实、我们对树的遍历方式其实是唯一的。在图形引擎中多半选择深度优先的先序遍历,也就是先访问根节点,再依次访问子节点。如果树的拓扑结构稳定,其实每次遍历的过程都是唯一的。所以运行时的每个节点其实都可以根据其遍历次序有一个不变的唯一序号。对于上面提到的屋檐下的灯笼,多个灯笼虽然共享着蓝图上的同一块数据,但每个灯笼,以及灯笼下的子节点都有不同的访问编号。我们可以用这个编号来索引附加(修改的)节点属性。

由于访问次序固定,我们也不再需要用 hash 表来记录 patch 集合,而只需要按访问先后次序来排列好 patch 即可。再访问过程中,每访问到一个节点,就把访问编号加一,检查 patch 链表头就知道是否当前节点丫头修改属性了,这样就可以做到严格的 O(1) 时间,同时也不增加内存开销。

order 的值虽然无法直接记录在蓝图上,但我们可以在蓝图中预算好每个子树的总节点数,这样计算节点的 order 成本仅 O(log n) 。而且仅在取节点引用,或是从非根节点开始遍历时才需要计算一次。

还剩一个问题:

遍历树结构变复杂了,即使我们把遍历算法写对,却很难用常规手法封装。用简单的迭代器模式是不够的,遍历树不仅仅需要访问到每个节点,还需要在遍历过程中感知到树的遍历层次变化。比如在 ejoy2d 现在的公开版本中,需要按树层级来累乘变换矩阵,这个临时矩阵是存放在遍历过程中的函数调用栈上的。我们还可能根据枝干上的(隐藏)属性来跳过子节点等等。

否则,既然访问持续恒定,为什么不直接把树摊平?btw, 在上面提到的当前项目中,维护引擎的同学已经把摊平树结构作为了一项优化。

我还没有见过哪个 C 版本的 n-ary tree 能够把接口设计好,做到高内聚性的实现;大多数情况下,C 语言的项目中都会根据实际需要来实现一个仅满足自身需要的 n-ary tree ,把模块内聚性的边界放在更高一些的层次,而不直接暴露树结构的接口。

C++ 倒是有几个树结构的实现:比如 tree.hh 以及 boost::graph ,它们都是想切合 STL like 的迭代器模式,实际用起来是很麻烦的。我想这也是为什么即使是 C++ 项目,大多数人也自己用更基本的数据结构 std::map std::set std::list 等组装。


我花了两天时间来实现上面的想法,代码放在 github 上 ,尚还有一些部分(主要是生命期管理)需要完善。

在我的实现中,我设计了以下数据结构:

tree_blueprint 表示树结构蓝图,在蓝图阶段可以从根开始构建树,增加子节点,但不可以删除和移动节点。这是因为这些灵活的需求多半在编辑器中才有,而编辑器完全可以用动态语言来实现编辑过程,蓝图只需要满足基本的构建需求就可以了。如果需要修改蓝图,不如从头创建一个新的。蓝图的序列化过程并没有实现,但它应该很容易做到。蓝图结构主要记录的是树的拓扑形态,每个节点上的附加属性用一个 void * userdata 传入,它不关心具体是什么。

tree_patch 是针对某张已经定型(不再修改)的蓝图的一些修改,它由一系列的补丁循序组成。每个补丁记录有对应的节点遍历次序号(order) , 和修改过的属性段 userdata 。补丁也允许对蓝图上对应节点的做额外挂接 (mount) ,但不可以新增子节点。重新挂接的子树是一个 tree 结构,而不能使蓝图节点。

treetree_blueprinttree_patch 的联合。一张蓝图和一组对应的补丁,构成了一个运行时的树结构。蓝图斯不可修改的,可以被多个 tree 引用。补丁是 tree 唯一的,不可被引用。补丁在每次新增节点后,都会生成一个新版本。对已有节点上修改属性数据则不会影响补丁的版本。

tree_node 是对 tree 上任意节点的引用,每个节点可以有多个 tree_node 引用共享。实际封装到上层后,可以用 cache 来保证做唯一引用以简化生命期管理。所有的运行期读写树节点的操作都需要通过 tree_node 来完成。

tree_blueprint 可以 print 出 treetree 可以取得根节点的 tree_nodetree_node 可以 setpatch 和 getpatch ,也可以 read 出对应蓝图上的原始属性信息,还可以 fetch 其子节点,或 mount 一个新的 tree 。

我觉得把出去 tree_node 之外的结构统一起来做生命期管理比较好。因为他们的数据间的相互引用关系比较复杂,用标记清除的垃圾回收算法比用引用计数更为简单牢靠。所以另外设计了一个 tree_manager 结构,管理了所有的以上结构,并用数字 id 来自带具体对象。

tree_node 是个例外,在 api 设计时,全部都由调用者传入这个结构的内存,它是对实际数据的引用,这里并没有做反向引用,也就是说 tree 本身并不知道自己被多少 tree_node 引用过了,我想这个问题在上层封装中比较容易解决。比如在 lua 封装中,可以用 tree 的 id 和 order 做唯一索引来制作一个 tree_node 的 cache 。

这里预设的场景是:fetch 一个 tree node 预留额外的属性空间这个操作是比较低频的,可以接受较大的时间成本。因为实际使用的时候,我们都是在初始化阶段就把需要关注的节点引用好,或者只在第一次访问时做唯一一次 fetch 操作。一旦保留了 tree node 对象,读写上面的属性应该是最快的,保证 O(1) 时间可以完成。遍历是另一个需要关注的性能热点,数据结构的设计应该尽量满足遍历最快,空间最省。

树的遍历接口我仔细设计过,虽然用起来比较麻烦,但基本保证了高内聚性。好在上层封装也仅有有限的几处调用树的遍历:渲染遍历、更新遍历、点击测试遍历。ejoy2d 并没有专门对遍历做封装,而是简单的复制了遍历代码;这次树结构变复杂,恐怕就不适合复制代码了。

这次我使用了一个回调函数的接口:

void (*tree_traverse_func)(void *bp, void *patch, void *argument, void *stackframe);

在访问每个节点时都会调用,前两个参数指蓝图上绑定的 userdata 及补丁(如果有)上绑定的 userdata 。

后两个参数用于模拟递归层次。argment 指上层调用传入的数据块,对于根节点,它就是 tree_traverse 调用传入的数据;然后在遍历过程中,遍历函数会在自己的栈帧上分配出一块内存,通过 stackframe 参数给回调函数,回调函数可以把需要传递给下层的数据写入,遍历框架会将其用 argument 传给下一层节点。如果当前访问的节点是叶节点,那么 stackframe 为 NULL 。

解释起来可能说不太清楚,可以看看例子里是怎么使用的。

June 06, 2017

sharedata 的替代品:datasheet

skynet 中有一个用来在多个服务间共享数据表的模块,叫做 sharedata

它的设计动机是:当我们有很多服务时,如果需要共享一份只读的数据表,把数据表分别在每个服务类加载会很浪费内存。而且,一旦数据表有热更新的需求,分散在多个服务中的数据更新起来会比较麻烦。

我试过很多方案来达成这个需求,一直都不是特别满意。目前的 sharedata 模块是用的最久、使用项目最多的一个。虽然它基本可用,但使用它的同学也提出了一些问题,我对这些问题做了一些思考。

首先、它其实并不能完全共享一块内存。我们很难做到像 C 数据结构一样,一份只读的数据结构让多个读取者持有指针,完全共享同一块内存。因为对于树结构的数据,如果期望让 lua 用原生的语法来访问,就需要把子结构的指针用 lua userdata 封装起来,这个结构本身是属于 lua vm 的,每个 vm 必须独立,不能共享。它是需要额外占用内存的。

如果把这个结构用 lightuserdata 封装,一是元表的问题很难解决的很好(不同的 lightuserdata 必须共享元表),二是 lightuserdata 无法做热更新:你很难(并非完全不行)通过遍历 lua vm 更新它。

而从节约内存的角度看这个模块的用途,它更多的是做到部分加载:策划会把很多数据打包到一个数据表里,但是一个服务在一段时间只会用到很少的一部分。把整个数据表加载到服务的 lua vm 内是很浪费内存的。

访问速度也是可能成为问题:lua 访问纯 table 的内容还是很快的,如果是 userdata 或带 metatable 的 table 的话,由于要至少多出一次函数调用,性能就大打折扣。sharedata 做了一定的 cache ,我们有一个项目在使用的时候更是自己额外多做了一层 cache ,为了配合 cache 工作,我还特定添加了 deepcopy 方法,把 sharedata 的子树复制成普通的 lua 表。这也可以看出,完全共享内存而减少内存消耗的需求并不那么强烈。


sharedata 在实现的时候,把数据热更新、副本引用管理的部分写在 C 层次,给实现也带来了不必要的复杂度。理论上热更新时,时间效率是很次要的,我们只需要保证正确即可,多长时间可以更新好并不太重要。

我在综合以上重新考虑后,最近重新实现了一个替代模块,暂命名为 datasheet 。它能做的是:把一个复杂的有一定限制的 lua 表,转换为一块 C 内存,由多个 lua 服务共享读取。

这里的一定限制指:表项的 key 只能是字符串,或是正的连续整数(数组)。加上这个限制可以简化实现。

它和 sharedata 的实现有所不同:它仅在第一次访问一个子表时,利用元方法触发,将子表的第一层完全复制到当前的 lua vm 中;如果这一层下还有子表,则只创建一个空表,附上元方法,惰性展开。展开后,它就变成了 lua 中一个普通 table ,原表也已去掉,访问操作完全没有效率损失。

从 lua 表转换为 C 内存块的过程交给独立的子模块 datasheet.builder 来完成,并由调用这个模块的服务来保持 C 内存块的生命期。这个 C 内存块将以 lua string 的形式存在于调用 datasheet.builder 的 lua 服务的 vm 中,只是把字符串指针共享给其它服务。

而任何服务一旦引用一张表,都可以把生命期保持到该服务退出。这些数据表采用引用数据管理,管理部分全部由 lua 实现。


数据热更新是这样实现的:

任何转换为 C 内存的数据表,每个子表都有一个唯一数字 id 。对应在 lua vm 中是一个包含有这个数字 id 的 userdata 。而在需要热更新数据表的时候,需要把老版本的数据表和新版本的数据表做一次差异比较,根据表项的 key 找到新老对应项,尽量保持相同的 id 生成新版本的数据块。

这样,在做热更新的时候,只要通知持有旧表的服务,更新 C 数据块指针,并把 vm 中的 cache 清空,下次访问任何一个子表时,重新从 C 数据块展开数据即可。


目前 datasheet 已经提交到 skynet 的 master 主干,以一个独立模块存在,接口方面和 sharedata 大致相同。有兴趣尝试的同学可以帮忙测试一下。它以后很有可能作为 skynet 1.1 的默认模块提供。

June 02, 2017

skynet 模块命名空间调整

前段时间有同学抱怨说 skynet 下提供的 lua 模块都没有名字空间,平坦的命名,容易和自己项目开发的模块命名冲突。虽然自己项目开发的模块可以单独给一个名字空间,但混杂在一起使用还是不美观。

我考虑了几天,决定在 skynet 1.1 版本中把大部分的模块都加上 skynet 前缀。

调整的模块有:

  • cluster : skynet.cluster
  • crypt : skynet.crypt
  • datacenter : skynet.datacenter
  • dns : skynet.dns
  • memory : skynet.memory
  • mongo :skynet.db.mongo
  • redis : skynet.db.redis
  • mysql : skynet.db.mysql
  • multicast : skynet.multicast
  • netpack : skynet.netpack
  • profile : skynet.profile
  • sharedata : skynet.sharedata
  • sharemap : skynet.sharemap
  • stm : skynet.stm
  • snax : skynet.snax
  • socket : skynet.socket
  • socketchannel : skynet.socketchannel
  • socketdriver : skynet.socketdriver

因为一些模块引用的外部库,所以没有改变:

md5 sproto bson

http 和 snax 原来就具备名字空间,所以暂时没有调整。

为了保持和 skynet 1.0 的兼容性,我在 lualib/compat10 下放置了这些被改名的模块的代理。为了兼容过去的项目,只需要把 lualib/compat10 添加到项目的 lua_path 中即可。