设计了一个数据格式

云风 2019-01-31 14:06

最近一段时间在忙着设计和实现我们游戏引擎用到的数据格式。

在此之前,我们一直在直接使用 lua 描述数据;但最近随着数据类型系统的完善,同事建议设计一种专有数据格式会更好。希望专用格式手写和阅读起来能比 lua 方便,对 diff 更友好,还能更贴近我们的类型系统,同时解析也能更高效一些。lua 的解析器虽然已经效率很高,但是在描述复杂数据结构时,它其实是先生成的构造数据结构的字节码,然后再通常虚拟机运行字节码才构造出最终的数据结构。这样的两步工作会比一趟扫描解析构造要慢一些且消耗更多的内存。

现有的流行数据格式都有一些我们不太喜欢的缺点:

json 是目前最流行的,但是它更适合通讯协议,数据由程序生成。对手写和阅读不是很友好:json 不支持注释;字典结构中 key 需要给字符串加引号,显得累赘。支持的数据类型有限,不易扩展数据类型。另外,标准 json 无法对浮点数做精确表达。

xml 是另一种通用选择。它比 json 更严谨,在扩展数据类型方面很方便。但 json 有的缺点它更盛:在手写的时候,往往一个很简单的值,需要额外写很多格式要求的信息,不借助专有编辑器时,书写不太方便。阅读起来有效信息比很低,需要借助专有查看器才能变得方便。冗余信息太多导致对 diff 也不算太友好。

ini 格式在 windows 上很流行,在 windows 之外也有很多人用。但是它做配置文件很舒服,描述复杂数据结构的话却有点力不从心。ini 只是在键值对的数据组加了一个层次,如果要描述多层结构,就很难沿用一致的语法。

lisp 是我所青睐的。Paradox 的数据格式就是采用的类 lisp 结构。据说顽皮狗的引擎也使用了 lisp 做内部数据结构。不过同事不太喜欢太多的括号,我也觉得这点值得改进。

yaml 看起来是最符合易于书写和阅读的格式。但它的解析器过于复杂,虽然格式设计上是为了方便一趟扫描解析,但现在依然没有一个特别高效的实现。我曾经跟踪过很长时间 libyaml 这个项目,贡献过 bugfix ,提过建议 。其中一个建议被开发团队持续讨论了一年多。因为要考虑多语言实现的 yaml 的一致性,所有细节都必须被反复推敲。不能产生方言:否则在一种语言环境上编码的数据,去到另一个环境就无法正常解析,这就失去了数据交换格式的意义。考虑到 yaml 相当复杂的格式定义,和诸多的实现版本,这太难了。后面我还会提到一些小的特殊需求,实际上扩展 yaml 是不实际的(很难被接纳),还不如干脆自己设计一套不是 yaml 的新格式,这也是最近这些工作的动机。

设计并实现一个专有数据文件格式,在提出要做这么一件事之前,我觉得我们的项目并不需要多复杂的东西。保留一定的通用性的前提下,设计的足够简单,满足我们的需求就好了。已有的数据格式不喜欢,那么改成我们喜欢的样子,我觉得有一个下午就能搞定。

在那个冬日的周末,中午的太阳晒得人懒洋洋的。我乘娃打了个哈欠,赶紧把他哄睡着。打开编辑器,想着儿子醒来前这几个小时差不多够用了。

事实上并没有这么简单。

第一版我对 Paradox 的数据格式做了一个简单的模仿。曾考虑过用 lua / lpeg 来实现,但又感觉未来可能需要更高的性能,且格式不复杂,用 C 实现也可以很清晰,不必列出 BNF ,不需要用 yacc 。手写一个解析器不过几小时的工作。实现的时候,我还顺手加上了一点我觉得方便的特性:在解析到 lua 中时,可以通过使用 [] 或 {} 来选择把字典解析成列表还是字典。整个解析器不过几百行 C 代码,一趟扫描就可以完成,并生成 lua 的数据结构。

周一拿给同事看的时候,并不满意。从原来 lua 数据文件中转过来的数据文本中太多的括号看起来并没有比原来 lua 版本好看多少。尤其是在序列化内存的大量 Entity 时,最外层结构需要一个数据列表,感觉 ini 风格的 section 分段会漂亮很多。

ini 风格的 section 是用 [name] 这样的形式来区分段落的。因为缺少括号,必须依赖下一个段落的开始来结束上一个段落。这样,就很难表达多级层次。我考虑借鉴 markdown 的方法,用 ### title 来表示段落。井号的数量可区分不同层。同时,还是想保留括号作为可选项。因为在描述一个向量的时候,我更希望沿用 { 0,0,0,1 } 这样的风格。

没有结束符的区段结构,解析器写起来要麻烦许多。更重要的是要防止人误用产生有歧义的结构文本。我决定让段落标识只能出现在最外层,一旦使用 {} 表示内部层次,内部层次中就不可以再出现段落符号。

