放棄ElasticSearch，GitHub從零打造搜尋引擎！ 2億代碼倉庫怎麼搜？

2021年12月，GitHub發布了一次技術預覽（technology preview），針對GitHub程式碼搜尋「啥也搜不出來」的問題進行了一次全面優化。

去年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的程式碼進行比對需要多長時間。

在配備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 上實際上有相當多的重複內容，所以研究人員提出下面兩個方法建立索引。

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

2. 將索引建模為樹，並使用差分編碼（delta encoding）來減少crawling的數量並優化索引中的元數據，其中元資料包括文件出現的位置清單（哪個path、分支和程式碼庫）以及關於這些物件的資訊（程式碼庫名稱、所有者、可見性等）。對於一些熱門倉庫來說，元資料量可能會相當大。

GitHub也設計了一個系統，使得查詢結果與提交後的程式碼保持一致。

如果使用者在團隊成員推送程式碼時搜尋程式碼庫，那麼在系統完全處理完新提交的文檔之前，搜尋結果中不應該包含這些文檔，Blackbird將commit查詢一致性作為其設計的核心部分。

Blackbird

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

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

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

此系統的關鍵特性是對初始ingest順序的最佳化以充分利用增量編碼。

GitHub使用了一種全新的機率資料結構來表示程式碼庫的相似性，並且透過從程式碼庫相似性圖的一個最小生成樹的水平順序遍歷中計算得到ingest的順序。

基於最佳化後的ingest順序，delta 樹的建置過程就是將每個程式碼庫與其父程式碼庫進行差分，這也意味著該系統只需要抓取目前程式碼庫特有的blobs，爬取包含從Git 取得blob 內容，分析後提取符號，以及建立將作為索引輸入的文件。

然後將這些檔案發佈到另一個Kafka主題中，也是在shards之間將資料分割的地方。每個shards使用主題中的一個Kafka分區。

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

然後，indexer shards找到這些文件並建立索引：tokenizing內容、符號和path以建構ngram indices和其他有用的indices(語言、擁有者、程式碼庫等) ，並將結果刷新到磁碟上。

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

query的生命週期

有了索引之後，透過系統追蹤query就變得簡單了，每個query都是一個正規表示式，可以寫作「 /arguments?/ org:rails lang:Ruby”，即尋找一個由Rails組織用Ruby語言編寫的程式碼。

在GitHub.com 和shards之間還有一個服務，負責協調接收用戶query，並將請求分散到搜尋叢集中的每個主機上，最後使用Redis 來管理磁碟空間（quotas）和快取一些存取控制資料。

前端接受一個使用者查詢並將其傳遞給黑鳥，然後將query解析為一個抽象語法樹，將其重寫為規範的語言ID，並在額外的子句上標記權限和範圍。

下一步將發送n 個並發請求: 向搜尋叢集中的每個shard發送一個，系統中設定的sharding策略就是向叢集中的每個shard發送查詢請求。

然後，在每個單獨的shard上對查詢進行一些轉換以便在索引中找到資訊。

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

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

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

總結

完整的系統架構介紹完以後，可以重新來檢視一下問題的規模了。

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

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

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

以上是放棄ElasticSearch，GitHub從零打造搜尋引擎！ 2億代碼倉庫怎麼搜？的詳細內容。更多資訊請關注PHP中文網其他相關文章！