« January 2014 | Main | March 2014 »

February 15, 2014

一起 select 引起的崩溃

2 月 13 日,陌陌争霸 计划在下午 16:00 例行维护,之前已经稳定运行了很长时间了。没想到在 14:30 左右,有一台从机意外崩溃。再次之前,从机崩溃并不会引起系统坏死,只需要新启动一台从机即可。但这次似乎不一样,所有玩家均不能登陆游戏,不得已,提前进行了长达两小时的紧急维护(将例行维护的工作合并)。

这次从机崩溃进行的大规模事故,可简单描述为:当从机上 5K 玩家掉线后,引起这批用户立刻连接其它从机。而事故发生后另一个小 bug 导致没有及时从系统中把这批用户重置,导致这批用户不可能立刻重新进入系统,反复重试。而每台从机上的网关配置最大连接数过小,导致他们阻塞了其他用户的登陆。

维护后修正了后面几个问题,由于时间紧迫,没有细查崩溃的直接原因。(另一个小插曲是,core 文件被输出到一个容量很小的分区,分区容量不足,导致 core 文件被截断,增加了分析难度。)系统重开后,不到半小时又有一台从机崩溃,这次没有产生雪崩,立刻启用了备用机替换。可在 5 分钟后,新的一起崩溃事件在另一台从机上发生。这使我们意识到问题的严重性。

由于后来的崩溃拿到了完整的 core 文件,可以看到 C 层的崩溃发生在游戏服务器和我们的运营平台服务器(分属两个机房)的对接环节。由于机房间网络状态不稳定,发生了一次重连操作,再重新建立连接时,程序出错。但是程序调用栈已经被部分破坏。同时,错误 log 中有大量玩家领奖品失败的记录 。最快速的判断是,两者有一定的相关性。我们已经两个月没有修改 C 代码了,之前一直很稳定,过年期间无人守护都没有发生这种严重的事故,所以很难理解 bug 的成因。最近只在 lua 曾增加了一些业务逻辑,比如一些奖品发放。不太能确定到底是何为因何为果。

到了 13 日晚饭时间,依然没有头绪。为了减少晚上再次崩溃的可能,我决定关闭奖品领取模块,再慢慢追查 bug 。


core 文件中的调用栈破坏使得从现场做分析变得有些困难。所以按一般的 bug 追查策略,我们推测是由于这次发奖的某种流程导致的问题。结合三次崩溃的现象,大致认为是某个玩家领取奖励触发了某个很难测试到的分支。花了一点时间在三次崩溃前 20 分钟的 log 中获得了几万个玩家的 id 。放在一起比对,只有一个玩家恰好出现在三个名单中。

但事后表明,这个玩家的出现时间完全是巧合而已。我们没有从这个玩家的信息中获得线索。但三次崩溃都出现在游戏服务器和运营平台对接重连中,这使得这部分相关代码变得最为可疑。

写这块代码的蜗牛同学正在马来西亚度婚假,所以就不打搅他了。13 日晚上,我阅读了所有我们编写的平台对接代码,没有找到问题。弄得这一整晚,晓靖和我都非常不爽。

14 日,我改去查蜗牛用到的 rabbitmq 的 C 库 ,初看下来也没啥问题。

在毫无线索的情况下,只好开始在 core 文件中重新寻找蛛丝马迹。把未损坏的堆栈数据和反编译的代码逐个比对。发现在 amqp_open_socket_noblock 函数中 portnumber 这个局部数组全部为 0 ,但 sockfd 却不是 -1 。这说明 socket 被创建后,portnumber 数组却被覆盖掉了。

再仔细阅读才发现,原来是 rabbitmq-c 为了控制 connect 的超时时间,使用了非阻塞 connect ,然后使用 select 判断 fd 是否可写来判定连接是否建立。 select 调用未考虑 sockfd 大于 FD_SETSIZE 。linux 的 select 手册中有这样一行注释:

Anfd_set is a fixed size buffer. Executing FD_CLR() or FD_SET() with a value of fd that is negative or is equal to or larger than FD_SETSIZE will result in undefined behavior. Moreover, POSIX requires fd to be a valid file descriptor.

这是一个很容易被程序员忽视的坑。FD_SET 其实是一个位数组,linux 默认是 1024 bit 。而 FD_SET 只是简单的把 fd 当作一个序号按位向位数组写数据。select 应该也是如此。所以当 fd 大于 1024 时,就会写越界。正确的方法是当需要 select 的 fd 大于等于 1024 时,最好在堆上分配 FD_SET ,分配空间应至少保证 fd/8 + 1 以上;或者用 poll / WSAPoll 更好。

