云风的 BLOG

一般游戏会把所需要资源数据打包成一个大文件，游戏运行时可以像访问普通文件一样，访问包内文件。如何打包如何更新资源包，是设计重点。

现在有很多资源包直接使用通用打包（压缩）格式，比如 zip 。也有自行设计的，多半是为了一些特殊需求。比如资源间有引用关系等。如果资源数量过多，通常还会对原始资源文件名做一次 hash 索引，加快包内文件检索效率。像暴雪的 mpq 格式，还有 unity3d 的 asset bundle 格式都是这样的。

一旦资源打包，原始文件名信息就不再需要了。应用程序可以在运行时通过文件名的 hash 值索引到包内文件。（所以第三方的 mpq 解包工具需要提供一份额外的文件名列表）

既然是 hash ，那么就应该在包格式设计中考虑 hash 冲突的解决方案。asset bundle 的设计人这方面经验欠缺，他们在生成 Deterministic 包的时候，遇到 hash 冲突就直接放弃打包 。这显然是不合理的。

对于一般几千个文件的包， 32bit hash 值肯定是够用的，但 hash 冲突绝对不能忽略。

一个简单的方法是加盐做二次 hash 。比如你在打包时发现有两个不同的文件名 A 和 B ，他们的 hash 值相同，比如 hash(A) 和 hash(B) 都是 H 。那么，在文件索引表中，就不应该在 H 名下记录数据，而是记录一个冲突标记，并引用一个 salt 。

然后，无论在打包阶段还是运行阶段，碰到 hash(A) 或 hash(B) 时，先查询到 H ，再重新计算一次 hash(A, salt) 或 hash(B,salt) 。这样就可以得到两个不一样的 hash 值了。

保证 hash(A, salt) 不等于 hash(B, salt) 应该在打包阶段完成，为了得到一致的数据包，salt 不用随机产生，而可以从一个固定串开始递增。反复尝试 salt 直到找到一个合适的串，可以区分 hash 冲突的串。

注意：通常你不应该采取直接把文件名和 salt 串拼接的方式来加盐。因为大部分 hash 算法是基于数据流 hash 的。如果两个串的 hash 值相同，那么在前面或后面连接一个相同的串，同样会冲突。

正确的方法是选择一个直接 seed 的 hash 算法，把 salt 当作 seed ; 或者把 salt 循环 xor 到文件名上也不错。

资源包间如果有引用关系怎么办？

包间引用不可以光靠 hash 值，因为 hash 值不是 guid ，很难保证不同的包内文件 hash 严格唯一。一个简单的方法是把对外引用的资源（文件）名单独保存在资源里，并对文件名做一个 hash 索引。这样资源包内向资源包做引用时，先用一个 hash 值应用到文件名，再间接引用到包的外部。

patch 应该怎么做？

大部分情况下，我们并不需要把 patch 真的合并到原始包中去。只需要把修改过的文件打一个新包即可。我个人建议 patch 包应该保留完整包的所有文件索引。但如果这个 patch 中并不对老文件做修改，就标记一下该文件不在包内即可。

这样，游戏运行时，可以只加载 patch 包，如果 patch 包指明数据不在包内，再打开前一个版本的资源包，它可能依旧是一个 patch 包，也可以是一个完整的资源包。

如果你的游戏需要频繁更新，那么可以定期生成一个完整资源包，并生成从这个完整版本后每个版本到最新版的 patch 包（这个过程可以通过完善你的工具链在自动进行，只要实现正确，生成 patch 的效率应该是很高的）。用户本地版本如果比这个完整资源包还老，就全量下载；如果版本较新，则只需要下载他的版本到最新版的 patch 包即可。

打包工具应该是怎样的？

如果你把打包看成是数据文件的版本维护就清楚了。你需要的是一个类似 git 的工具。

将一个本地目录初始化成资源仓库；

向仓库中添加或删除一个本地文件；

查看当前仓库跟踪了哪些数据文件；

将当前版本打包；

为两个已存在的版本求 diff ，生成 patch ；

利用若干 patch 合成一个完整数据包。

Posted by 云风 at 08:28 PM | Permalink | Comments (6)

