design | 重归混沌的BLOG

重新抽象图形API

这次抽象，我几乎全盘否定了之前的抽象。

本来，RHI的抽象已经基本完成了，可以开心的写基础的光照阴影这些功能了。

但是，在QQ群里无意间看到大佬们聊起来bindless, 然后去查了查资料，发现bindless性能又好，抽象又好做，于是果断入bindless的坑。

在bindless抽象中，会把所有用到的材质参数，纹理全部放加载到显存，然后使用一个ID索引来引用相关的资源。

随着重构的进行，我发现之前的设计思路有很多问题，这都是因为我对GPU资源管理的不熟悉所致。

当我们向GPU上传纹理时或做更新资源时，由于GPU离CPU较远，所以Vulkan总是倾向于我们调用批量接口。

对！就像Nvidia说的那样，Batch! Batch! Batch!，但不仅仅局限于DrawCall, 转换内存布局，上传资源都需要Batch。

那么，此前做的所有抽象基本完全无用了。

在之前的抽象中，我都是基于同步的思路来做的，比如我new一个图片就需要等待他上传成功才能返回，不然结构体中的一些数据没有办法进行初始化。

经过仔细思考后，我认为此前提到的方案1其实是更好的选择。

数据冗余的问题也不难解决，只要我们把图形API层需要用到的数据下沉到图形API层的内部代码中，然后在RHI层的结构中做一个代理函数，通过gpu_handle来获取相关属性并返回即可。在实际应用中，由于width,height,format等属性属于低频访问，无论怎么封装，其实都不能成为性能瓶颈。

这样，新RHI层的数据结构只需要持有相应gpu_handle即可，这个结构有释放资源的责任。

比较微妙的是，由于bindless的存在，我们shader中的参数，如纹理，材质参数也都是通过id来索引的。

这样我们便直接把图形API层的资源管理透明掉了，RHI的数据结构可以直接和shader进行匹配，而不用关心图形API层是如何管理资源的。

透明掉图形API层之后，我们便拥有了更大的实现自由，比如在new rhi::texture2d时，图形API层只需要把上传到GPU时所需要的数据保存下来，然后分配一个gpu_handle, 函数就可以立即返回了。

在业务逻辑调用DrawCall之前，把需要用到的资源上传到GPU即可。

在实践中，由于DrawCall也是通过写入CommandBuffer中最终提交才异步执行的，因此我们只需要保证在CommandBuffer中，上传资源相关的GPU命令先于相关的DrawCall命令之前执行就可以了。

在Batch的指导思想下，其实使用gpu_handle的封装方式，能获得更好的Cache Friendly。因为所有图形API层的数据结构总是在渲染时，被批量访问。

而且，由于gpu_handle并不是指针，如果有需要还可以实现一些池的优化技术，如内存整理等（随着分配释放的进行，池中可能会有很多空位长时间用不到，这时出于内存和Cache Friendly的考虑，需要整理一个池中的元素的分布)。

最后，这次重构代码在此。

ps. 由于一些原因，可能未来很长一段时间内，这个引擎的Thread都需要换出了，先在这里保存一下上下文，以便后面可以继续换入 😀

行为树的一种高效实现

在我的玩具项目中，需要有一定智能的NPC来辅助人类攻击防御塔。

通常实现智能会采用状态机，行为树，GOAP等技术。

GOAP技术我没有研究过，行为树在早些年大致了解过一些。因为觉得行为树性能太差，不可能取代状态机实现，之后就再也没有研究过了。

随着这些年我性能强迫症的好转，再加上听到行为树的次数逐年增加，我打算趁机仔细研究一下。

我找来《Behavior Trees in Robotics and AI》仔细读了一遍。这本书详细介绍了行为树，并且对比了行为树和状态机之间的优劣。

根据《Behavior Trees in Robotics and AI》描述，行为树一般有4种控制节点（Sequence, Fallback, Parallel, Decorator)和两种执行节点（Action和Condition)。只有执行节点才能成为叶子节点。

先来简单描述一下最重要的两种控制节点, Sequence和Fallback。

Sequence节点: 当执行Sequence节点时，从左往右顺序执行子节点，直到某一个子节点返回Failure或Running状态，伪码如下：

//Algorithm 1: Pseudocode of a Sequence node with N children
for i 1 to N do
    childStatus <- Tick(child(i))
    if childStatus = Running then
        return Running
    else if childStatus = Failure then
        return Failure
return Success

Fallback节点：当执行Fallback节点时，从左往右顺序执行子节点，直到某一个子节点返回Success or Running状态，伪码如下：

