云风的 BLOG

lua 5.2 正式发布了，对于 lua 语言本身的修改，重中之重就是对 environment 这个概念的修改。

可以说， 5.1 以前的 environment 已经没有了。environment 对于制造一个安全的沙盒（或是实现 DSL）是一个很重要的语言特性，我以前很喜欢使用，但也很容易用错。这次的修改我认为是一个谨慎的决定，并使得 lua 语言更为精简和严谨了。

我这样理解 5.2 中的 environment 。本质上，lua 取消了原有意义上的 environment 。所以我们可以看到 C Function 不再有环境了。function 、在 lua 中称为 closure ，仅仅只是函数体和 upvalue 的联合体。这简化了 lua 语言本身。全局变量实际上只是一个语法糖，编译时再前面加上了 _ENV. 的前缀。这样，从 load 开始，第一个 chunk 就被加上了 _ENV 这个 upvalue ，然后依次传递下去。

这个设计基本可以取代以前使用 getfenv/setfenv 改变函数环境的方法。但是又不完全等价。总体来说，增加了一些限制，但不太容易写出 bug 的代码了。

比如说，现在想给返回一个独立环境的函数，可以这样写：

function foobar(env)
    local _ENV = env
    return function() ... end
end

而以前大约是这样：

function foobar(env)
    return setfenv(function() ...  end, env)
end

这不太看得出好坏，但是如果是一组函数，就有区别了。5.2 中是这样:

function foobar(env)
    local _ENV = env
    local ret = {}
    function ret.foo()
        ...     
    end
    function ret.bar()
        ...
    end
    return ret
end

5.1 的等价代码大约是这样：

function foobar(env)
    local old = getfenv()
    setfenv(1,env)
    local ret = {}
    function ret.foo()
        ...     
    end
    function ret.bar()
        ...
    end
    setfenv(1,old)
    return ret
end

或者这样更函数式一点：

function foobar(env)
    return setfenv(
    function()
        local ret = {}
        function ret.foo()
            ...     
        end
        function ret.bar()
            ...
        end
        return ret
    end , env) ()
end

getfenv/setfenv 更灵活，却更容易出错。

对于制作沙盒来说，我感觉 lua 5.2 会更为鼓励使用 load 这种运行时的编译行为。即一定程度上的鼓励元编程。（因为取消了 setfenv ，所以给了 load 显式的参数来制定给 chunk 一个新的环境）

btw, 这个语言设计变更的同时也增强了函数式编程的性能。因为 lua 现在可以更方便的合并那些有相同 upvalue 的 closure 了。（从前除了 upvalue 还有 environment ，合并行为更为复杂）

12 月 30 日补充:

如果非要类似 setfenv 的功能, 修改一组函数的 _ENV 大概需要这样做了:

function getfuncs()
  local _ENV = _ENV
  local ret = {}
  function ret.foo()
    ...
  end
  function ret.setfenv(env)
    _ENV = env
  end
  return ret 
end

Posted by 云风 at 12:34 AM | Permalink | Comments (16)

今天吃晚饭的时候想到，我需要一个定制的内存分配器。主要是为了解决 共享内存 中的字符串池的管理。

这个内存分配器需要是非入侵式的，即不在要分配的内存块中写 cookie 。

而我的需求中，需要被管理的内存块都是很规则的，成 2 的整数次幂的长度。buddy memory allocation 刚好适用。

算法很简单，就是每次把一个正内存块对半切分，一直切到需要的大小分配出去。回收的时候，如果跟它配对的块也是未被使用的，就合并成一个大的块。标准算法下，分配和释放的时间复杂度都是 O(log N) ，N 不会特别大。算法的优点是碎片率很小。而且很容易做成非入侵式的，不用在被管理的内存上保存 cookie 。只需要额外开辟一个二叉树记录内存使用状态即可。

我吃完饭简单 google 了一下，没有立刻找到满足我要求的现成代码。心里估算了一下，C 代码量应该在 200 行以下，我大概可以在 1 小时内写完。所以就毫不犹豫的实现了一份。

然后，自然是开源了。有兴趣的同学可以去 github 拿一份。这样就省得到再需要时再造轮子了。嘿嘿。

btw, 当然这块代码有许多值得优化的地方，比如可以把里面的递归优化成循环回溯。这个算法我读初中时经常写。因为初一那个时候参加信息学奥赛时用的 basic 不支持局部变量，全部变量都是全局的，很难实现递归。所以早期我都不用递归遍历二叉树的，感觉写起来好麻烦。

不过循环回溯遍历树应该是比递归快不少的，因为减少了许多不必要的环境变量压栈，对不支持 closure 的 C 语言尤其是。

这个库用起来很简单。它并不实际管理内存（它不侵入被管理的内存）。你可以设想你另外有一大块内存是由许多最小单位块合起来的。你可以假设最小单位是 1K 。那么用 buddy_new(10) 就可以帮你管理 1024K 内存。

buddy_alloc 可以请求若干个最小单位块，返回一个序号。然后用户可以自己去大内存上索引出来用。用完调用 buddy_free 归还即可。

为了调试方便，我还提供了 buddy_dump 打印二叉树的细节，可以直观的看出那些内存区域未被使用，哪些已经被占用。

ps. 果然，写这篇 blog 花掉的时间比完成这些代码时间更长。代码也如我所料的没有超过 200 行。看看，把东西描述清楚就是比实现一个东西要花更长的时间，这就是项目人多反而做的慢的原因之一吧。

12 月 21 日:

感觉用了递归很不爽, 所以重写了实现, 改用完全二叉树储存, 去掉了递归. 并且(也是主要原因) 减少了内存占用.

如果需要优化的话, 应该加一组 free list , 这个再说。我自己的需求中，时间性能并不太敏感。

12 月 25 日: 楼下有 wuwenbin 提到可以在节点中保存最大连续空闲区域来优化分配过程. 这样代码更短小, 速度也可以快一点. 唯一的缺憾是内存略微消耗的多一点点. 实现在 https://github.com/wuwenbin/buddy2

Posted by 云风 at 09:38 PM | Permalink | Comments (35)

