谈谈我对数据同步的理解

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。显然这也没有错。

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

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


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

实现了一个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是支持这种功能的。

如何恢复全局INDEX

一般来说,当需要分配全局惟一id时,一般都会有一个变量来记录当前最新的id值,比如叫INDEX变量。

每次需要分配id时,只要简单的自增一下INDEX变量,然后INDEX的值即为当前分配出去的ID的值。

为了最大可能的延迟复用已经分配过的id,一般来说不会去特殊处理INDEX变量,即每次自增INDEX,并允许回绕情况的发生。

但是最近碰到问题就是,我有一堆分配过的id,如何重新恢复出INDEX的值。具体场景如下:

struct obj {
        unsigned int id;
        time_t createtime;
        ...
}

每一个obj对象都需要有一个全局惟一id和创建时间(createtime字段)与其关联,因此每new一个obj对象就需要为其分配一个不重复的全局id。

obj可以被人为删除,也会被过期删除,因此无法保证在任何时间所有还存活着的obj对象id是连续的。这些obj对象会被定时写入数据库。

一旦进程被重启,程序会从数据库加载所有还存活着的obj对象,以便可以恢复现场,使重启进程这一操作透明。要保证整个逻辑正确性,还必须要能正确的恢复出INDEX变量。

那么问题来了,而由于某种原因,INDEX并不方便被存入数据库中。

因此必须要根据现有的存活obj对象来恢复出在进程重启前的INDEX的值。

第一反应,肯定是遍历一之后找到obj对象中最大的id即为原来的INDEX,但是这里有一个陷阱就是INDEX会回绕,一旦INDEX会回绕之后,这个算法就不正确了。

考虑这样一种情况,进程运行了数月都没有重启,这时残留的obj对象id可能就只剩下0xfffffffe,0xffffffff,0,1,3,5这些了,重启之后采用上述算法无法重新恢复出重启前INDEX的值为5.

再一看,还有一个createtime用作参考,只要取obj对象中createtime最大的那个对象的id为INDEX就行了。

然而,由于createtime是以秒为单位的,逻辑上无法保证1秒只创建一个obj对象,问题再次绕回到第一个算法所遇到的困境。

因此,看起来,想要正确恢复出INDEX的值就必须解决回绕的问题。

要解决这个问题,就必须要有一种大小比较算法,这种算法即使在回绕时,也能正确判断大小。比如在0xfffffffe,0xffffffff,0,1,3,5这一堆id中,此算法会认为5是最大值,而在3,5,7,9这一块id中认为9才是最大值。

那么究竟有没有这种算法呢?比较巧的是,还真有这种算法。

假设有A,B,C三个32位无符号值,C=(A+B) % 4G。那么只要B大于0且小于2G,C – A就一定大于0。不过这里有一个陷阱,如果A和C是无符号变量,那么一定要将C-A的值转换为int之后再使用。

再回到设定场景中去,虽然我们1秒可以new很多个obj对象,但是绝不可能new出2G个之多。

有了这个事实和算法,答案就呼之欲出了,其中一种实现如下:

unsigned int id = 0;
time_t time = 0;
for (auto const &obj:objs) {
        if (obj.createtime < time)
                continue;
        if (obj.createtime > time) {
                time = obj.createtime;
                id = obj.id;
        } else if ((int)(id - obj.id) < 0) {
                 id = obj.id
        }
}
//now we got the final INDEX value

ps. 在阐述这个blog之前,我曾请教了几个人,但似乎并没有其他更好的做法,觉得这个实现还算精巧,就做个笔记.

谈谈协议的设计

闲来无事,最近接了个公众号玩玩,当然肯定是基于silly的:)

最初的打算是开一个daemon,在收到微信sdk callback后根据好友发送的消息来做出不同的处理。比如根据输入关键字然后去我的blog上去爬取相关信息,每天定时把最新的blog文章做群发。

在实现http client过程中,需要解析dns。虽然gethostbyname可以用来解析域名,但是整个silly底层是基于异步来实现的,而gethostbyname则是以阻塞方式解析的,因此使用gethostbyname会极大地降低整个框架的吞吐量。

