云风的 BLOG

Lua 5.2 最重大的改进，莫过于 "yieldable pcall and metamethods" 。这需要克服一个难题：如何在 C 函数调用中，正确的 yield 回 resume 调用的位置。

resume 的发起总是通过一次 lua_resume 的调用，在 Lua 5.1 以前，yield 的调用必定结束于一次 lua_yield 调用，而调用它的 C 函数必须立刻返回。中间不能有任何 C 函数执行到中途的状态。这样，Lua VM 才能正常工作。

(C)lua_resume -> Lua functions -> coroutine.yield
   -> (C)lua_yield -> (C) return

在这个流程中，无论 Lua functions 有多少层，都被 lua state 中的 lua stack 管理。所以当最后 C return 返回到最初 resume 点 ，都不存在什么问题，可以让下一次 resume 正确继续。也就是说，在 yield 时，lua stack 上可以有没有执行完的 lua 函数，但不可以有没有执行完的 C 函数。

如果我们写了这么一个 C 扩展，在 C function 里回调了传入的一个 Lua 函数。情况就变得不一样了。

(C)lua_resume -> Lua function -> C function 
  -> (C) lua_call  -> Lua function 
  -> coroutine.yield -> (C)lua_yield 

C 通过 lua_call 调用的 Lua 函数中再调用 coroutine.yield 会导致在 yield 之后，再次 resume 时，不再可能从 lua_call 的下一行继续运行。lua 在遇到这种情况时，会抛出一个异常 "attempt to yield across metamethod/C-call boundary" 。

在 5.2 之前，有人试图解决这个问题，去掉 coroutine 的这些限制。比如 Coco 这个项目。它用操作系统的协程来解决这个问题 (例如，在 Windows 上使用 Fiber )。即给每个 lua coroutine 真的附在一个 C 协程上，独立一个 C 堆栈。

这样的方案开销较大，且依赖平台特性。到了 Lua 5.2 中，则换了一个更彻底的方案解决这个问题。

其实，需要解决的问题是在 C 和 Lua 的边界时，如果在 yield 之后，resume 如何继续运行 C 边界之后的 C 代码。

当只有一个 C 堆栈时，只能从调用深处跳出来（使用 longjmp），却无法回到那个位置（因为一旦跳出，堆栈就被破坏）。Lua 5.2 想了一个巧妙的方法来解决这个问题。

C 进入 Lua 的边界一共有四个 API ：lua_call , lua_pcall , lua_resume 和 lua_yield 。其中要解决的关键问题在于 call 一个 lua function 有两条返回路径。

lua function 的正常返回应该执行 lua_call 调用后面的 C 代码，而中途如果 yield 发生，回导致执行序回到前面 lua_resume 调用处的下一行 C 代码执行。对于后一种，在后续的某次 lua_resume 发生后，lua coroutine 结束，还需要回到 lua_call 之后完成后续的 C 执行逻辑。C 语言是不允许这样做的，因为当初的 C 堆栈已经不存在了。

Lua 5.2 提供了新的 API ：lua_callk 来解决这个问题。既然无法在 yield 之后，C 的执行序无法回到 lua_callk 的下一行代码，那么就让 C 语言使用者自己提供一个 Continuation 函数 k 来继续。

我们可以这样理解 k 这个参数：当 lua_callk 调用的 lua 函数中没有发生 yield 时，它会正常返回。一旦发生 yield ，调用者要明白，C 代码无法正常延续，而 lua vm 会在需要延续时调用 k 来完成后续工作。

k 会得到正确的 L 保持正确的 lua state 状态，看起来就好像用一个新的 C 执行序替代掉原来的 C 执行序一样。

典型的用法就是在一个 C 函数调用的最后使用 callk ：

  lua_callk(L, 0, LUA_MULTRET, 0, k);
  return k(L);

也就是把 callk 后面的执行逻辑放在一个独立 C 函数 k 中，分别在 callk 后调用它，或是传递给框架，让框架在 resume 后调用。

这里，lua 状态机的状态被正确保存在 L 中，而 C 函数堆栈会在 yield 后被破坏掉。如果我们需要在 k 中得到延续点前的 C 函数状态怎么办呢？lua 提供了 ctx 用于辅助记录 C 中的状态。

在 k 中，可以通过 lua_getctx 获得最近一次边界调用时传入的 k 。lua_getctx 返回两个参数，分别是 k 和当前所处的执行位置。是原始函数（没有被 yield 打断的），还是在被 yield 打断后的延续点函数中。这有一点点像 setjmp 或 fork 的接口设计。

