支持惰性展开和差异更新的 Lua 表
年前最后两天，陆续给我们组的同事批了假，都回家过年了。我留守在公司做点项目无关的东西。
最近在 skynet 的讨论版有人讨论配置表的更新问题。这几年，不管在公司内，还是从外部听见，总有人在讨论这个问题。我重新理了一下需求：
- 数据以 Lua table 的形式提供：支持 Lua 所有的内置类型：整数、浮点数、子表 、字符串、布尔量。可选支持函数、指针。
- 数据表通常有很多（冗余）数据，但大多数情况下只会用到一下部分，初始化的过程应尽量快。
- 如有可能，少占内存。数据表属于不变数据，应尽可能的在多个 VM 间共享。数据表应对 GC 有尽可能少的影响。
- 可以在不关闭 VM 的前提下，更新数据。
- 访问数据表应遵从 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 中也有额外的一次性开销，只不过这个开销是分摊到很长一段时间上了。