向dns服务器请求解析域名时,应该首先以udp方式请求,如果服务端回应超过512字节,则会置截断标志位。客户端发现截断标志位后应该以tcp的方式重新发送请求,在发送请求时,跟udp唯一的区别是,需要在数据包最开始附上两个字节的包长。

这是我第一次遇见一份协议同时适用于udp和tcp协议的。强烈的反差感让我不禁在思考,协议到底应该以什么样的方式进行组织,才可以更方便服务端的解析。

对比一下dns的udp和tcp的协议格式,同一个请求在通过tcp发送时需要增加两个字节的包头。那是因为tcp是属于字节流会粘包,而udp是按报文发送的,换句话说,你发出去是什么,对方就会接到什么。不会有粘包的顾虑,因此tcp需要包头来进行切饱。

当然在tcp情况下即使不用包头,dns请求协议也足够描述出一个完成的数据包。那么为什么要加两个字节的包长呢?

想到这里我就不得不佩服发明’协议栈’的哥们了,说得太形象了。协议栈通过抽象分层,然后明确每一层的作用,这样不但在设计代码时可以更好的解耦,在移植时也可以通过换掉其中某一层来达到快速移植的目的。

以dns的tcp协议为例,有了两个字节的包长就可以在逻辑层以下,抽象出组包层。

组包层的实现,屏蔽掉了底层通信细节,抛给逻辑层的都是一个一个完整的包。逻辑层的实现仅仅是拿一个完整的数据包去反序列化去处理,它并不关心数据是从哪里来的。

假如我们的dns不再通过tcp来通信,而是通过串口。我们所需要做的仅仅需要重新实现一个组包层,组包层从串口读出数据并切割出一个一个完整的数据包抛给逻辑层。而之前实现的逻辑层则一点都不需要改变,从而达到了代码的最大复用性。

这一点我感触颇深,在为silly移植各种协议的过程中,发现有好多库都是把socket直接做到协议里面的,而silly为了达到高吞吐量在c语言层使用的是异步逻辑,只有在lua层才可以进行阻塞访问。因此移植一些c协议库起来就颇为制肘。

因此,在设计协议时,一定要进行抽象分层,明确责任。这样在以后协议移植时会大大增加代码的复用性。

解耦

事情起源于昨天的一次讨论。模块A如何在不同的时期返回不一样的数据类型的值,供其他不同的模块使用。

我自行脑补了一下,其实这类问题可以归结为对数据类型的解耦。

考虑一种特殊情况,有moduleA,moduleB,moduleC1,moduleC2等四个模块。moduleA在不同的时期产出不同的数据供moduleC1和moduleC2处理。moduleB用于将moduleA产出的数据根据具体情况情况分别调用moduleCx来处理。moduleCx的接口类似moduleC1::doSomething(type1 data);moduleC2::doSomething(type2 data); 

最low的解法莫过于在moduleB中分别定义type1,type2的变量接收一下,然后根据具体情况分别传入相应的moduleCx模块中。然而这样的写法根本不符合open-close原则。moduleCx从属性上来讲应该属于同一种东西的不同变种,以后会有很大的可能增加moduleC3(type3);moduleC4(type4)等模块。几乎每增加一种模块,moduleB都需要相应作出修改。

这样,moduleCx已经与moduleB深深的耦合在一起了。

为了解决这个问题。按照面向对象的做法,应该抽象一个纯虚类定义接口I,moduleCx分别实现接口I。这样moduleB只需要持有接口I的引用,仅仅把数据传入接口I即可。不论增加多少moduleC,对moduleB的修改总是close的。

然而这里存在一个非常大的问题。moduleCx的每个处理接口的数据类型不同,这是对抽象出接口I的最大障碍。只有将接口的数据类型与moduleCx进行解耦,才可以顺利抽象出接口I。

对于c语言来讲,比较粗暴的做法是使用void *,对于c++的做法最常用的做法是对数据类型抽象出一个基类P,所有接口的type均继承自基类P,moduleA的返回及moduleCx的接口类型均使用基类P。到了moduleCx内定后再自行转为实际使用的数据类型。

每一种语言都有相应的思维层次。

