重新抽象图形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都需要换出了,先在这里保存一下上下文,以便后面可以继续换入 😀

给Lua实现了一个数学库

我的玩具引擎计划以Lua语言为第一业务语言。

引擎可以加载出一个场景之后,我就需要一个相机控制器,来接收用户输入来移动和旋转相机,以实现场景漫游。

我打算使用Lua来编写这一逻辑。在计算相机的Transform时,需要进行一定的数学运算。这就需要一个Lua版的数学库

怎么给Lua写一个简洁高效的数学库,这并不是最近才开始思考的问题。

早些年在使用tolua框架时,就发现在Lua中进行数学计算时会产生大量的临时对象,极大的加重GC的负担。

虽然这两年时不时就会想起这个问题,也一直没有解决方案。

这次,在没有了Unity的包袱之后, 希望能找到一条全新的思路。

为什么在C#中写数学运算就不会产生GC呢。根本原因是,在C#中(vector3,quaternion,matrix)等对象都是struct类型,即值类型。这些对象都是在栈上分配,函数返回即销毁。就算当值返回,也是直接值拷贝出去的。

在Lua中,严格意义的值类型只有boolean,number两种类型。虽然string表现的像个值类型,但是临时string对象一样会产生内存垃圾。

所以我们一般实现vector3时,会使用Table或userdata来保存xyz。这是因为Lua中的值类型不足以装下xyz这么多数据。

一个很直觉的思路,我们能不能扩展Lua中的值类型,使他最多能包含xyzw四个字段。

答案是能,但是代价很大。内存的代价,性能的代价,以及维护的代价。

我仔细回忆了这几年有限的客户端经历,我发现数学运算都是扎堆的。

换句话说,我们的数学运算一般都是几个有限的输入和几处有限的输出。但是中间计算过程很复杂,只要解决了这些中间过程产生的临时变量,那也算基本符合预期了。

沿着这个思路,即然Lua中只有numbert和boolean是值类型,那我有没有可能用number来代表一个vector3或quaternion呢?

答案是肯定的。我们只需要用C实现一片额外的空间,然后用索引指向这个vector3或quaternion的值就大功告成了。

基于以上思路,我实现了一个数学栈。这个栈的范围只能在一个函数内使用。

如果你想将计算结果返回到另一个函数使用,你只能将栈中的值取出,然后显式返回给其他函数。

如果其他函数需要再次进行数学计算,就需要重新开辟一个数学栈空间。

大致用法如下:

local mathx = require "engine.math"
local camera_up = {x = 0, y = 0, z = 0}
local camera_forward = {x = 0, y = 0, z = 0}
local camera_right = {x = 0, y = 0, z = 0}

local stk<close> = mathx.begin()
print("rotation", component.get_quaternion(self))
local rot = stk:quaternion(component.get_quaternion(self))
local up = stk:mul(rot, stk:vector3f_up())
local forward = stk:mul(rot, stk:vector3f_forward())
local right = stk:mul(rot, stk:vector3f_right())
stk:save(up, camera_up)
stk:save(right, camera_right)
stk:save(forward, camera_forward)

首先使用math.begin()来创建一个数学栈,接着我们就可以在栈上进行各种数学计算。

当数学计算结束时,我们可以使用stk:save来取出数学栈中的xyzw的值。

stk:save有两种使用方式,当我们传入一个table时,stk会直接将xyzw的值置入table内。我们还可以不传入参数,这时stk:save就会根据值的类型返回xyz或xyzw的值。

这里使用了Lua的toclose特性, 当栈使用完之后,__close函数会自动将栈对象放入Cache中。

下次调用math.begin时,直接从Cache中分配,这样可以做到0内存分配。

在实现完这个库之后,我特意与xlua做了一个性能对比。

local stk<close> = math.begin()
local v1 = stk:vector3f(xx_v3_1)
local v2 = stk:vector3f(xx_v3_2)
v2 = stk:vector3f_cross(v1, v2)
v2 = stk:vector3f_cross(v1, v2)
v2 = stk:vector3f_cross(v1, v2)
v2 = stk:vector3f_cross(v1, v2)
stk:save(v2, xx_v3_2)

与同样逻辑的xlua写法对比,性能要高出300%左右。并且随着计算过程的增加,性能优势会越来越明显。

除此之外,在进行数学计算之前,我们往往需要获取到transform中的position,rotation,scale等属性。

这些属性要么是vector3, 要么是quaternion。如果我们用table或userdata来返回依然会加重GC负担。

仔细数一下其实这些数据类型最大也只有4个变量。因此,我让函数component.get_position直接返回xyz三个值,而component.get_rotation直接返回xyzw四个值。

至于是否需要存到table里,这个交由业务逻辑来控制。

