开源应用架构（卷 1）
Mercurial

12.1.1. 集中式版本控制

第一个版本控制系统是源代码控制系统 (SCCS)，首次描述于 1975 年。它主要是一种将增量保存到单个文件的方法，比仅保留副本更有效，但对将这些更改发布给其他人没有帮助。它于 1982 年由修订控制系统 (RCS) 所取代，RCS 是 SCCS 的一个更完善的免费替代方案（并且仍然由 GNU 项目维护）。

在 RCS 之后出现了 CVS，即并发版本控制系统，它于 1986 年首次发布，是一组用于操作 RCS 修订文件组的脚本。CVS 中的重大创新在于允许多个用户同时编辑，合并工作在事后进行（并发编辑）。这也需要编辑冲突的概念。开发者只有在基于存储库中可用的最新版本的情况下才能提交某个文件的最新版本。如果存储库和我的工作目录中存在更改，我必须解决这些更改（编辑更改了相同的行）造成的任何冲突。

CVS 还开创了分支和标签的概念，分支允许开发者并行处理不同的工作，标签则允许为易于引用的某个一致的快照命名。虽然 CVS 增量最初是通过共享文件系统上的存储库进行通信的，但在某些情况下，CVS 也实现了客户端-服务器架构，用于在大型网络（如互联网）上使用。

在 2000 年，三位开发者聚集在一起构建了一个新的 VCS，称为 Subversion，其目的是解决 CVS 中的一些重大缺陷。最重要的是，Subversion 一次处理整个树，这意味着修订中的更改应该是原子性的、一致的、隔离的和持久的。Subversion 工作副本还在工作目录中保留检出修订的原始版本，因此常见的 diff 操作（将本地树与检出的更改集进行比较）是本地的，因此速度很快。

Subversion 中一个有趣的概念是，标签和分支是项目树的一部分。Subversion 项目通常分为三个区域：tags、branches 和 trunk。这种设计已被不熟悉版本控制系统的用户证明非常直观，尽管这种设计固有的灵活性给转换工具带来了许多问题，主要是因为 tags 和 branches 在其他系统中具有更多结构化表示形式。

所有上述系统都被认为是集中的；在它们甚至知道如何交换更改的程度上（从 CVS 开始），它们依赖于其他一些计算机来跟踪存储库的历史记录。分布式版本控制系统会在拥有该存储库工作目录的每台计算机上保留全部或大部分存储库历史记录的副本。

12.1.2. 分布式版本控制

虽然 Subversion 比 CVS 有明显的改进，但仍然存在一些缺陷。首先，在所有集中式系统中，提交更改集和发布更改集实际上是同一件事，因为存储库历史记录集中在一个地方。这意味着在没有网络访问的情况下无法提交更改。其次，集中式系统中的存储库访问始终需要一个或多个网络往返，与分布式系统所需的本地访问相比，速度相对较慢。第三，上面讨论的系统在跟踪合并方面（有些系统已经变得更好了）不是很好。在同时工作的大型团队中，版本控制系统记录哪些更改已包含在某个新的修订版中非常重要，这样就不会丢失任何信息，后续的合并可以利用这些信息。第四，传统 VCS 所需的集中化有时显得人为，并促进了单个集成点。分布式 VCS 的支持者认为，更分布式的系统允许更具机动性的组织，开发者可以根据项目的需要在任何时间点推送和集成更改。

许多新工具已经开发出来以满足这些需求。从我的角度来看（开源世界），2011 年最值得注意的三个工具是 Git、Mercurial 和 Bazaar。Git 和 Mercurial 都始于 2005 年，当时 Linux 内核开发者决定不再使用专有的 BitKeeper 系统。两者都是由 Linux 内核开发者（分别为 Linus Torvalds 和 Matt Mackall）启动的，目的是解决对能够处理数十万个文件（例如，内核）中数十万个更改集的版本控制系统的需求。Matt 和 Linus 也都受到 Monotone VCS 的很大影响。Bazaar 是独立开发的，但它在同一时间获得了广泛的使用，当时 Canonical 采用它来用于所有项目。