//Algorithm 2: Pseudocode of a Fallback node with N children
for i 1 to N do
    childStatus <- Tick(child(i))
    if childStatus = Running then
        return Running
    else if childStatus = Success then
        return Success
return Failure

Action和Condition节点，是我们具体的业务逻辑，不是本次优化的重点。

对比行为树和状态机可以发现，行为树比状态机额外多出的开销，就是在执行执行节点之前，必须要先穿过控制节点。

如果我们在运行时能避过控制节点，只执行执行节点，那行为树和状态机的开销差别就只是多了几次函数调用而已。

仔细思考过之后，我认为这是可能的。

结合上面对Sequence和Fallback节点的定义。我们不难发现，在编程语言中，Sequence就是and(与)逻辑，而Fallback就是or(或)逻辑。

整棵行为树的控制节点就是用来描述if-else的逻辑，叶子节点是相应的业务逻辑。从这个角度来看，行为树和语法树有颇多相似之处。

不难发现，整棵树的执行路径，其实依赖于特定执行节点的特定返回值。

某一个执行节点（叶子节点）返回Failure或Success, 整棵行为树下一步要执行的执行节点是固定的。

某个执行节点返回Running，整棵树就停止执行。在下一Tick之后从头执行，这种情况比较简单，暂时不需要考虑。

来看一棵简单的行为树：

如果 Action 1 Done 返回Success，下一步将要执行的执行节点（叶子节点）就是 Actino 2 Done。
如果 Action 1 Done 返回Failure, 下一步将要执行的执行节点（叶子节点）就是 Action 1。

这种逻辑可以递归到所有的执行节点。

这样，我们只需要两张跳转表（Success跳转表，Failure跳转表)，就可以在运行时，以状态机的开销来实现行为树的功能。

以上面的行为树为例，我们可以生成如下跳转表：

local tree = {
["Action 1 Done"] = {
    ["Success"] = "Action 2 Done",
    ["Failure"] = "Action 1"
},
["Action 1"] = {
    ["Success"] = "Action 2 Done",
    ["Failure"] = nil, --nil 代表整棵树执行结束
},
["Action 2 Done"] = {
    ["Success"] = nil,
    ["Failure"] = "Action 2"
},
["Action 2"] = {
    ["Success"] = nil,
    ["Failure"] = nil,
}
}

在运行时，我们首先执行整棵行为树的第一个节点"Action 1 Done"。

如果"Action 1 Done"返回Success, 根据表tree可知，下一步需要执行的是"Action 2 Done"。

如果"Action 2 Done"返回Failure, 根据表tree可知，下一步需要执行的是"Action 2"。

这样我们仅需要生成一个跳转表，就可以在运行时抹掉所有控制节点所带来的开销。

最终，我花了200行代码实现了根据行为树生成上述跳转表的逻辑。

PS.我把生成跳转表的行为称之为编译。如果控制节点是Parallel或Decorator类型，或者有记忆功能。在编译过程中，需要将其保留，不能将其编译掉。不然无法完成和行为树等价的逻辑。

PPS. 在示例代码，我使用了behavior3来编辑行为树。

彻底解决多国语言

最近，我在抄王者荣耀玩。而多国语言自然是一个避不开的问题。

在这次的设计中，UI系统我采用了FairyGui。

FairyGUI通过“字符串表”和“分支”功能提供了多国语言解决方案。

FairyGUI把用到的所有文字导出到一个xml文件中，然后为每个外国语言翻译一个相应的xml文件（字符串表），只要在运行时加载相应的xml文件，就可以将所有UI上的文字自动切换到相应的语言。

当然多国语言不止有文字，还有图片等资源。FairyGUI可以为每个外国语言设置一个分支（假设所有外国语言都需要使用不同的图片），每个分支上可以使用不同的图片、布局等，只要执行 UIPackage.branch = "en";，打开UI时就会显示对应分支的UI。这样就实现了非文字类多国语言的方案。

这案相当惊艳，对我有不小的启发。

虽然FairyGUI已经有了相当完美的多国语言方案，但是游戏不仅仅只有UI，一些非UI部分同样会有多国语言的需求，比如不同国家玩家看到的英雄的Tips, 一些3D素材等。

因此，业务逻辑还需要一个自己的多国语言模块，这部分我6年前就实现过。

但是，FairyGUI的多国语言方案让我意识到一个事实，多国语言应该是一种和业务逻辑无关的需求。因此理论上，业务程序员不需要关心多国语言的存在，仅策划和美术关心就够了。

之前的设计中，所有多国语言的显示，都需要业务程序员干预，比如写一条local str = multi_lan.get(key)。