站在c语言层面,我眼中是内存和cpu因此我觉得把其他类型转为void *,在moduleCx中再转为相应的类型并没有什么不妥。因为在我眼中不过都是同一块内存罢了。

然而站在c++(面向对象)的层次,我眼中尽是对象。每个moduleC接口的参数type之间并无共同之处,为了使用语法糖而是用继承,总是感觉心里有些许别扭。

于是我想了另外一种独立于语言的做法。

可以定义类typeX,typeX就像是c中的union一样,可以包含type1,type2 … 等moduleCx的所有类型的数据。接口I和moduleB与moduleA的返回值均使用typeX。在moduleCx中通过typeX变量获取自己需要的数据即可。

如何实现typeX使得编码更方便,则需要具体情况具体分析了。

使用多态来做到open-close

自从看了设计模式了解到open-close原则后, 我在写代码时都是尽量遵循着open-close原则来进行编码。

而面向对象中的多态在做到open-close原则中起到不可忽略的作用。

一般在设计之初会先抽象出一个interface(也就是C++中的纯虚类), 这个interface中的函数接口一定是要仔细考量的,因为这关系到所有子类的实现。

然后根据具体情况去继承并实现interface,当我们新增功能时,仅仅重新继承一下interface生成一个新的类即可, 在一般情况下并不需要动到之前运行良好的类。当然不论你interface定义的有多么好, 在最后新增需求时都可能不会完全满足,然而这种情况下一般只需对interface增加函数即可, 对之前运行良好的代码也并不需要做出大的修改。

举个例子:
一个游戏有三个模式ModeA, ModeB, ModeC。我觉得这是一种最天然的抽象了,几乎就不用思考就可以肯定,多态一定是优于if else方式的。


使用多态的方式, 首先抽象出一个interface类似如下:

class IMode {
virtual doSomeThingA() = 0;
virtual doSomeThingB() = 0;
...
};

然后根据ModeA/ModeB/ModeC的实际玩法去实现IMode类开中函数。

这样只需要在游戏切换模式时使用如下类似代码散转一下即可:

IMode *mode;
switch (game_mode) {
case ModeA:
mode = new ModeA();
break;
...
default:
assert(!"unkonwn game mode");
break;
}

在代码主体逻辑中,仅仅使用mode指针即可,即主体逻辑并不关心当前mode是ModeA/ModeB/Modec中的哪个, 他仅仅去调用相关的IMode中的函数即可。

这样当去看主体逻辑代码时,暴露出来几乎全部是主体逻辑,而不会被模式相关的东西弄晕了头脑。

当新加一个ModeD模式时, 仅需要修改上面的Switch语句加一个case另外再实现一个class ModeD类即可, 并不需要修改之前运行良好的主体代码。也就符合了open-close原则。


再看if else的实现,假设如上IMode函数有50个函数DoSomething1~50, 如果使用if else的方式实现,则需要在调用DoSomething1~50的地方全写上类似如上switch的语句,需要搞清楚的是IMode有50个函数并不意味着这50个函数仅仅调用50次(甚至说是150次都不算多), 那么就会出现代码量暴增。

而且这样会导至所有的模式代码是以函数分开的,在增加每一个模式时主体代码都要增加50个函数并修改150处switch-case语句,如果改漏一处就会出现难以预料的bug, 这样大大增加了代码的维护难度。

当然这种还算是好的情况,如果在IMode类中的函数非常短,那么在使用if else方式实现时有些人偷懒就可能会直接用case一段代码语句直接搞定,甚至在后续开发中都可能出现这样的代码:

switch (game_mode) {
case ModeA:
case ModeB:
do_something();
if (game_mode == ModeA)
do_sometingA();
else
do_somethingB();
break;
...
};

如果有4个模式这样纠缠到一块,我打赌你看到这段代码时一定会想知道他家在哪里。

这样修改还有一个坏处就是并不符合open-close原则,因为你在改ModeB时可能会把ModeA改坏,而且有时后会很难测出来。


通过比较很容易就可以看出,多态和open-close的好处,在这里我并不想听到if-else/switch-case比使用多态效率高这种鬼话,我认为损失一点点性能能获得这么清晰的代码结构是非常值得的。

