不同虚拟机间共享不变的 Table

这种方式比较符合 Lua 正统，但缺点有二：

1. 如果数据表结构比较复杂，那么每一层的子表都需要创建 proxy 对象。如果访问的数据较多，proxy 对象的总量还是很大的，依旧有很大的内存开销。

2. 通过 c function 访问 C 对象，比直接访问 table ，开销要大的多。而且字符串在 Lua 虚拟机和 C 对象间传递，也有不小的开销。（这也是用 DataSheet 取代 ShareData 的主要动机）

我一直没有放弃通过修改 Lua 虚拟机来更好的解决这个问题。曾经尝试过很多方法，但直到最近才觉得找到了比较合理的方案。

前几天， 我尝试改进了虚拟机间共享函数原型的方案 。核心思想就是共享原型用到的常量表。随之想到，如果一张表的 key value 都只有数字、布尔量、轻量 C 函数和字符串的话，那么我们也可以像共享函数原型那样共享表。

我们只需要解决两个小问题：

1. 被共享的表必须是不可变的，这样才可能做到线程安全。

2. 被共享的表需要脱离局部虚拟机的 GC 流程。

第一个问题可以通过元表解决。我们可以设置一个空表作为 proxy ，附上一个元表，将 index 指向真正的数据表，newindex 指向异常函数。就可以阻止用户改写数据，且只增加了稍许访问代价：index 是一张表时运行效率比是一个 function 要高的多。

第二个问题需要改动一点点虚拟机源码。我的方案是从 Table 这个内部类型中，原本用来加速 metafield 访问的 flags 字段上借一个 bit ，用来表示这个 Table 是从外部共享进来的，在 GC 的 mark 流程，一旦标记到这里，就不再继续遍历。

剩下的工作就简单了。

可以为共享数据表创建一个独立的虚拟机，在共享前，按第一点方案，把所有字标都转换为只读表，顺便检查整个表是否符合共享需求：不能有 Thread Function Userdata 等类型的数据在里面。然后就有可能把 Table 指针直接交出去，复制到别的虚拟机直接访问。

但是，和共享函数原型的常量表遇到的问题一样，有可能有一些例外。这是因为，我们的短字符串还不能做到虚拟机间的完全共享。 关于这部分的工作，我在 2015 年介绍过 。前几天也提到，Erlang 为了解决类似问题，是把 atom 和 string 作为两种类型看待的，而 lua 并不区分。如果我们把所有虚拟机的短字符串统一管理，那么 gc 的问题极难解决。所以我采用了一个变通方案，在一部分时间，受控的开放全局短字符串表（称为 SSM ），这段时间运行所生成的短字符串全部视作 erlang 的 atom 类似物，进入 SSM 不再删除，且可以被所有虚拟机共享；当 SSM 关闭时，虚拟机继续在本地生成独立的短字符串。我暂时称之为 LSS （local short string ） 。

如果一个字符串已经是 LSS ，那么和它相同的字符串就无法进入这个虚拟机。这种情况比较罕见，但有可能出现。如果一个函数原型的常量表中出现一个至少一个字符串必须是 LSS ，那么我们就将整个常量表按原有方法复制一份。对于共享函数原型来说，就是这样的解决方案。实际应用的时候，我们几乎没有碰到过这种例外。所以这仅仅是一个后备方案，仅在测试代码中故意构造出来。

对于共享数据表面临的问题是一样的。如果出现了一个 LSS 怎么办？

我的方法是在本地创建一个 proxy 表取代母体中的那个用于阻止数据改写的 proxy 。把出现 LSS 的键值对拷贝到本地 proxy 中，就解决了访问问题。

稍微麻烦的是遍历的需求。对于 LSS 出现在 value 中比较简单，专门写一个 pairs 函数，每次都取一下 key 对应的 value 即可。

当 LSS 出现在 key 时，就无法简单处理（因为 LSS 的 key 和母体的 key 是两个不同的TString 对象，很难无状态迭代）。我就在 pairs 时拷贝整个子表。

我用线上产品的 300M 数据表做了测试，不会出现这种例外，所以以上的方案依旧是后备方案，目前也只是刻意构造的测试案例才会触发。

我想，这会是我为 skynet 解决数据表共享做的最终尝试，它可以较完美的解决性能开销问题，又能简化使用。未来建议淘汰掉 skynet 中 sharedata 和 datasheet 模块的使用。

目前 sharetable 这个新特性，我暂时放在分支中，欢迎同学们试用。但需要留意数据热更新的问题（如果你有这个需求）。

在实现这个新特性时，我反思了热更新数据这件事。我认为之前无论是 sharedata 和 datasheet 都多做了很多工作。我认为热更新本身应该从共享数据模块中剥离出来，留给使用者自己实现。所以新的 sharetable 只提供了 query 一个方法，每次远程 query ，都从母体索取最新的一个指针，放在本地制作克隆体。如果产生新的母体（用户加载了一份新数据表），应该执行维护一套机制通知引用之前版本的服务，然后每个服务自信 query 新副本。

