Lua中的函数式编程

最近在用Lua实现Websocket协议时,碰到了一个直击我的思维惯性的弱点的Bug。代码大约如下(实际实现较为复杂,比如还支持wss协议,因此定位到问题也着实花费了一些功夫,毕竟GC的执行是异步的.):

--websocket.lua
local M = {}
local mt = {
__index = M,
__gc = function(sock)
    close_via_c_layer(sock[1])
end}
function M:connect(url)
    local ip,port = parse from url
    local fd = connect_via_c_layer(ip,port);
    local sock = setmetatable({fd}, mt)
    return sock
end
....
return M
--foo.lua
local ws = require "websocket"
local sock = ws:connect("ws://127.0.0.1")
print(sock)

--main.lua
require "foo"
while true do
    collectgarbage("step", 1024)
    sleep for a while
end

起初,我发现foo.lua中建立的链接会被莫名关闭,各种排查websocket的实现。最后才发现竟然是sock对象的__gc函数被触发了。

查到的问题后,我足足想了有5分钟才明白过来为什么sock会被GC掉。

因为潜意识中,foo.lua类似于下面C代码,其中sock变量是与整个C代码的生命周期一致的。而在C语言中,代码是不会被回收的。因此sock是作用域有限的全局变量。

#include "websocket"
static websocket sock;
void exec()
{
    sock = websocket::connect("ws://127.0.0.1:8001");
    print(sock);
}

那为什么在Lua中sock变量会被GC掉,就要从Lua的基本规则说起:

在Lua中,一共有8种基本类型: nil、boolean、number、string、function、userdata、 thread 和 table。

其中’string,function,userdata,thread,table’等需要额外分配内存的数据类型均受Lua中的GC管理。

而require "foo" 的本质工作(如果你没有修改packaeg.preload的话)是在合适的路径找到foo.lua,并将其编译为一个chunk(一个拥有不定参数的匿名函数),然后执行这个chunk来获取返回值,并将返回值赋给package.loaded["foo"]。

在这个chunk被执行之后,整个LuaVM再无一处引用着此chunk. 因而此chunk可以被GC掉,而顺带着,被chunk引用的sock变量也一并被GC掉(因为sock变量仅被此chunk引用)。

一切都是这么的自然和谐,惟一不和谐的就是,我犯了这个错误。

以往在研究GC时,就单纯的研究GC,在一张图上经过若干步骤进行mark,再进行若干步骤进行sweep。

在编写Lua代码时,却往往根据以往的c/c++经验来判断变量的生命周期, 毕竟就算在如java,C#这些带GC的面向对象语言中,这些经验依然适用。

也因此,在我面向对象编程范式(也许叫‘基于对象’更合适,毕竟我极少使用继承)的思维惯性下,潜意识竟然将这两个紧密相关的部分,强行割裂开来。

以往写Lua代码时,我一直以为Lua是“原型对象”编程范式,然而这个“大跟头”让我发现,原来Lua的底层基石竟然是“函数式编程”范式(非纯函数式编程语言,Lua中的函数有副作用)。


在我们写代码之初,就被人谆谆教导:“程序=算法+数据结构”。

过一段时间(也许很久),我们又被教导各种编程范式,如:“面向对象编程范式,函数式编程范式”。

接着你就会问:“什么是函数式编程,什么是面向对象编程?”

会有很多人告诉你:“在函数式编程语言中,函数是一等公民。在面向对象编程中,万物皆对象”。

然后你(主要是我自己)就开始似懂非懂的用这些概念去“忽悠”其他人。

却从来没在意过,整个编程范式中,数据的生命周期是以何种方式被管理着,以及数据在以何种方式进行转换和通信。

借着这个Bug的契机,我从数据的视角来重新审视了一下这些话,有了一些意想不到的发现。这次终于打破了以往的范式惯性(上次学Lua时,我也是自信满满的认为我懂了函数式编程,结果摔了个大跟头)。

先来大致看看面向对象的哲学。

在纯面向对象编程语言中(C++显然不算),所有的逻辑交互均是在对象之间产生的,不允许变量产生在对象之外。

即使他们在努力的模仿函数式编程,比如所谓的委托,匿名函数。然而这些函数背后却总是逃不开this指针的影子。比如下面代码:

using System;
using System.IO;
namespace test {
class TestClass {
    public string a;
    public delegate int foo_t();
    public int bar() {
        foo_t func = ()=>{Console.Write(a + "\n"); return 0;};
        func();
        return 1;
    }
};
class Program {
    static void Main(string[] args)
    {
        TestClass tc = new  TestClass();
        tc.a = "foo";
        TestClass.foo_t cb = tc.bar;
        cb();
    }
}}

再来看看函数式编程范式中一等公民的定义:"如果一个语言支持将函数作为参数传入其他函数,将其作为值从其他函数中返回,并且将它们向变量赋值或将他们存储在数据结构中,就在这门语言中,函数是一等公民。

我认为对于有C/C++背景的人来讲,这不足以解释函数式编程的特点。

因为在C/C++语言中,函数指针同样可以做到上述所有的事情。

惟一的区别就是函数式编程语言中的函数其实是闭包(所需要的上下文+指令码(也许是CPU指令,也许是VM的OPCODE)),而C语言中的函数就真的是一段CPU指令。这两种函数有着本质上的区别。

类比面向对象是万物皆对象,函数式编程就应该是万物皆函数。

而实现万物皆函数,闭包是函数式编程必不可少的条件(这里不讨论纯函数式编程范式,连LISP都不是纯函数式编程语言)。

在函数式编程范式中,所有的逻辑交互均是以函数(闭包)为主体来运行。

每一个函数会携带自身所需的环境变量,以便在任何需要执行的地方执行。

自身的GC机制会保证,在函数(闭包)没有被回收前,其携带的环境变量永远有效。

在Lua的require和chunk的机制中我摔的跟头充分验证了这一点。

