2015.10 利用文件摘要简化游戏资源的引用管理

由于微信会对外部页面重新排版，在微信内置浏览器中，本文会出现下面的异常：

文中的链接无法正常访问
文中的代码段落多出了许多 html tag，变得不可读

请选择右上角菜单“在浏览器中打开”即可正常阅读。(本文的永久链接)

(此图引自 Understanding Go Dependency Management)

资源的引用管理是个有趣的话题，最近我在代码里实践了一种做法，可以在某些方面简化资源的管理，完成之后简单记录在这里。这篇文章先介绍传统的各种方式，然后简单说明一下，这个实践在传统方式的基础上做了哪些改善，解决了什么问题。

引子

游戏开发中的资源管理，通常是指针对游戏中的各类资源数据 (模型，贴图，脚本，数据表等等)，通过合理安排布局来提高资源访问的效率，进而改善游戏体验的过程。在布局方面的一些实践，譬如“如何区分对待不同的资源类型，如何做到更新友好”等等，这里就不详细讨论了。今天主要谈一下在大量资源已合理布局的情况下，如何有效地处置它们相互之间巨量的依赖和引用关系的问题。

简单地说，如果 A 引用了 B，那么应该如何简洁有效地表达这种引用呢？

有经验的开发者知道，这个问题并不像看上去这么简单。随着资源量的剧增，以及牵扯到的工作流程的细碎化，如果处置不善，资源引用问题会成为影响整个架构的根本性问题。

传统实践

方式 I - 基于偏移 (指针) 的引用

文件偏移 (file-offset) 应该是最基本最原始的引用方式了。在一个运行着的 C/C++ 程序中，通常我们通过在对象 A 中存储指针来引用对象 B。如果在序列化时，把这种指针引用以文件偏移的形式直接写入文件，就是最原始的资源引用管理。

(此图引自 ROOT User’s Guide - 13.4 Pointers and References in Persistency)

这种最原始的依赖管理，细分一下还有两种形式：

每个对象的地址 (&object) 被一并存下来用作该对象的 ID (顺便保证了全局唯一)，将引用者写入文件时，如果出现被引用者的指针，就直接写入其地址。这么做的好处是简单直接，速度快，与运行时地址空间一一对应，有时候甚至非常有利于调试。但缺点和限制是每个对象需要额外的4个字节 (64位就是8个字节)，而且必须保证在序列化的过程中不发生相关内存的释放和重新分配 (因为可能导致同一地址被不同的对象“复用”了)。
每个对象在被写入文件时，使用当时的文件偏移作为该对象的 ID (通过每个偏移在文件中的唯一性来保证全局唯一)，将引用者写入文件时，如果出现被引用者的指针，就写入其文件偏移。这么做省去了指针的存储开销，但由于文件写入是有先后次序的，先写入的对象如果引用了后写入的对象，此时还不知道文件偏移，就只有在第一遍写完所有对象之后，再写第二遍填上引用的空缺(或者是预先在内存中把偏移算好)。

为什么说这种方案很原始呢，因为__一个地址所能携带的信息太少了__。在载入时，我们必须在整个过程中都非常清楚自己在操作什么类型的数据，这样就需要大量额外的代码来在不同的情况下创建不同类型的对象，这是非常繁琐和易错的。究其原因，就是引用的信息量不够，做不到某种程度的自描述。

关于打包的单独讨论

由于这种方案足够的快，在一些游戏引擎的二进制数据文件中有非常普遍的应用。为了保证读取效率，游戏引擎通常会把逻辑上相关的资源打包在一起，避免反复读取零散的文件。由于__在包内的文件仍保持着与文件系统相一致的树状存储结构__，所以“物理包文件 + 虚拟的内部文件结构”，本质上跟典型的OS树状文件系统并无不同。提供这种打包机制的引擎通常会把这一层给抽象掉，大多数情况下，游戏代码仍像访问普通文件一样去访问内部的一个资源。这也就是在说，理想情况下，一个考虑周详的打包机制，应做到保留 OS 文件系统的基本语意，将其自身透明化，不破坏和干扰已有的文件访问方式。

出于简化讨论的目的 (不影响讨论的内容和结果)，我们将只讨论基于传统的 OS 文件系统下的资源相互引用问题，而把“是否应该打包，如何打包”等问题正交地拆分出去，视作另一个维度的考虑。

方式 II - 基于路径的引用

(形如 ‘/foo/bar/miracle.png’)

1
2

    texture = "/foo/bar/miracle.png";

正如标题里的例子那样，按照路径来索引资源，应该是__最自然和直观的引用方式__了。事实上，互联网上的资源和服务，大部分都是通过 URL，以路径方式来提供的。

(此图引自 (SlidePlayer) A+ Guide to Software)

使用路径来索引资源时，如有可能，应当尽量使用相同格式的归一化的平台无关的路径。混用 ‘\\’ 和 ‘/’，使用 “/../” 或 “/./"，等等，都会造成无法直接比较两个引用是否指向同一份资源，而且对同一资源的引用字符串 hash 的结果会不一致。

