代碼搜索引擎：基礎篇

0. 引 入

最近，我們遇到了兩個場景：

1. 負責基礎服務的工程師想下線一個接口但不知道有哪些服務調用

2. 負責 APM 系統的工程師想知道任意 RPC 接口的所有上游調用方

3. 一些上古服務仍然在運行，但沒有接入調用鏈追蹤系統

4. 調用鏈追蹤系統中維護的是「動態依賴關係」，即最近 N 天 (由 retention policy 決定) 捕獲的調用關係

5. 調用鏈追蹤系統中存儲的是經採樣策略過濾後的數據，可能存在漏採的情況

於是我們開始思考另一個方向：通過代碼搜索引擎提取靜態依賴關係。恰好在 2020 Q4 末，我們將內部所有項目倉庫從 Gerrit 遷移到了 Gitlab，爲代碼搜索引擎的落地鋪平了道路。

在下文中，我們將和大家分享代碼搜索引擎的調研報告，期望能幫助讀者瞭解代碼搜索引擎如何工作。報告主要討論以下話題：

• 爲什麼做

• 一般架構

• 設計決定

• 實現挑戰

• 開源項目

1. 爲什麼做

Google 內部曾對工程師做一次 調研，發現平均每位工程師每天會進行 5.3 次代碼搜索會話 (session)，執行 12 個代碼搜索請求；在 Github/Gitlab 等倉庫託管服務中，搜索是工程師最常用的功能之一；在「引入」中，我們也介紹了伴魚搭建代碼搜索引擎的初衷。那麼在業界的實踐中，代碼搜索引擎主要被用來解決哪些問題呢？

常見的代碼搜索場景包括：

• 理解代碼間的依賴關係

• 尋找即將棄用 (deprecated) 接口的引用地點

• 避免重複造輪子

• 分享編碼方案和編碼風格

• 發現低質量的代碼

• 定位安全問題

• …

儘管服務和倉庫不一定是一一映射關係，但如果服務被拆分，通常倉庫也會被拆分；服務拆分後可觀測性 (observability) 會下降，倉庫被拆分後可觀測性也會下降。在倉庫拆分前，搜索代碼只需要執行 grep 命令；倉庫拆分後，工程師連公司內部存在哪些倉庫都無法準確知道，更不用說 clone 到本地進行搜索。因此代碼搜索引擎實際上是一種提高倉庫可觀測性的工具。

2. 一般架構

如上圖所示，代碼搜索引擎通常可以分爲兩個部分：Web Server 和 Index Serer。

Web Server 負責渲染查詢頁面，接收用戶的查詢請求，將查詢調度到合適的 Index Server 中，獲取查詢結果，並返回到前端向用戶展示。Index Server 負責從倉庫託管服務中按給定的策略拉取相關倉庫數據到本地並建立索引。當倉庫數據更新時，需要同步倉庫變動，更新索引，保證數據的最終一致性。當倉庫數量過多，索引體積過大時，Index Server 需要支持橫向擴展，分片管理數據；當請求數量過多時，Web Server 也需要支持橫向擴展。

實踐中，有的項目會將 Web Server 和 Index Server 合而爲一，有的會將 Index Server 的倉庫同步和索引建立進一步拆分成兩個模塊，甚至將倉庫和索引的元數據用關係型數據庫單獨管理，但這一切都能夠以「一般框架」爲起點設計。

3. 設計決定

瞭解了代碼搜索引擎的一般架構後，我們從以下四個角度出發，討論該系統各個模塊的設計決定：

• 查詢語言

• 索引結構

• 數據管理

• 結果排序

如上圖所示，代碼搜索引擎的查詢語言通常由兩部分構成：「修飾詞」和「匹配器」。「修飾詞」用來指定查詢的範圍，如倉庫名稱、文件名稱、編程語言等等。它既用於幫助用戶更精確地描述查詢內容，也能夠爲搜索引擎更高效地執行提供線索。「匹配器」則是對目標代碼特徵的表述，它可以是關鍵詞 (keyword)、子串 (substring)、正則表達式 (regular expression)，也可以是包含編程語言特徵的結構化 (structural) 描述。舉例如下：語句

