« March 2012 | Main | May 2012 »

April 26, 2012

pbc 优化

最近几天优化了一下 pbc

这是一个大改动,所以写 blog 记录一下。

首先,我为 rmessage 定制了一个 heap alloc ,在使用 rmessage 解包的时候不再调用系统的 malloc 。而是从一个连续内存 heap 上取用内存。这样在删除 rmessage 对象时也会更快。因为只需要把 heap 回收即可。

当然这样会导致 rmessage 解包时用到的内存增加。对于内存紧张,性能关键部分,我还是推荐 pattern 模式。虽然比较难用,但可以保证时间和空间性能。

另外,我增加了 upb 的 Event-based parsing 模式,见新增接口 pbc_decode

不过我认为这个 api 不适合直接在 C 里调用,但是用来做动态语言的 binding 不错。现在 lua binding 中的 decode 就改用这个实现了。这样每次解包就把所有项都解出来,而不用附着一个 userdata 。回避了手动调用 close_decoder 的问题。

btw, 根据一个同学使用的反馈,他们大多不主动调用 close_decoder ,而依赖 gc 回收 decode 过程中产生的 C 对象。但是这些 C 对象申请的内存不会通知 lua ,所以 lua 的 gc 触发条件不会及时触发。这使得 pbc 的 lua binding 可能占用大量内存。我这次的修改主要针对这个问题。

April 19, 2012

让多个 Lua state 共享一份静态数据

如果你在同一个进程里有多个 lua state , 它们需要共享大量的只读数据, 那么可能就不希望在每个 state 启动的时候都加载和解析一遍这些数据.

所以我们需要一个共享只读数据的方法。

前段时间,我实现了一个 共享内存服务 ,这个可以保证共享内存的安全读写。不过,如果数据是只读的,那么就不需要这么复杂了。

我们只需要把数据加载到一个 lua state 中,其它的同一进程内的 state 通过 C 接口去读数据就可以了。

今天,我做了简单的实现,放在了 github 上。

目前可以支持 nil number boolean function table 的数据交换。

function 交换有一些限制,不可以绑定 upvalue 。是用 string.dump 和 load 实现的。

table 类型返回的其实是一组 key ,需要继续用 get 来读取数据。

关于线程安全:我相信只是读一个 lua state 是线程安全的。

经过 resty 同学提示,由于多线程可能同时改写 database 的 stack ,故而有安全隐患。为了解决这个问题,我预先在 database 的 state 中初始化了 32 个 thread ,这样,不同的 thread 可以用独立的 stack ,应该就线程安全了。


4 月 23 日:

旧的版本, 在企图查询一个不存在的 key 的时候, 由于 lua_pushstring 不能保证线程安全。所以我重写了全部的实现,改用 C 实现了 hash 表。这份实现的读过程是线程安全的。

April 18, 2012

开发笔记(17) : 策划表格公式处理

前段时间为策划提供过一些技术上的支持, 设计过一个简单的 DSL 。但随着更多策划加入团队,我觉得这个思路不能很好的贯彻下去。

策划更喜欢通过 excel 表格来表达他心中的数值关系,而不是通过代码语言。我需要找到另一种更切合实际的方案来将策划的想法转换为可以运行的代码。

研究了一下策划历史项目上的 excel 表格后,我归纳了一下其需求。我们需要把问题分步解决,excel 表格到程序可以利用的数据结构是一项工作,而从表达了数据之间联系的结构到代码又是另一项工作。

对于数值运算,有怎样的需求呢?

我更多看到的是一种声明式的表达,而不是过程式的。比如,策划会定义,“血量”这个属性,实际上是等价于“耐力 * 10”。我们把后者定义为一个公式。

许多表格其实就是在不同的位置表达了这种公式推导关系:一个属性等价于另一些属性组成的表达式。而在运行时,根据人物的一些基础属性,可以通过一系列的公式推导,得到最终的一系列属性值。满足这个需求并不难,读出表格里的对应项,做简单的解析就可以了。(这里涉及到另一个问题,表格里的对应项在哪里,今天暂且不谈)

对于这种声明式表达,程序要做的工作是进行一次拓扑排序,把需要先求值的属性排在前面,有依赖关系的属性求解放在后面。这样就可以转换为过程式的指令。

另一种表格称为查表。其实就是表达一种映射关系。如下表:

法术伤害物理伤害
战士0.51
法师10.5

如果公式中提到了“法术伤害”这个属性值时,需要根据“职业”这个属性,去这张表里查到对应项。职业可以是“战士”或“法师”,对应了不同的“法术伤害”值。从 C 语言的角度看,“职业”是一个枚举量,而法术伤害可以定义为一个一维数组,以枚举值为索引,便可以查到对应值。若是动态语言,更适合的方式是做一个字典,性能低一些,但更加灵活。