在《Unix编程艺术》P14中说过这样一句话,计算机编程的本质就是控制复杂度,比较两种实现方式可以看出第一种方式,不论增加多了种模式其复杂度几乎都不会增加,而第二种方式每增加一种模式都会使得代码变得更糟糕一些,而且永不停止直到他再也无法被维护。

服务器的分布式部署

两周前使用redis-benchmark测了一下silly的并发请求响应速度, 开1000个客户端, 平均大概每秒能响应6W个请求。
但是这些请求仅仅是PING/PONG协议,也就是说这基本上就是纯网络I/O的性能,如果考虑到逻辑处理、数据压缩、加密、解密等时间, 可能一个silly都不一定能够撑得起5000人的访问量。

所以最近两周除了在研究redis之外, 就是在研究怎么给silly增加cluster支持,以便可以将计算分摊到不同的计算机上来降低客户端的请求的响应延迟,silly应该怎么增加对cluster的支持。

直到昨天下班的路上我才想通,其实对于silly的模型来讲,他的任务应该相当的KISS,仅仅只是用coroutine的方式来处理数据即可。分布式功能应该在应用层实现,并不需要silly做额外的支持。


首先给定这样一个命题:
所有玩家在同一张地图上游戏,一台物理server能支持5000人的并发量,那么如何才能支撑百万级的玩家在同一张地图上游戏。

首先将服务器分为auth_server, channel_server, scene_server, ctrl_server这四种服务器。

整个服务器集群由一个auth_server、一个ctrl_server、若干channel_server、若干scene_server组成。

所有server在启动时主动向ctrl_server建立一条socket链接, 以便可以定时向ctrl_server汇报和查询状态(如当前负载情况等),另外在停服时可以直接操作ctrl_server, 然后ctrl_server通过建立的socket连接来通知所有server停服,这样可以避免人工操作出现的各种差错。

auth_server服务器的作用仅仅用来做用户认证,和负载均衡。在客户端用户登陆验证正确后,auth_server根据向ctrl_server查询到的所有channel_server的负载状态,挑选出各适的channel_server服务器的ip及端口号,然后将其和临时通行证一并发给客户端。 当客户端得到临时通行证和相应的channel_server地址/端口号之后,随即与auth_server断开连接以便auth_server可以有更多的资源处理其他客户的认证请求。

每一个scene_server管理地图上的一部分场景,并用来处理这块游戏场景内的游戏逻辑,这样所有的scene_server组合起来的集群就是一张大的地图,和完整的游戏逻辑。

每一个channel_server与所有的scene_server相连接,并将每一个scene_server负责的区域信息与此scene_server的socket连接做hash映射,每一个客户端只会与一个channel_server相连接。

channel_server所做的事仅仅是根据当前客户端的人物的位置,自行转发到不同的scene_server服务器中去, 具体逻辑由scene_server进行处理。 当客户端在地图中行走时,如果channel_server判断超出了当前的scene_server的范围, 则根据客户端的当前位置从映射表中查出当前区域信息所在的scene_server的socket链接, 并将数据转到的新的scene_server服务器中去。

这样看来只需要一个常量的代价(数据被中转一次,hash查询),channel_server和scene_server几乎可以无限扩展,那么整个逻辑的响应速度也会是常量。惟一受限的将会是auth_server的响应速度。

ps.集群的思想参考自redis的集群,由于我并没有参与过RPG游戏开发,因此上述观点均为理论推测。

silly的socket模块重构

最初, 我仅仅最只想将silly实现成一个socket异步框架, 每一个socket有数据或事件过来直接将注册的处理函数异步回调即可。

然后, 随着三国杀的一步步实现, 我发现我之前考虑处理时漏掉了数据库环节。

由于所有socket事件均为异步, 当一个client发过来一个请求, 而这个请求需要使用到数据库数据时, 可能就会写出类似下面这样的代码:

socket.recv(fd,function(fd, data)
--process segment1
db.get(key, function(value)
--process segment2
end)
end)

这种异步代码写起来非常费劲, 而且如果通信协议设计不好, 当–process segment2还没有被执行, 下一条socket的数据包又过来, 就有可能造成错误的结果, 而且不容易发现问题所在。

