云风的 BLOG

今天想写写这个话题是因为上周我们一个 MOBA 项目抱怨 skynet 的定时器精度只有 10ms （100Hz），无法满足他们项目 “帧同步” 的需求。他们表示他们的项目需要服务器精确的按 66ms 的周期向客户端推送数据，而 skynet 只能以 60ms 或 70ms 的周期触发事件，这影响了游戏的“手感” 。

讨论下来，我认为，这是对所谓“帧同步” 算法有什么误解。我们客户端运行时不应该依赖服务器的准时推送消息才能得到（手感）正确的结果。虽然在 skynet 下你可以写个服务代替底层提供的 timer 来更准确的按 15Hz 发出心跳消息，但我觉得服务器依赖时钟的精确是游戏设计上的错误，提供 “手感” 完全应该是客户端程序的责任。

这篇 blog 就来写写基于 lockstep 的网络游戏同步方案到底是怎么回事。

首先，我认为把 lockstep 翻译成帧同步，还有与之对应的所谓“状态同步” （我在多次面试中听过这个名词），都是对同步算法的错误理解造成的。把自己所理解的算法牵强附会到已有的在欧美游戏先行者中经过实践的方案上。

btw, 前几天和几位做区块链的同学吃饭，饭局上他们对国内区块链社区中名词混乱也是吐槽不已。说是国内流传颇广的中本聪比特币论文的翻译文本中，把 Transaction 错误翻译为交易，导致了众多不看原文的从业技术人概念混乱，对一些概念做有歧义的解读，结果在国内技术社区内简直无法交流。

我更愿意用 lockstep 的本意来翻译这个名词：锁定步进算法。这个术语是从军事语境引入的，用来表示齐步行军，也就是那种阅兵时的阵列，队伍中的所有人都执行一致的动作步伐；对比到机器，就是让网络上所有的机器都同时执行一样的操作，得到一样的结果。执行 lockstep 同步时，其实和时间是无关的，只和动作一致性有关。相信很多同学都参加过军训，经历过苦难的队列练习。训练时枯燥的摆 pose ，一步一步的队列同步，都是相当缓慢的，直到最后才依据哨声或口号进行有节奏的集体行动。

网络游戏发展到今天，从局域网游戏到互联网游戏，其实已经没有再使用纯粹的 lockstep 同步算法了。各个基于 lockstep 的项目都加入了很多细节改进来解决网络波动延迟等问题。本文不想深入讨论这些改进的细节，只想谈一下最基本的 lockstep 是怎样实现的。搞清楚基本原理后，相信每个人都会有很多改进的想法。

lockstep 最早是用于局域网 RTS 游戏的。局域网环境下不用太考虑网络干扰的因素，只用知道网络传输是需要时间的，无法像单机多人游戏环境中，多方可以直接用共享内存状态的方式实时同步。它的朴素想法是用最简单的方式，保证多台机器表现出完全一致的游戏状态即可。

能直接想到的方法就是把实时游戏还原成回合模式，参加游戏的所有玩家都在进行一个一个的回合操作，在每个回合中，大家相互不干扰的下达指令，然后一起亮出自己做了什么操作，接着依据所有人的操作在游戏中进行沙盘推演。这就好比两个人下棋，不像围棋那样你下一手，我再针对你的这手棋应一手；而更像桌游中常见的减少 downtime 的另一种模式，每个人都同时考虑这个回合我要做什么，把指令暗放在沙盘上，等所有人都操作完毕后，规则再自动推演。

1959 年设计的模拟一战的桌面游戏 Diplomacy 就是典型的这种规则（没玩过的同学强烈推荐试一下，有网络版）；新一点有权利的游戏版图版也差不多。

为什么我们不觉得星际/横扫千军这类基于 lockstep 算法的 RTS 游戏没有回合感呢？诀窍在于这个内在的回合非常短。我在网上找到一片介绍 Supreme Commander ，横扫千军的精神续作，同步算法的文章： Synchronous RTS Engines And A Tale of Desyncs ，它谈到游戏中的实际运算周期，也就是 simulation layer 只有 10 fps ，是远低于用户交互表现层帧率的。

我们可以这样理解，所有玩家都可以在 user layer 下达操作指令，但并不会立刻运行，而是提交到沙盘的指令队列上。在没有服务器时，则将操作以 p2p 方式同步给所有玩家，相当于所有玩家机器上都运行有一个游戏沙盘。沙盘收集完每个回合所有玩家的操作指令后，就向前推演一步。

注意，和桌游一样，不行动也是一种操作，即，每个回合都必须严格收集到所有玩家的操作才能推进。至少在局域网中，收集和同步这些操作指令是非常快的。每个玩家在当前回合中可以做的多个指令被打包认为是一个操作（也就是一个回合并不限制只能操作移动一个单位，和 Diplomacy 一样，你可以操作你拥有的所有单位，只要操作不违反游戏本身的规则），然后转发给所有其它玩家；如果有一个中心服务器，则是发给服务器，再由服务器广播给所有人；这个轮回可以远小于 100ms 。而在一个回合结束时刻，沙盘收集到了所有的操作，按规则推演即可。

