« October 2016 | Main | December 2016 »

November 23, 2016

如何让 lua 做尽量正确的热更新

很多项目采用 lua 的一大原因是 lua 可以方便的做热更新。

你可以在不中断进程运行的情况下,把修改过的代码塞到进程中,让随后的过程运行新版本的代码。这得益于 lua 的 function 是 first class 对象,换掉代码不过是在让相应的变量指向新的 function 对象而已。

但也正因为 lua 的这种灵活性,想把热更新代码这件事做的通用,且 100% 做对,又几乎是不太可能的。

首先,你很难准确的定义出,什么叫做更新,哪些数据需要保留,哪些需要替换成新版本。光从源代码和运行时的元信息上去分析是远远不够的。

lua 只有一种通用数据结构 table ,这方便了我们做数据更新;但同时也制造了一些模糊性难题。比如,如果在代码中有一些常量配置数据表,写死在源代码中,通常你是希望跟着新版本一起更新的;而有一些表,记录着运行时的状态,你又不希望在代码更新后状态清空。

所以一般做热更新方案的时候,都会人为加一些约束,在遵循约束条件的前提上,尽量让更新符合预期。

比如在 skynet 中就提供了一种简单的热更新方法

最近在给公司的项目做一些技术指导,同时也做一些工具来提高开发效率。对于开发期(而不是生产环境),或许提供一个更灵活的热更新方案更方便一些。我们不太需要结果 100% 正确,但是需要减少一些约束。

在开发期,最好就是改两行代码,能立刻让进程刷新成新版本的代码,并不中断运行。如果更新结果和预期不符,最坏的后果也不过是关掉程序重新来而已。但是如果仅仅是改两行代码,或加几行 log ,则基本不会出错,但开发效率却可以极大的提高。


下面来讨论一下,在约束条件足够少的情况下,如何设计一个尽量完备的热更新方案。

热更新的关键是:找到更新的代码模块和在内存中运行的对应模块,到底有什么差异,以及如何处理这些差异。

如果我们以模块为单位来更新,第一步就是要把要处理的数据约束在一个足够小的范畴,而不能扩大到整个虚拟机。

所以我先实现了一个沙盒,让 require 新模块的过程在沙盒中运行。我们只给沙盒注入有限的几个不会产生副作用的函数,比如 print ,require,pairs 等;只允许在模块初始化流程中调用这些无副作用的函数。那么,当模块初始化好之后,整个模块内部的数据(函数也是数据),都不会溢出沙盒(不会有引用指向沙盒外)。

由于 lua 的数据结构很简单,所以我们可以认为沙盒中放着一张只有 function 和 table 两种复杂数据类型构成的图。这是因为 coroutine.* setmetatable io.* 等这些可能产生其它类型数据的函数都不能在初始化阶段调用,这是一个合理的限制条件。

这个限制条件同样也能规范模块的开发方法。比如若有复杂的初始化流程必须提供一个模块的初始化函数,由外部驱动,而不能直接写在模块的加载流程中,这也回避了更新模块代码时的重复初始化过程。

在制作沙盒时,可以建立一个访问全局变量和其它模块内容的 dummy 方法。一些 lua 常用写法就可以支持,比如:

local debug = require "debug"
local tinsert = table.insert
local getinfo = debug.getinfo

这类常见的写法是可以支持的,只不过这些 local 变量在沙盒中运行时,指向的是一个 dummy 对象;当更新模块成功后,可以后续替换成真正的变量。但是,在模块初始化过程调用它们会失败。

第二步,我们可以分析沙盒中的数据图。为了简化实现,我们要求数据图的初始状态 key 都必须是 string 或 number 等值类型。这应该也算一个合理的要求。虽然 key 是 table 或 function 也能实现,但代码会复杂很多,不值得放宽这个限制。

接下来,沙盒中每个 table 和 function 都可以表达为一个简单值类型序列索引到的东西。

我们可以根据每条路径去对比内存中同样路径上的对象,找到它的老版本。对于 function 变成 table 或 table 变成 function 这种情况,通通认为是有二义性的,可以简单拒绝热更新。我们的原则是,在约束条件下尽量不出错,如果做就做对。