最后让我绞尽脑汁举一个不太恰当的例子来收尾吧(毕竟我也是刚刚(自以为)重新认识了函数式编程):

local function travel(tbl, process)
    return function()
        for k, v in pairs(tbl) do
            process(k,v)
        end
    end
end

local function printx(title)
    return function(x, y)
        print(title, x, '=>', y)
    end
end
local tbl = {"foo", "bar"}
local func = travel(tbl, printx("index:"))
tbl = {"newfoo", "newbar"}
----other logic
func()

重构登录逻辑

终于又甩掉了一个包袱, 这是我重构完第一句想说的话。

从我入职开始, 就因为这套登录逻辑的复杂性而略为不满, 其间还坑过我一次,但是因为一直勉强能用,所以也没有理由对它动手。

这一次终于因为不能够满足新需求,而让我有理由可以重构这段代码了。


旧的登录流程大致如下:

    $UST=(uid,session,token)
    Client-------------AuthServer---------------------GameServer-----------DBProxy
     *--"账号密码认证" ---> * 
                     检查账号密码,
                     生成session和token
                          *----------发送$UST----------->*
                                                     记录$UST
                          *<----------成功--------------*
    *<------$UST----------*
    *-------使用$UST登陆-------------------------------->*
                                                     校验$UST是否匹配
                                                        *------请求加载------->*
                                                                      加载玩家数据
                                                        *<---返回玩家数据------*
    *<---------------------------返回登陆成功------------*

每一个认证流程都会生成一个惟一session,类似tcp连接. 甚至加载玩家数据也会带着同样的session请求。如果此次数据加载与当前登陆session不符,则拒绝使用,直接抛弃。

session的存在使的整个“认证-登陆”流程可以做到精确无比。

然而,这种精确会带来其他问题,例如客户端出于某种bug多发了一次认证,就会导致整个登陆流程失败,并且会导致重复加载玩家数据(事实上我真的被这个问题坑过,查了好久才发现问题)。


经过这次重构后,我去掉了session机制,并将GameServer的整个登陆流程切分成三块相对独立的逻辑,即“认证逻辑”,“加载逻辑”,“登陆逻辑”。

  1. 当AuthServer检查账号密码正确后,即颁发token, 将uid,token发往GameServer。
  2. 当GameServer的“认证逻辑”到消息uid,token之后,记下token并随即调用“加载逻辑”进行数据加载。
  3. 当GameServer的“登陆逻辑”收到协议后会检查uid,token是否匹配,如果匹配则等待数据加载完成,然后向客户端返回登陆成功。

“认证逻辑”在收到AuthServer的消息后,仅简单的记录每一个要登陆的uid对应的最新的token,并踢掉当前在线的链接。

“加载逻辑”则需要对加载请求进行过滤,防止重复加载。当收到加载请求后,如果数据已经加载途中或已经加载完成,则直接扔掉加载请求。为了防止DBProxy挂掉,而造成加载卡死。每一个玩家会有一个30秒的加载超时时间(即超过30s后即使DBProxy还没有返回数据,下次收到加载数据请求,依然会再次向DBProxy请求)。

加载数据返回后,总是检查当前内存中是否已经有加载成功的数据,如果没有才使用当前DBProxy返回的玩家数据,如果已经有数据,则直接抛弃。

之所以这样做,是为了数据一致性问题。来看一下如下操作序列。

GameServer视角:加载数据请求A—〉等待30秒—>加载数据请求B—->加载数据请求A返回—>玩家开始操作,修改玩家数据—>向DBProxy更新数据—>另载数据请求B返回。

DBProxy视角: 加载数据A->返回加载数据A->加载数据B->返回加载数据B->修改数据

如果此时应用数据B,则在A返回和B返回对玩家数据的修改则全部会丢失。而旧的登陆逻辑,之所以在加载数据时依然带着session,应该也是为了防止数据一致性问题,但是我们玩家数据都是采用Write-Through方式来将一个玩家的所有数据都cache内存之后才进行修改的。因此我认为只取第一份成功加载的数据就可以解决一致性问题。

重构之后的登陆流程大概如下:

    $UT=(uid,token)
    Client-------------AuthServer---------------------GameServer-----------DBProxy
     *--"账号密码认证" ---> * 
                     检查账号密码,
                     生成session和token
                          *----------发送$UT----------->*
                                                     记录$UT
                          *<----------成功--------------*--------请求加载----->*
    *<------$UT----------*                                         加载玩家数据
                                                         | <-----返回玩家数据--*
    *-------使用$UST登陆--------------------------------> |
                                                         |
    *<------返回登陆成功----------------------------------* 

本来“加载逻辑”还要负责登陆超时的淘汰操作,即数据加载之后,客户端迟迟不向GameServer发送登陆请求,这时需要将加载出来的数据从GameServer淘汰掉。

但是由于我们专为手游实现了半弱联网机制。在socket断掉之后,N分钟以内会保留玩家数据。这可以保证在地铁或电梯等信号不好处链接断掉后,可以在信号良好时快速登陆。

因此“加载逻辑”将数据加载完成之后,直接交给原本的数据淘汰逻辑即可。


除了登陆流程以外,这次重构我还修改了"登陆"的语义。

重构前, 对AuthServer发起认证时,会先尝试对账号进行注册,再发送登陆协议。虽然这样可以避免在新号时连着发送三条认证相关的协议。但总感觉有点bad taste。

重构后,我将"登陆"定义为"如果账号不存在则先执行注册, 然后执行登陆逻辑"。

重构前,对GameServer发起登陆时,如果uid还没有对应的游戏数据,同样会返回错误。然后客户端根据错误码去发初始化消息进行初始化, 在初始化的过程中,如果由于某种原因连续多发,同样会出现问题。

重构后,当GameServer收到$UT准备加载数据前,会先检查uid是否被初始化过数据,如果没有,则直接向DBProxy请求创建。DBProxy创建玩家数据与DBProxy加载玩家数据具有相同的返回。

