2021年12月，GitHub發(fā)布了一次技術(shù)預(yù)覽（technology preview），針對(duì)GitHub代碼搜索「啥也搜不出來(lái)」的問(wèn)題進(jìn)行了一次全面優(yōu)化。

去年11月，在GitHub Universe開(kāi)發(fā)者大會(huì)上，官方再次發(fā)布了公開(kāi)測(cè)試版，主要解決開(kāi)發(fā)者尋找、閱讀和導(dǎo)航代碼的問(wèn)題。

在大會(huì)上，有人問(wèn)了一個(gè)重要的問(wèn)題，「代碼搜索」改進(jìn)背后的原理到底是什么？

最近，GitHub發(fā)布了一篇博客，詳細(xì)解釋了新模型背后的技術(shù)原理和系統(tǒng)架構(gòu)。

從零打造GitHub搜索引擎

簡(jiǎn)單來(lái)說(shuō)，新搜索引擎的背后就是研究人員用Rust重新編寫(xiě)的一個(gè)輪子，專門(mén)針對(duì)代碼搜索進(jìn)行優(yōu)化，代號(hào)黑鳥(niǎo)（Blackbird）。

乍一看，從零開(kāi)始構(gòu)建搜索引擎似乎是一個(gè)令人費(fèi)解的決定：為什么要從頭再來(lái)？現(xiàn)有的開(kāi)源解決方案不是已經(jīng)很多了嗎？為什么還要再浪費(fèi)精力造一個(gè)新的東西？

實(shí)際上GitHub一直在嘗試使用現(xiàn)有的解決方案來(lái)解決搜索問(wèn)題，但不巧的是，用于通用文本搜索的產(chǎn)品很難適配到「代碼」搜索上。由于索引速度太慢，導(dǎo)致用戶體驗(yàn)很差，并且所需的服務(wù)器數(shù)量很大，運(yùn)行成本也過(guò)高。

雖然有一些較新的、專門(mén)適配于代碼搜索的開(kāi)源項(xiàng)目，但它們?nèi)匀徊贿m合 GitHub這么大規(guī)模的代碼庫(kù)。

基于上述觀察，GitHub的開(kāi)發(fā)者設(shè)定的目標(biāo)和結(jié)論主要有三個(gè)：

1. 用戶在搜索過(guò)程中能夠得到全新的體驗(yàn)，可以通過(guò)提出一些代碼上的問(wèn)題來(lái)迭代搜索、瀏覽、導(dǎo)航（navigate）和閱讀代碼來(lái)得到答案。

2. 代碼搜索與通用文本搜索之間有著許多不同之處。

開(kāi)發(fā)者編寫(xiě)代碼是為了讓機(jī)器理解，所以代碼搜索的過(guò)程應(yīng)該利用上代碼的結(jié)構(gòu)和相關(guān)性；并且用戶可能會(huì)搜索標(biāo)點(diǎn)符號(hào)（例如，句號(hào)、開(kāi)括號(hào)等代碼中的操作符）；不要對(duì)代碼中的詞做詞干分析（stemming）；不要從query中刪除停止詞；或者使用正則表達(dá)式進(jìn)行搜索。

3. GitHub 的規(guī)模確實(shí)是一個(gè)獨(dú)特的挑戰(zhàn)。

舊版本的搜索引擎使用的是Elasticsearch，第一次部署的時(shí)候花了幾個(gè)月的時(shí)間來(lái)索引GitHub上的所有代碼(當(dāng)時(shí)大約有800萬(wàn)個(gè)代碼庫(kù))，但現(xiàn)在代碼倉(cāng)庫(kù)數(shù)量已經(jīng)超過(guò)了2億，而且這些代碼還不是靜態(tài)的：開(kāi)發(fā)者不斷提交，代碼也在不斷變化，對(duì)于構(gòu)建搜索引擎來(lái)說(shuō)非常具有挑戰(zhàn)性。

目前在測(cè)試版中，用戶可以搜索大約4500萬(wàn)個(gè)代碼庫(kù)，包含115TB的代碼和155億個(gè)文檔。

綜上所述，現(xiàn)成的東西滿足不了需求，所以，從零開(kāi)始再造一個(gè)。

試試Grep？

在搜索的時(shí)候，一個(gè)常用的工具就是「grep」，通過(guò)輸入表達(dá)式，就能在文本中進(jìn)行匹配，所以為什么不干脆用grep蠻力解決搜索問(wèn)題？

為了回答這個(gè)問(wèn)題，可以先計(jì)算一下用ripgrep對(duì)115TB的代碼進(jìn)行匹配需要多長(zhǎng)時(shí)間。

在一臺(tái)配備8核 Intel CPU 的機(jī)器上，ripgrep 可以在2.769秒內(nèi)(約0.6 GB/sec/core)對(duì)緩存在內(nèi)存中的13 GB 文件運(yùn)行正則表達(dá)式查詢。

