« 我们需要一个怎样的动画模块 | 返回首页 | Factorio 的乐趣 »

支持惰性展开和差异更新的 Lua 表

年前最后两天,陆续给我们组的同事批了假,都回家过年了。我留守在公司做点项目无关的东西。

最近在 skynet 的讨论版有人讨论配置表的更新问题。这几年,不管在公司内,还是从外部听见,总有人在讨论这个问题。我重新理了一下需求:

  1. 数据以 Lua table 的形式提供:支持 Lua 所有的内置类型:整数、浮点数、子表 、字符串、布尔量。可选支持函数、指针。
  2. 数据表通常有很多(冗余)数据,但大多数情况下只会用到一下部分,初始化的过程应尽量快。
  3. 如有可能,少占内存。数据表属于不变数据,应尽可能的在多个 VM 间共享。数据表应对 GC 有尽可能少的影响。
  4. 可以在不关闭 VM 的前提下,更新数据。
  5. 访问数据表应遵从 Lua 的使用惯例,并尽可能和原生表性能一致。

以上这些点很难同时全部满足,所以我给过许多不同的解决方案,都只是针对其中一部分需求。其中,性能最好的应该是 sharetable 这个方案,它是通过修改 Lua VM 的实现,做到了跨 VM 的数据共享。访问 VM 外的数据表的性能和本地数据完全一致。

如果使用传统方法,把数据放在 C userdata 里,例如 sharedata 方案,性能势必会打折扣。这是因为通过 metatable 读写数据,必须经过 Lua 的函数调用,它比 Lua Table 的访问要慢很多。

我这次做了一个中间方案,可供特别需求选用。

如果我们把数据全部放在 C 结构中,那么共享数据也就不成问题。为了提高 Lua 侧的访问速度,可以采用惰性复制的方式:未曾访问过的数据就留在 C 结构中、只要数据访问过一次,就复制到 Lua VM 中,后续访问就和原生数据结构完全一致。


那么、数据更新该怎么做?

如果我们让数据表只支持树结构,即节点不可以复用、不可以有环。同时,节点的 key 只可以是字符串和数字,那么,这个树状数据结构中,每个节点都有唯一的标识,即它从根节点开始抵达的唯一路径。

对于配置表的更新来说,往往不太修改表的结构,只动内部的数据。大多数场合,节点的 key 的名称都是有限的。如果我们收集所有 key 的名字,维护在一个集合中,并在更新过程中,只增不减。那么,我们就可以对每一个存在过的 key 赋予唯一的数字编号。同样,每一条通向数据节点的路径也可以有唯一的编号。

换句话说,一个节点,它的唯一标识如果是 a.b.c ,编号为 42 ,在未来的更新中,只要这个标识不变,就表示是同一个节点。a.b.c 可以在某次更新中被删除,但编号会永久保留。后续如果重建了 a.b.c ,编号依然是 42 。

基于这个原则,就可以方便的做数据表的数据更新。我们用一张弱表记录下所有被展开过的数据表的引用。一旦数据发生更新,就清光所有旧数据,并把这些表还原成(依赖唯一 id )待惰性展开的状态即可。这比 sharetable 的更新方案中,扫描整个 VM 找到被引用的共享表要高效的多。

我快速的实现了一下上面的想法:https://github.com/cloudwu/datatree

数据结构 datatree 分为两个部分。作为宿主,它是一个 Lua 结构,可以通过 update 方法更新数据。所有更新历史中的数据结构都被记录下来,但只保留最后一个版本的数据。

这个结构可以通过 pack 方法把最后一个版本的数据打包成一个 C userdata 。值得一提的是,这个 C 数据会被打包成一个连续的内存块,且内部没有任何指针。所以,你甚至可以把它直接保存到文件中,可以看成是一种 Lua 数据结构的持久化数据块。如果需要,可以用 mmap 映射到内存直接使用。

我们可以在不同的 VM 创建 shadow 对象,它的 update 方法接受前面打包的 C userdata 地址即可,并可返回一个能惰性展开的 Lua 对象。这个对象可以如普通 Lua 表一般使用。这个 update 的运行时间复杂度是 O(1) 的,只做非常少量的初始化工作。数据全部在在访问时按需从 C 结构中复制出来,而 C 数据结构被设计成可以方便的随机访问,展开每个节点的开销只和节点本身的数据大小有关,和包的大小无关。因为 update 对 C userdata 完全是只读访问的,所以它是线程安全的。


这个方案不仅仅可以用于 skynet 这种服务器环境。我觉得在客户端也可以使用。它的优势是避免大量数据的初始化开销。

相比之前的 sharetable ,劣势在于数据没有在 VM 间共享,多 VM 环境会浪费一些内存。且从 C 结构中复制数据到 Lua 中也有额外的一次性开销,只不过这个开销是分摊到很长一段时间上了。

Comments

冒个泡

优秀的skynet

Post a comment

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