DC3算法

最近做了一个差量更新工具, 实质就是一个Diff工具。这个Diff工具在本地生成一个patch文件。客户端通过网络下载到本地后,根据本地文件和patch文件来生成最新版本文件。

与传统patch不同的是,为了尽可能的减少网络传输,patch文件需要尽可能的小,并且不需要逆向patch(从版a到版本b生成的patch, 版本b使用这个patch可以还原到版本a).

基于以上考虑,我重新设计了一个二进制patch格式,整个patch文件中有两种Action(分别是COPY, INSERT),大致数据结构如下:

struct COPY {
        int pos;
        int size;
};
struct INSERT {
        int size;
        uint8_t buf[];
};

其中COPY代表从源文件a的某个位置(COPY.pos)copy一段(COPY.size)数据过来,INSERT代表在新文件b当前位置插入一段数据(这代表这段数据在文件a中找不到)。

之所以不需要新文件新文件的位置,是因为在生成patch时会严格按着新文件的写入顺序来生成patch, 这样也可以尽可能少的减少Action头所带来的开销。

在生成COPY指令时,我遇到了一个问题.

即,如何快速找到,同时存在于文件a和文件b中的最长子串。算法导论上的LCS(公共子序列)算法并不是很适合我,因为COPY只是去借数据,并不在乎这块数据在哪个位置。

最终发现,有序后缀数组更符合我的需求,空间复杂度极底,并且可以以lg(n)的时间复杂度来快速完成匹配。但是其生成算法DC3,我搞了将近2周才总算搞明白。

整个算法一共就分4步,原始数据在buf中,长度为N,(这里仅粗略描述):

1. 将(i % 3 != 0, i >= 0 and i < N)的值取出来放到一个数组SA12中.

2. 对S12进行排序, S12中的每个值n都代表一个三元组(buf[n],buf[n+1],buf[n+2]),排序后得到一个数组s12, 其中s12[x] = rank(x = n / 3 if n % 3 == 1, x = n / 3 + n1 if n % 3 == 2)。n1为i%3==1的个数。

3. 如果任意两个三元组都不相等,说明仅凭前三个字母就可以对后缀确定顺序,则直接执行步骤4。否则,对s12中的数据递归执行DC3。

4. 根据s12来生成数组SA12,然后将(i % 3 == 0,i >= 0 && i < N)的值取出放入SA0并进行排序,与SA12进行有序合并,成为SA。SA即为后缀数组的有序列表。

这算法并不是通常见到的,如快排,二分查找,甚至红黑树那么直观。他神奇到,我完全不知道这是在做什么,后缀数组已经排完序了。

在看这个算法时,在第2步我有几个很大的疑惑。

一是有个很神奇的操作,在生成s12的时,如果n % 3 ==1, 要把rank值放左边,n % 3 == 2要把rank值放右边。

二是左边和右边中间如果是连续的(没有空洞x, buf[x]会比buf数组中所有值都要小),就必须要插入一个分隔符(比buf数组中所有值都要小)

三是为什么要选3这个数字,2行不行。


搞明白之后发现,整个算法的核心思想就是”收敛”, 运用递归的思想不断的收敛,直到比如结果为止。举个例子:

              0 1 2 3 4 5 6 7 8 9 10
char buf[] = "m i s s i s s i p p i";

第一步先拿到SA12= [1,2,4,5,7,8,10],

本质上他们代表的是:[‘1,2,3′,’2,3,4′,’4,5,6′,’5,6,7′,’7,8,9′,’8,9,10′,’10,x,x’],不存在的以x代替buf[x]一定会最小值

对SA12进行排序之后原始排序如下.

[‘1,2,3’=【3】,’2,3,4’=【5】,’4,5,6’=【3】,’5,6,7’=【5】,’7,8,9’=【2】,’8,9,10’=【4】,’10,x,x’=【1】],

将n%3==1的放左边,n%3==2的放右边之后得到如下列表:

[‘1,2,3’=【3】,’4,5,6’=【3】,’7,8,9’=【2】,’10,x,x’=【1】,’2,3,4’=【5】,’5,6,7’=【5】,’8,9,10’=【4】], 因为这里有x,而buf[x]一定比buf[0~n]中的值都要小,所以就不用插入分隔符了,后面会看到分隔符的作用。

从上面列表可以看出’1,2,3’ === ‘4,5,6’ 这说明三元组不足以用来确定后缀的排序(不满足步骤3),因为要接着递归执行,先得到SA’如下

[‘1,2,3,4,5,6,7,8,9′,’4,5,6,7,8,9,10,x,x’,’7,8,9,10,x,x,2,3,4′,’10,x,x,2,3,4,5,6,7′,’2,3,4,5,6,7,8,9,10′,
‘5,6,7,8,9,10,x,x,x’, ‘8,9,10,x,x,x,x,x,x’]

可以明显看到,之所以要把i%3==1的放左边,i%3==2放右边,其实是为再次递归DC3做准备。第二次递归DC3,实质上是取所有后缀的前9个前缀来进行排序,如果还有相同的,则再次递归采用前27个前缀进行排序,直到排出顺序为止。

为了利用上次递归的结果,上面数组会被转化成转换之后(【3】【3】【2】【1】【5】【5】,【4】)再递归传入DC3。

而之所以要插分隔符,其实是为了防止类似序列中’7,8,9,10,x,x,2,3,4’中的’2,3,4’参与排序,毕间7,8,9,10已经是从位置7开始后缀子串的全部内容了,如果2,3,4参与比较就会产生错误。因为buf[x] < buf[i] (i >= 0 && i < n),因此当碰到x, 就会终止排序。

那么为什么要选3这个数字,其实跟步骤4是有关系的。

在步骤4进行有序合并时,i%3==1时,会将3元组扩展成4元组,i%3==2时,将3元组扩展成5元组,之后再比较。

当i%3==1时,如’0,1,2,3′, ‘1,2,3,4’ 由于’1,2,3’和’2,3,4’的值我们已经知道了,所以这两个四元组的比较可以简化为’0,s12[1]’与’1,s12[2]’之间的比较,由于s12[1]中的值各不相同,因此’0,s12[1]’ 与 ‘1,s12[2]’必不相同。

当i%3==2时, 如’0,1,2,3’, ‘2,3,4,5’,可以发现s12[3]不存在因为3%3==0, 所以需要将4元素扩展成为5元组,‘0,1,2,3,4′,’2,3,4,5,6’,这样就可以化简为’0,1,s12[2]’, ‘2,3,s12[4]’来进行比较。

其实到这里,为什么不用2就很明显了,因为在最后一步合并时2不满足重用上一步结果的要求

总的来说这是一个很神奇的算法,有动态规划的影子,各个步骤又配合的天衣无缝。

开卷有益(UNIX编程艺术篇)

最近《计算机程序设计艺术》看多了,每次写完代码之后,总会习惯估算一下指令级的开销。导致每次写代码都是性能导向,违反了很多设计准则。因此打算重新看一下《UNIX编程艺术》,来拉一下已经严重倾斜的天平。

刚看了二页,又想起一个困扰我多年的问题,而没想到的是这次我似乎想到了解决办法。

在写服务器程序时,将数据持久化到数据库,是一个必不可少的操作。它需要将一个结构体进行打包,然后通过网络发给数据库,数据库再进行,并将操作结果通过网网络返回给应用程序。虽然可以通过这样或那样的手段,降低这些步骤之间的延迟,但是其本身带来的开销还是远大于一次函数调用。

因此在写代码时,通常无法忽略持久化所带来的开销,需要尽可能的合并对同一对象的持久化。

然而合并过程往往没有那么美好,这会会频繁打断原本我们完美的抽象,让我们编写逻辑时总是需要随时背起一个思想包袱。

下面举个简单的例子。

在这个例子里,我们会有两个模块,一个是Hero模块对外提供对某个hero对象的操作(这里仅提供加攻击力和加经验),另外一个是Team模块,调用Hero模块提供的接口对一批hero进行操作(这里假设所有操作都是按队伍操作的)。

//Hero模块
struct hero {
int heroid; 
int attack; //攻击力
int exp;    //当前经验
int level;  //当前等级
};

std::unordered_map<int, struct hero> heros;

static void
persistent(int heroid)
{
    auto &h = heros[heroid];
    save_to_db(h);
}