开始这个话题前，离上篇开发笔记已经有一周多了。我是打算一直把开发笔记写下去的，而开发过程中一定不会一帆风顺，各种技术的抉择，放弃，都可能有反复。公开记录这个历程，即是对思路的持久化，又是一种自我督促。不轻易陷入到技术细节中而丢失了产品开发进度。而且有一天，当我们的项目完成了后，我可以对所有人说，看，我们的东西就是这样一步步做出来的。每个点滴都凝聚了叫得上名字的开发人员这么多个月的心血。

技术方案的争议在我们几个人内部是很激烈的。让自己的想法说服每个人是很困难的。有下面这个话题，是源于我们未来的服务器的数据流到底是怎样的。

我希望数据和逻辑可以分离，有物理上独立的点可以存取数据。并且有单独的 agent 实体为每个外部连接服务。这使得进程间通讯的代价变得很频繁。对于一个及时战斗的游戏，我们又希望对象实体之间的交互速度足够快。所以对于这个看似挺漂亮的方案，可能面临实现出来性能不达要求的结果。这也是争议的焦点之一。

我个人比较有信心解决高性能的进程间数据共享问题。上一篇 谈的其实也是这个问题，只是这次更进一步。

核心问题在于，每个 PC (玩家) 以及有可能的话也包括 NPC 相互在不同的实体中（我没有有进程，因为不想被理解成 OS 的进程），他们在互动时，逻辑代码会读写别的对象的数据。最终有一个实体来保有和维护一个对象的所有数据，它提供一个 RPC 接口来操控数据固然是必须的。因为整个虚拟世界会搭建在多台物理机上，所以 RPC 是唯一的途径。这里可以理解成，每个实体是一个数据库，保存了实体的所有数据，开放一个 RPC 接口让外部来读写内部的这些数据。

但是，在高频的热点数据交互时，无论怎么优化协议和实现，可能都很难把性能提升到需要的水平。至少很难达到让这些数据都在一个进程中处理的性能。

这样，除了 RPC 接口，我希望再提供一个更直接的 api 采用共享状态的方式来操控数据。如果我们认为两个实体的数据交互很频繁，就可以想办法把这两个实体的运行流程迁移到同一台物理机上，让同时处理这两个对象的进程可以同时用共享内存的方式读写两者的数据，性能可以做到理论上的上限。

ok, 这就涉及到了，如何让一块带结构的数据被多个进程共享访问的问题。结构化是其中的难点。

方案如下：

我们认为，需要交互和共享的数据，就是最终需要持久化到外存中的数据。整体上看，它好像一个小型内存数据库。它一定可以通过类似 google protocol buffers 的协议来序列化为二进制流。它和内存数据结构是有区别的。主要是一些约束条件，让这件事情可以简单点解决，又能满足能想到的各种需求。

数据类型是有限的：

1. nil
2. number
3. boolean
4. string
5. map
6. array

以上 6 种类型足够描述所有的需求，这在 lua 中已得到了证实。不过这里把 lua 的 table 拆分为 map 和 array 是对 protobuf 的一种借鉴。这里的 map 是有 data scheme 的，而不是随意的字典。即 key 一定是事先定义好的原子，在储存上其实是一个整数 id ，而 value 则可以是其它所有类型。

array 则一定是同类型数据的简单集合，且不存在 array 的 array 。这种方式的可行性在 protobuf 的应用中也得到了证实。

本质上，任何一个实体的所有数据，都可以描述为一个 map 。也就是若干 key-value 对的集合。array 只是相同 key 的重复（相当于 protobuf 里的 repeated）。

这里可以看出，除了 string 外，所有的 value 都可以是等长的，适合在 C 里统一储存。每个条目就是 id - type - value - brother 的一组记录而已。

其中 map 用二叉树的方式储存就可以满足节点的定长需求，左子树是它的第一个儿子，右子树是它的兄弟。

我们用一个固定内存块来保存整块数据，里面都是等长的记录，map 的记录中，左右子树都用保存着全局记录序号。

string 需要单独储存，所有的 string 都额外保存在另一片内存中（也可以是同一片内存的另一端）。在记录表中，记录 string 内容在 string pool 中的位置。

这样做有什么好处？

由于数据有 scheme（可以直接用 protobuf 格式描述），所以数据在每个层次上的规模是可以预估的，数据都是以等长记录保存的，对整个数据块的修改都可以看成是对局部数据的修改或是对整体的追加。这两个操作恰巧都可以做成无锁的操作。

换句话说，每次对整颗树具体一个节点的修改，都绝对不会损坏其它节点的数据。

有了这块组织好的数据结构有什么用呢？首先持久化问题就不是问题，但这只是一个附带的好处。这块数据虽然能完整的记录各种复杂的结构数据，但不利于快速检索。我们需要在对这颗树的访问点，制作一个索引结构。如果导入到 lua 中，就是一个索引表。当我们第一次需要访问这颗树的特定节点：体现为读写 xxx.yyy.zzz 的形式，我们遍历这颗树，可以方便的找到节点的位置。大约时间复杂度是 O(N^2) ：要遍历 N 个层次，每个层次上要遍历 M 个节点。当然这里 N 和 M 都很小。

一旦找到节点的位置，我们就可以在 lua 中记录下这个绝对位置。因为每个节点一旦生成出来，就不会改变位置了。下次访问时，可以通过这个位置直接读写上面的数据了。

string 怎么办呢？我的想法是开一个 double buffer 来保存 string 。string 和节点是一一对应的关系。当节点上的 string 修改时，就新增加一个 string 到 pool 里，并改变引用关系。当一个 string pool 满后，可以很轻易的扫描整个 string pool ，找到那些正在引用的 string ，copy 到另一个 string pool 中。这个过程比一般的 GC 算法要简单的多。

最后就是考虑读写锁的问题了。只有一些关键的地方需要加锁，而大部分情况下都可以无锁处理。甚至在特定条件下，整个设计都可以是无锁的。

btw, 这一周剩下来的时间就是实现了。多说无益，快速实现出来最有说服力。按照惯例，应该会开源。

Posted by 云风 at 07:59 PM | Permalink | Comments (18)

前几天写的 pbc 初衷就是想可以方便的 binding 到动态语言中去用的。所以今天花了整整一天自己写了个简单的 lua binding 库，就是很自然的工作了。