一般的程序不会有这个问题是因为通常一个进程需要的文件 fd 不会超过 1024 。而我们的系统管理了大量的外部连接,超过 1024 轻而易举。之前,机房间的网络正常,只在程序启动时创建连接一次连接。这时尚无外部连接,这个连接的 fd 一定是小于 1024 的,而之后也不会发生重连。


btw, 当我想去提一个 Issue 时,发现刚好是 2 天前已经有人提了

February 10, 2014

如何让玩家相信游戏是公平的

去赌场参观过的同学应该都见过那种押大小的骰子游戏。庄家投掷三枚骰子,把骰盅盖住,玩家可以押大或小。开盅后,如果发现三个数字之和大于等于 11 就算大,小于等于 10 就算小。如果你猜对了,庄家就 1 赔 1 算给你筹码;否则输掉筹码。另外,还可以以不同赔率压数字,或压三个相同。

为了保障庄家利益,三个相同的数字算不大不小。从概率上讲,这让长时间内庄家必胜。概率分析见这里

如果把这个游戏搬到网络上如何呢?(注意:网上赌博在很多国家是被禁止的,这里只做技术分析而已)

如何让玩家相信庄家没有作弊,真的产生了随机的骰子呢?

记得网易泡泡曾经在聊天室中做过一个简单的赌大小的文字游戏。我一同学兴致勃勃的玩过,他告诉我系统一定作弊过的。他写了个程序监控每局游戏开盅前的下注情况,到最后一秒再下住,永远下注少的一边(也就是跟庄),只花了一天时间就刷了无数泡泡币。

其实这只是游戏实现者的贪心和无知而已。其实这个游戏的规则保证了庄家利益,庄家没有必要作弊。但有些游戏设计者就是脑子转不过弯来,的确考虑过作弊。不是连六合彩这种极大化庄家利益的游戏规则都有流言暴出庄家作弊么?

那么,是不是网络版的赌大小一定得不到玩家信任呢?

其实有一个简单的方法可以向玩家证明骰子的随机性:

  1. 每局游戏前,先随机三个 1-6 的数字,并同时生成三个足够长(比如 80 字符, 长度在屏幕方便显示的范围即可)的文本随机串,把数字附在随机串的两端。比如随机出 2,4,5 这三个数字,就同时生成形如 2xxxxxxxxxxxxxxx2 , 4xxxxxxxxxxxxxxx4, 5xxxxxxxxxxxxxxx5 (xxxx 每次随机) 的字符串。计算这三个字符串的 md5 值,并事先通过网络展示给玩家。

  2. 玩家收到三个秘密串后开始下注。下注时间有限,只有几分钟的时间。由于 md5 的不可逆性,在这么短时间内,不可能知道串的原文。注:网络上所谓的 md5 破解,都是基于收集有意义的字符串的 md5 值构成海量的数据库比对查找的,并非对 md5 结果做逆运算。纯随机串的 md5 值不可能在很短时间求逆。

  3. 下注时间过了后,系统通过网络公布事先的三个随机数字构成的随机串,也就相当于开盅。这时候,玩家应该认赌服输了。如果他认为系统作弊,可以自行校验系统公布的串的 md5 值是否和事先公开的值相等。

如此便可证明,骰子是在玩家下注前就确定下来的,而不是根据玩家下注的行为更改让庄家获利。

没错,现在有数学证明可以在有限时间构造出另一个符合规则的串有相同的 md5 值。但那也需要相当的计算能力。如果这个网上赌场开的时间足够长,是没有那么多计算能力支撑长期的作弊的。之所以不必选用可能更安全的同类算法,是因为 md5 的普及率和认知程度最高,计算工具也随手可得而已。

如果想进一步提高信任度,让玩家相信没有提前计算出 md5 碰撞值,可以在随机的 xxxxx 中进一步加上上一局游戏的骰子 md5 值,让每次随机量都是和上一次相关的。甚至可以加上上一局游戏参与玩家的赌注金额。这样几乎不可能提交计算某一次游戏的随机串的 md5 碰撞。