void add_exp(int heroid, int exp)
{
    auto &h = heros[heroid];
    h.exp += exp;
    if (h.exp > exp_of_next_level)
        ++h.level;
    persistent(heroid);
}

void add_attack(int heroid, int val)
{
    auto &h = heros[heroid];
    h.attack += val;
    persistent(heroid);
}

//Team模块
void team_award()
{
    add_exp(1, 50);
    add_attack(1, 60);
}

上面的代码咋一看,很完美啊,高内聚,低耦合,API之间提供的功能也很正交。

但是它有一个致命问题,忽略了persistent函数所带来的开销,这个函数与普通函数是不同的。上面的代码一共会对同一个hero对象执行两次persistent操作。也就是整个开销扩大了200%,并且在我们编写业务逻辑时往往不止调用2个接口这么少。因此需要将team_award函数中将所有对heroid为1对象的persistent操作进行合并。

合并方法有多种,这里仅列出我最常用的一种(仅适用于1~3个同类型操作之间的合并,如果操作多而杂,这样做就非常不妥了),就是将add_exp和add_attack进行合并,提供如下函数,并在team_award函数中调用。

void add_exp_attack(int heroid, int exp, int attack)
{
    auto &h = heros[heroid];
    h.exp += exp;
    if (h.exp > exp_of_next_level)
        ++h.level;
    h.attack += attack;
    persistent(heroid);
}

这时代码开始有点’bad taste’了,很显然这是违反了‘正交性’原则的。在某些地方我们需要编写诸如`add_exp_attack(1, 0, 10)`类似的代码。然而我却一直没有办法,一直沿用至今。

直到今天我再次打开《UNIX编程艺术》时,我忽然发现了服务器程序的一个规律。那就是,服务器逻辑总是由‘客户端请求’和‘定时器超时事件’驱动的。

那么请处理完一个‘客户端请求’或‘定时器超时事件’之后应该就是最佳的持久化时机。

因此,只要我们在处理这两类事件需要持久化时设立Dirty标记,再由框架在每次处理完‘客户端请求’和‘定时器超时事件’之后根据Dirty标记去持久化所有改动的数据。困扰我数年的持久化合并问题就这么完美的解决了。

我们需要增加一个persistent模块,改动后的伪码大概如下:

//persistent模块
typedef (persistent_cb_t)(int key, int ud);
struct dirty {
    persistent_cb_t *cb;
    int ud;
};
std::unordered_map<int, dirty> persistent_cb;

void persistent_pend(int key, persistent_cb_t *cb, int ud)
{
    auto &d = persistent_cb[key];
    d.cb = cb;
    d.ud = ud;
}

void persistent_clear()
{
    for (auto &iter:persistent_cb) {
        auto &d = iter.second;
        d.cb(iter.first, d.ud);
    }
    persistent_cb.clear();
}
//Hero模块
struct hero {
int heroid; 
int attack; //攻击力
int exp;    //当前经验
int level;  //当前等级
};

std::unordered_map<int, struct hero> heros;

static void
persistent(int heroid, int ud)
{
    auto &h = heros[heroid];
    save_to_db(h);
}

void add_exp(int heroid, int exp)
{
    auto &h = heros[heroid];
    h.exp += exp;
    if (h.exp > exp_of_next_level)
        ++h.level;
    persistent_pend(heroid, persistent, 0);
}

void add_attack(int heroid, int val)
{
    auto &h = heros[heroid];
    h.attack += val;
    persistent_pend(heroid, persistent, 0);
}

//Team模块
void team_award()
{
    add_exp(1, 50);
    add_attack(1, 60);
}

//Socket请求处理模块
void socket_dispatch(int cmd, packet *req)
{
    switch(cmd) {
    case 1:
        team_award();
    }
    persistent_clear();
}
//Timer超时事件处理模块
void timer_expire()
{
    //调用所有超时回调
    persistent_clear();
}

由此我们完美解决了,代码抽象和合并持久化之间的矛盾。

谈谈我对数据同步的理解

We性质b和网游最大的不同也许就在于数据同步。

Web的工作流程(这里不包括页游)虽然也有很多变化,但是一般都大致分为三步。

1. 在浏览器输入网址, 浏览器通过HTTP协议请求服务器加载数据,服务器在收到HTTP请求之后,从数据库加载相应的数据(有可能是HTML,JS等一些用于浏览器渲染的数据)并返回给客户端。这一步我称之为查询

2. 浏览器收到服务器返回的数据之后,将数据渲染并呈现给用户。这一步我称之为渲染

3. 用户在看到浏览器呈现的内容之后,根据需要去执行不同的操作,这些操作为导致浏览器将一些数据发往服务器进行处理,这一步我称为提交

大部分Web逻辑除了在这三步之间循环之外,还有一个很重要的特点,那就是几乎很少与旁人进行实时交互。比如你在某论坛改了名字,也需要对方手动刷新才能看到。当然也有可以实现显示的,但那是极少功能才有的待遇(并且一般都是通过Hang住HTTP请求来实现的),这里不考虑这种情况。

因此,市面上对Web的高可伸缩性的研究,大都维绕着数据库来做。因为HTTP的数据同步量真的没有什么好研究的,这种模式几乎已经把数据同步量压缩到最低了。只有用户操作才会加载数据,这是多么节省的一种数据同步方式啊。


网游本身就是一个强交互的模式,玩家A做了一个操作,所有应该能看到玩家A的其他玩家都必须能看到玩家A做了什么操作(只是理论上,也许由于某种技能别人看不到)。

这样数据的同步量就会非常大,而且这种数据量,会随着同时在线的玩家的数量成指数性增加。

于是人们研究了各种减少数据同步量的算法,比如AOI、帧同步等。

这里我先私自把游戏分为开房间和大地图两种模式。

开房间模式的游戏,一般同一个房间的人数不会过多。所以最简单的做法就是,直接同步位置和状态。

每个人客户端移动过程中定时(比如10ms)广播坐标给房间内所有玩家,然后客户端根据收到的新坐标,做插值补偿。这又被称作影子跟随算法,即客户端实际表现的位置永远落后于其真正的位置。

如果客户端放了一个技能,就把这个技能效果广播给房间内的所有玩家。

但是这里会存在一个问题,如果这是一个延时类技能,比如几秒后生效,那么服务器在收到释放技能时就需要广播一次,当技能真正生效时,还需要再次广播一次。如果是一个每隔几秒就生效一次的buff就会更麻烦,每次buff生效,都要进行消息广播。数据量会远超于玩家的操作频次。

即然大部分数据量都是状态同步引起的,那么就把所有状态全部交给客户端自己运算,这就是帧同步的本质。客户端拥有整个游戏的全部运算逻辑,将整个游戏进程人为划分为逻辑帧,每个逻辑帧玩家上报自己的操作,由服务器进行房间内广播。客户端收到操作为自己还原各种状态。如果房间内有N个人,每个人操作M次,数据同步量只有M*N条消息,远低于之前的状态同步的数据量。这对于流量并不富裕的手机来说尤其是个好消息。

如何保证所有客户端逻辑和表现都一致,除了要做正确一逻辑帧操作还原外,还有一点很重要,就是复原随机逻辑(战斗中经常会有各种概率判断)。这一点可以通过伪随机序列来保证。


下面来看看大地图模式(这里的大地图模式,是指所有玩家在一张地图上,并且战斗过程中不切换场景)。

在大地图模式,所有玩家都在一张地图上行动,因此玩家数量与房间内的数量根本不是一个数据级(虽然有可能为了增加同时在线人数,会将地图进行分块处理。但即使如此,单块地图上的玩家也远大于房间内玩家数量)。

这也就意味着将数据(操作数据或状态数据)广播给地图上的所有玩家,是不现实的。所以必须要采用AOI算法,来选取需要收到这些数据的玩家。然后将这些数据组播给选取到的玩家。

在使用了AOI算法之后,一般来讲人数的量级与上面开房间模式需要同步的人数量级就差不多了。

那么是否使用了AOI之后,同样可以采用帧同步算法优化掉状态同步呢。

答案显然是否定的,上面也提到,所有的战斗系统一般都会有概率的存在,而一张大地图上必须也只可能有一个伪随机序列(因为玩家之间的视野是交错的)。这也就意味着所有的客户端不可能事先知道这个伪随机序列走到哪一步了(每场战斗都会使伪随机序列前进一步,如果要所有客户端都实时知道当前伪随机序列的进度,就必须在每一场战斗之后,将当前随机数广播给地图内所有玩家,这显然是不是现实的)。