谈谈跨平台图形API的抽象

本来按3月份的计划,是先把王者荣耀基本模式抄完 ,并以此为基础来抽象出一套基于Lua的通用客户端框架,然后根据需求再慢慢优化。

但是,3月底GAMES系列又出了一个新课GAMES104,《现代游戏引擎:从入门到实践》。

这门课一下子燃爆了我的兴趣,于是我决定暂停客户端框架的开发计划。学完GAMES104之后再回来继续开发客户端框架。

经过这几年的观察。我发现由于算力的缘故,很多高级的技术总是选应用于端游,然后再过很多年。才被用于手游开发(有时甚至还需要各种Trick才能跑得起来)。所以,要想学习和体验最新的引擎技术,最好还是通过端游引擎。

我打算趁着这次GAMES104的课程,写一个自己的引擎。

这个引擎应该使用最新的技术和最新的硬件特性。

这个引擎的业务逻辑语言为Lua。从表现力上讲,Lua要比C和C++强不少,虽然性能会慢一点,但是因为是实验性质的引擎,开发快反而会更重要。

这个引擎应该是跨平台的。虽然我的主要目标是端游,但是我也希望像在手机算力允许的情况下,可以在手机上玩耍。

我花了一周时间把vulkan教程上的例子抄了一遍(画一一个三角形,我竟然抄了3天半 ^_^!)。

然后就开始根据GAMES104的视频课程实现引擎了。

虽然第一版引擎以Vulkan图形API为基础,但是我还是希望能先抽象的个差不多的RHI(Render Hardware Interface), 为未来支持Direct3D和Metal打下基础。

这对我来讲很难,因为我没有任何Direct3D和Metal的基础,连Vulkan也只有一个星期的经验。

我还是想试一下。


一个最容易想到的方案是,为所有图形API设计相同的接口和相同的导出结构,然后使用宏来切换平台,这也正是RHI的表面含义.

伪码如下:

//-----rhi/texture.h------
namespace rhi {
    gpu_handle texture_create();
    texture_destroy(gpu_handle handle);
}
//-----rhi/texture.cpp-------
#ifdef RHI_VULKAN
#include "vulkan/texture.cpp"
#elseif RHI_DIRECT3D
#include "direct3d/texture.cpp"
#elseif RHI_METAL
#include "metal/texture.cpp"
#endif
//-----render/texture2d.h
namespace render {
    class texture2d {
    public:
        texture2d() {
            gpu_texture = texture_create();
        }
        ~texture2d() {
            texture_destroy(gpu_texture);
        }
    private:
        gpu_handle gpu_texture;
        int width;
        int height;
    }
}

但是这么做会有一些令人纠结的问题。

以texture2d为例,在Vulkan层面去使用texture时,部分情况是需要用到width和height,write_enable,filter_mode等属性,这时需要如何去获取这些属性。

这时有三种方案:

  • 第一种方案:在调用rhi::texture_create()时把所有需要用到的参数都传递过去,然后Vulkan层在内部保存供后面使用。这样做有两个坏处:数据冗余严重、需要额外的代码来将texture2d和gpu_texture之间的属性进行同步。

  • 第二种方案:在调用rhi::texture_create()时,直接把texture2d的this指针传递进去,Vulkan层在内部将gpu_texture和this进行绑定。Vulkan层在内部操作gpu_texture时可以通过这种绑定关系,查询到texture2d的指针,并读取相关设置信息。这么做同样也有坏处,首先是会产生循环引用,在render层textuer_2d引用了gpu_texture, 在vulkan层gpu_texture又引用了texture2d,然后是,因为rhi::texture_create的参数有了类型,那么就需要为每一种texture(textur2d, texture3d, cubemap)等添加一个texture_create/texture_destroy接口。

  • 第三种方案:在第二种方案的基础上,可以通过去掉gpu_handle的存在,来切断循环引用。

伪码如下:

//-----rhi/texture.h------
namespace rhi {
    bool texture_create(texture2d *tex);
    void texture_destroy(texture2d *tex);
}
//-----rhi/texture.cpp-------
#ifdef RHI_VULKAN
#include "vulkan/texture.cpp"
#elseif RHI_DIRECT3D
#include "direct3d/texture.cpp"
#elseif RHI_METAL
#include "metal/texture.cpp"
#endif
//-----render/texture2d.h
namespace render {
    class texture2d {
    public:
        texture2d() {
            rhi::texture_create(this);
        }
        ~texture2d() {
            rhi::texture_destroy(this);
        }
    private:
        int width;
        int height;
    }
}

当调用rhi::texture_create时,Vulkan层会创建一个texture的GPU资源,并这份GPU资源和texture2d指针进行绑定,但是这种绑定并不导出到外部接口使用。

