« July 2017 | Main | September 2017 »

August 29, 2017

MMORPG 的同步设计

前段时间有一个友商来了一个技术团队到我公司交流,主要是想探讨一下他们即将上线的一款 MMORPG 游戏在内部测试中发现的网络卡顿问题是否有好的解决手段。

经过了解,卡顿主要是在压力测试中表现出的网络消息流量过大造成的,又没有找到合适的方案减少流量。

关于 MMORPG 的网络部分的设计,我之前写过很多 blog 。最近两年写过这样两篇:MMORPG 客户端的网络消息框架如何只基于请求回应模式实现 MMO 级别的场景服务

昨天,我们自己的一个 MMORPG 项目中发生一个小 bug ,就这个 bug 我们做了一些讨论。我想借这个问题展开,在一个抽象层面谈谈我觉得 MMORPG 的网络同步应该怎样做。

具体 bug 是这样的:

在客户端登录后,服务器会推送个玩家背包的信息,客户端应根据这些信息初始化背包对象。

在场景中的某些掉落品会自动进入玩家的背包,客户端会根据这类信息修改背包的状态。

一般情况下,推送玩家背包信息的网络包一定会先抵达。但是由于一些有关断线自动重连的设计,导致了后一种掉落品信息包抢先在了初始化过程之前。

固然,这个 bug 有简单的解决方案。比如在 UI 系统中 model 和 view 完全分离(我们现在的确是这样做的),而 model 应该先由默认值初始化,不必等待登录完成再触发背包的初始化流程。

但我认为,应该在一个更高的抽象层面来看待这个问题。


物品掉落自动进入背包这条消息是服务器推送过来的,但是这条推送到底意味着什么?

如果是一个银行的客户端。当你的账户下发生了转账行为,别人向你转了一笔钱,如果你刚刚查询过账户余额,那么转账信息抵达后,是否应该由客户端将转账事件中的金额和上次查询的余额合并,自动计算出新的余额?

通常银行客户端软件绝对不会这样做,只会提供一个余额查询的功能。用户收到转账信息后,会再次查询。

这个例子或许并不恰当,账户转账发生并不频繁,用户对余额的关心也没有太多的实时性需求。但是它可以说明一件事情:事件的发生、即使事件会导致状态的变化是双方的共有知识、它和状态的变化本质上还是两件事。

对于网络游戏来说,玩家需要了解虚拟世界中发生的事件,也需要了解和他相关的对象的当前状态,这其实是两个不同的需求。


固然,如果依靠一些预先设计好的规则,客户端和服务器可以达成共识,根据虚拟世界中发生的事件,以及对象的初始状态,就可以同步对象的当前状态。很多网络游戏都基于这个方法设计,但我们应该认清本质:事件传达和状态同步是两件事,之所以选择这样的做法,其实是一种优化手段。因为我们只需要传达事件,省去了状态同步的网络流量。这个方法能成立,基于的是事先部署好的规则共识,以及事件的完整性。

MMORPG 类型的游戏的不同点在于,MMO 的世界很大,几乎不可能做全状态同步,也不可能传达世界中的所有事件。每个客户端都只关心整个世界的极小部分。所以 MMORPG 的设计中,几乎不会采用完全的初始状态 + 所有事件 的方法来同步世界状态。

也就是一部分事件仅仅只用来传达字面的意义,比如“ A 用 X 技能攻击了 B 造成了 Y 点伤害” 这种消息,可能仅用来做视觉表现以及文字 log 在屏幕上传达给玩家,而不会真的和服务器一样执行完全一样的逻辑(在 MOBA 类游戏中,参与人数较少,则可能采用完全逻辑去计算)。比如这个 X 技能导致 B 不能移动,很可能是单独的消息通知的,这样可以避免服务器和客户端由于了解的信息不对等而产生差异。

很多设计者对 “事件通知” 和 “状态同步” 这两个问题认识模糊,导致设计上含混不清。有的地方利用 “事件通知” 去计算状态变化,有的地方又单独设计状态同步协议,是很多 bug 的根源。


我的观点是:应当把 事件通知状态同步 在设计层次严格分离。所有事件通知的网络包都是可以丢弃和乱序的,它仅作为客户端的视觉呈现使用;而状态同步则是应该根据客户端的实际需求来严格同步,客户端处于什么状况,需要关心哪些对象,多少对象,根据这些需要来同步 MMO 世界中的一个子集。这些需要同步的对象既包括玩家自身的数值、背包,也包括了玩家所处的场景,他附近的其他玩家和 NPC ,还可以包括聊天频道信息、任务、排行榜、拍卖行信息。