表示的是：搜索 kubernetes 倉庫 master 分支中，匹配正則表達式 common.*Describe 的源碼。再看看「匹配器」，假設有一個文檔 (document) 內容如下：

func greeting() { fmt.Println("hello world")}

通過關鍵詞匹配，你可以搜索單詞，如 “greeting”，或詞組，如 “hello world”，搜索到該文檔，但無法通過搜索子串，如 “greet” 或 “Print” 達到目的；通過子串匹配，你可以搜索任意子串，如 “greet”、”Print”，當然跨越單詞的子串也沒問題，如 “ello wor”；通過正則表達式，你的描述可以更加靈活，如所有包含 ctx 參數的函數可以搜索 “^func.*ctx”。關鍵詞、子串、正則表達式的表達力依次遞增，但三者都屬於純文本匹配器。如果想基於編程語言的語法結構來搜索，那麼就需要結構化匹配器。例如在 Sourcegraph 中，你可以通過以下匹配器：

switch :[[v]] := :[x].(type) {:[] case nil: :[]}

來匹配 Go 源碼中 type switch 代碼塊中包含 nil case 的情況。

3.2 索引結構

代碼搜索引擎之於通用文本搜索引擎，就如時序數據庫之於關係型數據庫，前者是後者的一個特例。因此驅動代碼搜索引擎的許多索引結構源於通用文本搜索引擎。

如上圖所示，我們大致可以將代碼搜索引擎常用的索引結構分爲兩類：「基於文本」 (text-based) 和「語言感知」 (language-aware)。基於文本的索引結構只對語料做純文本分析，而語言感知的索引結構需要理解編程語言的語法結構，前者適用於所有文本搜索引擎，後者則爲代碼搜索引擎特有。

本節我們首先回顧一下「倒排索引」的基礎知識，隨後依次討論上圖葉子節點中的索引結構。

 3.2.1 倒排索引

文本搜索的實現離不開一個經典的數據結構 — 倒排索引 (Inverted Index)。本節簡單回顧倒排索引的基本結構以及它的一些基本變體。如果你對這個話題有興趣深入瞭解，我推薦弗萊堡大學的 Information Retrieval 課程 (視頻 | 資料)。

給定如下一組文檔 (documents)：

1. He likes to wink, he likes to drink.

2. He likes to drink, and drink, and drink.

3. The thing he likes to drink is ink.

4. He likes to wink and drink pink ink.

其中序號即爲文檔編號。最簡單的倒排索引就是先對其分詞，找出每個單詞對應的文檔列表：

{
  "and": [2, 4],
  "drink": [1, 2, 3, 4],
  "he": [1, 2, 3, 4],
  "ink": [3, 4],
  "is": [3],
  "likes": [1, 2, 3, 4],
  "the": [3],
  "thing": [3],
  "to": [1, 2, 4],
  "wink": [1, 4]
}

在相關書籍中，這個數據結構被稱爲 Posting Lists 或 Postings。爲了算法實現上的高效，每個單詞對應的文檔序號列表通常按順序排列。

有了上述結構，我們就能支持簡單的「關鍵詞搜索」(Keyword Search) 功能。假如用戶想查詢包含單詞 “wink” 的文檔，就找到單詞 “wink” 對應的文檔列表即可。上述結構也能支持「詞組搜索」 (Phrase Search)，比如 “likes to”，就可以分別找到 “likes” 和 “to” 對應的文檔列表，取二者交集。但對於這些篩選出來的文檔，我們還需要再進行一遍確認，因爲 “likes” 和 “to” 出現的位置和順序都無法保證符合要求，比如文檔 “To my mind, I likes the way you achieve this”。

另一種支持的「詞組搜索」 的方法是在 Postings 中加入每個詞語出現的位置信息，如：