这样整个"认证-登陆"逻辑相关的协议,由4条("注册","认证","创建","登陆")降为2条("认证","登陆")。

这里会有一个问题,刚开服时,可能有很多玩家只注册完就卸载走人了。这样会浪费我们的服务器资源。因为他只要发一条"认证",我们就帮他把数据创建好了。

幸运的是,我们新实现里, 恰好提前实现了删号功能。即一个低级玩家多久没登陆过之后,过一段时间会自动被清理。

ps.重构之后,个人觉得对于整个流程,服务端和客户端都各种更内聚了,因为整个登陆流程的判断都被挪到了服务端。

Unity资源管理(续)

上次增加资源半自动释放机制之后,根据log显示已经有30%~40%的资源被释放掉了(大部分为UI资源)。然而内存问题,并没有明显改善。

我们的资源管理是通过一个叫做ABM的模块进行管理的,ABM采用标准的引用计数方案来管理资源和AssetBundle的生命周期。

当使用ABM.load_asset时会首先检查这个资源的引用计数是否为0,如果为0则会触发加载相应AssetBundle操作。

加载AssetBundle时会首先检查AssetBundle的引用计数是否为0,如果不为0则直接将引用计数加1.并将结果返回即可。

如果AssetBundle的引用计数为0,则除了要对引用计数加1之外,还需要递归加载其所依赖的其它AssetBundle。

如果所需要加载的AssetBundle有依赖于其他AssetBundle,则先递归加载所有依赖的AssetBundle,最后再加载自身。

当卸载一个资源时,首先将其引用计数减1,然后检查其引用计数是否为0. 如果引用计数为0,则触发AssetBundle卸载操作。

卸载AssetBundle时,同样将其引用计数减1,如果引用计数为0,则调用Unity接口AssetBundle.Unload(true)真正释放AssetBundle. 同时递归卸载依赖的所有AssetBundle。

由于担心资源泄漏不可控,所以我们并没有使用AssetBundle.Unload(false)来进行AssetBundle释放。


在整个流程,只有AssetBundle的引用计数为0时,才会被调用Unity接口进行释放。而仅在AssetBundle被释放时,其内部被加载过的资源才会被释放。

换句话说,假如一个AssetBundle有10个资源,如果先加载其中9个,再加载任意2个,最后再将上次加载的9个资源进行释放。这10个资源就会同时存在于内存之中。

因此一个AssetBundle的利用率(即AssetBundle中同时引用计数大于0的资源数量除以AssetBundle中的资源数量)越低,这个AssetBundle中的资源同时出现数量就会越少,相邻两次同时存在内中的资源集合的交集就可能会越小,资源内存泄漏的概率就越大。

当然事情并不是绝对的,如上面的例子,如果先卸载9个资源,并且此AssetBundle没有被其他AssetBundle所依赖,就会产生一次AssetBundle.Unload(true),此时再加载此AssetBundle中的2个资源时,这个AssetBundle会被重新加载,并从AssetBundle加再次加载所需的2个资源。这样就不会有内存泄漏。

但是实际的AssetBundle依赖关系及资源加载顺序都比较复杂,很难保证上述良好的情况及顺序。因此我认为AssetBundle的利率用还是有很大的参考价值的。

为此,我写了一个AssetBundle Profiler,通过折线图来实时显示当前所有AssetBundle的平均利用率。

当选中某个采样点时,可以详细看到此时每个AssetBundle的利用率,并可以查看任意一个AssetBundle中所有资源的引用计数情况,及所在的图集(如果是图片的话)。

相信通过连续观察某一个AssetBundle的资源的详细加载情况,可以为我们如果优化拆分AssetBundle有不错的帮助。比如,我们可以通过资源的使用频次,根据频次的多少来做成树状态倚赖的AssetBundle关系,或者将逻辑上互斥的资源拆分成多个AssetBundle, 即使这些资源只属于同一个模块使用。


然而,上面的方法只能一定程度上改善内存泄漏问题,并不能真正解决问题。因为我们真的很难保证AssetBundle中的所有资源一起加载一起释放。

最好的办法就是,在一个资源的引用计数为0触发卸载AssetBundle之前,先调用Resources.UnloadAsset,将这个资源进行释放。

上述ABM的实现中,没有执行此操作的原因在于,当被加载的资源是一个Prefab时,他可以引用各种其他资源,这些资源会被AssetBundle.LoadAsset(Async)时, 会被Unity底层进行加载。

如果这个Prefab所依赖的资源在其他AssetBundle中,Unity就会通过AssetBundle的依赖关系告诉我们,需要加载这个被依赖AssetBundle。 至于Prefab所用的资源则由Unity底层自动加载,上层的ABM是感知不到的。

换句话说,ABM中的资源的引用计数是不准确的,它的精度仅能够正确指示AssetBundle的生命周期,而不能正确指示其自身的生命周期。

如果要想使资源的引用计数准确指示出资源的生命周期,就必须在加载Prefab这类引用其他资源的资源时,修正所有被Prefab依赖的资源的引用计数。

如果要这么做,就必须要做好两件事。

  1. 如何运行时获取资源之间的倚赖关系

  2. 如何时处理资源与AssetBundle的引用问题

对于第一件事,Unity并没有提供运行时获取资源之间的依赖关系。幸运的是,AssetDatabase.GetDependencies提供了一个非运行时接口。因此我们可以在生成AssetBundle时,通过生成一个文件来存储资源间的依赖关系并在运行时解出。

如果一个资源被“引用”之后引用计数为1,则递归对它所依赖的所有资源引用计数加1。同样如果一个资源被卸载后,如果引用计数为0,则递归对他所依赖的资源引用计数减1。

由于Unity底层会自动加载被依赖的资源。为了避免无谓的开销,在操作引用计数时,我们仅仅去修正资源的引用计数而并不实际去加载资源,同样也不需要去加载相应的AssetBundle(也不去操作其引用计数)。