关于老版本数据的回收，我认为可以也只能放在服务退出的时机。因为没有好的方法回收数据表中的（字符串）数据。而共享表母体中的字符串的生命期必须由母体持有。服务退出是一个好时机，因为它彻底结束了所有引用对象，方便我们做引用计数。

我认为共享数据表不仅仅在 skynet 环境有用，在客户端也是很有价值的。因为我们可以把数据表抽出来放在逻辑虚拟机之外的独立虚拟机里，以共享形式引用回去。这样，就极大的减少了逻辑虚拟机内的对象个数，可以极大的减轻 GC mark 流程的负担。这是过去几年，很多同学问过我的问题：有没有可能告诉 Lua 的 GC ，这一堆（几千个）对象我会一直使用，不要每轮 GC 都遍历一次？这一篇就是我的答案：我们可以做到。

另外，skynet 现在使用了一个独立的 Lua 虚拟机存放 Env （数据表）。访问 Env 需要一个全局锁。如果我们禁止运行时修改 Env 的话，那么也完全可以用共享表的方式来实现 skynet.getenv 方法了，避免了全局锁。

最后，反观整个方案，我认为核心机制是很简洁的。但实现的时候，有大量的复杂度花在了罕见情况的处理上。也就是 LSS 的存在。

那么有没有可能彻底去掉 LSS ，将所有 Lua 虚拟机中的短字符串统一管理呢？如果可以解决这个问题，之前的共享函数原型、以及这次共享数据表，都可以大大简化实现。

上一次思考这个问题是在 4 年前，当时我觉得实现一个全局 GC 不太可能兼顾简洁和高效，并适应高并发环境。但今天和同事重新讨论这个问题，我在重新讲解当初的思考过程时，突然发现，或许我还有一条路可以走。

接下来几天，我打算实现一下新的想法：

我们的需求是：

1. 把所有的短字符串放进同一张 hash 表里。这个 hash 表必须是适应高并发的。实现一个高并发且有弹性的 hash 表。

2. 需要跟踪每个独立的虚拟机所引用的短字符串，不再引用的字符串需要通知 SSM ，一旦所有虚拟机都不再引用一个字符串，就需要适机删除。也就是需要一个全局的 GC 来管理全局短字符串。同样，这个 GC 需要适应并发环境。

关于第一点，4 年前我实现了一个简洁的高并发 hash 表，但弹性不足。因为最早的需求我们只需要 SSM 中存放固定上限数量的字符串就够了，所以可以固定 hash 的规模。一旦我们无法预期 SSM 最终会存放多少字符串，那么就需要给 hash 表增加弹性，在字符串增加时，可以扩展桶的数量。增加弹性的同时，还需要兼顾高并发。我上周花了几天的时间做这项改进工作。其细节打算在下一篇 Blog 再介绍。

第二点，当初我没有找到好的解决方案。但今天我认为是可行的。

首先，我们需要把短字符串从单个 Lua 虚拟机内剥离出来，用引用计数来管理。理论上一个虚拟机引用一个字符串就加一次引用计数，不再引用就减一次引用。当然，加多次也是可以的，只要能正确的减少相同的次数。

怎么混合引用计数和 Lua 原本的标记清理 GC 呢？

我们可以认为，Lua 从外部引入一个短字符串，是有一个唯一的创建字符串的入口函数的，在这里，我们可以加引用。所有在本地虚拟机加过的短字符串，都能在这里加到一个集合 A 中。

在本地虚拟机的 GC Mark 流程，一旦碰到一个 GC 对象，目前的做法是在 GC 对象上做一个标记；但我们完全可以针对短字符串类型做不同的处理，比如放去一个集合 B 中。

在一趟 GC 循环结束，我们就可以得到一个完整的集合 A 和一个集合 B 。

这时，所有存在于集合 A 但不存在于集合 B 中的短字符串对象，都是本地虚拟机不再引用的，可以安全的减少引用计数了。

这就是标准的标记清除的 GC 算法，但是，通常，我们是在对象本身上设一个标记位，来标记对象是否在集合 B 中。这是最高效的做法。Lua 的 GC 就是这样工作的。

但这次，我们不能直接通过在对象上做标记的方式，标记一个对象属于集合 B 。这是因为同一个短字符串对象会属于大量不同的虚拟机中的集合 B 。所以标记位不能放在 TString 结构里。不过，我们真的可以用一个集合来解决这个问题呀。

同一个虚拟机中，短字符串几乎一定会出现很多次（做 key 的时候），我们可以用一个 cache 优化它。做一个不会扩展的 hash 表，只 cache 最后一次 mark 的 TString ，下一次 mark 的时候，如果碰巧在 cache 中找到它，就不必重复放在集合中。Lua 目前就是用类似的方法优化 lua_pushstring 的。

有趣的是，每轮本地 GC 循环结束，当前轮的集合 A 和集合 B 就不再需要了，因为它们仅对回收资源有意义，我们只需要把其所有权转交给全局 SSM 持有就好了。一个简单的全局队列就了能做到这一点。而分析比对 A 和 B 的差异，我们完全可以交给一个独立线程慢慢运作。这样，我们就有了一个简洁的并行 GC 结构。