写完了之后，我很好奇性能怎样，就写了一个非常简单的测试程序测了一下。当然这个测试不说明很多问题，因为测试用的数据实在是太简单了，等明天有空再弄个复杂点的来跑一下吧。我很奇怪，为什么 google 官方的 C++ 版性能这么差。

我的 lua 测试代码大约是这样的：

local protobuf = require "protobuf"

addr = io.open("../../build/addressbook.pb","rb")
buffer = addr:read "*a"
addr:close()
protobuf.register(buffer)

for i=1,1000000 do
    local person = {
        name = "Alice",
        id = 123,
    }
    local buffer = protobuf.encode("tutorial.Person", person)
    local t = protobuf.decode("tutorial.Person", buffer)
end

100 万次的编码和解码在我目前的机器上，耗时 3.8s 。

为了适应性能要求极高的场合，我还提供了另一组高性能 api 。他们可以把数据平坦展开在 lua 栈上，而不构成 table 。只需要把循环里的代码换成

    local buffer = protobuf.pack(
        "tutorial.Person name id",
         "Alice", 123)
    protobuf.unpack("tutorial.Person name id", buffer)

就可以了。这个版本只需要耗时 0.9s 。

一个月前，我曾经自己用 luajit + ffi 实现过一个纯 lua 的版本（没有开源），我跑了一下这个 case ，那个版本也很给力，达到前面的接口的功能，只需要 2.1s 。

不过我相信我新写的 binding 慢主要还是慢在 lua 上， 我换上了 luajit 跑以后，果然快了很多。

table 版本的耗时 1.7s , 平坦展开版是 0.57s.

看来 luajit 的优化力度很大。

btw, 我去年早些时候还写过一个 lua binding ，今天也顺便测了一下，在 luajit 下跑的时间是 1.2s 。没有这次写的这个版本快。

最后，我随手写了一个 C++ 的版本。应该有不少优化途径。不过我想这也是某中常规用法。

这段代码在开了 -O2 编译后，在我的机器上依旧需要时间 1.9s。若是这么看，那简直是太慢了 (比 luajit + c binding 还慢)。很久没研究 C++ 的细节，也懒得看了，如果谁有兴趣研究一下为什么 C++ 这么慢，我很有兴趣知道原因。

12 月 16 日

留言中 lifc0 说这段 C++ 代码中开销最大的是 stringstream 的构造和销毁, 所以我改了一段代码:

这样更符合现实应用, 每次初始化 stringstream 而不构造新的出来.

这样运行时间就从 1.90s 下降到 1.18s 了.

Posted by 云风 at 10:44 PM | Permalink | Comments (44)

前几天写的盒饭的问题 有很大争议。我并不认为我的结论一定正确，但我想讨论这个问题的人忽略了许多现实的复杂性。

我想说，这是个真实事件，并不是因为我想说明什么问题编的故事。我依然相信，我最后如果做一个交换，会更好一些。不过不想为这个事情争论下去 :)

我觉得这个问题和蒙特霍尔问题有相似之处，但并不相同。我也没想仔细去计算概率，直想快速判断，换或不换哪种得到正确结果的可能性更大。

下面我想向有兴趣讨论说说我上次说的比较含糊的一些条件。毕竟这些条件只有当事人才注意的比较清楚：

先谈谈，蒙提霍尔问题中，为什么参加游戏的人更换选择是更好的选择。

假设主持人完全不了解门背后的东西的话，我认为主持人的任何选择都不足以改变游戏者选中的概率。因为他们是独立事件。

但，一旦主持人了解了门背后的东西，并依据他的信息做有倾向性的选择话，这个选择就改变了之前的概率。

ok 回头来看我的盒饭问题。如果帮我订盒饭的人和其他人没有差异，且所有人做订饭这件事情上做出的选择没有差异性的话，我认为如果我了解到剩下的盒饭中每一份是什么的信息后，永远都应该选择同样种类最多的那一份，直到最后当牛展和香菇一样多，我选哪一份概率都一样。这是因为这些订饭事件相互之间是独立事件，没有影响概率。

选择同样种类最多的一份是因为牛展和牛展是一样的，即使我选的不是我订的那一份特定的牛展，而只要我订的是这个，就可以和别的定牛展的人互换。

事实却比上面说的要复杂一点，因为前提条件并不如假设般的明确。事实上，前提条件在我的脑子里也是在不断变化猜测的。

我并不认为牛展更受欢迎。因为一共有将近 20 份快餐，里面可能有多份牛展，也有多份香菇，还有别的一些什么，我并不了解。

一大堆快餐刚到的时候，我并不指望自己可以了解到我订的什么，所以也不着急去拿。只想等大家都拿完了，我去捡剩下的。直到剩的不多时，检查了剩下的四份的内容才有了上面的故事。

可以注意到，一开始，我们可以认为，订饭的同学前提都一样，反正是盒饭，也无所谓什么好吃什么不好吃。所以在菜单上选菜的时候（菜单上不只牛展和香菇两种）从我的角度都无法确定他们每个人选了什么。所以就预设为订了什么的概率都是相同的。也就是说，如果菜单上有四种东西，特定的人订牛展的概率就是 1/4 ，如果只有两样，那么订香菇的概率也就是 1/2 。这是从订饭者的角度看的。

不过在这件事上，我是把吃饭的各位同学与行政 mm 分开看的。因为行政并不吃饭，只是帮我订。（她在快餐送到的时候并不在场，最后也没有留她的一份，说明她中午并不在公司吃快餐）

订饭给自己吃，和帮别人订饭，选菜的概率就不均等了吧。

我最后的逻辑其实一句话就能说清楚：

当我不知道行政帮我订餐的偏好和选择的行为方式时（我不知道她怎样给我选了中饭），面对四份快餐，两种选择，前两个人都来拿走了牛展后，存在第三个人取走香菇的可能性是比较小的。

如果这么说还不清晰；那么假设有 100 个人来取饭，剩下有 100 份牛展，一份香菇；如果存在一个人定的香菇的话，那么根本不会让我等到最后两份这个人才出现。

因为，如果存在这个人，那么，他可能是第一个出现，可能是第二个出现，也可能是第三个出现。这个出现时机绝对是等概率的。没有任何理由，吃香菇的人就比别人晚吃饭。而我没有看到他出现，就很可能这个人并不存在。