无论是客户端还是服务器，把 lua 作为嵌入语言使用的时候，都在某种程度上希望把 lua 脚本做多线程使用。也就是你的业务逻辑很可能有多条业务线索，而你希望把它们跑在同一个 lua vm 里。

lua 的 coroutine 可以很好的模拟出线程。事实上，lua 自己也把 coroutine 对象叫做 thread 类型。

最近我在反思 skynet 的 lua 封装时，想到我们的主线程是不可以调用阻塞 api 的限制。即在主干代码中，不可以直接 yield 。我认为可以换一种更好（而且可能更简洁）的封装形式来绕过这个限制，且能简化许多其它部分的代码。

下面介绍一下我的新想法，它不仅可以用于 skynet 也应该能推广到一切 lua 的嵌入式应用（由你自己来编写 host 代码的应用，比如客户端应用）：

我们可以在第一个主模块加载时，在 skynet 中也就是 require "skynet" 这里，启动一个调度器的 coroutine 。

这个 coroutine 只用来管理一个数组，数组里全部是业务逻辑的线程。

这个调度器所属的 coroutine 对应的 lua_State 指针，应该记录在 lua vm 的注册表中，保证只到整个 vm 关闭前都活着，那么，接下来我们就可以放心的把它保存在 host 程序中了。

这样，在 host 程序中，除了原有的代表 vm 以及主线程的 L 之外，我们还有一个代表调度器 coroutine 的 cL 。

启动主逻辑的地方，在创建出 vm 后，通常是加载一个主程序文本，然后使用 lua_resume 运行主线程。如果主线程正常运行结束，则之后不再利用主线程 L 做任何事情；但若主线程被挂起，则把它加到调度线程管理的线程列表组里，之后当作普通业务线程去调度。

我们可以同时提供 lua 及 C API 来向这个数组添加新线程(coroutine) ，调度器的职责是永远在空闲的时候尝试 resume 新添加的线程，以及在外部 IO 消息抵达时去唤醒挂起的线程。这个调度过程中，原来的主线程和其它被创建出来的线程并无区别。

而调度器本身的算法并不需要太复杂，也完全没有必要用 host API 去实现，lua 来编写就完全胜任了。

有了这样的多线程机制后，我们可能还需要对 lua 原有的 coroutine 库做一点改造。改造后可以用业务层的 coroutine 和利用 lua coroutine 实现的线程库可以协同工作。这个之前我已经写过一篇 blog 了 。

Posted by 云风 at 09:53 PM | Permalink | Comments (5)

最近在尝试重新写 skynet 2.0 时，把过去偶尔用到的一个对象生命期管理的手法归纳成一个固定模式。

先来看看目前的做法：旧文 对象到数字 ID 的映射

其中，对象在获取其引用传入处理函数中处理时，将对象的引用加一，处理完毕再减一。这就是常见的基于引用计数的对象生命期管理。

常规的做法（包括 C++ 的智能指针）是这样的：对象创建时，引用为 1 （或 0）。每次要传给另一个处地方处理，或保留待以后处理时，就将其引用增加；不再使用时，引用递减。当引用减为 0 （或负数）时，把对象引用的资源回收。

由于此时对象不再被任何东西引用，这个回收销毁过程就可视为安全且及时的。不支持 GC 的语言及用这些语言做出来的框架都用这个方式来管理对象。

这个手法的问题在于，对象的销毁时机不可控。尤其在并发环境下，很容易引发问题。问题很多情况是从性能角度考虑的优化造成的。

加减引用本身是个很小的开销，但所有的引用传递都去加减引用的话，再小的开销也会被累积。这就是为什么大多数支持 GC 的语言采用的是标记扫描的 GC 算法，而不是每次在对象引用传递时都加减引用。

大部分情况下，你能清楚的分辨那些情况需要做引用增减，哪些情况下是不必的。在不需要做引用增减的地方去掉智能指针直接用原始指针就是常见的优化。真正需要的地方都发生在模块边界上，模块内部则不需要做这个处理。但是在 C/C++ 中，你却很难严格界定哪些是边界。只要你不在每个地方都严格的做引用增减，错误就很难杜绝。

使用 id 来取代智能指针的意义在于，对于需要长期持有的对象引用，都用 id 从一个全局 hash 表中索引，避免了人为的错误。（相当于强制从索引到真正对象持有的转换）