在表现层，沙盘（也就是每个玩家的客户端程序），可以做足够平滑的动画拟合，正在行军的单位不会因为 100ms 的间隔而间隙停顿，玩家也就不觉得他们在经历一个个不连续的回合了。

我们可以看到，在这个过程中，时间（100ms）对同步过程没有任何关系。只有收集完所有玩家当前回合的操作指令后，沙盘才会推演。正如我们在桌面玩 Diplomacy 时，一个回合吵上一个小时也是正常的，大家都认可我的行动确定了，才翻牌看看到底这个回合发生了什么。

和桌面游戏一样，无限拖延回合行动时间会极大的影响游戏的流畅度。我们不希望开一局 Diplomacy 玩上 8 个小时还无法结束，所以我们会限制每个玩家的决策时间。如果超过大家商定的时间还无法决策就认为你其实是按兵不动。这个时间在桌面游戏中可能是 10 分钟，在 RTS 中就是 100ms 。如果你在这个 100ms 中还没有操作，就认为你当前回合不想操作了。通常我们会考虑网络延迟，把截止时刻放在执行时刻前一点，保证所有人有收到指令的缓冲时间，让客户端能流畅表现。

如果去掉这个回合时间限制，我们来看 RTS ，如果一局游戏整个时长是 10 分钟，以 10Hz 为回合周期，其实一局游戏就是 6000 个回合。按规则，每个人都必须提交 6000 个操作。所以理论上，你以什么频率去提交这 6000 个操作都无所谓，只要每个操作都是合法的即可。如果沙盘推演的时候可以合法的忽略掉无法执行的操作（比如你试图指挥一个已经死掉的单位行动），那么在多人游戏中，每个人机器上都循序执行这 6000 个操作，就可以得到完全确定的结果。

抽象的看一局 8 人参加的 10 分钟 RTS ，就是收集到 6000 组，每组 8 人的操作指令，就得到了这局游戏的确定性结果。这个确定性和每个人每个操作的提交时间是无关的。

但现实中，玩家需要从前面的操作对沙盘推演后的中间状态做出判断，才能做出后续的正确决策，提前发出操作指令是没有任何好处的。而沙盘只有收集到当前回合需要的 8 个操作指令才能向后步进（ step ）一下，如果有人延迟提交，那么反应在游戏中就是其他人的客户端会卡住等待。这就是我们打星际网络不好时，弹出一个等待框等待某个网络出问题的玩家遇到的情况。

那么，这和回合制游戏的区别又在哪里呢？区别在于，实时游戏虽然内在被分为若干回合，但是和玩家的人机交互上并没有明确的提交一个回合结束的操作。实现（让玩家感觉平滑）的难点也往往在如何确定玩家当前回合的操作是不是做完了。

在 RTS 中，往往允许一个玩家指挥多个单位，手速快的玩家就可以做到单个回合发布多个操作指令。沙盘的推演是等一个回合结束才开始的；如果玩家操作一个单位就算结束的话，那么对下一个单位的操作的执行势必推迟到下个回合（至少延迟 100ms）。但是如果等满 100ms 才汇总过去 100ms 的操作打包成一个回合的指令也会带来问题：最坏情况下，发出一个操作，要最多在本地等待 100ms 然后发出指令，等待回合结束，那么总的操作延迟最大变为 100+n ms ，n 是网络延迟。

但 RTS 游戏在交互上又和回合制游戏有所不同，它不准取消已发出的指令。对于操作单位比较少的 MOBA 类游戏我们又可以这样设计：如果我们已对自己可操作单位下达完指令，无论回合时间有没有到，都认为自己当前回合的操作已经结束。若是一个单位可以有多个技能可以选择时，只需要在规则上给技能加上公共 CD 时间，即释放一个技能后，在一定时间内不准释放下一个技能；这样就从规则上禁止了同一个回合内释放多个技能。

由于玩家不需要明确的下达 idle 一个回合的指令，通常 idle 这种不操作是用超时机制自动触发的。我们一般把 idle 指令的自动执行时刻点放在上一个回合结束时刻点后延大约半个回合周期即可。这个时间点不必特别精确。假设是 50ms ，那么在收到上个回合的信息，推演出沙盘的下个步骤 50ms 后，如果从最后一个发出的指令到这一刻，这段时间内没有操作，就发出 idle 操作。

这样，下一个操作的执行延迟最长就是 150ms ：因为如果你在 idle 操作发出后立刻做了一个操作，那么必须等 50 ms ，沙盘向前推进一步（你的操作是 idle ），然后再等 100ms ，你这个操作才被确认执行。

针对传统的 lockstep 算法，通常是这样实现的：设定一个逻辑周期，通常是 100ms ，和渲染表现层分开。

玩家在客户端的操作会被延迟确认。我们可以给没有操作设定延迟时长，从 0 到 50ms （一半的回合周期）。当收到回合确认同步信息（即所有玩家当前回合的操作指令）后，找到指令队列中延迟时间最短的那个时间，设置超时时长。超时后，把指令队列作为下个回合的操作指令打包发出。