构建分布式版本控制系统显然会带来一些挑战，其中许多挑战是任何分布式系统固有的。首先，虽然集中式系统中的源代码控制服务器始终提供历史记录的规范视图，但在分布式 VCS 中没有这样的东西。更改集可以并行提交，这使得不可能在任何给定存储库中按时间顺序排列修订版。

几乎普遍采用的解决方案是使用更改集的有向无环图 (DAG) 而不是线性排序（图 12.1）。也就是说，新提交的更改集是其所基于的修订版的子修订版，并且任何修订版都不能依赖于自身或其后代修订版。在这种方案中，我们有三种特殊类型的修订版：根修订版，没有父级（存储库可以有多个根）；合并修订版，具有多个父级；头修订版，没有子级。每个存储库都从一个空的根修订版开始，并沿着更改集链进行，最终到达一个或多个头。当两个用户独立提交更改并且其中一个人想要拉取另一个人的更改时，他或她必须明确地将另一个人的更改合并到一个新的修订版中，然后他随后将其作为合并修订版提交。

请注意，DAG 模型有助于解决集中式版本控制系统难以解决的一些问题：合并修订版用于记录有关 DAG 新合并分支的信息。结果图也可以有效地表示一组大型并行分支，合并成较小的组，最终合并成一个被认为是规范的特殊分支。

这种方法要求系统跟踪更改集之间的祖先关系；为了方便交换更改集数据，这通常通过让更改集跟踪其父级来完成。为此，更改集显然也需要某种标识符。虽然有些系统使用 UUID 或类似的方案，但 Git 和 Mercurial 都选择使用更改集内容的 SHA1 哈希。这具有额外的有用属性，即更改集 ID 可用于验证更改集内容。事实上，由于父级包含在哈希数据中，因此可以使用其哈希验证任何修订版之前的全部历史记录。作者姓名、提交消息、时间戳和其他更改集元数据与新修订版的实际文件内容一样被哈希，以便也可以验证它们。由于时间戳是在提交时记录的，因此它们在任何给定存储库中也不一定按线性顺序进行。

对于之前只使用过集中式 VCS 的人来说，所有这些可能都很难适应：没有很好的整数来全局命名修订版，只有一个 40 个字符的十六进制字符串。此外，不再有任何全局排序，只有局部排序；唯一的全局“排序”是一个 DAG 而不是一条线。当您习惯于 VCS 在发生此类事情时发出警告时，意外地通过提交到已具有另一个子更改集的父修订版来启动一个新的开发头可能会令人困惑。

幸运的是，有一些工具可以帮助可视化树排序，Mercurial 提供更改集哈希的明确短版本和仅用于本地的线性编号来帮助识别。后者是一个单调递增的整数，表示更改集进入克隆的顺序。由于此顺序在不同的克隆之间可能不同，因此不能依赖它进行非本地操作。

12.2.1. 挑战

在我们深入研究实际的数据结构之前，我想提供一些关于 Mercurial 发展环境的背景信息。Mercurial 的第一个概念可以追溯到 Matt Mackall 于 2005 年 4 月 20 日发送给 Linux 内核邮件列表的一封电子邮件。这发生在决定不再使用 BitKeeper 开发内核后不久。Matt 在他的邮件中概述了一些目标：简单、可扩展和高效。

在 [Mac06] 中，Matt 声称现代 VCS 必须处理包含数百万个文件的树，处理数百万个更改集，并在数十年内跨数千个用户并行创建新修订版的情况下进行扩展。在设定了目标之后，他回顾了限制技术因素

• 速度：CPU
• 容量：磁盘和内存
• 带宽：内存、局域网、磁盘和广域网
• 磁盘寻道速度

磁盘寻道速度和广域网带宽是当今的限制因素，因此应该优化。本文将继续探讨评估此类系统在文件级性能的常见场景或标准。