其实在 Lua 5.2 的官方文档中，对以上已经做了详尽的说明。可以看 4.7 节 Handling Yields in C 。

或许，我们还可以参考这个接口设计，实现一个不需要独立堆栈的 C 版 Coroutine 库。只是用起来会很麻烦吧。

Posted by 云风 at 12:07 PM | Permalink | Comments (8)

最近三周按计划在做第一里程碑的发布工作，几乎所有新特性都冻结了。大家都在改 bug 和完善细节。

服务器的性能还有不小的问题，压力测试的结果不能满意。原本我希望可以轻松实现 40 人对 40 人的战场。现在看起来在目前台式机上还有困难，虽然换上高配置的服务器可以达到，但会增加不少成本。我们决定动手做一些优化。

固然过早优化的必要性不大，但早期发现的性能问题有可能是设计原因造成的。尽早发现设计中的错误，早点改正，比后期在低层次优化要省力的多。

我们采用的是大量进程（非 OS 进程，这里指 Erlang 进程）协作工作的模式。可以充分利用多核的优势，但却对内部通讯的数据交换产生的极大的压力。初步发现在多人对战时，90% 的内部通讯包是状态包的同步 。虽然我们的框架实现，会让单台机器上的 Erlang 进程间通讯，变成同一进程内的简单函数参数传递。但数据列集和内存复制还是会带来一些负荷。

目前还不太确定内部数据包传递的边际成本到底是否影响到整体性能，我打算从优化这一部分的设计和实现入手，确定问题所在。

状态同步，简单说就是一个玩家的 Agent 在做一个动作时，它需要把这个行为通知所有在虚拟场景中他附近的玩家。当很多人（超过 50 人）在一起时，就有大量的数据包需要广播出去。我们目前的做法是基于这样一个假设：服务器内部数据包的传递非常廉价。广播包比逐个发送更加廉价，这是因为，单机内部广播，可以避免大量的数据复制。所以，在同一张地图上，我们会简单的把任意一个 Agent 的状态改变信息广播给同张地图的所有其他人。这样就不需要动态维护分组信息。当每个 Agent 收到广播包后，再根据自身的逻辑进行过滤，再发给对应的客户端。

或许我们需要一个更为高效的广播方案，避免一些无谓的包复制。

我想实现这样一个数据结构：

有很多写入者，可以并发的向一个消息队列写入信息包。同时有很多读取者，可以并发的从这个队列读取这些信息包。

假设内存无限大，队列可以无限长。那么队列无需清除永远不会被读到的数据。写指针可以被共享，任何人写入都向前移动写指针（队列尾）即可。每个读取者各自维护一个读指针（队列头），可以并发读取，互不影响。

此数据结构可以被简单的实现，并做到无锁的并发安全。

我是这样实现的：

用两块连续内存，一个保存索引 INDEX_QUEUE，一个保存信息包的实际数据 DATA_QUEUE。

对于进入队列，大概是这样的流程:

  1. OFFSET = SYNC_FETCH_AND_ADD(DATA_QUEUE.TAIL , SIZE)
  2. WRITE_DATA(DATA_QUEUE , OFFSET, DATA , SIZE)
  3. INDEX = SYNC_FETCH_AND_ADD(INDEX_QUEUE.WTAIL, 1)
  4. INDEX_QUEUE[INDEX] = OFFSET
  5. WHILE NOT SYNC_COMPARE_AND_SWAP(INDEX_QUEUE.RTAIL , INDEX, INDEX+1)

下面解释一下：

第一步，我们增加数据队列的尾指针，空出足够的空间。第二步将数据写入准备好的内存中。第一步的原子性保证了第二步的数据准备工作可以并行进行。

在读队列中的数据时，我们依据的是索引队列的指针位置，而不是数据队列。这样，不会读到没有准备好的数据。

索引队列有两个尾指针，以保证第四步的安全写入。

第三步，原子递增索引队列的 WTAIL ，分配出一个索引空间，供第四步原子写入索引。

第五步，将 RTAIL 递增。注意这里，不能简单的加一。而是要在 WTAIL 的原有值的基础上加一。这是因为，要避免执行第四步时同时读队列。而且我们必须保证第四五步并发时，较小的 INDEX 值先被加一推进 RTAIL 。