这样,问题就变简单了:找到了对象之间的新老版本对后,就是怎么替换的问题。如果新版本中有对象不存在,那么不用删除老版本,因为如果老版本无人使用,那么就随它去好了;如果新版本对老版本有新增,直接加入新对象。

对于同类对象替换:函数当然是用新版本替换老版本,但是要小心的处理 upvalue ,这个下面展开说;对于 table ,我的建议是直接把新版本的 k/v 插入老版本的 table ,取并集。这种合并 table 的规则最为简单。

upvalue 如何合并呢?

upvalue 其实是 lua 中的一个隐式类型,大致相当于 C++ 的引用类。比如:

local a = {}

function foo()
  return a
end

a 是 foo 的一个 upvalue ,在 lua 中 a 的类型是 table ,但 upvalue 的实际类型却不是。因为你可以在别处修改 a ,foo 返回值也会跟着改变。

lua 提供了两个 api :debug.upvalueid 和 debug.upvaluejoin 来操作 upvalue 。

我建议的规则是,当我们需要把 f1 替换成 f2 时,应该取出 f2 的所有 upvalue ,按名字 join 给 f1 。不过这里存在的问题是, f1 如果新增了 upvalue 该怎么办?。

我们不能简单的保留 f1 新增的 upvalue ,比如:

--老版本
local a,b

function foo()
  return a
end

function foo2()
  return b
end

-- 新版本
local a,b

function foo()
  return a,b
end

function foo2()
  return b
end

这里老版 foo 只有一个 upvalue a ,但新版 foo 有两个 a 和 b 。我们在处理 foo 更新的时候,可以把老版的 a 关联给新版的 foo ;但在老版的 foo 中,却无法找到 b 。

如果我们不理会新增的 b 让其保留在 foo 上,那么接下来就会出现 foo2 的 b 被关联走;结果在新版本中, foo 和 foo2 原本共享的 b 变成了两个。

所以正确的做法是,把一个模块中所有的函数对象一起处理,所有处理过的 upvalue 以upvalueid 为索引记录在一起,这样在推导 upvalue 的归属时,可以保持同一版本中的关联性。

如果推导产生了歧义,例如新版本中两个函数共享一个 upvalue ,而老版中是分离的,那么都认为代码有二义性,拒绝更新。

再考虑这种情况:

local mod = {}

local pool = {}

function mod.foo()
    return function()
        return pool
    end
end

这里,mod.foo() 返回一个函数,引用了 pool 。这点,在初始化 mod 的时候,该函数是不存在的,所以无法被分析到。所以在合并对象,处理 upvalue 的时候,必须将新版 upvalue 的值合并到老版 upvalue 中,再将新版 function 的 upvalue join 到老版的 upvalue ;不可以反过来做。

注意:这里返回的那个匿名函数 function() return pool end ,如果一旦被持有,旧版本是无法被更新成新版本的。


由于我们可以先在沙盒中尽量把有效性检查全部做完,所以不会出现更新了一半的状态出错,让内存中的状态处于中间状态的情况。

最后,我们只需要遍历整个 VM ,把所有引用老版本函数的地方,修改为新版本对应函数。整个工作就完成了。


说起来容易,做起来还是很麻烦的。我花了两天的时间才把实现基本完成。放在 github 上

目前还没有仔细测试,有时间我会再 review 一遍。正如文章前面所说,在我们的应用场合(用于开发期调试),正确性暂时没有太高的要求,所以可以先将就着用用吧。 :) 如果你想在你的项目利用它做更多的事情,欢迎使用,但请留意可能出现的 bug 。欢迎修正 bug 后提交一个 pull request 。


11 月 25 日补:

关于前面提到的限制,如果旧有模块中有函数返回了一个函数,这个返回的函数虽然属于这个模块,但是却是无法更新的。只能做到,新的版本再调用函数生成它时,新的版本被更新,已有的的函数则只能保持原样。

这个限制的根源在于,重新加载的模块新版本,在加载完成后,对应的函数并不存在。因为对于 lua ,function 是 first class 的。过去的运行中,可能已构建了很多这样的函数对象,每个都是不同的(如果 upvalue 不同),而如果更换成新版本的函数,必须通过调用已有的函数才能构建出来,而且每调用一次才能生成一个新对象。