后续操作某个GPU资源时,直接使用texture2d指针即可。

至于绑定方式,可以有多种多样,最简单直接方式就是使用unordered_map(显然性能并不会太高)。

第三种方案和第二种方案有一个通病,就是一个texture2d资源同时需要至少两个对象来表示,render层的texture2d和vulkan层的gpu_texture2d, 这会造成内存碎片问题。


花了2周时间反复重构了多次,都不太满意。

在重构过程中,我想到了一个全新的思路。

伪码如下:

//-----render/texture2d.h
namespace render {
    class texture2d {
    pubilc:
    static texture2d *create(int width, int height);
    static void destroy(texture2d *tex);
    protected:
        texture2d() {}
        ~texture2d() {}
    protected:
        gpu_handle gpu_texture;
        int width;
        int height;
    }
}

//-----vulkan/vk_texture2d.h
namespace vulkan {
    class vk_texture2d : public render::texture2d {
    public:
        vk_texture2d(int width, int height) : texture2d() {
            //todo some gpu create
        }
        ~vk_texture2d() {
            ~texture2d()
            //release some gpu resource
        }
    private:
        //some GPU-related resource
    }
}

//-----vulkan/vk_factory.h
namespace render {
    texture2d *texture2d::create(int width, int height) 
    {
        return new vk_texture2d(width, height);
    }
    void texture2d::destroy(texture2d *tex)
    {
        delete (vk_texture2d *)tex;
    }
}

在这次抽象中,我彻底去掉了RHI相关的所有中间层。而且几乎解决了上述方案中所有的缺点:内存碎片不存在了,循环引用没有了,GPU和CPU端数据的粘合逻辑消失了。

当然,这套抽象也有他自己的缺点:

但是,相比他能解决的问题,我觉得这两个问题都不算是大问题。

业务逻辑是使用Lua来做,所以本来也不会用到new来创建渲染对象。

少使用乃至不使用继承更是我一惯的坚持原则。

最后, 完整代码附上

寻路和Flocking算法的结合

最近本来在研究行为树, 然后无意间发现了一本名叫《Artificial Intelligence for Games, Second Edition》的书,就顺便看了起来。

书中第三章提到了一个Flocking算法,该算法一般用于模拟群体(羊群,鸟群,鱼群,人群)的移动行为。

这让我想起了大约一年前,他们QQ群里分享了一个蚁群行军的视频。当时为了研究他是如何时实现的,还特意去学习了VO,RVO算法(没有学会),最终也没有实现出来。

这次,我想用Flocking算法再试一次。


先简单介绍一下Flocking算法。

对于鸟群中的一只鸟而言,除了他本身要飞行的速度向量Velocity外,还有三个额外的分量来辅助校正最终的速度向量。

这三个额外分量分别如下:

Separation:每只鸟都会考虑到它们相对周围其他鸟的位置,如果过近,就会产生一个排斥速度分量。

Cohesion: 每只鸟都会检查自己半径R范围内鸟的位置,计算出这群鸟的质心,产生一个向质心靠拢的速度分量。

Alignment: 每只鸟都会检查自己半径R范围内的鸟的速度,计算出这群鸟的平均速度,然后产生一个向平均速度靠拢的速度分量。

最终每只鸟的速度为:Velocity + Separation + Cohesion + Alignment(在叠加过程中,可以根据情况给每个分量加上相应的权重)。

Flocking在没有障碍物的场景,比如天空,海底,平原等表现都很不错。但是一旦进入有障碍物的场景如蚁穴,就会很难工作。

这时就需要加入寻路系统来提供路径支持。


然而,事情并没有这么简单。

由于有SeparationCohesionAlignment速度分量的存在,即使我们给每只鸟单独寻出来一条路径,也不能保证这只鸟就一定会严格按照路径行走。

比如我们为某只鸟寻出来的路径为((0,0), (0,1),(0,2))(我们把地图切成很多小块格子,坐标为格子坐标,不是实际的世界坐标)。

在从(0,0)到(0,1)运行的过程中,由于鸟群的干扰,可能会把这只鸟挤到了(1,1)格子,这时可能(1,1)是到不了(0,2)的,需要重新寻路。

这就意味着,每只鸟每跨过一个格子,就需要重新寻路一次,这么大的开销足以使FPS降到5。


在网上搜到一种解决方案。

给整个鸟群指定一个Leader。为Leader计算一条路径,Leader严格按照路径行走。鸟群中的其他鸟使用Flocking算法来跟随Leader即可。

我尝试了这种方案后,发现这个方案在绕过大片障碍物时非常好用。但是在通过狭窄通道时,很容易发生跟随失败,导致一些鸟永远卡在那里不能行动。

