GitHub痛改代码搜索引擎,18小时给155亿个文档创建索引,背后技术原理已公开

提升50%创建索引速度

萧箫 发自 凹非寺
量子位 | 公众号 QbitAI

还记得GitHub发布的新版代码搜索引擎吗?

经过一番测试优化后,GitHub现在公开了背后的技术原理。

最新版搜索引擎,不仅解决了之前搜代码时“驴唇不对马嘴”的情况,还可以直接用正则表达式搜索;此外也解决了部分项目上传后搜不到等问题……

网友们看完技术原理后感到惊喜:

这真不错!我看到了谷歌代码搜索引擎的影子。

其实我知道,很少有做代码搜索引擎的人愿意去GitHub,但很高兴能看到这一功能将变得更好用。

要知道,此前GitHub的代码搜索引擎,一度被用户吐槽“形同虚设”。

有不少用户直接自己找了更好用的代码搜索引擎,专门搜索想要的代码:

在这种情况下,新版GitHub代码搜索引擎究竟采用了什么技术,做出了哪些改进?

基于Rust语言的搜索引擎

GitHub新版代码搜索引擎名叫Blackbird,它的关键在于重新构建了一个索引。

这里主要实现两类索引,包括正向索引(Forward index)和反向索引(Inverted index)。

简单来说,正向索引指先给数据库中的各种内容编号(ID),然后通过这些内容ID来搜索对应的具体内容:

这种搜索方法虽然比较直观,也容易理解,但搜索量太大了。如果我们只想通过关键字搜索对应内容,就需要用到反向索引。

反向索引即通过内容中关键词,直接搜到对应的内容ID,从而立刻定位到对应的内容。

具体到反向索引实现方法上,GitHub采用了一种名叫ngram索引的方法,可以很方便地查找内容的子字符串。

这种方法怎么理解?

以limits这个字符串为例,如果ngram中的n=3,那么我们就可以将它分为lim、imi、mit、its四个子字符串。

这时候搜索任意一个字符串,都能找到对应的内容ID,从而定位到想要搜索的内容。

但GitHub的程序员们也意识到,这样构建的索引太大了,要真这样搜索的话会导致服务器不够用,因此还需要对这种方法进行优化。

在Hacker News中有一位GitHub程序员对此做出了解释,即采用一种叫做覆盖稀疏ngrams(covering sparse ngrams)的方法生成候选集,并搜索对应内容,其中9代表ch、6代表he、3表示es,以此类推:

以这类方法为基础建立的系统如下:

所以,新版搜索引擎是否真的比之前更好用了?

测试版体验如何?

目前GitHub中有大约4500万个存储库、115TB代码和155亿个文档。

据GitHub官方表示,原本在改进之前,处理155亿个文档需要大约36个小时。

然而在重写代码之后,需要抓取的文档数量降低了50%以上,因此只需要18个小时左右就可以重新给整个语料库创建索引。

除此之外,需要搜索的内容量也降低了不少。

原本需要搜索的内容在115TB左右,现在将重复内容和数据删除之后,包括索引和内容压缩副本加起来只有25TB大小,缩减到之前的25%左右。

目前测试版依旧在开放申请中,有不少GitHub用户已经试用了一波。

虽然有不少用户对新搜索引擎测试版反响不错,但也有人提出了一些建议。

例如目前这个代码搜索引擎还没办法过滤fork项目,有时候用代码搜索引擎,搜出来全是同一个项目。

对此GitHub程序员也给出了反馈,表示他们之前一直在调整索引这一块,以后会考虑这样的附加功能。

除此之外,也有用户表示,GitHub新版搜索引擎依旧不好用,它从来不区分符号的定义和使用,有时候搜出来的结果,往往需要往后翻5页左右,才能找到想要的结果。

对此,还有网友推荐了自己常用的代码搜索引擎,如Sourcegraph。

你试用过GitHub的新代码搜索引擎了吗?或是还有什么其他好工具推荐?

新版代码搜索引擎申请试用:
https://github.com/features/code-search

参考链接:
[1]https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/
[2]https://news.ycombinator.com/item?id=34680903

版权所有,未经授权不得以任何形式转载及使用,违者必究。