如果显示多国语言的UI设计有变动，业务程序员就要相应的增加或删减multi_lan.get语句。

这违反了Open-Close原则，同时增加了业务程序的心智负担。

我希望这次可以更近一步，业务程序员完全不需要干预。

我重新思考了一下整个游戏的运行流程后发现，屏幕上的所有显示内容其实都是来源于配置。游戏逻辑代码中不需要也不应该去写死每一个字符串（文字或资源路径)。

这样只要我们从配置入手，就可以在底层彻底解决多国语言的问题。

虽然，新的设计要比之前复杂很多。但是，大部分开销和复杂度都在离线（打表）逻辑，运行时代价不高。

按以往的经验，程序需要的配置表往往不是策划直接操作的第一格式。

策划大都是先用Excel来配置相关数据，之后再使用程序提供的配置生成工具，将Excel文件转换为程序使用的配置表格式。

这次多国语言的主角就是这个配置生成工具。

由于Excel的特性，一般在使用Excel文件作配置表时，都会使用关系型数据库的思路来操作。即先设计表结构，再填充表内容。

比如一个Hero表的Excel文件格式可能是下面这样：

HeroID	HeroName	HeroTips	HeroSpeed
int(a)	string(c)	string(c)	int(s)
1000	刘备	刘皇叔是大哥	100
1001	关羽	关云长是二哥	50
1002	张飞	张翼德是小弟	50

第一行用于标识每一列数据的字段名。

第二行用于标识每一个字段的类型(int, string), 以及是被客户端(c、a), 还是服务端(s、a)使用。

第三行开始（包括)就是真正的配置数据。

按照之前的多国语言思路，整个流程大致是这样的。

先将上述Hero表拆分为Hero表和Language表。 Hero表用来配置Hero相关信息的，Language表用于配置多国语言信息。

Hero表：

HeroID	HeroName	HeroTips	HeroSpeed
int(a)	string(c)	string(c)	int(s)
1000	HeroName_1000	HeroTips_1000	100
1001	HeroName_1001	HeroTips_1001	50
1002	HeroName_1002	HeroTips_1002	50

Language表:

Key	Value
string(c)	string(c)
HeroName_1000	刘备
HeroName_1001	关羽
HeroName_1002	张飞
HeroTips_1000	刘皇叔是大哥
HeroTips_1001	关云长是二哥
HeroTips_1002	张翼德是小弟

然后在需要显示HeroName和HeroTips的地方（即使HeroTips是资源路径同样适用)使用如下代码:

local id = 1000
local name = Language[Hero[id].HeroName]
local tips = Language[Hero[id].HeroTips]

上述工作流有不少弊端：

程序不满足Open-Close原则，业务程序员需要关心哪些字段是需要做多国语言处理的，一旦UI改了表现设计，可能需要程序修改代码。相比之下，改了UI表现的FairyGUI却不需要修改业务逻辑代码。
对策划不友好，策划需要手工维护Hero表和Language表之间的同步，人类极不擅长这类工作。这使用两表之间同步极易出错，而且不易发现（只有在运行时用到配错的那一行数据时，才能发现错误)。就算是使用自动化测试都不太可能覆盖表中100%的数据。
由于人类极不擅长Hero和Language表之间的同步，导致策划在修改Language表时，往往只增加不删除，这会导致Language越来越大。以我的经验来讲，这种情况是存在的，尤其是对于半路接手的策划。
由于所有跟文字相关的内容都被移到Language表中，这导致Hero表的可读性下降，往往打开一个Hero.xls之后，你找不到“刘备”是哪个。策划们的通常做法是再加一个字段, 这个字段即不用于客户端也不用于服务端，仅用增加可读性。但是，增加了一个字段的同时，又增加了维护数据之间同步的工作量，出错的概率更大了。

在新的多国语言设计中，我为Excel文件引入了lan类型。

lan类型不仅表明这个字段是一个字符串类型，还表明这个字段对于每个外国语言都有一个不同的值。

我们的Hero表最终配置如下：

HeroID	HeroName	HeroTips	HeroSpeed
int(a)	lan(c)	lan(c)	int(s)
1000	刘备	刘皇叔是大哥	100
1001	关羽	关云长是二哥	50
1002	张飞	张翼德是小弟	50

是的，策划的工作仅仅是把需要进行多国语言处理的字段由string改成lan即可（当然根据需要可以扩展为lan[](c)等列表类型)。

配置生成工具会有一个选项叫做导出多国语言文件，用于导出所有表中类型为lan的字段。

配置生成工具总是会在输出文件的末尾追加新添加的文字。而已经翻译过的文字保持不变。

