云风的 BLOG

最近想做一个游戏服务器和 IM 互通的服务。最初的想法是可以增进游戏帐号的安全，比如游戏用户可以通过绑定一个 IM 帐号，从而不用登陆游戏就向游戏服务器发一些指令。这些指定通常是用来冻结一些帐号的功能。而游戏服务器也可以通过 IM 帐号向离线用户发送一些关键消息。这样，只需要解除绑定 IM 帐号需要一定的时间，或使用更安全的途径，即可以让游戏帐号更加安全。（至少，游戏用户可以从 IM 上获知他的游戏帐号每次登陆登出的时间、IP 等等）

后来细想，这里面可以做的东西还有许多。玩家会因为多一个信息通道，而更轻松的去玩那些需要长期驻留的游戏。游戏厂商也可以多一个挽留玩家的渠道，甚至用来宣传新游戏或游戏的增值服务，等等。好处不再列举。

其实、绑定 IM 帐号和绑定手机号本质上区别不大。只不过，IM 帐号几乎是零费用，又不像 SMS ，控制权掌控在移动手里。IM 更适合做双向交流（SMS 的双向交流不那么方便，而且对用户和游戏运营商都有经济负担）。独立提供一个 Game2IM 的服务供众多游戏运营商使用也是个有趣的主意。和 SMS 一样，只要给出一个简单接口让游戏运营商调用，把游戏网络和 IM 网络互联就可以了。

实现这个想法有两个方案。其一是制作各种 IM 的机器人，通过机器人和用户 IM 沟通。这个方案技术门槛稍低，有许多现成的机器人可以使用。缺点是，受 IM 提供商的限制（比如好友数量限制）。无法使用机器人的签名针对性的向用户传递特有的消息。除非你为每个游戏用户定制一个机器人，但那样，每个机器人都需要单独一个连接，对资源消耗过大。

第二个方案就是使用已有的 IM 互通方案，自己提供一个特有的 Game-IM 网络，跟已有的 IM 网络互通。比较流行的 IM 互通协议用基于 SIP 的 SIMPLE 和起源于 Jabber 的 XMPP 。

我最常用的 IM 是 google talk ，本身就实现了标准的 XMPP Client 和 XMPP Server 协议；而我们的 网易 popo 也实现了 XMPP 的 s2s 网关。我想研究一下 XMPP 是个不错的选择。

花了一整天的时间，把 XMPP 核心协议 仔细通读了一遍，收获颇多。原来以为 XMPP 是个可怕的巨无霸。我对 XML 原本也没有太多好感。最后，看法有所改变。

其实，XMPP 仅仅是定义了一个网络服务间相互通讯的协议。它已经把服务间需要关心的东西减少到了最少。具体的应用每家服务提供商可以随意扩展。popo 在制作新版本时，我曾多次建议采用已有的标准协议，再此基础上开发自己的东西。当时或许大家都认为标准协议容易促手促脚，我当时也没啥研究，没有多言。今天看来，我更觉得这是一个决策失误。本来我们有一个很好的机会，利用 popo 联系起网易的各种服务，现在这条路将走的更为艰辛。其实，XMPP 定义的东西，即使自己去设计也会定义出类似的一套来。而把各种网络服务互通本该是发展的重点，为 IM Client 增添专有花哨的特性就有些舍本逐末了。更为恼火的是，popo 到现在也没有一个很好的非 Windows 平台解决方案。怎能让诸多把握着互联网上部分话语权的技术人士接受？（或者，同在杭州的 IT 圈子，popo 的开发人员是不是应该看看支付宝的同行们做了些什么？）

谈谈我对 XMPP 的粗浅理解。这些仅仅建立在我对 RFC3920 的一天阅读的基础上，难免会有错误，不足以做技术参考。

XMPP 抽象出一个在互联网上唯一的对象实体，用 JID 来表达。通常一个 JID 由三部分组成，node@domain/resource 。比 email 的表达形式多了一个 /resource 。这是因为 email 地址本身虽然可以表达一个实体，都是往往不够表达这个实体下的具体服务。就好比一个 ip 地址可以表示一台机器，但是我们还需要 port 号来表达这台机器具体提供的服务一样。