如果至少有一个 0 操作延迟的动作，那么就会在收到上个回合确认后，立刻发出。如果没有任何操作，那么最多会再等待 50ms 发出一个 idle 操作作为当前回合的操作指令。

这个 10Hz 的逻辑周期，并不是由收到网络信息包驱动的，而是采用客户端内在的时钟稳定按 100ms 的心跳步进。网络正常的情况下，客户端会在逻辑心跳的时刻点之前就收到了所有其它玩家当前回合的操作指令；因为如果玩家在频繁交互，大部分动作都是 0 延迟的，会在上个回合时刻点就发出了；如果玩家没有操作，也会在 50ms 前发出操作；在网络单向延迟 50 ms （ ping 值 100ms）之下，是一定能提前获知下个回合沙盘要如何推演的。

也就是说，若网络条件良好，每当逻辑周期心跳的那一刻，我们已经知道了所有人会做些什么。在逻辑层下，沙盘上所有单位都是离散运动的；我们确定知道在这个时刻，沙盘上的所有单位处于什么状态：在什么位置、什么移动速度、处于什么状态中…… 。对于表现层，只需要插值模拟逻辑确定的时刻点之间，把两个离散状态变为一个连续状态，单位的运动看起来平滑。

当网络条件不好时，我们也可以想一些办法尽可能地让表现层平滑。例如，在下个回合的逻辑时刻点 20ms 之前再检查一次有没有收齐数据，如果没有，就减慢表现层的时间，推迟下个逻辑时刻点。玩家看起来本地的表现变慢了，但是并没有卡住。如果网络状态转好，又可以加快时钟赶上。

如果实在是无法收到回合操作指令，最粗暴且有效的方法是直接弹出一个对话框，让本地游戏暂停等待。当同步正常（也就是收到了那个网络不好的玩家上个回合的操作指令后），再继续。如果玩家掉线或网络状态差到无法正常游戏而被踢下线，那么则可以在规则上让系统接管这个玩家，然后让剩下的玩家继续，之后的回合不再等待这个玩家的操作指令。

从上面的描述我们可以清楚的看到，lockstep 的核心其实是按回合锁定游戏进程，逐步推演。时钟周期对游戏规则其实并不重要，超时机制的存在是客户端用来解决如何确定当前回合要提交的多少操作而设定的；而模拟层的心跳周期则影响了表现层如何把离散状态拟合成连续状态。

那么，基于 lockstep 的同步方案一定要基于每个客户端计算操作，通过这些操作达到完全一致状态么？

并不是。

基于操作和对操作的一致性计算，达到每个客户端有一致的结果；这种实现方法仅仅只是因为早期的 RTS 游戏没有中心服务器，且操作本身的占用带宽比较小而已。

如果我们有一个权威主机，所有客户端把操作发往这个主机，由它来计算，然后把当前回合的计算结果：沙盘上每个单位的状态变化广播给所有客户端，一样可以得到一致的结果。算法还是基于 lockstep 的，仅仅只是传输的数据不同。客户端没有收到下一个 step 的状态前，依然不能推进游戏进程。区别在于，客户端收到了其他人的操作，自己演算这些操作引起的后果；还是信任权威服务器算好的结果。

这两者的区别已经和 lockstep 算法无关了。两种方法，玩家都不能对规则作弊。每个操作时序都是确定的，即每个回合你做了什么似无法抵赖的。基于操作的演算，你无法把一次攻击操作对敌人造成的伤害从 100 改成 1000 造成对手死亡；因为其他玩家会认为你的运算结果和他们的不一致，造成游戏无法推演下去；这种不一致发生时，大家如何知晓？一般的做法是每个人的客户端同时计算出每个回合的所有单位的状态的一个 hash 值，如果发现自己算的和别人的不一致，就表示不一致。如果没有修改客户端的话，这一版是客户端本身的 bug 造成的。对于基于权威服务器的演算，客户端只有表现结果的职责，更无法改变结果。

不过，基于操作一致性演算的方案，前提是要保证这些操作在每台设备上从上一个状态计算到下一个状态必须是完全一致的，这样才不会让玩家玩的时候看到的沙盘状态差之毫厘失之千里。这也必须让每个客户端拥有完整的沙盘信息。如果游戏规则有战争迷雾的话，虽然按规则，玩家不可以看到迷雾中的敌方单位，但是沙盘演算又无法缺失这些信息，所以实质上，迷雾中的敌方单位运动每个客户端都是可知的。玩家想作弊的话，可以轻易的在自己的客户端上打开所有迷雾。

如果采用单个权威服务器运算的方法，这个服务器知道所有玩家可以看到哪些单位不可以看到哪些单位的行为；它在每个回合广播状态时，就可以有选择的只通知那些可知信息，就能解决战争迷雾作弊问题。

这种方式的缺点是，服务器运算负担较大，且对带宽要求更高。不像前者，即使设立一个中心服务器，也仅仅做一些转发操作的工作就够了。

和 lockstep 对应的同步方式是什么呢？我认为核心点在于要不要 lock 。

