放弃ElasticSearch，GitHub从零打造搜索引擎！2亿代码仓库怎么搜？( 二 ) _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小时内重新索引整个语料库。