用过 gtalk 的人应该很喜欢 gtalk 可以在不同的地方同时登陆这个不错的特性。用过以后，才能体会，无论是 qq 还是 msn 还是 popo ，只允许一个登陆是多么愚蠢的设定。gtalk 其实遵守了标准的 XMPP 协议，它用来区别一个帐号（一般是一个 gmail 邮件地址）的多处登陆，正是利用了不同的 resource 标识。

XMPP 规范的最重要的一条通信协议就是，如何把消息从一个 JID 发送到另一个 JID (message)。这有点像 email 协议，但不同的是，它强调了实时性和安全性（虽然不是必须的）。因为 JID 可以在不同的 domain 下，这就需要 domain 间相互协作。对于 IM 网络来说（XMPP 远不只用于 IM 协议），就是不同的 IM 服务间互通。

对于 domain 下的 xmpp 服务的发现，利用了 DNS 协议的一些功能。xmpp 的 s2s 服务提供位置，放在了 DNS 的 SRV 记录里。你可以用 nslookup 做个试验，启动 nslookup ，输入 set type=SRV

然后查询 _xmpp-server._tcp.gmail.com 你会发现 gmail.com 的 xmpp s2s 服务地址已经端口号 5269 。同样，也可以查询 _xmpp-server._tcp.163.com 或 _xmpp-server._tcp.popo.163.com 查到网易 popo 的 xmpp 中转服务器地址。

btw, 查询 _xmpp-client._tcp.gmail.com 可以查到 gtalk 的 client 登陆地址，而网易 popo 则没有提供 xmpp client 登陆点。

按 RFC3920 所述，在 xmpp server 互联的时候，会优先尝试获取 domain 的 SRV 记录，如果失败就直接去连默认的 6259 端口。然后就可以开始握手协议。

xmpp 比较强调 s2s 的安全性，所以推荐的握手都是建立在 TLS 层之上，使用 SASL 认证。TLS 层需要服务器有一个数字证书，为了安全可信，建议是找个根证书签名。不过自己签名也行，只需要服务器缓存证书即可。握手过程在 RFC3920 中描述的非常细致，可以按照其编码，问题不大。需要注意的是，这里的 XML 流格式要求很精确，不允许传输多余的东西。我一度认为采用 XML 会导致协议的实现上非常臃肿，其实不然。采用 XML 只是一个表象，适合人阅读和调错而已。RFC 中特别要求不去实现 XML 中的某某特性就是一例。我们不应该为了 XML 而去 XML 。

其实 XMPP 的 c2s 和 s2s 并无太大区别，s2s 做的人手我想是因为开源项目和开源库比较少吧。而开源的 client 实现则是一大堆。c2s 和 s2s 的通讯都是基于那几条协议而已，s2s 的实现难点在于握手比较复杂（其实 c2s 也一样，只是很多库帮你做好了）。c2s 是共享一个 tcp 连接做双向通讯；而 s2s 则是用两条 TCP 连接。两条连接也一定程度上避免了 s2s 的欺骗，当然真正的安全来至于 TLS 和 SASL 的保障。DNS 毕竟是一个很脆弱的东西。

除了点对点消息外，XMPP 定义了消息的组播。也就是一个 JID 可以以自己的名义发布消息 (presence)。而服务器来决定该发给谁。发送目标是由订阅消息决定的。其它多个 JID 可以订阅某个 JID 的消息。对于 IM 来说，最常用的就是上线下线等状态变化消息了。

第三条即是对某个 JID 的状态进行设置和获取 (iq)。于 IM 应用来说，设置签名，昵称，状态等都依赖于它。

XMPP 的核心协议无非规定了以上三种通讯协议，此外规范了服务器间互连的握手认证方案。然后给出了一些错误信息的表述方法。稍微了解过之后，很容易编写。如果希望重造轮子的话，对于 C 语言开发者来说，最繁琐的可能是 XML 的解析于生成。我自己稍微考察了一下，有个叫 LoudMouth 的库还不错。

