« 为 bgfx 设计了一个 IDL | 返回首页 | 并发 Hash Map 的实现 »

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

这几年,我一直在寻找不同 Lua 虚拟机间共享大量不变的结构化数据的方法。因为这对于游戏这类数据驱动的软件是非常重要的需求。我们现在正在运营的游戏“风之大陆”,服务器上的策划生产出来的数据表格,转换为 Lua 源文件后,就已经达到了 300M 之巨,全部加载到 Lua 虚拟机中,会消耗 700M 内存。

我为这个需求实现过好几套方案:最初是 Sharedata 这个模块,后来又实现了一个叫 DataSheet 的替代品。

过去的方案用的思路都是把数据表放在 C 对象中 。Lua 中建立一个 proxy 对象去访问它。C 对象可以跨虚拟机共享,proxy 对象则在不同的虚拟机中各创建一份。

这种方式比较符合 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 结构。

Comments

看来隔离出大量虚拟机的做法也是有不少代价的, 如此体量的工程用Lua总觉得不堪重负了.
楼下的方式加载数据非常适合用内存映射, 不过需要组织好利于访问的数据结构.

策划编辑的都是静态数据吧。如果是只读数据,不需要游戏中编辑,完全可以做到只分配一次内存,只读一次。数据的查找方式,数据结构什么的都可以以二进制的方式存在磁盘上一次读进来的,如果再做点相同数据的复用。理论上内存里的数据是应该和磁盘上一样大,比实际的数据容量应该还要小一点。然后服务器内存应该不是什么需要优化的地方,一般情况不是太离谱都不会是瓶颈,区区几百M根本不算什么。

尝试把配置表转换成字符串然后通过弱表控制然后被清理了重新loadstring,内存是降了很多控制住了,请问效率方面会得不偿失么

Post a comment

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