• 存储压缩：哪种压缩最适合保存磁盘上的文件历史记录？实际上，哪种算法能最大程度地利用 I/O 性能，同时防止 CPU 时间成为瓶颈？
• 检索任意文件修订版：许多版本控制系统会以这样一种方式存储给定修订版，即必须读取大量旧修订版才能重建较新的修订版（使用增量）。我们希望控制这一点，以确保检索旧修订版仍然很快。
• 添加文件修订版：我们定期添加新的修订版。我们不想每次添加新修订版时都重新编写旧修订版，因为当有许多修订版时，这会变得太慢。
• 显示文件历史记录：我们希望能够查看所有修改过特定文件的变更集的历史记录。这也允许我们进行注释（以前在 CVS 中称为 blame，但在一些后来的系统中重命名为 annotate 以消除负面含义）：查看当前文件中每行的源变更集。

本文将继续探讨项目级别的类似场景。此级别的基本操作是签出修订版、提交新修订版和查找工作目录中的差异。特别是后者，对于大型树木（例如 Mozilla 或 NetBeans 项目的树木，它们都使用 Mercurial 进行版本控制）来说可能很慢。

12.2.2. 快速修订版存储：Revlogs

Matt 为 Mercurial 想出的解决方案称为 revlog（修订版日志的缩写）。Revlog 是一种有效存储文件内容修订版（每个修订版与之前的版本相比都有一些更改）的方法。它需要在访问时间（因此优化磁盘寻道）和存储空间方面都高效，并以上一节概述的常见场景为指导。为此，revlog 实际上是磁盘上的两个文件：索引和数据文件。

索引由固定长度的记录组成，其内容在 表 12.1 中详细说明。使用固定长度的记录很好，因为这意味着拥有本地修订版号允许直接（即常数时间）访问修订版：我们只需读取索引文件中的位置（索引长度×修订版），即可找到数据。将索引与数据分离还意味着我们可以快速读取索引数据，而不必遍历所有文件数据来寻找磁盘。

块偏移量和块长度指定数据文件的一部分，需要读取这些部分以获取该修订版的压缩数据。要获取原始数据，我们必须首先读取基修订版，并应用增量直到此修订版。这里的诀窍是决定何时存储新的基修订版。此决定基于增量的累积大小与修订版的未压缩长度的比较（数据使用 zlib 压缩，以便在磁盘上使用更少的空间）。通过这种方式限制增量链的长度，我们确保在给定修订版中重建数据不需要读取和应用大量的增量。

链接修订版用于让依赖的 revlog 指向最高级别的 revlog（我们将在后面详细介绍），父修订版使用本地整数修订版号存储。同样，这使得在相关 revlog 中轻松查找它们的数据成为可能。哈希值用于保存此变更集的唯一标识符。我们有 32 字节，而不是 SHA1 所需的 20 字节，以便允许将来扩展。

12.2.3. 三个 Revlog

有了提供历史数据通用结构的 revlog，我们可以将文件树的数据模型构建在其之上。它由三种类型的 revlog 组成：changelog、manifest 和 filelogs。changelog 包含每个修订版的元数据，以及指向 manifest revlog 的指针（即 manifest revlog 中一个修订版的节点 ID）。反过来，manifest 是一个文件，其中包含文件名列表以及每个文件的节点 ID，指向该文件 filelog 中的修订版。在代码中，我们有 changelog、manifest 和 filelog 类，它们是通用 revlog 类的子类，提供了这两个概念的清晰分层。

changelog 修订版如下所示

0a773e3480fe58d62dcc67bd9f7380d6403e26fa
Dirkjan Ochtman <dirkjan@ochtman.nl>
1276097267 -7200
mercurial/discovery.py
discovery: fix description line

这是您从 revlog 层获得的值；changelog 层将其转换为简单的值列表。第一行提供 manifest 哈希值，然后我们获得作者姓名、日期和时间（以 Unix 时间戳和时区偏移量表示）、受影响的文件列表和描述消息。这里隐藏了一件事：我们允许 changelog 中使用任意元数据，为了保持向后兼容性，我们在时间戳之后添加了这些位。