如果这么说还不清晰；那么假设有 100 个人来取饭，剩下有 100 份牛展，一份香菇；如果存在一个人定的香菇的话，那么根本不会让我等到最后两份这个人才出现。

这样，回头从另一个角度看，大家订的什么饭却很难说是一个等概率事件了。作为自己的中餐，可能牛展更好吃，会偏好多一点；也有可能有从重心理，在订的时候看到别人订了这个，就也选这个，等等等等。

我可以认为吃饭的同学在做自己中饭选择的时候，前提条件相同；但可以认为帮我订饭却自己不吃的人在做选择的时候有另外的逻辑。最后为什么剩下更多的牛展，而不是四份不同的菜，或是两份牛展两份香菇，有可能是因为随机选择的一种选择，也可能是参与订饭的人的立场不同导致差异的正常结果。

这些差异，能够使我做出不同的选择。但我不了解所有的前提条件，所以只能通过已知的条件做判断：过来取饭的次序（他们出现的时间相差不到一分钟）的概率要比每个人选了什么菜的概率要明确的多。

和蒙特霍尔问题类似的地方在于，主持人和游戏者立场不同；帮我订饭的人和给自己订饭的那些同学的立场也不同。

记得 10 年前跟人争论蒙特霍尔问题时，我编造过一个类似的问题，来说明我的观点：如果三个门后有一个有汽车，你和你的朋友去挑；你仔细检查了门，发现它们都是一样的，所以你觉得很难判断哪个几率更大，所以你选了其中一个；这时候你的朋友也上了，他也仔细检查了一遍，然后对你说，我比较确定是这一个（不是你选的那个）。这时你拉开你选的，失望的发现你的运气不佳；这个时候给你一个选择再选一次，你是选你朋友选的呢（相信他的判断），还是选另一扇呢？

生活中遇到需要抉择的问题时，我不会在脑子里去计算精确的概率。但我会简单的相信：我碰不到小概率事件。如果碰上了貌似很小概率才会发生的事情时，我更多的倾向于相信：一些我所不了解的事情中隐含了某些导致这个结果的条件。

对于上面最后那个问题，我会选择我的朋友选中的那扇门。因为我确定他和我的目的相同，都希望选中汽车。或许他只是和我一样是碰运气；但也可能是我没发现的线索，他却发现了。而后者的几率略大一些。

Posted by 云风 at 11:17 PM | Permalink | Comments (40)

这周我开始做场景模块。因为所有 PC 在 server 端采用独立的 agent 的方式工作。他们分离开，就需要有一个模块来沟通他们。在一期目标中，就是一个简单的场景服务。用来同步每个 agent 看到的世界。

这部分问题，前不久思考过 。需求归纳如下：

1. 每个 agent 可以了解场景中发生的变化。
2. 当 agent 进入场景时，需要获取整个世界的状态。
3. agent 进入场景时，需要可以查询到它离开时自己的状态。关于角色在场景中的位置信息由场景服务维护这一点，在 开发笔记1 中提到过。

大批量的数据同步对性能需求比较高。因为在 N 个角色场景中，同步量是 N*N 的。虽说，先设计接口，实现的优化在第二步。但是接口设计又决定了实现可以怎样优化，所以需要比较谨慎。

比如，同步接口和异步接口就是不同的。

请求回应模式最直观的方式就是设计成异步接口，柔韧性更好。适合分离，但性能不易优化。流程上也比较难使用。（使用问题可以通过 coroutine 技术来改善 ）即使强制各个进程（不一定是 os 意义上的进程）在同一个 CPU 上跑，绕开网络层，也很难避免过多的数据复制。虽有一些 zero-copy 的优化方案，但很难跨越语言边界。

同步接口使用简单，但在未经优化前，可能不仅仅是性能较差的问题，而是完全不可用。一旦无法优化，接口修改对系统的变动打击是很大的。（异步接口在使用时因为充分考虑了延迟的存在，及时没有优化，也不至于影响整个系统的运转）

在这次的具体问题上，我判断使用同步接口是性能可以接受的。即，用户可以直接查询场景的各种状态。蜗牛同学希望实现上更简单，干脆就是把所有 agent 以及未来的 npc 服务实现在一起，大家共享场景状态。因为框架使用 coroutine 调度，其实是相互没有冲突的。

在一个场景物理上在一个 CPU 上跑这个问题上，我没有不同意见。但是，我希望在设计上依旧独立。agent 的并发在实现上是不存在的，但在设计上是考虑进去的。agent 之间物理上完全独立，但在交互上使用一些优化手段达到零成本。

模块在物理上分离，是高健壮性和柔韧性的充分条件。最小依赖单一模块实现的质量。

至于性能开销，我的观点是，把所有东西塞到一起，使得沟通成本下降；比如大家都跑在同一 lua state 中，没有跨语言边界的信息传递；其实是一种成本延迟支付。抛开可能引起的健壮性下降问题，动态语言的 GC 代价也是初期无法预期的。

不过无论采用何种实现方案，接口设计总比其它更重要。需要留意的是，先分开实现再合起来，比先合在一起以后再分离，在实践操作中要难得多。这在历史上许多系统的大模块设计中被反复证明过：我看过太多上万行的 C++ 代码，几十个类绞在一起，留下飞线和后门，让类与类之间做必要的沟通。静态语言尚且如此，毋提动态语言这种随意性更高的东西了。

这周，怪物公司和小V 还在忙 client 那边跟美术的沟通和工具插件开发，原定的 C/S 联调一再被推迟。我自己在写了两三百行场景服务的 C 代码后，觉得可以暂放一下。所以最终接口还不需要完全敲定。前两天想到一些优化方案，也暂时不需要实现，先记录一下。

关于并发读场景状态的问题：

场景数据其实是允许读取方不那么严格需要一致的。因为场景数据是局部累积的一种缓慢变化。任何一个读方都不必一定读到最新的版本，而只要求读到一个完整的版本。即，我读到的场景是 0.05s 以前的状态也是可以被容忍的。0.05s 对于人类是一瞬间，但对于计算机却是一个相当长的时间段。

这种延迟本身也是存在的，因为更新场景的写入者本身也一定存在于不同机器上，对于网络通讯， 50ms 已经是一个不错的相应速度了。