从上面的分析可以得出一个结论,制约大地图模式使用帧同步算法的惟一因素,就是无法复原随机逻辑。那么如果我们游戏地图内没有随机因素(暂且不论是不是有可能),是否可以在AOI的基础上再使用帧同步算法的变种呢。

我们来分析几种情况来看看是否可行,这里需要强调一点,我们假设整个通信采用TCP(TCP具有FIFO性质)传输,服务器采用的是单线程模式。

1. 玩家B先看到了玩家A,然后玩家A被打了掉了5滴血,最终玩家A还有75滴血。

玩家B首先在视野内看到了玩家A,这时会同步到玩家A的血量为80.

然后B收到了玩家A被打的操作(这个操作固定伤5滴血),玩家B将80减去5得出玩家A还有75滴血的结果。显然这是正确的。

虽然可能buff之类带时间的逻辑不好控制,但是相信经过合理的设计,逻辑上应该不会有太大问题。

2. 玩家B还没收看到玩家A,然后玩家A被打掉了5滴血。

玩家B收到玩家A被打的操作消息后,发现自己视野内还没有加载出玩家A的数据(注意是从服务器加载到的数据,不是客户端还没有把模型之类的数据加载完), 于是将消息抛弃。

之后,玩家B收到的从服务器请求来的数据,A的血量为75。显然这也没有错。

所以在没有伪随机存在的情况下,完全可以使用帧同步算法的理论,进一步优化状态同步。

很巧我们最近开发的游戏,大地图上的表现确实不需要伪随机序列。


这次分析再次告诉我,一定要认清算法的局限在哪里,这样才能根据实际情况灵活组合运用。别人不能用,并不是你就一定不能用。

又一个lua调试器

最初,我并没有打算为Silly提供一个lua调试器,因为我本人不是一个重度调试器使用者。在开发期间出bug,看一下代码,打几条log可能比使用调试器会更快的找到问题,尤其是服务端程序,在很多时候其实只有log这一原始工具可以使用。但就我周围的人来推断,应该还是有很多重度调试器使用者。

因此,最终还是计划为Silly增加一个lua调试器作为基本组件存在。但是这个调试器到底以哪种方式提供调试功能,我一直在纠结中。

就我个人而言,我用过至少两种完全不同的调试器,gdb和dtrace(严格来讲dtrace可能不算是调试器)。

gdb主要用于开发期间进行阻塞式调试,虽然也可以写调试脚本用在生产环境中调试,但是在gdb加载符号文件时,延迟比较明显。

dtrace提供的是动态跟踪手段,在程序中放置相应的探针,当程序执行到探针的位置时,就执行这个探针上的函数。在放置探针时几乎没有卡顿延迟的现象,而且在放置探针后其对程序的整体执行性能影响甚小。因此在特殊时期可以用于生产环境调试使用。

最开始我觉得也许应该为Silly增加一个类似dtrace的调试器。这个调试器只提供一个probe接口,probe有两个参数,参数1是代码位置(文件名与行号),参数2是一个探针函数。当调用probe注册一个探针之后,代码执行到指定行时,就会执行调用probe时注册的探针函数。这样当线上出问题时,就可以像dtrace一样编写一段代码注入到程序中,将我们所关心的信息全部dump出来,而不会影响程序的正常执行。

但是,最近重新仔细思考发现,dtrace之所以可以如此高效,是因为他可以有各种加速手段。比如在增加探针时,可以通过调试信息快速定位到要增加的探针在CPU指令的哪个位置,还可以通过int 3中断被动触发探针函数等(这些只是大概的猜测,具体实现也许不同,但是至少可以证明的是,他可以非常高效的确定探针函数是否应该被执行)。而在lua中,即使仅仅确定什么时间探针函数需要被执行,也至少需要在全局hook事件”call”,在每次触发”call”事件时,遍历检测是否有探针触发。这会极大的拖慢程序的整体性能。因此即使实现了探针机制也不适合在生产环境做调试使用。

既然不可以在生产环境使用,那么做成类dtrace的方式也就没有必要了。如果是在开发期间使用,还是Gdb那种阻塞交互式调试最方便易用。

这不是第一次实现lua调试器了,两年前我就实现了一个非常简易并且低效的阻塞式调试器

当时我们的客户端代码采用lua编写,偶尔会出现一些偶发性bug,并且出错的地方总是一些没有提前预料到的地方,因此没有任何log。而当我们在出错的地方加上详细的log再重启客户端后,问题又不能被重现了。

这个调试器就是这种情况下产生的,他的作用仅仅是当出现偶发性bug时,能够在不重启客户端的情况下,打印出我们想要的上下文。因此在实现时一切从简,只有s(单步步入)、c(继续运行)、 b(设置断点)和 d(删除断点功能)的功能,并且没有考虑整个调试器的效率。


这次实现,希望除了要具备上一个调试器所有功能以外,还要支持gdb中命令n(单步步过)的功能。此外,它还应该是高效的。

在Silly中,所有的代码都是被包在某一个coroutine中被执行的,整个程序运行期间,可能会有数十或上百个coroutine并发执行。因此在调试某一个coroutine中运行的代码时,应该尽可能的保证其他coroutine应该可以不受调试器的干扰而正常执行。

这样就不能使用之前调试器中的方式(直接阻塞等待命令输入)来实现阻塞式调试器。因为那样会塞住整个Silly进程,所有的coroutine都会被卡住。因此,整个lua调试器的命令输入均来源于socket, 这样可以充分利用Silly自身的高并发能力而减少阻塞。

我把整个调试器实现成了一个调试状态机,共分为三个状态,分别是:checkcall, checkline、checkbreak。

程序运行时,整个调试器处于checkcall状态。在checkcall状态,调试器会检测所有的coroutine的”call”事件。只检测“call”事件可以最大程度保证程序的运行效率,而之所以会检测所有的coroutine,是因为这时还不知道被断点的代码将会在哪个coroutine上被执行。

每次触发”call”事件后,都会检测此函数中是否被设置断点。如果被设置断点,则进入checkline状态。

进入checkline后,将程序中所有的coroutine的事件检测取消,只保留当前coroutine的”call/return/line”事件,并且此后,所有针对事件检测范围的修改均只影响此coroutine。

在每个line事件被触发后,都要检测此行代码是否被设置断点,如果有则进入checkbreak状态。

需要说明的这里有一个可能存在的优化,比如下面代码。

function foo(x)
...
end

function bar()
local x = 3
...
foo(x)
local y = 10
...
end

假设在checkcall状态下触发”call”事件的是bar函数,并且有断点设置在bar函数内。这时调试状态机会进入checkline状态,如果foo函数中没有断点的存在,理论上我们只需要检测bar函数中所有行是否触发断点即可,也就是在执行foo函数时,不必触发”line”事件。这也是在checkline状态,我们需要检测”call”和”return”事件的原因。

checkline状态中,如果触发了断点,则挂起当前coroutine并进入checkbreak状态。

checkbreak状态主要处理用户命令输入比如b(设置断点)、d(删除断点)、s(单步步入),n(单步步过)、c(继续运行)等命令。

b/d/c命令都没什么好说的,无非就是向断点列表中增加删除断点信息,及将因为触发断点而被挂起的coroutine唤醒。

命令s的实现是参照Intel x86 CPU架构中的TF标志的思路,即如果单步标志位被置起,则每执行一行都会有触发断点的效果(当前coroutine被挂起等待,用户下一次命令输入)。

命令n在实现时,其实费了颇多周折。如果这一行的代码是调用一个函数,命令s会直接进入到这个被调用的函数的上下文并暂停执行并等待用户输入命令。而命令n则是直到这个被调用的函数返回才会暂停执行。

最开始是通过设置临时断点的方式来实现的,每执行一行,就为下一行设置一个临时断点,后来发现当函数执行到最后一行时,下一行的临时断点就失效了。

经过多次分析总结之后,发现命令n和s惟一的差别仅在于函数调用这里,其余情况下,n与s的作用一模一样。

有了这个关系,问题就简单多了。引入一个变量calllevel代表调用层数,每当call事件触发时,calllevel加1,每当return事件触发时,calllevel则减1。这样calllevel为0时,命令n就可以和命令s的处理方式相同。