这对我们做好第二次事,造成了困扰。因为此时资源的引用计数与AssetBundle的引用计数完全割裂了。我们需要重新找到一个判断何时加载AssetBundle的依据。

最开始我认为应该将资源间依赖产生的引用计数单独记录,可以叫depend_ref, 而原先的引用计数ref含义及触发的操作保持不变。

如此,我们就可以在产生资源依赖时修正depend_ref,而在资源释放时,如果ref和depend_ref同时为0,则调用Resources.UnloadAsset。

这样做一定是对的,因为其实depend_ref与AssetBundle之间的依赖关系其实是重合的,所以就算ref的值为0而触发AssetBundle卸载操作,只要depend_ref不为0,这个AssetBundle的引用计数一定大于1,从而不可能被真正释放。

经过观察发现,而在释放时,depend_ref+ref一起产生作用,在加载时,ref单独产生作用,在处理依赖关系时depend_ref单独产生作用。

而ref产生的惟一作用就是当它为0时,进行加载和卸载AssetBundle。

前面说过就算ref等于0只要depend_ref大于0,AssetBundle是不可能被卸载的,因为depend_ref本质是反应的是AssetBundle之间的依赖关系,同时因为depend_ref大于0,说明依赖他的资源还在内存中,因此资源不能释放,他所在的AssetBundle也不能释放。因此depend_ref和ref逻辑是统一的,可以进行合并。

而在加载时,ref的作用仅仅是在等于0时进行AssetBundle加载。这是一个2值变量,就是说要么是true, 要么是false。恰好我们有一个相似的变量可以使用,每个被加载成功且没有卸载资源,ABM必须要保留其引用,以避免重复加载。当我们卸载此资源后,为了避免被误为,一般会将资源引用置为null。终于,ref可以和depend_ref进行合并了,我们的抽象更完美了一些。


修改后ABM流程如下。

当加载一个资源时先通过资源间的依赖关系修正相关资源的引用计数,以正确表明资源的生命周期。

判断需要通过ABM加载的资源的引用是否为null,如果不为null则直接返回。如果为null则加载相应的AssetBundle(处理AssetBundle及其依赖的引用计数逻辑不变)。

当卸载一个资源时同样根据资源间的依赖关系修正相关资源的引用计数,如果引用计数为0,且ABM持有的资源引用不为null,则调用Resources.UnloadAsset同时触发AssetBundle的卸载操作。然后将资源引用置为null。

ps. "释放"指通过AssetBundle.Unload(true),而"卸载"指处理AssetBundle的引用计数,如果为0,则真正"释放"

pps. 如果多张图片在一张图集里,只要图集中任意一张图片没有Resources.UnloadAsset,整张图集也不可能被卸载。

DC3算法

最近做了一个差量更新工具, 实质就是一个Diff工具。这个Diff工具在本地生成一个patch文件。客户端通过网络下载到本地后,根据本地文件和patch文件来生成最新版本文件。

与传统patch不同的是,为了尽可能的减少网络传输,patch文件需要尽可能的小,并且不需要逆向patch(从版a到版本b生成的patch, 版本b使用这个patch可以还原到版本a).

基于以上考虑,我重新设计了一个二进制patch格式,整个patch文件中有两种Action(分别是COPY, INSERT),大致数据结构如下:

struct COPY {
        int pos;
        int size;
};
struct INSERT {
        int size;
        uint8_t buf[];
};

其中COPY代表从源文件a的某个位置(COPY.pos)copy一段(COPY.size)数据过来,INSERT代表在新文件b当前位置插入一段数据(这代表这段数据在文件a中找不到)。

之所以不需要新文件的位置,是因为在生成patch时会严格按着新文件的写入顺序来生成patch, 这样也可以尽可能少的减少Action头所带来的开销。

在生成COPY指令时,我遇到了一个问题.

即,如何快速找到,同时存在于文件a和文件b中的最长子串。算法导论上的LCS(公共子序列)算法并不是很适合我,因为COPY只是去借数据,并不在乎这块数据在哪个位置。

最终发现,有序后缀数组更符合我的需求,空间复杂度极底,并且可以以lg(n)的时间复杂度来快速完成匹配。但是其生成算法DC3,我搞了将近2周才总算搞明白。

整个算法一共就分4步,原始数据在buf中,长度为N,(这里仅粗略描述):

  1. 将(i % 3 != 0, i >= 0 and i < N)的值取出来放到一个数组SA12中.

  2. 对S12进行排序, S12中的每个值n都代表一个三元组(buf[n],buf[n+1],buf[n+2]),排序后得到一个数组s12, 其中s12[x] = rank(x = n / 3 if n % 3 == 1, x = n / 3 + n1 if n % 3 == 2)。n1为i%3==1的个数。

  3. 如果任意两个三元组都不相等,说明仅凭前三个字母就可以对后缀确定顺序,则直接执行步骤4。否则,对s12中的数据递归执行DC3。

  4. 根据s12来生成数组SA12,然后将(i % 3 == 0,i >= 0 && i < N)的值取出放入SA0并进行排序,与SA12进行有序合并,成为SA。SA即为后缀数组的有序列表。

这算法并不是通常见到的,如快排,二分查找,甚至红黑树那么直观。他神奇到,我完全不知道这是在做什么,后缀数组已经排完序了。

在看这个算法时,在第2步我有几个很大的疑惑。

一是有个很神奇的操作,在生成s12的时,如果n % 3 ==1, 要把rank值放左边,n % 3 == 2要把rank值放右边。

二是左边和右边中间如果是连续的(没有空洞x, buf[x]会比buf数组中所有值都要小),就必须要插入一个分隔符(比buf数组中所有值都要小)

三是为什么要选3这个数字,2行不行。