如果想解决这个问题,需要给 lua 增加一种能力:可以根据一个函数的 prototype 来直接构建出 function 对象。

prototype 是 lua 内部的一种数据类型,可以简单理解成一个函数去掉 upvalue 后的部分。当你写:

function foo(a)
  return function()
    return a
  end
end

时,每次对 foo(a) 的调用都会生成一个不同的匿名函数对象,它们引用的 a 都是不同的(每个分别指向不同的 a )。但是这些不同的匿名函数对象拥有相同的 prototype 对象。

如果使用 lua 的内部 c api 可以实现这样一组 api ,根据一个函数的 prototype 来构建新的函数,构建的函数的 upvalue 全部为 nil ,但你可以再使用 debug.upvaluejoin 来连接到正确的 upvalue 上。

#include 
#include 

#include 
#include 
#include 

static int
lclone(lua_State *L) {
    if (!lua_isfunction(L, 1) || lua_iscfunction(L,1))
        return luaL_error(L, "Need lua function");
    const LClosure *c = lua_topointer(L,1);
    int n = luaL_optinteger(L, 2, 0);
    if (n < 0 || n > c->p->sizep)
        return 0;
    luaL_checkstack(L, 1, NULL);
    Proto *p;
    if (n==0) {
        p = c->p;
    } else {
        p = c->p->p[n-1];
    }

    lua_lock(L);
    LClosure *cl = luaF_newLclosure(L, p->sizeupvalues);
    luaF_initupvals(L, cl);
    cl->p = p;
    setclLvalue(L, L->top++, cl);
    lua_unlock(L);

    return 1;
}

static int
lproto(lua_State *L) {
    if (!lua_isfunction(L, 1) || lua_iscfunction(L,1))
        return 0;
    const LClosure *c = lua_topointer(L,1);
    lua_pushlightuserdata(L, c->p);
    lua_pushinteger(L, c->p->sizep);
    return 2;
}

int
luaopen_clonefunc(lua_State *L) {
    luaL_checkversion(L);
    luaL_Reg l[] = {
        { "clone", lclone },
        { "proto", lproto },
        { NULL, NULL },
    };
    luaL_newlib(L, l);
    return 1;
}

以上,clone 这个 api 可以接收两个参数,第一个必须为一个 lua function ,第二个参数为 0 时,复制自身;为 1~n 时,以内部定义好的 prototype 来构建新的函数副本。

proto 可以返回函数的内部prototype 的指针,和 debug.upvalueid() 类似,它可以帮助你判断两个不同的函数是否有相同的 prototype 。

有了这两个新 api 的帮助,我们就可以完善前面的 reload 库了。我将实现放在里 proto 这个分支上。同时希望这组新的 api 可以进入 lua 下个版本的标准中去。


如果只想更替函数 prototype ,如果我们限制新老模块的 prototype 接口必须完全相同,那么利用我上面提供的 api 可以更简单的实现更新。见 proto 分支上的 hardreload.lua 。

November 20, 2016

如何优雅的实现一个 lua 调试器

最近一段时间在帮公司一个项目组的客户端 review 代码。

我们的所有项目,无论渲染底层是用的 ejoy2d 还是 Unity3d ,实际开发的时候都基本是使用 lua 。所以开发人员日常工作基本是在和 Lua 打交道。

虽然我个人挺反感围绕着调试的开发方式,也就是不断的在测试、试错,纠正的循环中奔波。我认为好的程序应该努力在编写的过程中,在头脑中排错;在预感到坏味道时,就赶快重写。而坏味道通常指代码陷入了复杂度太高的境地,无法一眼看出潜在的问题。对付复杂度最好的武器是简化代码,而非调试器。

在真正遇到 bug 时,应该仔细浏览代码,设想各种出错的可能。而不是将错误的代码运行起来,查看运行中的状态变化。

话说回来,看到项目组的同学真的碰到 bug 时,不断的启动 Unity 客户端,把时间浪费在等待那几行 debug log 上,我觉得效率还是很低。必要的调试工具应该能提升一些开发效率的。