做这个新特性时,我发现之前快速写出来的词法解析及语法解析模块很按新需求扩展。我意识到未来很可能还会做大改变,干脆就推倒重写,这次不图快,尽可能的写清晰,用更直白(但更啰嗦)的实现。

完成之后,我们查看了生成的数据,发现虽然语法上可以表达出层次,但是没有缩进的多层结构实在惨不忍睹。或许是程序员早已习惯了视觉空间上的变化来表达层次结构吧,光有标签是不够的。最后还是为生成的数据加上了缩进。而解释器会简单的将缩进当成分隔符忽略掉。

可是既然有了缩进表示层次,我们何必再用蹩脚的段落表示方法呢。

再一次的大改就是去掉新加的特性,转而用缩进来表示层次。当然,{} 的层次表示方法还是保留的。同样不能混杂使用,只能从外层开始使用缩进,一旦开始用 {} 后,缩进就变成了简单的分割符。

这里我们不想规定缩进到底是 tab 还是空格,是 2 个还是 4 个或 8 个。我对 yaml 略有怨言的地方就是它不能用 tab 缩进,这不符合我的编辑习惯。本质上,缩进就是把层次信息加在每行元素上,从而可以省略层次结构结束的标记。我们只需要认为同样的缩进串表示的是同级的层次,不同的缩进串将关闭前一个层次。理论上,你想把外层向内部从长到短反着排版都没关系,只要保证同层的行的缩进串是相同的就够了。

但我并不想给这种灵活性,允许排版成奇怪的样子没什么好处。最终我还是规定更深的层次必须有更长的缩进串,但不规定每个新层次需要累加固定的长度。比如第二层可以用两个空格,第三层加到 6 个或者家一个 tab 也是没关系的。

另外,我增加了 yaml 里用 --- 表示区段的方法。这可以减少最外层的缩进。这是一个喜闻乐见的特性,在很多数据文件格式中都可以看到类似的东西。比如 record-jar 就用 %% 来表示分段。

主体功能完成后,整个结构看起来就像一个简化版的 yaml 。最直接的改进就是可以比标准 yaml 解析要高效的多。如果做配置文件,效率不会是问题,但我们的游戏引擎打算把它做成通用数据格式,效率高一点可以缩短日后的管卡数据加载时间。

接下来就是加一些 yaml 中没有,或是难以实现,但我们又需要的特性了。

其一就是 anchor 的向后引用。yaml 可以用&anchor的方式对一组数据做一个锚点,然后之后用*anchor对之前的结构进行引用。这是一个很有用的特性,在别的格式中很难做到。我们在序列化场景树时就用的上:*anchor相当于一个指针,可以指向另一个数据结构。这可以避免直接序列化整棵树导致的缩进层次过大。且能解决 DAG (有向无环图)的序列化问题:多个孩子引用了同一个子节点。

但是 yaml 为了解析器实现方便(保证可以一次扫描解析完毕),它规定,对锚点只能做向前引用,即必须先声明锚点,才可以对其引用。锚点可以重复,总是引用最近的一个。

这导致有环的图无法被描述出来。我想去掉这个限制。在 Lua 中,所有复杂数据结构都是用 table 统一承载的,而我们几乎只在 Lua 中使用这个数据结构,这就可以用一种技巧来解决向后引用的问题:我们只需要在解析的时候碰到未定义的锚点时,提前把一个空 table 出来,等到锚点被定义时,再去填充这个 table 即可。

btw, Unity 就是使用 yaml 做数据描述,但并只是部分使用了锚点的机制。它定义了锚点,却没有用 yaml 的语法去引用它们。

另一个想改进的地方是自定义数据类型。yaml 是用自定义 tag 来实现的。通常解析器会提供 event 机制来触发自定义 tag ,动态语言封装解析库的时,接管这个事件来处理自定义数据。不过现有的实现做起来还是太麻烦且低效。

既然我们是专有格式,且只给 Lua 使用,就可以用一种取巧的方法来实现一个简化版本。

我的做法是,允许用户用 [] 取代 {} 来描述一个数据结构。但一旦采用 [] ,解析器在解析完毕后,回调一个用户函数,把数据过滤一次。对于 [ 0, 0, 0 ,1 ] 这样的向量,我们就可以简单的做一次后处理,加工成 lua userdata 返回出去。还可以对外部文件引用写成 [ file path ] 的形式,这是一个列表,第一个字段 file 表示这个自定义结构的类型,后面的是参数。Unity 在类似问题上处理要复杂一些,它对外部文件引用生成了一个类似 {fileID: 400000, guid: 5df3a2b3f00ce8a418ad24d290ed5deb, type: 3} 的数据结构,我猜测这依赖更高层模块的解析,而无法在读取 yaml 的时候同步完成。

这个项目的 github 仓库在这里。原本以为一个下午就可以搞定,可目前距离第一次提交已经三周了。

等稳定后,我会将这个仓库合并入引擎的主干。

[返回] [原文链接]