就是客户端表现的时候，是否必须收集齐所有玩家的回合指令才允许向后推延。多数 MMORPG 就没有那么严格的一致性要求。服务器只需要在游戏沙盘变化后，把新的状态同步给客户端，为了减少带宽要求，这个同步频率也不必严格限制为固定周期。而客户端则不用严格等待服务器的步进，无论服务器有没有新的状态下发，也自行推测（或不推测，保留前一个状态）和模拟游戏沙盘。当服务器下发新状态时，修正客户端的表现即可。

如同本文最前所述，现在已经没有太多网络游戏遵循严格意义的 lockstep 同步来实施了。一般都可能针对网络波动和延迟做一些优化。最终很可能会是一个杂合方案。

例如，你可以做这样一个优化来解决网络不稳定的问题：让权威服务器有权利自行做无操作超时，而不必等待客户端发出超时 idle 指令。

即，如果服务器超过一段时间没有收到某个客户端发过来的指令，就认为它当前回合不操作，并打包整个回合所有玩家指令（或指令计算后的状态结果）广播；如果事后这个客户端的操作晚到，扔掉即可。这样就不会因为有人突然网络断开连接无法发出当前回合的指令，而让所有人都卡住。

但对应的客户端就要做一些处理，不可以认为自己发出的指令一定会被执行，而是以服务器下发的为准。发现自己的指令被取消，就做一些弥补：有些可以自动重发，有些则明确在交互界面上通知玩家。

对于格斗游戏那种，逻辑帧率很高的游戏类别，如何基于 lockstep 做同步？

以我玩的比较多的 DOA 为例，它的内在帧率是 60fps 。这类游戏都有明确的出招帧率表，DOA5LR 甚至在训练模式都明确标出来。

如果按传统的 lockstep ，每个逻辑帧都需要双方确认才能继续，那么在互联网上肯定运行不了。受光速所限，在一定距离外，互联网物理上就无法保证 16ms 的 ping 值。16 ms 只够光信号在 2400 km 的距离上跑一个来回，这个距离在地球表面轻易可以超过。

所以格斗游戏每个招式都有起手时间和恢复时间。比如以 DOA 里霞的 P (拳为例) 这个属于比较快的招式，它的帧数为 9(2)13 ，就是起手有 9 frame ，有 2 frame 的击中判定，然后有 13 frame 的恢复时间无法发出新招。这个 9 frame 在 60fps 下就是 150ms 足够应付一般的网络延迟了。

我们可以这样看，你在 DOA 里所发出的任何技能动作，这个动作是否可以发生，是由前述某个 frame 所决定的。而这个动作在击中判定时是否有击中，同样也是前述某 frame 的确定状态所确定了。

假设我们允许 9 frames 也就是 150ms 的最大延迟，那么本地客户端只需要确定当前帧向过去 9 frame 的对方状态，就能知道现在的呈现 frame 的交互结果。例如本地渲染在第 100 frame ，这个时候，我输入了一个技能，如果确定的逻辑 frame （即对手反馈回来的他的 frame ），只要在 91 frame 之后，我都能知道我当前的输入是否成功。如果可以输入这个招式，我的本地只要马上表现我操作的角色做对应的动作就可以了，这样就能保证手感。而对手，可以根据已确认的过去某帧的状态去猜测现在的状态；多数情况下是准确的，因为实际上格斗游戏你来我往的交互节奏并不高。客户端还可以根据接下来收到的对手的操作，不断地修正画面。也就是在网络对战时，客户端其实同时在计算两个状态，一个根据已经收到的对手的操作，算出一个过去的确定状态，一个是根据过去的状态推演出的当前的状态。

所谓手感，就是让我操作的角色立刻反应出我刚刚的操作，根据游戏规则，我当下能做出的操作是由过去一个时刻敌我状态所能决定的，所以一旦符合规则，那么动作一定可以发出；所以不会有事后发生歧义需要回滚的情况。而对手在我的显示器上的画面呈现，在招式起手阶段是滞后于真实情况的，但会随着时间推移而迅速弥补上。

如果网络状态不好，可能发生的情况就是当前的画面进度超出了逻辑确定帧能确保的范围，那么客户端就可以零界点快到时，开始降低渲染帧率，看起来就是在放慢动作；极端情况下让画面静止卡住等待。

总之，整个游戏的每一帧游戏画面，对于我方控制的角色，状态是一直确定的，敌方是不断跟进模拟的；但对于整个游戏进程来说，每一帧的双方状态都是确定的，只不过这个确定状态并非实时表现在画面上。画面有所超前。

对于格斗游戏来说，一局 3 分钟，60fps ，也就是双方各提供 10800 个操作，只要保证每个操作都是规则下有效的，那么就一定能得到每一帧确定的结果。

为什么服务器的 timer 精度对游戏的表现没有影响？

这是因为，如果是无权威服务器结构，即使有一个中心服务器，它的职责也仅仅是负责转发每个客户端的操作序列，无关时间。收到即转发。