读队列的流程简单的多，每个线程独立维护各自的队列头指针，所以不再需要原子操作，每次仅需要从队列头读到 RTAIL 处即可。

由于队列内存不可能无限大，所以我们需要实现成循环队列，在内存块满的时候，回转一下。这会使实际的实现代码比上面的伪代码更复杂一些。不过还是可以实现成无锁的数据结构。

在我们的实际应用中，队列维护者不需要了解所有的读取者。每个队列的订阅者，在订阅的那一刻，重置读指针到队列尾。然后以一定的频率（目前是 0.1s），每次都处理完队列里的所有数据。而队列按照估计值，大约可以保存至少 1 秒甚至更多的数据包（大约有 3 万个数据包的余量，即使有上千人拥挤在同一个地图上，也需要花上远大于 0.1 秒的很长时间才会填满）。

这样，每个 Agent 需要向地图广播数据的时候，只需要把数据压入地图广播消息队列。然后定期从广播消息队列读取这个心跳的所有广播包就可以了。它甚至不需要从队列中复制出广播包来做过滤和转发处理，而用指针指向队列上的数据区直接处理就够了。

我只花了半天时间，200 多行 C + Lua 封装代码就实现了这个数据结构。但是多线程程序果然到处都是坑，又花了一天时间才解决掉其中的并行问题的 bug 。

我们成功的把内部通讯包降低到原有的 10% 。整体性能有所提升（大约 10% 到 20%），没有我预想的效果那么明显。接下来还需要更多的统计信息，找到下一个热点。

Posted by 云风 at 03:22 PM | Permalink | Comments (47)

物品交易和掉落系统不是一期里程碑的内容，手头事情不多，就还是先做设计了。

物品掉落和交易，本质上是一件事情。区别在于玩家之间的物品交换于玩家和系统之间的物品交换。这部分的设计，我在去年初曾经写过一篇 blog 总结过。

这次重新设计实现，做了少量的改动。主要是一些简化。设计原则是，交易服务器独立，简洁，健壮，容易回溯交易历史做数据恢复和分析。

交易服务，我认为是一个后备系统。在数据不出问题时，不大用理会它的存在。它仅仅是用来保证物品不被复制，确定每件物品可以有唯一的所有人。在出现争议的时候，可以作为仲裁机构。

在游戏服务中，玩家或其他实体储存的物品，同样会保存在玩家数据中，利用共享内存读写 。 每件物品记录在对应的包裹格类，直接记录物品名称或指代名称的 id 。即，同样的物品用同样的标识。之外，再额外记录一个(或若干个)物品唯一 id (用 64bit 或 128bit ) 。这样做，避免在访问物品的功能时，额外去查一张表。

交易认证服务，其实只关心一件事情。即，某个物品 id 归属于谁。它不关心物品 id 代表的是什么含义。当然，可以有另一个数据库记录这个关系。在物品的所有者改变时，交易服务来保证其原子性。除了玩家间的转换，还有大量的和系统间的交换。掉落物品其实是从系统改为玩家所有，而玩家销毁物品则是把所有者改为系统所有。

我把交易系统所操作对象分为三类，Entity 表示所有者，Goods 表示物品，Currency 表示货币。货币是唯一不用唯一 ID 来记录的，它只记录数量。游戏中可能有多种不同的货币，所以需要额外记录一个货币的类型。

每笔交易都是由若干交易品构成的，每件交易品是 GoodsID 或 CurrenyType + CurrenyAmount ，为了让系统可以检查出交易品的合法性，我们需要同时绑定物品所有人，或物品所有人名下的货币总量。大体上，每次交易，对于一个交易方需要提供的信息是：

EntityID (所有人标识) Balances (所有人货币账户余额) { GoodsID (物品标识) | Currency (支出货币金额) }

展示我只打算支持两方交易，所以单条交易请求，只需要提供两个交易方的支出就可以完成交换了。

交易系统会校对双方的账户余额是否正确，交易交易品的所有人是否正确。如果有一项不正确，则取消交易，并返回错误的交易品是什么（或是正确的账户余额）。

其它协议大体上没有改变，和以前写的那篇类似。只是我增加了创建 Entity 时可以初始化账号余额的参数，用起来更方便一点。初始化物品也可以设置所有者，而不是默认给系统所有，进行一次交易才能赋予玩家。

