超越 GVFS: 更多 Git 大存储库的优化细节

在过去的几年中，微软一直将整个公司业务转移到基于 Visual Studio Team Services 的现代工程系统中，并使用 Git 作为版本控制系统。对于微软中的许多项目来说，这是没有问题的，因为：Git主页中如此描述：

Git 为 Linux 内核而生，这意味着它从一开始就必须能够有效地处理大规模代码仓库。

而且 Git 确实对 Linux 内核的项目进行了非常有效的处理，这对于一个开源项目来说确实是相当大规模的。它在 HEAD 中包含6万个文件，其历史记录跨度 12 年。

但对企业项目而言：6万个文件并不算多。

我所工作的存储仓库，其中包含了 Visual Studio Team Services 的代码库，拥有125,000个文件，比它的两倍还大。而在微软，这只能算是“中等规模”。当我们谈论一个大规模的源码树时，我们讨论的是：Windows，它的体量高达 350 万个文件。这包括创建 Windows 构建所需的源代码、测试和构建工具，以及创建了整个操作系统的 ISO。

这起初听起来很疯狂，但真的不用太过惊讶。对比下 Linux 内核，这 6 万个文件仅仅用于构建一个内核（和相关模块），该内核必须能够载入到你的机器的 RAM 中。我使用的内核 —— stack Ubuntu 16.04 镜像文件——是 7 兆字节，并附带另外 200 兆字节的模块数据。

Linus 曾开玩笑说内核已经变得“臃肿而庞大”。当然，这个 200 兆字节比 90 年代初期要大得多，当时内核不得不放到一个软盘上，而不得不为一个只有 4 兆字节 RAM 的机器适配，同时确保剩下足够的空间来驱动该系统。

而 Windows 10 呢? 那是 4GB 大小的 ISO 镜像。

由于所有Windows——内核、库，应用程序——是一起发布的，它们也被一起版本化，在一个大的“monorepo”中。 当计划将 Windows 迁移到 Git 时，我们考虑将代码库分解成许多较小的存储库，并将它们按照 Git 子模块或 Android 的 repo 系统进行分层处理。 但有时候 monrepos 是最简单的协作方式。

不幸的是，像 Windows 这样庞大的 monorepo 有一个问题，Git 并没有处理好过如此大的存储库的先例。

在过去几年中，我们一直在努力调整 Git 来自适应处理像 Windows 存储库这样真正大型的 monorepos。这项工作的最大部分——到目前为止，是 GVFS，Git Virtual Filesystem（Git虚拟文件系统）。

GVFS 允许我们的开发人员在 clone 时不用把 350 万个文件全部下载，而是在开发人员工作的源代码树的较小部分中进行页面访问。

Saeed Noursalehi 正在撰写一系列有关 GVFS 的文章，以及如何让我们让 Git 变得可伸缩。 这是非常高级的功能，绝对能够用于处理 Windows 大小规模的源代码树，但它并不全是我们在处理 Windows 存储时必须做的全部工作。

将这么多文件放在单个存储库中对 Git 的数据结构和存储机制来说是很大的挑战，即使是在不是所有的文件都实际保存于工作目录中的情况下。

虽然 GVFS 是像 Windows 团队这样的巨型存储库的重要解决方案，但我们所做的这些额外工作将帮助常规的 Git 用户获得更多的标准存储库大小。

索引（也称作“暂存区”或“缓存”）是 Git 仓库的核心数据结构之一。它包含仓库中每个文件的列表，并且几乎所有涉及工作目录的操作都会查阅它。

索引将填充您在克隆仓库时以及切换分支时检出的路径列表。当您运行 status 以确定哪些文件处于 staged 和 modified 的状态，它将被审查。并且当您进行合并时，新的树（以及所有冲突）都将存储在索引中。

由于它用于这么多操作，所以访问索引必须很快，即使它包含 350 万个文件。Git 保持索引访问速度的一种方法是通过保存路径列表的排序，以便您可以通过二进制搜索来查找您需要的内容。

但是保存此列表的排序依然是有开销的。我们注意到大型存储库中的一个痛点是切换分支：这种日常的操作需要 30 秒到一分半钟不等。显然，检出操作中把文件传输到磁盘上的这个步骤是最慢的，不过如果我们再深入探究下去，会惊奇地发现，我们同样也花费了大量的时间去创建新的索引，以便它包含新分支中的文件列表。

对于我们要插入索引的文件，我们会尝试找出我们要插入的文件。这意味着系统是通过对索引的二份查找来找到新路径的位置的。

在逻辑上充分说明，列表文件在我们插入时就已经被排序了。因此，我们会忙于在每个路径上执行一个 O(log n) 查找，这样做的目的只是为了去发现我们要在索引末尾附加的路径。因此我们改变了这个步骤，跳过二分查找，只做追加。

这个看似很小的优化在 git checkout 调用中节省了 15-20% 的时间。事实证明，当 n 是 350 万个文件时，O(n log n) 变得相当缓慢。

当我们在查看索引时，我们观察到另一个类似的小操作：文件的校验和验证。当 Git 客户端编写索引时，它们计算其内容的 SHA-1 散列，并将其附加到文件的末尾。这使得 Git 在重新读取索引时会比较该哈希值，以确保它不会被微小的磁盘损坏所破坏。

对于小型的存储库和适用于 Linux 内核大小的存储库，这种计算基本上不是问题：计算 SHA-1 散列时读取索引耗时很低。但是对于像 Windows 这样的大型存储库，散列索引的内容几乎和解析它一样耗时。

我们首先将散列计算工作分解成后台线程，结果非常好。但是，最终，在每个操作上验证散列通常是不必要的，因为校验和检测到这种微妙的文件损坏是非常罕见的。 （虽然并不是完全没有听说过）。