比如下面这种情况:

                   xxxxxL
                  x
  ------------ x --------------
                  x
                   x
                      xB

Leader在位置L处,B位置处的鸟要跟随Leader,必然要产生一个从B位置向L位置的速度。

如果B鸟按这个跟随速度运动,就会被卡在墙的一侧,永远的脱离队伍。

我尝试优化这种方案,除了Leader之外,我加入了Target角色。

所有的鸟在运动时,会在自身周围一定范围内寻找一个Leader或Target作为跟随的目标。

找到跟随目标之后,自身也会变成Target角色,供其他鸟跟随。

如果找不到合适的跟随目标,自己就会变成临时Leader。然后重新计算一条路径,并严格按照路径运动。直到遇见一个合适的Target之后,这只鸟就会再次变回Target。

这种方案可以应对各种极端障碍物情况。但是这个方案几乎把Flocking所有的特性都抹掉了,鸟群在整个运动过程中会排成一字长蛇阵,看起来非常不自然。


我找到当时的QQ聊天记录,仔细读了几遍,然后换了个思路。

计划让鸟群运行到某个目标点那一刻,使用Dijkstra算法计算出地图上所有格子到目标点的最佳运动方向。

这里有个小技巧,我们使用目标点作起始点,然后运行Dijkstra算法。

当Open列表为空时,就已经完成了地图上所有格子到目标点的最佳方向计算。

每只鸟在移动前,根据当前位置计算出当前格子,然后直接查询出下一步的目标点。

理论上,根据目标点计算出鸟的Velocity速度向量,再叠加SeparationCohesionAlignment速度分量就是最终的速度值。

然而,现实是残酷的。

经过实验发现,由于鸟群的作用力,经常会有鸟被挤进障碍物中,尤其是在经过狭窄通道时。

因此我们还需要静态避障速度分量。

在《Artificial Intelligence for Games, Second Edition》中第“3.3.15 Obstacle and Wall Avoidance”节中,讲到可以使用射线检测来躲避静态障碍物。

测试发现,当角度比较奇葩时,射线检测不到障碍物的存在,从而导致最终被挤到墙里面去,3.3.15节也有提到过这种情况。

最终,我采用了AABB来检测周围是否存在障碍物,当有障碍物时,根据障碍物的质心和当前鸟的位置来产生一个远离障碍物的速度分量,这个分量的权重要显著大于其他4个速度分量。

如果障碍物形状态复杂时,可能需要重写AABB检测逻辑,根据相交的边计算出远离障碍物的速度分量。


到目前为止,最大的开销就剩下为地图上所有格子计算最佳方向了。

如果地图过大,这样计算是不现实的。

在写这篇文章时,我想到了一个优化算法,还没来得及测试。

通过观察Flocking算法,不难发现鸟群中的鸟几乎全是按照大致相同的路线行走的。

也就是说,只要我们想办法生成一个有宽度的路径,基本上就可以满足给鸟群寻路的需求了。

首先使用AStar算法,从整个鸟群的质心到目标点计算出一条路径。

然后,对第一步中路径的每个格子,都使用Dijkstra算法,计算出周边格子到这个格子的最短路径。计算时要限制Dijkstra算法遍历的深度。只要我们选取的深度合适,大部分鸟行走的格子都会被命中。

值得一提的是,在应用Dijkstra算法时,路径中相临格子的周围是相互覆盖的,需要根据权重进行刷新。

举个例子:

已经使用AStar算法计算出A到D的路径为(A,B,C,D)。

对格子B应用Dijkstra算法时,对邻居E生成了最佳运动方向为向B运动,E到D的权重为E(1)+B(2) = 3。

对格子C应用Dijkstra算法时,同样会处理到邻居E,这时不能简单的跳过E,而应该计算E到D的权重为E(1) + C(1) = 2。

这时应将E的最佳运动方向改为向C而不是B。

如果某只鸟被挤到了一个我们事先没有计算过的格子上,就使用AStar以此格子为原点向目标点寻路。

这里有一个可以优化的地方,我们已经有了一条很宽的路径,只要AStar寻到已有的路径格子就可以停止继续寻路了。

最后,Demo在此

行为树的一种高效实现

我的玩具项目中,需要有一定智能的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]