如果在本地内存，做同步读取，任何一个需要原子性的读操作，需要的时间都远远低于 0.01s 数个数量级，这个速度差，让我们有一起契机摆脱并发操作需要的锁。

简单说，我想引入一个 triple buffer ，让本地内存中，场景数据有三份几乎相同的 copy 。为了后面好描述，我把它们称为 A B C 。

所有的场景更新者，通过一个消息队列提交更新需求，向 A B C 更新。每个更新请求，都需要依次更新完 A B C 后才销毁。

场景服务提供者控制一个写指针，每隔 0.01s 在 A B C 间翻转。也就是说，当 0.01s 的周期一到，下一次原子写操作就写向下一个场景镜像。

A B C 这三个场景镜像采用共享内存的方式，供唯一的一个写入队列以及不受限的读取者共享。写入队列维护进程在翻转写指针的同时，也翻转读指针。当写指针在 A 时，读指针在 C ；当写指针翻转到 B 时，读指针调整到 A ；等等。

每次读操作可以看成是原子的，操作前先获取目前的读指针指向的镜像，然后直接在这份镜像上做完后续的读操作。因为一次读操作需要消耗的时间远远低于 0.01s ，而写指针触碰回这个镜像的时间则在 0.01s 到 0.02s 之间，不会短于 0.01s 。这样，绝对不会发生读写冲突。

当然，用 double buffer 也是可行的，但需要在读取完毕后重新检查一下当前的读指针，看看是否还指向原来的镜像，如果已经切换了，就需要放弃刚才的结果，重新读一次。而且在读过程中，需要保证错误的数据（可能因为正在写入而不完整）不会引起程序崩溃。这样开发难度会增加。

事后复审读指针依旧可以做，如果发生异常记入 log ，一旦发生再来考量时间窗口的大小设置是否合理，或是看看到底什么意外导致了读写冲突。

对于高负载下，读操作可能被挂起，引起的原子性被破坏的问题，其实也是可测算的。

首先，在读 api 中，应该避免任何 IO 操作以及系统调用，比如写 log 。一切 log 都应该在操作完毕后再统一进行。一次原子读操作中，需要保证是单纯的 CPU/内存 操作指令。这样可以保证单一 api 的过程，最多被 os 调度器打断一次。（因为指令数足够少，远小于 os 的最小时间片跑的 cpu 指令数）

写操作的间隔时间足够长，如果调度器是公平的，就可以保证在同样条件下写操作的镜像翻转消耗的时间片大于两倍的单次读操作的时间片。这样，做两次翻转后，保证一次读操作至少经历了同样的两倍以上的时间片。可以认为，单次读操作不会被写操作损坏。

Posted by 云风 at 02:47 PM | Permalink | Comments (28)

话接 开发笔记1 。我们将为每个玩家的接入提供一个 agent 服务。agent 相应玩家发送过来的数据包，然后给于反馈。

对于 agent 服务，是一个典型的包驱动模式。无论我们用 Erlang 框架，还是用 ZeroMQ 自己搭建的框架，agent 都会不会有太多的不同。它将利用一个单一的输入点获取输入，根据这些输入产生输出。这个输入点是由框架提供的。框架把 Agent 感兴趣的包发给它。

我们会有许多 agent ，在没有它感兴趣的包到来时，agent 处于挂起状态（而不是轮询输入点）。这样做可以大量节省 cpu 资源。怎样做的高效，就是框架的责任了，暂时我们不展开讨论框架的设计。

下面来看，一旦数据包进入 agent 应该怎样处理。

游戏服务逻辑复杂度很高，比起很多 web 应用来说，要复杂的多。我们不能简单的把外界来的请求都看成的独立的。把输入包设计成 REST 风格，并依赖数据服务构建这套系统基本上行不通。几乎每个包都有相关的上下文环境，就是说，输入和输入之间是有联系的。简单的把输入看成一组组 session 往往也做不到 session 间独立。最终，我把游戏服务器逻辑归纳以下的需求：

游戏逻辑由若干流程构成。比如，agent 可以看作是登陆流程和场景漫游服务流程。

每个流程中，服务器可以接收若干类型的包，每种类型的包大多可以立刻处理完毕。可以简单的认为提供了一个请求回应模式的处理机。

在处理部分数据包时，可以开启一个子流程，在子流程处理完毕前，不会收到父流程认可的数据包类型。（如果收到，即为非法逻辑）

在处理部分数据包时，也可以开启一个并行流程，这个流程和已有的流程处理逻辑共存。即，框架应根据包类型把数据包分发到不同的并行流程上。例如，在场景中漫游时，可能触发一个玩家交易的并发流程。（玩家交易行为需要多次交互确认的手续，不能一次性的完成。在交易过程中，其它如战斗、聊天的处理不可中断）

每个流程都可能因为某次处理后中断退出。继而进入后续的代码逻辑。这个中断退出行为，对于并发和非并发流程都有效。

RPC 可以看作一个简单的并发流程，即等待唯一返回包，并继续流程逻辑。

我希望能设计一个简单的 DSL 来描述我要的东西，大约像这个样子：

...1
listen :
    case message A :
        ...2
        listen :
            case message B:
                ...3
                break
            case message C:
                ...4
            case message D:
                ...5
        ...6
    case message E:
        ...7
        break
...8
listen :
    case message F:
        fork listen :
            case message G:
                ...9
            case message H:
                ...10
                break
        ...11
    case message I:
        ...12

解释一下上面这张表：

它表示，服务器启动后，会运行 ...1 这些代码，然后开始等待输入 A 或 E 两种消息 。如果收到 E 类消息，就执行 ...7 段代码，再因 break 跳出到 ...8 的位置。

如果收到 A 类消息，执行 ...2 代码，然后进程改为等待 B,C,D 类消息。此时，A,E 类消息都无效。直到收到 B 类消息后，执行流程到 ...6 并结束 A 消息的处理。再次等待输入 A 或 E 。

...8 后的阶段大致相同，但在 F 类消息的处理中，使用了并行的输入(fork listen) 。此时，系统会同时等待 G/H 和 F/I 的输入。只到有 H 类消息输入，中断 F 的处理流程，执行完 ...11 后，系统去掉 G/H 的输入等待。