导出的语言文件Lan.xlsx如下：

CN
刘备
关羽
张飞
刘皇叔是大哥
关云长是二哥
张翼德是小弟

在Lan.xlsx中添加要支持的语言及翻译内容，例如添加英语支持：（注：配置生成工具不会也不应该修改已经翻译过的文字, 如果某一列已经删除，可以将这一列移动第二个Sheet中去，以做备份)

CN	EN
刘备	Liu Bei
关羽	Guan Yu
张飞	Zhang Fei
刘皇叔是大哥	Uncle Liu is the eldest brother
关云长是二哥	Guan Yunchang is the second brother
张翼德是小弟	Zhang Yide is the younger brother

再使用配置生成工具中的导出配置文件功能，生成客户端和服务端需要使用的配置即可（这里可以使用增量导出功能，参考Makefile的做法)。

至于配置生成工具到底如何工作，采用不同的配置文件格式有不同的做法。

以Lua为例，我们导出的配置文件如下：

--hero.lua
local lan = require LAN .. ".hero"
local M =  {
[1000] = {
    HeroID = 1000,
    HeroName = lan.HeroName_1000,
    HeroTips = lan.HeroTips_1000,
    HeroSpeed = 100,
},
[1001] = {
    HeroID = 1001,
    HeroName = lan.HeroName_1001,
    HeroTips = lan.HeroTips_1001,
    HeroSpeed = 50,
},
[1002] = {
    HeroID = 1002,
    HeroName = lan.HeroName_1002,
    HeroTips = lan.HeroTips_1002,
    HeroSpeed = 50,
},
}
return M
--cn/hero.lua
local M = {
HeroName_1000 = '刘备',
HeroName_1001 = '关羽',
HeroName_1002 = '张飞',
HeroTips_1000 = '刘皇叔是大哥',
HeroTips_1001 = '关云长是二哥',
HeroTips_1002 = '张翼德是小弟',
}
return M
--en/hero.lua
local M = {
HeroName_1000 = 'Liu Bei',
HeroName_1001 = 'Guan Yu',
HeroName_1002 = 'Zhang Fei',
HeroTips_1000 = 'Uncle Liu is the eldest brother',
HeroTips_1001 = 'Guan Yunchang is the second brother',
HeroTips_1002 = 'Zhang Yide is the younger brother',
}
return M

有同学说，你这个和策划配出来的XML格式并没有什么不同啊，优势在哪里。

以写代码而论，本质上你写的高级语言和汇编并没有什么不同。为什么你要写高级语言呢，因为写的效率高，出错概率小。

有了这个思路，再次对比上面新旧两种多国语言方案的优劣：

新的多国语言方案，策划只需要做两件事就能保证一定正确：1. 配置正确的lan类型。 2. 给出正确的翻译文本

旧的多国语言方案，同步Language和Hero表有负担，一旦同步错误不容易发现，没有特殊手段清理Language表中废弃的行，Hero.xls表失去可读性等各种缺点。

关于游戏服务器的服务拆分

先阐明一下观点,可以使用单体（单线程）应用程序解决的问题,都不应该使用分布式系统来解决，因为分布式真的很复杂。

在游戏服务器中，我们做服务拆分，大部分情况下都是为了可伸缩，而不是为了高可用（这里暂不考虑那些使用WEB模式实现游戏服务器的思路。我认为这种思路，逻辑的复杂度和实时性都不能保证，而且还需要处理并发问题。)

以前我就说过，游戏服务器的开发更像是在开发数据服务。

现在，我觉得可以更明确一点。

游戏服务器的开发，其实就是针对某种业务逻辑开发的专用数据库。而玩家的客户端就真的是我们开发的数据库的客户端，来进行“增删改查"。

之所以我认为游戏服务器开发过程中，使用分布式不是为了高可用。是因为，在整个游戏服务器中，每个服务都是单点不可替代的。如果某个服务挂了，在它还没有被启动起来之前，所有与之相关系的业务都会出现异常。除非每个服务都会有对应的候补进程，然后将数据实时冗余在候补进程中。

如果使用“最终一致性”，冗余就会有同步延时。而在游戏服务器这种实时“数据库”领域，有延时就代表崩溃时会有数据丢失，这也谈不上高可用了。

如果使用“强一致性”，虽然同步没有延时，但是会出现网络请求链路过长，性能和请求的实时性不能保证。

因此，可伸缩往往也是大多数游戏服务器最终的目的。虽然我们一般不要求高可用，但是我们在部分服务Crash的情况下，也要保证不能产生错误的结果（可以产生异常，而终止某条逻辑)。