例如,玩家受伤(HP 减少),自动拾取物件,这些都是事件,如果客户端收到这些事件,可以做出对应的动画表现;而当前玩家的 HP ,背包里有些什么物品则属于状态同步管理的范畴。我们应该使用合适的同步策略来做。可以是客户端推断出状态会发生变化去查询一次和上个已知版本的差异,也可以是向服务器订阅对应的对象的状态差异变化,还可以是简单的请求对象的全量状态数据。采取何种同步方案就属于设计和优化细节了。


如果因为网络流量问题,我们需要做出限制的话,事件通知是可以按信息优先级丢弃或推迟送达的。怎样丢弃可以由设计人员判断信息丢失后会给玩家客户端的视觉表现造成怎样的影响。即使全部丢弃了,客户端也不应该出错,并保持基本可玩。

状态同步应该在一个更高的抽象层面设计实现。所谓同步,无非是将服务器上的一个数据结构复制到客户端。最粗笨的方法是客户端提起请求,服务器全量返回序列化后的数据结构。最早期的 web 服务都是这样做的,相当于玩家不断的在一个他关心的页面按 F5 刷新页面。在这个基础上,优化是必须做的。

我们有很多方法来做差异更新,我在 “如何只基于请求回应模式实现 MMO 级别的场景服务” 一文中提出过我的方案。这未必是唯一的方法。不依赖客户端请求,服务器直接推送差异也是 MMORPG 用的比较多的方法。我认为这些都是针对状态同步的具体优化,可以结合具体情况具体考量。基于客户端请求和服务器直接推送的区别仅在于:基于客户端请求需要消耗更多的客户端上行流量、而服务器直接推送则需要消耗服务器额外的开销去维护客户端到底需要同步哪些信息。至于同步延迟的问题,两者没有什么区别。因为即使是基于客户端请求,也可以提前发起请求,只在状态变化的时候服务器再回应;而不必等到客户端需要时再请求状态差异。

例如大多数 MMORPG 服务器都会在服务器计算玩家周围的对象,并在周围对象移动时推送这些移动信息。我个人认为在流量有限的时候,在场景中树立若干灯塔,灯塔管理灯塔范围内的玩家 id,再由客户端主动查询灯塔要好一些。可以避免服务器在计算每个玩家周围的对象时陷入一个 O(n^2) 的复杂度,也能回避无脑推送巨量的消息。玩家可以跟踪一个灯塔的状态,然后再根据一个玩家列表,进一步选择同步有限几个玩家的坐标(不同设备和不同网络条件下能同时观测的对象数量是不同的)。这样可以更加有效。

回到文初的 bug 。由于断线重连问题导致物品掉落自动拾取和背包初始化乱序的问题。那个自动拾取的消息推送就只会显示一段拾取动画、在屏幕上显示一行 log 文字,最多触发一次背包状态更新的查询,而不会去操作一个未初始化的背包对象了。

August 16, 2017

Lua 5.3.4 的一个 bug

昨天我们一个项目发现了一处死循环的 bug ,经过一整晚的排查,终于确认是 lua 5.3.4 的问题。

起因是最近项目中接入了我前段时间写的一个库,用来给客户端加载大量配置表格数据 。它的原理是将数据表先转换为 C 结构,放在一块连续内存里。在运行时,可以根据需要提取出其中用到的部分加载都虚拟机中。这样做可以极大的提高加载速度。项目在用的时候还做了一点点小修改,把数据表都设置成 weaktable ,可以让暂时不用的数据项可以回收掉。

正式后面这个小修改触发了 bug 。

排除掉是我这个库引起的 bug 后,我们把注意力集中在 lua 的实现上。

bug 的现象是:运行一段时间后,某次 table copy 的过程中,对一个 table 的 set 操作陷入了死循环。我们知道 lua 的 table 中有一个闭散列 hash 表,如果在插入新项目时,发现 hash 冲突,则需要重新找到一个空的 slot 并将其串在 hash 查询时所在的 slot 上的链表中。

而 bug 发生时,这个链表损坏了,指向了一个空 slot ,空 slot 的 next 指针指向自己,导致死循环遍历。

从 coredump 上分析,我认为是 hash 查询出来的冲突对象(一个 long string )的数据结构受损。原本在 long string 结构中有一个 extra 变量指示这个对象是否有计算过 hash ,它的值只能是 0 或 1 ,但这里却是 67 。而 hash 值则为 0 (通常 hash 值是 0 的概率非常小),导致重新索引 hash slot 时指向了 slot 0 ,那里是空的。

我们自定义了 lua 的分配器,在分配器中输出 log 显示,在访问这个 slot 前,那个受损的 long string key 对象其实已经被 lua vm 释放过了。


一开始我们怀疑是自定义的内存分配器有 bug ,但很快放弃了这个想法,转而去追查 lua 的 gc 过程。这个 table 是 key value 都是弱的弱表,若只设置 value 为弱则不会触发 bug 。