接下来是 manifest

.hgignore\x006d2dc16e96ab48b2fcca44f7e9f4b8c3289cb701
.hgsigs\x00de81f258b33189c609d299fd605e6c72182d7359
.hgtags\x00b174a4a4813ddd89c1d2f88878e05acc58263efa
CONTRIBUTORS\x007c8afb9501740a450c549b4b1f002c803c45193a
COPYING\x005ac863e17c7035f1d11828d848fb2ca450d89794
…

这是变更集 0a773e 指向的 manifest 修订版（Mercurial 的 UI 允许我们将标识符缩短为任何明确的前缀）。它是一个简单的树中所有文件的列表，每行一个文件，其中文件名后跟一个 NULL 字节，再跟一个指向文件 filelog 的十六进制编码的节点 ID。树中的目录没有单独表示，而是简单地从文件路径中包含斜杠推断出来。请记住，manifest 与每个 revlog 一样在存储中进行 diff，因此此结构应使 revlog 层能够轻松地仅在任何给定修订版中存储更改的文件及其新的哈希值。manifest 通常在 Mercurial 的 Python 代码中表示为类似哈希表的结构，文件名作为键，节点作为值。

第三种类型的 revlog 是 filelog。Filelogs 存储在 Mercurial 的内部 store 目录中，它们几乎与它们跟踪的文件同名。这些名称进行了一些编码，以确保所有主要操作系统都能正常工作。例如，我们必须处理 Windows 和 Mac OS X 上的区分大小写的文件系统、Windows 上特定的禁止的文件名以及各种文件系统使用的不同字符编码。可以想象，跨操作系统可靠地执行此操作可能非常痛苦。另一方面，filelog 修订版的内容并不那么有趣：只是文件内容，除了有一些可选的元数据前缀（我们用它来跟踪文件复制和重命名，以及其他一些小事）。

此数据模型使我们能够完全访问 Mercurial 存储库中的数据存储，但它并不总是很方便。虽然实际的底层模型是垂直方向的（每个文件一个 filelog），但 Mercurial 开发人员经常发现自己希望从单个修订版处理所有细节，他们从 changelog 中的变更集开始，并希望轻松访问该修订版的 manifest 和 filelog。他们后来发明了另一组类，这些类清晰地构建在 revlog 之上，它们正是这样做的。这些被称为 contexts。

关于单独 revlog 的设置方式的一件好事是排序。通过对追加进行排序，使 filelog 首先追加，然后是 manifest，最后是 changelog，存储库始终处于一致状态。任何开始读取 changelog 的进程都可以确信指向其他 revlog 的所有指针都是有效的，这解决了该部门中的许多问题。不过，Mercurial 也有一些显式锁，以确保没有两个进程同时追加到 revlog。

12.2.4. 工作目录

最后一个重要的数据结构是 dirstate。Dirstate 代表了工作目录在任何给定时间点的状态。最重要的是，它跟踪签出了哪个修订版：这是所有来自 status 或 diff 命令的比较的基线，它也决定了要提交的下一个变更集的父级。当 merge 命令已发出时，dirstate 将设置两个父级，试图将一组更改合并到另一组更改中。

由于 status 和 diff 是非常常见的操作（它们可以帮助您检查当前获得的内容与上次变更集之间的进度），dirstate 还包含工作目录上次由 Mercurial 遍历时的状态的缓存。跟踪上次修改的时间戳和文件大小可以加快树遍历的速度。我们还需要跟踪文件的狀態：它是在工作目录中被添加、删除還是合併。這將再次有助於加快遍历工作目錄的速度，並使在提交時輕鬆獲取此資訊。

12.3.1. 分支