系统不会只有一个 ID ，在掉落系统中，每张地图每个副本都有独立的 EntityID 。我们会在副本开始初始化好左右的可掉落物品（对于开放地图，会略微复杂一点，由某种和时间以及玩家数量有关的量来定期初始化）。货币也是定额配给在地图的 Entity 账户里的。和玩家账户不同，系统账户允许为负值，但是当系统账户为负时，会提醒维护人员。这样，我们比较好控制副本的货币产出。

销毁物品会把物品所有者更改为一个回收站名下，而不会从数据库中删除。但在实现上，或做一些特别优化，把这部分冷数据（正常逻辑不再访问的到的数据）移动到分离的数据库中。

这个系统接口简洁，需求单一，需要考虑的是在海量数据时足够稳定高效。所以对热数据（在线玩家的物品）需要做一些 cache 优化。对于每件物品都有一个唯一 ID ，可以预想到整个游戏世界中的对象可以轻易超过 10 亿这个数量级。因为日后还有合并服务器的需求，务必要保证所有服务器间也不可以有重复 id 的物品。这个数量非常之大，在实现时要从多方面考虑性能优化问题。

数据库的选择上，我认为是一个比较次要的问题。交给最终实现的人来选就好了。其实需要维护的数据仅仅是物品ID 到所有人 ID 的映射关系，使用 SQL 数据库也好，NoSQL 数据库也好，都没有特别的必要性。晓靖同学自告奋勇想做这套系统，他决定使用 Redis 来做数据储存，我觉得没有太大问题。

在数据容灾问题上，我们打算把交易请求通过独立服务来逐条记录 log 。保证使用 log 就可以完全恢复出数据库中的数据来。靠加强 Log 系统来保证数据不易损坏。

Posted by 云风 at 03:39 PM | Permalink | Comments (31)

我们原来订的计划是在 6 月中旬结束第一个历程碑。完成游戏最基本的内容，场景漫游，战斗，NPC 管理，登陆认证等等。

和以前我自己带的项目不同，这次由 dingdang 做产品制作人，安排了专人做项目管理。我们的计划定的很早，也还算按部就班的在做了。

这次我们或许选了一条不太好走的路，一切都是从零开始，作品的要求也竖的较高。过去半年（从 2011 年 11 月开始正式制作，2012 月 3 月开发团队组建完毕），各个不同的部分分头开发，希望在第一个里程碑能做一个较为完整的整合了。

为了让里程碑可以顺利完成，程序初步整合放在了 6 月 1 日，这样可以有 2-3 周的充裕时间，冻结新特性，专心修改细节和 bug 。

在离 6 月 1 日还有一周的时间，我们才发行了第一个内部版本，非常简陋不堪。最后提前 2 天决定开始加班。很长时间没有通宵过的我们开始试着通宵一次了。算是大家一个默契。

那天整整忙了一晚上，在用自己制作的美术资源替换掉别的游戏中截取出来的模型和动画数据时，出了许多问题。服务器那边许多新模块也是草草上马的。因为是多个人开发，分别的模块细节都没有理解清楚，整合时也出了一些纰漏。一直到 6 月 1 日的照阳升起的时候，大家还忙个不休。

一个晚上似乎都在不停的吃东西，早上又一起奔去华师门口的小店吃热干面。我们大声的说话讨论，让自己不至于困的倒下。

虽然不是一个对外的版本，但依然还是希望可以按时间完成。这样整个团队的士气能得到鼓舞。这可能是通宵加班最大的价值。等到 1 号下午的时候，我们交付了一个基本可用的版本。在全公司演示。第一次看到的同事表示一周时间能做如此大的改进相当的满意。我很希望可以公开当时我们的视频，但是市场有关的行为还是留给市场部门的同事来决策吧。只好放在我的手机中了。

当然，通宵毕竟是伤身体的事儿，以后就不轻易做了。这次我缓了两三天才回过劲来。凭心而论，如果能好好休息，总的工作时间甚至能更短一些，只是会晚于计划交付罢了。有些应急的补丁可能也会不那么急者打上，而去寻求更完备的方案。

接下来一段时间肯定不会通宵了。不过会加班两三周。其实我觉得也没那么多事情，也就是个态度吧。

最近两天开始筹备下一个里程碑的技术点了。过几天再续写开发笔记。

Posted by 云风 at 11:54 PM | Permalink | Comments (8)