上述工作流有不少弊端:

  1. 程序不满足Open-Close原则,业务程序员需要关心哪些字段是需要做多国语言处理的,一旦UI改了表现设计,可能需要程序修改代码。相比之下,改了UI表现的FairyGUI却不需要修改业务逻辑代码。

  2. 对策划不友好,策划需要手工维护Hero表和Language表之间的同步,人类极不擅长这类工作。这使用两表之间同步极易出错,而且不易发现(只有在运行时用到配错的那一行数据时,才能发现错误)。就算是使用自动化测试都不太可能覆盖表中100%的数据。

  3. 由于人类极不擅长Hero和Language表之间的同步,导致策划在修改Language表时,往往只增加不删除,这会导致Language越来越大。以我的经验来讲,这种情况是存在的,尤其是对于半路接手的策划。

  4. 由于所有跟文字相关的内容都被移到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表失去可读性等各种缺点。

谈谈数据库的选型

在开发游戏服务器程序的过程中,好像大家都默认使用Mysql, 如果有性能问题,大不了再加个Memcached, 或者干脆使用Redis来做数据库。

但这么做是否真的对所有模式的游戏服务器都合适呢, 对于某些游戏模式,是不是有更好的选择?

这是我最近在看《MySql是怎样运行的》,突然想到的问题。

我挑了三款存储模式完全不同的数据库, 来对比一下它们的特点。


Mysql: 一款关系型数据库。

由于有RedoLog,UndoLog的存在, 支持事务数据落地比较可靠

存储引擎InnoDB采用B+Tree作为存储结构, 而由于B+Tree的性质以及RedoLog,BinLog,UndoLog等机制的存在,导致Mysql的写入性能远低于查询性能。

因此Mysql适用于查询压力大,但是写入压力小的场景。虽然这些复杂的机制拖慢了写入速度,但是MySql可以提供各种复杂的查询

即使如此,由于Mysql的数据结构是严格和磁盘对应的,相比Memcached和Redis等,将数据以内存数据结构的方式完全存储在内存的程序来讲,Mysql的查询性能还是要差不少。

这也是为什么在一些读流量大的地方,有时候会加Memcached或Redis作为前端,以防止大流量将Mysql冲垮(还可以使用从机做读写分离)。


Redis: 一款读写性能都很卓越的NoSql内存数据库。

本质上Redis就是一个带持久化功能的内存缓存,所有的数据以最适合内存访问的方式存储,因此查询极快写入极快不支持事务仅支持键-值查询

其持久化方式分为RDB和AOF两种方式:

RDB是通过定时将进程内存中的数据集快照写入磁盘文件,这种持久化方式性能较高, 但安全性较低。默认配置下,可能会丢失最近60s的数据,由于RDB每次都是重新写入全量数据集,随着持久化频率间隔的降低,会显著增加CPU和IO开销。

AOF是性能和可靠性的另一种折衷, 每一条修改命令都会尽可能快的(不是立即,Redis会在Sleep前才会尝试)写入到文件系统缓存。至于什么时机通知操作系统将文件系统的脏页刷新到磁盘上, Redis最高可以配置为每次写入到操作系统文件系统缓存时,都执行刷新操作,默认为每秒通知操作系统刷新。

AOF文件的大小会随着数据修改次数的增加而逐渐变大,当大到一定程度后,Redis会Fork一个进程对AOF文件进行重写,以达到减少AOF文件尺寸的目的。AOF的重写时机同样可以进行配置。

不管是AOF还RDF方案, 都有一个不可避免的缺点, 每次生成RDB文件或重写AOF文件时, 都会将内存中全量的数据写入文件, 在数据量很大的情况下, 会产生CPU峰值


LevelDB: 一款写性能卓越的NoSql数据库。

LevelDB底层采用LSM数据结构来存储数据, 所以写入极快查询较慢, 不支持事务仅支持键-值查询(还支持键的遍历)

与Redis相反,LevelDB将所有数据都存储在硬盘上,仅在自身内存中缓存热数据

由于LSM数据结构的特殊性,LevelDB还需要WAL(Write Ahead Log)来保证数据的可靠性。

WAL的作用和MySql的RedoLog的作用几乎一样,都是用于在意外Crash时,恢复还没有写入磁盘的数据。

在LSM数据结构中, 所有数据都是存储在SSTable中, 而SSTable是只读的。

这意味着随着数据增删改次数的增加,SSTable会变的越来越大。这时LevelDB的后台线程会在合适的时机,合并SSTable,以达到减少SSTable文件的目的。

LevelDB在合并数据时,是以SSTable文件为单位进行的, 而每个SSTable文件的大小一般为2M。这保证了,即使在数据库存有超大规模数据时,其合并过程依然是可控的


总的来讲,MySql适合查询场景复杂, 而且查询多于写入的场景。Redis适合单进程数据量不大,并且对查询和写入都要求极高的场景。而LevelDB则适合于写多,读少的场景。

不管是Redis的内存限制,还是RDB生成/AOF的重写机制,都限制了其单进程能处理的数据量要远低于Mysql和LevelDB。同时,Redis的查询和写入性能也是这三者之间最出色的。