lua 官方提供了完善的 debug api 可以查询所有的信息;但并没有一套官方的调试工具。我都不记得是第几次写调试工具了。至少在这个 blog 上就记录了好几次。最近的一次是 3 年前

每次做完送给人用了两天就扔掉了。这次一时兴起,周末又做了一个。当然每次都会有一些不一样的想法。

这次的版本只开了个头,把构想中的基础架构搭好了。那就是,我认为一个优雅的调试器不应该过多的干涉被调试的实体(比方说你想监控被调试的程序内存使用的情况,和 gc 的工作)。

过去的一些版本都是把调试器代码直接嵌入被调试的虚拟机的,调试器本身和被调试的代码并没有明显的界限。调试过程也会在同一个虚拟机中运行。

我这次想玩点不一样的,让调试器运行在一个独立的虚拟机内,它通过一组接口来观察被调试程序。这样,在这个基础上制作的调试器,可以更放心的添加一些花哨的功能了。比如启动一个图形界面、或是提供一个 web server ,调试者可以通过浏览器来监控内部状态,发送调试指令。

当然最简单的用法是非侵入式的输出 log 。不必在被调试代码中硬加上几句 print 输出 log (这是没有调试工具时,大家最常用的调试方法),而可以把 print 查看内部状态的代码写在独立的调试器模块中。我们可以用编程的方式来编写调试过程,而不局限于一个交互式调试工具提供的有限手段。


我这次设计的调试模块,只提供一个概念:探测点。

你可以在被调试代码中设置探测点,探测点并不是断点,而更像一个观测点。在这个点上,调试器并不会停下来等待调试者的指令,而是运行调试器里的一个函数。(这个函数是运行在独立的虚拟机里的,完全不用代码有什么副作用)

你可以在探测点函数中,访问被调试代码在该处的状态,做一些合适的事情。比如把状态输出到 log 文件中,比如根据状态条件来选择做些事情;当然也可以暂停下来,交互式等待调试命令。

探测点可以分为两种,一种是在调试前,硬编码在代码中的,只要运行到那里,就会触发一下探测行为;还有一种是利用 lua 的 Hook 透明添加的。

两种探测点可以混合使用。比如在游戏主循环中预先硬编码进一个探测点,平时不启动调试器,运行到探测点时就自动忽略;当需要的时候,让这个探测点起作用,然后在探测函数中,设置 hook 点,进一步的调试。


初步的代码放在 github 上,这段时间会慢慢完善。不过期待它短期内发展成为一个图形式的漂亮交互调试器可能有点不现实,除非做前端的朋友有兴趣来完善它。(比如增加一个 web server ,直接可以通过浏览器连接到程序里交互调试)


最后说点这个东西的实现中一个有趣的部分:

由于调试器和被调试程序处于两个不同的 VM 中,所以调试器代码并不能直接引用被调试代码环境中的 table 。这里是怎么做到的呢?

我设计了一个 C 结构(封装成 userdata),里面保存了一个无法被直接引用的 lua 对象的引用路径。

比如,从探测点出发,你想获得某个对象的状态,无非只有几个途径。获取某个栈帧的 local 变量、upvalue 、或是从全局表中检索到一个对象等等,如果这个对象是一个 table ,可以进一步的去取 table 里的子域。总之,你总是通过一层层的简洁途径获得最终想观察的变量的。

那么,在调试器中,只需要把这个过程记录下来、而不需要铆定一个特定的对象。这个过程封装成一个 userdata ,它的实际含义和最终对应的对象是一致的。

November 16, 2016

ETC 图素的合并

在制作 2d 游戏时,通常我们需要把大量小图素合并到一整张大贴图上。这可以使用装箱算法 (Bin Packing)完成。当然,很多人很懒,那么就用别人做好的工具,比如 Texture Packer 。

但是在实际开发中, Texture Packer 有几个严重的缺陷 ,我个人还是建议自己来做合图的工具,完善工具链。

缺陷 1 :装箱过程其实并不需要了解图片上的内容,而只需要知道图片的尺寸。所以装箱过程需要的内存量应该只和被装的图素个数相关,和图片大小无关。而 texture packer 并不是这样做的,它把装箱和合成贴图两部工作放在一个黑箱里了,会导致运行时无谓的内存消耗(更不用说它本质上是一个 GUI 程序),不是很适合自动化工具链。