如果是权威服务器结构，那么服务器保证的是在一个较长时间段内执行了固定次数的逻辑帧即可，这些逻辑帧是在什么时刻执行的并不那么重要。因为 lockstep 同步要的是准确的状态序列，客户端利用这个序列呈现每个 step 的画面。流畅度是由客户端时钟保证的，而非由服务器推送的包驱动。影响服务器的包抵达的时刻的因素很多，有服务器内部处理的时刻，也有网络传输因素。甚至，抛开网络不谈，即使是单机游戏，从 CPU 处理数据到液晶屏上显示出来，其精度误差也可能超过 10ms （液晶屏的刷新率为 60 Hz ），保证业务处理时刻的时间准确性在 10ms 以下是没有太大意义的。

保证手感这件事，只有在客户端用一个精确的时钟去控制，服务器尽可能的保证在这个时刻到达前，当前 step 的数据推送到，而客户端精准的在这个时刻处理，并拟合呈现层的画面，才能确保客户端的流畅。

权威服务器若有额外逻辑，比如 MOBA 战场上指挥一些 NPC 单位，这些额外的操作也应该用 frame 来驱动，而非时钟。即，要实现成在第 300 frame 时刷出一个 NPC ，而不能实现成在第 30 秒时刷出一个 NPC 。服务器大致保证一秒步进 10 个 frame 就够了，而不需要精确的保证这些 frame 在准确的时刻发生。对于游戏规则来说，只有每个 frame 发生了什么，而和真实时间是完全解耦的。

客户端只需要把逻辑帧略微向服务器时刻之后 shift 很短一点时间，在网络通畅时，完全能保证在每个逻辑帧抵达之前就收到了服务器下发的信号。即使是上面 60fps 的格斗游戏类别也不例外。

Posted by 云风 at 10:38 AM | Permalink | Comments (37)

我们给游戏引擎设计了一个虚拟文件系统，可以挂接不同的文件系统实现，比如本地文件系统模块，内存文件系统模块，网络文件系统模块。比如前几天谈到的资源仓库，就是一个文件系统模块。

这个虚拟文件系统是用 lua 编写的，这就有了一个小问题：lua 代码本身也是放在虚拟文件系统中的，那么就需要解决自举。这些代码很有可能需要从网络更新（网络文件系统模块），而网络模块也是 lua 编写的，代码同样放在这套文件系统内。

这篇 blog 我想谈谈自举是怎样完成的。

首先我不想做的太复杂。我们不需要特别弹性的不同文件系统模块挂接到虚拟文件系统的不同目录上的功能。所以我写死了一个叫 .firmware 的目录，专门存放用来自举所需的基础代码（的备用版本）。这块代码在启动后可以在网络模块加载完毕后，用新的版本覆盖。

其次，除了非常必要的 C 代码（例如调用 os 的文件访问 api）外，我希望全部用 lua 实现。

但是，所有 lua 代码，包括文件系统的实现都是放在文件系统内的。我们需要初始化 lua 虚拟机，加载必要的代码，然后才能建立起最低可运行的环境。也就是说，建立这个环境时，lua 虚拟机还并不存在。这样就需要解决先有鸡还是先有蛋的问题。

好在我们先封装了 lua 虚拟机模块，简化了使用。我基于它，创建出一个最小可用的虚拟机环境，只用来读取虚拟文件系统支持模块（先不加载网络模块），然后封装成 C API ，藏起 lua vm 这个细节，专供自举阶段使用。当自举完成，就可以销毁这个虚拟机，在正式的环境重新加载相关 Lua 模块了。

大概是这样的：

struct vfs * vfs_init(const char *firmware, const char *repo);
const char * vfs_load(struct vfs *V, const char *path);
void vfs_exit(struct vfs *V);

初始化的时候，传入一个 firmware 的路径，把自举所需的最小 lua 代码放进去。再传入 repo 仓库路径，供 vfs lua 代码可以工作后，作为新版本替代。

也就是说，我先把 bootstrap 的 lua 代码以原生文件的形式，放在 firmware 里，（针对 ios 版，就是打包在 app 中）一开始加载出来使用。用这块代码创建出可以访问 repo 的最小环境（但不包括网络功能）。repo 是我们的资源仓库，里面有上次从网络上同步过来的最新代码。然后，我们从 repo 中再次加载新版本的 vfs 支持代码，之后用最新版本的 vfs 支持代码去访问 repo 仓库中的其它部分。

一旦新版本出了问题，也可以直接把 repo 删干净，回退到最老的 firmware 版本上。

vfs 的 C 实现尽量少嵌入写死的 lua 代码，大约是这样的：

struct vfs {
    struct luavm *L;
    int handle;
};

static int
linitvfs(lua_State *L) {
    luaL_checktype(L,1, LUA_TLIGHTUSERDATA);
    struct vfs ** V = (struct vfs **)lua_touserdata(L, 1);
    *V = lua_newuserdata(L, sizeof(struct vfs));
    return 1;
}

extern int luaopen_winfile(lua_State *L);

static int
lfs(lua_State *L) {
    // todo: use lfs
    return luaopen_winfile(L);
}

static int
cfuncs(lua_State *L) {
    luaL_checkversion(L);
    luaL_Reg l[] = {
        { "initvfs", linitvfs },        
        { "lfs", lfs },
        { NULL, NULL },
    };
    luaL_newlib(L, l);
    return 1;
}