搞明白之后发现,整个算法的核心思想就是"收敛", 运用递归的思想不断的收敛,直到比如结果为止。举个例子:

              0 1 2 3 4 5 6 7 8 9 10
char buf[] = "m i s s i s s i p p i";

第一步先拿到SA12= [1,2,4,5,7,8,10],

本质上他们代表的是:[‘1,2,3′,’2,3,4′,’4,5,6′,’5,6,7′,’7,8,9′,’8,9,10′,’10,x,x’],不存在的以x代替buf[x]一定会最小值

对SA12进行排序之后原始排序如下.

[‘1,2,3’=【3】,’2,3,4’=【5】,’4,5,6’=【3】,’5,6,7’=【5】,’7,8,9’=【2】,’8,9,10’=【4】,’10,x,x’=【1】],

将n%3==1的放左边,n%3==2的放右边之后得到如下列表:

[‘1,2,3’=【3】,’4,5,6’=【3】,’7,8,9’=【2】,’10,x,x’=【1】,’2,3,4’=【5】,’5,6,7’=【5】,’8,9,10’=【4】], 因为这里有x,而buf[x]一定比buf[0~n]中的值都要小,所以就不用插入分隔符了,后面会看到分隔符的作用。

从上面列表可以看出’1,2,3′ === ‘4,5,6’ 这说明三元组不足以用来确定后缀的排序(不满足步骤3),因为要接着递归执行,先得到SA’如下

[‘1,2,3,4,5,6,7,8,9′,’4,5,6,7,8,9,10,x,x’,’7,8,9,10,x,x,2,3,4′,’10,x,x,2,3,4,5,6,7′,’2,3,4,5,6,7,8,9,10′,
‘5,6,7,8,9,10,x,x,x’, ‘8,9,10,x,x,x,x,x,x’]

可以明显看到,之所以要把i%3==1的放左边,i%3==2放右边,其实是为再次递归DC3做准备。第二次递归DC3,实质上是取所有后缀的前9个前缀来进行排序,如果还有相同的,则再次递归采用前27个前缀进行排序,直到排出顺序为止。

为了利用上次递归的结果,上面数组会被转化成转换之后(【3】【3】【2】【1】【5】【5】,【4】)再递归传入DC3。

而之所以要插分隔符,其实是为了防止类似序列中’7,8,9,10,x,x,2,3,4’中的’2,3,4’参与排序,毕间7,8,9,10已经是从位置7开始后缀子串的全部内容了,如果2,3,4参与比较就会产生错误。因为buf[x] < buf[i] (i >= 0 && i < n),因此当碰到x, 就会终止排序。

那么为什么要选3这个数字,其实跟步骤4是有关系的。

在步骤4进行有序合并时,i%3==1时,会将3元组扩展成4元组,i%3==2时,将3元组扩展成5元组,之后再比较。

当i%3==1时,如’0,1,2,3′, ‘1,2,3,4’ 由于’1,2,3’和’2,3,4’的值我们已经知道了,所以这两个四元组的比较可以简化为’0,s12[1]’与’1,s12[2]’之间的比较,由于s12[1]中的值各不相同,因此’0,s12[1]’ 与 ‘1,s12[2]’必不相同。

当i%3==2时, 如’0,1,2,3′, ‘2,3,4,5’,可以发现s12[3]不存在因为3%3==0, 所以需要将4元素扩展成为5元组,‘0,1,2,3,4′,’2,3,4,5,6’,这样就可以化简为’0,1,s12[2]’, ‘2,3,s12[4]’来进行比较。

其实到这里,为什么不用2就很明显了,因为在最后一步合并时2不满足重用上一步结果的要求

总的来说这是一个很神奇的算法,有动态规划的影子,各个步骤又配合的天衣无缝。

开卷有益(UNIX编程艺术篇)

最近《计算机程序设计艺术》看多了,每次写完代码之后,总会习惯估算一下指令级的开销。导致每次写代码都是性能导向,违反了很多设计准则。因此打算重新看一下《UNIX编程艺术》,来拉一下已经严重倾斜的天平。

刚看了二页,又想起一个困扰我多年的问题,而没想到的是这次我似乎想到了解决办法。

在写服务器程序时,将数据持久化到数据库,是一个必不可少的操作。它需要将一个结构体进行打包,然后通过网络发给数据库,数据库再进行,并将操作结果通过网网络返回给应用程序。虽然可以通过这样或那样的手段,降低这些步骤之间的延迟,但是其本身带来的开销还是远大于一次函数调用。

因此在写代码时,通常无法忽略持久化所带来的开销,需要尽可能的合并对同一对象的持久化。

然而合并过程往往没有那么美好,这会会频繁打断原本我们完美的抽象,让我们编写逻辑时总是需要随时背起一个思想包袱。

下面举个简单的例子。

在这个例子里,我们会有两个模块,一个是Hero模块对外提供对某个hero对象的操作(这里仅提供加攻击力和加经验),另外一个是Team模块,调用Hero模块提供的接口对一批hero进行操作(这里假设所有操作都是按队伍操作的)。

//Hero模块
struct hero {
int heroid; 
int attack; //攻击力
int exp;    //当前经验
int level;  //当前等级
};

std::unordered_map<int, struct hero> heros;

static void
persistent(int heroid)
{
    auto &h = heros[heroid];
    save_to_db(h);
}

void add_exp(int heroid, int exp)
{
    auto &h = heros[heroid];
    h.exp += exp;
    if (h.exp > exp_of_next_level)
        ++h.level;
    persistent(heroid);
}

void add_attack(int heroid, int val)
{
    auto &h = heros[heroid];
    h.attack += val;
    persistent(heroid);
}

//Team模块
void team_award()
{
    add_exp(1, 50);
    add_attack(1, 60);
}

上面的代码咋一看,很完美啊,高内聚,低耦合,API之间提供的功能也很正交。

