« June 2012 | Main | August 2012 »

July 29, 2012

开发笔记(24) : Lua State 间的数据共享

最近工作展开后, 我们一共有 10 名程序员在目前的项目上工作。我暂时没有和其他人有依赖关系的工作,最近一周在改进以前做的一些东西,在不修改接口的前提下,争取提供更高的性能,以及完成一些之前没完成的功能,为以后的扩展做准备。

最近值得一提的东西是:关于我们的共享储存的数据结构。

最早在设计的时候,是按多进程共享的需求来设计的。希望不同的进程可以利用共享内存来共享一组结构化数据。所以实现了这么一个东西 。这个东西实现的难点在于:一、共享内存不一定在不同进程间有相同的地址,所以不能在结构中用指针保持引用关系;二、不希望有太复杂的锁来保证并发读写的安全性。

后来,我们采用了 Erlang 做底层的框架。在同一台机器上,只有一个系统进程。所以,这个东西可以不必实现的这么复杂。我抽了三天实现,重新实现了一个。这次不考虑跨进程的问题,只在同一进程的不同线程中,让独立的 Lua State 可以访问同一份结构化数据。至于结构化数据支持到怎样的数据类型,我认为和 Lua 原有的 table 类型大致一致就可以了。

最后,就完成了这么一个东西。我认为到目前这个阶段,这个模块还是比较独立的,适合开源分享。以后的工作可能会和我们具体项目的模块整合在一起,还需要做一些修改,就不太适合公开了。有兴趣的同学可以在我的 github 上看到代码。https://github.com/cloudwu/lua-stable

这个模块分了两个层次的 API 。其一是一组 raw api ,其实是直接对 C 函数的调用,而数据结构也是纯粹的 C 结构。这样,不用 Lua 接口也可以访问。而 Lua 封装层也仅仅只是做了浅封装。尤其是不生成任何的 userdata ,直接用 lightuserdata 保存的指针即可。当我们需要在多线程,多个 Lua State 间共享数据时,只需要在一个写线程上的 State 中把结构创建出来,然后将指针想办法传递到另一个读线程上的 State 中。就可以利用这组 raw api 访问读取指针引用的 C 结构数据。这个读写过程是线程安全的。

我在实现这个 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 定制,所以会比通用的格式更高效一些。

我把它开源了。https://github.com/cloudwu/lua-serialize

July 23, 2012

C 的 coroutine 库

今天实现了一个 C 用的 coroutine 库.

我相信这个东西已经被无数 C 程序员实现过了, 但是通过 google 找了许多, 或是接口不让我满意, 或是过于重量.

在 Windows 下, 我们可以通过 fiber 来实现 coroutine , 在 posix 下, 有更简单的选择就是 setcontext

我的需求是这样的:

首先我需要一个 asymmetric coroutine 。如果你用过 lua 的 coroutine 就明白我指的是什么。

其次,我不希望使用 coroutine 的人太考虑 stack 大小的问题。就是说,用户在 coroutine 内可以使用的 C stack 大小和主线程一样多。

我需要单个 coroutine 空间占有率不要太高,因为我可能会使用上千个 coroutine ,我不希望每个都占用百万字节的堆栈。

因为,在我的应用场合,coroutine 切换的那一刻,使用的堆栈并不多(它可能调用一些需要大量堆栈的库函数,但那些库函数中并不会发生切换),所以,在切换的时刻做栈拷贝是可以接受的。coroutine 切换并不算频繁,这个切换成本是可控的。

最终,我以我的需求实现了我需要的这个版本。

当然,暂时它不支持 windows 。其实 port 到 windows 平台不算困难,只需要把 setcontext 那组 api 改成 fiber 的即可。

July 19, 2012

开发笔记(23) : 原子字典

问题是早就提出了的。在 开发笔记 18 中,就写到一个需求:一个玩家数据的写入者,可以批量修改他的属性。但是,同时可能有其他线程在读这个玩家的数据(通过共享内存)。这可能造成,读方得到了不完整的数据。

我们可以不在乎读方得到某个时间的旧数据,但不可以读到一份不完整的版本。就是说,对玩家数据的修改,需要成组的修改,每组修改必须是原子的。

