江苏龙网

  1. 主页 > 生活百科 > >

放弃ElasticSearch，GitHub从零打造搜索引擎！2亿代码仓库怎么搜？

Github

目前GitHub新版搜索引擎已经处于测试阶段，只需18小时即可建完4500万个代码库的索引 。2021年12月，GitHub发布了一次技术预览（technology preview），针对GitHub代码搜索「啥也搜不出来」的问题进行了一次全面优化 。
【放弃ElasticSearch，GitHub从零打造搜索引擎！2亿代码仓库怎么搜？】去年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的代码进行匹配需要多长时间 。
 

放弃ElasticSearch，GitHub从零打造搜索引擎！2亿代码仓库怎么搜？

文章插图
 
在一台配备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 上实际上有相当多的重复内容，所以研究人员提出下面两个方法建立索引 。


推荐阅读


上一篇：没有了

下一篇：2023年十佳 Linux 服务器发行版