当需要移动或重命名资源的时候，路径就失效了。这时候，简单的做法是，总是在编辑器提供的资源管理工具中进行 move/rename 的操作，这样可以自动更新所有对该资源的引用。涉及到全库范围的扫描和修改，当资源量大时可能会非常慢。

一个常见的实践是使用所谓的 “Redirector"，当 move/rename 发生时，在原来资源的位置放置一个跳转，指向新的位置，这样所有的相关资源都可以保持对原资源的引用，无需被动更新。在全库范围内，可以定期地运行自动化工具来清理这些跳转，更新引用以直接指向真正的资源。除了把操作的影响局部化以外，这种做法还有一个好处是，如果团队内一个人在 move/rename 时，另一个人创建了对老资源的引用，这个机制可以确保两个人的工作被合并时能够正常工作，而上面的“扫描并更新”的实践则会导致后者的引用失效。

(此图引自 The how and why of 301-302 redirects. )

方式 III - 基于 GUID 的引用

(形如 ‘{77BA2B2B-3EA5-4C49-A3D2-0DA6A03D2B44}’)

1
2

    texture = "{77BA2B2B-3EA5-4C49-A3D2-0DA6A03D2B44}";

使用 GUID 的优点非常明显——由于不依赖在磁盘上的具体位置，不管路径和命名怎么变，只要 GUID 保持不变，就能保证总是索引到对应的资源。

但问题也非常明显：

首先是__可读性问题__，给定任意一个 GUID 必须依赖工具查找才知道对应的资源是什么，对工作效率的影响是很大的。考虑到有时会无意中删除或者忘了提交某个资源，仅凭一个 GUID 没有任何可能的途径来知道缺失了什么，而如果是路径的话我们至少有机会知道是哪个文件的问题。(是的我们可以通过版本管理软件来 blame 可是如果该文件被多人修改过就很被动了)
其次是__额外信息的存储和同步的问题__，由于很多文件格式本身是找不到位置存 GUID 的，这就需要单独建一个同名的 .metadata 文件并与原文件一同管理，这进一步增大了负担，降低了工作效率。更重的实践使用一个中央数据库来把所有资源的 GUID 收拢到一处统一管理，这就需要提供各种工具去处理更新，合并，与版本管理软件协作等问题。

确定性的 GUID 生成

由于工作关系，我曾在一个商业引擎的资源管理相关代码上工作过一段时间。不幸的是，该引擎使用了 GUID 来管理资源的标识和引用。更为不幸的是，该引擎通过“在打包时动态地为资源生成 GUID ”来成功地把打包问题和资源管理问题深深地耦合在了一起。由于在开发过程中，代码和资源会持续地迭代变化，打包的环境总是处于或微小或剧烈的干扰之中，所有这些带来的直接后果就是，打出的资源包内大部分资源的 GUID 几乎总是随着版本在持续地变化，而前后两次打包出的资源也无法兼容和重用。可以想见，对于一个需要联网并时常热更新的游戏来说，这是一个多么不幸的设计。