虽然说“如无必要，勿增实体”。然而，我们在开发之初往往很难评估到我们的单体应用是否可以满足“策划”们突如其来的需求。

因此，除非极其明确的游戏类型，否则往往在设计之始，都不得不预留一些分布式设计。以免增加某个需求之后，需要大规模重构代码。

以我目前的认知，一个通用分布式游戏服务器框架，最多可以帮助业务程序员解决服务发现、服务依赖、RPC机制、集群健康监控等一些服务级别的管理。

而最重要的一环服务拆分，则留给了我们人类来做。

在服务拆分过程中，我们往往需要关注服务间的数据依赖关系、服务的内聚性、服务间的交互频率、每个客户端请求所经过的链路长度等指标。

同时，遵循“如无必要，勿增实体”原则，服务的拆分应该尽可能的少，这不但会减少链路长度，同时还会降低整个分布式系统出现故障的概率。

这是因为，每个服务都是单点。如果某个服务异常可能导致其余所有服务都产生异常。因此整个分布式系统出现故障的概率，是所有服务出现故障的概率之和而不是积。

事实上，当单体应用程序变成分布式之后，整个逻辑的复杂度都会有相当程度上的提升，尤其在数据一致性上。

在关系型数据库，如Mysql中，有一项功能叫“外键约束”，用于保证数据完整性。然而随着各种Mysql分布式方案的出现，这项功能被越来越少的使用。其原因就是因为在分布式系统中，“外键约束”很难实现，需要应用逻辑自己来保证。

在我们游戏服务设计中，也存在同样的问题。

假如有一个“联盟服务”，有一个“城池服务”。联盟可以借助占有的城池成为国家，“城池”服务则管理着城池相关的归属问题，比如复杂的领土争夺。如果城池丢失，则国家需要变回联盟。

这时，一般会有两种实现方案：

1) “城池服务”在城池丢失时，直接推送给“联盟服务”进行处理，并不在意“联盟服务”是否收到消息。
2) “城池服务”在城池丢失时，通过RPC请求等待“联盟服务”处理完“国家变联盟”逻辑之后，再修改城池归属。

即使在不考虑网络问题的情况下，这两种方案也会存在数据不一致的情况。

比如方案1，在“城池服务”发送给“联盟服务”消息之后，“联盟服务”Crash掉。

比如方案2，在"城池服务”收到“联盟服务”的成功返回后，“城池服务”还没有写入数据库，就Crash掉。

借用数据库的理论，如果需强的一致性就需要2PC，3PC来解决，然而就算2PC，3PC也不能完全解决个别极端情况。

因此，在服务启动时，必须要检查数据约束是否满足，并修正不满足约束的数据。

由于我们需要在启动时进行“数据溯源”（即A需要依赖B来检查约束，B需要依赖C来检查逻辑约束）来修正约束，就势必会产生“服务间依赖”，这时最好不要有循环依赖。

如果我们在拆分服务时，服务的内聚性不够好（比如将联盟和国家数据拆分成“联盟服务”和“国家服务”。由于国家是依托联盟而成存在，如果联盟不存在了，则国家必然不存在了)，则会产生更复杂的依赖链，同时会加大数据不一致的概率。

解决了“服务的内聚性”，我们可能会迎来一个新的矛盾“服务间交互频率”。而且极大概率，这两者是相互冲突的。这需要我们做出取舍，软件设计就是这样，按下葫芦起了瓢，我们永远需要做trade-off。

举个例子，比如我们“城池服务”中的逻辑和国家数据耦合很紧密，如果我们把联盟和国家数据都放在“联盟服务”中。有可能会导致每处理一条客户端请求，“城池服务”和“联盟服务”之间要通信十数次。这会大大增大调用链的长度。

调用链的变长，会导致浪费很多CPU在网络处理和协议序列化上。同时也会降低系统的稳定性，增加客户端请求的RTT。

如果这个开销在整个系统中难以承受。我们就需要考虑，违反“服务内聚”原则将国家数据，挪到“城池服务”中，即使这会使“城池服务”和“联盟服务”变成循环引用。

至于什么程度是“难以承受”，又到底要怎么变通，这取决于个人的经验以及对整个业务系统的认知程度。

上面一直在说分布式的复杂性，还没有提到如何做到“高可伸缩”。并不是拆成分布式系统之后，就一定能做到高可伸缩。

先来描述一个简化的业务场景。

整个世界是由数百万个正方形格子无缝拼接而成。玩家出生后，会随机分配一个空闲格子作为出生点。

