实现了一个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, 处理多连接绝对不是一件容易的事,在第三版方案确定好,又重写了两次才终于把逻辑理顺。