id 到对象指针的转换可以无效，而每次转换都意味着对象的直接使用者强制做一个额外的检查。传递 id 是不需要做检查的，也没有增减引用的开销。这样，一个对象被多次引用的情况就只出现在对象同时出现在多个处理流程中，这在并发环境下非常常见。这也是引用计数发挥作用的领域。

而把对象放在一个集合中这种场景，就不再放智能指针了。

长话短说，这个流程是这样的：

将同类对象放在一张 hash 表中，用 id 去索引它们。

所有需要持有对象的位置都持有 id 而不是对象本身。

需要真正操作持有对象的地方，从 hash 表中用 id 索引到真正的对象指针，同时将指针加一，避免对象被销毁，使用完毕后，再将对象引用减一。

前一个步骤有可能再 id 索引对象指针时失败，这是因为对象已经被明确销毁导致的。操作者必须考虑这种情况并做出相应处理。

看，这里销毁对象的行为是明确的。设计系统的人总能明确知道，我要销毁这个对象了。 而不是，如果有人还在使用这个对象，我就不要销毁它。在销毁对象时，同时有人正在使用对象的情况不是没有，并发环境下也几乎不能避免。（无法在销毁那一刻通知所有正在操作对象的使用者，操作本身多半也是不可打断的）但这种情况通常都是短暂的，因为长期引用一个对象都一定是用 id 。

了解了现实后，“当对象的引用为零时就销毁它” 这个机制是不是有点怪怪的了？

明明是：我认为这个对象已经不需要了，应该即使销毁，但销毁不应该破坏当下正在使用它的业务流程。

这次，我使用了另一个稍微有些不同的模式。

每个对象除了在全局 hash 表中保留一个引用计数外，还附加了一个销毁标记。这个标记只在要销毁时设置一次，且不可翻转回来。

现在的流程就变成了，想销毁对象时，设置 hash 表中关联的销毁标记。之后，检查引用计数。只有当引用计数为 0 时，再启动销毁流程。

任何人想使用一个对象，都需要通过 hash 表从 id 索引到对象指针，同时增加引用计数，使用完毕后减少引用。

但，一旦销毁标记设置后，所有从 id 索引到对象指针的请求都会失败。也就是不再有人可以增加对象的引用，引用计数只会单调递减。保证对象在可遇见的时间内可被销毁。

另外，对象的创建和销毁都是低频率操作。尤其是销毁时机在资源充裕的环境下并不那么重要。所以，所有的对象创建和销毁都在同一线程中完成，看起来就是一个合理的约束了。 尤其在 actor 模式下， actor 对象的管理天生就应该这么干。

有了单线程创建销毁对象这个约束，好多实现都可以大大简化。

那个维护对象 id 到指针的全局 hash 表就可以用一个简单的读写锁来实现了。索引操作即对 hash 表的查询操作可遇见是最常见的，加读锁即可。创建及销毁对象时的增删元素才需要对 hash 表上写锁。而因为增删元素是在同一线程中完成的，写锁完全不会并发，对系统来说是非常友好的。

对于只有唯一一个写入者的情况，还存在一个小技巧：可以在增删元素前，复制一份 hash 表，在副本上慢慢做处理。只在最后一个步骤才用写锁把新副本交换过来。由于写操作不会并发，实现起来非常容易。

Posted by 云风 at 03:37 PM | Permalink | Comments (12)

接前一篇文 ，谈谈 skynet 消息队列的一些新想法。

之前谈到，每个服务的消息接收队列可以是定长的，且不必太长。因为正常运行中，每个服务都应该尽量消化掉需要处理的消息，否则会预示着某种上层设计的问题。

但是，在接收队列满的时候直接丢掉消息显然是不合理的。那意味着必须有更健全的错误传播机制，让发送失败方可以出错而中断业务。允许发送消息出错可能使上层结构设计更难。

让发送方阻塞在 skynet 中显然也不是个好方案。因为 skynet 的服务是允许阻塞时重入执行另一条新 session 的，这是和 erlang 最大的不同。这可以让单个 lua vm 的性价比更高，可以在要需要的时候，做共享状态，而不必全部业务都通过相对低效的消息通讯来完成；但其负面代价是重入会引发一些隐讳的 bug 。很多已有的 skynet 项目都依赖 send 消息不阻塞这点来保证逻辑正确，不能轻易修改。