在我们游戏中,玩家数据是需要长驻内存的,即使一个玩家下线,别的玩家还是可以影响他的所有数据(包括货币和英雄)。

这意味着,我们必须在开服期间,就要从数据库加载所有游戏数据到游戏进程。之后只需要操作进程内数据即可。

在不考虑数据安全的情况下,甚至我们都不需要数据库。

只需要在停服时,像Redis写入RDB一样,将每个系统的数据按照约定的格式写入到不同的文件,下次开服再加载回来。

使用数据库的理由是,它可以让我们按需写入数据,可以提高数据的安全性。

那么,我们对它的需求就只剩一点了:“写入要快,持久化要安全”。

从安全性上来讲,Mysql, LevelDB, Redis的AOF都满足要求。

就写入速度而言,显然MySql落选了,因为他是为查询设计的数据库系统。

就现在需求而言,而Redis和LevelDB在CPU和内存足够的情况下,其实差别不大,甚至Redis要优于LevelDB。

如果我们想再节约一点,就会发现LevelDB在内存和CPU峰值方面优于Redis, 同时他的写入性能要差于Redis, 因为LevelDB有WAL和SSTable两次写入。

ps. 这种取舍其实很像数据结构的优化,一份平均每写10次只查一次的数据,显然没有必要每次写入之后都对数据排一下序,选择时关键是还是要看清数据库的定位以及自己的需求。

再谈Lua热更新(终)

在写这篇文章之前, 我特意在标题前加了个"终"字。因为我相信,这就是生产环境中热更新的最终出路。

大约在4年前,我实现过一版热更新

但是这个版本并不理想。在一些简单场景下工作良好,场景稍一复杂,就显得捉襟见肘。

比如下面代码, 我的热更新实现就无法很好的进行更新。

--M1.lua
local M1 = {}
local case = {
[1] = function() --[[xx]] end
[2] = function() --[[xx]] end
}
function M1.foo(x)
    case[x]()
end
return M1
--M2.lua
local foo = require "M1.foo"
local M2 = {}
function M2.foo(x)
    foo(x)
end
return M

它即不能很好的更新M1.foo函数,因为M2直接持有了M1.foo函数的引用。也不能很好的更新M1中的case引用的函数, 因为case中的函数不是任何一个函数的直接上值。

当然,我们可以加入一些强制规范来解决问题。比如:不允许一个模块持有其他模块的函数引用,不允许一个函数只被引用而不被函数引用,所有上值全部入表,等等。

不允许一个模块持有其他模块的函数这个问题不大,毕竟可以增加代码可读性。但是,限制总是有或多或少增加实现者的负担,也会限制实现者的创造性。

热更新作为一种非常规修复Bug的方案,我不希望他对实现者做过多的干扰。

在这之后我一度认为进程级滚动更新才是未来,不仅可以修复Bug, 还可以进行不停机功能更新。


直到前两天,和一位同学再次聊起热更新。

我突然想到,进程级滚动更新有一个致命的弱点,他是有损的(当然在WEB领域是无损了,因为WEB服务器无状态)。某个进程在升级期间,会有短暂的服务不可用。

进程级滚动升级和停服升级相比,服务不可用的时间会大大降低。但是就临时修Bug而言,热更新可能还是更为合适。

那么,还是想办法改造一下热更新的实现吧。

我又重新思考了一下整个程序的构成,程序是由模块组成的,而模块与模块的交互是通过模块的导出函数进行的。

这样如果我们以模块为粒度进行热更新,就不太会造成模块撕裂的现象。比如下面代码:

--M1.lua
local M1 = {}
local function foobar()
        print("1")
end
function M1.foo()
        foobar()
        print("foo1")
end

function M1.bar()
        foobar()
        print("bar1")
end
return M1
--M2.lua
local M2 = {}
local functin foobar()
        print("2")
end
local function M2.foo()
        foobar()
        print("foo2")
end
local function M2.bar()
        foobar()
        print("bar1")
end
return M2

如果仅仅只使用M2.foo去更新M1.foo, 就会造成新的M1.foo调用的foobar和旧的M1.bar调用的foobar不是同一个函数。

但是以模块为粒度进行更新就不会有这种问题,我很快便实现了第二版

随后发现,第二版除了解决了模块撕裂问题外,和第一版没有本质区别。第一版存在的问题在第二版依然存在。

问题并不是解决不了,但是这些方案都代表着超高的代价,我认为在生产环境这是不可接受的。

case表中引用函数问题,可以递归遍历上值中的Table来解决。但这里有一个潜在的风险,不小心引用了一个超大Table, 可能会有遍历整个LuaVM的风险。