缺陷 2 :如果要求最终合并的图是 pvr 或 etc 压缩贴图,那么还需要最后再对目标图做一次压缩。通常这个压缩过程是比较慢的。

这个缺陷 2 在开发期需要反复打包资源时,对开发效率影响尤其大。但其实如果自己好好设计工具链,是完全可以避免的。

下面就谈谈应该怎么处理 ETC 这类压缩贴图的合并问题。

ETC 这类压缩贴图,内部其实是按 4x4 像素为一个单位区分开的。各个单元之间没有相关性,也只有这样,显卡才能快速处理。所以,完全没有必要在合并图素后,对目标大图做压缩。

正确的做法是,为小图生成对应的压缩数据,好比编译器将 .c 文件 编译成 .o 文件;而装箱合图的过程好比链接器,将压缩后的小图合并到目标贴图上去。

开发过程中,每次修改,主要针对的都是部分小图素;甚至只是添加新的图素,而并没有改动老的。所以这样处理可以极大的减少每次合成大贴图的时间。而装箱程序,只需要输入每个图素的尺寸,输出目标图上的排列就够了,然后用图像处理工具根据装箱布局去组合小的压缩过的图像数据,合成最终的贴图。

我们可以找到一些开源的工具来压缩图素,比如 Ericsson 开源的 etcpack 这个实现的非常糟糕,但用的人很多的工具。这个工具可以把图片文件转换成用 ETC 算法压缩过的数据,生成一个后缀为 .ktx d额压缩图片文件。

我今天写了一个 lua 库,帮助你完成合并多个 .ktx 为一个 .ktx 的过程。

如果真想看一眼的话,那么它的代码在 github 上,它没有人维护,没有使用说明,没有注释,没有测试,也不保证运行结果正确。当然如果你发现有 bug 的话,又乐于修正的话,提个 pull request 还是很欢迎的。

November 03, 2016

Lua 中 Cache 冷数据的落地

今天有同学跟我讨论了一下最近发现的一个 bug ,我觉得挺有意思的。

需求是这样的:

我们的系统中,有一些数据是从外存(数据库)加载进来的,由于性能考虑,并不需要每次修改这些数据就写回外存。希望在数据变冷后,定期落地即可。

典型的场景是一个 cache 模块,cache 的是一些玩家的业务数据,可以通过 uuid 从数据库索引到。一旦业务需要访问玩家数据,cache 模块会从数据库加载对应数据,然后把数据表交出去。当业务再次需要这些数据的时候,cache 模块一旦发现数据存在于 cache 中,就直接交给玩家。

cache 模块还希望在数据很久没有被业务访问时,将这些数据写回数据库。

我们的系统是基于 lua 构建的,数据 cache 模块和修改这些数据的逻辑在同一个 vm 里。难点在于,修改数据的业务逻辑是可以长期持有数据的,cache 模块需要正确感知这点。

先来看看最朴素的实现方法:

cache 模块其实就是一张 uuid : 数据 表。加载数据的时候,检查 cache 中是否存在,如果没有就把数据写到 cache 表中。然后刷新一下数据的时间戳,表示最后访问的时间。

数据落地流程是:从队列中取出一个超时(最后一次访问过于久远的)待落地数据,擦除 cache 对应项,标记 uuid 为锁定状态(阻止加载流程在落地过程重新加载),落地,完成后解锁(并唤醒潜在的加载需求)。

这个方法可以实现在使用数据的过程中,如果有新的访问需求,是不需要从数据库加载,并贡献内存中的同一份数据对象的。

但是这个方法是有漏洞的,因为访问时间久远,并不意味着没有人持有它。而落地前的锁只能阻止加载的冲突,不能阻止持有数据的人在落地过程中改写数据。


为了解决这个问题,我们之前采取了一个改进方案。

使用 lua 的弱表来管理 cache 。在没有人引用数据后,弱表中对应项会消失,此时才是数据落地的最佳时机。因为不会有改写者干扰这个流程,仅仅锁住新的加载会引起的冲突即可。注:如果需要定期落地,只需要定期把数据复制出去落地即可。

