云风的 BLOG

周末一直在考虑怎样在游戏服务器中保存和管理那些有平面坐标的对象。希望能方便的查到每个对象附近的东西。以往用过的方法是给（平面）场景打上格子，然后再把每个对象放入相应的格子中。

这次又遇到这个问题，却不想用网格的方法来解决问题了。

原因主要是这么几点：一，用网格对于大场景特别消耗内存，而且不太适合做无限延展的场景。二，查询每个对象周围的东西时，不太方便。格子的粒度越小，速度越慢。

虽然这两个问题，都可以通过改进算法来回避。不过这次，我想尝试一下用四叉树解决这个问题。

用四叉树的话，内存占用量应该 O(n) 。如果定死了四叉树的扩展深度，可以推算出节点的最大可能消耗量。我想，如果只是为了解决 AOI 的计算，5 级深度已经足够。这样，大约预分配出 20 * n 个节点，几乎肯定够用了。

我希望场景是从坐标原点向四周无限延展开，没有什么具体的尺寸限制。所以，这次实现的时候对四叉树做了改造。第一级的划分是一个特例，它将平面分成四块，每一块都可以向某个方向无限延伸。

接下来，把各种可供切割的平面分为 9 类：

 2 6 1
 7 5 9
 3 8 4

我给这些类别编了号，5 号类型的平面有固定大小，可以被明确切割成四块，这四块依然是类型 5 。而类型 1 的块，被切割成四块后，四块的类型(按四个象限分布)分别是 1,6,5,9 。同理，类型 2,3,4 的平面，也会被切割成不同类型的四块。

类型 6,7,8,9 的平面由于他们只向一个方向延伸，所以只能被切割成 2 块，一块固定大小的正方型（类型 5），一块保留它原来的类型。

这样，我的数据结构不是一个完整的四叉树，有个支干上就只有两个分支了。如果一个对象被放到了离坐标原点过远的地方，树的深度可能很大（超过 5），但是宽度会减半。如果大多数对象都在原点附近的话，查找是很快的。

今天化了一通宵的时间来实现这个东西，写了四百多行 C 程序。因为要实际用到项目中去，效率上的考虑比较多，顾而时间用了近 8 个小时；而且篇幅也比我想象的长的多。

一般，我们会在四叉树的每个节点上保存父节点的指针。这样，遍历这棵树就不需要用递归实现。好久没有写纯算法的程序了，平时递归写惯了，今天为了实现个用回溯法遍历树的算法还颇费了点工夫。为了提高查找一个节点附近节点的效率，最后也做了特别的实现。

另外，因为树节点总数可以估算出来，我用了个预分配的大节点池，并内部实现了 gc 算法。这样，从四叉树上拿掉节点非常简单，分配新节点也很容易。事后想了一下，不用 gc 的话，用一个 freelist 来管理也慢不到哪去。

在四叉树的叶子上，存放一个对象链表即可。可以用一个备用链表，分配，释放，移动位置都不需要重新构造。估算了一下，对象在四叉树描述的场景中移动，处理过程应该是常数时间了。查询 AOI 区域的对象也是一个常数时间。总的来说，对今天的工作成果还是挺满意的 :)

隔日补充：

其实，通过动态增加层次来向边界延展的算法实现起来更简单，也没有增加太多储存和查询的负担。昨天晚上把问题想复杂了。睡一觉起来后，把程序改了。

Posted by 云风 at 06:18 AM | Permalink | Comments (25)

为了个考试，害我几天都没睡好。早起摸黑的练车。这下了了桩心事。希望这辈子不要再有考试。

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

今天开始正式开始做数据服务器。在这点上，我希望一组服务器上所有的逻辑服务遇到的数据存取需求都通过一个单一的数据服务器完成。而且，写入数据是单向通讯的。即，逻辑服务器只提读写盘请求，而无须确认。写数据好说，读数据稍微难处理一点，我现在的方案是，数据服务器加载数据的部分只对位置服务器负责，把数据提交到位置服务器即可。位置服务器可以通过分析数据知道玩家的数据流应该流向哪台逻辑服务器。

