去年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) ，还包括所有唯一内容的压缩副本，这也意味着包括内容在内的总索引大小大约只有原始数据大小的四分之一！