玩家在整个世界的主要任务就是打格子，然后形成势力，并最终占领整个服务器。

每个玩家拥有有限个英雄和10支队伍，每支队伍可以上阵三个英雄。

玩家以队伍为单位去占领格子，队伍的出发点，永远是玩家的出生点。

队伍从出发点经过有限时间后到达目标点，经历战斗并最终占领格子。

队伍出发之后到达目标之前称为行军中。行军中的队伍，如果会路过当前客户端显示的世界区域，则会将路线显示出来。

行军中的队伍在到达目标点之前，不会再参与任何逻辑计算。

只要目标点周围两圏范围内有自己的格子，就可以直接行军过去占领，与行军所经过的路线无关。

最初我认为，这样的业务场景，应该会有Role,League,World,Scene这4种服务。

Role用于处理玩家英雄相关数据和请求，可以水平部署多份，有伸缩性。
League用于处理联盟相关数据和请求，全服只有一份，无伸缩性。
World用于管理队伍和格子数据，及队伍相关请求，全服只有一份， 无伸缩性。
Scene用于镜像World的格子数据，供客户端只读拉取，可以水平部署多份，无伸缩性。

为League服务增加可伸缩性并不难。因此随着数据规模的增加，整个分布式系统最终的瓶颈将是World服务。整个分布式系统的伸缩性都将被World的伸缩性所限制。

而我之所以这么分，是因为我对整个业务场景没有清晰的认知，而且有点性能强迫症所致。

当时的思路是这样的：

队伍和格子数据关系很密切，因此需要将队伍和格子数据放在一个服务中处理。这样，客户端来一个请求“占领某格子”，队伍的“出发”，“到达”，“战斗”，“占领”，“返回” 全都在一个服务中搞定了，可以极大的减少服务间的交互。

当我把队伍相关数据放在World服务之后，限制就出现了。

如果我把World服务按地图区域切分，水平部署多份，那么相关的队伍信息，到底应该以怎样的方式分布在相关的World服务中呢，无解。

如果World无法水平部署，那么怎么分摊客户端不停拖屏，所带来的查询压力呢。

只有增加Scene只读服务，用于实时镜像World服务中的格子数据和队伍的行军路线。供客户端拖屏查询使用。

现在重新看待这个问题，我认为应该分为Role,League,World这3种服务。

Role用于处理玩家英雄和队伍的相关数据和请求，可以水平部署多份，有伸缩性。
League用于处理联盟相关数据和请求，全服只有一份，无伸缩性。
World用于管理格子数据，及战斗规则实现，按区域切分，可以水平部署多份， 有伸缩性。

当我们把队伍相关逻辑放入Role服务之后，很多逻辑都会变得更清晰，代价是会多出几次低频率的RPC请求。大概流程如下：

客户端发送“占领某格子”的请求时，Role服务向World服务发出RPC请求，校验目标地的合法性。

World服务返回合法，Role服务为当前操作的队伍设置到达定时器。并再次通过RPC请求路线相关的World服务，设置行军路线供客户端查询使用。

队伍到达目标点之后，Role服务向World服务发出RPC请求，进行战斗并占领行为。World服务向Role服务返回战斗成功。

Role服务再次为队伍设置返回定时器。

队伍到达出生点之后，Role服务通过RPC请求路线相关的World服务，取消行军路线。

从上面流程可以看到，虽然增加了5次RPC请求，但是瞬时RPC请求数量并不高。

虽然在设置和取消行军路线时，需要消耗CPU来计算行军路线会经过哪些World服务，但是这些消耗是常量，随着服务的水平伸缩，很快就被抵消了。

同时还会有两处额外的开销，也需要能通过水平伸缩来抵消。

1) 在客户端拉取当前屏幕地块信息时，有可能需要收集1个以上的World服务中的地块信息
2）在客户端拉取行军路线的队伍信息时，也需要向1个以上Role服务拉取相关的队伍信息

但是不管怎样，整个分布式系统都是以常量的开销，获得了高可伸缩的能力。

我使用这两个方案进行对比，是想说明分布式系统中服务的拆分，非常依赖于个人对整个业务模式理解，这一点真的很难。

再说一些细节问题。

在设计分布式系统之初，我为了减少“服务间的交互”，常常使用缓存技术。

经过一段时间的思考，我认为这是不正确的，因为冗余数据往往是滋生Bug的温床。少量的RPC交互并不会产生性能热点。

如果已经确定了某些交互频率确实过高影响性能。应该首先尝试将交互过多的数据放在同一个服务中，如果确定这样做会产生bad taste，再考虑缓存技术。