簡(jiǎn)單的計(jì)算后就能發(fā)現(xiàn)，對(duì)于當(dāng)下的海量數(shù)據(jù)來(lái)說(shuō)，該方法是行不通的：假設(shè)代碼搜索程序運(yùn)行在一個(gè)擁有32臺(tái)服務(wù)器的集群上，每臺(tái)機(jī)器有64個(gè)核心，即使把115TB的代碼全放到內(nèi)存里，并且一切運(yùn)行順利，2,048個(gè) CPU 核大概需要96秒跑完「一個(gè)」query，而且只能是一個(gè)，其他用戶得排隊(duì)，也就是說(shuō)只有QPS是0.01的話才能用grep

所以蠻力走不通，只能先建一個(gè)索引。

搜索索引（serach index）

只有以索引的形式預(yù)先計(jì)算好相關(guān)信息后，才能讓搜索引擎在查詢時(shí)快速響應(yīng)，簡(jiǎn)單來(lái)說(shuō)，索引就是一個(gè)key-value映射，在倒排索引（inverted index）的情況下，key就是一個(gè)關(guān)鍵詞，value就是出現(xiàn)該詞的有序文檔ID列表。

在代碼搜索任務(wù)中，研究人員用到了一種特殊類型的倒排索引，即ngram索引。

一個(gè) ngram 是長(zhǎng)度為 n 的字符序列，例如 n = 3（trigams）意為key的最大長(zhǎng)度只能是3，對(duì)于較長(zhǎng)的key來(lái)說(shuō)，就需要按照長(zhǎng)度3進(jìn)行切割，比如limits就被分為lim, imi, mit和its

執(zhí)行搜索時(shí)，綜合多個(gè)key的查詢結(jié)果，合并后得到該字符串所出現(xiàn)的文檔列表

下一個(gè)問(wèn)題是如何在相對(duì)合理的時(shí)間內(nèi)完成索引的構(gòu)建。

研究人員觀察到：Git 使用內(nèi)容尋址散列，以及 GitHub 上實(shí)際上有相當(dāng)多的重復(fù)內(nèi)容，所以研究人員提出下面兩個(gè)方法建立索引。

1. shard by Git blob object ID 提供了一種在 shards 之間均勻分布文檔的好方法，并且可以避免重復(fù)，同時(shí)能夠根據(jù)需要隨時(shí)擴(kuò)展shards的數(shù)量。

2. 將索引建模為樹(shù)，并使用差分編碼（delta encoding）來(lái)減少crawling的數(shù)量并優(yōu)化索引中的元數(shù)據(jù)，其中元數(shù)據(jù)包括文檔出現(xiàn)的位置列表（哪個(gè)path、分支和代碼庫(kù)）以及關(guān)于這些對(duì)象的信息（代碼庫(kù)名稱、所有者、可見(jiàn)性等）。對(duì)于一些熱門(mén)倉(cāng)庫(kù)來(lái)說(shuō)，元數(shù)據(jù)量可能會(huì)相當(dāng)大。

GitHub還設(shè)計(jì)了一個(gè)系統(tǒng)，使得查詢結(jié)果與提交后的代碼保持一致。

如果用戶在團(tuán)隊(duì)成員推送代碼時(shí)搜索代碼庫(kù)，那么在系統(tǒng)完全處理完新提交的文檔之前，搜索結(jié)果中不應(yīng)該包含這些文檔，Blackbird將commit查詢一致性作為其設(shè)計(jì)的核心部分。

Blackbird

下面是Blackbird搜索引擎的架構(gòu)圖。

首先，Kafka會(huì)提供events來(lái)指定索引的內(nèi)容，然后就會(huì)有大量的爬蟲(chóng)（crawler）程序與Git進(jìn)行交互，其中還有一個(gè)從代碼中提取符號(hào)的服務(wù)；再次使用Kafka對(duì)每個(gè)shard進(jìn)行索引，獲取目標(biāo)文檔。

雖然該系統(tǒng)只是響應(yīng)像「git push」來(lái)抓取更改內(nèi)容等類似的事件，但在首次ingest所有代碼庫(kù)時(shí)還需要做一些額外的工作。

該系統(tǒng)的一個(gè)關(guān)鍵特性就是對(duì)初始ingest順序的優(yōu)化以充分利用增量編碼。

GitHub使用了一種全新的概率數(shù)據(jù)結(jié)構(gòu)來(lái)表示代碼庫(kù)的相似性，并且通過(guò)從代碼庫(kù)相似性圖的一個(gè)最小生成樹(shù)的水平順序遍歷中計(jì)算得到ingest的順序。