分支通常用于分离以后将集成的不同开发线。这可能是因为有人正在尝试一种新方法，只是为了能够始终保持主开发线处于可发布状态（功能分支），或者能够快速发布旧版本的修复程序（维护分支）。这两种方法都很常见，并且为所有现代版本控制系统提供支持。虽然隐式分支在 DAG 基版本控制中很常见，但命名分支（分支名称保存在变更集元数据中）并不常见。

最初，Mercurial 没有办法显式命名分支。相反，分支通过创建不同的克隆并单独发布它们来处理。这很有效，易于理解，特别适用于功能分支，因为开销很小。但是，在大型项目中，克隆仍然可能非常昂贵：虽然存储库存储将在大多数文件系统上进行硬链接，但创建单独的工作树很慢，并且可能需要大量磁盘空间。

由于这些缺点，Mercurial 添加了另一种分支方式：在变更集元数据中包含分支名称。添加了一个 branch 命令，它可以为当前工作目录设置分支名称，以便该分支名称将用于下次提交。正常的 update 命令可用于更新到分支名称，并且在分支上提交的变更集将始终与该分支相关。这种方法被称为 命名分支。但是，Mercurial 花了几次发行版才开始包含一种方法来重新关闭这些分支（关闭分支将隐藏分支，使其不再在分支列表中显示）。分支关闭是通过在变更集元数据中添加一个额外字段来实现的，该字段表明此变更集关闭了分支。如果分支有多个头，则必须关闭所有头，然后分支才会从存储库中的分支列表中消失。

当然，不止一种方法可以实现它。Git 使用引用来命名分支，这与 Mercurial 的命名方式不同。引用是指向 Git 历史记录中另一个对象的名称，通常是更改集。这意味着 Git 的分支是短暂的：一旦您删除了引用，就没有任何分支存在的痕迹，类似于使用独立的 Mercurial 克隆并将其合并回另一个克隆的结果。这使得在本地操作分支变得非常容易和轻便，并且防止了分支列表混乱。

这种分支方式非常流行，比 Mercurial 中的命名分支或分支克隆流行得多。这导致了 bookmarksq 扩展的出现，该扩展很可能会在未来被合并到 Mercurial 中。它使用一个简单的非版本化文件来跟踪引用。用于交换 Mercurial 数据的线协议已经扩展，以允许关于书签的通信，从而可以将它们推送出去。

12.3.2. 标签

乍一看，Mercurial 实现标签的方式可能有点令人困惑。您第一次添加标签（使用 tag 命令）时，一个名为 .hgtags 的文件将被添加到存储库中并提交。该文件中的每一行都将包含一个更改集节点 ID 和该更改集节点的标签名称。因此，标签文件与存储库中的任何其他文件一样对待。

这样做有三个重要的原因。首先，必须能够更改标签；错误会发生，并且应该能够修复它们或删除错误。其次，标签应该是更改集历史记录的一部分：能够看到何时、由谁以及出于什么原因创建了标签，甚至标签是否被更改，都是有价值的。第三，应该能够追溯地标记更改集。例如，一些项目在从版本控制系统导出发布工件之前对其进行了广泛的测试。

这些属性都可以轻松地从 .hgtags 设计中得出。虽然一些用户对工作目录中存在 .hgtags 文件感到困惑，但它使标签机制与 Mercurial 的其他部分（例如，与其他存储库克隆同步）的集成变得非常简单。如果标签存在于源树之外（例如在 Git 中），则必须存在单独的机制来审核标签的来源并处理来自（并行）重复标签的冲突。即使后者很少见，但拥有一个设计，其中这些事情甚至不是问题，也是件好事。

为了正确地实现所有这些，Mercurial 只会在 .hgtags 文件中追加新行。这也方便了合并文件，如果标签是在不同的克隆中并行创建的。任何给定标签的最新节点 ID 始终优先，添加空节点 ID（代表所有存储库共有的空根修订版）将起到删除标签的作用。Mercurial 还将考虑存储库中所有分支的标签，使用最近度计算来确定它们之间的优先级。

12.5.1. 编写扩展