static const char * init_source = "local _, firmware = ... ; loadfile(firmware .. '/bootstrap.lua')(...)";

struct vfs *
vfs_init(const char *firmware, const char *dir) {
    struct luavm *L = luavm_new();
    if (L == NULL)
        return NULL;
    struct vfs *V = NULL;
    const char * err = luavm_init(L, init_source, "ssfp", firmware, dir, cfuncs, &V);
    if (err) {
        fprintf(stderr, "Init error: %s\n", err);
        luavm_close(L);
        return NULL;
    }
    if (V == NULL) {
        luavm_close(L);
        return NULL;
    }

    V->L = L;
    err = luavm_register(L, "return _LOAD", "=vfs.load", &V->handle);
    if (err) {
        // register failed
        fprintf(stderr, "Register error: %s\n", err);
        luavm_close(L);
        return NULL;
    }
    return V;
}

void
vfs_exit(struct vfs *V) {
    if (V) {
        luavm_close(V->L);
    }
}

const char *
vfs_load(struct vfs *V, const char *path) {
    const char * ret = NULL;
    const char * err = luavm_call(V->L, V->handle, "sS", path, &ret);
    if (err) {
        fprintf(stderr, "Load error: %s\n", err);
        return NULL;
    }
    return ret;
}

这里在初始化的时候仅仅是用原生的 loadfile 读入了 bootstrap.lua 这个文件而已。所以可以在不动任何 C 代码的基础上做到业务逻辑的更新。

最后来看看 bootstrap.lua 的实现：

local errlog, firmware, dir, cfuncs, V = ...

cfuncs = cfuncs()

package.preload.lfs = cfuncs.lfs    -- init lfs

local vfs = assert(loadfile(firmware .. "/vfs.lua"))()
local repo = vfs.new(firmware, dir)
local f = repo:open(".firmware/vfs.lua")    -- try load vfs.lua in vfs
if f then
    local vfs_source = f:read "a"
    f:close()
    vfs = assert(load(vfs_source, "@.firmware/vfs.lua"))()
    repo = vfs.new(firmware, dir)
end

local function readfile(f)
    if f then
        local content = f:read "a"
        f:close()
        return content
    end
end

local bootstrap = readfile(repo:open(".firmware/bootstrap.lua"))

if bootstrap then
    local newboot = load(bootstrap, "@.firmware/bootstrap.lua")
    local selfchunk = string.dump(debug.getinfo(1, "f").func, true)

    if string.dump(newboot, true) ~= selfchunk then
        -- reload bootstrap
        newboot(...)
        return
    end
end

function _LOAD(path)
    local f = repo:open(path)
    if f then
        local content = f:read "a"
        f:close()
        return content
    end
end

_VFS = cfuncs.initvfs(V)    -- init V , store in _G

它会去加载 vfs.lua 建立一个最小环境，然后用新加载出来的 vfs 模块，重加载 bootstrap.lua 自身，看是否有更新，最终保证采用的是仓库中最新的代码来加载文件。

Posted by 云风 at 11:04 AM | Permalink | Comments (3)

我打算就我们在开发客户端引擎框架时最近遇到的两个问题写两篇 Blog ，这里先谈第一个问题。

我们的框架技术选型是用 Lua 做开发。和很多 C++ 开发背景（现有大部分的游戏客户端引擎使用 C++ 开发）的人的认知不同，我们并不把 Lua 作为一个嵌入式脚本来看待，而是把它当成一种通用语言来设计整个引擎框架。

其实这更接近 HTML5 流行之后，用 javascript 设计游戏引擎框架：虽然 javascript 的虚拟机本身是用 C++ 开发的，但和游戏引擎相关的部分全部用 javascript 实现，直到涉及渲染的部分，又通过 WebGL 回到 C++ 编写的代码中。这里，我只是把 javascript 换成了 Lua 而已。

选择 Lua 有很大成分是因为我的个人偏好，另一部分原因是 Lua 有优秀的和 C/C++ 代码交互的能力。可以方便地把性能热点模块，在设计上做出良好的抽象后，用 C/C++ 编写高性能的模块，交给 Lua 调用。

但和 Javascript 不同，我们在做原生 App 时，和操作系统打交道的部分还是得用操作系统的语言，C/C++/Objective C/Java 等等。Lua 虚拟机还是要通过一个 C 模块实现嵌入到 App 中去，这个工作得我们自己来完成。

让 Lua VM 置入 App 和操作系统打交道的这部分代码显然是平台相关的，Lua 的 C API 固然简洁，但是还是很庞大的。如果每个平台都直接用 Lua C API 控制虚拟机，这些平台相关的代码还是略显繁杂。我认为，把平台相关代码约束到一个足够小的范围，还需要对 Lua C API 再做一次抽象。

我们面临的需求是：创建一个（或几个）Lua 虚拟机，定期驱动它运行。重点在，定期驱动它运行。这可视为向虚拟机发送消息，虚拟机本质上是消息驱动的（其实 Windows 程序也是）。通常，有一个时钟驱动的行为，或者有一个渲染帧驱动的行为；然后，有外部输入消息，例如触摸屏消息等。