以上逻辑是基于每个玩家有独立的数据的，而且一个玩家同时只存在于唯一一个场景。也就是说，当一组数据存活的时候，只唯一属于一台逻辑服务器。这样做的好处是，切换场景非常的简单，只是让玩家从一个场景退出，给数据服务器发出写盘指令，并发送所有数据。数据服务器写盘的同时也 cache 了这些数据，并向位置服务器提交新的位置，并把这些数据转发向位置服务器。位置服务器可以再转交给新的场景。

对于玩家登陆和登出的处理并没有特别之处，我们可以设立两个虚拟场景，一个负责登入，一个负责登出。每个新连接自动导入登入场景，这个场景负责发出加载指令（下面可以看到，甚至无须设置加载数据的协议）。然后再做一个自动的场景切换操作即可。而玩家登出，则是转入登出场景，这是一个黑洞，玩家的连接可以在这里安全的断掉。

当玩家不停的穿梭于各个场景之间时，为了避免频繁的数据转发，我们可以给玩家数据做一个赃标记。如果没有弄赃，实际的数据可以不被转发。这个标记的另一个意义在于，若数据没有弄赃，而数据服务器的 cache 中又没有数据时，就需要从外存加载了。其实这就是一个读请求。

月初我在公司内部讲解这个设计时，遭到了一些同事的疑问。最典型的一个是，帮派信息如何处理。的确，类似帮派的信息，不属于任何一个玩家。如果你单独设一个非玩家对象保存这些数据时，可能会分布到不同的逻辑服务器上。的确对数据服务器的设计是一个挑战。

今天仔细考虑过以后，我发现可以从设计上避免这个问题。方法如下：

以帮派为例，可以设一个帮派总坛的场景。这个场景可以是虚拟的，在 client 表现上甚至可以只有一个界面，进入这个场景的玩家之间可以相互不可见。这样减少了大量的通讯量。

玩家任何时候查询，修改，帮派数据的时候，都强制他进入这个场景工作（也就是独立进程维护唯一数据）。做完操作后，玩家可以从哪来的回哪去。表现上，他可能并不会察觉到自己进入了一个遥远的地方。

甚至很多玩法应蕴而生。比如帮派在各地开了分舵。组织要求你把总坛的物质运输到分舵。其实仓库里的数据都是放在一个进程中。表现上，玩家可能千里迢迢的押运货物，只是修改了一下物品的归属地而已。

帮派也可以开出空头支票，玩家接受支票交易时，或许要去帮派回所去查一下帮派的信誉度，或者验证一下支票能不能兑现。因为支票开出去到了玩家手上后，数据已经交给玩家个人管理，和帮派数据无关了。

这样，复制出来的帮派数据都有了时延，比如你不能及时得到帮主是谁，帮派里有什么变化等等。（只是举例，实际万一想解决，可以走聊天这种不可靠通道）但是我个人认为这是符合现实的。因为现实中要得知一件事情，也是依赖一个信息发生源的。

想通了这些后，个人感觉我们的设计最终还是保持了简洁。满符合 KISS 原则。每个进程好好干好一件事吧 :)

ps. 这里也突出了心跳服务器的重要。许多虚拟场景，如帮派管理等，可以放慢它的心跳（至少不用处理战斗时 10Hz 那么高的频率），这样也降低了这些进程的负载。而玩家体验却并不会有太大的影响。

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

目前，我们的游戏服务器组是按多进程的方式设计的。强调多进程，是想提另外一点，我们每个进程上是单线程的。所以，我们在设计中，系统的复杂点在于进程间如何交换数据；而不需要考虑线程间的数据锁问题。

如果肆意的做进程间通讯，在进程数量不断增加后，会使系统混乱不可控。经过分析后，我决定做如下的限制：