这里同样有优化的空间,在“call”事件响应中,如果calllevel大于1,说明我只关心”return”事件,就可以把“line”事件的检测取消。

虽然我前面说要做一个高效的调试器,然而这个版本其实还是有很多可以优化的空间,比如可以重新设置断点列表的数据结构,以使在checkcall状态时可以尽快检测当前函数中是否有断点等。不过,至少这个版本,在使用lua debug hook上,我已经做到了尽可能的高效。

客户端缓存落地方案

先大致描述一下场景,客户端按登陆流程成功登陆后,开始按各个模块加载所需数据,待收到消息返回后cache在内存中,只有当所有模块全部加载完成之后,客户端才算真正登陆成功,这时玩家才可以进行各种操作。在玩家操作过程中,客户端不断与服务器进行消息交互,并始终与服务器数据保持一致(这里是指状态一致,不是指所有数据全部一致,服务端存储的数据与客户端所需要的数据并不完全相同)。

由于模块过多,每个模块都是分别独立加载,因此从用户点击登陆按钮开始到真正可以操作所经过的时间显得有些漫长。客户端同学提出,由于客户端内存中的数据与服务器保持一致,那么在客户端退出时将cache中的模块数据存储为文件。下次登陆直接跳过模块的网络数据加载过程,直接从本地加载。

刚听到这个想法,我被其惊艳到了,随后心里却隐隐感觉不妥,但是并没有发现有什么问题。

仔细思考后,终于知道哪里不妥了,玩家的某一个ID可能同时会登陆多个客户端,那么理论上每一个客户端都会有一份这个ID的cache,就需要所有客户端与服务器在玩家数据上保持一致。这明明是一个典型的分布式一致性问题,那么由CAP定理,问题不可能这么容易被解决。

后来他们又围绕着这个机制进行了进一步加强,服务器为每个玩家ID的cache落地后数据维护一个版本号,这个ID每登陆一次,客户端就对其自增并发往服务器进行存储。这确实会把问题概率降低好几个数量级,但是我觉得可靠性依然不够。

比如客户端将数据写入文件的过程中crash了,服务器在向数据库记录版本号时crash了等等都有可能导致数据的不一致性。虽然这个概率很低,但并不是没有可能。

最近受paxos影响颇深,就想着有没有办法在任意糟糕的网络状况下和数据落地可能出错(比如写文件或DB时crash了)的情况下保证数据的一致性。


先说一下登陆流程。

客户端持帐户名向LoginServer进行帐户认证,如果认证成功LoginServer会拿着帐号ID向GameServer索取一个session。当LoginServer成功获取session之后将uid和session一同返回给客户端。客户端再持uid和session到GameServer端进行登陆。其中session在GameServer端分配,规则为一直自增。

大致的想法是:

在GameServer登陆之后,服务端向客户端返回GameServer的启动时间戳StartTime和下次从LoginServer登陆时将会拿到的session(这里称为next_session),next_session在GameServer整个启动周期内(从启动服务器进程到进程退出)有效。客户端在收到登陆成功消息之后将next_session和StartTime存入内存,当进程退出时首先所有数据落地完成之后,再将next_session和StarTime字段一起进行落地。

下次在从LoginServer认证成功,获取到session后,与本地存储的next_session进行比较,如果一致则说明中间没有人登陆过,那么数据一定是一致的。由于session是在GameServer整个启动周期内有效,所以如果中间服务器重启session会0开始分配。因此除了需要比较LoginServer返回的session与上次获取到的next_session是否一致之外还需要比较本次GameServer返回的StartTime与上次落地的StarTime是否一致。

整个算法的一致性可以很容易进行证明。

因为每次登陆成功在GameServer端是一个原子操作,而session的分配是直接在内存完成的,不存在操作数据库的行为,也一定是原子的。登陆成功和分配next_session在一个消息中被处理,因此整个操作一定是原子的,这保证了session的有效性。即然保证了服务端session的正确性,那么客户端只要保证在所有模块数据落地之后再落地next_session和StartTime就可以保证数据的一致性。不管是服务器和客户端在哪一步crash其实都无关紧要。

正如CAP定理所说的一样,这个算法虽然保证了一致性,但是会有两个缺陷。

1. 由于session是个4字节无符号整型,因此如果每秒有1000个人登陆,24天后就会回绕。因此如果一个客户端上的数据24天内都没能动过,不管session是否一致,都需要在登陆时重新向服务器拉取新数据。

2. 为了保证session分配的原子性和有效性,session是不存DB的(如果对DB进行存储则有两种方案,一种是等DB成功返回之后, session才分配成功,这样会增加登陆时间,第二种是将存储session的消息发向DB直接返回分配session成功, 这样会有数据不一致的风险),因此每次停服维护之后,玩家第一次登陆一定是需要拉取全新数据。

理清上述算法逻辑之后,对比最初客户端同学提出的算法,其实只要将Server端版本号的改成纯内存版,就可以解决Server端crash引起的不一致问题,将客户端版本号在最后所有模块落地之后再落地,则可以解决客户端存储时crash数据不一致问题。那么看来我之所以没在原版基础上去思考改进,可能是因为我当时正在看登陆逻辑的代码:D


绕了一大圈,不管哪种算法都挺累的。

回过去再看看,最根本的问题其实是模块过多加载数据过慢,而缓存落地只是为了解决它,又引申出来的一系列问题。

那么我们真的非要落地才可以解决模块加载慢的问题么,我不这么认为,分布式数据同步一定是复杂的,所以如果有其他办法来解决加载慢的问题,分布式肯定不是首选。

站在服务端的角度,只要客户端登陆成功了,不管客户端是否需要发消息加载数据,服务端都必须要把这个玩家的所有数据加载入内存。因此玩家登陆慢与游戏服务器的数据加载没有一点关系。

再看一下加载过程可能出现的问题。

1. 频繁发包,导致系统调用过多,开销过大
2. 各模块数据加载之间可能有数据依赖,即必须等一个模块返回后,才能请求另一个模块
3. 模块加载的数据过多,流量过大,带宽不足,所以网络传输时间长

从之前的经验来看,一般客户端登陆时拉取的都是一些最基础的信息,这些信息每个模块都很小(几十到几百个字节不等)。只有真正点开模块的UI时才会加载更详细的数据。因此问题3不存在。

问题1肯定是存在的,至于到底对加载过慢产生了多少影响,需要经过仔细评测才能得出结论。

不管怎么样,先把所有模块的加载协议合并,对比一下最初的加载过程,看看有多大差距。

在游戏服务器判断,此连接有合法Session之后,收集所有模块的基础信息,将其打包与登陆成功消息一起返回到客户端。客户端不再为每个模块单独请求数据。

下面来估算一下修改前和修改后的开销。假设游戏有30个模块,每个模块的基础信息是100字节。

30个模块单独加载数据,请求数据和回应数据至少需要30次write和30次read,一共60次系统调用,同样会有30个请求包和30个回应包,一共60个包。(在没开启nagle算法的情况下)

所有模块数据在登陆成功之时,由服务器收集并将其跟随登陆成功消息一起返回给客户端,不需要再多调用一次系统调用。30个模块的数据总大小为30 * 100 = 3000字节,而一个MTU大概为1500个字节左右,估算下来大概只有3个包左右。

优化前后,系统调用个数比是30比0,数据包个数比是60比3。而数据包越多,在网络上迷路的概率就越大。

事情到这里还没有结束,再分析一下客户端从LoginServer认证到从GameServer的登陆过程。

客户端到LoginServer会经历一次公网Connect时间和一次公网RTT。到GameServer会再经历一次公网Connect时间和一次公网RTT。如果客户端从LoginServer认证,LoginServer到GameServer之间会再经历一次内网RTT。

如果客户端从LoginServer认证并在GameServer登陆成功之后将得到的session存储,下次启动时从外存中加载session并按某种约定算法(比如将session自增,GameServer每次认证成功后也将此uid所关联的session自增)生成新的session, 直接向GameServer认证。就可以省掉一次公网Connect时间一次公网RTT和一次内网RTT。

其中公网Connect是非常慢的,通过都会在几十到几百毫秒,而一次公网RTT也至少要10毫秒以上。在网络情况一般的情况下,就这一项优化都可以减少掉数百毫秒的开销。

