开发笔记 (6) : 结构化数据的共享存储
开始这个话题前，离上篇开发笔记已经有一周多了。我是打算一直把开发笔记写下去的，而开发过程中一定不会一帆风顺，各种技术的抉择，放弃，都可能有反复。公开记录这个历程，即是对思路的持久化，又是一种自我督促。不轻易陷入到技术细节中而丢失了产品开发进度。而且有一天，当我们的项目完成了后，我可以对所有人说，看，我们的东西就是这样一步步做出来的。每个点滴都凝聚了叫得上名字的开发人员这么多个月的心血。
技术方案的争议在我们几个人内部是很激烈的。让自己的想法说服每个人是很困难的。有下面这个话题，是源于我们未来的服务器的数据流到底是怎样的。
我希望数据和逻辑可以分离，有物理上独立的点可以存取数据。并且有单独的 agent 实体为每个外部连接服务。这使得进程间通讯的代价变得很频繁。对于一个及时战斗的游戏，我们又希望对象实体之间的交互速度足够快。所以对于这个看似挺漂亮的方案，可能面临实现出来性能不达要求的结果。这也是争议的焦点之一。
我个人比较有信心解决高性能的进程间数据共享问题。上一篇 谈的其实也是这个问题，只是这次更进一步。
核心问题在于，每个 PC (玩家) 以及有可能的话也包括 NPC 相互在不同的实体中（我没有有进程，因为不想被理解成 OS 的进程），他们在互动时，逻辑代码会读写别的对象的数据。最终有一个实体来保有和维护一个对象的所有数据，它提供一个 RPC 接口来操控数据固然是必须的。因为整个虚拟世界会搭建在多台物理机上，所以 RPC 是唯一的途径。这里可以理解成，每个实体是一个数据库，保存了实体的所有数据，开放一个 RPC 接口让外部来读写内部的这些数据。
但是，在高频的热点数据交互时，无论怎么优化协议和实现，可能都很难把性能提升到需要的水平。至少很难达到让这些数据都在一个进程中处理的性能。
这样，除了 RPC 接口，我希望再提供一个更直接的 api 采用共享状态的方式来操控数据。如果我们认为两个实体的数据交互很频繁，就可以想办法把这两个实体的运行流程迁移到同一台物理机上，让同时处理这两个对象的进程可以同时用共享内存的方式读写两者的数据，性能可以做到理论上的上限。
ok, 这就涉及到了，如何让一块带结构的数据被多个进程共享访问的问题。结构化是其中的难点。
方案如下：
我们认为，需要交互和共享的数据，就是最终需要持久化到外存中的数据。整体上看，它好像一个小型内存数据库。它一定可以通过类似 google protocol buffers 的协议来序列化为二进制流。它和内存数据结构是有区别的。主要是一些约束条件，让这件事情可以简单点解决，又能满足能想到的各种需求。
数据类型是有限的：
- nil
- number
- boolean
- string
- map
- 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
Posted by: wangchunye | (18) November 8, 2012 11:44 AM
Posted by: 偏复杂 | (17) July 24, 2012 09:52 AM
Posted by: pthread_t | (16) May 21, 2012 02:53 AM
Posted by: river2202 | (15) January 2, 2012 10:53 PM
Posted by: 语录搜 | (14) December 27, 2011 12:13 AM
Posted by: lokiwang | (13) December 22, 2011 02:00 PM
Posted by: sjinny | (12) December 17, 2011 10:34 AM
Posted by: sjinny | (11) December 17, 2011 10:33 AM
Posted by: sunnyxu | (10) December 16, 2011 11:41 AM
Posted by: dwing | (9) December 16, 2011 10:39 AM
Posted by: arrow | (8) December 16, 2011 10:25 AM
Posted by: 小龙红 | (7) December 16, 2011 10:08 AM
Posted by: somking | (6) December 15, 2011 11:51 PM
Posted by: sjinny | (5) December 15, 2011 11:32 PM
Posted by: cat | (4) December 15, 2011 11:23 PM
Posted by: mataxa | (3) December 15, 2011 09:04 PM
Posted by: Cloud | (2) December 15, 2011 08:48 PM
Posted by: Atry | (1) December 15, 2011 08:39 PM