1. 如果一个进程需要和多个服务器做双向通讯，那么这个进程不能处理复杂的逻辑，而只是过滤和转发数据用。即，这样的一个进程 S ，只会把进程 A 发过来的数据转发到 B ；或把进程 B 发过来的数据转发到 A 。或者从一端发过来的数据，经过简单的协议分析后，可以分发到不同的地方。例如，把客户端发过来的数据包中的聊天信息分离处理，交到聊天进程处理。

2. 有逻辑处理的进程上的数据流一定是单向的，它可以从多个数据源读取数据，但是处理后一定反馈到另外的地方，而不需要和数据源做逻辑上的交互。

3. 每个进程尽可能的保持单个输入点，或是单个输出点。

4. 所有费时的操作均发到独立的进程，以队列方式处理。

5. 按功能和场景划分进程，单一服务和单一场景中不再分离出多个进程做负载均衡。

性能问题上，我是这样考虑的：

我们应该充分利用多核的优势，这会是日后的发展方向。让每个进程要么处理大流量小计算量的工作；要么处理小流量大计算量的工作。这样多个进程放在一台物理机器上可以更加充分的利用机器的资源。

单线程多进程的设计，个人认为更能发挥多核的优势。这是因为没有了锁，每个线程都可以以最大吞吐量工作。增加的负担只是进程间的数据复制，在网游这种复杂逻辑的系统中，一般不会比逻辑计算更早成为瓶颈。如果担心，单线程没有利用多核计算的优势，不妨考虑以下的例子：

计算 a/b+c/d+e/f ，如果我们在一个进程中开三条线程利用三个核同时计算 a/b c/d e/f 固然不错，但它增加了程序设计的复杂度。而换个思路，做成三个进程，第一个只算 a/b 把结果交给第二个进程去算 c/d 于之的和，再交个第三个进程算 e/f 。对于单次运算来算，虽然成本增加了。它需要做额外的进程间通讯复制中间结果。但，如果我们有大量连续的这样的计算要做，整体的吞吐量却增加了。因为在算某次的 a/b 的时候，前一次的 c/d 可能在另一个核中并行计算着。

具体的设计中，我们只需要把处理数据包的任务切细，适当增加处理流水线的长度，就可以提高整个系统的吞吐量了。由于逻辑操作是单线程的，所以另需要注意的一点是，所有费时的操作都应该转发到独立的进程中异步完成。比如下面会提到的数据存取服务。

对于具体的场景管理是这样做的：

玩家连接进来后，所有数据包会经过一个叫做位置服务的进程中。这个进程可以区分玩家所在的位置，然后把玩家数据分发到对应的场景服务进程中。这个位置服务同时还管理玩家间消息的广播。即，单个的场景（逻辑）服务并不关心每个数据包为哪几个玩家所见，而由这个服务将其复制分发。

当玩家切换场景，场景服务器将玩家的数据发送给数据服务，数据服务进程 cache 玩家数据，并将数据写入数据库。然后把玩家的新的场景编号发回位置服务进程，这样位置服务器可以将后续的玩家数据包正确的转发到新的场景服务进程中。

掉落物品和资源生产同样可以统一管理，所以的场景（逻辑）进程都将生产新物件的请求发给物品分配服务，由物品分配服务生产出新物件后通知位置服务器产生新物品。

这样一系列的做法，最终保证了，每个场景服务器都有一个唯一的数据源——位置服务进程。它跟持久化在数据库中的数据无关，跟时钟也无关。由此带来的调试便利是很显著的。

最近，面临诸多进程的设计时，最先面临的一个复杂点在于启动阶段。显然，每个进程都配有一套配置文件指出其它进程的地址并不是一个好主意。而为每个服务都分配一个子域名在开发期也不太合适。结果我们采取了一个简单的方案：单独开发了一个名字服务器。它的功能类似 DNS ，但是可以让每个进程自由的注册自己的位置，还可以定期汇报自己的当前状态。这样，我们可以方便的用程序查询到需要的服务。名字服务器的协议用的类似 POP3 的文本协议，这让我们可以人手工 telnet 上去查阅。我相信以后我们的维护人员会喜欢这样的设计的。:D