我的解决方案是给每个服务再做一组发送队列。最接收方忙的时候，把待发消息放在自己这里的发送队列中。这样就可以由框架来确保消息都能正确的依次发送（这里不保证目的地不同的消息的先后次序，但保证目的地相同的消息次序）。

这两天，我仔细考虑了这个方案。从单一接收队列改为一个接收队列和若干发送队列。实现复杂度一定是增加了，但并没有达到不可接受的程度。这个方案并不难想到，也不难做到，但 3 年前实现 skynet 时我并没有这么做，一定是有些原因吧。

其中一个核心问题是，处理 IO 和 timer 的线程不同于普通的服务，它们是和系统打交道的。也按类似的机制做就不太合理了。它们要做的是尽量匀速的接收外部消息，并马上转发到 skynet 内部，它们是面对几乎所有 skynet 内部服务高频工作的。不应该有复杂的调度机制。

ps. IO 和 timer 线程也不是普通的 skynet 服务。我曾经把 IO 做成一个独立服务，后来又放弃了这个做法而移到核心中去。

一个变通的方法是让两个特殊的定制服务和 IO 及 timer 线程对 1 对 1 对接。对接的通道是无限长的，由于只有一个读取方一个接收方，这个消息队列在实现时也可以有针对性。

另一个问题是，在服务退出时如果处理遗留消息。

我们必须让未处理的请求被妥善回应。在 skynet 1.0 中，这个步骤是在上层完成的。lua 层会在 exit 时遍历所有没有回应的请求，发送一个 error 消息。

而当发送消息不再保证送达时，问题就变得有点棘手。在新方案中，未发出的消息是暂存在自己的发送队列中的，一旦自己都不在，谁来保证这些消息送达呢？

同样的问题还有：当暂发请求真正发出的时候，对方已经退出，需要重新产生一个错误回应。

我的解决方案是：首先在底层就严格区分请求/回应/单向推送/错误传播 这些消息，可以直接在底层做出合理处理；然后让服务的销毁也严格放在唯一一个服务中进行。在销毁过程中，收集待发消息队列，采集这些消息，然后将需要处理的放在自己这里，之后持续发送。

关于服务的创建和销毁部分。我有许多新想法，打算另开一篇 blog 来记录。

总结一下，这篇主要谈消息队列的新设计。在消息队列方面，我计划按需定制三类队列。

第一，多写一读的固定长度并发队列。由于只有一个读者，且队列长度固定不变。所以在出队列的一端是不需要任何锁的。锁只放在进队列的一端。但这里并不需要无锁设计来减少 spin lock 的盲等。因为任何一个写入者碰到队列满或队列有别的写入者正在操作，都可以一致视为队列忙，不必反复重试。它只需要把待发数据放在自己的发送队列即可。

第二，读写全在一起的无并发队列。用来暂存在接收方忙时的待发数据（还会用于服务销毁时收集待办业务）。这个队列可以在 OOM 未发生前无限增长。因为无并发情况，很容易实现正确。每个服务将配备多个这样的队列。这个待发队列不会用得太多，所以默认长度会很短，多个队列也不需要用 hash 表索引，简单一个数组即可。需要用时直接 O(n) 遍历（n 不会太大，因为过载可能的服务并不会太多，多的话系统根本不能正常工作）。

第三，专用于 IO 线程及 timer 线程和 skynet 内部服务对接的一读一写队列（管道）。写入方和读取方分属不同线程。这个队列有可能按需增长。这个可以用一个读写锁来保证并发正确。写锁只发生在写入队列满时，读取方每次读操作都需申请读锁。注意，这里队列满的扩展队列操作同时只有一个操作者，所以不必锁住队列后再做复制扩展队列空间；而可以扩展前先对老队列做一个副本并行处理，再用写锁做一个新老指针交换。

最后，昨天我实在忍不住光在脑子里想，刷了一天的代码（大约 1000 行完全新写的）。

