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. 在这次纠结的过程中,在一定程度上治愈了我的性能强迫症。

再谈分布式服务架构

在两年前,我曾经设计过一版,高可伸缩服务器架构, 但只进行了理论推演,并没有使用具体业务逻辑验证过。以这两年的经验来看,这个架构不具备可实施性。

在之前的架构中,我只考虑了Gate和其服务之间的交互。没有考虑其他服务之间也会有基于"玩家"的交互,还可能有基于"联盟"等其他对象的交互。

按这套模型继续演化下去,为了解决"任意两服务"之间的交互问题,势必需要所有服务都有一份相同的Agent对象。这样一来,整个架构的复杂性就大大提升了。

这两年里,我一直在思考,游戏服务器和WEB服务器最本质的区别是什么?为什么WEB可以很轻松的做伸缩, 而游戏服务器想要做对就很难。

现在,我想我有了答案。

WEB的经典模式其实是"逻辑"服务和"数据"服务分离。

每一次WEB请求都是一次全新的上下文来处理。如果需要延续之前的状态,就从"数据"服务获取之前的状态之后再处理。

而由于"逻辑"没有状态,因此几乎可以无限扩展。

如果事情到这里就完美解决,这个世界就不会有“理想情况”和“现实情况”之分了。

这个世界是平衡的,看似WEB可以轻松获取高可伸缩的能力,但其实高可伸缩的压力全落到了"数据"服务(大部分情况下,数据服务都是由数据库来完成)。

由于可能会有任意多个"逻辑"服务,同时访问和修改同一个数据。为了解决并发问题,数据库需要提供ACID功能。

当数据量和读写并发量上来以后,数据库就需要进行"分片"来提供可伸缩性。然而,数据库分片之后,ACID的功能就大打折扣。分布式情况下ACID的难度要远高于单机ACID, 而且性能也得不到保证。这也是为什么后来会有很多NOSQL的出现。NOSQL其实更应该叫NO ACID才对。

为了尽可能的不分片,人们总是倾向于先极限压榨"单机""数据"服务的吞吐量,比如设计一主多从机制来改善查询压力(大部分情况下,你看到网页过3秒跳转的,都是利用了这种机制。主机和从机之间的同步一般在1s以内,延迟3秒就是为了能确保在从机上查询出刚刚在主机上写入的数据)。甚至还会在数据库之前再加Redis或Memcached等缓存系统来改善数据库的压力,一般这种缓存数据服务都是NOSQL,其目的就是为了避免ACID和硬盘数据结构所带来的性能影响

因此可以得出一个结论,其实WEB的可伸缩性的限制并不是不存在,而是主要落在"数据"端。

而"数据"端的可伸缩设计,由于各种现实环境的掣肘,即使是到了现在,也依然没有一个银弹方案。可以认为依然是一地鸡毛。

而游戏服务由于性能原因,不太可能像WEB的工作流程那样,每一次对数据的查询和修改都直接穿透到"数据"服务。

大部分常见的做法是,在服务器启动和玩家登陆时,加载必要的数据到"逻辑"进程的内存中。

在接收到请求之后,直接在内存中处理相关数据,然后在合适的时间节点(比如每个请求处理之后,每个定时器事件处理之后,每隔一段时间之后)对脏数据进行落地。

这么比较下来,其实我们的游戏服务,更像是WEB的"数据"服务而不是"逻辑"服务。而从WEB"数据"服务的可伸缩设计历史来看,游戏服务的高可伸缩性也并不是这么容易就可以实现的。


由于我们需要操作的必要数据都已经在内存中了,我们也不可能再借助一主多从或redis/memcached等机制提升性能了。

我们可以提升性能的惟一手段就是伸缩,而伸缩性的惟一的手段就是“分片”(把玩家的数据,全服数据分摊到不同的游戏服务中)。

然而,由于现代分布式数据库领域都还没有特别完美的ACID解决方案。我们的游戏服务之间的交互更不可能提供ACID功能了。

幸运的是,这个世界是平衡的。在我们需要极高性能的同时,对错误的容忍度也相应提高了。

在此之前,先定义两个术语:

"错误" -> 是指产生了不可预料/推理的结果,比如并发过程中,两个线程同时对一个变量进行自增(没有使用原子操作指令)。这种结果是无法预料了,就算出了错了,你也很难推理出正确结果。