但无论是表达式求值,还是查表求值,目的都是一个:用一组属性通过某种变换得到新的属性值。每一张表格都提供了一组变换关系,最终可以从一组基础属性推导出各种需求的值来。


把策划这个需求解决好并不太难,尤其是对于动态语言来说更为简单。难点在于性能。尤其对于即时战斗的 MMO 来说,每次攻击都需要做一系列的运算,这些运算若是依赖大量的表格推演,性能很难保证。我想,最为彻底的方案是把这些属性数值之间的关系编译成目标机器上的原生代码。为此,我选择了 tcc 这个工具。这样,我只需要用 lua 去一次性生成 C 代码,然后交给 tcc 编译就好了。

ps. tcc 最新版本的 git 仓库在这里

我首先定义了 lua 和 tcc 交互的接口。最简单的方式是只支持一种数据类型,float 。一个 tcc 内的函数可以接受若干个 float 输入,产生若干个 float 输出。这样的 C 函数的原型看起来是这样:

    void func(float input[] , float output[]);

交互接口很容易实现,为 lua 写一个 C 扩展即可。

接下来是实现一个 lua 模块利用 tcc 生成需要的运算函数。

这个一个模块,提供一个公式对象,然后可以把一系列的表达式以及查表规则设入对象,最后调用编译方法得到编译好的运算函数。

f = require "formula"

test = f()
test:table("属性表", { "战士" , "法师"  } ,
   { ["物理伤害"] = { 1 , 0.5 } , ["法术伤害"] = { 0.5 , 1} })

test:expression("攻击强度", "力量 * 2")
test:expression("血量", "耐力 + 1")
test:expression("伤害", "攻击强度 / 血量 * 物理伤害")

test:lookup("物理伤害","属性表","职业")

test:compile { "伤害" }

print(test { ["力量"] = 2 , ["耐力"] = 3.5 , ["职业"] = "战士" })

这里,table 方法可以把一个查询表置入对象。分别是表名,key 表,和数据表。

expression 可以设置属性间的换算表达式。

lookup 可以设置一种查找规则。

最后只需要把基础属性传给 compile 得到的 C 运算函数(传入前做一个替换工作,把字典替换成循序的参数),得到运算结果。

下面看一下,内部生成的 C 代码是怎样的:

float table_1[] = {1,0.5}; void main(float input[],float output[]) { float t[7]; t[0]=input[0]; t[2]=input[1]; t[4]=input[2]; t[1]=t[0] + 1; t[3]=t[2] * 2; t[5]=table_1[(int)t[4]]; t[6]=t[3] / t[1] * t[5]; output[0]=t[6]; }

一共有三个输入参数,以及一个输出参数,还有三个中间变量。

我们可以把一共 7 个量看作是 7 个寄存器,在分析之前的公式关系时,无非就是做了一下寄存器分配的工作。除了生成这些表达式运算的代码行外,还提取出了查表需要的表列。这里,通过分析输入,可以知道“职业”这一个属性其实是一个枚举量,能用整数表达。那么把“战士”对应到 0 的这个过程其实是在 lua 代码中查表完成的。而 C 函数则接受的是数字而不是字符串了。

最终我们可以计算出“伤害”属性的值,放在 t[6] 中,最后赋予 output[0]。当然,这段 C 代码的生成还可以进一步优化。这些可以留到以后去做了。

April 11, 2012

Lua int64 的支持

虽然今天发了 twitter ,以及向 lua mailling list 里投递了消息,不过想想还是写一篇 blog 记录一下。

Lua 只支持一种 number ,默认是 double 类型。虽然你可以通过修改 luaconf.h 里的定义,把 lua number 改成 int64 。但是为了 int64 类型而放弃浮点数,恐怕不是大多数人想要的。

int64 通常用在 uuid 上,也就是说不需要对其数学运算,只需要可以比较就好了。我以前最喜欢的做法是用 8 bytes 长的 string 来表示一个 int64 。这样,即可以做唯一的 key 用,又不用做复杂的扩展。

pbc 的 lua binding 库 中,对 fixed64 类型,我就是这样处理的。

今天遇到新的需求,有同学希望可以在项目中直接处理 64bit 的 timestamp 。这就需要对 int64 做数学运算了。

虽然最终我们去掉了这个需求(使用 32bit 的 timestamp ),但我还是忍不住去想,到底怎样在 lua 中支持 64bit 整数运算最好。

在 luajit 中,是定义了一个 userdata 并重载其运算符完成的。即,你可以用 ffi.cast("int64_t",0) 来构造一个 64bit 的 0 。

姑且不谈 userdata 的额外开销问题,这样做有一个问题就是当 64bit 的 cdata 做 table 的 key 的时候,相同值的 int64 并不是同一个 key 。