确认问题出在清除弱表项的环节,也就是 lgc.c 中的 GCSatomic 阶段的 atomic 函数中。它有一个步骤是调用 clearkeys(g, g->allweak, NULL); 清除在扫描过程标记出来的弱表,并检查 key 是否需要清除。

该函数是这样的:


/*
** clear entries with unmarked keys from all weaktables in list 'l' up
** to element 'f'
*/
static void clearkeys (global_State *g, GCObject *l, GCObject *f) {
  for (; l != f; l = gco2t(l)->gclist) {
    Table *h = gco2t(l);
    Node *n, *limit = gnodelast(h);
    for (n = gnode(h, 0); n < limit; n++) {
      if (!ttisnil(gval(n)) && (iscleared(g, gkey(n)))) {
        setnilvalue(gval(n));  /* remove value ... */
        removeentry(n);  /* and remove entry from table */
      }
    }
  }
}

遍历 hash 表,当 value 不为空,且 key 可以被清除的时候,将 slot 清空。

string 对于 gc 是一个特殊的对象,因为它即是一个 GCObject ,但又被视为值而不是引用。string 并不会因为在 vm 中没有 weak table 之外的地方引用而被清除。对 string 的特殊处理是在 iscleared 函数中完成的。

/*
** tells whether a key or value can be cleared from a weak
** table. Non-collectable objects are never removed from weak
** tables. Strings behave as 'values', so are never removed too. for
** other objects: if really collected, cannot keep them; for objects
** being finalized, keep them in keys, but not in values
*/
static int iscleared (global_State *g, const TValue *o) {
  if (!iscollectable(o)) return 0;
  else if (ttisstring(o)) {
    markobject(g, tsvalue(o));  /* strings are 'values', so are never weak */
    return 0;
  }
  else return iswhite(gcvalue(o));
}

如果发现 key 是一个 string 则会将其标黑。

但是在 clearkeys 里漏掉了一点,如果 value 为 nil 是不会执行 iscleared 函数的。而什么时候 key 为 string , value 为 nil 呢?最简单的途径是主动给 table 的表项设置为 nil 。这样,在 gc 一轮后,hash 表中就可能残留一个已经被释放的 GCObject 指针。

如果这个 string 是一个短 string 其实不会引起问题,因为再次设置 hash 表的时候,short string 是按指针比较的,不会访问其内容;但是 long string 不一样,hash set 时真的会比较对象的内容:两个 long string 是否相等取决于 string 的值相同,而不必是对象内存地址相同。


制作一个纯 lua 的 MWE 很困难,所以我写了一段 C 代码来演示这个问题:

#include <lua.h>
#include <lauxlib.h>
#include <lualib.h>
#include <stdlib.h>
#include <lstring.h>

static void *
l_alloc (void *ud, void *ptr, size_t osize, size_t nsize) {
    if (nsize == 0) {
        printf("free %p\n", ptr);
        free(ptr);
        return NULL;
    } else {
        return realloc(ptr, nsize);
    }
}

static int
lpointer(lua_State *L) {
    const char * str = luaL_checkstring(L, 1);
    const TString *ts = (const TString *)str - 1;
    lua_pushlightuserdata(L, (void *)ts);
    return 1;
}

const char *source = "\n\
local a = setmetatable({} , { __mode = 'kv' })\n\
a['ABCDEFGHIJKLMNOPQRSTUVWXYZ' .. 'abcdefghijklmnopqrstuvwxyz' ] = {}\n\
print(pointer((next(a))))\n\
a[next(a)] = nil\n\
collectgarbage 'collect'\n\
local key = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' .. 'abcdefghijklmnopqrstuvwxyz'\n\
print(pointer(key))\n\
a[key] = {}\n\
print(pointer((next(a))))\n\
";

int main() {
    lua_State *L = lua_newstate (l_alloc, NULL);
    luaL_openlibs(L);
    lua_pushcfunction(L, lpointer);
    lua_setglobal(L, "pointer");
    luaL_dostring(L, source);

    return 0;
}

运行输出:

...
userdata: 00000000006fedd0     这里是ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
free 00000000006FAB50     这里进入 GC 开始释放不用的对象
free 00000000006FA890
free 00000000006FE940
free 00000000006FE910
free 0000000000000000
free 00000000006FA650
free 00000000006FEDD0      这里显示前面那个长字符串 6FEDD0 已经释放了。
free 00000000006FEBC0
free 0000000000000000
free 00000000006FAA50
free 00000000006F9770
userdata: 00000000006f1eb0   这里构造了一个新的字符串
 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
userdata: 00000000006fedd0   这里显示前面那个已经被释放的 6FEDD0  字符串又回来了。

这个 bug 最简单的修改方法是把 clearkeys 中的 !ttisnil(gval(n)) 条件判断去掉。不过或许还有更完善的解决方案。

我已经将 bug report 到 lua 的邮件列表,暂时尚未被官方确认修正。