起先,我想用读写锁来解决这个问题。方案想好了,一直没有实现。只是把读写锁的基本功能实现了。

这几天这个问题被重提出来。因为,前段我们都采用了鸵鸟政策,当问题不存在(事实上我们也没有发现实际中出现可观测到的问题)。

反正探讨了好几个解决方案,一开始都是围绕怎么加锁,锁的粒度有多大来展开的。甚至,我们把其中的一种方案都实现出来了,并写了压力测试程序测试。不过,这些方案都不太令人满意。大家担心锁的开销,以及逻辑代码编写者所需求关心的问题太多,导致有死锁的可能性。

昨天差一点决定用一个地图锁来解决这个问题,就是用牺牲同一个地图进程上,玩家间并行的可能性为代价的。这个方案也不无不可。但昨晚躺在床上一直睡不安稳。因为这样做,就失去了一开始我期望用并行方案来设计游戏服务器的初衷。如果这样,还不如全部退化到单地图单进程来编写程序。那么一定有方法是可以避开锁以及避免让写逻辑的程序员去关心数据共享的读写冲突问题的。


今天,我实现了一个数据结构,暂时命名为原子字典。

这个模块用 C 编写,在 Lua 中使用。从 Lua 中看起来和 Lua 的 table 无异。只是多了写限制,比如 key 只能是 string 。value 只能是 number 和 string 。没有层次结构。 当然这些限制只是为了简化实现而已,并不被算法限制。

我们可以把一组相关数据放在一个原子字典中。原子字典可以被同进程,不同线程的 Lua State 共享(稍微改进,也可以利用共享内存跨进程)。自己的 Lua State 读写这个字典,感觉不到任何差异。

我提供了一个 barrier 函数,由应用程序间隙调用。对于我们的系统,是由单一源的数据包驱动的,所以只需要在数据包处理函数处写上 barrier 的调用即可。

当前 Lua State 对字典内容的修改,只在调用了 barrier 之后,才对其它线程上的 Lua State 可见。所以,你永远看不到别的 Lua State 对字典内容的修改过程,而看到的是一个个快照。


我是这样实现的:

估算出系统物理线程的上限(我们的系统中,是严格小于等于系统的核数的)。我给每个字典对象都预先开辟了 N 个副本空间(N 大于最大线程数)。

字典有一个引用,标识了当前的最新版本的副本。

任何人读写字典,都引用最新版本,且把这个版本引用计数加一。这个引用是直读的。同时,把字典的引用计入当前 Lua State 的 Barrier 控制器上。

当你想改写字典,先检查从上次 Barrier 调用以来,是否曾经修改过。如果是第一次修改,在对象的预留副本池中找到一个空闲空间,引用加一,并把原始的只读副本复制过去,接着再修改。

每次 Barrier 调用时,遍历所有记录在案的读写过的字典对象。如果是经过改写的,就把它更新为最新版本(同时做一些整理工作,主要是针对字符串类型的处理。这里字符串值类型,我是放在预分配的字符串池中的);否则,直接减掉引用。这个方案不解决并发写问题。如果有两个以上并发写,只有一个会生效,另一个版本则丢弃掉。这是我们框架的一个约定。我们同时只允许一个写入者。当然,如果有必要,理论上也可以做一些回滚重写的过程。


差不多一个玩家身上的属性组大约在 100 这个数量级。大部分是数字(float)。所以每次改写,需要有额外 0.5K 左右的数据拷贝。每个玩家的处理逻辑中,一秒大约发生十个左右会有数据写操作,所以我认为这个代价(为每个玩家每秒多 5K 的数据拷贝)是可以接受的。

为了测试我的模块的正确性。我构造了一个有 30 个线程的多线程程序,每个持有一个原子字典对象。这个字典对象中放有 A B C D 四个字段。循环 10000 次,每次更新它的四个字段,前三个取随机数,第四个用 100 减去前三个的总和。

同时,每个线程在每个循环周期内,检查其它 29 个线程的对象,检验这些对象内四个字段的和是否为 100 。


很高兴我能花一天实现完成了这个模块,大约有 800 行 C 代码,200 行测试代码。虽然一开始有点小 bug ,没能通过我自己写的测试。但花了一点时间就修正了。