相比那个分布式的方案,我个人更喜欢这个,简单而有效而不会引入过于复杂的问题。

Paxos算法

大神说,世界上只有一种一致性算法,那就是Paxos。 但是大部分文章或论文的套路都差不多,先说paxos是一个完美的一致性算法,然后就给出证明等等,最后才给出实现步骤。

然而,对于我这个初学者来讲,我更希望先知道这个算法是如何工作的,然后再去研究他们的证明过程。这其实也符合学习的过程,先抛出问题,思考之后,最后看答案印证。然而大神写的Chubby并不开源,而证明过程也很数学化,很难理解在实际执行流程当某一步出现错误时,这个算法是如何保证数据的一致性的。

本文从paxos算法实际运行过程来对《Paxos Made Simple》和《The Part-Time Parliament》做一下补充。在该算法中有三种参与角色,分别用Proposer、Acceptor、Learner来表示, 下面先给出Paxos的算法执行流程(来自Paxos Made Simple)。

阶段1:(协商编号阶段)

a. Proposer选择一个提案编号为n,然后向Acceptors中的大多数人发送编号为n的Prepare请求
b. 如果一个Acceptor收到一个编号为n的Prepare请求,且n大于它已经响应的所有Prepare请求的编号,那么他就会Promise它不会再Accept任何编号小于n的提案,同时会将它已经通过(Accept)的编号最大的的提案作为响应。(一个提案由’编号n’和’值value’组成)

阶段2:(协商提案阶段)

a. 如果Proposer收以半数以上的Acceptor对于它的Prepare请求(编号为n)的响应,那么它就会发送一个编号为n, value为v的提案的Accept请求给那些Acceptor,这里v是收到的响应中编号最大的提案的值,如果响应中不包含提案,那么它就是任意值。(一个提案由(n,value)组成)

b. 如果Acceptor收到一个针对编号为n的提案Accept请求,只要它还未对编号大于n的Prepare请求作为响 应,它就可以通过这个提案。

阶段3:(选定(Choose)一个值,注:此阶段由《Paxos Made Paxos》 2.3浓缩而成)

当一个提案的Accept请求已经被大多数Acceptor接受,这个值就是被Choosen了。


下面开始分析,这个算法是如何保证一致性的。

分析1. 可能有多个Proposer同时进行, 就一定有并发问题,来看看Paxos如何解决并发问题

对于单个Acceptor, 阶段1.b可以保证提案的编号只能被用一次,而且一定是递增的。配合阶段2.b则可以保证一个ID(编号n)最终只会与一个值相对应。

这个思路有点像是无锁队列,先原子获取到队列的位置(编号n),由于原子获取队列的位置,所以每一次获取的位置都是惟一的,这样向队列中放置值是不会有并发问题的,因为每个线程操作的其实是不一样的位置。(只不过Paxos这个队列的长度只有1个长度,永远是最大的ID(编号n)代表着这个队列的惟1位置)。而获取ID的原子性,是通过在Acceptor端保证的。

分析2. 为什么需要大多数Acceptor都同意

假设两个大多数集合分别为A和B,集合A集合B中必然有一个公共成员(假设所有成员为X,Y,Z三个成员,集合A中成员为X,Y, 那么不管集合B如何选择,只要他的成员数大于所有成员数的一半,集合B就至少要包含集合A中的一个成员X或Y),。由于A中成员是全部Accept了Accept请求,因此集合B中必然会有一个成员作为A中成员Accept过最新的Accept请求。

分析3. 仔细阅读论文就会发现,论文中有零星片语提到过“一个Paxos实例(instance)只能确定一个值,这个值一旦确定就永远不能更改。如果想确定多个值,需要启动多个Paxos实例(也叫MultiPaxos)”。所以下面仅仅分析一个实例如何保证这一个值是一致的。

阶段2.a保证,一旦收到的大多数Prepare的响应后(假设这个大多数为集合A),那么发送给Acceptor的值必须为集合A中Acceptor在阶段1.b中返回的提案集合B中编号最大的提案的值。配合上面的分析2,就可以推导出阶段3的结论,因为如果一个Accept请求(携带值v)被大多数Acceptor接受,那么之后再发送任何Accept请求,其值都一定是被大多数Acceptor接受的那个提案的值。之后这个值永远不会再被变更,因此一致性得到了保证。


上面是理想情况分析,再来分析几种异常情况。

假设共有A,B,C,D,E共5个Acceptor节点,将阶段1称为
P阶段,阶段2称为A阶段, P1为第一次Prepare,P2为第二次Prepare。A1,A2同样代表第一次和第二次Accept。

1. P1(编号为n1)发送给了A,B,C三个节点,A,B节点执行并响应成功,但是节点C对P1响应失败,接着发送P2给C,D,E三个节点并且得到成功的响应。

P1的失败分为两种,一种是C节点执行P1失败了,还有一种是C节点执行P1成功了,但是对P1的响应包丢了。

如果P1执行成功了,那么C,D,E集合由于集合C的存在,就可以保证P2发出的编号n2一定是大于n1的,

如果P1执行失败了,发送给C,D,E集合的P2请求中的编号则可能与n1相同。

但是由于P1的失败导致A1并没有被请求,而是接着执行了P2。将最近一次被选定(Choosen)的提案编号称为n0,那么n2 >= n1 > n0。这并不违反Paxos协议。

2. P1(编号n1)发送给A,B,C三个节点,并且执行成功。A1发送给A,B,C三个节点后,只有C节点失败了(比如发向C节点的A1请求,在传输过程中丢失了)。

由于P1的成功,可以保证P2的编号n2一定大于n1。

A1同样有成功和失败两种可能。

当A1被执行成功,C,D,E集合在执行A2时,由于阶段2.a的存在,发送给C,D,E集合的A2请求中的值一定是节点C上在A1时被设置的值v1。

当A1被执行失败时,C,D,E集合在执行A2时,可能是一个与v1完全不同的值v2。

如果C,D,E对A2请求全部执行成功,则之后不管再发什么请求,这个值始终会为v2。

到此值v2被选定(Choosen)。

3. 继情况2之后,如果C,D,E部分成功,比如只有D和E成功了.此时A,B的值为v1,D,E的值为V2,C的值为v0(即发送P1命令之前的值)。

接下来提案的选取过程又会至少有两种情况。

如果选取了A,D,C,那么此时最终被Choosen的值为v2(因为n2>n1)。

如果选取了A,B,C,那么此时最终被Choosen的值为v1(因为n1 > n0)。

至此整个值被Choosen,整个Paxos协商过程达到稳定。


上面并没有分析多个Proposer并发请求P和A时,结果是否正确。这是因为在分析之初我们就已经确定,编号n的存在可以解决并发问题。

但是编号n只能保证并发情况下不产生错误结果,但是并不保证在并发的情况下,在有限时间内可以有某个值被Choosen这一点,也即活锁,这个可以通过选取Leader来实现。但这只是优化手段,这里就不讨论了。

比如两个Proposer按P1,P2,A1,A2这样的序列发送请求,就永远不可能最终选定一个值。

文字的描述总归是没有代码描述更具体,尤其是可以轻易运行的代码。

ps.在读两篇官方论文时,需要特别注意’accept’,’choosen’,’instance’这三个词。Accept只代表某一个Acceptor节点接受了某个提案,但是choosen代表至少大数多Acceptor都Accept了某个提案。从开始Paxos流程到最终确定一个值称一个instance,如果想确定多个值就必须通过多个Paxos Instance。

HTTP服务器的特点

最近一个月在学习关系性数据库mysql, 顺便看了一下http服务器的编写。写了这么久的游戏服务器,数据库也一直使用nosql。因此在初次尝试使用mysql编写http服务器程序时,产生了强烈的反差。

在使用APP的验证过程中,经常会遇到短信验证码问题。

下面就以‘如何实现短信验证码服务’来对比一下http服务器和游戏服务器(mysql和nosql)解决此类问题的不同之处。主要涉及数据结构定义、优化、及逻辑代码的更新问题。

先来明确一下‘业务流程’,最简单的‘短信验证码服务’至少要提供3个操作:

1. APP向‘短信验证码服务’发送请求获取验证码
2. 其他服务向‘短信验证码服务’发送请求校验验证码是否正确(这里的‘其他服务和‘短信验证码服务’有可能是同一个服务,这里只是假定,‘短信验证码服务’被单独实现为一个微服务)
3. 定期删除超时的短信验证码(这里验证码超时时间为5分钟)

先说执行流程:

http服务器的每次请求都是相互独立的,即每个请求都是先查询当前DB(这里假设使用Mysql)的状态,然后将状态写入内存,然后根据内存中的状态执行逻辑,然后把处理结果写入DB,释放所有资源(这里仅仅是理论上,比如可能连接DB时会采用连接池,那么释放时也仅仅是把链接归还到链接池而已)。而这里要实现的‘短信验证服务’基本上属于纯DB操作,因此下面直接展示sql语句,逻辑代码直接略过。

而游戏服务器则不太一样,一般会把要操作的数据提前加载入内存,当处理请求时,直接根据当前内存的状态,来处理逻辑,最后把结果写入内存,并极据不同的策略更新到DB。也就是说,不管DB定义的数据结构是怎样的,进程内的数据结构才是直接影响请求处理效率的关键。

先来看按‘http服务器’如何实现‘短信验证服务’。

首先定义mysql中的数据结构:

create table verifycode (
	phone bigint unsigned not null primary key,
	code int unsigned not null,
	time timestamp not null
);

为电话号码为‘100000000’生成一个短信验证码:

insert into verifycode (phone,code) 
values (100000000, floor(rand() * 10000)) 
on duplicate key update 
time= current_timestamp(),code=floor(rand() * 10000);

为‘其他服务’提供电话号码为‘100000000’验证码为10005验证功能:

select count(*) from verifycode where phone = 100000000 and code = 10005;

定期删除过期的验证码(此段代码需要开个定时器执行):

delete from verifycode where 
time < DATE_SUB(CURRENT_TIMESTAMP, INTERVAL 5 MINUTE);

再来看看如果按‘游戏服务器’的方式该如何实现(直接在进程内操作, 以C++的方式呈现)。

定义数据结构:

struct verifycode {
        long int phone;
        int code;
        time_t time;
};
std::unordered_map<long int, struct verifycode> verifycode_pool;

为电话号码为‘100000000’生成一个短信验证码:

auto &c = verifycode_pool[++codeidx];
c.code = rand() % 10000;
c.phone = 100000000;
c.time = time(nullptr);

为‘其他服务’提供电话号码为‘100000000’验证码为10005验证功能:

auto iter = verifycode_pool.find(100000000);
return (iter != verifycode_pool.end() && iter->second.code == 10005);

定期删除过期的验证码(此段代码需要开个定时器执行):

time_t now = time(nullptr) - 5 * 60;
for (auto iter = verifycode_pool; iter != verifycode_pool; ) {
        if (iter->second.time < now)
                iter = verifycode_pool.erase(iter);
        else
                ++iter;
}

对比一下mysql版本和C++版本的短信验证码服务。可以发现,C++版本的代码基本上就是mysql版本中sql语句的翻译。

也就是说到目前为止,除了http服务器每一个请求都会重新读取Mysql和写入mysql的设计原则与游戏服务器不同外,设计思路上完全一致。


但是上述实现有几个问题。

1. 定期删除过期验证码,需要扫描整张表,时间复杂度为O(N),在有大量验证码的情况下,一次清理就会卡整个进程或整张表,导致”Stop The World”,而mysql在不使用索引的情况下,扫描整张表会更慢。
2. sql语句使用了now(),rand()之类的函数,这将导致mysql查询缓存失效(mysql版’短信验证码服务’特有问题,这个可以通过在应用程序中生成常量值来替换sql语句中的now/rand函数,下面优化不再列出)

为了解决删除过期验证码过慢的问题。

‘http服务器’的优化版本需要做出如下修改,为time字段添加索引:

create table verifycode (
	phone bigint unsigned not null primary key,
	code int unsigned not null,
	time int not null,
        index(time)
);

而C++版本则需要重新设计数据结构, 并实现相应的算法。

采用Time Wheel的方式,将过期的Key直接为300组,超时直接删除整组。

time_t lastupdate = now();
std::unordered_map<long int, int> verifycode;
std::unordered_set verifyexpire[5 * 60];

为电话号码为‘100000000’生成一个短信验证码:

int idx = now() / (5 * 60);
verifycode[100000000] = rand() % 10000;
verifyexpire[idx] = 100000000

为‘其他服务’提供电话号码为‘100000000’验证码为10005验证功能:

auto iter = verifycode.find(100000000);
return (iter != verifycode.end() && iter->second == 10005);

定期删除过期的验证码(此段代码需要开个定时器执行):

time_t now = time(nullptr);
while (lastupdate <= now) {
        int idx = lastupdate % (5 * 60);
        auto &e = verifyexpire[idx];
        for (auto phone:e)
                verifycode.erase(phone);
        e.clear();
        lastupdate++;
}
lastupdate = now;

从优化后的代码,再来对比一下两者的优缺点。

HTTP服务器,特点:
1. 业务逻辑每个请求都需要读取写入数据库,因此相比游戏服务器的方式来讲会请求会慢很多
2. 业务逻辑均采用关系数据库来进行存储(这是并不是绝对的,现在很多服务器已经开始采用nosql来存储了), 一般只能维绕着sql语句和索引进行优化
3. 数据与逻辑分离,可以动态热更新逻辑代码
4. 数据与逻辑分离,当业务请求能力处理不足,而瓶颈不在DB时,可通过增加逻辑服务器来动态扩容,具有极大的可伸缩性
5. 合理的DB集群架构设计,当DB达到瓶颈时,可动态扩容

游戏服务器,特点:
1. 数据均在进程中内存进行操作,可扩展性差。
2. 由于进程中内存残留业务逻辑状态,几乎或很难进行逻辑代码的热更新。
3. 不同的业务模型需要根据情况设计,才可以使集群具有可伸缩性,不像HTTP天然具有可伸缩性。
4. 数据表现力强,可以充分利用编程语言提供的各种表现方式,优化形式多样。
5. 所的请求全部基于内存状态进行处理,处理速度快

ps.mysql中的InnoDB索引采用B+Tree来实现,因此time字段加上索引后,单纯的从算法上与使用TimeWheel实现的C++版本相比,时间复杂度上并不会有显著区别。在更复杂的应用场景,DB和编程语言实现过程中的优化形式可能会相差甚远,但其本质上也是相同的,都是尽可能快的提高访问速度。

实现了一个AOI模块

在场景服务中,如果有一个人A的行为想要被其他人看得到,就必须将A的数据包进行转发给其他人。

最KISS的办法,就是直接把A的数据包直接在场景服务内组播。

但是在一个场景服务中可能有成百上千个人,如果直接在服务进程内进行广播,数据流量会大到一个很夸张的地步,至少以目前的网速来讲是不现实的。

因此,往往场景服务都为人物设计一个视野半径,即只将数据包转发给在我视野内的人,这样可以极大的降低数据的转发流量。

而AOI(Area Of Interest)正这样一个可以帮我们快速确定视野内有多少人的模块。

研究了一下,AOI最普遍的实现方式一般有两种。一种是十字链表法,一种是9宫格来实现的。

两种方式各有优缺点:十字连表在插入时,时间复杂度是O(n), 而9宫格的空间复杂的相对地图来讲空间复杂度是O(n)。

为了尽可能的高效,我最终使用9宫格的方式来实现

为了简化实现复杂度,在整个AOI空间中的人具有相同的视野(不存在近视眼:D), 这样我们就可以依赖一个事实,A能看到B,B就能看到A。

API设计如下:

struct aoi;
typedef void *(* aoi_alloc_t)(void *ud, size_t sz);
struct aoi *aoi_create(float region[2], aoi_alloc_t alloc, void *ud);
void aoi_free(struct aoi *aoi);
void aoi_leave(struct aoi *aoi, int id);
void aoi_move(struct aoi *aoi, int id, float coord[2]);
int aoi_detect(struct aoi *aoi, struct aoi_event **event);

aoi_create用于创建一个AOI空间,在创建时,你可以传入自定义的内存分配器来帮你实现一些特殊的需求。

aoi_free用于释放一个AOI空间,但是aoi_free并不负责释放struct aoi结构所占用的内存,需要由上层应用根据具体情况去释放struct aoi所占用的内存。