扩展必须通过在 Mercurial 启动时读取的配置文件之一中添加一行来启用；一个键与任何 Python 模块的路径一起提供。有几种方法可以添加功能

• 添加新命令；
• 包装现有命令；
• 包装所使用的存储库；
• 包装 Mercurial 中的任何函数；以及
• 添加新的存储库类型。

添加新命令可以通过简单地在扩展模块中添加一个名为 cmdtable 的哈希表来完成。这将被扩展加载器获取，扩展加载器会将其添加到分派命令时考虑的命令表中。类似地，扩展可以定义名为 uisetup 和 reposetup 的函数，这些函数在 UI 和存储库实例化后由分派代码调用。一种常见的行为是使用 reposetup 函数将存储库包装在扩展提供的存储库子类中。这允许扩展修改各种基本行为。例如，我编写的一个扩展会挂钩到 uisetup 并根据环境中可用的 SSH 身份验证详细信息设置 ui.username 配置属性。

更极端的扩展可以被编写来添加存储库类型。例如，hgsubversion 项目（不包含在 Mercurial 中）为 Subversion 存储库注册了一种存储库类型。这使得从 Subversion 存储库克隆几乎就像它是一个 Mercurial 存储库一样。甚至可以将更改推回 Subversion 存储库，尽管由于这两个系统之间的阻抗不匹配，存在一些边缘情况。另一方面，用户界面是完全透明的。

对于那些想要从根本上改变 Mercurial 的人来说，在动态语言的世界中有一种被称为“猴子补丁”的东西。因为扩展代码在与 Mercurial 相同的地址空间中运行，并且 Python 是一种相当灵活的语言，具有广泛的反射功能，所以可以（而且很容易）修改 Mercurial 中定义的任何函数或类。虽然这会导致一些难看的 hack，但它也是一种非常强大的机制。例如，hgext 中的 highlight 扩展修改了内置的 webserver，以便在存储库浏览器中添加语法高亮显示到允许您检查文件内容的页面中。

还有另一种扩展 Mercurial 的方法，它要简单得多：别名。任何配置文件都可以将别名定义为现有命令的新名称，该命令已经设置了一组特定的选项。这也使得能够为任何命令提供更短的名称。最近版本的 Mercurial 还包括将 shell 命令作为别名调用的功能，这样您就可以使用 shell 脚本设计复杂的命令。

12.5.2. 钩子

版本控制系统长期以来一直提供钩子，作为 VCS 事件与外部世界交互的一种方式。常见用法包括向 持续集成系统 发送通知或更新 web 服务器上的工作目录，以便更改在全球范围内可见。当然，Mercurial 也包含一个子系统来调用这样的钩子。

事实上，它又包含两种变体。一种更像是其他版本控制系统中的传统钩子，因为它在 shell 中调用脚本。另一种更有趣，因为它允许用户通过指定一个 Python 模块和一个要从该模块调用的函数名来调用 Python 钩子。这不仅更快，因为它在同一个进程中运行，而且还传递 repo 和 ui 对象，这意味着您可以轻松地在 VCS 内部启动更复杂的交互。

Mercurial 中的钩子可以分为预命令、后命令、控制和杂项钩子。前两种对任何命令来说都是微不足道的，方法是在配置文件的钩子部分中指定一个 pre-command 或 post-command 键。对于其他两种类型，有一组预定义的事件。控制钩子的区别在于它们在发生某件事之前运行，并且可能不允许该事件继续进行。这通常用于在中央服务器上以某种方式验证更改集；由于 Mercurial 的分布式特性，在提交时无法强制执行此类检查。例如，Python 项目使用一个钩子来确保在整个代码库中强制执行一些编码风格方面——如果一个更改集添加了不符合允许风格的代码，它将被中央存储库拒绝。

钩子另一个有趣的用法是 pushlog，它被 Mozilla 和许多企业组织使用。Pushlog 记录了每一次 push（因为一次 push 可能包含任意数量的变更集），并记录了谁发起了 push 以及何时发起的，为仓库提供了审计跟踪。