{ "drink": { "1": [30], "2": [13, 24, 35], "3": [23], "4": [22] }, // ...}

通常稱這種 Postings 爲 Positional Postings。這時支持「詞組搜索」就是小菜一碟了，典型的空間換時間。

如果用戶記不住完整的單詞和詞組，怎麼辦？這就需要支持一種新的搜索方式 —「子串搜索」(Substring Search)，如搜索 “ink”，要給出 “drink”、”wink” 和 “ink” 的結果並集。顯然，每次遍歷 Postings 中的所有 key 效率不高，尤其是需要做多語言支持的時候，那麼一個常用的技巧就是 q-gram (或 n-gram)。gram 就是若干連續字符的集合，而前面的 q 或 n 表示的是連續的字符個數，2-gram 就是字符的兩兩組合，3-gram (trigram) 就是三個字符的任意組合，依次類推。比如字符串 “freiburg” 包含的所有 3-gram 包括：

$$f, $fr, fre, rei, eib, ibu, bur, urg, rg$, g$$

而 q-gram index 就是把前面的 Postings 中的詞語換成這些 q-gram。那麼查詢子串 “reibur” 就可以轉化爲查詢 rei AND eib AND ibu AND bur。

💡 留個思考：如果想支持模糊檢索該怎麼做呢？

以上是對倒排索引的簡單回顧，接下來我們來討論代碼搜索引擎常用的索引結構。

 3.2.2 Trigram

Russ Cox 在博客 How Google Code Search Worked 中提出用 Trigram 索引來支持代碼搜索，其結構與 3.2.1 節中介紹的 3-gram 完全一致，這裏不再贅述。

❓爲什麼是 3-gram，而不是 2-gram 或 4-gram

In practice, there are too few distinct 2-grams and too many distinct 4-grams, so 3-grams (trigrams) it is. — Russ Cox

3.2.3 Positional Trigram

Positional Trigram 與 Trigram 間的關係就是 Positional Postings 與 Postings 間的關係，基本結構如下：

{ "${trigram}": { "${doc_id}": [1, 3] // positions }}

即在 Trigram Index 的基礎上增加位置信息。

3.2.4 Suffix Array

一個字符串的 Suffix Array 是它所有後綴子串按字典序排列的數組。假設給定一個字符串 “hello world”：

它的所有後綴子串包含：”hello world”、”ello world”、”llo world” 等等，排序後得到：

其中第一列表示後綴子串在原字符串中的位置。拿到上述排序結構後，查詢子串就可以轉化成二分查找問題：以查詢子串 “llo” 爲例，先在上圖中的第二列，即所有後綴子串的第一個字母，以字符 “l” 爲目標執行二分查找，找到一塊區域 (5-7 行)，然後對這個區域繼續嵌套執行二分查找，直到遍歷完目標子串的所有字符爲止。

💡留兩個思考：

1. 如何高效地存儲 Suffix Array 索引？需要存儲所有子串嗎？(答案在 Nelson Elhage 的博客裏)

2. Suffix Array 索引建立的時空複雜度是多少？

 3.2.5 基於文本索引的查詢過程

無論是 Trigram、Positional Trigram 還是 Suffix Array，如果想支持通過正則表達式搜索代碼，都要實現以下流程：

1. 將正則表達式轉化成子串的「與」、「或」組合

2. 將子串的組合查詢轉化成對應的索引查詢 (Trigram, Positional Trigram, Suffix Array) 執行索引查詢，獲取候選文檔列表

3. 對每個候選文檔執行實際的正則表達式，將匹配成功的結果返回

4. 由於第 1 步和第 2 步可能不是等價轉換，因此需要通過第 4 步得到精確的查詢結果。這裏問題的難點在於：如何將正則表達式轉化成子串的「與」、「或」組合。

舉一些簡單的例子：

• /Google.*Search/ → Google AND Search

• (Path|PathFragment).=.*/usr/local → ("Path" OR "PathFragment") AND "/usr/local"

需要關注的是，第 1、2 步的選擇性越大，第 4 步的成本就越小，因此轉化方案的好壞取決於其轉化效率和結果查詢的選擇性。對這個話題感興趣，可以深入瞭解業界的解決方案：

• Google Code Search

• Zoekt

• Livegrep

• Regular Expression Search via Graph Cuts

 3.2.6 Ctags

Ctags 是 unix 或 unix-like 系統中內置的工具，爲源碼倉庫生成「語言對象」 (language objects) 的索引。目前仍在維護的版本是 Universal Ctags，想了解更多細節可以閱讀它的官方文檔。

以我的一個玩具項目「Zhenghe-MD/regexgo」爲例，執行：

$ git clone https://github.com/ZhengHe-MD/regexgo.git$ cd regexgo && ctags */.go

就能在 regexgo 文件夾中看到一個 tags 文件，其內容如下所示：

MatchString nfa.go /^func MatchString(n nfa, word string, options Mat/TestBackTracking nfa_test.go /^func TestBackTracking(t testing.T) {$/TestNFASearch nfa_test.go /^func TestNFASearch(t testing.T) {$/TestToPostfix parser_test.go /^func TestToPostfix(t testing.T) {$/addEpsilonTransition nfa.go /^func addEpsilonTransition(from state, to state) /addTransition nfa.go /^func addTransition(from, to state, symbol byte) {/backtracking nfa.go /^func backtracking(s state, visited map[state]int/const nfa.go /^const ($/import nfa_test.go /^import ($/nfaSearch nfa.go /^func nfaSearch(n *nfa, word string) bool {$/toPostfix parser.go /^func toPostfix(exp string) string {$/

每行數據是一個 (language object, file, regexp matcher) 三元組。Ctags 常常被用於 IDE 實現定義跳轉的功能，它也可以被集成到代碼搜索引擎中，更好地服務於「語言感知」的查詢。Ctags 背後由不同編程語言的解析器 (parser) 驅動，後者的原理則是另一個話題，不在本文中討論。

 3.2.7 LSIF

從 Ctags 的例子中可以看出，Ctags 中記錄的「語言對象」信息量很小，基本上只有函數信息。要支持表達力更強的「語言感知」查詢，其記錄的信息還遠遠不夠。在數據模型和信息量上，LSIF 比 Ctags 走得更遠：

The goal of the LSIF is to support rich code navigation in development tools or Web UI without needing a local copy of the source code. — LSP/LSIF docs

由於 LSIF 的設計目的是支持豐富的代碼跳轉能力，因此它需要記錄包括變量定義、引用，函數的定義、調用及它們之間的關係。LSIF 是將這些實體，及實體之間的關係用圖結構來建模。以下是 Chris Wendt 在 GopherCon 2019 上題爲「LSIF + Go」演講中的其中一張 slide，其中紅框爲圖的點，綠線爲圖的邊。

將這張圖記錄到索引中，就可以在必要的時候按「圖」索驥，支持豐富的「語言感知」查詢。以下是 LSIF 的索引文件數據示例：

//...{"id":6,"type":"vertex","label":"definitionResult"}{"id":7,"type":"edge","label":"next","outV":4,"inV":5}{"id":8,"type":"edge","label":"textDocument/definition","outV":5,"inV":6}{"id":9,"type":"edge","label":"item","outV":6,"inVs":[4],"document":3}{"id":10,"type":"vertex","label":"hoverResult","result":{"contents":[{"language":"go","value":"package \"fmt\""},"Package fmt implements ... \n\n"]}}{"id":11,"type":"edge","label":"textDocument/hover","outV":5,"inV":10}{"id":12,"type":"vertex","label":"range","start":{"line":4,"character":5},"end":{"line":4,"character":12}}{"id":13,"type":"vertex","label":"resultSet"}{"id":14,"type":"vertex","label":"definitionResult"}//...

3.3 數據管理

代碼搜索引擎需要管理兩組數據：倉庫和索引。根據使用場景需要，引擎可以將它們存儲在 HDD 或 SSD 上，並在服務的時候載入必要的部分到內存中。因爲數據模型比較簡單，代碼搜索引擎會直接使用文件系統存儲倉庫和索引。

  3.3.1 數據分片

就如早期的 Slack 可以基於 workspace_id 隔離計算、存儲資源，支持系統橫向擴展，代碼搜索引擎中也存在這樣一個東西，它就是 repo_id。它既可以幫助查詢引擎縮小搜尋範圍，也可以幫助存儲引擎管理倉庫和索引數據。

 3.3.2 倉庫

倉庫通常被託管在雲服務中，如 Github、Gitlab、BitBucket 等等，因此代碼搜索引擎的核心工作之一就是從託管服務中同步倉庫。這裏有兩個小的設計決定：同步內容和同步時機。

同步內容

以 Git 爲例，你可以選擇 clone、shallow clone 或 bare clone。git clone 會拉取倉庫的所有歷史並 checkout 到默認分支 (main/master) 最新的 commit 上；git clone --depth=k 會拉取倉庫最新的 k 個 commit 數據，丟棄之前的歷史；git clone --bare 只拉取倉庫的 .git 文件夾。三者的區別體現在拉取數據的大小和保留的倉庫歷史信息上。

同步時機

如果代碼搜索引擎需要爲之建索引的倉庫數量不多，可以簡單的按用戶對實時性的要求定期全量拉取，如 1 小時、1 天等等；如果需要索引整個 Github 上的大部分，甚至所有開源項目，就需要結合事件回調、動態調整更新頻率等複雜策略控制各個項目的同步時機。必要的時候還需引入關係型數據庫存儲相關元數據。

 3.3.3 索引

大多數代碼搜索引擎的數據管理模塊會以一個索引文件對應一個倉庫，這與上文提到的數據分片策略相關。有些引擎會選擇在索引文件中冗餘一份源碼，使得查詢過程可以完全在索引文件中完成，同時可以將倉庫與索引的管理解耦。其中一個實現上常見的技巧是將每個倉庫的所有源文件按某個固定順序連接 (concatenate) 起來，然後再對整個大文件建立索引：

在絕大多數時候，研發關心的是倉庫的最新版本，因此一個務實主義的做法是隻對最新的版本建立索引。

Indexing every branch of every repository isn’t a pragmatic use of resources for most customers, so this decision balances optimizing the common case (searching all default branches) with space savings (not indexing everything). — Sourcegraph

倉庫發生變化後，數據管理模塊需要將這些變化反饋到索引上。

3.4 結果排序

對於像 Google 這樣的搜索引擎，排序是非常重要的一環，把用戶最想獲取的信息按質量從高到低排序就是它的設計目的之一。實際上排序質量的衡量背後有一系列的理論研究在支撐。然而，目前絕大多數開源代碼搜索引擎並不太關心排序，個人認爲其原因可能在於：

1. 開發者通常能非常精準地在查詢語句中描述自己想要的代碼，甚至做到 100% 的 precision 和 recall

2. 代碼搜索引擎搜索範圍通常爲一個公司或部門內部的所有倉庫，數量不多，結果列表不會很長

一些雲端倉庫託管服務也提供搜索服務，從其用戶使用的角度考慮，支持基於流行度、活躍度、話題的排序就變得相當必要。

4. 實現挑戰

本節介紹搭建一個代碼搜索引擎可能會遇到的問題。這個列表會隨着日後的調研和實踐繼續增補內容。

4.1 Unicode

Zoekt 項目的作者，Google 工程師 Han-Wen 在 Gerrit Summit 2017 上的 分享 中曾經介紹過，在他開發第一版 Zoekt 時，只考慮了源碼中的 ascii 字符，當他期望擴大項目適用範圍，支持 unicode 時，發現自己以前有很多邏輯不再適用。因爲 unicode 的每個字符的長度不定，一些基於字符串字節長度的計算不再成立。如果你的代碼搜索引擎是面向各種語言的，在寫代碼時需要對此格外留意。

4.2 安全問題

對於一個組織內部的代碼搜索引擎來說，最大的風險就是代碼中的敏感信息泄露。開發者可能會無意地將一些 token、祕鑰、郵箱、手機號等等信息放到源碼中。儘管這樣的風險本來也存在，但代碼搜索引擎的存在放大了泄漏風險。

4.3 分頁

假如一個搜索請求命中的文檔很多，出於性能和體驗考慮，用戶在前端更希望支持分頁。代碼搜索引擎支持分頁比在關係型數據庫中支持分頁要難一些，因爲你永遠無法知道一個臨時的查詢會在一個倉庫匹配多少次，你也無法爲此提前建立精確的索引。如果對此感興趣，可以看看 Sourcegraph 如何解決這個問題。

5. 開源項目

本節介紹的項目在時間線上排列如下：

其中 Google Code Search 算是這個領域的開山之作，後續的項目都是 「inspired by Russ Cox’s work」。

5.1 Google Code Search

⚠️ 本節的大部分內容來自於 Russ Cox 的博客 How Google Code Search Worked。

 5.1.1 一點歷史

如果這個世界要求必須有一些工程師來研究代碼搜索工具，那麼十有八九這些工程師來自 Google。2006 年夏天，Russ Cox 來到 Google 實習。當時，Google 內部有一個叫作「gsearch」的項目用於代碼搜索，它的實現可以簡單地理解成分佈式 grep，即啓動多臺機器存儲不同的倉庫集合，每次查詢時將 grep 命令下發到各個機器，每個機器在本地執行 grep 後返回，並將結果彙總。

Russ Cox 的 mentor，Jeff Dean 在他開始實習時說：「如果能做一個支持搜索全世界開源代碼的工具，是不是很酷？」在當年 10 月，這個項目 Google Code Search 終於上線。

 5.1.2 查詢語言

Google Code Search 支持通過正則表達式搜索，Russ Cox 描述這種查詢方式爲「geekily great but a very small niche」。Russ Cox 開源的核心代碼並沒有支持通過「修飾詞」來縮短檢索範圍，而只是提供了類似 grep 的命令行工具。這大概是因爲開源出來的代碼足以展示一個代碼搜索引擎的運行邏輯，剩下的就讓有興趣的開發者自行擴展。

這裏有一個值得一提的小插曲，Russ Cox 在項目的概念驗證階段中發現大部分手頭的正則表達式引擎都不能保證線性時空複雜度，因爲它們使用的是回溯法 (backtracking) 而非有限自動機 (finite automata)。儘管 Google Code Search 使用的正則表達式引擎仍然是 Plan 9 grep 中的實現，若干年後，這個引擎終於被替換成了 RE2。當然，如何實現一個正則表達式是另一個有趣的話題，但不在本文的討論範圍內，有興趣可以先讀一下 Russ Cox 的 正則表達式系列博客。

 5.1.3 索引

Google Code Search 使用的是最基本的 Trigram Index。索引本身並無複雜之處，實際花費 Russ Cox 大量精力的是「從正則表達式到 Trigram 查詢」的轉化上。

 5.1.4 運行

上文介紹過，在 Google Code Search 中 Russ Cox 只提供了本地的可執行命令，供開發者試驗。項目提供的可執行命令包括 cindex、csearch 和 cgrep。cindex 會對所有輸入的源碼文件，建立一個單獨的索引文件，默認存儲在 $HOME/.csearchindex 中。比如：

$ cindex $HOME/src /usr/include

會爲 $HOME/src 和 /usr/include 文件夾下的所有源碼文件建立索引。如果重複執行該命令，會自動增量更新發生變化的部分，多次操作效果冪等。csearch 可以支持用正則表達式在 cindex 已經建立好的索引上檢索代碼。cgrep 則是提供 grep 類似交互風格的 csearch。

 5.1.5 小結

5.2 Hound

兩位在 Etsy 工作的工程師，Kelly Norton 和 Jonathan Klein，基於 Google Code Search 搭建了 Hound 來解決他們在公司內部遇到的代碼搜索需求。

We’ve used many similar tools in the past, and most of them are either too slow, too hard to configure, or require too much software to be installed. Which brings us to… — Hound README.md

Hound 在啓動時需要讀取一個配置文件，描述數據存放的根目錄，以及需要搜索哪些倉庫。一個配置文件的示例如下：

{ "dbpath" : "db", "repos" : { "Hound" : { "url" : "https://github.com/etsy/hound.git" } }}

因此如果你希望它能夠自動發現新的符合要求的倉庫，則需要額外提供「倉庫發現」邏輯。

 5.2.1 存儲

Hound 的所有數據存放在配置文件中制定的 dbpath 目錄下。該目錄下存放兩種文件夾：

• 倉庫文件夾：vcs-${Repo.Url}

• 索引文件夾：idx-${random_hash}

每個倉庫中存放着 git clone 下來的數據；索引文件夾的佈局如下：

idx-10837b48f746028d├── excluded_files.json├── metadata.gob├── raw│ ├── README.md│ ├── go.mod│ └── ...│└── tri

其中 tri 文件就是 Google Code Search 中 cindex 生成的索引文件，而 raw 文件夾下冗餘了一份倉庫中所有被建立索引的源碼文件。

 5.2.2 服務化

Hound 的啓動流程如下圖所示：

Hound 只有一個進程，啓動後它會先觸發首次同步，同時構建索引。不論成功或失敗，一旦所有倉庫都被訪問一次後，就通過 HTTP 服務開放搜索 API，之後每隔 30 秒， Hound 就會啓動一次數據的全量更新。對於少量倉庫的場景，這個策略運行得很完美。

5.3 Livegrep

Livegrep 項目的 README 這麼介紹自己：

Livegrep is a tool, partially inspired by Google Code Search, for interactive regex search of ~gigabyte-scale source repositories.

可以看出，其設計目的是爲了在超大型項目上實現實時搜索，而非我們所面臨的「微倉庫」場景。

 5.3.1 查詢語言

Livegrep 支持「修飾器」+「匹配器」構成的查詢語句，其中「匹配器」兼容 RE2 的正則表達式語法。其搜索主頁提供了一些說明：

 5.3.2 索引

Livegrep 使用 Suffix Array 給倉庫建立索引，它的作者 Nelson Elhage 在博客 Regular Expression Search with Suffix Arrays 中曾提到，在實踐中 Livegrep 需要使用原倉庫語料 (corpus) 3-5 倍的空間建立索引，是典型的空間換時間策略。這也說明獲得它提供的 極致搜索體驗 需要付出代價。

 5.3.3 存儲

Livegrep 爲一個倉庫建立一個索引文件，構建完畢後可以拋開倉庫獨立運行。根據能夠獲取到的信息， Livegrep 主要關注單個倉庫搜索，爲了速度，它會默認將整個索引文件加載進內存，如果內存放不下可以使用 mmap 選項。由於索引體積較大，同時在成百上千個倉庫中搜索並非 Livegrep 所擅長的事情。

 5.3.4 服務化

Livegrep 的架構與代碼搜索引擎的一般架構基本一致，一個進程用於拉取代碼、建立索引、提供查詢 API，一個進程提供搜索頁面和 API 服務。據其文檔所述，要支持倉庫的變更同步，需要啓動額外的進程，如「livegrep-github-reindex」。

5.4 Zoekt

⚠️ 本節大部分內容來自於 Zoekt 項目的設計文檔。

Google 的工程師 Han-Wen 在 2016 年首次發佈了 Zoekt 項目，並在 Gerrit Summit 2016 的演講「Zoekt - Codesearch for Git」中介紹了這個項目。在接下去的一年中，他繼續優化 Zoekt 項目，並在 Gerrit Summit 2017 的演講 「Zoekt, improved - Codesearch, one year later」中介紹了他解決的問題和改進的功能。

 5.4.1 查詢語句

Zoekt 支持「修飾器」+「匹配器」構成的查詢語句，其搜索主頁提供了許多查詢示例和說明，以下是截圖：

 5.4.2 索引和存儲

Zoekt 將每個倉庫的所有源碼文件連接成一個大文件，並基於它構建 Positional Trigram 索引，並將索引數據用 gob 編碼後直接附加在大文件後面：

這個文件的後綴名爲 ${repo}.zoekt。由於 .zoekt 文件同時包含代碼和索引，只要沒有新的代碼更新，Zoekt 可以只靠索引文件來提供搜索服務。

除此之外，Zoekt 還支持通過引入 ctags 優化查詢結構的排序。

 5.4.3 服務化

Zoekt 部署包含兩個模塊：zoekt-indexserver 和 zoekt-webserver。它的架構與代碼搜索引擎的一般架構基本一致。zoekt-indexserver 負責代碼同步和索引維護，它原生繼承了許多代碼託管服務，如 Github、Gitlab、Bitbucket、Gerrit 和 Gitiles，同時還支持配置倉庫過濾器，通過倉庫名稱等特徵來選擇支持的搜索範圍，解決了倉庫發現的問題，這方面比 Hound 要友好很多。默認配置下，zoekt-indexserver 每天拉取一次倉庫數據，重建索引。zoekt-webserver 則負責提供 HTTP 服務和搜索頁面。

5.5 Sourcegraph

實際上 Sourcegraph 是一家公司的名字，同時也是它們的核心代碼搜索產品的名稱。基於其大規模代碼檢索能力，Sourcegraph 還發布了多個產品：

• Code Search：提供海量倉庫搜索功能

• Code Intelligence：提供跨倉庫的類似 IDE 的豐富的雲上代碼訪問、跳轉功能

• Batch Changes：跨倉庫批量修改代碼，推送 PR/MR 並跟蹤合併結果

本節我們主要關注它的 Code Search 產品，下文中如無特殊說明，我們用 Sourcegraph 指代其 Code Search 產品。

 5.5.1 查詢語言

Sourcegraph 支持「設計決定」一節中提到的所有查詢語言，也是當前唯一支持結構化查詢的代碼搜索引擎。想了解它支持的完整語法和使用示例，可以翻閱它的官方文檔。如果你對 Sourcegraph 如何支持結構化查詢有個大致瞭解，可以看看它們的設計文檔 RFC 40，同時也許你會對 comby 感興趣。

 5.5.2 索引

Sourcegraph 實際利用 Zoekt 驅動，因此它使用的自然也是 Positional Trigram 索引。值得一提的是，Sourcegraph 公司的 Code Intelligence 產品還有一個 Precise Code Intelligence 版本，是由 LSIF 索引驅動。

 5.5.3 存儲

Sourcegraph 在隔離代碼和索引上更近了一步。在它的架構中存在一個支持橫向擴展的 gitserver 服務，負責從不同的代碼託管服務中拉取數據。而由 zoekt-indexserver 負責對 gitserver 中的倉庫構建 Positional Trigram 索引。更準確地說，還有一個叫做 repo-updater 的組件負責 gitserver 數據拉取任務的調度，後者將元數據存儲在 Postgres 中，同時向 gitserver 發送相關命令。

由於 Sourcegraph 需要支持爲海量倉庫建立索引，它還基於倉庫活躍度制定了數據同步的退避 (backoff) 策略。舉例如下：如果一個倉庫的最後一個 commit 在 8 小時以前，下一次數據同步就會在 4 小時 (8 小時的 1/2) 後調度，如果屆時仍然沒有數據變動，則再下一次數據同步任務將在 6 小時候被調度。

 5.5.4 服務化

⚠️ 本節內容來自於官方文檔 Sourcegraph architecture overview。

以下是 Sourcegraph 的架構全圖：

代碼同步由 gitserver 和 repo-updater 完成，詳情可查看 Life of a repository；基於文本的代碼搜索由 Zoekt 項目支持，包括 zoekt-indexserver 和 zoekt-webserver。在未建立索引的分支上的查詢由 searcher 完成。syntect-server 負責往搜索結果中添加語法高亮信息，詳情可查看 Life of a search query；precise-code-intel-worker 則負責前面提到的 Precise Code Intelligence。

作爲一個商業化的代碼搜索引擎項目，Sourcegraph 無論在系統設計上還是產品體驗上都更加完善。如果你期望享受極致的使用體驗，且不想花費時間、精力去了解、部署、運維一個代碼搜索引擎，那麼 Sourcegraph 是個很好的選擇。

5.6 項目對比

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/jAoxTlhoqgeT2AXRTSdCxQ