以上，国庆假期结束以来的工作。感谢项目组其他同事的辛勤编码。

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

又是一个长假，由于连着年度旅游，假期比往年更长一些。出去旅游前，就有同事嘲笑，“出去玩还背着那么厚一本书，累不累啊。”我自己知道，书是带回家看的。

这个假期伴随我的是这样一本书——《UNIX 编程艺术》。几个月以前就开始读了。以前是随手翻开中间几页读上一篇；这次，躺在阳台前的躺椅上，舒服的晒着阳光。终于，从头至尾的完成了。

贯穿始终的 KISS 原则，很多年前就被谆谆教导过了。它被我无时无刻的都拿出来警告自己的设计过程。读完这本书，让我对 KISS 又有了一次升华。其实，这本书对我几个月来设计游戏服务器架构的影响是满大的。坚定了我每写一个程序做好一件事的决心。让我更确信用多进程的设计取代多线程的决定是正确的；我们坚持的二进制模块复用的模型是切合 SPOT 原则的。

回顾自己对 C++ ，逐步的敬而远之，并非因为读了这本书。这本书基本没谈 C++ ，但是只言片语却深合我心。书中对 C++ 的不屑，于我看来并非如我曾经读过的某些书评所述：来源于作者对 C++ 了解的肤浅。

我自己仍旧对 C++ 充满兴趣，并继续努力对 C++ 做最大的理解，其实正是为了可以压抑住在项目中使用它的念头。这是我最近一年来编程思想最大的转变。同时，身边的人也受到了这种影响并慢慢接受。我相信，我们的方向是正确的。

Posted by 云风 at 08:32 PM | Permalink | Comments (39)

MMO 的 engine 中，需要解决的最重要的问题之一，就是如何把游戏世界中的状态改变消息正确的通知给需要知道这条信息的玩家。

通常，我们会设定每个玩家的 AOI ( Area Of Interest )。当一个对象发生改变时，它会把消息广播出去；那些 AOI 覆盖到它的玩家会收到这些广播消息。

但是，在我们现在的游戏系统中，简单的 AOI 系统是不够用的。比如，类似 wow 中的盗贼隐身，明明已经离你很近，但是你的 client 却看不见他。诚然，我们可以在 client 判断这个逻辑，对盗贼不于显示，而 engine 依然广播盗贼移动的消息。对于不作弊的 client ，这是个简单的解决方案。但在理论上却提供了看见隐身人的可能性，所以，我期望有更好的方法让 engine 可以只将消息广播到那些必须接收这些消息的 client 。但是，在实现这个同时，又不能让底层 engine 牵扯太多逻辑信息。

这里提出一个简单的方案：

基本的 AOI 系统中，对象只有方位坐标是为 AOI 模块所知的。如果希望让每个玩家的视野有所不同，对于观察者（玩家）可能还需要多设定一个视野半径的参数。如上面举出的盗贼隐身一例，解决那种逻辑这些数据是不够的。

我所构想的系统中，观察者有两个参数，雷达半径和雷达强度；而被观察者除了坐标外，还有一个信号半径的参数。（这里，玩家通常既是观察者又是被观察者；而 npc 是纯粹的被观察者）

雷达半径就是前面所说的视野半径；而雷达强度决定了在离目标一定距离时，可以分辨的最大尺寸的物体。这个尺寸当然不是指对象的模型大小，而是指被观察者的信号半径。

有了这几组数据，我们就可以决定被观察者是否为观察者所见。通常，雷达半径、强度，和物体的信号半径都是不变的。但是，游戏逻辑可以根据需要来改变它们；比如通过装备、升级、战斗时 buffer 等等。不过底层 engine 不需要了解这些逻辑的细节，只需要把基本参数拿出来算一下就可以确定了。