好吧，我食言了，等不到年后了。skynet 2.0 重写计划开始了一天。新代码暂时只能编译通过，还不完整，不能运行。我暂放在一个临时仓库里，等合适的时候再合并到 skynet 主仓库的 2.0 分支上。

有兴趣的同学可以帮忙 review 一下，印证一下这两篇 blog 的想法的具体实现。

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

这个月 skynet 的 1.0 就会 release 最终版了，除了维护这个稳定版本。我考虑可以对一些不太满意的地方尝试做大刀阔斧的改变（当然不放在目前的稳定版本中）。

我对 skynet 解决的核心问题：多服务任务调度以及内部消息传播这块不是很满意，觉得如果换个方式实现可能会好一些。下面先把想法记下来。

目前，每个服务都有一个唯一的消息队列，且在内存足够的前提下，会无限增长。也就是说，向一个服务发消息是没有失败的可能的。多数情况下，单个服务的消息队列不会太长，在生产消费模型中，也不允许太长。太长意味着消费速度远远低于生产速度，情况多半会恶化。在历史上发生过多起事故，都是和服务过载 有关。

虽然 skynet 提供了 mqlen 这种方法供使用者查询当前服务的消息队列长度，以做出应变，但治标不治本。我想做一个大的设计改动来重新考虑这一块。

我们可以把每个服务的消息队列实现成固定长度，且固定长度并不需要太长，大约 256 个 slot 这种级别就足够了。一个固定长度的循环队列实现起来要简单的多，且很容易做成进出队列互不影响。因为出队列只发生在一个服务内，不可能并发，根本不需要考虑竞争；而仅仅只需要考虑进队列的竞争问题。

当队列满，或有人在入队列操作时，都认为队列忙，不需要做锁，直接失败即可。遇到忙的时候发送方可以自行缓存代发数据。而多方同时写入队列时，对 skynet 来说，其实不需要保证先后次序，有时序要求的仅仅是同一发送者对一个特定接受者。在队列不忙时，谁先写都是没问题的；且同一服务下，当有多个待发出队列时，先处理哪一个也不太所谓。

这样就可以把消息进出这块的所有竞争都去掉，实现起来也非常简单。而且可以大大缓解服务过载后的雪崩问题。因为退出一些有未发出消息的服务，那些没有发出的消息也自然被扔掉了。而目前的设计则会将所有消息都堆积在一条消息队列中，这些消息在玩家频繁上下线时会有大量无效信息。

这里提到的新设计比现在复杂的一点是，该什么时候唤醒一个服务。在现有的情况下，只有一个服务获得新消息，且不在热服务队列中，它才会把自己压入热服务队列，待工作线程去处理。而做出以上改变后，一个服务又未发出的消息时，也需要在接收方解除拥塞后唤醒。

我的想法是索性把服务的任务调度也一并改进。采用一个更简单更粗暴的方式来做。

目前其实把服务分成两类的，一类是热服务，就是有消息待处理的；另一类是冷服务，服务活着，但消息队列暂时为空。工作线程只要从热服务队列中依次取出服务调用回调函数即可。

这么设计是考虑到热服务的数量通常远小于总的服务数量，如此能减少工作线程轮询一个服务是否有消息可处理的开销。

是不是可以考虑另一种算法呢？

每个工作线程可以重复一个工作循环。

第一步就是遍历所有的服务，挑选出当前有事情要做（包括有消息要处理，有消息发出被拥塞）的服务，去掉正在被别的工作线程处理的那些（服务忙），把这些服务放在当前工作线程下的一个集合中。

第二步，依次处理自己集合中的服务消息。在处理工作中，如果碰到别的工作线程已经在处理，或消息队列空，或待发队列依然无法处理（接收方拥塞）则立刻将该服务从自己的集合中去掉。

由于移出集合的条件很宽松，而不会加入新的元素，所以只要不断循环第二步，自己所属的集合会越来越小。但为了防止某几个服务霸占工作线程，还可以加一个循环次数上限，相当于让过热的服务有个冷却的机会。

当第二步的集合为空，或是达到了循环上限。那么结束这个工作循环，回到第一步继续。

以上是一些初步的想法，晾到年后再动手实现。

Posted by 云风 at 07:40 PM | Permalink | Comments (6)