开源版本: https://github.com/cloudwu/atomdict

July 13, 2012

开发笔记(22) : 背包系统

我们项目的第一个里程碑杯已经比较顺利的完成了。主要是完成最基本的用户注册登陆,场景漫游,走跑跳,远程进程法术等技能攻击,怪物及 npc 的简单行为,等等。尝试了几十个玩家与上百个 npc 的混战,还比较流畅。

中间小作休整,然后开始做第二里程碑的计划安排。这次预计要三个月,完成几乎所有的 MMO 必须的游戏功能了。

其中一个大的任务就是要完成背包、物品、装备、货币、掉落、交易这些相互关联的模块。

下面简单记录一下背包系统的设计实现思路:

我们希望可以追踪每件可能被交易的物品,每件物品都有 64bit 的唯一 id 。在背包格里可以叠加若干件相同物品,但是每件物品都有单独 id 。这个 id 是用于最终和拥有者校验用的,不必传输给客户端,在交易系统外也不需要被读取。

最终,定了三个概念:背包( BAG )、仓库( STORAGE )和物品( ITEM )。

物品包括了装备,但不包括货币(只追踪数量不记录每个单位的 id 的东西,可以放在背包里,也可以独立列出)和任务物品。这里任务物品可能被放在背包中,并可以移动位置。但不可以被交易,不用记录物品 id ,它其实是一种任务进度指示器。

仓库保存了玩家所有拥有的物品,每个玩家只有一个仓库,仓库里每个格子只能存放一件物品,不可以叠加。只可以向仓库添加或删除物品,不可以交换位置,也不可以指定格子存放。实际上,仓库只是用来辅助物品追踪,确定物品所有权用的。

背包是玩家所有,存放所有物品以及任务物品和货币的容器。一个玩家可以拥有多个背包,装备栏、银行仓库等都是用背包来实现的。背包格里可以叠加存放多个相同物品,也可以用来存放货币或任务物品。

物品是以 lua 对象的形式保存在内存中的,不同类别的物品有不同的方法可以获得物品的不同属性。我想以一个类别名加一组构造参数的方式来持久化物品对象。

比如大多数游戏内的物品只需要用“物品”和“名字”来唯一确定一种东西。“物品”是它的类别名,它只需要有一个构造参数就是“名字”。具体的物品等级、交易价格、详细介绍等等,都是通过这个名字可从策划填写的表格中检索出来。当然这里也可以不是用“名字”,而是“类别 id ”。从这个 id 进一步检索出物品名也可以。

装备更复杂一些,光有一个名字还不能构造出来。它可能还有随机附加属性等参数。这里有一个小技巧,可以只在构造参数里记录一个随机种子,在构造过程中,利用这个种子构造出多个随机量。

还有更复杂的特有装备,比如玩家制造的装备,需要记录下装备制造者的名字。或是有用宝石强化过的装备,需要记录强化信息。

大原则就是,用类别和绑顶在类别上的参数,可以唯一表达出这个东西是什么。类别用字符串表示,对应相应的对象构造脚本。

装备对象至少要提供一个方法,可以把内存中的对象再次序列化为类型名于一组构造参数。

清楚的定义出装备的概念,以及表达方法后,我们就把装备模块和背包以及交易模块分离了。

背包系统直接用先前开发的共享储存系统 映射出来。但在实现时,还额外为每个物品格附加一个域存放物品对象。在每次加载后,都利用物品类别名和构造参数构造出物品对象来。运行过程中,都是用这个对象来完成物品相关的操作。

每个背包格里都只能有一个物品对象,但可以引用多个仓库格,以示叠加。交换两个背包格不会影响仓库的内容,只是索引交换一下。但是,如果背包格里的对象不存在于仓库中时(可能是任务物品,也可以是某种特殊货币),就需要在移动物品时,重新在目标格序列化物品对象。

我们并没有专门去做玩家数据存盘过程。所以一直保持所有需要存盘的内容都放在共享储存系统里是很重要的。只要有需要,随时都可以从另一个进程来读取并持久化它们。至于在边界情况下可能造成的物品复制问题,则由交易系统去保证。