如果实现 s2s 网关的话，有些细节做起来可能很麻烦，比如查询 DNS 的 SRV 记录。这个在 jabberd 1.x 里其实有独立的模块实现好了，取来用即可 (见 dnsrv) 。而 TLS SASL 层的实现则早就有现成的开源库了。

实现一个 jabber server 或许比你想象的还简单。in.jabberd 居然只用 600 多行 C 代码就从零实现了一个 jabber 服务器。当然功能非常的简陋了。

至于我想做的东西，我希望一个在名为 xyz 的梦幻西游服务器上的 12345 号玩家，一旦选择绑定他的 popo 帐号 player@popo.163.com ，他在他的 popo 上就会收到名叫 12345.xyz@xyq.163.com 的好友请求。当他通过好友认证后，就可以从这个通道获取游戏里的信息，也可以对游戏帐号做有限的操作。我想有了这样一项服务，对玩家对运营商都会有极大的好处的。

Posted by 云风 at 05:28 PM | Permalink | Comments (14)

自从我有了一小笔网易 (NTES) 的股票后（执行期权所得，并且为此上缴了 40% ~ 45% 的个人所得税），美元就一直在跌。从当初的 8 块多一直跌到现在的 6 块 8 。虽然我这人没啥钱，但也不愿意看见自己银行里的钱贬值。我又没啥多余的精力去理财，只好选择了长线投资股票，"投资" 那些我熟悉的公司。

首先要感谢九城，去年 TBC 他们一直搞不定，我就萌发了做空 NCTY 的念头。我觉得这是一个比较稳当的长期投资，卖空价位是 40 到 45 美金左右。

其次是新浪，我觉得我从来不用新浪的服务，他们的服务也没见得多好。为啥每个季度财报上还有那么多收入？看着新浪的头儿一个接一个的换，不像能稳定的样子。这让我很难理解。我在 33 到 40 之间做空了 SINA 。

然后要感谢这次金融危机，让我觉得即使是我这个根本没多少时间分心去关注股市这种无聊东西的人也可以稳定的获得收益。我选择了另一个不太能理解的高价位股票 SOHU (搜狐) 。那几天，我对他们高达 80 股价很不以为然。当然直到金融危机开始后好几天才醒悟过来，其实这是个好机会的：在 55~60 的位置卖空了 SOHU 。

最近公司股票的交易窗口打开了，虽然在上个窗口我已经在 26 的高位出掉了一些公司的股票。那些是去年大家都不看好我们公司 NTES 时，我在交易窗口里 13 到 18 左右买入的。这次这么严重的金融危机，让我有了点回避风险的念头。所以这几天回到 18 块就套现了。

可惜现金利息不高，美圆又在贬值。总要找个安全的位置把它们放起来。我想盛大 SNDA 是个不错的资金保值的地方，在 23 块的地方卖空了。貌似我没有看错。不过金融危机里，我想大多数人都不会看错吧。

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

以前谈过多次 AOI (Area of Interest) 的实现，因为我们的游戏尚在开发，模块需要一个个的做。前期游戏世界物件不多的时候用个 O(N^2) 的算法就可以了：即定时两两检查物件的相对距离。这个只是权益之计，这几天，我着手开始实现前段时间在 blog 上谈过的 独立的 AOI 服务器。

既然是独立进程，设计协议是最重要的。经过一番考虑，大约需要五条协议，四条是场景服务器到 AOI 服务器的（列在下面），一条由 AOI 服务器发送消息回场景服务器。

1. 创建一个 AOI 对象，同时设置其默认 AOI 半径。注：每个对象都有一个默认的 AOI 半径，凡第一次进入半径范围的其它物体，都会触发 AOI 消息。

2. 删除一个 AOI 对象，同时有可能触发它相对其它 AOI 对象的离开消息。

3. 移动一个 AOI 对象，设置新的 (2D / 3D) 坐标，并给出线速度的建议值。