要实现这么一套 DSL ，首先需要用已有的动态语言先实现一下所有功能，等需求稳定后，再设计 DSL 的语法。支持 coroutine 的 lua 非常适合做这件事情。

这套东西的框架其实是一个 coroutine 的调度器。每个执行流（就是 case message），不论是不是并行的，都是一个 coroutine 。当遇到 listen ，fork ，break 的时候 coroutine yield 出来，由调度器来决定下一步该 resume 哪个分支就好了。

框架只需要接收外界传入的带类型信息的 message ，在调度器里维护一张消息类型到执行流的映射表，就可以正确的调度这些东西。

剩下的事情就是处理穿插在其中的代码块内，数据相互之间可见性的问题；以及给 RPC 提供一个更易用的接口了。

我大约花了不到 100 行 lua 代码来实现以上提到的功能的雏形，贴在下面，尚需完善：

--- agent.lua
local setmetatable = setmetatable
local coroutine = coroutine
local assert = assert
local unpack = unpack
local print = print
local pairs = pairs

module "agent"

local function create_event_group(self, events, thread , parent_group)
    local group = {
        event = {},
        thread = thread,
        parent = parent_group,
    }
    if parent_group then
        for k,v in pairs(parent_group.event) do
            self.event[k] = nil
        end
    end

    for k,v in pairs(events) do
        group.event[k] = { func = v , group = group }
        assert(self.event[k] == nil , k)
        self.event[k] = group.event[k]
    end
end

local function pop_event_group(self, group)
    for k in pairs(group.event) do
        self.event[k] = nil
    end
    if group.parent then
        for k,v in pairs(group.parent.event) do
            assert(self.event[k] == nil , k)
            self.event[k] = v
        end
    end
end

function create(main)
    local mainthread = coroutine.create(main)
    local self = setmetatable( { event = {} } , { __index = _M })
    local r , command , events = coroutine.resume(mainthread , self)
    assert(r , command)
    assert(command == "listen" ,  command)
    create_event_group(self, events, mainthread)
    return self
end

function send(self, msg , ...)
    local event = self.event[msg]
    if event == nil then
        print (msg .. " unknown" , ...)
    else
        local event_thread = coroutine.create(event.func)
        local group = event.group
        while true do
            local r, command, events = coroutine.resume(event_thread, self, ...)
            assert(r,command)
            if command == "listen" then
                create_event_group(self, events, event_thread , group)
                break
            elseif command == "fork" then
                create_event_group(self, events, event_thread)
                break
            elseif command == "break" then
                pop_event_group(self, group)
                event_thread = group.thread
                group = group.parent
            else
                break
            end
        end
    end
end


function listen(agent , msg)
    coroutine.yield("listen",msg)
end

function quit(agent)
    coroutine.yield "break"
end

function fork(agent, msg)
    coroutine.yield("fork",msg)
end

--- test.lua

local agent = require "agent"

a = agent.create(function (self)
    self:listen {
        login = function (self)
            self:listen {
                username = function(self , ...)
                    print("username", ...)
                    self:listen {
                        password = function(self, ...)
                            print("password", ...)
                            self:quit()
                        end
                    }
                    self:quit()
                end ,
            }
        end,
        ok = function (self)
            self:quit()
        end,
    }
    print "login ok"
    local q = 0
    self:listen {
        chat = function (self, ...)
            print("chat", ...)
        end,
        question = function (self , ...)
            print("question", ...)
            local answer = "answer" .. q
            q = q+1
            self:fork {
                [answer] = function (self, ...)
                    print("answer", ...)
                    self:quit()
                end
            }
        end,
    }
end)

a:send("login")
a:send("username","alice")
a:send("username","bob")
a:send("password","xxx")
a:send("login")
a:send("username","bob")
a:send("password","yyy")
a:send("chat","foobar")
a:send("ok")

a:send("chat", "hello")
a:send("question","?0")
a:send("chat", "world")
a:send("question","?1")
a:send("answer0","!0")
a:send("answer1","!1")

12 月 5 日补充:

周一上班和蜗牛同学讨论了一下需求， 最后我们商定抽象出一个 session 出来， 供 fork 出来的流程使用。因为并行的流程会使用相同的消息类型，但流程上是独立的。

根据 session id 和 message type 做两级分发要清晰一些。

然后，我们再对 rpc 调用做简单的封装，使用更简单。

改进后的代码就不再列出了。

Posted by 云风 at 05:30 AM | Permalink | Comments (13)

今天起晚了, 到了办公室, 行政mm 出去了, 中饭却已经订好。据说随便帮我订了一份。

几分钟后，快餐送过来，我很纠结我应该拿哪一份吃。只好等其他同学取走。当桌子上还剩下四份的时候，我决定试一下手气，看看能不能拿到我的那一份。

打开检查了一下，发现有三份是相同的，都是牛展，一份是香菇。盘算了一下，我拿走牛展拿对的几率有 75% 。

这个时候蜗牛同学和怪物公司都过来了，居然他们都拿了牛展。这个时候我犯了个错误，没有及时的放下手上的盒饭。果然，几分钟后，PS 同学就在抱怨他的牛展怎么变成香菇了。

我检讨了一下，本来我是有机会修正我的错误的，这其实是一个简单的概率问题：

当有四份快餐的时候，假定另外三人的选择是随机的，三人出现的次序也随机。那么，如果存在一人订的香菇的概率是 75% 。我一开始的选择并没有错。

但是出现了两个取走牛展的同学后就不一样了。假如我的那一份真的是牛展的话，发生这件事的概率只有 1/3 。所以，我的饭是香菇的可能性要更大一些。

这件事上，我的结论是，晚上要早睡，早上早起就可以不麻烦别人帮忙订饭。

Posted by 云风 at 12:54 PM | Permalink | Comments (60)

我一直不太满意 google protocol buffers 的默认设计。为每个 message type 生成一大坨 C++ 代码让我很难受。而且官方没有提供 C 版本，第三方的 C 版本 也不让我满意。

这种设计很难让人做动态语言的 binding ，而大多数动态语言往往又没有强类型检查，采用生成代码的方式并没有特别的好处，反而有很大的性能损失（和通常做一个 bingding 库的方式比较）。比如官方的 Python 库，完全可以在运行时，根据协议，把那些函数生成出来，而不必用离线的工具生成代码。

