客户端缓存落地方案

先大致描述一下场景,客户端按登陆流程成功登陆后,开始按各个模块加载所需数据,待收到消息返回后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。

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

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

服务器的分布式部署

两周前使用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游戏开发,因此上述观点均为理论推测。