在做策划表格解析的时候，我们希望可以在表格里直接填写一些脚本代码。我们的脚本语言使用的 Lua ，所以，直接填写 Lua 代码最为简单。但是，策划同学强烈需要在脚本中直接使用中文。而 Lua 原生并不支持使用中文作为变量名。一开始我们使用了一些变通的方案：比如建立一个字典，把中文词通过程序替换成相应的拼音。倒也能工作。

昨天在午饭途中的电梯里，我想到了另一个方案，用了一个下午实现出来验证可用。

修改 Lua 的语法解析代码，让其支持汉字并非难事。但我不太想通过给 Lua 打补丁，修改 Lua 语言的方式来做这件事情。即，我不想因为这个项目为 Lua 创造一门方言。但是，我们却可以把策划表格中填写的代码当成一种 DSL ，正如之前我实现的公式解析 那样。把这部分用 Lua 的方言来实现，把修改的影响减少到最小，而不蔓延到整个系统的实现语言中去，或许是个更好的方法。

因为 Lua 是否支持中文变量名，只是一个语法解析层面的问题。到了虚拟机解析 bytecode 层面就不存在了。即，我们修改 Lua 的实现，让它支持中文变量名，它解析源代码生成的 bytecode ，是完全可以直接在未修改过的 Lua 环境中运行的，甚至连调试信息都完全兼容。

我们可以在系统的 Lua 环境中以 Lua 库的形式再嵌入一个修改过的 Lua 解析器，用这个支持汉字变量名的解析器来解析从策划表格中读出来的脚本，生成 bytecode ，然后再在母体中运行它们。正好之前制作了一个多 State 的 共享数据库 用来储存表格数据，完全可以在初始化数据库时使用修改版的 Lua 解析器。

在未修改的 Lua 环境中嵌入另一个版本修改过的 Lua 虚拟机在链接设置上需要特别小心。因为这是两个版本的 Lua 却有相同的 API 。我的做法是先定义一组 C 接口，仅用来编译 Lua 代码：

struct code_state * code_open(void *buffer, size_t sz);
const char * code_load(struct code_state *L, const char * source, size_t *dump_sz);
void code_close(struct code_state *);

这里，struct code_state 其实就是 lua_State 但换个名字以示区分。我在定义接口时，考虑到希望更好的控制内存，在初始化的时候，由外部传入解析中需要用到的内存块。利用 lua 可直接定制 Alloc 的特性(实现一个简单的 bump allocator)，让这个独立的 Lua 虚拟机资源使用高效可控。

我把这组 API 实现在一个独立的动态库中，静态链接修改过的 Lua lib ，并不导出任何 Lua 相关的 api 。这样就和母体的 Lua 环境绝缘了。

第二步，实现一个标准的 Lua 扩展库，动态链接前面这组 C 接口，就可以方便的在母体的 Lua 环境中加载支持汉字变量名的 Lua 代码。

如何修改 Lua 源代码支持汉字变量名呢？

Lua 的源代码结构非常清晰，做到这一点相当简单。以 Lua 5.2 为例，语法解析代码在 llex.c 中，但阅读一下就可以发现我们并不需要修改这个文件。Lua 是通过自己定义的 lislalpha lislalnum 两个函数来判断变量名的。

这两个函数定义在 lctype.h 中，我们只需要修改这个文件即可。

下面，我希望让 Lua 认为 UTF-8 中汉字字符也通过 lislalpha 的检查。关于 UTF-8 汉字的编码规则，可以参考之前我写过的一篇 blog 。虽然不太严谨，我直接把 0x80-0xbf 0xe0-0xef 段的字符全部认为是汉字。

根据配置，Lua 定义了两个版本的 lislalpha 。当系统使用标准 ASCII 字符集时，Lua 使用自己优化过的查表版本；否则则调用系统的 isalpha 函数。对于后者，Lua 还检查了下划线，我们只需要追加汉字集的检测即可。

对于前一种情况，可以修改 lctype.c 中 Lua 自己的查表实现，也就是一张表。

在这张表里，Lua 定义了单个字节每个编码的属性，用位域表示的。支持判断一个字符是否是 ALPHA ，是否为数字，或是 16 进制数字，是否可以打印（这在 Lua 标准库中输出字符串有用到）等等。

我们只需要修改这张表就可以了。把第 8 到 B 行，以及 E 行全部修改为 0x01 或是 0x05 （0x05 可以让 Lua 认为汉字是可打印的）。

Posted by 云风 at 11:38 AM | Permalink | Comments (10)