我觉得有一个更轻量的方式来解决 int64 支持的问题。那就是在 64 位平台上,我们完全可以用 lightuserdata 无损失的表示一个 int64 。

通过给 lightuserdata 设置 metatable ,我们可以接管它的数据运算。唯一不足的是,比较一个 int64 和普通的 lua number 是否相等时,lua 不能隐式的做转换。(而大于小于比较则没有问题)

我花了半小时实现了我的想法,放在了 github 上 ,有兴趣的同学可以拿去用。

这个库只提供了一个显式的 api ,即构造一个 int64 数字。可以从 lua number 构造,也支持从一个 8 字节宽的小头的字符串来构造。实际在内存储存的是一个 lightuserdata 即一个 64bit 指针(所以这个库不适用于 32 位平台)。你也可以通过 C 接口 lua_pushlightuserdata 来把一个 64bit 整数压入堆栈。

把 int64 转换为普通的 lua number 借用了 # 操作符。

希望这个小东西对你有帮助。

April 09, 2012

如何更准确的网络对时

这个周末 想到这个问题, 是由另一个问题引起的.

为了模拟复杂的网络环境,我们在内网安装了模拟环境

怪物公司同学周末调试客户端时,修改了自己机器的网关,增加了模拟延迟。奇怪的是,他的客户端在切换网关时并没有断开连接。可延迟也果真发生了。

我和他探讨了一下,觉得这个模拟延迟是单向的。当游戏服务器发送数据包回桌面时,由于服务器和他的桌面机在同一个网段,所以 IP 包被直接发回了。TCP 连接也不因为修改了过去的通路和断开。

当然,这种模拟并不是我们想要的。正确的方法应该是在修改网关(指向延迟模拟机器)的同时,也修改桌面机的 IP ,或是给自己机器绑定两个 IP ,使用模拟环境网段的 IP 来重新建立 TCP 连接。或者在模拟网关上做一次 NAT 。反正方法有很多,不展开讨论了。只有正确的模拟双向延迟(或网络颠簸)才好得到接近现实情况的场景。

不过这次错误,引出我另一个思考。如果 TCP 上行和下行延迟差距较大,有没有什么特别糟糕的事情发生呢?我的第一反应是,网络对时不准了。

我们的对时协议一般都遵从这样一个假定。我们的桌面机发送一个数据包到服务器所需要消耗的时间,大约等于服务器发一个数据包回桌面机的时间。这样,我们测试出一个数据包来回的时间,除 2 ,就得到了单程时间。这样就可以根据时间服务送来的服务器时间,把桌面时间和服务器时间基本校准了。

可一旦上下行速度不一致,甚至偏差较大时,这个假定被破坏掉了,时间也无法校准了。


有没有什么办法可以知道 A 点到 B 点的单程时间呢?如果只有 A 和 B 存在,似乎永远都无法测准。你很难知道 A 到 B 的开销是不是和 B 到 A 的开销相同。除非双程时间特别短(至少有一次特别快),误差就不会超过这个双程时间了。极端情况是,A 到 B 特别慢,而 B 到 A 是瞬间到达的。(有如我前面提到的情况,A 到 B 经过了一个故意的延迟,而 B 到 A 走了局域网的另一条路,瞬间抵达了)

我认为,如果能增加足够多的第三方路径,就能提高这个校对精度。

假定,我们有另外几台服务器,C D E 。A 向其发的包,它们都立刻把包转发到 B ; 反过来,B 发过来的包,也都立刻转到 A 。

那么,我们就可以制造出几条间接连接 A B 的不同路径。

我们假定,互联网上,两个 IP 间的通讯时间,双向延迟接近是常态,而时间不同是例外的话;就可以让对时包走不同的路径从 A 到 B ,可以推算出不同路径的单向时长(假定是双向时长的一半)。

估算出每条路径的延迟后,我们同时从 A 走不同的路径发送校时包到 B 。由于不同路径的延迟不同,B 会先后收到来源于 A 的包。如果认为前面假定成立,那么,相互比对,就可以除掉那些不稳定的路径,最终可以推算出 A 到 B 的直接连接路径上的单程时长了。


周末瞎想而已,不必当真 :)

April 06, 2012

Ringbuffer 范例

前段时间谈到了 ringbuffer 在网络通讯中的应用 。有不少朋友写 email 和我探讨其实现细节。

清明节放假,在家闲着无聊,就实现了一个试试。虽然写起来还是挺繁杂的,好在复杂度还在我的可控范围内,基本上也算是完成了。

设想这样一个需求:程序 bind 并listen 一个端口,然后需要处理连接到这个端口上的所有 TCP 连接。当每个连接上要数据过来时,收取这些数据,识别出封包,发送给对应的逻辑层处理。如果数据不完整,则暂时挂起这些数据,直到数据收取完整再行处理。