关于 MD5 的碰撞构造,多个 md5 chunk 比单个 chunk 要容易的多。单 chunk 的碰撞构造在 2012 年的这篇 paper Single-block collision attack on MD5 中提到的方法的计算复杂度在 2 的 50 次方 MD5 运算量级。不是现在普通的计算机计算能力所能承受的。

虽然不是所有玩家都可以理解这个规则,但规则容易直接在游戏中公示。服务器记录所有历史的数据供玩家备查。还是很容易取得玩家群体的信任的。

February 08, 2014

在移动网络上创建更稳定的连接

我们的手机游戏发布有一段时间了。立项之前我写的一篇 blog , 在移动设备上开发游戏需要克服的两大技术难点: 移动网络的不稳定性以及手机硬件资源的约束。由于开发时间所限,第一点我们并没有专门去做。

我一直不想动手去做一个临时方案解决 TCP 断线重连问题,因为实现一个 TCP over TCP 是没有太大意义的。移动网络发展迅速的今天,整个行业都在努力提高移动网络的稳定性,所以费力做这个事情很可能在两年之后就变得完全没有必要。

比如,iOS 7.0 发布 后,让 MultiPath TCP 技术为更多人所知。从许多中文资料对其的解读,主要集中在 MPTCP 提供了更大的带宽上;甚至一些网络喷子借机来喷国内的 3G 收费高的问题,认为同时利用 3G 网络和 wifi 下载没有意义。但我认为其对于移动网络的真正意义在于提供一个更加稳定的连接。

顾名思义,MPTCP 允许在同一 TCP 连接的通讯两端建立多条通讯路径,如这篇文章 所言:Just like IP can hide routing changes, MPTCP can hide the details of which paths it is using at any given time.

这两天,我们在自己的服务器上安装了支持 MPTCP 的新内核做了测试。发现:如有可能,设备会为新的 IP 地址建立新的通讯路径。如果连接两端各有两个 IP ,那么在初始的 TCP 连接建立后,通过协商,最终会建立 4 条 TCP 连接出来,交叉连接了所有的 IP 。任何一条通路有效都不影响通讯。btw, 如果你的机房有网通,电信两个 IP 的话,如果客户端设备支持 MPTCP ,那么会自动同时使用两个通路同时维持一个逻辑上的连接。这对国内的网络环境非常有利,不需要使用 bgp 机房,也不需要在多线机房配置复杂的 DNS 了。

当你的手机从 3G 网络切换到新的 wifi 热点时,设备会自动利用新的 wifi 网络做数据传输;离开 wifi 热点后,又能无缝切换回 3G ;再次进入新的 wifi 热点范围,还可以重新利用新的 wifi 网络。这样,移动设备可以穿梭于多个网络之间而永不断开连接。

可惜的是,Apple 目前并没有完全开放 MPTCP 给应用层使用。经我的测试,只有 Siri 的连接才会发送 MPTCP 握手协商。这篇 blog 也证实了这一点

ps. 经过这两天的测试,还发现 MPTCP 似乎只能利用第一次连接的通路做控制信息交换。当第一次连接的 IP 实效后,不能把后来的通路提升为主控连接。所以 MPTCP 看起来不能在只有一个网络设备上正常工作。(我原先预期它可以在同一个设备上切换 IP 还可以正常建立新的子流,看来是搞错了)


借着阅读 MPTCP 的协议文档,我也想了许多。我觉得在现阶段在应用层上实现一个更稳定的 TCP 连接也是可行的。但协议设计要考虑的很多,下面记录一下我的设计方案:

我希望针对游戏服务器的特性,实现一个不对称的连接协议。即,只能由客户端发起连接,而发起连接的一方无法主动断开连接。服务器只接受连接,有权利断开连接。

这个协议基于已有的 TCP 协议,通讯是基于带长度信息的包构成。客户端到服务器的前两个包为握手包,服务器只用回应第一个握手包,客户端发送的第二个握手包用于校验,当服务器不认可握手过程,可直接断开连接。

连接建立过程如下:

.1. 客户端向服务器发起一个 TCP 连接,并发送第一个握手信号:包含一个 0 和按 Diffie-Hellman 密钥交换算法产生一串随机量 A 。

.2. 服务器收到第一个握手信号后,检查第一个字段,若不为 0 则进入连接修复阶段 2.2,否则继续创建连接过程 2.1。

.2.1 此时服务器生成另一个随机串 B ,并通过 DH 密钥交换算法得到了一个 secret 。此时回应 DH 算法需要的 B ,以及一个新的随机串 E (用于校验)。

