热点|Hot
15年做不好的代码搜索，基于Rust重写引擎终于搞定：GitHub声称能从此“改变游戏规则”
GitHub宣称，源代码搜索引擎将给业界带来颠覆性变革。
GitHub上可供搜索的代码浩如烟海，全球代码仓库已经超过2亿，并且这些代码不是静态的：它在不断变化，这就给代码搜索引擎带来了相当大的挑战。
上线15年来，GitHub一直努力给大家提供一个好用的代码搜索引擎，但一直不能如愿。这两年，GitHub用Rust从头开始构建了自己的搜索引擎，专门用于代码搜索领域，并且自发布后已经极大地改善了该平台的代码搜索能力。
GitHub从头构建代码搜索引擎的动机
搜索是工程师最常用的功能之一，谷歌内部曾对工程师做一次调研，发现平均每位工程师每天会进行5.3次代码搜索会话（session），执行12个代码搜索请求。
对于GitHub这个用户已经达到一亿的代码托管平台来说，具备一个性能良好的搜索引擎尤其重要。然而GitHub自身的代码搜索引擎一度被用户吐槽“形同虚设”，连GitHub工程师Timothy Clem自己都吐槽说“用户体验糟糕”。在这种情况下，一些开发者会使用额外的工具查找代码，比如https://grep.app/或https://sourcegraph.com/search。
实际上，GitHub在这十几年中一直在努力改进其搜索引擎，第一版搜索引擎通过将所有公共文档索引到Solr实例中来工作。对于公共存储库，当时看起来“一切都挺好”，但大型私有存储库仍然无法搜索。
到2010年，搜索领域出现了相当大的动荡，Solr作为一个子项目加入了Lucene，而Elasticsearch作为一种在Lucene之上构建和扩展的好方法逐渐兴起。在2013年初，GitHub推出了由Elasticsearch集群支持的全新代码搜索，整合了公共和私有存储库的搜索体验并更新了设计。
“当我们第一次部署Elasticsearch时，花了几个月的时间来索引GitHub上的所有代码，当时大约有800万个存储库，平均每秒能响应5个搜索请求。”
因为运营规模巨大，在发布后的几天或几周内，GitHub就马上经历了第一次代码搜索中断……
再加上代码库的不断增加，“代码搜索是迄今为止我们运营的最大集群，自发布以来，它的规模又增长了20-40倍”，该公司发现现有技术的正常运行已经越来越难以维持，“从Solr到Elasticsearch，我们尝试用各种通用文本搜索产品来支持代码搜索，但效果都不好。除用户体验糟糕之外，托管成本还非常昂贵，而且索引速度也很慢。”
他们意识到，代码搜索与一般文本搜索有着很大的区别，毕竟代码是写给机器来理解的，需要利用代码之间的结构和相关性，并且还需要支持正则表达式进行搜索。
“归根结底，现成的东西都不能满足我们的需求，所以我们放弃了开源方案，从头开始构建了搜索引擎。”
基于Rust语言的搜索引擎
从2020年开始，GitHub开始全力以赴构建自定义搜索引擎。这款代码搜索引擎被命名为Blackbird，用Rust编写，它创建并增量维护一个由Git blob对象ID分片的代码搜索索引。增量的形式能节省大量存储空间，并保证了跨分片的均匀负载分布。同时支持对文档内容进行正则表达式搜索，还可以捕获额外的元数据，例如它还维护符号定义的索引。最终Blackbird满足了大家的性能目标：速度非常快，索引也非常紧凑，重量约为（去重）语料库大小的1/3。
本周一，Clem发布了一篇博文，讲述了Blackbird的工作原理，深入探讨了这个可对四分之一代码仓库进行搜索的新技术。
Blackbird目前可对近4500万个GitHub代码仓库进行访问，涵盖的代码总体量达115 TB、涉及155亿份文档。要在这么多行代码之间切换，单靠grep（类Unix系统上用于搜索文本数据的常用命令行工具）显然是远远不够的。
Clem解释道，在8核英特尔CPU上，通过ripgrep对内存内的13 GB文件执行详尽的正则表达式查询大约需要2.769秒，相当于0.6 GB/秒/核心。
“我们很快意识到，面对GitHub所拥有的大量数据来说，用grep的办法根本行不通。代码搜索实际运行在每节点64核、总计32节点的集群之上。即使我们设法将115 TB的代码全放进内存并实现了完美并行查询，那2048个CPU也要饱和运行96秒才能完成一次查询！在此期间，只有当前查询可以运行，其他操作全都得排队。”
每秒只能执行0.01次查询，这就直接给grep判了死刑。
于是，GitHub决定将大部分工作预加载至预先计算出的搜索索引当中，这些索引本质上属于键值对映射。如此一来，我们就能使用数字键（而非文本字符串）来搜索编程语言或单词序列等文档特征，从而大大降低对计算资源的需求。
尽管如此，这些索引还是太大、远远超出了内存容量。因此GitHub又为需要访问的各个索引构建了迭代器。根据Clem的介绍，这些迭代器会延迟返回经过排序的文档ID，而各ID所代表的正是关联文档的级别和满足的查询条件。
为了保持搜索索引的可管理性，GitHub采取分片方法——使用Git的内容可寻址哈希schema与增量编码将数据拆分成多个部分，借此存储数据差异（增量）以减少需要抓取的数据和元数据。考虑到GitHub上存放着大量冗余数据（例如不同fork），这套方案确实效果拔群，一举通过重复数据删除技术将115 TB数据缩减至25 TB。
最终系统的运行速度要远超grep，将最初可怜的每秒0.01次查询提升至每秒640次查询。此外，索引的执行速度可达到每秒约12万个文档，所以处理全部155亿个文档需要约36个小时。而由于增量（变更）索引减少了所需抓取的文档数量，重新索引只需要18个小时。
GitHub Code Search目前处于beta测试阶段，感兴趣的朋友可以点击此处前往体验（https://github.com/features/code-search）。
参考链接
https://github.blog/2021-12-15-a-brief-history-of-code-search-at-github
https://www.theregister.com/2023/02/07/github_code_search/?td=rt-3a
https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/