但是它有一个致命问题,忽略了persistent函数所带来的开销,这个函数与普通函数是不同的。上面的代码一共会对同一个hero对象执行两次persistent操作。也就是整个开销扩大了200%,并且在我们编写业务逻辑时往往不止调用2个接口这么少。因此需要将team_award函数中将所有对heroid为1对象的persistent操作进行合并。

合并方法有多种,这里仅列出我最常用的一种(仅适用于1~3个同类型操作之间的合并,如果操作多而杂,这样做就非常不妥了),就是将add_exp和add_attack进行合并,提供如下函数,并在team_award函数中调用。

void add_exp_attack(int heroid, int exp, int attack)
{
    auto &h = heros[heroid];
    h.exp += exp;
    if (h.exp > exp_of_next_level)
        ++h.level;
    h.attack += attack;
    persistent(heroid);
}

这时代码开始有点’bad taste’了,很显然这是违反了‘正交性’原则的。在某些地方我们需要编写诸如`add_exp_attack(1, 0, 10)`类似的代码。然而我却一直没有办法,一直沿用至今。

直到今天我再次打开《UNIX编程艺术》时,我忽然发现了服务器程序的一个规律。那就是,服务器逻辑总是由‘客户端请求’和‘定时器超时事件’驱动的。

那么请处理完一个‘客户端请求’或‘定时器超时事件’之后应该就是最佳的持久化时机。

因此,只要我们在处理这两类事件需要持久化时设立Dirty标记,再由框架在每次处理完‘客户端请求’和‘定时器超时事件’之后根据Dirty标记去持久化所有改动的数据。困扰我数年的持久化合并问题就这么完美的解决了。

我们需要增加一个persistent模块,改动后的伪码大概如下:

//persistent模块
typedef (persistent_cb_t)(int key, int ud);
struct dirty {
    persistent_cb_t *cb;
    int ud;
};
std::unordered_map<int, dirty> persistent_cb;

void persistent_pend(int key, persistent_cb_t *cb, int ud)
{
    auto &d = persistent_cb[key];
    d.cb = cb;
    d.ud = ud;
}

void persistent_clear()
{
    for (auto &iter:persistent_cb) {
        auto &d = iter.second;
        d.cb(iter.first, d.ud);
    }
    persistent_cb.clear();
}
//Hero模块
struct hero {
int heroid; 
int attack; //攻击力
int exp;    //当前经验
int level;  //当前等级
};

std::unordered_map<int, struct hero> heros;

static void
persistent(int heroid, int ud)
{
    auto &h = heros[heroid];
    save_to_db(h);
}

void add_exp(int heroid, int exp)
{
    auto &h = heros[heroid];
    h.exp += exp;
    if (h.exp > exp_of_next_level)
        ++h.level;
    persistent_pend(heroid, persistent, 0);
}

void add_attack(int heroid, int val)
{
    auto &h = heros[heroid];
    h.attack += val;
    persistent_pend(heroid, persistent, 0);
}

//Team模块
void team_award()
{
    add_exp(1, 50);
    add_attack(1, 60);
}

//Socket请求处理模块
void socket_dispatch(int cmd, packet *req)
{
    switch(cmd) {
    case 1:
        team_award();
    }
    persistent_clear();
}
//Timer超时事件处理模块
void timer_expire()
{
    //调用所有超时回调
    persistent_clear();
}

由此我们完美解决了,代码抽象和合并持久化之间的矛盾。

谈谈我对数据同步的理解

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

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

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


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

又一个lua调试器

最初,我并没有打算为Silly提供一个lua调试器,因为我本人不是一个重度调试器使用者。在开发期间出bug,看一下代码,打几条log可能比使用调试器会更快的找到问题,尤其是服务端程序,在很多时候其实只有log这一原始工具可以使用。但就我周围的人来推断,应该还是有很多重度调试器使用者。

因此,最终还是计划为Silly增加一个lua调试器作为基本组件存在。但是这个调试器到底以哪种方式提供调试功能,我一直在纠结中。

就我个人而言,我用过至少两种完全不同的调试器,gdb和dtrace(严格来讲dtrace可能不算是调试器)。

gdb主要用于开发期间进行阻塞式调试,虽然也可以写调试脚本用在生产环境中调试,但是在gdb加载符号文件时,延迟比较明显。

dtrace提供的是动态跟踪手段,在程序中放置相应的探针,当程序执行到探针的位置时,就执行这个探针上的函数。在放置探针时几乎没有卡顿延迟的现象,而且在放置探针后其对程序的整体执行性能影响甚小。因此在特殊时期可以用于生产环境调试使用。

最开始我觉得也许应该为Silly增加一个类似dtrace的调试器。这个调试器只提供一个probe接口,probe有两个参数,参数1是代码位置(文件名与行号),参数2是一个探针函数。当调用probe注册一个探针之后,代码执行到指定行时,就会执行调用probe时注册的探针函数。这样当线上出问题时,就可以像dtrace一样编写一段代码注入到程序中,将我们所关心的信息全部dump出来,而不会影响程序的正常执行。

但是,最近重新仔细思考发现,dtrace之所以可以如此高效,是因为他可以有各种加速手段。比如在增加探针时,可以通过调试信息快速定位到要增加的探针在CPU指令的哪个位置,还可以通过int 3中断被动触发探针函数等(这些只是大概的猜测,具体实现也许不同,但是至少可以证明的是,他可以非常高效的确定探针函数是否应该被执行)。而在lua中,即使仅仅确定什么时间探针函数需要被执行,也至少需要在全局hook事件”call”,在每次触发”call”事件时,遍历检测是否有探针触发。这会极大的拖慢程序的整体性能。因此即使实现了探针机制也不适合在生产环境做调试使用。

既然不可以在生产环境使用,那么做成类dtrace的方式也就没有必要了。如果是在开发期间使用,还是Gdb那种阻塞交互式调试最方便易用。

这不是第一次实现lua调试器了,两年前我就实现了一个非常简易并且低效的阻塞式调试器