在实时游戏服务器中，服务间会经常产生消息推送。在我们不使用缓存技术的情况下，某些业务逻辑会产生竞争问题。

还是以联盟立国为例，客户端调用“联盟服务”选定国都C1进行立国，“联盟服务”通过RPC调用“城池服务”检查是否为自己城池。

“城池服务”收到这条消息，返回消息M1，告知当前城池还是属于此联盟。之后城池突然别被的联盟打掉，然后“城池服务”给“联盟服务”推送了一条消息M2，告知当前城池所有者已经变为了另一个联盟。

由于“联盟服务”调用“城池服务”使用的链接和“城池服务”向“联盟服务”推送的链接不是同一条，所以M1和M2会有一个竞争问题。

如果M2先于M1到达，则“联盟服务”必须要抛弃M1的结果，因为M1是不准确的。

如果M2后于M1到达，则“联盟服务”可以正常处理M1，因为稍后到来的M2再次校正结果。

同样，虽然缓存技术容易滋生Bug, 但是他可以解决上述竞争问题。

9月1日补充。

之所以有这篇文章有出现。其实是因为我想梳理一下思路，从框架层面解决M1和M2的消息竞争问题。

经过几天的思考，我认为框架没有能力也不应该解决这类问题。这类问题可以广义的归纳为异步问题。

比如，我打掉了一块格子，我需要花钱让他升级。当我们调用rpc:submoney(uid, 100)返回时，有可能这块地已经被别人打掉了，我需要在rpc:submoney回来之后，重新检查这块格子是不是我的。

总的来说，服务间通信，异步是常态，这需要业务程序员自己去做约束。

ps. 分布式真的很复杂D:

实现一个数据库存储队列

大约在在两年前，我就意识到定点存库的必要性，并在今年应用到实际项目中了。

从历史经验来看，将数据库存储行为收集并合并起来，确实可以极大的降低抽象代码过程中的心智负担。我们在写代码时已经不需要考虑数据库的存储频率，反正最终所有修改过的数据，只会存一次。

从我意识到定点存库的必要性之后，我就一直对当时的抽象不太满意，在最原始的抽象中，刷新数据是需要业务逻辑来完成的。而数据库合并模块本质上只做了去重而已，这也就是说，其实大量定点存储代码实际是散落在业务逻辑各处的。而在此之后虽然我一直在思考该怎么缓存这些数据库操作，但是一直没有什么实质性进展。

直到最近一段时间，我一直在刻意强迫自己放弃部分性能，以达到更好的抽象后才突然有了点想法。

以Redis数据库的hset(key, field, value)为例，最直接的设计就是把每个key下面的value有变动的field收集起来。然后在特定时机将这些field写入相应的key。相应的伪码如下：

	struct key {
		std::unordered_set<uint32_t> dirty_fields;
	};
	std::unordered_map<string, key> dirty_keys;

这其实就是第一版的抽象，因为没有value相关信息，所以序列化及更新数据库的责任都落在了相关的业务逻辑模块，这个数据库操作缓存模块有与没有其实区别不大。

最近我仔细研究了一下Redis的数据模型和我们业务逻辑的数据模型。我发现其实只要抽象出’set’,’hset’, ‘del’, ‘hdel’这些对应的操作，然后对这些操作进行缓存和去重就能满足99%的需求。

现在还有一个问题需要解决，如何将序列化的工作接管过来。这样就不会存在任何回调了。这个问题其实不难解决，只要我们设计一个通用的接口类提供一个serialize接口即可。

伪码大概如下：

	struct obj {
		std::string serialize() const = 0;
	};
	struct cmd {
		std::string name;
		uint32_t field;
		obj *value;
	};
	
	struct key {
		std::unordered_map<uint32_t, cmd> dirty_fields;
	};
	std::unordered_map<string, key> dirty_keys;
	
	void hset(const std::string &key, uint32_t field, obj *value) {
		auto &set = dirty_keys[key];
		auto &cmd = set[field];
		cmd.name = "hset";
		cmd.field = field;
		cmd.value = value;
	}
	void hdel(const std::string &key, uint32_t field) {
		auto &set = dirty_keys[key];
		auto &cmd = set[field];
		cmd.name = "hdel";
		cmd.field = field;
		cmd.value = nullptr;
	}
	void set(const std::string &key, obj *value) {
		auto &set = dirty_keys[key];
		auto &cmd = set[0];
		cmd.name = "set"
		cmd.value = value;
	}
	
	void del(const std::string &key) {
		auto &set = dirty_keys[key];
		set.clear();
		auto &cmd = set[0];
		cmd.name = "del";
		cmd.value = nullptr;
	}
	void flush() {
		for (auto &kiter:dirty_keys) {
			auto &key = kiter.second;
			auto &kname = kiter.first;
			for (auto &citer:key.dirty_fields) {
				auto &cmd = citer.second;
				if (cmd.name == "hset") {
					auto dat = cmd.value->serialize();
					HSET(kname, cmd.field, dat);
				} else if (cmd.name == "set") {
					auto dat = cmd.value->serialize();
					SET(kname, dat);
				} else if (cmd.name == "del") {
					DEL(kname);
				} else if (cmd.name == "hdel") {
					HDEL(kname, cmd.field);
				}
			}
		}
	}