我写的这个小模块实现了这样一组特性,因为使用了唯一的 ringbuffer 缓存所有的连接,可以保证在程序运行过程中,完全没有额外的内存分配操作。

在编写时,一开始考虑到可能跨平台,想使用 libev, libuv, 或 libevent 来实现。可是仔细思考后,觉得这些库的 callback 模式简直是反人类,完全不符合自然的数据处理流程。使用起来体验非常糟糕。如果考虑到自己做 buffer 管理,想和它们原有的处理框架结合在一起,那实现过程绝对是一个噩梦。

在阅读 redis 的源代码过程中,我发现它并没有实现第三方的连接库,而是自己分别实现了 epoll kqueue select 的处理逻辑。简单清晰。而 epoll 这类 api 原本就相当的简洁,何苦去链接一个近万行的框架库把问题弄复杂呢?

所以,最终我自己定义了一组 API 接口完成需求:

struct mread_pool * mread_create(int port , int max , int buffer);
void mread_close(struct mread_pool *m);

int mread_poll(struct mread_pool *m , int timeout);
void * mread_pull(struct mread_pool *m , int size);
void mread_yield(struct mread_pool *m);
int mread_closed(struct mread_pool *m);
int mread_socket(struct mread_pool *m , int index);

暂时我不处理数据发送,让用户自己用系统的 send api 来完成,只关注 recv 的处理。这组 api 中,使用 create 来监听一个端口,设置最大同时连接处理数,以及希望分配的 buffer 大小就可以了。

库会为这个端口上接入的连接分配一个子连接号,而没有直接用系统的 socket 句柄。这可以方便应用层的处理。如果你设置了最大连接数为 1024, 那么这个库给你的编号就一定是 [0,1023] 。你可以直接开一个数组来做分发。

poll 函数可以返回当前可以接收的连接编号。可以设置 timeout ,所以有可能返回 -1 表示没有连接可读。

在 poll 之后,pull 函数可以用来收取当前激活的连接上的数据。你可以指定收多少字节。这个函数是原子的,要么返回你要的所有字节,要么一个字节都不给你。

由于库内部管理了接收 buffer ,所以不需要外部分配 buffer 传入。库的内部会识别,如果内部数据是连续的,那么直接返回内部指针;如果不连续,会在 ringbuffer 上重新开一个足够大的空间,拼接好数据返回。

buffer 的有效期一直会到下一次 poll 调用或是 yield 调用。

yield 函数可以帮助你正确的处理逻辑包。这是因为库还帮你做了一件事,如果你不调用 yield ,那么如果你 pull 了多少数据,再下一次 poll 调用后,同一个连接上,会重新 pull 到相同的数据。

举例说,如果你的逻辑包有两个字节的包头表示逻辑长度。你完全可以先 pull 两个字节,根据两个字节的内容做下一次 pull 调用。如果实际数据没有全部收到,你不必理会即可。如果手续收齐,那么调用一次 yield 通知库抛弃之前收取的数据即可。

当 pull 返回空指针,有可能是数据还没有收全,也有可能是连接断开。这时用 closed 这个 api 检测一下即可。


写了这么多,一定有同学想找我要源代码了。懒虫们,没问题。我已经提交到 github 上了。你可以从这里拿到 https://github.com/cloudwu/mread

不过,这个只是我的节日娱乐之作。没有经过仔细测试,用在生产环境请务必小心,它几乎是肯定有 bug 的。另外,我只实现了 epoll 的部分,虽然扩展到 kqueue 或是 select / iocp 并不会太困难,不过假日过完了,也没空完善它了。

我由衷的希望有同学有兴趣有能力可以帮我完善这个库,让它更具有实用价值。写 email 给我,我会尽量配合。


这个东西的特点是什么呢?

我相信它足够高效,至少从 api 设计上说,可以实现的很高效。

因为它几乎就是直接调用 epoll 这些系统 api 了。而且尽量少调用了系统 api 。从实现上,每次 pull 调用,库都尽量多的读取数据并缓存下来,而不是按用户需求去收数据。

空间占用上,它也一点都不浪费,不会为每个独立的连接单独分配缓存。你大概可以根据你的网卡吞吐量和应用程序能处理的带宽,估算出一个合理的 ringbuffer 总量,那么这个库就应该可以正常工作。

就上一篇谈 ringbuffer 的 blog 我说过,当 ringbuffer 用满,它仅需要踢掉最早残留在系统里的挂起的连接。如果 client 是友好的(不发半个逻辑包),它几乎不会被踢掉。

libevent 这类库设计了一个 callback 框架,让你在每个连接可读时,采用 callback 函数来处理即将收到的数据。和这种用法相比,这个库的处理逻辑更加自然,也不需要你定制这定制那。复杂度被藏在里模块内部。外部接口和 socket api 一样简单易用,甚至更易用。因为它可以帮你保证逻辑包的原子性。