之所以这样设计,是因为考虑到将AOI库嵌入到一门含GC的语言中(比如lua),alloc所创建的内存是不需要显式释放的。

我们可以在手动管理内存语言(比如C)中创建和释放可能是这样的:

void *alloc(void *ud, size_t sz)
{
        (void)ud;
        return malloc(sz);
}
struct aoi *aoi = aoi_create(region, alloc, NULL);
aoi_free(aoi);
free(aoi);

而如果在自动内存管理的语言(比如lua)中可能是这样的:

struct aoi *aoi = aoi_create(region, (aoi_alloc_t)lua_newuserdata, L);
aoi_free(aoi);

因为lua_newuserdata创建的内存是由luaVM自己释放的,并不需要aoi_free来显式释放。

上层应用为每一个人(实体)分配一个惟一ID,在人物移动时调用aoi_move来更改坐标。

在调用aoi_move之后,aoi模块会将产生的事件,压入事件队列。

而aoi_detect函数则用来从事件队列中取出一个事件。返回1就代表返回了一个有效事件,如果返回0就代表没有事件返回。

所以一种典型使用方式是:

struct aoi_event *e;
aoi_move(aoi, id, coord);
while (aoi_detect(aoi, &e)) {
        //do anything you what
}

如果在调用aoi_move之后没有及时调用aoi_detect来取出事件,事件会被缓存直到下一次调用aoi_detect。

为了方便AOI模块嵌入其他语言或做成一个独立的服务存在,就必须要尽可能的减少aoi模块与上层模块的数据交互量。

AOI模块只向上返回‘进入’和‘离开’人物视野事件。

每次调用aoi_move只产生与上次结果相比的差集。即只返回此次移动新‘进入/退出’视野事件。

至于视野内的坐标移动,上层应用可以采用任意的处理方式,可以不需要AOI模块的参与,比如,为每一个人建立一个周围人列表,视野内移动直接转按周围人列表组播即可”

实现细节很简单:

将整个地图空间打成一个一个小格子,格子的精度需要根据具体情况来做权衡。格子过大,会导致视野内人数过多,组播时流量会增大,格子过小会导致人物频繁发生‘进入/离开’视野,同样增加数据通信流量。

每次移动时,根据当前所在坐标,半径三个元素,找到旧的视野范围A的格子。再根据新的坐标和半径找到新的视野范围B格子。然后求出A和B的差集。

再根据A和B的差集就可以产生,此次移动所产生的新的事件。

一个高可伸缩的游戏服务器架构

设计完socket通讯协议后,就面临着服务器架构设计了。我希望他是一个去中心化且具有高可伸缩性的集群架构。

水平扩展是高可伸缩的首要条件,因此,在设计之初就必须考虑好水平扩展考方案。事实上这一部分几乎花了我1整个月的时间来设计,在此期间我重写了3版才总算确定下来我认为可用的方案。

第一版设计方案如下:

将服务器分为3类,分别是GateServer, LoginServer, LogicServer。

GateServer管理客户端链接,数据包的加密、解密、广播、转发等与业务逻辑无关的操作。当压力过大时可通过部署多个实例来水平扩展。

LoginServer处理游戏帐号认证,为客户端分配一合适的GateServer(可能是负载最轻),为客户端与GateServer连接分配临时密钥等操作。

客户端通过连接LoginServer分配的GateServer来进行游戏。如果需要限制玩家单人登陆(同一个帐号同时只能有一个socket来管理), 则只能部署一个,如果压力过大,可做登陆排队处理。

LogicServer是游戏业务逻辑服务器,可根据业务类再行分类。每个业务类型服务器可单独部署一份。

每一个LogicServer在启动时向GateServer建立一条socket连接。并把自己可处理的协议ID发送给GateServer进行注册。

当GateServer收到客户端协议ID后,根据LogicServer注册信息来将不同的协议内容转发给不同的LogicServer服务器处理。

LogicServer接收GameServer转发来的协议后,将处理结果发回源GateServer,再由GateServer处理后发回给客户端。

LogicServer之间根据业务模型的需求直接进行互联。

例如:有一个RoleServer(LogicServer类型)进程和一个SceneServer(LogicServer类型)进程,如果SceneServer在业务逻辑中需要RoleServer提供一些支持。那么SceneServer直接对RoleServer进行连接并请求,不需要任何中心服务器结点。

很容易发现,这个架构的瓶颈一定是在LogicServer的定位上。假如单个RoleServer不足以承载足够多的人,而RoleServer内部的逻辑又交互很密切,RoleServer所承载的最大人数将是整个架构的所能承载的最大人数。这严重制约了整个架构的伸缩性。

因此,想要提高整个架构的伸缩性,就必须要让”同一业务类型服务器”可以部署多个实例。


在第二版的设计中,LogicServer向GateServer注册协议ID时,顺便通知GateServer其本身是否有可能会被布署多份实例。

GateServer在向LogicServer转发协议时根据其是否’可能会被被部署’来做不同的处理。如果此LogicServer是可能会部署多份的,则用hash(uid)的值来确定将此协议内容转发到具体哪一个LogicServer服务器。

事情往往没有看上去那么美好,在实现SceneServer时,发现上述规则并不适用。因为SceneServer如果部署多个实例,一定是按地图区域划分的,与hash(uid)没有必然联系。如果要对SceneServer进行正确的消息转发就必须要新增一种LogicServer的子类型。

同样,如果新增某个业务逻辑服务器需要另外一种转发逻辑,就需要同时修改GateServer的转发逻辑。这与框架与业务逻辑解耦的初衷不符。

看起来已经不可能完全保证,在业务逻辑变动的情况下,完全不修改GateServer的代码了。


因此在第三次实现中,我把转发逻辑独立出来,交由业务逻辑处理。

在GateServer中增加了一个元素Agent。框架本身不提供Agent的实现,只提供Agent类的接口。具体的Agent由业务逻辑实现。

在每一个连接到来时,GateServer为其分配一个Agent对象。当客户端消息到来后,GateServer将其交由对应的的Agent对象处理,GateServer不再负责具体的转发逻辑。由此来将业务逻辑代码彻底剥离开来。

假设整个集群部署如下:

有一个GateServer, 两种不同的业务类型的LogicServer。每种LogicServer分别部署N份实例

+-----------------------+ +-------------+ +-------------+
|                       | |             | |             |
|         Gate          | |             | |             |
|                       | |             | |             |
|  +-------+ +-------+  | |             | |             |
|  |       | |       |  | |             | |             |
|  | Agent | | Agent |  | |             | |             |
|  |       | |       |  | |             | |             |
|  +-------+ +-------+  | | LogicServer | | LogicServer |
|                       | |             | |             |
|  +-------+ +-------+  | |  Role x N   | | Scene x N   |
|  |       | |       |  | |             | |             |
|  | Agent | | Agent |  | |             | |             |
|  |       | |       |  | |             | |             |
|  +-------+ +-------+  | |             | |             |
|                       | |             | |             |
+-----------------------+ +-------------+ +-------------+

那么从业务逻辑层面来看,其实就相当于每一个Agent对象分别包含了一个Role Server实例和一个Scene Server实现。如下图:

+-----------------------------+
|                             |
|            Agent            |
|                             |
|   +----------------------+  |
|   |                      |  |
|   |        Role x 1      |  |
|   |                      |  |
|   +----------------------+  |
|   +----------------------+  |
|   |                      |  |
|   |        Scene x 1     |  |
|   |                      |  |
|   +----------------------+  |
|                             |
+-----------------------------+

整个集群一种可能的工作流程是这样的:

帐号认证过程(LoginServer部分):

1. 客户端连接LoginServer进行认证,LoginServer首先检查客户端认证信息是否合法。

2. 如果合法接着检查此帐号是否已经在线,如果在线,则找到此帐号在线的GateServer,并向其发着kick命令。

3. GateServer向LoginServer回应kick成功

4. LoginServer为当前帐号分配GateServer,向GateServer请求为此uid生成一个合法token。

5. LoginServer将GateServer的IP和Port及token返回给客户端

游戏过程(GateServer部分):

1. 客户端拿着从LoginServer获取到的ip和token去连接GateServer并进行认证。

2. GateServer收到新的客户端连接就为其新建一个Agent对象,此后便将此连接所有消息都效由Agent对象处理。