我们把这些属性绑定在对象上，由 engine 决定对象的远程方法应该发给哪些人。进一步的，我们可以给对象的每个远程方法加一个权值，以优化网络通讯。比如，人物对象可以有一些诸如挥手一类的 emote 行为，可以有一个较低的信号半径权值。当一个玩家可以看见 500m 外的一个人物时，或许这个人物正在做的挥手动作他还看不见；直到他们接近到 250m 时才能收到挥手的消息。

这样的系统，对于 3d 第一人称的 mmo 或许会有用。了解过我们公司另一个项目没能很好的解决这个问题，写此文将自己的想法记录之。

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

很多网上服务都需要用户注册，而注册的过程往往降低了用户体验。已经有许多人在做一些尝试，简化注册的过程。最简洁的莫过于第一次使用即注册，但是这依然有用户名以存在的麻烦。

很早以前有过一个想法，如果大家都用自己使用的 email 地址做用户名登陆，通常就不会有用户名冲突的情况了，甚至可以选择不使用密码。反正许多网上服务，并不需要密码保护个人身份或者个人数据。而且等到需要的时候，完全可以通过 email 设定一个密码。

一旦用户选择给 email 用户名加一个 nickname 或者由系统自动产生一个名字，而 email 地址不可见，那么 email 地址就成了一个密码的作用，只不过密码强度太低罢了。

这个方法的好处是显而易见的：用户的记忆量下降了。注册的难度也降低了许多。而提供服务的网站，却可以得以区分用户。

那么如何识别出伪用户，让真用户不因为有人可以对他冒名顶替而失去网上唯一身份的安全感呢。除了用户自己要求加一层密码保护外，我想可以让系统智能一些的判断。比如挑选出异常的登陆 ip 发 email 通知，或者在长时间不登陆的时期，对于突然的新一次登陆发 email 提醒。我认为做一些合适的手段，这个方案会更容易让用户接受。

今天突然又想到另一个问题，能不能取消用户名，而只有密码呢？在我们的网络游戏的论坛上，有这样的告示提醒玩家，不要轻易的暴露自己的用户名。也就是说，用户名其实也是用户个人身份安全保障的一部分。如果我们把用户名和密码连在一起输入，对于每个人，其实就是一个全局唯一串用来识别身份。把这个串切分成用户名和密码两部分，只是一种惯例而已（当然还有实现上的方便）。

我们何不尝试破除这个惯例，直接让用户在注册的时候完整的输入一个唯一字符串？

我们在用户注册的时候就检查出一些不安全的密码设定，保护用户的帐号安全。比如，要求密码至少 8 位，且包含字母和数字（甚至要求大小写混用或是外加标点）。一旦不符合基本安全要求，就拒绝注册。这样可以极大的避免两个人使用相同密码。

而一旦某人使用了一个前人已经用过的密码串注册，可以直接提示他密码不安全，不准注册。然后封存前一个人的帐号，并 email 通知他修改密码（如果没有留 email 则直接封一段时间帐号即可，并在他下次登陆的时候提示修改密码）。

如果这样做，当然有可能被人撞上一组可以进入系统的别人的密码。但是我认为传统的用户名密码设计不会更安全。相反，我们可以得到这样一个好处：让用户用更安全的密码。这来自于非恶意的猜测。而对于恶意的攻击，可以想出更多的方法来阻挡。比如提示正常用户，当密码失效的时候，即时检查自己的 email ，或者等待一段时间（解冻期）再试。而当自己的密码不太安全时，系统可以协助用户重设密码（可以是自动的）。对于恶意暴力尝试进入系统的 ip ，则可以直接让他短时间内不能用任何密码登陆。

暂时就想了这么多，写出来只为留住思维的火花。

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