云风的 BLOG

Lua 中的短字符串做了 string interning 的处理，即在同一个虚拟机内，值相同的字符串只存在一份。这可以极大的提高用字符串做 key 的 hash 表的查询速度。因为字符串比较的时间复杂度从 O(n) 下降到 O(1) ，比较查询的 key 和 hash 表内的 key 是否一致，只需要对比一下对象的指针是否相同即可。

我在解决多 Lua 虚拟机共享字符串对象这个问题时，合并了不同的 Lua 虚拟机中的短字符串表。让同一进程所有虚拟机共享一个短字符串表（ SSM ）。

我最初在实现 SSM 的时候，考虑到多虚拟机 GC 的复杂性，采用了只增不减的方案。即让部分短字符串进入 SSM ，设置一个上限，避免 SSM 无线膨胀。但 Lua 并没有把经过 interning 处理的字符串作为独立类型，目前只用字符串长度作为区分，也就是无法和不 interning 的短字符串共存。所以，那些已存在本地虚拟机短字符串表中的字符串，就不从 SSM 中获取对象。

修改过 Lua 的 string interning 算法是这样的：

1. 查看字符串是否存在于本地字符串表 (LSM) 如果存在，就立刻返回。这一步和原版 Lua 一致。

2. 查看字符串是否存在于 SSM ，如果存在，就返回。

3. 检查是否 SSM 上限已到，如果不能再增加新字符串，把字符串添加到 LSM ，返回。

4. 将字符串添加到 SSM ，返回。

考虑到我们通常在一个进程中运行数千个 Lua 虚拟机，SSM 是一个比 LSM 大得多的 hash 表，需要极高的并发访问性能。

我在最初设计时，考虑到 SSM 会设定一个容量上限，所以完全可以预估 hash map 大致需要多少个桶来避免最糟糕的 hash 冲突。如果桶的数量固定，那么就不必考虑 rehash 的过程。提高并发性能最简单的方法是对单个桶加小锁，避免对整个 hash map 加大锁。

做 string interning 时，先算出 hash 值，既而可以判定归属在哪个桶，这个过程是不需要加锁的。而大多数情况，我们对单个桶的读操作数量远超过写操作数量。因为 Lua 虚拟机在运作时，只有从外部构建字符串才会进行 interning ，内部字符串传递是不需要的。

每个桶一个读写锁非常合适。在没有 hash 碰撞发生时，不会有任何锁碰撞。如果桶的规模预估合理，hash 碰撞的概率就会降低到一个相对小的程度。我对 Lua 的 hash 算法和 hash 表的实现用大量数据做过测试，在 hash 表装满时，同一个桶下不同的字符串数量平均在 1.2 到 1.3 之间。可以认为，每次锁操作基本是 O(1) 的。

前段时间，我们增加了函数原型常量表的共享。每次加载新的代码，都临时打开了 SSM ，让新代码中的常量可以顺利进入 SSM 。做这次修改时，我在苏梅岛度假，没有太仔细考虑，结果放到线上，引起了一起事故。事故表现为服务器开启 2 天后，运行 CPU 负荷上升，导致玩家登录很慢，最终无法正常游戏。

事后追查原因是多方面造成的。首先，原来假定每次加载新代码临时打开 SSM ，这个操作是有限的，次数和源代码文件数量相关。实则并不是。打开 SSM 的位置不合理，lua require 时，整个搜索过程，包括那些尝试过，无法打开的文件，也被计入在内。最终打开 SSM 的次数远高于预期。

其次，打开 SSM 是通过增加上限容量 4096 来实施。给一个上限是为了控制最坏情况的出现。因为SSM 是全局的，不能单独控制当前工作线程。如果同时有另一个线程上跑了个 VM 在这段时间大量构造字符串，就会不断向 SSM 添加新元素。用一个上限控制，可以防止短时间添加了太多字符串。但是，我没有在关闭 SSM 后把这个容量调整回去。导致只要打开一次，SSM 最终一定会增加 4096 个新字符串。

由于我们一开始设计时，SSM 是不做任何 rehash 的，固定了 64K 个桶，所以在运行 2 天后，终于向 SSM 里添加了太多的元素。每个桶里都放了数百个元素，最长的超过了一千。这远超预估的 1.3 。

临时解决线上问题很简单，关闭 SSM 在加载源文件时，自动打开的机制即可。不过我在度假回来好好调查了整个问题，固然把 SSM 的开关控制可以更好的解决，依然能够把字符串重量控制在一个预计范围内，但我觉得还是有必要增加 SSM 的桶扩充的能力。

不过，实现 hash map 的 resize ，又不影响并发性能，就不那么简单了。避免在 hash map 的 resize 时 stop the world ，是需要解决的核心问题。

我现在采用的方案是这样的：

hash map 被分成两张表，A 表是读写表，可以插入新元素，也可以查询；B 表是只读表，只能查询。A 表和 B 表可以有重复项，任何一张表里存在一个元素，都认为这个元素存在。我们不处理删除元素的操作，所以不用考虑删除操作在 A B 表的同步问题。

插入操作一定向 A 表写入，查询操作则依次查询 A B 表。

在通常情况下，B 表是不存在的，所以无论是插入还是查询，都按过去的算法工作针对 A 表操作即可。

resize 是由固定线程主动检查整个 hash map 的状况触发，一旦发生，就创建出 B 表。这是通过给整个 hash 表加一个读写锁实现的。对于非 resize 操作，加读锁，保证操作过程中不会创建出 B 表；resize 则使用写锁，锁成功后，仅仅把原来的 A 表放到 B 的位置，转换为只读表；再创建出空的 A 表即可。这个过程极短，仅有两次指针操作。