当时我们的客户端代码采用lua编写,偶尔会出现一些偶发性bug,并且出错的地方总是一些没有提前预料到的地方,因此没有任何log。而当我们在出错的地方加上详细的log再重启客户端后,问题又不能被重现了。

这个调试器就是这种情况下产生的,他的作用仅仅是当出现偶发性bug时,能够在不重启客户端的情况下,打印出我们想要的上下文。因此在实现时一切从简,只有s(单步步入)、c(继续运行)、 b(设置断点)和 d(删除断点功能)的功能,并且没有考虑整个调试器的效率。


这次实现,希望除了要具备上一个调试器所有功能以外,还要支持gdb中命令n(单步步过)的功能。此外,它还应该是高效的。

在Silly中,所有的代码都是被包在某一个coroutine中被执行的,整个程序运行期间,可能会有数十或上百个coroutine并发执行。因此在调试某一个coroutine中运行的代码时,应该尽可能的保证其他coroutine应该可以不受调试器的干扰而正常执行。

这样就不能使用之前调试器中的方式(直接阻塞等待命令输入)来实现阻塞式调试器。因为那样会塞住整个Silly进程,所有的coroutine都会被卡住。因此,整个lua调试器的命令输入均来源于socket, 这样可以充分利用Silly自身的高并发能力而减少阻塞。

我把整个调试器实现成了一个调试状态机,共分为三个状态,分别是:checkcall, checkline、checkbreak。

程序运行时,整个调试器处于checkcall状态。在checkcall状态,调试器会检测所有的coroutine的”call”事件。只检测“call”事件可以最大程度保证程序的运行效率,而之所以会检测所有的coroutine,是因为这时还不知道被断点的代码将会在哪个coroutine上被执行。

每次触发”call”事件后,都会检测此函数中是否被设置断点。如果被设置断点,则进入checkline状态。

进入checkline后,将程序中所有的coroutine的事件检测取消,只保留当前coroutine的”call/return/line”事件,并且此后,所有针对事件检测范围的修改均只影响此coroutine。

在每个line事件被触发后,都要检测此行代码是否被设置断点,如果有则进入checkbreak状态。

需要说明的这里有一个可能存在的优化,比如下面代码。

function foo(x)
...
end

function bar()
local x = 3
...
foo(x)
local y = 10
...
end

假设在checkcall状态下触发”call”事件的是bar函数,并且有断点设置在bar函数内。这时调试状态机会进入checkline状态,如果foo函数中没有断点的存在,理论上我们只需要检测bar函数中所有行是否触发断点即可,也就是在执行foo函数时,不必触发”line”事件。这也是在checkline状态,我们需要检测”call”和”return”事件的原因。

checkline状态中,如果触发了断点,则挂起当前coroutine并进入checkbreak状态。

checkbreak状态主要处理用户命令输入比如b(设置断点)、d(删除断点)、s(单步步入),n(单步步过)、c(继续运行)等命令。

b/d/c命令都没什么好说的,无非就是向断点列表中增加删除断点信息,及将因为触发断点而被挂起的coroutine唤醒。

命令s的实现是参照Intel x86 CPU架构中的TF标志的思路,即如果单步标志位被置起,则每执行一行都会有触发断点的效果(当前coroutine被挂起等待,用户下一次命令输入)。

命令n在实现时,其实费了颇多周折。如果这一行的代码是调用一个函数,命令s会直接进入到这个被调用的函数的上下文并暂停执行并等待用户输入命令。而命令n则是直到这个被调用的函数返回才会暂停执行。

最开始是通过设置临时断点的方式来实现的,每执行一行,就为下一行设置一个临时断点,后来发现当函数执行到最后一行时,下一行的临时断点就失效了。

经过多次分析总结之后,发现命令n和s惟一的差别仅在于函数调用这里,其余情况下,n与s的作用一模一样。

有了这个关系,问题就简单多了。引入一个变量calllevel代表调用层数,每当call事件触发时,calllevel加1,每当return事件触发时,calllevel则减1。这样calllevel为0时,命令n就可以和命令s的处理方式相同。

这里同样有优化的空间,在“call”事件响应中,如果calllevel大于1,说明我只关心”return”事件,就可以把“line”事件的检测取消。

虽然我前面说要做一个高效的调试器,然而这个版本其实还是有很多可以优化的空间,比如可以重新设置断点列表的数据结构,以使在checkcall状态时可以尽快检测当前函数中是否有断点等。不过,至少这个版本,在使用lua debug hook上,我已经做到了尽可能的高效。

客户端缓存落地方案

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

HTTP服务器的特点

最近一个月在学习关系性数据库mysql, 顺便看了一下http服务器的编写。写了这么久的游戏服务器,数据库也一直使用nosql。因此在初次尝试使用mysql编写http服务器程序时,产生了强烈的反差。

在使用APP的验证过程中,经常会遇到短信验证码问题。

下面就以‘如何实现短信验证码服务’来对比一下http服务器和游戏服务器(mysql和nosql)解决此类问题的不同之处。主要涉及数据结构定义、优化、及逻辑代码的更新问题。

先来明确一下‘业务流程’,最简单的‘短信验证码服务’至少要提供3个操作:

1. APP向‘短信验证码服务’发送请求获取验证码
2. 其他服务向‘短信验证码服务’发送请求校验验证码是否正确(这里的‘其他服务和‘短信验证码服务’有可能是同一个服务,这里只是假定,‘短信验证码服务’被单独实现为一个微服务)
3. 定期删除超时的短信验证码(这里验证码超时时间为5分钟)

先说执行流程:

http服务器的每次请求都是相互独立的,即每个请求都是先查询当前DB(这里假设使用Mysql)的状态,然后将状态写入内存,然后根据内存中的状态执行逻辑,然后把处理结果写入DB,释放所有资源(这里仅仅是理论上,比如可能连接DB时会采用连接池,那么释放时也仅仅是把链接归还到链接池而已)。而这里要实现的‘短信验证服务’基本上属于纯DB操作,因此下面直接展示sql语句,逻辑代码直接略过。