去年的时候我曾经写过一个 lua 版本的库 。为了独立于官方版本，我甚至还用 lpeg 写了一个 .proto 文件的解析器。用了大约不到 100 行 lua 代码就可以解析出 .proto 文件内的协议内容。可以让 lua 库直接加载文本的协议描述文件。（这个东西这次帮了我大忙）

这次，我重新做项目，又碰到 protobuf 协议解析问题，想从头好好解决一下。上个月一开始，我想用 luajit 好好编写一个纯 lua 版。猜想，利用 luajit 和 ffi 可以达到不错的性能。但是做完以后，发现和 C++ 版本依然有差距 (大约只能达到 C++ 版本的 25% ~ 33% 左右的速度) ，比我去年写的 C + Lua binding 的方式要差。但是，去年写的那一份 C 代码和 Lua 代码结合太多。所以我萌生了重新写一份 C 实现的想法。

做到一半的时候，有网友指出，有个 googler 最近也在做类似的工作。μpb 这个项目在这里 。这里他写了一大篇东西阐述为什么做这样一份东西，大体上和我的初衷一致。不过他的 api 设计的不太好，我觉得太难用。所以这个项目并不妨碍我完成我自己的这一份。

C 版本之所以很难把 api 设计好，是因为 C 缺乏必要的数据结构。而且没有垃圾回收，缺乏数据类型的元信息。

考虑再三，我决定提供两套 api ，满足不同的需求。

当性能要求不太高的时候，仅仅满足 C 语言开发的便捷需要，提供一套简单易用的 api 操作 protobuf 格式的 message 。我称之为 message api 。

大体上有两组 api :

对于编码 protobuf 的消息，使用 rmessage 相关 api

struct pbc_rmessage * pbc_rmessage_new(struct pbc_env * env, const char * typename , struct pbc_slice * slice);
void pbc_rmessage_delete(struct pbc_rmessage *);

uint32_t pbc_rmessage_integer(struct pbc_rmessage * , const char *key , int index, uint32_t *hi);
double pbc_rmessage_real(struct pbc_rmessage * , const char *key , int index);
const char * pbc_rmessage_string(struct pbc_rmessage * , const char *key , int index, int *sz);
struct pbc_rmessage * pbc_rmessage_message(struct pbc_rmessage *, const char *key, int index);
int pbc_rmessage_size(struct pbc_rmessage *, const char *key);

对于解码消息，使用 wmessage 相关 api

struct pbc_wmessage * pbc_wmessage_new(struct pbc_env * env, const char *typename);
void pbc_wmessage_delete(struct pbc_wmessage *);

void pbc_wmessage_integer(struct pbc_wmessage *, const char *key, uint32_t low, uint32_t hi);
void pbc_wmessage_real(struct pbc_wmessage *, const char *key, double v);
void pbc_wmessage_string(struct pbc_wmessage *, const char *key, const char * v, int len);
struct pbc_wmessage * pbc_wmessage_message(struct pbc_wmessage *, const char *key);
void * pbc_wmessage_buffer(struct pbc_wmessage *, struct pbc_slice * slice);

pbc_rmessage_new 和 pbc_rmessage_delete 用来构造和释放 pbc_rmessage 结构。从结构中取出的子消息，字符串，都是由它来保证生命期的。这样不需要用户做过于繁杂的对象构建和销毁工作。

对于 repeated 的数据，没有额外再引入新的数据类型。而是把 message 内部的所有域都视为 repeated 。这种设计，可以极大的精简需要的 api 。

我们用 pbc_rmessage_size 可以查询 message 中某个 field 被重复了多少次。如果消息中并没有编码入这个 field ，它能返回 0 感知到。

我把所有的基本数据类型全部统一成了三种：integer , string , real 。bool 类型被当成 integer 处理。enum 类型即可以是 string ，也可以是 integer 。用 pbc_rmessage_string 时，可以取到 enum 的名字；用 pbc_rmessage_integer 则取得 id 。

pbc_rmessage_message 可以获得一个子消息，这个返回的对象不必显式的销毁，它的生命期挂接在父节点上。即使消息中没有编码入某个子消息，这个 api 依然可以正确的返回。从中取出的子域都将是默认值。

integer 不区分 32bit 数和 64bit 数。当你能肯定你需要的整数可以用 32bit 描述时，pbc_rmessage_integer 的最后一个参数可以传 NULL ，忽略高 32bit 的数据。

wmessage 的用法更像是不断的向一个未关闭的消息包类压数据。当你把整个消息的内容都填完后，可以用 pbc_wmessage_buffer 返回一个 slice 。这个 slice 里包含了 buffer 的指针和长度。

需要注意的是，如果使用 pbc_wmessage_integer 压入一个负数，一定要将高位传 -1 。因为接口一律把传入参数当成是无符号的整数。

考虑到某些内部实现的性能，以及后面讲提到的 pattern api 的方便性（如果你完全拿这个库做 C/S 通讯）。建议所有的 string 都在末尾加上 \0 。因为，这样在解码的时候，可以将字符串指针直接指向数据包内，而不需要额外复制一份出来。

pbc_wmessage_string 可以压入非 \0 结尾的字符串，因为压入的数据长度是由参数制定的。当然你也可以不自己计算长度。如果长度参数传 <=0 的话，库会帮你调用 strlen 检测。并且将最终的长度减去这个负数。即，如果你传 -1 ，就会帮你多压入最后的一个 \0 字节。

Pattern API 可以得到更高的性能。更快的速度和更少的内存占用量。更重要的是，对于比较小的消息包，如果你使用得当，使用 pattern api 甚至不会触发哪怕一次堆上的内存分配操作。api 工作时的所有的临时内存都在栈上。

相关 api 如下：

struct pbc_pattern * pbc_pattern_new(struct pbc_env * , const char * message, const char *format, ...);
void pbc_pattern_delete(struct pbc_pattern *);
int pbc_pattern_pack(struct pbc_pattern *, void *input, struct pbc_slice * s);
int pbc_pattern_unpack(struct pbc_pattern *, struct pbc_slice * s , void * output);