4. 设置一个 AOI 对象相对另一个的 AOI 半径，覆盖其默认设置。注：AOI 半径可分两种，一为进入半径，二而离开半径。通常一开始，每个 AOI 对象为其它对象均设置一个进入半径；当消息触发后，由场景逻辑重新设置一个离开半径。例如，一个 AOI 对象的默认半径是 10 米，当它被创建并指定坐标后，任何物体进入它的 10 米范围内，都会立刻由 AOI 服务器发送出一个 AOI 消息；而后两者之间不会再自动触发消息。场景服务器收到消息后，可主动向 AOI 服务器设置新的 AOI 离开半径 12 米，当此物体远离到 12 米远后，离开消息触发；下一步再由场景服务器重置进入半径。

这套协议相对简单，可以满足游戏的一般需要，并隐藏 AOI 服务的实现细节。对象全部由 handle 方式传递，由场景服务器自己保证 handle 的唯一性。在我这次的实现中，每个 AOI 对象同时只能拥有一个 AOI 半径触发器，但是协议本身无此限制。

下面，我们再来看一下实现细节。

一般的 AOI 模块有两种实现方式，最常用且最简洁的方式是打格子。无论是小格子也好（一格只能占一个对象）还是大格子也好（一格是一个较大区域，在区域内再使用 O(N^2) 算法逐一比较），实现起来都很清晰明了。

按 KISS 原则，我建议没有特殊需求的情况下都使用格子的算法。当然，格子算法也有一些不足，比如格子本身的内存消耗，跟场景规模有关，却与对象实现无关，有时候，会浪费大量内存（独立进程可以一定程度回避这个问题）；对于变化不定的 AOI 半径，固定单位长的格子方案在效率上也略有缺陷。

另一个思路是几年前我在和天下组的同事聊天时了解的。为每个对象创建两或三个维度上的线段，并对线段端点做插入排序。我本身对这个算法不太感兴趣，就不展开谈了。

昨天晚上躺下比较早，翻来覆去睡不着，想到一个新的思路来实现 AOI 模块。

最 KISS 的方案是每个心跳一一比较 AOI 对象的距离。时间复杂度是 O(N^2) ，在 N 比较小时，其实是最佳方案。因为其实现非常简单。注意这里，对于 A 和 B 两个对象， A B 和 B A 是两组。这是因为 A 的 AOI 半径和 B 的 AOI 半径很可能不同。那么对于 N 个对象，要比较 N * (N-1) 次。除非游戏中玩家都在小副本中，且副本里的 NPC 数量不多（或者 NPC 之间不需要做 AOI ）不然在大规模场景中难以接受。

btw, 所谓被动怪，就是不需要做 AOI 处理的 NPC 。在很多游戏中大量放置，除了帮助脑残玩家快速升级外，也是为了节省服务器资源。wow 中那些 NPC 之间也会野外碰见并交战，NPC 间会呼朋结友一起上的设计，其实是很考验 AOI 模块性能的。

应该如何提高 N 比较大时的性能？

我们主要，相隔较远的物体，是不需要时时检测它们之间的距离的。而大部分物体间隔都远超双方的 AOI 半径。我们只要从这里着手改进算法就可能得到很大的性能提高。

比较容易想到的是使用一个 timer 。我们可以根据两个物体间的距离，以及移动速度，估算出一个最短相遇时间。这个时间往往远超一个心跳。按这个时间，把 AOI 检查放到 timer 队列里即可。

我在实现时是这样做的：要求场景服务器在发送物体坐标时，同时发送一个线速度的建议值。我按这个值的两倍计算物体两两间的相遇最短时间，并注册 timer 。以后只要不超过这个速度的两倍就可以忽略它。否则，重新计算跟这个物体相关的所有目标距离，调整对应的所有 timer 在 timer 队列中的位置（这需要特制一个 timer 模块来提供这个功能）。

这个优化依旧有一个问题。它需要为每对物体创建一个 timer 节点。所以空间复杂度是 O(N^2) ，这可能大大超过内存预算（虽然独立进程也可以缓解这个问题，但只要想一下，N 可能上万，就知道问题有多严重）。