背包有几个基本操作:

  • QUERY:查询一个物品格里的物品对象和数量。
  • TRADEOUT :把一个物品格里的所有物品都拿出来。生成一个交易单。这个 API 主要是把物品从背包里抹掉,如果物品格对仓库有引用,也同时抹掉。返回的交易单是一组纯数据,里面有物品的序列化信息,以及所有的物品唯一 id 。
  • TRADEIN :把一个交易单里提到的所有物品,合并到一个物品格里。这个是 TRADEOUT 的逆操作。
  • EXCHANGE :交换两个物品格。
  • SPLIT :把一个物品格内的多件物品分割成两份,放在新的格子中。
  • CONSUME :消耗掉一个物品格中的若干件物品。

这里提到一个新概念,就是交易单。交易单上记录了一批物品,是物品的序列化信息,以及这些物品的 id (如果有 id)。这个交易单可以很容易被跨进程传输到交易或掉落系统里去处理。交易系统和调用分配系统都会使用这个数据结构做数据交换。

July 11, 2012

Lua 5.2.1 的一处改变

Lua 5.2.1 正式发布有段时间了。虽然相对于 5.2.0 只是一个小版本的提升,但也是有些东西可以拿出来讲讲的。

比如,在这次小版本更新中,字符串类型被分为了长字符串和短字符串两类。长字符串(大于 40 字节的字符串),不再做内部化处理了。

一开始我以为这是为了性能的一处小改进,可以在字符串处理比较多的场合,少做一些 hash 计算和 hash 表插入。后来查了一下邮件列表发现,其实是为了安全性,防止别人做 hash dos 攻击。一起改变的是字符串的 hash 过程使用了一个随机种子。默认设定和时间有关。值得注意的是,这处改变可能会使得嵌入 lua 的程序每次运行的内存状态不一致,有可能给调试带来一定的麻烦。

今天的源码阅读收获,我已经记录在我那本想慢慢完成的书,《Lua 源码欣赏》中了。以前写过两章中断了。这几天新写的两章在这里 。因为想在最后再综合整理,所以就独立输出 pdf 了。

July 09, 2012

在 C 中设置 Lua 回调函数引起的一处 bug

我们的服务器框架提供了一个 C 接口, 在 RPC 调用时, 回调一个事先注册的函数.

C 中标准的回调函数的接口设计, 标准方法是设置一个 C 函数指针加一个 void * 类型的数据指针.

由于我们的游戏逻辑使用 Lua 来实现, 所以这里只需要实现一个 C 函数去调 Lua 机里的函数, 而对应的 void * 自然就是 lua_State *

今天,同事在实现服务的热更新功能。发现多次热更新 lua 写的服务会导致一处 core dump ,一直没有找到原因。通过阅读代码,我仔细思考后,确定了 bug 所在。

我们的热更新是通过重新初始化 lua 中的各种状态,且重置 skynet 框架的 callback 函数实现的。

热更新并不会重新打开一个新的 lua state 而是在原有的 state 中进行的,这样才能继承一些不需要更新的数据和状态。

热更新的触发也是通过响应一个 RPC 调用来触发的。准确的说,是在前一次注册的 callback 函数中进行的。

问题在于,触发热更新机制是由一个 lua rpc 函数启动。而每个 lua rpc 调用都被包装成了一个独立的 coroutine 。

lua 的 coroutine 在 lua 的术语中被称为 thread 。每个 thread 都有一个独立的 lua state 。所以,重置 skynet 的 callback 函数时,C 上下文中的 state L 是一个 thread 的 L ,而不是 lua 创建时 main thread 的 L 。

当代码热更新几次后,先前的那些临时的 rpc 调用的 thread 被垃圾回收。L 指针变得无效了。而在当初设置 skynet 的 callback 函数时却传入了它。这导致了 callback 函数工作时,访问了一个已经被释放的 L 指针。

正确的方法是,当你在 C 里想保存 L 供以后 callback 函数使用时,不要轻易使用当前上下文的 L 。因为调用你的 C 函数的 lua 函数,不一定是在主线程中。lua 5.2 获取主线程的方法是:

  lua_rawgeti(L,  LUA_REGISTRYINDEX, LUA_RIDX_MAINTHREAD);
  lua_State *mL = lua_tothread(L,-1);
  lua_pop(L,1);