GitHub 新代码搜索背后的技术

你的名字 2024-03-27 14:21 0阅读 0赞

## GitHub 新代码搜索背后的技术 ##

*本文译自：[The technology behind GitHub’s new code search][The technology behind GitHub_s new code search]*

了解如何构建世界上最大的公共代码搜索索引。

从一年前推出我们对新的和改进的代码搜索体验的[技术预览，到我们去年 11 月在 GitHub Universe 发布的][11 _ GitHub Universe][公开测试版][Link 1]，围绕我们如何，对一些核心 GitHub 产品体验进行了一系列创新和显着变化，作为开发人员，查找、阅读和导航代码。

我们听到的关于新代码搜索体验的一个问题是，“它是如何工作的？” 为了补充[我在 GitHub Universe 上的演讲][GitHub Universe]，这篇博文给出了该问题的高级答案，并提供了一个了解系统架构和产品技术基础的小窗口。

那么，它是如何工作的*呢*？简短的回答是，我们在 Rust 中从头开始构建了自己的搜索引擎，专门用于代码搜索领域。我们称这个搜索引擎为黑鸟，但在解释它的工作原理之前，我认为它有助于稍微了解我们的动机。乍一看，从头开始构建搜索引擎似乎是一个有问题的决定。为什么要这么做？不是已经有很多现有的开源解决方案吗？为什么要建立新的东西？

公平地说，在 GitHub 的几乎整个历史中，我们已经并且一直在尝试使用现有的解决方案来解决这个问题。[您可以在 Pavel Avgustinov 的帖子GitHub 代码搜索简史][Pavel Avgustinov _GitHub]中阅读更多关于我们旅程的信息，但有一点很突出：我们没有太多运气使用通用文本搜索产品来支持***代码***搜索。用户体验差，索引速度慢，托管成本高。有一些更新的、特定于代码的开源项目，但它们肯定无法达到 GitHub 的规模。因此，了解所有这些后，我们有动力通过三件事来创建我们自己的解决方案：

1.  我们有一个全新的用户体验愿景，即能够提出代码问题并通过迭代搜索、浏览、导航和阅读代码获得答案。
2.  我们了解***代码***搜索与一般文本搜索有着独特的区别。代码已经被设计成可以被机器理解，我们应该能够利用这种结构和相关性。搜索代码也有独特的要求：我们要搜索标点符号（例如，句号或左括号）；我们不想阻止；我们不希望从查询中删除停用词；并且，我们要使用正则表达式进行搜索。
3.  GitHub 的规模确实是一个独特的挑战。当我们第一次部署 Elasticsearch 时，花了几个月的时间来索引 GitHub 上的所有代码（当时大约有 800 万个存储库）。今天，这个数字超过了 2 亿，而且代码不是静态的：它在不断变化，这对搜索引擎来说很难处理。对于测试版，您目前可以搜索近 4500 万个存储库，代表 115TB 的代码和 155 亿个文档。

归根结底，现成的东西都不能满足我们的需求，所以我们从头开始构建了一些东西。

### 只用grep？ ###

不过，首先，让我们探索解决问题的蛮力方法。我们经常收到这样的问题：“你为什么不直接使用 grep？” 为了回答这个问题，让我们在 115 TB 的内容上使用[ripgrep做一些餐巾纸计算。][ripgrep]在配备八核 Intel CPU 的机器上，ripgrep可以在 2.769 秒内对缓存在内存中的 13 GB 文件[运行详尽的正则表达式查询，或大约 0.6 GB/秒/核。][0.6 GB]

我们很快就会发现，对于我们拥有的大量数据来说，这真的行不通。代码搜索运行在 64 核，32 机集群上。即使我们设法将 115 TB 的代码放入内存并假设我们可以完美地并行化工作，我们也会让 2,048 个 CPU 内核饱和 96 秒来处理单个查询！只有那个查询可以运行。其他人都必须排队。结果是高达每秒 0.01 次查询 (QPS)，祝你好运，将你的 QPS 加倍——这将是与领导层就你的基础设施账单进行的有趣对话。