"异常" -> 是指产生了一些异常的,但是可推理出正确结果的操作。比如两个线程同时去对一个变量自增, 一个线程在自增前对此变量加锁,在锁定过程中,另一个线程尝试获取锁(非阻塞),如果获取失败,他直接打了一行log即算完成。在这种情况下,即使变量的最终值是不正确的,但是我们借助log是可以还原出这个变量最终值的。

我认为在游戏服务器的分布式领域中,我们只要阻止错误的发生就可以了。至于异常是避免不了的(比如超时)。

基于这个原则和我两年前的架构设计,我重新抽象了整个分布式架构

在这次的设计中,我不再为玩家设计Agent。而是为每一个服务设计Agent.

当一个服务SA会被其它服务调用时,SA需要提供一段Agent代码来暴露他的能力。

依赖SA的服务仅通过这段Agent代码来间接与SA交互。

当然SA可能会被水平扩展多份,但是具体这次请求会被路由到哪一个SA的实例上,则由相应的Agent代码来决定,这样从调用方的角度来看,就像集群中永远只有一个SA实例存在一样。

这次的抽象和上次一样,我并不企图抹平分布式的事实,仅仅只是为了抹平同一个服务会被水平布署多份的事实。


在设计完这个抽象之后,一个自然而然的事实,摆在我面前。

假如,有三个服务A,B,C。每一个服务都有一段对应的Agent代码agent.A, agent.B, agent.C。

因此,在每个服务中,每一份Agent代码都各有一份实例:
A::agent.B,A::agent.C
B::agent.C,B::agent.A,
C::agent.A,C::agent.B

我们需要保证所有的X::agent.A,X::agent.B, X::agent.C实例中的对相应服务的连接是一致的。

讲道理,用配置文件是最简单,也是最可靠的,但是服务间的启动依赖需要自己实现代码来管理。

索性将服务发现一起实现了吧(坏处就是,即然是服务发现,就意味着节点在挂掉和重启之间,是有可能进行地址变更的)。

在WEB领域,一般服务发现典型的做法是,使用etcd或zookeeper。

但是对照一下上面对WEB的概述就会发现,他们的服务发现,一般是用于"逻辑"的服务发现,而不是"数据"的服务发现。

我们的游戏服务与WEB的"数据"服务相似。每一个实例都负责惟一的一份数据,而且我们游戏服务并没并有提供ACID。

试想一下,如果我们用’etcd’来做服务发现会发生什么情况。

我们有一个role_1服务负责处理uid: 1000-2000的玩家数据,由于某种原因,它失联了。我们认为他挂了,又启动了一个实例role_1_new来负责处理uid: 1000-2000的玩家数据。但其实role_1只是与集群中的部分节点失联而已。这时就会出现,role_1和role_1_new同时操作着1000-2000的玩家数据, 这种就属于"错误"而不是"异常"。因为这种操作不可推理,也不可逆。

一旦出现这种情况后,我们的期望应该是"异常"而不是"错误"。


为了解决这个问题,我们必须自己设计“服务发现”机制。

在这次设计中,我将所有实例分为两类,master和worker。

master用于协调所有worker之间的互联,以及提供某种一致性,不参与业务逻辑,全局只有一份。

worker节点则真正用于处理业务逻辑,worker可以再细分为不同种类的服务(比如auth, gate, role),具体由业务逻辑来决定。每个服务可以水平布署多份实例。

为了确保不会出上述两个服务实例处理同一份数据的情况。我将一个实例成功加入集群的过程分为两个阶段:"up", "run"。

在"up’阶段,worker携带服务名向master申请加入集群,master检查此服务是否全部健在(即已经有足够多的处于"up"或"run"状态的服务存在),如果全部健在,则向此worker返回加入失败,worker收到失败后自动退出。如果此服务有空缺(比如需要5个实例,但现在只有4个健康实例。master会定期检查所有worker的心跳状态,如果有worker心跳超时,则将其标记为"down"状态,但是并不通知集群,直到有新的worker替换它才会通知集群,这么做是为了防止过载误判。)则master向所有worker广播当前集群信息(所有的Worker的信息)。worker收到广播之后,如果发现某个实例被替换,则关闭掉相应的rpc连接,并返回成功。在所有worker都返回成功之后,master向申请的worker节点返回成功。

worker在"up"阶段完成之后,会拿到当前分配的slotid和当前服务被计划布署实例的个数capacity。其中slotid即为(1~capacity)中的一个值,一般用于做数据分片。