直接给数据块加上 __gc 方法,在 gc 流程中做数据落地是不可行的。因为不提倡在 __gc 方法中做过于复杂的工作。所以我们只是在 __gc 中把对象重新放回一张叫 save 的待处理表,即让这个数据表“复活”了。所谓复活,指在之前的 gc mark 流程,它已不被 vm 里除 __gc 方法外的任何地方引用,但是在 sweep 阶段,又被重新塞会 vm 中,并不真的被 sweep 掉。关于这个用法,lua 实现的很好。

之后,落地流程可以慢慢的逐个处理 save 表。这个过程中,如果有业务需要访问数据,那么它可以同时检查 cache 表和 save 表里是否有数据,如果存在于 save 表中,则移回 cache 表。

ps. 在此基础上,还可以做一个优化:在 cache 表的数据不多的时候,不要设置成弱表,防止不用的数据太早被清理。只有表大到一定程度才设置成弱表;或者使用两张表做 cache ,一张弱表一张强表,定期按时间戳把冷数据移去弱表部分。


方案看起来不错。

当数据正被引用时,它总是存在于 cache 表中,不同地方的多次访问会取到同一个引用。

只有当数据没有任何业务引用时,它才会从 cache 表中移走,有另一个落地流程会逐步处理这些不被人引用的数据。这可以防止在落地流程中,有业务对数据修改。

在待落地处理的数据尚未处理时,如果有新的访问需求,那么会抢在落地前拿回来,整个系统中每份数据的引用还是一致的。

锁只需要加在数据落地和数据加载上,防止数据落地的过程中,同时加载数据。


但今天有同学报告了这个方案的 bug 。

问题出在 gc 把未引用的数据从 cache 这张弱表里抹掉的操作,和被抹掉的数据的 __gc 方法将其加回 save 表这两者并不在一个原子操作内。

也就是说系统会处于某种第三状态。一个 uuid 对应的数据并不在 cache 表中,也不在 save 表中,从业务逻辑上看,这组数据从 vm 中消失了。

当一组数据处于第三态时,如果此刻发生了访问请求,那么就会触发加载流程,从数据库加载一个老版本(新版本尚未落地)。

怎么解决呢?

直接的方法是,当一组数据加载时,我们把 uuid 记录在一个独立集合中;只有在它真正被落地/丢弃处理后,才从这个集合抹掉。

这样数据无论处于三种状态中的什么状态,我们都可以阻止已经处于系统中的数据再次从外存加载一个旧版本。

但一旦处于第三态的数据被请求,我们似乎没有什么好的方法把它从第三态拉回来。因为它的的确确从 vm 中(暂时)消失了。能做的只有等。说到等,这和等数据从数据库加载似乎没有本质区别。我们只能在有等待操作期间,不断的调用 gc 的 step ,督促 gc 过程进行下去,直到(也肯定能等到)数据从第三态出来,进入 save 表。(lua 的 gc 默认行为是只有新的内存申请发生,才可能发生下一步的行动)


有没有别的方案?

利用元表给数据访问加一个间接层能从另一个角度解决这个问题。

如果我们给需要 cache 数据表加上一层代理,让代理的 __index__newindex 都指向真正的数据表。那么业务用起来就是完全一样的。

cache 表里放的仅仅是 uuid : 代理对象。

另外,将真正的数据表全部放在一张额外的 all 表中,并不让业务层直接接触这张表。

业务层不再引用某个 uuid 对应的数据时,cache 中消失的其实是代理对象,而不是真正的数据表。真正的数据表依然存在于 all 表中。

落地流程要处理的其实是 all 和 cache 的差集。它可以定期把差集求出来,放入 save 表中去处理。注:这里依旧生成一张 save 表,而不是直接对差集处理,是因为求差集时刻在变化,而我们无法一次将所有的差集里的数据全部落地。


ps. 以上的方案都隐含着另一个问题没有解决:如果业务私自保留了数据表中的部分子表的引用,cache 模块是无法感知的。不过这点比较容易通过约束业务的使用方法来回避。