一个模块持有其他模块引用的函数问题, 可以通过遍历整个LuaVM中函数的上值来修正。


种种迹象表明,不可能存在一种方案,即智能又高效又正确。

即然如此,只好采用一种更灵活,但是复杂的方案了。虽然很复杂,但是能解决问题

这个复杂的方案就是:不管是以函数为单位还是模块为单位,都不再实现一键热更功能。取而代之的是,每次Bug的修复,都需要重新编写修复脚本

修复脚本中,我们可以使用Lua原生的debug.upvaluejoin来正确的将修复函数引用到被修复的函数的上值,然后使用修复函数替换被修复函数

针对一个模块持有另一个模块的导出函数引用的情况,我们也可以使用debug.setupvalue来进行修正。

与此同时。我观察到,模块撕裂在某种程度上是不会有副作用的。

比如下面代码:

M.foo和M.bar虽然调用的不是同一个foobar函数,但是由于foobar1和foobar2逻辑相同,并且共享上值。这种情况下,模块撕裂现象虽然会增加内存,但却并不会有副作用。

local M = {}
local a, b = 0,0
local function foobar1()
    a = a + 1
    b = b + 1
end
local function foobar2()
    a = a + 1
    b = b + 1
end
local function M.foo()
        foobar1()
        print("foo2")
end
local function M.bar()
        foobar2()
        print("bar1")
end
return M

修复脚本的方案下,修复逻辑可以是千变万化。但是一个共通点,我们在编写修复脚本时总是需要先定位到一个函数,然后对两个或两组函数进行上值的join。

在这种思路下,我实现了第三版热更新。共提供三个接口:

  • sys.patch.create 用于创建一个上下文, 用于在随后的修复操作中做一些必要的缓存。
  • sys.patch.collectupval(f_or_t)用于收集一个或一组函数的上值信息, 该函数会递归遍历所有上值为函数的上值。
  • sys.patch.join(f1, f2)/sys.patch.join(f1, up1, f2, up2)用于将f1函数的上值以上值名字为关联信息引用f2的上值, 如果f1的某个上值名字不存在于f2的上值列表中,则这个上值的路径将会被存储到路径列表中, sys.patch.join在执行完之后, 总是会返回一个路径列表, 即使这个列表为空。

我们应该如何利用上面这组接口定位一个函数呢。

通过观察,我们可以得知一个事实。函数与函数的引用关系其实是一张有向有环图。这也就意味着不管我们想定位哪一个函数,它一定就在某一个函数的上值或者上值的Table中。

因此,sys.patch.collectupval收集来的上值,不但可以辅助我们做新旧函数的上值引用,还可以辅助定位我们需要更新的函数。

最后以一个简单的热更新例子来结束:

--run.lua
local M = {}
local a, b = 1, 1
function M.foo()
    a = a + 1
end
function M.bar()
    b = b + 1
end
function M.dump()
    return a, b
end
return M
--fix.lua
local M = {}
step = 3
local a, b = 1, 1
function M.foo()
    step = 4
    a = a + step
    b = b + step
end
function M.bar()
    b = b + 1
end
function M.dump()
    return a, b
end
return M
--修复脚本 将使用fix.lua来修复run.lua中的逻辑
local patch = require "sys.patch"
local run = require "run"
local ENV = setmetatable({}, {__index = _ENV})
local fix = loadfile("fix.lua", "bt", ENV)()
local P = patch:create()
local up1 = P:collectupval(run)
local up2 = P:collectupval(fix)
local absent = P:join(up2, up1)
print(absent[1], absent[2])
debug.upvaluejoin(up2.foo.val, up2.foo.upvals.b.idx, up2.dump.val, up2.dump.upvals.b.idx)
print("hotfix ok")
for k, v in pairs(fix) do
    run[k] = v
end
for k, v in pairs(ENV) do
    if type(v) == "function" or not _ENV[k] then
        _ENV[k] = v
    end
end

在这个例子中,我们可以看到fix.lua中的M.foo函数引用的上值b, 是不能被正确引用的。因为run.lua中的M.foo函数没有上值b, 这时我们就需要手动调用debug.upvaluejoin来修正fix.lua中的M.foo函数的上值b的引用。

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

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