worker根据slotid和capacity开始从数据库加载所需数据。

加载完成之后,worker再向master申请接管消息处理。此时master会再次将集群信息广播给所有worker, 待所有worker都返回成功之后master返回成功。在worker收到广播消息之后,发现有新的“run”节点,则创建与其对应的rpc连接。

至此,新加入的实例,处于一致状态。

API设计类似如下:

----master实例
local capacity = {
        ['auth'] = 1,
        ['gate'] = 2,
        ['role'] = 2,
    }
    local ok, err = master.start {
        listen = addr,
        capacity = capacity
    }
---worker实例
    worker.up {
        type = "auth",
        listen = listen,
        master = master,
        proto = require "proto.cluster",
        agents = {
            ["gate"] = gate,
        }
    }
    worker.run(MSG)

其中在worker.up时需要提供关心的服务列表,提供其相应的agent对象。每个服务在新建立rpc连接时,都会回调其对应的agent.join,示例代码如下:

function M.join(conns, count)
    if not gate_count then
        gate_count = count
    else
        assert(gate_count == count)
    end
    for i = 1, count do
        local rpc = conns[i]
        if rpc then
            gate_rpc[i] = rpc
        end
    end
end

BTW, 这种组网机制还可以提供一些时序保证(就是上面提到的一致性),如果在worker.up或worker.run返回之后,Agent对象中还没有建立相应的rpc连接,那么这个Agent对象所对应的服务一定在此之后才能成功加入集群。

游戏上线一个月后的反思

大约在1个月前,游戏终于上线了,在这一个月以来,服务器竟然crash了5+次,还有几次严重Bug.

除了觉得测试力度不够之外,我也在想到底有那些环节是我能做而没做好的。

仔细思考下来,出Bug的原因大概有两种典型情况。


写代码时,逻辑思维不严谨,并且函数之间耦合性过强,导致随便一个很平常的改动,都会产生新的Bug, 甚至是crash. 比如我经常写出类似下面这种函数之间耦合性过强代码。

struct foo {
    bool isfinish;
    time_t rsttime;
    //...
};
static viod try_reset(struct foo *f) {
    if (f->rsttime < time(NULL)) {
        //reset foo fields
    }
}
static int bar(struct foo *f) {
    if (f->isfinish)
        return -1;
    try_reset(f);
    //....do more things
}

这上面这个代码里,bar和try_reset耦合性实在是太强了,强到甚至我调换一下try_reset的调用顺序,都会导致整个逻辑出错。这次出的Bug中有好几个都是这种原因,原始逻辑是1年前写的,上线前调整了一下,结果没测到,然后就出问题了。

我仔细回忆了一下,这种强耦合的实现方式,是我最近两年才开始出现的情况。

之所以会出现这种情况,一方面是因为代码估算做多了之后,我对一条两条指令的开销同样很敏感,以至于很多时候把控不住优化的尺度,把设计弄糟。另一方面,我一直坚持设计正确,不需额外检查这一原则。对于上面的代码,本来设计try_reset就是需要调用方保证,一定在foo.finish为false时才调用,所以try_reset没有理由去检查foo.finish字段。

事实上,这并不是我第一次发现这个问题,以前也发生过几次这种问题。每次发生之后,总是自嘲一句“过早的优化是万恶之源”,然后改正了事。

但是连续几次的Bug, 让我头脑清醒了很多,我觉得我有必要重新审视一下这个问题,这应该不仅仅是过早优化的问题。

这段代码相关的需求大概是这样:如果foo在开始之后,需要完成若干操作,如果在开始之后的规定时间段内没有完成,则重置完成进度,重新完成。

为了“削峰填谷”,我并没有为每一个foo设置一个定时器(即使是固定时间轮),只是在每次获取foo结构时,尝试重置foo的进度。

经过重新审视了整个需求发现,其实“try_reset"的前置条件有两个:一个是没有完成,一个是过期时间。

但是在实现过程中, 把条件1放在了调用方,条件2放在了被调用方(也就是try_reset)。这样try_reset执行结果是否正确,竟然需要调用方来保证。以致于所有调用try_reset的函数,都会与try_reset有强耦合。这其实很像是“契约式编程”,但是除非有语言层面支持,不然只是靠人脑来保证契约前置条件是不靠谱的,所以我个人其实也不是很相信“契约式编程”。

将try_reset函数更改如下,其实可以避免很多Bug, 尤其是多年之后需要修改更时如此:

static viod try_reset(struct foo *f) {
    if (f->isfinish == false && f->rsttime < time(NULL)) {
        //reset foo fields
    }
}

那么上面问题的答案来了,是“过早优化么”?不是。“设计正确不需要检查”这个原则正确么,我依然认为是正确的。因为这种类型的Bug,其根本原因是没有设计好。

根据历史的设计经验,我一般都会有意识的将class/module设计为自成闭环。但是在一个class/module内部函数级实现时,几乎没有仔细思考抽象过,都是实现调用方函数的过程中做的,顺手提取出一个子函数供调用方调用,因此大部分情况下,内部函数和调用方之间都有很强的耦合性。当一个模块过大时,这种耦合性会呈几何倍数增加。

现在回过头来看,其实每一个函数在提取时,都值得仔细抽象来和调用方解偶,即使现在它只有一个调用方。据我过去的经验,你最开始抽象出来的函数,往往会随着业务逻辑的衍变,产生多个调用方。


上面的问题,大部分情况下只是会产生逻辑bug, 一般不太会诱发crash.

据最近几次crash的经验来看,主要原因就是在对于个unordered_map在for循环时,删除了其中的一些元素。比如下面代码:

struct st {
    int id;
    int progress;
    //other fields
};
std::unordered_map<int, struct st> DB;

bool bar(struct st &x)
{
    ++x.progress;
    if (x.progress >= MAX_PROCESS) {
        database_delete_by_id(x.id);
        DB.erase(x.id);
        return false;
    }
    //process x
    return true;
}

void foo(std::vector<int> &l)
{
    l.reserve(DB.size())
    for (auto &iter:DB) {
        auto &x = iter.second;
        if (bar(x)) {
            l.emplace_back(x.f1);
        }
    }
}

这种Bug最为讨厌,只要bar函数删除一个元素,就会导致整个迭代器失效,并且不是必崩的。所以这种Bug即使在测试足够的情况下,也很容易逃逸到线上。一般我都会将代码改成如下:

struct st {
    int id;
    int progress;
    //other fields
};
std::unordered_map<int, struct st> DB;

static std::unordered_map<int, struct st>::iterator
check(std::unordered_map<int, struct st>::iterator iter, bool &clear)
{
    auto &x = iter->second;
    if (x.progress >= MAX_PROCESS) {
        database_delete_by_id(x.id);
        clear = true;
        return DB.erase(iter);
    } 
    clear = false;
    return ++iter;
}

static std::unordered_map<int, struct st>::iterator
bar(std::unordered_map<int, struct st>::iterator iter, bool &clear)
{
    bool clear;
    auto &x = iter->second;
    ++x.progress;
    iter = check(iter, clear);
    if (clear == false) {
        //process x
    }
    return iter;
}

void foo(std::vector<int> &l)
{
    bool clear;
    l.reserve(DB.size())
    for (auto iter = DB.begin(); iter != DB.end(); ) {
        bar(iter, clear);
        if (clear == false) {
            l.emplace_back(x.f1);
        }
    }
}

事实上,我个人很不喜欢这种改动,一股bad taste扑面而来。我也很不喜欢unordered_map的这个限制,他会让for循环方和被调用方强耦合在一起。

for循环方必须保证被调用方不会删除unordered_map中的元素才可以调用。即使是第二种写法,也有一种浓浓的耦合味道。

最近重新审视这种代码时,我发现也许我们可以使用“变换式编程(《程序员修炼之道(第二版)》P149)来解决这种问题。

struct st {
    int id;
    int progress;
    //other fields
};

std::unordered_map<int, struct st> DB;

static std::unordered_map<int, struct st>::iterator
check(std::unordered_map<int, struct st>::iterator iter)
{
    auto &x = iter->second;
    if (x.progress >= MAX_PROCESS) {
        database_delete_by_id(x.id);
        return DB.erase(iter);
    } else {
        return ++iter;
    }
}

static void
batch_check()
{
    auto iter = DB.begin();
    while (iter != DB.end()) {
        iter = check(iter);
    }
}

static void
batch_process()
{
    for (auto &iter:DB)
        ++iter->second.progress;
}

void foo(std::vector<int> &l)
{
    bool clear;
    l.reserve(DB.size())
    batch_process();
    batch_check();
    for (auto &iter:DB) {
        l.emplace_back(iter.second.f1);
    }
}