由于整个业务逻辑都是在 Lua 中完成，所以我们并不需要从 Lua VM 中获取什么东西。如果操作系统需要些什么，更多的是传入一个外部库，由 Lua 代码把内部的信息通过库传递出去，而不是外部去获取。裁剪掉后者这个需求，Lua 的 C API 中绝大多数 API 都是不必要的。

我最后设计出来的封装接口只有 5 个 C API ：

struct luavm * luavm_new();
const char * luavm_init(struct luavm *L, const char * source, const char *format, ...);
void luavm_close(struct luavm * L);
const char * luavm_register(struct luavm * L, const char * source, const char *chunkname, int *handle);
const char * luavm_call(struct luavm *L, int handle, const char *format, ...);

new init close 是 VM 的构建销毁 API ，我们可以在 init 时传入初始化脚本，从外部注入 Lua 的扩展模块。注意：通过 Lua 的原生 require 机制，在部分平台（如 ios）上，是无法取得外部的 C 模块的。

我的解决方案是写一个符合 lua package searcher 的函数，在初始化的时候替换掉原生的 C 模块 searcher ：

static int
preload_searcher(lua_State *L) {
    const char * modname = luaL_checkstring(L,1);
    int i;
    for (i=0;preload[i].name != NULL;i++) {
        if (strcmp(modname, preload[i].name) == 0) {
            lua_pushcfunction(L, preload[i].func);
            return 1;
        }
    }
    lua_pushfstring(L, "\n\tno preload C module '%s'", modname);
    return 1;
}

然后我们就可以把所需的 C 模块的 luaopen_xxx 静态链接到程序中，放在 preload 数组里就可以让 Lua VM 顺利 require 到。

这里，只提供了一对 register/call API 让外部可以调用一个 VM 中的方法。

我们可以在 register 时注入一段简单的脚本，返回一个 Lua 函数。框架给它绑定一个数字 id ，之后 call 就可以调用这个 handle 对应的函数了。在引擎中，需要暴露到从原生代码直接调用的函数并不会太多，可能只有 update draw message 等寥寥几个。

所有 Lua 调用都有可能抛出 error ，在接口上，我全部用 const char * 来示意是否有 error ，方便原生代码在使用时处理。

但这只是一个后备方案。我更倾向于提供第二种途径，让 Lua VM 内部也可以拿到这些错误信息，这样可以做的更完备。例如，可以把错误 log 通过网络途径发送走，或做更复杂的过滤等。我的方案是，在 init 的时候，框架构建出一个 table ，传给 init 代码。这代码可以把这个 table 记录下来，例如是放在全局变量中。然后每次 VM 的入口函数在运行前，都可以检查这个 table 中有没有新的内容，那就是最后发生的错误信息，处理它再将 table 清空。框架则在每次有新的错误信息后，追加在这个 table 末尾。

让 C 代码向原生代码传递参数，我才用了 C 传统的 format ... 的可变参数形式。format 串中，n 表示 double ，i 表示 integer ，b 表示 boolean ，s 表示 const char * , p 表示 void * ，f 表示 lua_CFunction 。

另外，我还支持了接收 call 方法从 Lua 中返回一些简单数据类型，用对应的大写字母即可。call 的时候传递指针。比如，向接收一个 int 返回值，就传一个 int * ，这和 scanf 的风格一致。

最后值得一提的时，虽然这个小的 lua vm 封装模块只完成了很微小的工作，但要把事情做对，还是需要谨慎实现的 ，需要考虑调用 lua c api 时可能发生的任何错误。比如很容易被忽略掉的内存不足的 error 。（ lua_pushstring 就是有可能抛出异常的，不能裸调）

从 lua 中返回 const char * 也要警惕，避免把可能 gc 的字符串指针返回。我的解决方案是，在虚拟机启动后，创建一个独立的 coroutine 专门作为和外界交换数据的区域。所有可能返回到外界的字符串，但暂时放在这里。所以直到下次在调用 lua 虚拟机前，都可以认为上次返回的字符串是安全的。

最后，放上我的代码做参考。注意，这段代码是从我们开发中的引擎中抽出来的片段，仅作参考，该代码片段不会（因为 bug ）持续维护。

Posted by 云风 at 03:16 PM | Permalink | Comments (9)

去年底，我为我们的 3d engine 设计了资源仓库的结构。

随后交给开发组的一个同学实现，这半年来，一直在使用。最近做了引擎一个小版本的内部验收，我感觉这块东西还有比较大的改进余地。因为资源文件系统目前和开发期资源在线更新部分现在掺杂在一起，而网络更新部分似乎还有些 bug ，偶尔会卡住。我觉得定位 bug 成本较高，不如把这块重新实现一遍，顺便把新的改进想法加进去。

这段时间，我重新思考了资源仓库应该怎样设计更合理。越细想越觉得和 git 要解决的问题基本一致。我们的引擎的一个重要特性就是，在 PC 上开发，在移动设备上运行调试。我们需要频繁的将资源同步到设备上，这其实和 git 的运作方式是类似的。我们重新实现的该模块在本地文件系统上的数据组织结构最终也和 git 仓库差不太多了。