这次的重构,我希望可以在上层屏蔽掉底层的异步逻辑,这样代码写起来会更清晰不容易出错。


大概设计是这样的。

每一个socket在建立链接之后, 便拥有一个coroutine, 和一个数据队列。
每一个socket数据包过来之后均使用这个socket的coroutine来处理,如果coroutine在处理数据包过程中挂起,则将数据推入此socket的数据队列中.
每个socket的coroutine恢复并处理完上一个数据包后,会检查队列是否为空, 如果队列为空则yield等待下一下数据包的到来, 否则将消耗完数据队列中的数据。

由于socket/tcp具有fifo的特性, 如果目标数据库服务器的request/response同样是按照fifo方式处理的话, 就可以实现一个socketfifo模块(如果是其他方式,只要对sockefifo稍加修改即可)。

socketfifo模块用来在每一个socket的coroutine中管理数据库socket的命令/应答,在向数据库socket发送命令后阻塞此socket的coroutine, 直到获取到数据库socket发过来的数据。

socketfifo持有一个coroutine队列。

socketfifo向数据库socket发送命令之后, 将当前的coroutine(即调用socketfifo模块的socket所在的coroutine)塞入coroutine队列中, 然后挂起当前的coroutine。
在socketfifo收到数据后,按照fifo的特性,从coroutine队列中取出一个coroutine将其唤醒并将数据返回给此coroutine。这样即可达到阻塞访问socket的目的。

虽然用同样的方法实现了阻塞connect, 但如果connect函数并非是在coroutine中调用就需要手动创建一个coroutine来将connect函数包住。


在重构过程中发送一个关于客户端主动close事件的bug。

抽象上看, 整个silly是通过两个通道来运行起来的。

socket –> worker (silly_queue) 主要向worker通知客户端的行为事件
worker –> socket(pipe) 主要向socket发送操作命令

最初设计时, 当客户端断开连接时, socket模块随即就释放所有资源,但是此时有可能silly_queue中还有此socket的数据包。
而socket模块中是有链接池存在的, 当某个socket被释放回链接池之后, 是有可能被分配给其他client的。

假设有两个socket, s1, s2。
在极端的情况下, 当s1主动断开链接时, 恰好worker还有s1的数据没有处理完,因此worker还不知道s1已经断开了,但此时s1所占用的struct conn结构体已经被释放到链接池了。
此时s2连接到服务器,恰好将struct conn分配给s2使用。

由于silly分配的socket id的特殊性,虽然s1和s1拥有不同的socket id, 但是他们都能索引到同一个struct conn结构体,如果此时处理s1数据包的函数需要向s1发送数据, 此时其实是向s2发送的数据包, 就会产生数据错乱的情况。

因此修改了一下socket关闭的策略, 当检测到client关闭socket之后,释放除struct conn结构体之后的所有资源,然后将struct conn置成一个特殊状态,直到worker收到client的关闭消息后再调用close函数,将struct conn归还给链接池。

在worker在主动关闭socket时,同样存在另外一个队列缓存问题, 当worker向socket模块发送close命令时, 并不知道silly_queue中是否还有此socket的数据,那么socket.lua模块就不知道应该什么时间释放与此socket有关的资源, 过早的释放资源容易引起其他问题。

因此在worker向socket模块发送shutdown(worker主动关闭socket命令定义为shutdown, 与tcp的shutdown无关)之后, socket模块释放除struct conn结构体之外的所有资源, 其后将struct conn置成一特殊状态,向worker回一条SILLY_SOCKET_SHUTDOWN消息, 当worker处理SILLY_SOCKET_SHUTDOWN消息时, 肯定已经消耗掉silly_queue中的与此socket有关的数据了。

此时socket.lua可以释放与此socket有关的资源,并调用close命令将struct conn结构体归还给链接池。

btw, 将多进程改进为多线程时,我曾以为可以躲避通信的复杂度, 现在看来, 当时想的太少了。 只要按照多进程的设计思路(使用队列通信), 不管是否真的是多进程, 异步通信协议的处理是必不可少的。