当然这样的改动会增加一点点性能开销,但是我认为这点开销不会成为热点的致因。


在研究上述问题的同时,我也在想,除了良好的抽象之外,我还能为代码的可靠性做些什么。

是的,答案只有一个,为代码写测试代码。

我查了很多关于单元测试理论性的书籍,他们都告诉我,单元测试就是要把被测试的类通过mock类隔离掉,转而只测试这一个类。

但是游戏服务器的业务太复杂了,以至于会有少量循环引用的情况。这样我实现的mock类到最后,除了可以设置假数据之外,几乎和真实的类的功能一模一样了。

而且我看到书上的很多例子,为了可测试性,会对被测试类的接口加以修改。这种侵入式的测试,我很难适应。

而且游戏服务器还有三大不可控因素: 时间,配表,数据库

时间 – 在业务逻辑中,有大量时间相关的逻辑,比如多久回复多少资源, 执行一次操作后有多久的CD。与此相对的是,测试代码需要尽可能快的跑完。

配表 – 在业务逻辑中,有大量逻辑是根据配置来,因此测试代码并不能写死,需要根据配置自适应。而且升级配表之后,很难保证测试代码的正确性。

数据库 – 在业务逻辑中,玩家所有的操作造成的影响都会被存入数据库,因此测试不具有可重复性。

其实我很早以前就想为我写过的业务逻辑编写测试代码,但是基于以上种种原因,尝试了几次均以失败而告终。

由于最近出Bug的概率太高了,我下定决心想去解决游戏服务器的单元测式。

即然书上的理论在我这里行不通,那么我去看一些开源项目对单元测试是如何落地的。

我分别考察了Lua和Redis,发现他们都没有做大量侵入式的单元测试。而是通过他们“特有的方式”来触发相关的代码执行。

比如Lua是通过执行Lua代码来测试Lua虚拟机的各种角落,而Redis则是通过网络协议来测试。

我研究了一下这种方式,发现对游戏服务器同样可行。

其实我们根本不需要mock类。理论上我们可以通过网络协议来操作模块处理指定状态。然后再发协议操作某个特定模块,以验证这个模块的正确性。只要我们为服务器的每一个模块编写一个对应的测试操作模块,就可以大幅度减少测试代码, 大大提高了测试的可行性。

比如account操作模块提供一个account.eusure_create_role_whith_money(name, passwd, money)来保证创建一个名字为name, 密码为passwd, 初始金币为money的账号。

解决了mock类的问题之后,再来看看时间问题。

为了让测试代码尽可能快的运行,我们只有一种选择,那就是调时间。但是频繁去调开发机的时间,会造成一些很麻烦的后果,而且每个单元测试之后,都要把时间调回来。

好在,当时为了减少time()函数造成的系统调用,我封装了一个time.cpp静态类,所有的时间都是通过time::get()函数来获取的。我设计了一条GM指令,可以调整时间偏移量。为了避免测试相关的GM指令逃逸到线上去。我在本地Makefile加入了一个TEST宏,以确保只有test版本才会有这些指令。如此,时间的问题解决了。事实上不仅仅是调时间,我还加了少部分用于控制特殊逻辑的GM开关,以方便测试代码执行(就像Lua同样在源码里留了一些桩点用于测试使用),这些控制逻辑同样是被TEST控制。

配置表的问题,咋一看很麻烦,但是静下心来想想,其实我们的代码依赖的并不是表中的内容。而是表结构。所以在写完测试代码之后,除非功能有变化,不然根本没有理由去更改表的内容。惟一麻烦的是,有时候我们需要通过改表来隔绝其他模块造成的干扰。这种情况下,我们就需要为这引单元测试代码定制一份配置表出来。这也意味着我们的单元测试框架需要有,能为不同单元测试代码指定不同配置的能力。

数据库的问题,其实在我们编写测试操作模块时就已经解决了。我们只需要像Redis一样,在执行每个单元测试之前,把所有测试进程杀死,并且清空数据库即可。每个单元测试自己负责构造自己所需要的数据。由于我们的测试操作模块提供的都是很上层的操作。因此创建数据部分,并不会花费太多代码。

基于以上事实,我实现了一个简易的单元测试框架,并配合valgrindt和GCC的ASan,可以同时进行逻辑测试和内存问题测试。

这个框架有部分项目相关性,而且代码并不算太多,因此并没有开源。

