原文地址：https://substack.com/@engineerscodex/p-163255622

最近達到了三億美元 ARR 的 AI 集成開發環境（IDE）—— 備受歡迎的 Cursor，是使用 Merkle 樹來快速索引代碼的。接下來，我們要看看這種方法具體如何實現。

什麼是 Merkle 樹

Merkle 樹創建了一個層級結構：每個葉節點標記有數據塊的加密哈希值，每個非葉節點標記有其子節點標籤的加密哈希值；通過比較哈希值可以高效檢測任何層級的變化。

將它們視為數據的指紋系統：

1. 每段數據（如文件）獲得唯一的指紋（哈希值）
2. 成對的指紋被組合並給予新的指紋
3. 這一過程持續進行至得到一個主指紋（根哈希）

根哈希彙總了包含在各個部分中的所有數據，作為對整個數據集的加密承諾。這種方法的優點是，任何單個數據發生的變化，都將改變其上方的所有指紋，最終改變根哈希。

Cursor 如何使用 Merkle 樹進行代碼庫索引

根據 Cursor 創始人的帖子和安全文檔，Cursor 將 Merkle 樹作為其代碼庫索引功能的核心組件。以下是其工作原理：

步驟 1：代碼分塊和處理

進行處理前，Cursor 先在本地對代碼庫文件分塊，將代碼分割成語義上有意義的片段。

步驟 2：Merkle 樹構建和同步

啓用代碼庫索引時，Cursor 會掃描在編輯器中打開的文件夾，計算所有有效文件哈希值的 Merkle 樹並將其與 Cursor 的服務器同步（這一步在 Cursor 安全文檔中有展開描述）。

步驟 3：生成嵌入向量

將代碼塊發送到 Cursor 服務器後，使用 OpenAI 的嵌入 API 或自定義嵌入模型創建嵌入向量。這些向量表示捕捉了代碼塊的語義含義。

步驟 4：存儲和索引

嵌入向量及元數據（如起始/結束行號和文件路徑）存儲在遠程向量數據庫（Turbopuffer）。為了保持隱私、同時仍能進行基於路徑的過濾，Cursor 為每個向量存儲一個混淆後的相對文件路徑。據 Cursor 創始人所説，請求結束後，代碼就不再存儲在 Cursor 的數據庫中。

步驟 5：使用 Merkle 樹進行定期更新

每十分鐘，Cursor 會檢查哈希值不匹配的情況，使用 Merkle 樹識別哪些文件發生了變化。Cursor 安全文檔中提到，只需上傳已更改的文件、大大減少帶寬使用，是 Merkle 樹結構最具價值的地方：實現高效的增量更新。

代碼分塊策略

代碼庫索引的有效性很大程度上取決於代碼如何分塊。詳細的分塊方法可以參考這篇「構建類似 Cursor 的代碼庫功能」博客：

簡單的方法按字符、單詞或行分割代碼，但它們往往會錯過語義邊界，導致嵌入質量降低。

• 可以基於固定的標記計數分割代碼，但這樣可能在中途切斷函數或類等代碼塊。
• 更有效的方法是使用理解代碼結構的智能分割器，例如使用高級分隔符（如類和函數定義）在適當語義邊界處分割的遞歸文本分割器。
• 還有一個優雅的解決方案：基於代碼的抽象語法樹（AST）結構來分割代碼。通過深度優先遍歷 AST，它將代碼分割成適合標記限制的子樹。為避免創建過多小塊，只要保持在標記限制之內，就會將兄弟節點合併為更大的塊。可以使用 tree-sitter 等工具進行 AST 解析，支持多種編程語言。

嵌入向量在推理時的應用

Cursor 如何創建和存儲代碼嵌入後，它們實際上是如何使用的？下面就將解釋這些嵌入在正常使用時的實際應用。

語義搜索和上下文搜索

使用 Cursor 的 AI 功能（如使用 @Codebase 或 ⌘ Enter 提問關於代碼庫的問題）時，會發生以下過程：