在游戏服务器中,我们做服务拆分,大部分情况下都是为了可伸缩,而不是为了高可用(这里暂不考虑那些使用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:

ECS的初步实现

从我开始研究ECS算起, 到现在已经将近20天了。

第一版ECS库终于实现完成了。先不论性能如何,基本功能都实现了。

在我的理解中,ECS中最复杂的地方是EC部分的管理和查询。而S部分的复杂度主要是依赖关系的问题,这会取决于具体的项目。

因此,在这个ECS库中主要解决EC的问题,关于S的部分并没有提供。这也是我称为库而不是框架的原因。


在整个实现过程中,由于我还没能完全克服性能强迫症,导致我的心路历程非常坎坷(每次实现到一半,总会因为这样或那样的原因,让我推倒重来)。

最开始,我认为守望先锋的ECS之所以那么复杂,是因为他们使用了C++这种强类型语言。为了解决动态组合(动态添加和删除C)的问题,不得不在API上做出一些让步。

如果拿Lua来实现,语言本身就支持动态组合,那添加/删除Component的行为,可以退化为添加/删除“标签”功能。

每个System只需要过滤出含有特定“标签”组的Entity, 然后加以处理就行了。

很快我放弃了这一想法,主要原因是我认为作为一个合格的框架或库,它应该提供一些限制。可以让我们写出符合ECS原则,更易读的代码。

在上面的设计中,客户程序员很容易就违反了ECS原则,他完全可以只过滤某一个ComponentA, 然后去修改这个Entity中的ComponentB, 甚至删掉ComponentB但是并不会删除ComponentB的标签。这会导致一些很奇怪的Bug。而且从代码的易读性上来讲也没有好处。

在后续的设计中,我又陆续纠结了,Eid的分配问题, Component的存储问题,同一个Entity中的Component的关联问题。

在经过陆陆续续几次推倒重来之后,直到今天才实现完第一个版本。

在这不断的推倒重来中,我总是在是否“需要暴露Eid给客户程序”之间摇摆不定。最终,我认为是需要的。

我们总是需要在程序的某处去New出一个个的Entity。同样我们也总会需要在程序的某处,去修改某个特定Entity的某个Component数据。

在我看来,整个ECS的运行机制很像一个巨大的“粉碎机”。 我们总是在某一个入口投入足量的Entity, 然后ECS库或框架将这些Entity粉碎成各种Component,供System查询并操作。

因此在这一版的ECS库的实现中,我把Component作为主角来实现的。Entity的作用在这里,将一组Component进行关联,以方便Component查询和生命周期的管理。


先简单介绍一下API:

--创建一个名为Admin的world对象。使用相同名字多次调用ECS.fetch_world, 返回的是同一个world对象
local world = ECS.fetch_world("Admin")

--注册Component类型。 其中world.register的第二个参数是为了方便建立Component缓存池和Debug阶段检查一些Component的合法性(暂时还没有实现)。
world:register("vector2", {x = 0, y = 0})
world:register("vector3", {x = 0, y = 0, z = 0})

--创建一个Entity, 这个Entity只含有一个"vector2"的Component
local eid = world:new { vector2 = {x = 2, y = 2}}

--向eid所代表的Entity上添加一个"vector3"的Component
world:add(eid, "vector3", {x = 3, y = 3, z = 3})

--向eid所代表的Entity上删除一个"vector3"的Component
world:remove(eid, "vector3")

--查询world中的所有类型为"vector2"的Component
for v2 in world:match("all", "vector2") do
    w:touch(v2) --将Component v2置为脏标记
end

--查询world中所有被w:touch过的类型为"vector2"的Component
for v2 in world:match("dirty", "vector2") do
end

--查询world中所有已经死亡的类型为"vector2"的Component
for v2 in world:match("dead", "vector2") do

end

--删除Entity
world:del(eid)

--执行清理操作,每调一次为一个逻辑帧
world:update()

整个设计大概是这样的:

每个Component类型都有一个数字id称为tid。每个Component实例都有一个数字id称为cid。我们总是可以根据tid和cid来找到某一个具体的Component实例。

在相同的Component类型中,新创建的Component的cid总是比旧的Component的cid要大。在world:update时所有Component的cid会进行重排,但是依然满足这一约束。这会提供一个便利,在我们使用for遍历world:match时,依然可以不受限制的添加任何Compoent实例。

当某个Component实例被删除时,仅将其挂在“dead”链表上,并不做其他操作。如果已经在“dead”链表上,则不做任何处理。这会产生一个限制,刚对某个Entity删除了一个Component之后,不可以立马添加一个同类型的Component

当某个Component实例被touch时,仅将其挂在“dirty”链表上。

当某个Entity被删除时,将此Entity下的所有Component标记为"dead", 然后将Entity挂在"dead"链表,不做任何处理。

在执行world:update时会产生以下行为:

1. 释放所有的Entity及其eid(以备后面复用)
2. 释放所有标记为“dead"的Component, 并整理存活的Component的cid
3. 清除"dead"链表
4. 清除"dirty"链表

总的来讲,所有的添加都是立即生效,所有的释放都会延迟到world:update中执行。

ps. 在这次纠结的过程中,在一定程度上治愈了我的性能强迫症。