3. GateServer收到LogicServer发来的消息后,根据此消息所属的uid找到对应的Agent来处理,然后把消息交由Agent来处理。

游戏过程(Agent部分):

1. 收到GateServer传递过来的由客户端发来的消息,找到其对应的服务器类型,然后根据此服务器类型需要的转发逻辑来转发到相应的LogicServer中去处理。
2. 收到GateServer传递过来的由LogicServer发来的消息,将其转发给对应的客户端连接

上述过程只是一个整体上的过程,有很多细节都没有详述。比如GateServer可能把消息解密再传递给Agent处理, LoginServer与GateServer可能还需要交换密钥等。

BTW, 处理多连接绝对不是一件容易的事,在第三版方案确定好,又重写了两次才终于把逻辑理顺。

关于网络协议封装的一些新想法

最近业余时间在写一个小游戏。在为客户端封装socket层时头脑一热,有了一些新的想法, 在这里记录一下。

客户端使用的是Unity3d引擎。而在Unity3d中,基础的socket库只提供两种模式,一种是阻塞模式,一种是异步callback模式。

一般都需要基于这两种模式下进一步封装,才可以更方便的使用。

咨询了几个做客户端的并搜了一下,发现大家的惯用手法都是开一个线程去使用socket阻塞去读,然后把读到的数据通过队列传回主线程进行处理。

但是也许是单线程的思维模式已经深入我心了,所以我个人并不是很喜欢这个实现。

在我的设想中,我希望能够在直接在主线程完成对socket的读写及拆包工作。这仅仅是客户端自己的数据,理论上量不会太大,所以即使把这部分工作放入主线程也不会影响渲染。

但是在这种设计下,阻塞模式和异步callback模式都不太合适。因为阻塞模式在read时会使主线程卡住影响渲染,而callback模式则很容易掉入callback hell。

只有非阻塞模式才能满足需要。即,调用socket.read函数时,可以传入任意大小的长度,但是不管有没有读到数据socket.read一定会立即返回。

基于callback模式重新抽象出了NetSocket模块

NetSocket模块提供了Connect, Read, Send, Close等4个接口。

NetSocket.Connect提供非阻塞连接而NetSocket.Close提供非阻塞关闭。
NetSocket.Read可以指定任意读取长度,但是不管是否能读取到数据,它都会立即返回。
NetSocket.Send可以发送任意长度数据,并且一定会立即返回。

有了这一组接口后,就可以在主线程毫无顾及的去操作socket而不用担心阻塞及并发问题了。


有了可用的socket组件,下面就需要封装协议包的组成布局了。

为了不粘包,一般都会首先在包头加2~4个字节的包长,指出后面还有多少个数据属于当前这一个包的内容。这个包头长度一般用于数据包拆分。

不管是客户端还是服务器,都需要有一个东西,可以识别这个数据包的内容是什么,那就是command id,即协议ID。

一般来讲client向server请求的并不是都可以成功,如果出错,服务器需要指出这个协议ID的出错信息,即错误码。

而几乎99%的协议请求都不能100%保证必成功,因此将错误码加入包头部分是合理的,那么一整个协议包的内容可能就是这个样子的。

————————–
|包长度|协议ID|错误码|协议内容|
————————–

如包长度,协议ID和协议内容出现在协议包内都是毫无疑问的事,但是错误码很让人纠结。

虽然99%的请求都不一定100%成功,但是也并不会100%失败。而在请求成功时,协议包依然携带了一个0错误码(一般0为Success),我认为这是一种无意义的浪费。

在纠结了一段时间之后,我修改了协议包的组成布局。将错误码从包头中去掉,如下:

———————
|包长度|命令码|协议内容|
———————

至于返回错误码,我把这件事交给了一个通用协议,协议内容定义如下:

        struct error {
                int cmd;
                int err;
        }

所有请求出错后,都不再返回相应的协议ID,而是用一个ERROR的协议取代。ERROR协议ID对应的协议结构体是error。

error::cmd用于指出是哪个命令出错了,而error::err用于指出这个命令的出错码。

在接收到ERROR协议之后,上层自动将ERROR协议转换为error::cmd所对应的协议,调用并将error::err作为错误码传给error::cmd对应的处理函数。

由此,我们就可以做到,如果不需要错误码,就不必承受它所带来的开销。


封装完数据包结构,下面就是封装协议序列化了。

发送功能一般没什么好说的,序列化成byte array,然后直接发出去即可。

接收协议就比较麻烦,因为不管怎么样总觉得这样不够完美。最常用的封装方式一般如下:

//Module1.cs
void process_cmd1(int cmd, byte[] dat)
{
        cmd1_packet ack = new cmd1_packet();
        ack.pares(dat)
        //do some for request
}

//NetProtcol.cs
void process() {
        ...
        //int cmd;
        //byte[] data;
        //假设cmd和data已经读取完毕,准备进行反序列化
        //假设所有的通讯协议结构均采用类protobuf之类的方式定义
        switch (cmd) {
        case CMD1:
                Module1.Instance.process_cmd1(cmd, data)
                break;
        }
        ...
}

这种方式最大的问题就是,随着命令条数的增加,case会越来越长,不利于阅读。并且每一个函数的开头都有两行固定用于解析协议的代码。

当然case的问题,其实很容易就可以优化掉,只要实现一个map/Dictionary就可以了,比如下面代码:

//NetProtcol.cs 修改代码
Dictionary<int, callback_t> protocol = new Dictionary<int, callback_t>();
void register(int cmd, callback_t cb)
{
        protocol[cmd] = cb;
}
void process() {
        ...
        //int cmd;
        //byte[] data;
        //假设cmd和data已经读取完毕,准备进行反序列化
        //假设所有的通讯协议结构均采用类protobuf之类的方式定义

        //然后把switch语句换成下面代码
        if (protocol.ContainsKey(cmd))
                protocol[cmd](cmd, data)
        ...
}
//Module1.cs 增加代码
void Start() {
        NetProtocol.Instance.register(CMD1, process_cmd1)
}

但是他依然解决不掉每个协议处理函数最开头的那两行协议解析语句。

接收协议部分的封装我并不陌生,在写服务器程序时,我不止一次实现过上述类似的代码,但都只能做到类似map/Dictionary的样子(在强类型语言中)。

这一次在实现时,突发奇想。如果在调用NetProtocol.register函数时,提前把协议包new好,并与cmd进行关联。

那么在处理协议时就可以把ack.pares(dat)之类的协议解析语句,直接放入NetProtocol.process函数中处理。

但是这里需要有一个前提就是所有的协议包都需要有一个基类,并且这个基类提供Parse接口。假设所有的协议包都继承自class wire。那么代码看上去可能就是下面这个样子。

//NetProtcol.cs 修改代码
Dictionary<int, callback_t> protocol_cb = new Dictionary<int, callback_t>();
Dictionary<int, wire> protocol_obj = new Dictionary<int, wire>();

void register(int cmd, wire obj, callback_t cb)
{
        protocol_obj[cmd] = cb;
        protocol_cb[cmd] = cb;
}
void process() {
        ...
        //int cmd;
        //byte[] data;
        //假设cmd和data已经读取完毕,准备进行反序列化
        //假设所有的通讯协议结构均采用类protobuf之类的方式定义

        //然后把switch语句换成下面代码
        if (protocol_obj.ContainsKey(cmd)) {
                wire obj = protocol_obj[cmd];
                obj.Parse(data)
                protocol[cmd](cmd, obj)
        }
        ...
}
//Module1.cs 增加代码
void process_cmd1(int cmd, wire dat)
{
        cmd1_packet ack = (cmd1_packet) dat;
        //do some for request
}
...
void Start() {
        cmd1_packet ack = new cmd1_packet();
        NetProtocol.Instance.register(CMD1, ack, process_cmd1);
}

其实这么做只是省了一行代码而已,似乎并不值得如此大费周张。但是,它的意义在于,我们可以借用这种方式,打破在process函数中不可以处理协议反序列化的困境。

在此基础上,我们还可以更近一步,将CMD1和cmd1_packet进行关联,这样在上层我们就可以完全弱化掉cmd的存在,来降低上层应用的使用负担。

这次的实现中,我正是这样做的

当然,这需要使用的类protobuf工具做一些支持,比如可以从cmd1_packet对象反查出与其对应的协议ID。刚好我自己实现的zproto是支持这种功能的。