1. 查詢嵌入：Cursor 為問題或正在處理的代碼上下文計算一個嵌入向量。
2. 向量相似度搜索：這個查詢嵌入被髮送到 Turbopuffer（Cursor 的向量數據庫），它執行最近鄰搜索，找到語義上與該查詢相似的代碼塊。
3. 本地文件訪問：Cursor 客户端接收結果，其中包括混淆的文件路徑和最相關代碼塊的行範圍。實際的代碼內容仍然在用户的機器上，並在本地檢索。
4. 上下文組裝：客户端從本地文件中讀取這些相關的代碼塊，將它們作為上下文發送到服務器，供 LLM 與所給問題一起處理。
5. 知情響應：LLM 現在擁有來自你代碼庫的必要上下文，可以對你的問題提供更明智、更相關的迴應，或生成適當的代碼補全。

這種基於嵌入的檢索允許：

1. 上下文代碼生成：在編寫新代碼時，Cursor 可以參考你現有代碼庫中的類似實現，保持一致的模式和風格。
2. 代碼庫問答：你可以提出關於代碼庫的問題，並獲得基於你實際代碼的答案，而非通用回答。
3. 智能代碼補全：代碼補全可以通過了解你項目的特定約定和模式來增強。
4. 智能重構：在重構代碼時，系統可以識別代碼庫中可能需要類似更改的所有相關部分。

Cursor 為什麼使用 Merkle 樹

關於這個問題，許多細節都與安全相關，可以在 Cursor 安全文檔中找到。

1. 高效的增量更新

通過使用 Merkle 樹，Cursor 可以快速識別自上次同步以來哪些文件發生了變化。它只需上傳已修改的特定文件，而不是重新上傳整個代碼庫。這一點對於大型代碼庫尤為重要，因為重新索引所有內容在帶寬和處理時間方面成本太高。

2. 數據完整性驗證

Merkle 樹結構使 Cursor 能夠有效驗證被索引的文件與存儲在服務器上的文件是否匹配。傳輸過程中，利用層級哈希結構，可以輕鬆檢測任何不一致或損壞的數據。

3. 優化緩存

Cursor 將嵌入存儲在以塊的哈希為索引的緩存中，確保第二次索引相同代碼庫會快得多。這對於多個開發者共用代碼庫的團隊非常有利。

4. 保護隱私的索引

為了保護文件路徑中的敏感信息，Cursor 通過按 '/' 和 '.' 字符分割路徑並用存儲在客户端的密鑰加密每個段來實現路徑混淆。這仍會泄露一些關於目錄層級的信息，但至少隱藏了大多數敏感細節。

5. Git 歷史集成

在 Git 倉庫中啓用代碼庫索引時，Cursor 也會索引 Git 歷史。它存儲提交 SHA、父信息和混淆的文件名。為了使同一 Git 倉庫和同一團隊的用户能夠共享數據結構，用於混淆文件名的密鑰是從最近提交內容的哈希中派生的。

握手過程

Merkle 樹實現的一個關鍵，是同步中的握手過程。Cursor 應用程序的日誌顯示，初始化代碼庫索引時，Cursor 創建一個 merkle 客户端並與服務器執行「啓動握手」：將本地計算所得 Merkle 樹的根哈希發送到服務器（如 GitHub Issue #2209 和 Issue #981）。

握手過程使服務器得以確定代碼庫需要同步的部分。根據握手日誌，Cursor 計算代碼庫的初始哈希，並將其發送到服務器進行驗證（如 GitHub Issue #2209）。

技術實現挑戰

Merkle 樹方法有許多優勢，但也面臨實現挑戰。

Cursor 的索引功能經常承受重負荷，導致許多請求失敗，文件需要多次上傳才能完全索引，以至於 repo42.cursor.sh 的流量很容易高於預期。

另一個挑戰與嵌入安全相關。研究表明，某些情況下可以反轉嵌入。雖然當前的攻擊通常依賴於訪問嵌入模型和處理短字符串，但存在這樣一種潛在風險：獲得 Cursor 向量數據庫訪問權的對手可能從存儲的嵌入中提取關於索引代碼庫的信息。

💡 更多資訊，請關注 Bytebase 公號：Bytebase