开发笔记(24) : Lua State 间的数据共享
by 云风
at 2012-07-30 10:32:24
original http://blog.codingnow.com/2012/07/dev_note_24.html
最近工作展开后， 我们一共有 10 名程序员在目前的项目上工作。我暂时没有和其他人有依赖关系的工作，最近一周在改进以前做的一些东西，在不修改接口的前提下，争取提供更高的性能，以及完成一些之前没完成的功能，为以后的扩展做准备。
最近值得一提的东西是：关于我们的共享储存的数据结构。
最早在设计的时候，是按多进程共享的需求来设计的。希望不同的进程可以利用共享内存来共享一组结构化数据。所以实现了这么一个东西 。这个东西实现的难点在于：一、共享内存不一定在不同进程间有相同的地址，所以不能在结构中用指针保持引用关系；二、不希望有太复杂的锁来保证并发读写的安全性。
后来，我们采用了 Erlang 做底层的框架。在同一台机器上，只有一个系统进程。所以，这个东西可以不必实现的这么复杂。我抽了三天实现，重新实现了一个。这次不考虑跨进程的问题，只在同一进程的不同线程中，让独立的 Lua State 可以访问同一份结构化数据。至于结构化数据支持到怎样的数据类型，我认为和 Lua 原有的 table 类型大致一致就可以了。
最后，就完成了这么一个东西。我认为到目前这个阶段，这个模块还是比较独立的，适合开源分享。以后的工作可能会和我们具体项目的模块整合在一起，还需要做一些修改，就不太适合公开了。有兴趣的同学可以在我的 github 上看到代码。https://github.com/cloudwu/lua-stable 。
<p>这个模块分了两个层次的 API 。其一是一组 raw api ，其实是直接对 C 函数的调用，而数据结构也是纯粹的 C 结构。这样，不用 Lua 接口也可以访问。而 Lua 封装层也仅仅只是做了浅封装。尤其是不生成任何的 userdata ，直接用 lightuserdata 保存的指针即可。当我们需要在多线程，多个 Lua State 间共享数据时，只需要在一个写线程上的 State 中把结构创建出来，然后将指针想办法传递到另一个读线程上的 State 中。就可以利用这组 raw api 访问读取指针引用的 C 结构数据。这个读写过程是线程安全的。</p>
我在实现这个 C 模块时，曾经想到过采用无锁算法。Atry 同学曾经留言问过，为什么我不实现一个无锁的 hash 表，比如 HAMT 。的确，我曾经考虑过，也花了整整一天实现纠结在实现细节上。为什么 Ctrie 在 Scala 上有不错的实现，但是没有一个好的 C/C++ 的版本？记得 2007 年的软件开发大会上，我听过 Andrei 演讲的 Lock-Free Data Structures 。C++ 实现无锁数据结构最繁琐的部分是什么？是在这么一个没有语言级的 GC 支持的语言中，那些临时副本如何正确的销毁的问题。这本是一个和数据结构实现无关的问题，但却用了最多精力去处理它。
简单说就是，当我们在修改数据结构中某个副本时，为了修改过程的原子性，我们需要复制一个副本出来，修改，然后利用 CAS 交换到主干上。这个过程中，其它读线程，可能引用老的版本，读完后就需要销毁掉过期的版本。在有 GC 机制的语言中这非常简单。但是在 C/C++ 这种手动管理内存的条件下，几乎变得不可能。对，我们可以用引用计数来管理。但难点在于引用记数本身需要放在对象上，那么改写引用值却需要获得对象本身先，这个变成了绕不过去的死结。在并发条件下，如果你不使用锁，那么获得对象指针后，到操作引用记数之间，无法确保对象不在那一刻被其它线程减少引用而销毁掉。
正确的做法是使用 Hazard pointer 。我记得那年我听 Andrei 用了两小时中几乎一半的时间讲解 Hazard pointer 的细节。要实现这个东西过于繁杂，代码量甚至超过原本要实现的数据结构的代码。所以最终我决定用一个简单的锁来保证正确的加减引用。
在提供了 raw api 后，我为了兼容之前的版本，提供了另一个更适合 Lua 程序员使用的版本。给这个 C 结构加上元信息让 Lua 可以识别。这样，在 Lua 里访问它可以更像一个 lua table ，且所有域必须事先严格定义出带类型的结构才允许使用。不至于在拼写错误的情况下不能立刻发现错误。也不会搞错每个字段的数据类型。
为了节省 Lua 中的内存，（在我前几个月实现的版本中，为每个对象而不是每类对象都绑定了独立的元表，将元信息绑定在元方法的 upvalue 中）我为每个类型生成了唯一的元表，绑定到 C 结构上。如果对效率敏感的话，可以考虑去掉这个元信息。既然有了元信息，还可以把字符串的键变换为数字键，提高 C 结构的访问效率。
最后，我给 array 形式的结构增加了显式的尺寸信息，让它用起来更舒服一些。
下一步，我想把前几天写的 原子字典 整合到上面来。有考虑过使用 STM 来实现这个东西，比如 David Xu 同学建议的 TinySTM 。还是有点担心引入太多的第三方库搞得过于复杂而放弃了。
另外，在 stable 模块中，我预留了 int64 的支持。在 64 位平台上，最高效的做法是使用 lightuserdata 来模拟 。因为这和平台相关，所以这部分的工作我就不放在开源版本里了。
btw, 在整合 int64 的过程中，发现 Lua 的 __eq 的元方法行为有点小怪异。对于 lightuserdata 是不触发这个元方法的，所以无法支持隐式的（number 到 lightuserdata）类型转换。
还有一小段代码值得介绍一下：
我们原本用来做线程间 RPC 调用的参数传递，依赖的是 Proto buffer 。但是，现在大量的数据交换是在同一台机器上。考虑到一个改进点是，直接把参数序列序列化到内存，变成一个指针传递到另一个线程，然后反序列化出来。这样会比 Proto Buffer 打包和解包略快一些，也不用定义额外的 proto 文件（但没有协议显式定义的过程未必全是好事）。
我实现了一个简单的 Lua 对象的序列化模块，可以把一个 Lua Value 序列化为一块二进制数据。因为它专门为 Lua 定制，所以会比通用的格式更高效一些。