当然这里面其实还有两个个细节问题。

如果你的数据是直接使用std::unordered_map<uint32_t, dbst> DB进行存储，直接调用hset("foo", 1, &DB[1])需要考虑DB进行rehash的情况。因此需要new一个新的dbst并将新指针传递过去，类似这样hset("foo", 1, new dbst(DB[1]))。同时struct cmd需要做出如下改变：

	struct cmd {
		std::string name;
		uint32_t field;
		std::unique_ptr<obj> value;
	};

看似我们需要很多次new, 但是仔细分析一下整个内存分配行为，就会发现，整个操作序列大概类似这样：new（首次对一个对象进行set/hset）,new,new,new/delete(重复对一个对象进行set/hset),new/delete,delete,delete。也就是说这种分配具有局部性，一般不太会造成内存碎片和性能问题。

需要保证在调用flush函数之前，所有指针的有效性，这个只要稍微留意一下，其实不难保证。

做完如上抽象后，我在想，有没有可能再次简化上述数据结构。

我仔细研究了一下我们的数据模型，我发现一件很有意思的事。

我们在数据库的每一条数据，都在内存中有一份惟一的对应。也就是说一个指针一定只对应一个value（set(key, value)/hset(key, field, value)）。只要这个指针在整个数据生命周期期间，不发生改变，我们就可以直接使用指针来作主键去重，在业务逻辑层使用std::unordered_map<uint32_t, std::unique_ptr<dbst>来缓存数据库数据即可。

这样数据结构就可以简化为如下：

	struct obj {
		std::string serialize() const = 0;
	};
	struct cmd {
		std::string name;
		std::string key;
		uint32_t field;
		obj *value;
	};
	std::unordered_map<intptr_t, size_t> v2i;
	std::vector<cmd> cmds;

	static cmd &overwrite(obj *v) {
		auto iter = v2i.find((intptr_t)v);
		if (iter != v2i.end()) {
			cmds[iter->second].name = "nop"
		}
		cmds.emplace_back();
		return cmds.back();
	}
	
	void hset(const std::string &key, uint32_t field, obj *value) {
		auto &cmd = overwrite(value);
		cmd.name = "hset";
		cmd.key = key;
		cmd.field = field;
		cmd.value = value;
	}
	void set(const std::string &key, obj *value) {
		auto &cmd = overwrite(value);
		cmd.name = "set"
		cmd.key = key;
		cmd.value = value;
	}
	void hdel(const std::string &key, uint32_t field) {
		cmds.emplace_back();
		auto &cmd = cmds.back();
		cmd.name = "hdel";
		cmd.key = key;
		cmd.field = field;
		cmd.value = nullptr;
	}
	void del(const std::string &key) {
		cmds.emplace_back();
		auto &cmd = cmds.back();
		cmd.name = "del";
		cmd.key = key;
		cmd.value = nullptr;
	}
	void flush() {
		v2i.clear();
		for (auto &cmd:cmds) {
			if (cmd.name == "hset") {
				auto dat = cmd.value->serialize();
				HSET(cmd.key, cmd.field, dat);
			} else if (cmd.name == "set") {
				auto dat = cmd.value->serialize();
				SET(cmd.key, dat);
			} else if (cmd.name == "del") {
				DEL(cmd.key);
			} else if (cmd.name == "hdel") {
				HDEL(cmd.key, cmd.field);
			}
		}
	}

做成一个操作队列，最麻烦的其实是在两个hset/set之间插入hdel/del。这时会有两种选择：

扫描cmds, 找到相同的key+field, 将删除，并将最后一个相同key+field的cmd结构改成hdel/del。
直接将del/hdel添加到队列末尾。

由于没有直接证据表明，方式1会快，加上我最近刻意强迫自己牺牲部分性来保持简洁性。因此我选用了方式2.

谈谈我对数据同步的理解

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之前，我曾请教了几个人，但似乎并没有其他更好的做法，觉得这个实现还算精巧，就做个笔记.