我们需要进一步的优化。

在游戏中，大部分对象是老死不相往来的，由于是那些身处各地的 NPC 。只有极少数出生地不同的 NPC 会由于脚本设计游走各方。而玩家，那些有可能大范围活动的对象，相对 NPC 的数量又是少了一个数量级。我们只要在内存中除掉这些无谓的数据就好了。

假设半径 100 米在游戏中是一个比较大范围，NPC 没事不会超过这个活动范围，而玩家一般情况下跑过 100 米也需要一段时间（这要花上好几秒，秒对于 CPU 是个很长的时间单位）。

我们可以给所有对象设置一个 100 米为单位的活动范围。如果两个对象之间的直线距离大于 200 米加上他们的最大 AOI 半径，我们就可以不记录这两个对象之间的关系（认为它们不可能相遇）。而一旦一个对象离开它原来的记录原点超过 100 米，就认为它发生了迁徙，立刻把它对场景中所有的对象重新做一次比较（时间复杂度 O(N) ），这个操作固然慢，但是还可以接受，而且并不常发生。

综上，是我这次实现的 AOI 服务的一个框架了。实现它们还需要两三天时间。

Posted by 云风 at 04:14 PM | Permalink | Comments (13)

其实很早就做完了，但是一直在完善。现在基本上可以玩了。

一个卡牌类的游戏，对于玩过《卡片召唤师》的玩家一看就明白是什么 :) 对于没玩过的，可以参考《大富翁》的规则。但这是个很考验技术的卡片类游戏哟，只是形式上类似《大富翁》。

原系列《卡片召唤师》已经有超过 10 年的历史，所有规则和平衡多做的相当好。我们会慢慢的在原始规则上，增加一些新的玩点。

有兴趣的朋友可以去 http://xyc.163.com 下载客户端。官方网站（由于并非我们的开发团队维护）若没及时更新下载连接，可以看这里：这个帖子里有最新的下载地址以及若干相关问题。安装包很小(40M左右)，而且是绿色的。 欢迎来游戏官方论坛交流，论坛地址是 http://xyc.netease.com

有网易通行证（网易邮箱）或网易 popo 的帐号就可以登陆了。目前是免费运营阶段，且没有任何道具收费。赢得游戏完全看技术和实力。

这个游戏虽然不是我们工作室的主打产品，但我个人在这个项目上也投入了颇多精力。对这类游戏我个人是非常的喜爱，游戏的策划更是 10 年的老玩家。总之，大家都是非常认真的在做了。虽然游戏类型很冷门，但还是希望能吸引到同好。

游戏上手不太难，也不简单。在官方论坛攻略区有不少新手指引帖。

ps. 《冰与火之歌》的桌面游戏设计的真不错。我们 5 个人连带研究规则到完整结束一局游戏玩了整整一通宵都无倦意。Down Time 被设计者压缩到很短，游戏进程非常紧凑。可惜我们这款《卡牌对决》的 Down Time 还是稍长了一些。

Posted by 云风 at 06:19 PM | Permalink | Comments (19)

最近在帮另一办公室的同事调试程序，有些东西远程弄起来比较麻烦，征得同意后，我希望直接连入对方的局域网来弄。但是申请 VPN 权限以及修改对方路由的程序比较繁琐，所以我想找个简单的方法。

首先我在我们办公室的网关上做了个 NAT ，让对方可以 ssh 到我的机器。

