当前位置: 首页 > 科技观察

放弃ElasticSearch,GitHub从零开始搭建搜索引擎!2亿代码仓库如何搜索?

时间:2023-03-15 23:39:41 科技观察

2021年12月,GitHub发布技术预览(technologypreview),针对GitHub代码搜索“找不到任何东西”的问题进行了全面优化。去年11月,在GitHubUniverse开发者大会上,再次正式发布公测版,主要解决开发者查找、阅读和导航代码的问题。大会上,有人问了一个重要的问题,“代码搜索”改进背后的原理是什么?近日,GitHub发布了一篇博客,详细解释了新模式背后的技术原理和系统架构。从头开始构建GitHub搜索引擎简单来说,新搜索引擎的背后是一个由研究人员用Rust重写的轮子,针对代码搜索进行了优化,代号为黑鸟(Blackbird)。乍一看,从头开始构建搜索引擎似乎是一个令人费解的决定:为什么要从头开始?不是已经有很多开源解决方案了吗?为什么浪费能源建造一个新的?事实上,GitHub一直在尝试使用现有的解决方案来解决搜索问题,但遗憾的是,一般文本搜索的产品很难适应“代码”搜索。由于索引速度慢,用户体验很差,而且所需的服务器数量运行成本高得令人望而却步。虽然有一些较新的开源项目专门适配代码搜索,但仍然不适合像GitHub这样庞大的代码库。基于以上观察,GitHub开发者设定的主要目标和结论有以下三个:1.用户在搜索过程中可以获得全新的体验,可以迭代搜索、浏览、导航(navigate)和阅读代码来获得答案.2.代码搜索和一般的文本搜索有很多区别。开发人员编写代码是为了让机器能够理解,因此代码搜索过程应该利用代码的结构和相关性;用户可以搜索标点符号(例如,句号、左括号等代码中的运算符);对查询中的词进行词干提取;不要从查询中删除停用词;或使用正则表达式进行搜索。3.GitHub的规模确实是一个独特的挑战。老版本的搜索引擎使用的是Elasticsearch,刚部署时用了几个月的时间索引了GitHub上的所有代码(当时大约有800万个代码仓库),而现在代码仓库的数量已经超过20亿,而且代码也不是一成不变的:开发人员在不断地投入,代码也在不断地变化,这对于构建搜索引擎来说是非常具有挑战性的。目前处于测试阶段,用户可以搜索大约4500万个代码存储库,其中包含115TB的代码和155亿份文档。综上所述,现成的东西不能满足需求,所以,从头开始再做一个。试试Grep?搜索时,常用的工具是“grep”。通过输入一个表达式,就可以在文本中进行匹配,那么为什么不简单地使用grep来解决搜索问题的暴力破解呢?要回答这个问题,可以先计算一下用ripgrep匹配115TB的代码需要多长时间。在配备8核IntelCPU的机器上,ripgrep可以在2.769秒(约0.6GB/秒/核心)内对缓存在内存中的13GB文件运行正则表达式查询。经过简单的计算,可以发现这种方法对于目前的海量数据是不可行的:假设代码搜索程序运行在一个有32台服务器的集群上,每台服务器有64个核心,即使115TB的代码都在内存中,一切顺利。2048个CPU核心运行“一个”查询大约需要96秒,而且只能有一个查询。暴力破解是不行的,只能先建立索引。搜索索引(serachindex)只有在以索引的形式预先计算出相关信息后才进行查询时,才能使搜索引擎快速响应。简单的说,索引就是一个key-value的映射。在倒排索引(invertedindex)的情况下,key是一个关键词,value是这个词出现的文档ID的有序列表。在代码搜索任务中,研究人员使用了一种特殊类型的倒排索引,称为ngram索引。ngram是长度为n的字符序列。比如n=3(trigams)表示key的最大长度只能是3,对于更长的key,需要按照3的长度进行裁剪。比如limits分为lim,imi,mit,及其执行搜索,它们将多个键的查询结果组合起来,组合得到该字符串出现的文档列表。接下来的问题就是如何在一个相对合理的时间内完成索引的构建。研究人员观察到Git使用内容可寻址的哈希,而GitHub上实际上有相当多的重复内容,因此研究人员提出了以下两种索引方法。1.ShardbyGitblobobjectID提供了一种很好的方法,可以在分片之间均匀分布文档,避免重复,并可以根据需要随时扩展分片的数量。2.将索引建模为一棵树,并使用差分编码(deltaencoding)来减少爬取次数并优化索引中的元数据,其中元数据包括文档出现位置的列表(哪个路径,分支和代码库)以及有关这些对象的信息(存储库名称、所有者、可见性等)。对于一些流行的存储库,元数据的数量可能非常大。GitHub还设计了一个系统,使查询结果与提交的代码保持一致。如果用户在团队成员推送代码时搜索代码库,则在系统完全处理它们之前,新提交不应包含在搜索结果中。Blackbird将提交查询一致性作为其设计的核心部分。黑鸟下面是黑鸟搜索引擎的架构图。首先,Kafka会提供事件来指定索引的内容,然后会有大量的爬虫(crawler)程序与Git进行交互,还有从代码中提取符号的服务;再次使用Kafka对每个分片进行索引,得到目标文档。虽然系统仅响应“gitpush”之类的事件以获取更改等,但在首次嵌入所有存储库时还有一些额外的工作要做。该系统的一个关键特性是优化初始摄取顺序以充分利用增量编码。GitHub使用一种新的概率数据结构来表示代码库的相似度,摄取顺序是通过对代码库相似度图的最小生成树的水平顺序遍历来计算的。基于优化后的摄取顺序,delta树的构建过程是将每个代码库与其父代码库区分开来,这也意味着系统只需要爬取当前代码库特有的blob,包括从Git中获取blob内容,分析后提取符号,并创建将作为索引输入的文档。然后将这些文件发布到另一个Kafka主题,该主题也是数据在分片之间分区的地方。每个分片在主题中使用一个Kafka分区。使用Kafka可以将索引和爬取解耦,Kafka中对消息的排序也可以让查询结果保持一致。索引器分片然后找到这些文档并构建索引:标记内容、符号和路径以构建ngram索引和其他有用的索引(语言、所有者、代码库等),并将结果刷新到磁盘。最后,分片被压缩,将较小的索引折叠成较大的索引,这些索引查询效率更高且更易于移动。查询的生命周期有了索引之后,通过系统跟踪查询就变得容易了。每个查询都是一个正则表达式,可以写成“/arguments?/org:railslang:Ruby”,即查找由Ruby语言编写的Rails代码组织的查询。GitHub.com和分片之间还有一个服务,负责协调接收用户查询并将请求分发到搜索集群中的每个主机。最后,Redis用于管理磁盘空间(配额)和缓存一些访问控制数据。前端接受用户查询并将其传递给Blackbird,然后Blackbird将查询解析为抽象语法树,将其重写为规范语言ID,并在附加子句上标记权限和范围。下一步是发送n个并发请求:一个到搜索集群中的每个分片,系统中设置的分片策略是向集群中的每个分片发送查询请求。然后,在每个单独的分片上,对查询执行一些转换以在索引中查找信息。最后聚合所有分片返回的结果,按分数重新排序,过滤(再次检查权限),返回top100,然后github.com前端进行语法高亮,术语高亮,分页,最后我们就可以呈现结果了到页面。实际使用中,单个shard的p99响应时间在100ms左右,但由于聚合响应、检查权限、语法高亮等原因,整体响应时间较长。索引服务器上每个CPU内核的查询需要100毫秒,因此64核主机的上限约为每秒640次查询。相对于grep方式(0.01QPS),这种方式可以说是相当快了。总结完完整的系统架构后,我们可以重新审视问题的规模。GitHub的ingestpipeline每秒可以发布大约120,000个文档,因此处理全部155亿个文档大约需要36个小时;但是,增量索引可以将要抓取的文档数量减少50%以上。这使得整个过程能够在大约18小时内重新索引整个语料库。指标规模有所突破。初始内容量为115TB。删除重复内容并使用增量索引后,内容量减少到28TB左右。而索引本身只有25TB,其中不仅包括所有索引(包括ngrams),还包括所有唯一内容的压缩副本,这也意味着包括内容在内的总索引大小仅为原始数据大小的四分之一左右!