ps. 在编辑测试框架过程中,发现一个有意思的问题。当可执行程序在运行过程中,替换其所依赖的so文件会造成进程崩溃。研究了一下发现,这是因为so文件的代码部分是通过mmap到进程内存空间直接执行的。而mmap的特性就是,对映射内存的修改,直接反映到文件,对文件的修改直接反应到mmap的进程内存地址。而cp命的执行步骤一般是,将文件大小截断为0,然后再写入新文件内容。当文件大小截断为0这个步骤,一下子就把so的代码部分破块了,崩溃也就成了必然。

谈谈随机数的使用

在日常开发中,伪随机函数几乎是必不可少的一个函数。

大部分我们在使用这个函数时,就自然而然拿来用了,很少去思考用的对不对,反正他是随机的,并且也很难去验证(需要各种大量数据统计)。

所以即使概率看起来不太对,也可以安慰自己说,其实是统计的数据量不够。但有时候真的是因为我们误用了随机函数。

在《计算机程序设计艺术》卷2中,详细介绍了线性同余序列的生成算法。
下面就以线性同余算法为例,来分析一下,为什么随机函数还有可能被误用,他原本不就是随机的么?

在游戏开发中,一般都会设计有开宝箱环节,假设每个宝箱每次开出A的概率是30%,开出B的概率是70%,宝箱可以重复开。

我们的代码可能会这么写

    int open_box(box *b)
    {
        int n = rand() % 1000;

        return  n < 300 ? b->a : b->b;
    }

是的,这段代码就是开宝箱存在“垫刀”的根本原因。

我们来看一下线性同余(LCG)伪随机算法的定义:

Nj+1 = (A*Nj + B) (mod M)(j, j+1为下标)

其中A,B,M为线性同余序列生成常数。

LCG周期为M,A,B,M的关系限定如下:

  1. B,M互质
  2. M的所有质因子都能整除A-1
  3. 若M是4的倍数,则A-1 也是
  4. A, B, N0都比M小
  5. A,B是正整数

通俗点来讲就是,线性同余生成的[0,M)个数在统计学意义上,是等概率出现的。也就是说在足够多次随机以后,他们出现的次数是相同的。

咋一看,感觉上面的代码好像没啥问题。因为[0,M)是等概率出现的,因此rand()%1000之后的值,也是等概率出现的。

但是!我们忽略了一个事实,这段代码意味着。所有人的所有宝箱(甚至还有其他系统)共用了一个伪随机序列。

假设rand()%1000的伪随机序列是这样的:

900,1,300, 500, 299, 785, 556 …

我们来模拟一下多个宝箱交替打开的行为:

开宝箱1,rand()%1000返回的是900, 因此开出来的是B

开宝箱2,rand()%1000返回的是1, 因此开出来的是A

开宝箱1,rand()%1000返回的是300, 因此开出来的是B

开宝箱1,rand()%1000返回的是500, 因此开出来的是B

开宝箱2, rand()%1000返回的是299, 因此开出来的是A

如果宝箱1和宝箱2一直在以类似的顺序交替打开。即使开再多次,你也很难拍着胸脯说,宝箱1和宝箱2开出来的A,B概率分布是符合预期的。

毕竟你亲口告诉玩家,每个宝箱都有30%的概率开出来的是A,但是宝箱1却从来开不出A。

事情之所以会演变成这样。根本原因是,除了有一个伪随机序列之外,还有一个真随机事件,即玩家开宝箱的时机选择。

用软件工程的话来说,宝箱1和宝箱2通过一个全局变量(同一个线性同余序列)耦合在一起了,他们不是正交的。因此,开一个宝箱势必会影响另一个,所以它必然是错的。

还有很多类似的情况,比如一个技能的触发概率。我们本来告诉玩家的是每个技能以某种特定的概率触发,但是我们很可能做成了,以某种概率释放了某个技能。

在我们用随机函数之前,一定要先问问自己,所有使用rand()函数的地方其实是共用了同一个伪随机序列,这样真的没问题么?


2021/11/16补充:

经过这一年多来的观察, 除了"垫刀"的问题之外, 我们还习惯使用如1000, 10000之类的数字来代替100%的概率. 这就会产生一个现象, 就是1000或10000很可能和LCG公式中的M是有公约数的, 这会导致LCG的周期缩短, 其影响远大于"垫刀"产生的不良影响。在我们将接近1000或10000的质数作为100%概率的代表时,随机数的分布有明显改善。

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

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

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


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