新智元报道
编辑：LRS
目前 GitHub 新版搜索引擎已经处于测试阶段，只需 18 小时即可建完 4500 万个代码库的索引。
2021 年 12 月，GitHub 发布了一次技术预览（technology preview），针对 GitHub 代码搜索「啥也搜不出来」的问题进行了一次全面优化。
去年 11 月，在 GitHub Universe 开发者大会上，官方再次发布了公开测试版，主要解决开发者寻找、阅读和导航代码的问题。
在大会上，有人问了一个重要的问题，「代码搜索」改进背后的原理到底是什么？
最近，GitHub 发布了一篇博客，详细解释了新模型背后的技术原理和系统架构。
从零打造 GitHub 搜索引擎
简单来说，新搜索引擎的背后就是研究人员用 Rust 重新编写的一个轮子，专门针对代码搜索进行优化，代号黑鸟（Blackbird）。
乍一看，从零开始构建搜索引擎似乎是一个令人费解的决定：为什么要从头再来？现有的开源解决方案不是已经很多了吗？为什么还要再浪费精力造一个新的东西？
实际上 GitHub 一直在尝试使用现有的解决方案来解决搜索问题，但不巧的是，用于通用文本搜索的产品很难适配到「代码」搜索上。由于索引速度太慢，导致用户体验很差，并且所需的服务器数量很大，运行成本也过高。
虽然有一些较新的、专门适配于代码搜索的开源项目，但它们仍然不适合 GitHub 这么大规模的代码库。
基于上述观察，GitHub 的开发者设定的目标和结论主要有三个：
1. 用户在搜索过程中能够得到全新的体验，可以通过提出一些代码上的问题来迭代搜索、浏览、导航（navigate）和阅读代码来得到答案。
2. 代码搜索与通用文本搜索之间有着许多不同之处。
开发者编写代码是为了让机器理解，所以代码搜索的过程应该利用上代码的结构和相关性；并且用户可能会搜索标点符号（例如，句号、开括号等代码中的操作符）；不要对代码中的词做词干分析（stemming）；不要从 query 中删除停止词；或者使用正则表达式进行搜索。
3. GitHub 的规模确实是一个独特的挑战。
旧版本的搜索引擎使用的是 Elasticsearch，第一次部署的时候花了几个月的时间来索引 GitHub 上的所有代码(当时大约有 800 万个代码库)，但现在代码仓库数量已经超过了 2 亿，而且这些代码还不是静态的：开发者不断提交，代码也在不断变化，对于构建搜索引擎来说非常具有挑战性。
目前在测试版中，用户可以搜索大约 4500 万个代码库，包含 115TB 的代码和 155 亿个文档。
综上所述，现成的东西满足不了需求，所以，从零开始再造一个。
试试 Grep？
在搜索的时候，一个常用的工具就是「grep」，通过输入表达式，就能在文本中进行匹配，所以为什么不干脆用 grep 蛮力解决搜索问题？
为了回答这个问题，可以先计算一下用 ripgrep 对 115TB 的代码进行匹配需要多长时间。
在一台配备 8 核 Intel CPU 的机器上，ripgrep 可以在 2.769 秒内(约 0.6 GB/sec/core)对缓存在内存中的 13 GB 文件运行正则表达式查询。
简单的计算后就能发现，对于当下的海量数据来说，该方法是行不通的：假设代码搜索程序运行在一个拥有 32 台服务器的集群上，每台机器有 64 个核心，即使把 115TB 的代码全放到内存里，并且一切运行顺利，2,048 个 CPU 核大概需要 96 秒跑完「一个」query，而且只能是一个，其他用户得排队，也就是说只有 QPS 是 0.01 的话才能用 grep
所以蛮力走不通，只能先建一个索引。
搜索索引（serach index）
只有以索引的形式预先计算好相关信息后，才能让搜索引擎在查询时快速响应，简单来说，索引就是一个 key-value 映射，在倒排索引（inverted index）的情况下，key 就是一个关键词，value 就是出现该词的有序文档 ID 列表。
在代码搜索任务中，研究人员用到了一种特殊类型的倒排索引，即 ngram 索引。
一个 ngram 是长度为 n 的字符序列，例如 n = 3（trigams）意为 key 的最大长度只能是3，对于较长的 key 来说，就需要按照长度 3 进行切割，比如 limits 就被分为 lim, imi, mit 和 its
执行搜索时，综合多个 key 的查询结果，合并后得到该字符串所出现的文档列表
下一个问题是如何在相对合理的时间内完成索引的构建。
研究人员观察到：Git 使用内容寻址散列，以及 GitHub 上实际上有相当多的重复内容，所以研究人员提出下面两个方法建立索引。
1. shard by Git blob object ID 提供了一种在 shards 之间均匀分布文档的好方法，并且可以避免重复，同时能够根据需要随时扩展 shards 的数量。
2. 将索引建模为树，并使用差分编码（delta encoding）来减少 crawling 的数量并优化索引中的元数据，其中元数据包括文档出现的位置列表（哪个 path、分支和代码库）以及关于这些对象的信息（代码库名称、所有者、可见性等）。对于一些热门仓库来说，元数据量可能会相当大。
GitHub 还设计了一个系统，使得查询结果与提交后的代码保持一致。
如果用户在团队成员推送代码时搜索代码库，那么在系统完全处理完新提交的文档之前，搜索结果中不应该包含这些文档，Blackbird 将 commit 查询一致性作为其设计的核心部分。
Blackbird
下面是 Blackbird 搜索引擎的架构图。
首先，Kafka 会提供 events 来指定索引的内容，然后就会有大量的爬虫（crawler）程序与 Git 进行交互，其中还有一个从代码中提取符号的服务；再次使用 Kafka 对每个 shard 进行索引，获取目标文档。
虽然该系统只是响应像「git push」来抓取更改内容等类似的事件，但在首次 ingest 所有代码库时还需要做一些额外的工作。
该系统的一个关键特性就是对初始 ingest 顺序的优化以充分利用增量编码。
GitHub 使用了一种全新的概率数据结构来表示代码库的相似性，并且通过从代码库相似性图的一个最小生成树的水平顺序遍历中计算得到 ingest 的顺序。
基于优化后的 ingest 顺序，delta 树的构建过程就是将每个代码库与其父代码库进行差分，这也意味着该系统只需要抓取当前代码库所特有的 blobs，爬取包括从 Git 获取 blob 内容，分析后提取符号，以及创建将作为索引输入的文档。
然后将这些文件发布到另一个 Kafka 主题中，也是在 shards 之间将数据分区的地方。每个 shards 使用主题中的一个 Kafka 分区。
使用 Kafka 可以将索引与 crawl 解耦，并且 Kafka 中对消息的排序也可以也可以使得查询结果一致。
然后，indexer shards 找到这些文档并构建索引：tokenizing 内容、符号和 path 以构造 ngram indices 和其他有用的 indices (语言、所有者、代码库等) ，并将结果刷新到磁盘上。
最后，对 shards 进行压缩（compaction），将较小的索引折叠成较大的索引，这样查询起来更有效，移动起来也更容易。
query 的生命周期
有了索引之后，通过系统跟踪 query 就变得简单了，每个 query 都是一个正则表达式，可以写作「/arguments?/ org:rails lang:Ruby」，即查找一个由 Rails 组织用 Ruby 语言编写的代码。
在 GitHub.com 和 shards 之间还有一个服务，负责协调接收用户 query，并将请求分散到搜索集群中的每个主机上，最后使用 Redis 来管理磁盘空间（quotas）和缓存一些访问控制数据。
前端接受一个用户查询并将其传递给黑鸟，然后将 query 解析为一个抽象语法树，将其重写为规范的语言 ID，并在额外的子句上标记权限和范围。
下一步将发送 n 个并发请求: 向搜索集群中的每个 shard 发送一个，系统中设定的 sharding 策略就是向集群中的每个 shard 发送查询请求。
然后，在每个单独的 shard 上对查询进行一些转换以便在索引中查找信息。
最后聚合所有 shard 返回的结果，按分数重新排序，筛选(再次检查权限) ，并返回 top 100，然后 GitHub.com 的前端进行语法突显、术语高亮、分页，最后我们才能将结果呈现给页面。
实际使用中，单个 shard 的 p99 响应时间大约是 100ms，但是由于聚合 response、检查权限以及语法突显等原因，总的响应时间要长一些。
一个 query 在索引服务器上占用一个 CPU 核心 100 毫秒，因此 64 个核心主机的上限大约是每秒 640 个查询。与 grep 方法(0.01 QPS)相比，这种方法可以说是相当快了。
总结
完整的系统架构介绍完以后，可以重新来审视一下问题的规模了。
GitHub 的 ingest pipeline 每秒可以发布大约 12 万个文档，因此全部处理完 155 亿个文档需要大约 36 个小时；但是增量索引（delta indexing）可以降低所需抓取的文档数量的 50% 以上，使得整个过程可以在大约 18 小时内重新索引整个语料库。
在索引规模方面取得了一些突破，初始的内容量为 115TB，删除重复内容、使用增量索引后将内容的数量减少到 28TB 左右。
而索引本身只有 25TB，其中不仅包括所有索引(含 ngram) ，还包括所有唯一内容的压缩副本，这也意味着包括内容在内的总索引大小大约只有原始数据大小的四分之一！
参考资料：
https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/