所以我们可以简化这个，在读取索引时完全跳过哈希值的计算。现在，你仍然可以使用 git fsck 验证索引的校验，但每个读取索引的其他操作都将获得加速。

git 本身 — 命令行应用程序，当然是我们使用 Git 存储库最明显的方式，但这并不是唯一的方法。在 Visual Studio Team Services 中，在其中我们托管所有的 Git 存储库（包括 Windows）的地方，使用 libgit2 项目来处理 Git 存储库。

libgit2 是一个开源项目，现在主要由 GitHub 和 Microsoft 的员工维护，它的架构支持自定义数据库驱动程序进行存储库访问。这使得 Visual Studio Team Services 能够在 Azure blob 存储中非常有效地存储代码仓库，而不是仅仅在文件系统中备份(dump)空存储库。

当 Microsoft 将合并功能添加到 libgit2 时，我们可以高效地将 Azure 托管的存储库中的 pull 请求合并到 VSTS 中 — 我们希望处理来自大型存储库的 pull 请求。但是，尽管我们做了最佳规划，但仍然存在着在 Windows 存储库规模大小的项目上面临性能问题的地方。

当 Git 保存修订版本时，它并不会保存在两个修订版本之间改动的文件列表，或它们是如何改动的。相反，它会在每个版本中存储整个版本树的快照。这意味着当 git 显示你已重命名的一个文件时，它实际上是通过遍历两个不同版本中的所有文件，将每个被删除的文件与每个已添加的文件进行比较。如果已删除的文件与新添加的文件非常类似，则 git 判定你实际从旧的文件重新命名为新的文件。

这种重新命名检测在 merge 期间尤为重要 - 如果一个开发人员将文件从 foo.txt 重命名为 bar.txt，另一个开发人员对 foo.txt 进行了改动，那么你需要确保将这些更改包含在新的文件中。通过重命名检测，如你所愿，改动将包含在 bar.txt 中。没有重新命名检测，你将在 foo.txt 上（它在一个分支中被编辑而在另一个分支中被删除了）触发冲突，你将得到一个名为 bar.txt 的新文件。这根本不是你想要的。

不幸的是，重命名检测本质上是二次方复杂度的：你将每个已删除的文件与每个添加的文件进行比较，以确定哪个具有最佳的相似性匹配。为了避免类似情况开销会非常大，git 有一个名为 merge.renameLimit 的设置项，可以避免对于太大的 n 执行这种高昂的O(n^2)比较操作。

像 git 一样，libgit2 服从 merge.renameLimit 来进行昂贵的相似检测。但像 git 一样，libgit2 不用在使用 merge.renameLimit 进行精确重命名检测担忧。勿须比较两个文件的内容以确定它们是否相似，精确的重命名检测只是查看文件 ID，这个 ID 就是其内容的 SHA-1 哈希值。 相同的哈希值意味着相同的内容，因此你可以轻松地通过比较ID来确定文件是否被重命名。

不幸的是，libgit2 使用相同的 O(n^2) 算法，将每个已删除的文件的 ID 与每个添加的文件的 ID 进行精确重命名检测。 当 Windows 推送了一个非常大的重构，在那里它们重命名了一个目录的所有文件，精确的重命名检测将不可控，它对涉及的数千个文件 ID 进行二次时间比较，会导致该请求超时。

要处理这个看似简单的重构更改，我们要回头看看 libgit2 的重命名检测功能。我们遍历删除文件的列表，并构建一个哈希表，将他们的 ID 映射到旧文件名，而不是将每个已删除的文件与每个添加的文件进行比较。 然后我们遍历列表中添加的文件，寻找该散列中的 ID：如果发现，那么我们知道我们有一个重命名文件。

这种直接的改动将 O(n^2) 操作简化成线性时间的简单检测，这样 Windows 再次以这些大规模的重构来创建 pull 请求。

在许多方面，这项工作只是 Git 变革的下一步，以处理更大的存储库。我们正在尝试使用更高效的数据结构和访问模式来替换效率较低的数据结构和访问模式，但这项工作在之前做过。这些O(n log n)操作中的许多都是O(n^2)级别的，并且被改进一次以帮助 Git 可伸缩到目前的规模。

但这项工作是枯燥乏味并且耗时的。不像跟踪大多数 bug，性能工作需要不同的调试技巧；通常在调试器中进行调试并没有什么帮助。良好的性能分析工具能有所帮助——我们特别地更新了 Git for Windows，以便能够在 Visual Studio 下进行编译，以使我们能够利用 Visual Studio 内置的优秀性能分析工具。

但一般来说，它需要建立一个再现环境，并且一遍又一遍地运行相同的慢速操作，试图找出性能问题的根本原因，或者变糟糕的原因。经常需要结合大量的重复代码阅读，来慢慢寻找聪明的解决方案（但是一旦你最终找到，它们就显得很明显）。

一旦我们了解问题的根源，这些性能问题的修复几乎总是采用折中的方案。有时候，我们会通过申请更多内存来解决这个问题，缓存一些值，这样我们就不必再次重新计算它们了。有时候，我们用逻辑处理该问题，识别到一种模式，并利用它来减少我们的工作量。有时候我们会用 CPU 解决问题，通过多线程并行工作。

但是，每个性能问题都需要我们把我们最稀有和最有价值的资产投入到这个问题上：我们的开发人员。

虽然我们正在为 Windows 团队进行这项性能改善工作，但我们正在将这些更改贡献给 Git，以提高 git 整体性能。这将影响整个软件开发行业，从微软到 Linux 内核内核到下一个划时代项目的启动。如果你想帮助我们改进软件开发：这是我们的招聘地址。