阅读 ssh 的手册我发现 openssh 支持一个 -w 参数，用来连接两端的 tun 设备。不过试了半天没有搞定 :( 所以又想了其它办法。

后来，我安装了 vtund 。对方在本机上以 server 模式启动 vtund ，监听本地端口。然后再通过 ssh -R 把本地端口映射到我的机器上。

我的机器以 client 方式启动 vtund ，连接上映射过来的 vtund 服务端口即可。

这个时候，两边使用 ifconfig 均可以查到 tun0 设备。用 ifconfig 设置一下点对点路由。由于两边系统不太一样，分别是 freebsd 和 linux ，语法有细微不同。感觉上 linux 的语法繁琐一些。

接下来，对方机器上设置好 ip 转发，作为网关。我的机器删除原有默认网关，并添加默认网关为对方的 vtun 的 ip 。 另外记得增加一条路由规则，由原网关连入对方 ip 。

一切搞定 :D 我的机器可以自由访问对方的局域网了。

ps. 为了安全，用来接收对方 ssh 登陆的用户特别设置了一下。在 .ssh/authorized_keys 里设置上 permitopen 只允许映射 vtund 的端口，并加上 command 强制允许一个死循环脚本。

这个方法反过来用的话，挺适合在外面不安全的环境上网的。在不安全的环境里，先通过 ssh 连接到自己信任的网络上，建立一个 VPN ，然后再访问其它网络资源。

Posted by 云风 at 02:27 AM | Permalink | Comments (4)

今天调公司里的 VPN 时，发现我的 freebsd 机器 traceroute 老是失败。

控制台报告

traceroute: sendto: Permission denied

（以上错误信息用来引导 google 同类问题的同学）

一开始是 ping 都不行，我查看了 firewall 的设置，允许 icmp 包通过。ping 就可以用了，但是 traceroute 还是不行。

这让我很疑惑，后来用 tcpdump 查了一下，发现 freebsd 的 traceroute 默认是用 udp 协议做的。真是惯性思维害人啊。windows 和 linux 下都是使用 icmp 的。

man 了一下，发现 freebsd 的 traceroute 可以用 -P ICMP 选择 icmp 协议。然后一切正常，不需要修改 firewall 的设置了。

Posted by 云风 at 09:28 PM | Permalink | Comments (5)

今年的 SD 2.0 大会据说还是在那个荒郊野外的九华山庄开。我们这里一个打算去的同事都有意见了，好不容易去趟北京，连六环都没进去。

前段时间孟岩让我准备一下，我想不出啥好玩的题目。后来就想聊点基本的东西，也是最近两年开发中纠结了很久总结出的丁点经验吧，有关内存管理的问题。

主题是关于：用 C/C++ 构建的系统，在内存管理这个层面，如何促进系统的健壮性和性能。session 的题目最终被命名为：高性能健壮系统中的内存管理 。有点绕口。

这两周一直很忙，直到前两天搜到今年大会的课程单 才发现，原来我的题目跟大家的相比，还真的老土了 :) 我想有点违背所谓 2.0 的宗旨。或许在十年前讲这个问题，感兴趣的人会多一些？呵呵，无所谓了，开会主要以交朋友为主嘛。

上周末理了个提纲，鉴于上次的经验，这次我还是提前把 PPT 放出给大家下载比较好。有意见尽管在下面留言。

我目前只是打了个草稿，可以点下面的链接下载。这段时间如有更新，会在本篇注明：

高性能健壮系统中的内存管理 （2008 年 11 月 10 日上载）

Posted by 云风 at 09:23 PM | Permalink | Comments (28)

在 9.douban 看到一篇 blog ：最节省时间的方法——学习 ，深有同感。

学习是多么奇妙的一种经历啊，无论是从过程还是结果来看，都是这样。我想说了，这篇 blog 里都说了，务须重复。

对于那些被我自己挥霍掉的时间，总是有一种负罪感。所以我把零碎的时间收集起来阅读，寻找更高效的方式吸收知识。再把整块的时间划分好，去做些可以提高和消化这些东西的事情（所谓学和习吧）。这就几乎是我目前生活的全部了（当然，学习的对象不应仅仅包括某种技能）。以至于我觉得学习应该是人的天性，人的基本需要。

说到 在学校里读了许多年书的最终结果 ，我倒是在离开校园的时候也偷偷发了个誓，那就是再也不接受任何形式的考试了。最终违背了一次誓言，通过考试拿了个驾照。

之外，我对学校倒没有特别的厌恶。毕竟是在那里，我学到了我所拥有的知识中最根本的部分。

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