为了解决这个问题，经过我跟另一位同事的先后努力，这个引擎中，涉及资源管理方面的所有的 GUID 生成都被我们改为了确定性的 (deterministic guid generation)。也就是尽量保证，在任何一个给定的上下文中，生成的 GUID 总是确定一致，并与该上下文基本对应。这个确定性的 GUID 生成实践，本质上是一个通过使用互不干扰的多个随机序列 (std::mt19937 & std::uniform_int_distribution ) ，抓取并嵌入上下文相关的信息，来把 GUID 的生成尽可能局部化的过程。关于此问题的更详细的记录信息可参阅[此文档 (PDF)](https://github.com/mc-gulu/old-bits/blob/master/(2013%29%20Deterministic%20Guid%20Generation.pdf)，这里就不再细说了。

经过这次折腾，俺对 GUID 用于折腾所能产生的巨大能量有了充分而深刻的认识。此事的一个后遗症是，从那以后听到用 GUID 管理引用和依赖的方案，俺就不由自主想呵呵了。

方式 IV - Unique Name 全局唯一命名

(形如 ‘v1_ui_mainframe_miracle_png_hd’)

1
2

    texture = "v1_ui_mainframe_miracle_png_hd";

简单来说，Unique Name 本质上是一个改良版的 (具有一定可读性的) GUID。它兼具了路径引用和 GUID 引用的优点 (可读性好，可随意修改物理路径) 但除了改良的可读性这一点之外，上面所有的 GUID 相关讨论也同样适用于 Unique Name。

当资源量大到一定的体量并仍在持续增长时，(为了避免冲突) Unique Name 将变得越来越臃肿。过长的描述不仅容易造成额外的管理和沟通负担，也会加大运行时的内存开销，实践中在需要时可以 hash 一下。

改进的实践 - 路径 + 摘要 (“Path + Digest”)

(形如 ‘/foo/bar/miracle.png:(digest-string)’)

呼~~终于说到这一次的实践了。

1
2

    texture = "/foo/bar/miracle.png:bd37de66ffdcfd5bf544502a1fae1e99";

还好一句话就能说清楚：在路径后面加一个该资源的内容摘要 (算法随意不影响，目前使用 MD5) 就是我目前采取的方案。

关键点

那么与上面的方案相比，这个方案有何不同呢？

资源重命名或移动时，能够做到自动检测和修改
- 一般情况下，如果仅仅是重命名或移动，根据内容算出来的摘要是不变的，当通过路径找不到资源时，通过比较摘要，就可以提示用户 (或自动重定向到) 重命名或移动后的资源。
- 检测和修改是可惰性的，可延迟至对应的资源打开时再转换，不必立即一次性扫描和更新所有引用
- 重命名和更新可以在 OS 的文件系统内完成，无需在特定工具内
资源更新时自动识别和更新摘要
- 当资源发生变化时 (通常是美术/策划保存了一个新版本) 编辑器会在加载此资源的引用者时为其生成新的摘要。
- 这个也是可惰性的，也就是加载了哪个资源，哪个资源才需要重新生成
不像 GUID 那样需要单独存储，无需额外的 metadata 文件管理负担
- 由于摘要没有产生资源以外的额外信息，随时可以根据资源本身生成，所以无需额外的 metadata 文件
简化全库范围的操作
- 方便检查重复资源 (全库比较摘要即可)
- 全库范围自动修复所有的重命名和移动 (完全应用 1.)
- 全库范围自动重算 (完全应用 2.)

实现逻辑

有同学可能会问：“如果移动，重命名，更新等各种操作混杂在一起，我怎么知道什么时候该自动重定向，什么时候该更新摘要呢？”

嗯，这就是路径 (Path) 和摘要结合 (Digest) 的精髓所在了。我们根据引用去查找资源时，是按照下面伪码的逻辑进行的：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37



Resource* getResource(const std::string& refString)
{
    // 分解为路径和摘要两部分
    std::string path = GetPathPart(refString);
    std::string digest = GetDigestPart(refString);

    // 尝试访问位于此路径的文件
    Resource* res = GetActualFile(path);
    if (res) 
    {
        // 文件存在的情况，检查摘要是否一致
        if (digest == GetActualDigest(path))
        {
            return GetActualFile(path);
        }
        else
        {
            // 文件存在，摘要不一致，则认为是资源更新，重算摘要
            RefreshDigest(path);
        }
    }
    else
    {
        // 文件如果不存在，符合重命名/移动的条件，提示用户资源未找到，是否进行全库范围搜索
        if (在另一个地点找到了摘要符合的资源)
        {
            // 提示用户 (或自动) 更新引用路径
            RefreshPath(newPath);
        }
        else
        {
            // 提示资源缺失 (in-editor) 或使用 err-placeholder (in-runtime)
            ...            
        }        
    }
}

也就是说，路径的判定优先级高于摘要。在认定当下属于何种情况时，路径为主导，摘要为辅助。如果路径吻合但摘要不符，则认为属于资源更新的情况；如果路径失效，则使用摘要去全库匹配。两种行为分别针对两种不同情况的处理，泾渭分明，各司其职。

批量处置

上面的代码是单个资源获取的流程，实际上在编辑器中打开一张地图 (或一个 UI 界面) 时，如果一个资源一个资源地单独汇报和处置，效率就太低了，可以在全部加载完毕后，统一批量地进行一次全库范围的匹配，然后弹出一个汇报和处置的对话框。在这个处置对话框中，重命名/移动/更新都是黄色叹号，而无法识别/找不到资源则是红色叹号，通常如果都是黄色叹号的话直接全部更新就可以了。

代码中的引用

在代码中为了简便，可以__仅使用路径__即可。在运行游戏的过程中，会自动生成一个 digest_cache.txt 文件，每一行是一个资源的完整引用，可以把这个文件提交到版本管理的库中。这样，很容易通过程序手段在资源发生重命名，移动和更新等事件时，检测并更新这个文件，必要时，可提示用户代码内的路径需要更新。

小结

总得来说，这个方案具有以下的特征：

良好的可读性
无需额外的 metadata 文件存储
对资源的重命名/移动无需在编辑器等专有工具内完成，没有潜在的破坏其他资源引用的心理负担
唯一需要保证的是，重命名和移动资源的时候，不要同时更新其内容即可。

好了，关于这个资源引用管理的实践，到这里就讲完了。在资源管理方面，你有什么心得呢？欢迎跟我一起讨论:)

[注]

本文在讲述几种传统方式时，部分内容引自这个页面 (需翻墙)”。
本文的进一步讨论见这里
本文同时发在我的知乎专栏 (链接)
本文已授权 GameRes 的网站转载和11月2日公众号推送。

[2015-11-02] 补：昨晚有两点遗漏，

没有说明“使用新的实践后无需在编辑器内做重命名和移动等操作”

没有说明“无需像 GUID 那样需要额外的单独文件存储和管理”

已补入“改进的实践 - 关键点”一节。

(全文完)