.2.2 当第一个字段不为 0 则认为是需要修复一个已有连接,这个数字表示在旧连接上客户端已收到过服务器发过来的数据包数量。此时,第二个字段应理解为旧连接上已收到数据包的指纹。服务器根据包数量和指纹可以核对所有保持的有效连接,如果不能找到匹配的连接(指纹相同),就断开客户端。否则回应客户端在旧连接上一共收到客户端发送的数据包数量,以及一个新的随机串 E ,用于确认客户端是否知道旧连接的 secret 。(这个校验是有必要的,否则会有人监听到链接重建过程,而重复发送这个握手包来踢掉合法用户刚修复的连接)

.3. 客户端收到随机串 E 后,和 secret 连接在一起做一次 hash (可以使用 md5 算法) H,回应服务器。这可以让服务器校验客户端是否真的拥有 secret 。

.4. 服务器收到二次握手信号 H 后,用同样的 hash 算法做一次 secret 校验,确认是合法的客户端后继续通讯;若是非法连接则立即断开。

.5.1 如果是新连接,那么服务器利用得到的 secret 初始化 RC4 加密算法需要的 s-box ,之后的通讯利用 RC4 算法加密。

.5.2 如果是旧连接修复,那么服务器将客户端未收到的数据包重发一次。并从旧通道上复制 RC4 所用的 s-box 以及 secret 用于后续通讯。

.6. 此后的每次数据通讯,在数据打包后,都利用 RC4 算法做一次加密,并利用数据更新数据指纹(可以用加密后的数据流的 CRC 值)。每个数据包都记录当前的指纹,并 cache 最近发送的 128 个数据包用于事后的连接修复。

.7. 设定一个超时时间,定期清理没有数据来往的 TCP 连接。

这个协议的好处是,客户端在握手完成后,任何时间都可以向服务器发起一个新的 TCP 连接取代旧的连接(无须利用旧连接是否还有效),而对应用层来说,连接重来没有中断过。

应用层可以做一些配合工作:比如设计一分钟一次的心跳,如果长时间没有收到心跳包,就主动发起新的 TCP 连接去取代旧的。这对无线网络能增加网络的稳定性。比如你切换 wifi 网络时,由于 IP 地址的变化, TCP 连接不可能保持,但这套协议可以帮助你自动修复它。在没有 MPTCP 支持时,它还可以尽量去使用更高质量的网络(只要重新连接时去尝试新的网络设备即可)。


我计划在 skynet 中实现一个和网络 API 无关的 C 模块作为中间层来完成以上工作:

接口大约是这样:

struct socket_pool;

// when sz == 0 and buffer == NULL, fd is closed
// when sz > 0 and buffer != NULL, buffer is the data 
struct socket_package {
    int fd;
    int sz;
    const char * buffer;
};

struct socket_pool * socketpool_new();
void socketpool_release(struct socket_pool *sp);
void socketpool_timeout(struct socket_pool *sp);

void socketpool_pushinput(struct socket_pool *sp, int fd, const void * buffer, int sz);
void socketpool_pushoutput(struct socket_pool *sp, int id, const void * buffer, int sz);

int socketpool_popoutput(struct socket_pool *sp, struct socket_package *p);
int socketpool_popinput(struct socket_pool *sp, struct socket_package *p);

void socketpool_closefd(struct socket_pool *sp, int fd);
void socketpool_close(struct socket_pool *sp, int id);

fd 是底层的 socket handle ,id 是应用层的连接 id 。

当网络层有任一 fd 收到数据时,通过 pushinput 接口把数据推送到 socketpool 中。调用 popinput 会报告哪个 id 上有新的数据包(或是没有新的数据包)。

向一个 id 写数据只需要调用 pushoutput ,然后反复调用 popoutput 可以得到真正需要将哪些数据写入具体的 fd ,把它们交给网络层 API 发送即可。

如果有 fd 断开,或向主动关闭 id ,可以调用 closefd / close ;而 popoutput 则有可能收到一个 fd 关闭的信号,然后调用网络层 API 去对应的 fd 即可。

这个模块会处理数据打包加密,修复连接重新补发包等问题,并将这些隐藏在实现中。


2 月 14 日补充:

我实现了一个开源版本, API 有所不同。目前尚未仔细测试,有兴趣的同学可以一起来完善它。