只是没有经济高效的方法可以将这种方法扩展到 GitHub 的所有代码和所有 GitHub 的用户。即使我们在这个问题上投入了大量资金，它仍然无法满足我们的用户体验目标。

你可以看到这是怎么回事：我们需要建立一个索引。

### 搜索索引入门 ###

如果我们以索引的形式预先计算一堆信息，我们只能快速查询，您可以将其视为从键到该键出现的文档 ID 排序列表（称为“发布列表”）的映射。例如，这里有一个编程语言的小索引。我们扫描每个文档以检测它是用什么编程语言编写的，分配一个文档 ID，然后创建一个倒排索引，其中语言是键，值是文档 ID 的发布列表。

#### 远期指数 ####

<table> 
 <thead> 
  <tr> 
   <th><strong>Doc ID</strong></th> 
   <th><strong>Content</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>def lim<br>puts “mit”<br>end</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>fn limits() { </td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>function mits() { </td> 
  </tr> 
 </tbody> 
</table>

#### 倒排索引 ####

<table> 
 <thead> 
  <tr> 
   <th><strong>Language</strong></th> 
   <th><strong>Doc IDs (postings)</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>JavaScript</td> 
   <td>3, 8, 12, …</td> 
  </tr> 
  <tr> 
   <td>Ruby</td> 
   <td>1, 10, 13, …</td> 
  </tr> 
  <tr> 
   <td>Rust</td> 
   <td>2, 5, 11, …</td> 
  </tr> 
 </tbody> 
</table>

对于代码搜索，我们需要一种特殊类型的倒排索引，称为 ngram 索引，这对于查找内容的子字符串很有用。[ngram][]是长度为*n*的字符序列。例如，如果我们选择 n=3（trigrams），则组成内容“limits”的 ngrams 为`lim`, `imi`, `mit`, `its`。使用我们上面的文档，这些三元组的索引将如下所示：

<table> 
 <thead> 
  <tr> 
   <th><strong>ngram</strong></th> 
   <th><strong>Doc IDs (postings)</strong></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>lim</td> 
   <td>1, 2, …</td> 
  </tr> 
  <tr> 
   <td>imi</td> 
   <td>2, …</td> 
  </tr> 
  <tr> 
   <td>mit</td> 
   <td>1, 2, 3, …</td> 
  </tr> 
  <tr> 
   <td>its</td> 
   <td>2, 3, …</td> 
  </tr> 
 </tbody> 
</table>

为了执行搜索，我们将多次查找的结果相交，以提供字符串出现的文档列表。使用三元组索引，您需要四次查找：`lim`、`imi`、`mit`和`its`才能完成对 的查询`limits`。

与 hashmap 不同的是，这些索引太大而无法放入内存，因此我们为需要访问的每个索引构建迭代器。这些延迟返回排序后的文档 ID（ID 是根据每个文档的排名分配的）并且我们将迭代器相交并合并（根据特定查询的要求）并且只读取足够远以获取请求数量的结果。这样我们就不必将整个发布列表保存在内存中。

### 索引 4500 万个存储库 ###

我们面临的下一个问题是如何在合理的时间内构建此索引（请记住，这在我们的第一次迭代中花费了数月）。通常情况下，这里的技巧是确定对我们正在使用的特定数据的一些洞察力，以指导我们的方法。在我们的案例中，有两件事：Git 使用[内容可寻址哈希][Link 2]以及 GitHub 上实际上有很多重复内容这一事实。这两个见解使我们做出以下决定：

1.  **按 Git blob 对象 ID**进行分片，这为我们提供了一种在分片之间均匀分布文档同时避免任何重复的好方法。由于特殊的存储库，不会有任何热服务器，我们可以根据需要轻松扩展分片的数量。
2.  **将索引建模为树**并使用增量编码来减少爬行量并优化我们索引中的元数据。对我们来说，元数据就像文档出现的位置列表（路径、分支和存储库）以及有关这些对象的信息（存储库名称、所有者、可见性等）。对于流行内容，此数据可能非常大。

我们还设计了系统，以便查询结果在提交级别的基础上保持一致。如果您在队友推送代码时搜索存储库，则在系统完全处理之前，您的结果不应包含新提交的文档。事实上，当您从存储库范围的查询中获取结果时，其他人可能正在对全局结果进行分页并查看不同的、先前但仍然***一致***的索引状态。使用其他搜索引擎很难做到这一点。Blackbird 提供这种级别的查询一致性作为其设计的核心部分。

### 让我们建立一个索引 ###

有了这些见解，让我们将注意力转向使用 Blackbird 构建索引。此图表示系统的摄取和索引端的高级概述。

![在这里插入图片描述][676e87acec2744f59f685ac33b5378f5.png_pic_center]

Kafka 提供了告诉我们去索引某些东西的事件。有一堆与 Git 交互的爬虫和从代码中提取符号的服务，然后我们再次使用 Kafka，以允许每个分片按照自己的节奏使用文档进行索引。

虽然系统通常只响应`git push`抓取更改内容等事件，但我们还有一些工作要做，以便第一次摄取所有存储库。该系统的一个关键属性是我们优化了我们进行初始摄取的顺序，以充分利用我们的增量编码。我们使用表示存储库相似性的新颖概率数据结构并通过从存储库相似性图[1][][的最小生成树][Link 3]的级别顺序遍历驱动摄取顺序来执行此操作。

使用我们优化的摄取顺序，然后通过将每个存储库与我们构建的增量树中的父存储库进行比较来抓取每个存储库。这意味着我们只需要爬取该存储库（而不是整个存储库）独有的 blob。爬取包括从 Git 中获取 blob 内容，对其进行分析以提取符号，以及创建将作为索引输入的文档。

然后将这些文档发布到另一个 Kafka 主题。这是我们在分片之间划分[2][]数据的地方。每个分片使用主题中的单个 Kafka 分区。通过使用 Kafka，索引与爬行分离，Kafka 中消息的排序是我们获得查询一致性的方式。

索引器分片然后获取这些文档并构建它们的索引：在序列化之前构建 ngram 索引[3][]（用于内容、符号和路径）和其他有用的索引（语言、所有者、存储库等）并在足够的工作完成时刷新到磁盘积累。

最后，分片运行压缩以将较小的索引折叠成较大的索引，这些索引查询效率更高且更容易移动（例如，移动到只读副本或用于备份）。Compaction 还按分数[k-merge][]发布列表，因此相关文档具有较低的 ID，并且将首先由惰性迭代器返回。在初始摄取期间，我们延迟压缩并在最后进行一次大运行，但是随着索引跟上增量变化，我们以更短的间隔运行压缩，因为这是我们处理文档删除等事情的地方。

### 查询的生命周期 ###

现在我们有了一个索引，通过系统跟踪查询就很有趣了。我们要遵循的查询是一个符合[Rails 组织][Rails]的正则表达式，用于查找以 Ruby 编程语言编写的代码：`/arguments?/ org:rails lang:Ruby`. 查询路径的高级架构看起来有点像这样：

![在这里插入图片描述][b39e4b0f5e3243fd9355a0b03d69535c.png_pic_center]

在 GitHub.com 和分片之间是一项服务，它协调接受用户查询并将请求分散到搜索集群中的每个主机。我们使用 Redis 来管理配额和缓存一些访问控制数据。

前端接受用户查询并将其传递给 Blackbird 查询服务，我们将查询解析为抽象语法树，然后重写它，将诸如语言之类的东西解析为其规范的[Linguist][]语言 ID，并在额外的条款上标记权限和范围. 在这种情况下，您可以看到重写如何确保我将从公共存储库或我有权访问的任何私有存储库获得结果。

And(
        Owner("rails"),
        LanguageID(326),
        Regex("arguments?"),
        Or(
            RepoIDs(...),
            PublicRepo(),
        ),
    )

接下来，我们扇出并发送*n 个*并发请求：一个到搜索集群中的每个分片。由于我们的分片策略，查询请求必须发送到集群中的每个分片。

在每个单独的分片上，我们然后对查询进行一些进一步的转换，以便在索引中查找信息。在这里，您可以看到正则表达式被翻译成一系列关于 ngram 索引的子字符串查询。

and(
      owners_iter("rails"),
      languages_iter(326),
      or(
        and(
          content_grams_iter("arg"),
          content_grams_iter("rgu"),
          content_grams_iter("gum"),
          or(
            and(
             content_grams_iter("ume"),
             content_grams_iter("ment")
            )
            content_grams_iter("uments"),
          )
        ),
        or(paths_grams_iter…)
        or(symbols_grams_iter…)
      ), 
      …
    )

如果您想了解有关将正则表达式转换为子字符串查询的方法的更多信息，请参阅 Russ Cox 关于[正则表达式匹配与 Trigram 索引][Trigram]的文章。我们使用不同的算法和动态 gram 大小而不是 trigrams（见下文[3][]）。在这种情况下，引擎使用以下克数：`arg`、`rgu`、`gum`，然后是`ume`和`ment`，或 6 克`uments`。

每个子句的迭代器运行：*and*表示相交，*或*表示并集。结果是文档列表。在评分、排序和返回请求数量的结果之前，我们仍然必须仔细检查每个文档（以验证匹配并检测它们的范围）。

回到查询服务，我们聚合所有分片的结果，按分数重新排序，过滤（双重检查权限），并返回前 100 名。GitHub.com 前端仍然需要做语法高亮，term高亮、分页，最后我们就可以将结果渲染到页面上了。

我们来自各个分片的 p99 响应时间大约为 100 毫秒，但由于聚合响应、检查权限和语法突出显示等原因，总响应时间会稍长一些。一个查询占用索引服务器上的单个 CPU 内核 100 毫秒，因此我们的 64 核主机有大约每秒 640 个查询的上限。与 grep 方法 (0.01 QPS) 相比，它的速度非常快，并为同时用户查询和未来增长提供了充足的空间。

### 总之 ###

现在我们已经看到了完整的系统，让我们重新审视问题的规模。我们的摄取管道每秒可以发布大约 120,000 个文档，因此处理这 155 亿个文档大约需要 36 个小时。但是增量索引减少了我们必须爬取的文档数量 50% 以上，这使我们能够在大约 18 小时内重新索引整个语料库。

索引的大小也有一些重大胜利。请记住，我们从要搜索的 115 TB 内容开始。内容去重和增量索引将**唯一**内容减少到大约 28 TB。索引本身只有 25 TB，其中不仅包括所有索引（包括 ngram），还包括所有唯一内容的压缩副本。这意味着我们的总索引大小（包括内容）大约是原始数据大小的四分之一！

如果您还没有注册，我们希望您[加入我们的测试版][Link 4]并尝试新的代码搜索体验。让我们知道您的想法！我们正在积极添加更多存储库并根据像您一样的人的反馈修复粗糙的边缘。

#### 笔记 ####

--------------------

1.  为了确定最佳摄取顺序，我们需要一种方法来判断一个存储库与另一个存储库的相似程度（在内容方面相似），因此我们发明了一种新的概率数据结构来在与[MinHash][]和[超级日志日志][Link 5]. 这种数据结构，我们称之为几何过滤器，允许计算集合相似性和集合之间具有对数空间的对称差异。在这种情况下，我们要比较的集合是由 (path, blob\_sha) 元组表示的每个存储库的内容。有了这些知识，我们可以构建一个图，其中顶点是存储库，边是用这个相似性度量加权的。计算该图的最小生成树（以相似度作为成本），然后对树进行层序遍历，为我们提供一个摄取顺序，我们可以在其中充分利用增量编码。实际上，这个图非常庞大（数百万个节点，数万亿条边），因此我们的 MST 算法计算出的近似值仅需几分钟即可计算并提供我们想要的 90% 的增量压缩优势。
2.  该索引由 Git blob SHA 进行分片。分片意味着将索引数据分散到多个服务器上，我们需要这样做以便轻松地水平扩展读取（我们关注 QPS）、存储（磁盘空间是主要关注点）和索引时间（这受限于各个主机上的 CPU 和内存）。
3.  我们使用的 ngram 索引特别有趣。虽然 trigrams 是设计空间中众所周知的最佳点（正如[Russ Cox 和其他人][Trigram]所指出的：bigrams 的选择性不够，quadgrams 占用了太多空间），但它们在我们的规模上会造成一些问题。
    
    对于象卦这样的普通克`for`，选择性不够。我们得到了太多的误报，这意味着查询速度很慢。误报的一个例子是找到一个包含每个单独的 trigram，但不是彼此相邻的文档。在您获取该文档的内容并仔细检查您已经完成了大量必须丢弃的工作之前，您无法判断。我们尝试了多种策略来解决这个问题，比如添加跟随掩码，它使用位掩码来表示跟在三元组后面的字符（基本上是四元组的一半），但它们饱和得太快以至于无法使用。
    
    我们称该解决方案为“稀疏克”，它的工作原理如下。假设你有一些函数，给定一个二元组给出一个权重。例如，考虑字符串`chester`。我们给每个二元组一个权重：“ch”为 9，“he”为 6，“es”为 3，依此类推。 ! 
    
    使用这些权重，我们通过选择内部权重严格小于边界权重的区间来标记化。该区间的包含字符构成了 ngram，我们递归地应用该算法，直到它在 trigrams 自然结束。在查询时，我们使用完全相同的算法，但只保留覆盖的 ngram，因为其他的都是多余的。

[The technology behind GitHub_s new code search]: https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/
[11 _ GitHub Universe]: https://github.blog/2021-12-08-improving-github-code-search/
[Link 1]: https://github.blog/2022-11-15-a-better-way-to-search-navigate-and-understand-code-on-github/
[GitHub Universe]: https://www.youtube.com/watch?v=QCs76SC1ZZ0
[Pavel Avgustinov _GitHub]: https://github.blog/2021-12-15-a-brief-history-of-code-search-at-github/
[ripgrep]: https://github.com/BurntSushi/ripgrep
[0.6 GB]: https://github.com/BurntSushi/ripgrep#quick-examples-comparing-tools
[ngram]: https://en.wikipedia.org/wiki/N-gram
[Link 2]: https://en.wikipedia.org/wiki/Content-addressable_storage
[676e87acec2744f59f685ac33b5378f5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8b5c4c2889e94699b8fd772136e66f20.png
[1]: https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/#fn-69904-1
[Link 3]: https://en.wikipedia.org/wiki/Minimum_spanning_tree
[2]: https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/#fn-69904-2
[3]: https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/#fn-69904-bignote
[k-merge]: https://en.wikipedia.org/wiki/K-way_merge_algorithm
[Rails]: https://github.com/rails
[b39e4b0f5e3243fd9355a0b03d69535c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e982b1b12a7c415ca9be520334793c46.png
[Linguist]: https://github.com/github/linguist
[Trigram]: https://swtch.com/~rsc/regexp/regexp4.html
[Link 4]: https://github.com/features/code-search
[MinHash]: https://en.wikipedia.org/wiki/MinHash
[Link 5]: https://en.wikipedia.org/wiki/HyperLogLog