这次实现，我们去掉了目录和文件处理方式上的差异，一律都变成了以其内容的 hash 值为文件名（key）的数据块。仓库仅仅是一个 key-value 的数据仓库，以内容 hash (选用了 sha1 算法）为文件名放在仓库目录下。为了避免单个目录文件太多（对大多数文件系统不友好），把内容散列到最多 256 个子目录下。

普通文件就是完全没有修改过的文件本身；而目录是自己建立的索引信息。我采用的是文本格式，一行一个文件描述，记录有文件类型（文件 f 或目录 t ）hash 值，文件名。最终一个目录索引文件看起来是这样的：

d 10a34637ad661d98ba3344717656fcc76209c2f8 f0
f da39a3ee5e6b4b0d3255bfef95601890afd80709 f0_1.txt

这表示该目录下有一个子目录 f0 和一个文件 f0_1.txt 。

这样做会使得子目录下任何一个文件的改变，都会改变目录索引本身的 hash 值，进而会影响父目录的 hash 值。也就是说，整个仓库中的任何一点修改，都最终会影响到根目录的索引。

在接口上，我仅提供了从 hash 值 query 数据；修改根目录指针（一个 hash 值）；从文本路径查找最终对象的 hash 值等这么几个。

通过不同的根目录指针，我们可以让不同的历史版本存在于同一个仓库中，并且最大限度地重用版本间相同的数据。对于服务器/ PC 编辑器端，我们仅需要提供一个重建索引的操作方法。我们从根索引递归遍历下去，为每个目录创建出索引文件。

和 git 不同的是，我们可以不强制把本地文件系统（ git 的工作区）的文件复制到仓库中，而是在仓库中建立一个引用文件。引用文件的文件名使用 hash.ref 的命名方式，表示这个 hash 值对应的实际数据并不在仓库中，而是引用的外部文件。其内容就是外部文件的路径、hash 值和时间戳。由于不同的文件可能内容完全相同，因为一个引用文件可以指向不同的路径，我们会在引用信息中用多行指名；这样在一个文件失效后，还可以依次索引到没有变更的文件。

在快速重建仓库索引时，发现有引用文件，就只比较时间戳。时间戳相同就不必重算 hash 值。

程序以 c/s 结构运行时，在移动设备上先建立一个空的镜像仓库，同步 PC 端的资源仓库。运行流程是这样的：

首先在客户端启动的时候，向服务器索取一个根索引的 hash ，在本地镜像上设定根。

客户端请求一个文件路径时，从根开始寻找对应的目录索引文件，逐级查找。如果本地有所需的 hash 对象，就直接使用；否则向服务器请求，直到最后获得目标文件。api 的设计上，open 一个资源路径，要么返回最终的文件，要么返回一个 hash ，表示当前还缺少这个 hash 对象；这样，可以通过网络模块请求这个对象；获得该对象后，无须理会这个对象是什么，简单写入镜像仓库，然后重新前面的过程，再次请求未完成的路径，最终就能打开所需的资源文件。

这个方式的巧妙之处在于，不需要传统的版本号管理的方式，就可以完美处理多版本问题。客户端和服务器同步过程，只有第一步的根 hash 同步是强制的，且仅同步一个 hash 值。如果移动设备上有多个不同的版本（比如在不同的开发人员的机器上切换），在一开始同步完根 hash 后，完全不用再有任何网络传输。这个过程比 git 切换版本还要快，因为我们在移动设备上没有工作区的概念，不需要在切换版本时拷贝文件到工作区。

在最终版本发布时，也可以做简单的打包，避免小文件过多。简单的把仓库文件打包即可。仓库中就是简单的 key-value 结构，处理包文件比本地文件目录更简单。

同时，发布版本的更新要比传统版本号方式要简单的多。

在发布产品中，我们多半不提供开发期这种按需索要缺少的资源的工作方式，而是将当前版本的所有数据都提前下载后。在这种预下载模式下客户端在启动时从服务器索取一个根 hash ，如果和本地的根相同，则说明版本没有更新；否则，将自己的根 hash （代表了一个版本）发送给服务器。

服务器理论上保留有所有历史发布过的版本，所以会找到这个历史版本。这时服务器可以自己对比这两个版本，计算出客户端缺失的对象，然后打包发送给客户端。

当然，服务器可以缓存一些常见的版本（因为大部分玩家都会停留在上个版本），省略这步比较操作，直接让玩家从 CDN 下载打包好的更新包；对于不常见版本，可以计算出一个最接近的更新包（在 CDN 上），然后把更新包中没有的文件单独打包出来。

这个流程其实和 git 的 fetch 操作非常类似，只不过我们可以针对网游的特质，做一点优化罢了。

因为我们的引擎几乎全部是用 lua 实现，包括这里提到的资源仓库的相关模块，所以理论上这块代码本身也可以被这个仓库管理。这样，还涉及一些代码自举和自更新的流程，这一块的细节也有点意思，我打算过两天另外写一篇 blog 介绍。

Posted by 云风 at 09:52 AM | Permalink | Comments (7)