« pbc 库的 lua binding | 返回首页 | Buddy memory allocation (伙伴内存分配器) »

开发笔记 (6) : 结构化数据的共享存储

开始这个话题前,离上篇开发笔记已经有一周多了。我是打算一直把开发笔记写下去的,而开发过程中一定不会一帆风顺,各种技术的抉择,放弃,都可能有反复。公开记录这个历程,即是对思路的持久化,又是一种自我督促。不轻易陷入到技术细节中而丢失了产品开发进度。而且有一天,当我们的项目完成了后,我可以对所有人说,看,我们的东西就是这样一步步做出来的。每个点滴都凝聚了叫得上名字的开发人员这么多个月的心血。

技术方案的争议在我们几个人内部是很激烈的。让自己的想法说服每个人是很困难的。有下面这个话题,是源于我们未来的服务器的数据流到底是怎样的。

我希望数据和逻辑可以分离,有物理上独立的点可以存取数据。并且有单独的 agent 实体为每个外部连接服务。这使得进程间通讯的代价变得很频繁。对于一个及时战斗的游戏,我们又希望对象实体之间的交互速度足够快。所以对于这个看似挺漂亮的方案,可能面临实现出来性能不达要求的结果。这也是争议的焦点之一。

我个人比较有信心解决高性能的进程间数据共享问题。上一篇 谈的其实也是这个问题,只是这次更进一步。

核心问题在于,每个 PC (玩家) 以及有可能的话也包括 NPC 相互在不同的实体中(我没有有进程,因为不想被理解成 OS 的进程),他们在互动时,逻辑代码会读写别的对象的数据。最终有一个实体来保有和维护一个对象的所有数据,它提供一个 RPC 接口来操控数据固然是必须的。因为整个虚拟世界会搭建在多台物理机上,所以 RPC 是唯一的途径。这里可以理解成,每个实体是一个数据库,保存了实体的所有数据,开放一个 RPC 接口让外部来读写内部的这些数据。

但是,在高频的热点数据交互时,无论怎么优化协议和实现,可能都很难把性能提升到需要的水平。至少很难达到让这些数据都在一个进程中处理的性能。

这样,除了 RPC 接口,我希望再提供一个更直接的 api 采用共享状态的方式来操控数据。如果我们认为两个实体的数据交互很频繁,就可以想办法把这两个实体的运行流程迁移到同一台物理机上,让同时处理这两个对象的进程可以同时用共享内存的方式读写两者的数据,性能可以做到理论上的上限。

ok, 这就涉及到了,如何让一块带结构的数据被多个进程共享访问的问题。结构化是其中的难点。

方案如下:


我们认为,需要交互和共享的数据,就是最终需要持久化到外存中的数据。整体上看,它好像一个小型内存数据库。它一定可以通过类似 google protocol buffers 的协议来序列化为二进制流。它和内存数据结构是有区别的。主要是一些约束条件,让这件事情可以简单点解决,又能满足能想到的各种需求。

数据类型是有限的:

  1. nil
  2. number
  3. boolean
  4. string
  5. map
  6. array

以上 6 种类型足够描述所有的需求,这在 lua 中已得到了证实。不过这里把 lua 的 table 拆分为 map 和 array 是对 protobuf 的一种借鉴。这里的 map 是有 data scheme 的,而不是随意的字典。即 key 一定是事先定义好的原子,在储存上其实是一个整数 id ,而 value 则可以是其它所有类型。

array 则一定是同类型数据的简单集合,且不存在 array 的 array 。这种方式的可行性在 protobuf 的应用中也得到了证实。

本质上,任何一个实体的所有数据,都可以描述为一个 map 。也就是若干 key-value 对的集合。array 只是相同 key 的重复(相当于 protobuf 里的 repeated)。

这里可以看出,除了 string 外,所有的 value 都可以是等长的,适合在 C 里统一储存。每个条目就是 id - type - value - brother 的一组记录而已。

其中 map 用二叉树的方式储存就可以满足节点的定长需求,左子树是它的第一个儿子,右子树是它的兄弟。

我们用一个固定内存块来保存整块数据,里面都是等长的记录,map 的记录中,左右子树都用保存着全局记录序号。

string 需要单独储存,所有的 string 都额外保存在另一片内存中(也可以是同一片内存的另一端)。在记录表中,记录 string 内容在 string pool 中的位置。

这样做有什么好处?

由于数据有 scheme(可以直接用 protobuf 格式描述),所以数据在每个层次上的规模是可以预估的,数据都是以等长记录保存的,对整个数据块的修改都可以看成是对局部数据的修改或是对整体的追加。这两个操作恰巧都可以做成无锁的操作。

换句话说,每次对整颗树具体一个节点的修改,都绝对不会损坏其它节点的数据。