我们首先需要创建一个 pattern 做编码和解码用。一个简单的例子是这样的：

message Person {
  required string name = 1;
  required int32 id = 2; 
  optional string email = 3;
}

这样一个消息，对于在 C 的结构体中，你可能希望是这样： struct Person { pbcslice name; int32t id; pbc_slice email; } 这里使用 pbc_slice 来表示一个 string 。因为对于 message 来说，里面的字符串是有长度的。并且不一定以 \0 结尾。slice 同样可以表示一个尚未解开的子消息。

我们使用 pbc_pattern_new 可以让 pbc 认识这个结构的内存布局。

struct pbc_pattern * Person_p = pbc_pattern_new(env , "Person" ,
  "name %s id %d email %s",
  offsetof(struct Person , name),
  offsetof(struct Person , id),
  offsetof(struct Person , email));

然后就可以用 pbc_pattern_pack 和 pbc_pattern_unpack 编码和解码了。pattern 的定义过程冗长而且容易出错（你也可以考虑用机器生成它们）。但我相信在性能及其敏感的场合，这些是值得的，如果你觉得写这些不值得，可以考虑用回上面的 message api 。

对于 repeated 的数据，pattern api 把他们看成一个数组 pbc_array 。

有这样一组 api 可以用来操作它：

int pbc_array_size(pbc_array);
uint32_t pbc_array_integer(pbc_array array, int index, uint32_t *hi);
double pbc_array_real(pbc_array array, int index);
struct pbc_slice * pbc_array_slice(pbc_array array, int index);

void pbc_array_push_integer(pbc_array array, uint32_t low, uint32_t hi);
void pbc_array_push_slice(pbc_array array, struct pbc_slice *);
void pbc_array_push_real(pbc_array array, double v);

数组是个略微复杂一些的数据结构，但如果你的数据不多的话，它也不会牵扯到堆上的额外内存分配。不过既然有可能调用这些 api 可能额外分配内存，那么你必须手工清除这些内存。而且在第一次使用前，必须初始化这个数据结构 (memset 为 0 是可以的)。

void pbc_pattern_set_default(struct pbc_pattern * , void *data);
void pbc_pattern_close_arrays(struct pbc_pattern *, void *data);

pbc_pattern_set_default 可以把一块内存，以一个 pattern 的形式，初始化所有的域。包括其中的数组的初始化。

pbc_pattern_close_arrays 使用完一块数据，需要手工调用这个 api ，关闭这个数据块中的数组。

关于 Extension ，我最后放弃了直接支持。没有提供类似 get extension 的 api 。这是因为，我们可以更简单的去处理 extension 。我把所有的 extension field 都加了前缀，如果需要，可以用拼接字符串的方式获得消息包内的扩展域。

最后介绍的是 pbc 的环境。

struct pbc_env * pbc_new(void);
void pbc_delete(struct pbc_env *);
int pbc_register(struct pbc_env *, struct pbc_slice * slice);

pbc 库被设计成没有任何全局变量，这样你想在多线程环境用会比较安全。虽然库并没有考虑线程安全问题，但在不同的线程中使用不同的环境是完全没有问题的。

每个环境需要独立注册需要的消息类型，传入一个 protobuf 库官方工具生成的 .pb 数据块即可。以 slice 的形式传入，register 完后，这块数据内存可以释放。

这个数据块其实是以 google.protobuf.FileDescriptorSet 类型来编码的。这个数据类型非常繁杂，使得 bootstrap 过程及其难写，这个在后面会谈到。

全部代码我已经开源方在 github 上了，可以在 https://github.com/cloudwu/pbc 取到代码。详细的用法也可以从那些 test 文件中找到例子。

这个东西很难写，所以代码很乱，在写这篇 blog 的时候我还没有开始整理代码的结构。大家想用的将就用，请善待 bug 和它的朋友们。

用一个复杂的 protobuf 协议来描述协议本身，真的很淡疼。当我们没有任何一个可用的协议解析库前，我们无法理解任何 protobuf 协议。这是一个先有鸡还是先有蛋的问题。就是说，我很难凭空写出一个 pbc_register 的 api ，因为它需要先 register 一个 google.protobuf.FileDescriptorSet 类型才能开始分析输入的包。

不依赖库本身去解析 google.protobuf.FileDescriptorSet 本身的定义是非常麻烦的。当然我可以利用 google 官方的工具生成 google.protobuf.FileDescriptorSet 的 C++ 解析类开始工作。但我偏偏又不希望给这个东西带来过多的依赖。

一开始我希望自定义一种更简单的格式来描述协议本身，没有过多的层次结构，只是一个平坦的数组。这样手工解析就有可能。本来我想给 protoc 写一个 plugin ，生成自定义的协议格式。后来放弃了这个方案，因为希望库用起来更简单一些。

但是这个方案还是部分使用了。这就是源代码中 bootstrap.c 部分的缘由。它读入一个更简单版本的 google.protobuf.FileDescriptorSet 的描述。这块数据是事先生成好的，放在 descriptor.pbc.h 里。生成这块数据使用了我去年完成的 lua 库。相关的 lua 代码就没有放出来了。当然到了今天，pbc 本身足够完善，我们可以用 pbc 写一个 C 版本。有兴趣的同学，可以在 test_pbc.c 的基础上修改。

这个玩意很难写, 主要是那个鸡生蛋,蛋生鸡的问题,导致我在实现过程的很长时间里,脑子里都糨糊一般. 所以很多代码实现的很糟糕, 但又不舍得删(因为难为我把它们写出来了, 重写很难调错). 希望一边写一边优化的坏习惯, 在对于这种比较难实现的东西上, 让我编写的好生痛苦. 为了效率, 我甚至写了三个针对不同情况处理的 map .

中间因为想法改变, api 设计改变,废弃了好几千行代码. 最终也就是这个样子了. 有空再重新理一下.

最终, 还有许多细节可以进一步优化, 比如如果只针对小头的机器做, 许多不必要的代码都可以省略掉. 对于 packed 数组也值得进一步优化. 甚至可以考虑加一点 JIT .

事情总算告一段落了。连续写了 5000 行代码，我需要休息一下。

Posted by 云风 at 12:40 AM | Permalink | Comments (56)