基于優(yōu)化后的ingest順序，delta 樹(shù)的構(gòu)建過(guò)程就是將每個(gè)代碼庫(kù)與其父代碼庫(kù)進(jìn)行差分，這也意味著該系統(tǒng)只需要抓取當(dāng)前代碼庫(kù)所特有的 blobs，爬取包括從 Git 獲取 blob 內(nèi)容，分析后提取符號(hào)，以及創(chuàng)建將作為索引輸入的文檔。

然后將這些文件發(fā)布到另一個(gè)Kafka主題中，也是在shards之間將數(shù)據(jù)分區(qū)的地方。每個(gè)shards使用主題中的一個(gè)Kafka分區(qū)。

使用Kafka可以將索引與crawl解耦，并且Kafka中對(duì)消息的排序也可以也可以使得查詢結(jié)果一致。

然后，indexer shards找到這些文檔并構(gòu)建索引：tokenizing內(nèi)容、符號(hào)和path以構(gòu)造 ngram indices和其他有用的indices(語(yǔ)言、所有者、代碼庫(kù)等) ，并將結(jié)果刷新到磁盤(pán)上。

最后，對(duì)shards進(jìn)行壓縮（compaction），將較小的索引折疊成較大的索引，這樣查詢起來(lái)更有效，移動(dòng)起來(lái)也更容易。

query的生命周期

有了索引之后，通過(guò)系統(tǒng)跟蹤query就變得簡(jiǎn)單了，每個(gè)query都是一個(gè)正則表達(dá)式，可以寫(xiě)作「/arguments?/ org:rails lang:Ruby」，即查找一個(gè)由Rails組織用Ruby語(yǔ)言編寫(xiě)的代碼。

在 GitHub.com 和shards之間還有一個(gè)服務(wù)，負(fù)責(zé)協(xié)調(diào)接收用戶query，并將請(qǐng)求分散到搜索集群中的每個(gè)主機(jī)上，最后使用 Redis 來(lái)管理磁盤(pán)空間（quotas）和緩存一些訪問(wèn)控制數(shù)據(jù)。

前端接受一個(gè)用戶查詢并將其傳遞給黑鳥(niǎo)，然后將query解析為一個(gè)抽象語(yǔ)法樹(shù)，將其重寫(xiě)為規(guī)范的語(yǔ)言 ID，并在額外的子句上標(biāo)記權(quán)限和范圍。

下一步將發(fā)送 n 個(gè)并發(fā)請(qǐng)求: 向搜索集群中的每個(gè)shard發(fā)送一個(gè)，系統(tǒng)中設(shè)定的sharding策略就是向集群中的每個(gè)shard發(fā)送查詢請(qǐng)求。

然后，在每個(gè)單獨(dú)的shard上對(duì)查詢進(jìn)行一些轉(zhuǎn)換以便在索引中查找信息。

最后聚合所有shard返回的結(jié)果，按分?jǐn)?shù)重新排序，篩選(再次檢查權(quán)限) ，并返回 top 100，然后GitHub.com 的前端進(jìn)行語(yǔ)法突顯、術(shù)語(yǔ)高亮、分頁(yè)，最后我們才能將結(jié)果呈現(xiàn)給頁(yè)面。

實(shí)際使用中，單個(gè)shard的p99響應(yīng)時(shí)間大約是100ms，但是由于聚合response、檢查權(quán)限以及語(yǔ)法突顯等原因，總的響應(yīng)時(shí)間要長(zhǎng)一些。

一個(gè)query在索引服務(wù)器上占用一個(gè) CPU 核心100毫秒，因此64個(gè)核心主機(jī)的上限大約是每秒640個(gè)查詢。與 grep 方法(0.01 QPS)相比，這種方法可以說(shuō)是相當(dāng)快了。

總結(jié)

完整的系統(tǒng)架構(gòu)介紹完以后，可以重新來(lái)審視一下問(wèn)題的規(guī)模了。

GitHub的ingest pipeline每秒可以發(fā)布大約12萬(wàn)個(gè)文檔，因此全部處理完155億個(gè)文檔需要大約36個(gè)小時(shí)；但是增量索引（delta indexing）可以降低所需抓取的文檔數(shù)量的50%以上，使得整個(gè)過(guò)程可以在大約18小時(shí)內(nèi)重新索引整個(gè)語(yǔ)料庫(kù)。

在索引規(guī)模方面取得了一些突破，初始的內(nèi)容量為115TB，刪除重復(fù)內(nèi)容、使用增量索引后將內(nèi)容的數(shù)量減少到28TB左右。

而索引本身只有25TB，其中不僅包括所有索引(含ngram) ，還包括所有唯一內(nèi)容的壓縮副本，這也意味著包括內(nèi)容在內(nèi)的總索引大小大約只有原始數(shù)據(jù)大小的四分之一！