有了这块组织好的数据结构有什么用呢?首先持久化问题就不是问题,但这只是一个附带的好处。这块数据虽然能完整的记录各种复杂的结构数据,但不利于快速检索。我们需要在对这颗树的访问点,制作一个索引结构。如果导入到 lua 中,就是一个索引表。当我们第一次需要访问这颗树的特定节点:体现为读写 xxx.yyy.zzz 的形式,我们遍历这颗树,可以方便的找到节点的位置。大约时间复杂度是 O(N^2) :要遍历 N 个层次,每个层次上要遍历 M 个节点。当然这里 N 和 M 都很小。

一旦找到节点的位置,我们就可以在 lua 中记录下这个绝对位置。因为每个节点一旦生成出来,就不会改变位置了。下次访问时,可以通过这个位置直接读写上面的数据了。


string 怎么办呢?我的想法是开一个 double buffer 来保存 string 。string 和节点是一一对应的关系。当节点上的 string 修改时,就新增加一个 string 到 pool 里,并改变引用关系。当一个 string pool 满后,可以很轻易的扫描整个 string pool ,找到那些正在引用的 string ,copy 到另一个 string pool 中。这个过程比一般的 GC 算法要简单的多。


最后就是考虑读写锁的问题了。只有一些关键的地方需要加锁,而大部分情况下都可以无锁处理。甚至在特定条件下,整个设计都可以是无锁的。

btw, 这一周剩下来的时间就是实现了。多说无益,快速实现出来最有说服力。按照惯例,应该会开源。

Comments

是啊,我觉得我们的服务器也没这么复杂

楼主好多东西弄得好复杂。做过几个游戏的,游戏后台根本没这么复杂。对于有经验的游戏团队,关键还是在于策划啊。

string 的实现很难保证效率,特别是对于频繁修改的情况下。 是否可以考虑从实际情况考虑,而非算法角度,使用定长或者增量定长的方式?

"技术方案的争议在我们几个人内部是很激烈的。让自己的想法说服每个人是很困难的。"
在帖子里看不到其它的方案啊?优缺点?如果争议很激烈那么肯定有另外不错的方案。开发笔记如果是一个团队的笔记,各个角度的记录,会更有价值。当然,就是不知道团队内其他成员是否认同云风开发笔记的观点,是否也能一起完成开发笔记。相信是一个不错的实践。

游戏开发 感觉我有点扛不住

这个设计让我想起了lisp,另应该可以实现部分数据加载的特性。

求细节设计,比如那个ID是什么作用?

我觉得这种方式的问题和多线程滥用的问题类似:引入了太多不必要的复杂性,如果本来可以很简单的逻辑因此而不得不依赖于事务机制,那么似乎有违kiss原则。

我觉得这种方式的问题和多线程滥用的问题类似:引入了太多不必要的复杂性,如果本来可以很简单的逻辑因此而不得不依赖于事务机制,那么似乎有违kiss原则。

有两点
1.定长结点以及他们的链接关系
主要是后者,云风这里是打算非常精细地处理链接关系的改变,使得每个处理都是事务的

2.跨进程主要考虑某些进程操作一半abort的情况,这里只能用容忍部分结点泄漏的方式

主要是事务,通常用invalid flag的方式可以解决大部分问题。。

这篇笔记描述的是底层的进程间共享复杂数据的问题, 至于并发的原子性和事务性保证的问题云风认为是上层再去实现的. 这两个层次就描述了一种高效的内存数据库, 不过要在进程间而不是线程间实现这种共享内存的高效, 确实很有挑战性, 尤其是跨C和Lua之间的共享.

数据和逻辑分开的思想个人也比较赞同!!不过这个也要看情况而定,有些运行动态数据,和逻辑紧密相关的,建议还是跟着逻辑走更方便一点,这个会直接影响后续的开发效率。比如场景数据和玩家NPC的运动逻辑,这个分开来会得不偿失。技术方案没有对错之分,特别对于前期的团队,如何更快的去实现产品原型,会显得更重要

云风永远是神

会不会有多个对象写同一个数据的情况,怎么保证正确性啊

话说如果数据和逻辑在物理上分离,那么意味着逻辑读数据的存取都是异步操作,这时要确保操作的原子性和时序就会很困难吧。如果再为了确保原子序和时序而把机制弄得更复杂,可能会得不偿失。我觉得数据和逻辑如果本质上就是紧密关联的,那么在实现时也应该用紧耦合的形式。

没看懂 不过好象很厉害的样子

>>如果我们认为两个实体的数据交互很频繁,就可以想办法把这两个实体的运行流程迁移到同一台物理机上,让同时处理这两个对象的进程可以同时用共享内存的方式读写两者的数据,性能可以做到理论上的上限。

感觉这个是关键。

另,高性能并发最好从core和cache的层次来考虑。而不是寄希望于lua和JIT,哪怕是C。

@Atry

那不是这个层次解决的问题. 等这个实现完了, 我再去考虑.

那如果需要同时修改两个节点怎么办?

Post a comment

非这个主题相关的留言请到:留言本