所以，resize 启动本身可能被大量其它操作推延（任何操作都需要对 hash map 加读锁），但切换到 resize 状态， stop the world 的过程仅两次指针操作而已。

resize 的过程不可并行，也就是不能两个线程同时做 resize 。这是通过写锁后检查状态来判定的。如果两个线程同时想进行 resize ，第 2 个线程在写锁成功后，就能检查出已经有另外线程进入了 resize 工作（B 表已经存在），就立刻退出。

所以，对于 B 表，也就是过去一个阶段所有的元素都在这里，不会有人再修改它们。resize 过程就可以安全的把它们逐个转移到 A 表，即 resize 过程对 B 表是在不断改写的，但其它线程只能读取它。resize 过程就是循环逐个对 B 表中的每个桶做 rehash ，它是单独对每个桶上锁的，不会 stop the world 。一旦 resize 过程完成，再次对 hash 表加写锁，把已经是空表的 B 表删除。

下一步，我会给 SSM 加入 gc ，采用引用计数来删除不用的元素。因为删除是可选的，所以完全可以在查询字符串时，再判断引用计数是否为零，且只在非 resize 状态下，才进行删除操作。

在实现完后，Yang Xi 同学建议我看一下 2007 年 Google Tech Talks 上的 Advanced Topics in Programming Languages: A Lock-Free Hash Table 。我觉得思路是类似的。但是我需要解决的问题更简单，因为我无需处理删除 key 和修改 key/value 的操作。所以，resize 过程就只有 0 和 1 两个状态，无需做一个复杂的状态机。

我没有使用 lock free 的算法，是因为我认为只要把读写锁粒度控制的很细，锁内做的事务控制的足够少，性能上并没有劣势。结合我们的实际业务，我并需要实现一个通用的并行 hash map ，可以说这里采用 lock free 毫无优势。锁住后不加其它的锁，也不会有死锁的隐患。改成 lock free 难度并不大，但是要证明实现的正确，却比读写锁要复杂的多。

Posted by 云风 at 11:08 AM | Permalink | Comments (9)

这几年，我一直在寻找不同 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 结构。

我已经对 skynet 的 lua 做了全面修改，采用了这种方式，目前放在 ssm 分支上。

Posted by 云风 at 03:21 PM | Permalink | Comments (12)

上个月为 bgfx 贡献了一周多的工作时间，起因是 bgfx 的作者在我的 sproto 项目下发了个 issue （现在已经转到 bgfxidl 项目下）。他想为 bgfx 的接口设计一个 Interface Description Language ，这样可以避免手工维护多语言接口文件，还可以方便做许多代码生成的工作。

我在 2006 年左右尝试利用 COM 的 IDL 做过一些工作，想来这和 COM 面临的问题是一样的。我认为 lua 是一个可以用来做 DSL/IDL 非常好的工具，所以我向 bgfx 项目推荐了它。而且 bgfx 用的构建工具 Genie 就是基于 lua 的，这样工具链就比较统一。

一开始的需求仅仅是生成 C99 的 API 描述 .h 文件。lua 的函数调用，如果只有一个参数，且参数类型字符串常量或表，可以省略括号。这使得它的语法天生适合做数据描述语言，所以我给了这么一个方案：

func.createShader
    "ShaderHandle"
    .mem "const Memory*"

这样就定义了一个函数 createShader ，返回值为 ShaderHandle ，参数为 mem 其类型为 const Memory * 。一开始我觉得也就是一个下午的事情，在周末哄小孩午休后，就花了半天时间搞定了基本功能。

可能是做的太顺利，需求接踵而来。在接下来的一周多时间，我们增加了 Enum 定义、struct 定义、类方法定义、函数参数默认值、等等特性。

idl 的功能也不限于生成 C/C++ 的 .h 文件，还自动生成了 C 的 bindings 函数。其中，像 handle 这样的， bgfx 自己特别定义的特殊类型的转换部分是最麻烦的。

另一个麻烦的东西是代码注释。我们希望在 IDL 里维护接口文档，又希望在生成的代码上也能看到漂亮的 Doxygen 风格文本。Lua 原有的语法有点不够用。

经过几次修订，我最终定下的方案是，使用 Lua 的中括号风格的长字符串来书写文档。但又额外提供一个模块，在 Lua 文件被加载前，可以把源码中的三个减号开头的单行注释全部转换为长字符串。两种方案可以共存。如果不使用文档预处理模块，那么注释可以被自然忽略掉，使用的话，就把文档加入 IDL 的数据结构中，供代码生成器调用。

现在，IDL 语法看起来丰富多了。这里可以看到 bgfx api 的完整 IDL 描述。

最终的 IDL 变成了一个上千行代码的小型项目。它在这里 ，和 bgfx 使用一致的 License 。虽然这个项目是为 bgfx 深度定制的，但我认为核心模块可以被其它有 IDL 需求的大项目借鉴。

目前，bgfx 的接口文件已经完全由代码生成了。btw, bgfx 的作者还特别嘱咐我来提交相关内容的 PR ，再合并。他希望我的工作可以反应在最终 bgfx 的仓库里。

下一步，bgfx 会利用代码生成器生成一个动态库的封装，把所有 api 通过一个单一接口加载，并提供 api 调用的 log 功能。python 的 bindings 也会逐步从手工维护转移到利用 IDL 做代码生成。

bgfx 的作者也写了一篇关于它的 blog 。

Posted by 云风 at 03:14 PM | Permalink | Comments (3)