而游戏服务器则不太一样,一般会把要操作的数据提前加载入内存,当处理请求时,直接根据当前内存的状态,来处理逻辑,最后把结果写入内存,并极据不同的策略更新到DB。也就是说,不管DB定义的数据结构是怎样的,进程内的数据结构才是直接影响请求处理效率的关键。

先来看按‘http服务器’如何实现‘短信验证服务’。

首先定义mysql中的数据结构:

create table verifycode (
	phone bigint unsigned not null primary key,
	code int unsigned not null,
	time timestamp not null
);

为电话号码为‘100000000’生成一个短信验证码:

insert into verifycode (phone,code) 
values (100000000, floor(rand() * 10000)) 
on duplicate key update 
time= current_timestamp(),code=floor(rand() * 10000);

为‘其他服务’提供电话号码为‘100000000’验证码为10005验证功能:

select count(*) from verifycode where phone = 100000000 and code = 10005;

定期删除过期的验证码(此段代码需要开个定时器执行):

delete from verifycode where 
time < DATE_SUB(CURRENT_TIMESTAMP, INTERVAL 5 MINUTE);

再来看看如果按‘游戏服务器’的方式该如何实现(直接在进程内操作, 以C++的方式呈现)。

定义数据结构:

struct verifycode {
        long int phone;
        int code;
        time_t time;
};
std::unordered_map<long int, struct verifycode> verifycode_pool;

为电话号码为‘100000000’生成一个短信验证码:

auto &c = verifycode_pool[++codeidx];
c.code = rand() % 10000;
c.phone = 100000000;
c.time = time(nullptr);

为‘其他服务’提供电话号码为‘100000000’验证码为10005验证功能:

auto iter = verifycode_pool.find(100000000);
return (iter != verifycode_pool.end() && iter->second.code == 10005);

定期删除过期的验证码(此段代码需要开个定时器执行):

time_t now = time(nullptr) - 5 * 60;
for (auto iter = verifycode_pool; iter != verifycode_pool; ) {
        if (iter->second.time < now)
                iter = verifycode_pool.erase(iter);
        else
                ++iter;
}

对比一下mysql版本和C++版本的短信验证码服务。可以发现,C++版本的代码基本上就是mysql版本中sql语句的翻译。

也就是说到目前为止,除了http服务器每一个请求都会重新读取Mysql和写入mysql的设计原则与游戏服务器不同外,设计思路上完全一致。


但是上述实现有几个问题。

1. 定期删除过期验证码,需要扫描整张表,时间复杂度为O(N),在有大量验证码的情况下,一次清理就会卡整个进程或整张表,导致”Stop The World”,而mysql在不使用索引的情况下,扫描整张表会更慢。
2. sql语句使用了now(),rand()之类的函数,这将导致mysql查询缓存失效(mysql版’短信验证码服务’特有问题,这个可以通过在应用程序中生成常量值来替换sql语句中的now/rand函数,下面优化不再列出)

为了解决删除过期验证码过慢的问题。

‘http服务器’的优化版本需要做出如下修改,为time字段添加索引:

create table verifycode (
	phone bigint unsigned not null primary key,
	code int unsigned not null,
	time int not null,
        index(time)
);

而C++版本则需要重新设计数据结构, 并实现相应的算法。

采用Time Wheel的方式,将过期的Key直接为300组,超时直接删除整组。

time_t lastupdate = now();
std::unordered_map<long int, int> verifycode;
std::unordered_set verifyexpire[5 * 60];

为电话号码为‘100000000’生成一个短信验证码:

int idx = now() / (5 * 60);
verifycode[100000000] = rand() % 10000;
verifyexpire[idx] = 100000000

为‘其他服务’提供电话号码为‘100000000’验证码为10005验证功能:

auto iter = verifycode.find(100000000);
return (iter != verifycode.end() && iter->second == 10005);

定期删除过期的验证码(此段代码需要开个定时器执行):

time_t now = time(nullptr);
while (lastupdate <= now) {
        int idx = lastupdate % (5 * 60);
        auto &e = verifyexpire[idx];
        for (auto phone:e)
                verifycode.erase(phone);
        e.clear();
        lastupdate++;
}
lastupdate = now;

从优化后的代码,再来对比一下两者的优缺点。

HTTP服务器,特点:
1. 业务逻辑每个请求都需要读取写入数据库,因此相比游戏服务器的方式来讲会请求会慢很多
2. 业务逻辑均采用关系数据库来进行存储(这是并不是绝对的,现在很多服务器已经开始采用nosql来存储了), 一般只能维绕着sql语句和索引进行优化
3. 数据与逻辑分离,可以动态热更新逻辑代码
4. 数据与逻辑分离,当业务请求能力处理不足,而瓶颈不在DB时,可通过增加逻辑服务器来动态扩容,具有极大的可伸缩性
5. 合理的DB集群架构设计,当DB达到瓶颈时,可动态扩容

游戏服务器,特点:
1. 数据均在进程中内存进行操作,可扩展性差。
2. 由于进程中内存残留业务逻辑状态,几乎或很难进行逻辑代码的热更新。
3. 不同的业务模型需要根据情况设计,才可以使集群具有可伸缩性,不像HTTP天然具有可伸缩性。
4. 数据表现力强,可以充分利用编程语言提供的各种表现方式,优化形式多样。
5. 所的请求全部基于内存状态进行处理,处理速度快

ps.mysql中的InnoDB索引采用B+Tree来实现,因此time字段加上索引后,单纯的从算法上与使用TimeWheel实现的C++版本相比,时间复杂度上并不会有显著区别。在更复杂的应用场景,DB和编程语言实现过程中的优化形式可能会相差甚远,但其本质上也是相同的,都是尽可能快的提高访问速度。