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

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

在大會上，有人問了一個重要的問題，「代碼搜索」改進背后的原理到底是什么？

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

從零打造GitHub搜索引擎

簡單來說，新搜索引擎的背后就是研究人員用Rust重新編寫的一個輪子，專門針對代碼搜索進行優(yōu)化，代號黑鳥（Blackbird）。

乍一看，從零開始構建搜索引擎似乎是一個令人費解的決定：為什么要從頭再來？現有的開源解決方案不是已經很多了嗎？為什么還要再浪費精力造一個新的東西？

實際上GitHub一直在嘗試使用現有的解決方案來解決搜索問題，但不巧的是，用于通用文本搜索的產品很難適配到「代碼」搜索上。由于索引速度太慢，導致用戶體驗很差，并且所需的服務器數量很大，運行成本也過高。

雖然有一些較新的、專門適配于代碼搜索的開源項目，但它們仍然不適合 GitHub這么大規(guī)模的代碼庫。

基于上述觀察，GitHub的開發(fā)者設定的目標和結論主要有三個：

1. 用戶在搜索過程中能夠得到全新的體驗，可以通過提出一些代碼上的問題來迭代搜索、瀏覽、導航（navigate）和閱讀代碼來得到答案。

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

開發(fā)者編寫代碼是為了讓機器理解，所以代碼搜索的過程應該利用上代碼的結構和相關性；并且用戶可能會搜索標點符號（例如，句號、開括號等代碼中的操作符）；不要對代碼中的詞做詞干分析（stemming）；不要從query中刪除停止詞；或者使用正則表達式進行搜索。

3. GitHub 的規(guī)模確實是一個獨特的挑戰(zhàn)。

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

目前在測試版中，用戶可以搜索大約4500萬個代碼庫，包含115TB的代碼和155億個文檔。

綜上所述，現成的東西滿足不了需求，所以，從零開始再造一個。

試試Grep？

在搜索的時候，一個常用的工具就是「grep」，通過輸入表達式，就能在文本中進行匹配，所以為什么不干脆用grep蠻力解決搜索問題？

為了回答這個問題，可以先計算一下用ripgrep對115TB的代碼進行匹配需要多長時間。

在一臺配備8核 Intel CPU 的機器上，ripgrep 可以在2.769秒內(約0.6 GB/sec/core)對緩存在內存中的13 GB 文件運行正則表達式查詢。

簡單的計算后就能發(fā)現，對于當下的海量數據來說，該方法是行不通的：假設代碼搜索程序運行在一個擁有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

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

下一個問題是如何在相對合理的時間內完成索引的構建。

研究人員觀察到：Git 使用內容尋址散列，以及 GitHub 上實際上有相當多的重復內容，所以研究人員提出下面兩個方法建立索引。

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

2. 將索引建模為樹，并使用差分編碼（delta encoding）來減少crawling的數量并優(yōu)化索引中的元數據，其中元數據包括文檔出現的位置列表（哪個path、分支和代碼庫）以及關于這些對象的信息（代碼庫名稱、所有者、可見性等）。對于一些熱門倉庫來說，元數據量可能會相當大。

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

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

Blackbird

下面是Blackbird搜索引擎的架構圖。

首先，Kafka會提供events來指定索引的內容，然后就會有大量的爬蟲（crawler）程序與Git進行交互，其中還有一個從代碼中提取符號的服務；再次使用Kafka對每個shard進行索引，獲取目標文檔。

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

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

GitHub使用了一種全新的概率數據結構來表示代碼庫的相似性，并且通過從代碼庫相似性圖的一個最小生成樹的水平順序遍歷中計算得到ingest的順序。

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

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

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

然后，indexer shards找到這些文檔并構建索引：tokenizing內容、符號和path以構造 ngram indices和其他有用的indices(語言、所有者、代碼庫等) ，并將結果刷新到磁盤上。

最后，對shards進行壓縮（compaction），將較小的索引折疊成較大的索引，這樣查詢起來更有效，移動起來也更容易。

query的生命周期

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

在 GitHub.com 和shards之間還有一個服務，負責協調接收用戶query，并將請求分散到搜索集群中的每個主機上，最后使用 Redis 來管理磁盤空間（quotas）和緩存一些訪問控制數據。

前端接受一個用戶查詢并將其傳遞給黑鳥，然后將query解析為一個抽象語法樹，將其重寫為規(guī)范的語言 ID，并在額外的子句上標記權限和范圍。

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

然后，在每個單獨的shard上對查詢進行一些轉換以便在索引中查找信息。

最后聚合所有shard返回的結果，按分數重新排序，篩選(再次檢查權限) ，并返回 top 100，然后GitHub.com 的前端進行語法突顯、術語高亮、分頁，最后我們才能將結果呈現給頁面。

實際使用中，單個shard的p99響應時間大約是100ms，但是由于聚合response、檢查權限以及語法突顯等原因，總的響應時間要長一些。

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

總結

完整的系統(tǒng)架構介紹完以后，可以重新來審視一下問題的規(guī)模了。

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

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

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