8 月 24 日:

官方已确认这个 bug ,见邮件列表

August 11, 2017

基于办公的 IM 的基础设计

现在的 IM 在设计上是基于会话的,多个人可以组成一个会话,相当于一个聊天室,当一个人加入到一个会话后,就可以看到从加入开始之后这个聊天室里所有参与人的发言。有的 IM 会把两人对话也抽象成同一个东西,也可能出于优化的考虑把双人对话特殊处理。

所以,这些 IM 在操作界面上会有一个会话列表:表现出来会是联系人名单、聊天群列表等等。选中会话列表中的项目,进入会话查看聊天记录、发言,就是这类 IM 的使用逻辑。

我认为,这种对即时通讯的抽象方式,其实是不适合办公环境的。和日常个人社交环境不同,办公群体其实是一个相对关系密切的团体,我们通常不会拉黑一个同事不让他给你发消息,也不会拒收公司发的通告,也不会因为一个同事平常不和你打交道就拒绝建立联系。项目组里的讨论,也未见得是多么保密的事情,需要防止隔壁组的同事旁听。你也很少会在办公 IM 上和妹子私聊谈人生理想。

我们这几年使用腾讯的 RTX 作为公司办公使用,我就感受到了太多这类设计缺陷。比如,有同事找我有事,我忽略了他的私聊信息;找人一般在对方活跃的项目群组里吼;程序群沦为了日常扯淡的位置,常常同时讨论着不同的问题,线索及其混乱。“群”这个设计,我在很多年前就思考过 ,我一直觉得需要在根本上换个角度看待社交聊天的需求。

我现在的想法是这样的:

作为办公 IM ,我们不应该基于固定会话(群)来设计,而应该是“通知”和“话题”。

所谓通知,就是有人发起了一条消息,他需要把这条消息传达给某些对象,对象可以是人,也可以是某个组织:比如程序、游戏项目组、等等。

组织并非是群那样的聊天室,而仅仅是一个标签,由人来关注标签,而不是去组织这个聊天室里有多少听众。

而话题,则是由消息或旧话题衍生而来。任何通知消息、话题内部消息,都可以变成一个新话题。话题也可以包含在一则消息里转发给某个对象。

用户的客户端应该把所有的通知按时间线排列在一起,呈现在同一个地方。也就是说,无论是谁给我发消息(默认就是通知)都应该投递在一起,而不是像现在 RTX 那样只是在系统托盘里闪烁提醒、也不是微信 qq 那样,联系人名单上多出一个小红点。

而一旦我回复一个通知消息,其实就把这则通知转化成了一个话题,在时间线上,话题内的消息是归属在一起的。同一时刻,无论你的思维切换多么快,其实在短时间内你只能聚焦在一个话题上,所以客户端界面是很容易表达的,把当前话题展开在主界面(通知的时间线)即可,切换话题后自然可以折叠起来。

话题并不是聊天室、它更像是论坛的帖子。一个话题可以有很多人参与(至少发言一次),更应该支持更多的人浏览。我们不应该按聊天室的思路:用户只有在加入聊天室的那一刻开始,才能收到后续的消息,而应该像论坛那样,他只是打开了这个话题帖,可以随时聊天过去到现在发生的事情。话题内的任何一个消息,都可以由用户展开为新话题,老话题对新话题只是一个引用链接而已,并不需要有层级关系,我们也可以把任意一个话题或尚未转化为话题的消息转发出去,如果有人对他评论,就生成了新话题。

话题是一个有时效性的东西,对于办公来说,如果一个话题超过 8 小时没有新的消息,就可以认为这个话题已经结束了。但是事后我们依然可以对老话题浏览,或是继续讨论,而继续讨论就是生成的一个新话题了。

只要生成话题足够方便,每个用户的主时间线上就只会有不多的通知消息,信息传达更为有效。而管理每天的消息、检索旧消息也有很强的时间线。不像现有的 IM 群聊天,每天的聊天内容会被自然的组织成话题,这些话题上标识了参与人数、归属的组织的 tag 、继承于哪个父话题或通知、经历的时间段、衍生出哪些后续话题,等等。

即使是两个人之间的对话,也同样应该是话题的形式,而不应该把消息直接组织成一长串的聊天历史。话题未必有明确的主题,只是一种更自然的信息聚合形式而已。

对于办公场合来说,有意个最重要的优势:用户群有足够的自律。基于这种自律,我认为上面的思路若实现出来很容易推广使用。

在自律之外,或许还需要一些权限管理。这些权限管理应该是相对松散简单的,主要是限制用户订阅特定组织的 tag (比如一般员工不能订阅管理层的 tag ),限制围观特定话题(比如两人之间的私聊话题默认就是不对第三人开放权限的),话题可以锁定不准转发。权限设置的细节还需要进一步推敲。