Meilisearch 透過 Arroy 的過濾磁碟 ANN 擴展搜尋能力

這是系列部落格文章的第 3 部分 最初發佈於我的個人部落格。 從 第 1 部分 和 第 2 部分開始您的旅程。

我們可以將向量儲存在 Arroy 中，並有效率地計算搜尋樹節點，但我們仍然需要一些功能才能在 Meilisearch 中使用。我們的全文搜尋引擎對過濾具有強大的支援；選擇文件的子集是支援的基本功能。例如，我們最大的客戶之一需要能夠過濾超過 1 億個 YouTube 影片元數據及其相關的圖像嵌入，以有效地選擇在特定時間範圍內（例如，單日或單週）發布的影片。這代表了我們旨在透過我們的過濾系統解決的可擴展性和回應性挑戰，使其成為客製化我們開發的完美用例。

Meilisearch 支援您文件中可過濾屬性的以下運算子： <、 <=、 =、 != >= 和 >。在內部，我們大量使用 RoaringBitmaps，它們是經過良好優化的整數集合，支援快速二元運算，例如聯集和交集。當引擎收到具有過濾器的使用者請求時，它首先計算過濾器中文件的子集，該子集將輸入到搜尋演算法中，也就是按品質對文件進行排名的演算法。此子集由 RoaringBitmap 表示。

在 Arroy 之前是如何運作的？

自 2018 年以來，僅對經過濾的文件子集進行排名一直運作良好，但現在我們有了一個新的資料結構可以搜尋，我們需要看看如何實作它。引擎已經支援向量儲存功能數月，但效率不高。我們使用的是記憶體中的 HNSW，並在記憶體中反序列化整個資料結構，搜尋目標向量的最近鄰居，這會傳回一個迭代器。

fn vector_store(db: Database, subset: &RoaringBitmap, target_vec: &[f32]) -> Vec<DocumentID> {
    // This takes a lot of time and memory.
    let hnsw = db.deserialize_hnsw();

    let mut output = Vec::new();
    for (vec_id, vec, dist) in hnsw.nearest_neighbors(target_vec) {
        let doc_id = db.document_associated_to_vec(vec_id).unwrap();
        if !output.contains(&doc_id) {
          output.push(doc_id);
          if output.len() == 20 { break }
        }
    }

    output
}

您可能會想知道為什麼我們要檢索與向量 ID 相關聯的文件 ID。自向量儲存功能開始以來，Meilisearch 支援每個文件的多個向量。這很不幸，因為我們必須查找我們正在迭代的每個向量。我們需要維護此查找表。如果子集夠小，例如 document.user_id = 32，則迭代器可以迭代整個向量資料集。我們希望文件操作是原子且一致的，因此我們必須將 HNSW 儲存在磁碟上，並避免在 LMDB 交易和此向量儲存資料結構之間維護同步。呵！而且該函式庫不支援增量插入。我們每次插入單個向量時都必須從頭開始在記憶體中重建 HNSW。

將 Arroy 整合到 Meilisearch 中

當我們致力於更新 Meilisearch 以包含新的向量儲存 arroy 時，我們首次嘗試了 mob 編程。這是我們同時一起編寫程式碼的地方。聽起來可能會讓我們變慢，但實際上它使我們的工作效率超高！透過在問題出現時立即共同解決，我們將 arroy 安裝到 Meilisearch 的速度遠遠快於我們單獨工作時的速度。

Arroy 的不同之處在於它不會傳回迭代器來傳回搜尋結果。現在，我們的搜尋引擎更智慧，可以找出它需要傳回的確切結果數量，即使在考慮過濾器時也是如此。這種團隊合作改進了我們的搜尋工具，並向我們展示了在面對大型技術挑戰時，協同工作是關鍵。

在 Arroy 中搜尋時進行過濾

您可以在本系列第 1 部分中找到 arroy 內部資料結構的描述。以下是您可以找到的不同類型節點的列表

• 項目節點。使用者提供的原始向量。左側的小點。
• 正常節點，也稱為分割平面。它們表示將項目節點子集一分為二的超平面。
• 後代節點。它們是由您遵循特定正常節點路徑時會找到的項目 ID 組成的樹葉。

典型的搜尋會在與無限距離相關聯的二元堆積中載入所有正常節點。請記住，有很多隨機產生的樹，因此有很多進入點。升序距離對二元堆積進行排序；首先彈出找到的最短節點。

在搜尋演算法中，我們從這個堆積中彈出最近的項目。如果它是正常節點，我們會獲取超平面的左側和右側

• 如果我們再次找到正常節點，我們會將超平面的距離與目標/查詢向量的正負距離相關聯。
• 如果我們找到後代節點，我們不會將它們推送到佇列中，而是直接將它們添加到潛在的輸出列表中，因為它們代表我們找到的最近向量。

您可能已經注意到我要去哪裡了，但這就是奇蹟發生的地方。我們修改了 arroy 以在 RoaringBitmaps 中儲存後代列表，而不是原始整數列表。與原始 Spotify 函式庫相比，這是另一個改進，因為這些列表的權重較小。現在更容易與經過濾的子集進行交集。

但是，始終存在一個問題：向量 ID 不是文件 ID，並且 Meilisearch 在執行過濾器後只知道文件。迭代我之前談到的查找表，使用與經過濾的文件對應的所有向量 ID 來構建最終點陣圖，當許多文件是此子集的一部分時，例如 document.user_id != 32，則效率不高。我不建議在搜尋函式中使用 O(n) 演算法。

使用多個索引進行有效過濾

幸運的是，我們開發了一個有趣的特色功能，但它並非旨在以這種方式在 arroy 中使用：支援單個 LMDB 資料庫中的多個索引。我們最初開發多個索引功能是為了能夠僅開啟單個 LMDB 資料庫來儲存不同的向量類型。是的！在 Meilisearch v1.6 中，您可以描述位於單個索引中的不同嵌入器。您可以使用可以儲存在單個文件中的不同維度和距離函數來識別不同的向量。也可以為與同一嵌入器關聯的單個文件定義多個向量。

索引由 u16 識別。此功能可以欺騙演算法，使其比先前的 HNSW 解決方案更有效。在文件中為每個嵌入器和向量使用一個儲存很有趣，因為我們現在可以使用文件 ID 來識別向量。不再需要查找資料庫和向量 ID。向量 ID 縮減為文件 ID。我們可以使用過濾器的輸出過濾 arroy 索引。

Meilisearch 端的搜尋演算法不同。我們請求每個 arroy 索引中的最近鄰居，按文件 ID 對結果進行排序，以便能夠對它們進行重複資料刪除，並且不會多次傳回同一個文件，再次按距離對它們進行排序，然後只傳回前 20 個文件。這看起來很複雜，但我們談論的是每個單個文件的向量數量為 20 個文件。通常，使用者將只有一個向量。

fn vector_search(
    rtxn: &RoTxn,
    database: Database,
    embedder_index: u8,
    limit: usize,
    candidates: &RoaringBitmap,
    target_vector: &[f32],
) -> Vec<(DocumentId, f32)> {
    // The index represents the embedder index shifted and
    // is later combined with the arroy index. There is an arroy
    // index by vector for a single embedded in a document.
    let index = (embedder_index as u16) << 8;
    let readers: Vec<_> = (0..=u8::MAX)
        .map(|k| index | (k as u16))
        .map_while(|index| arroy::Reader::open(rtxn, index, database).unwrap())
        .collect();

    let mut results = Vec::new();
    for reader in &readers {
        let nns = reader.nns_by_vector(rtxn, target_vector, limit, None, Some(candidates)).unwrap();
        results.extend(nns_by_vector);
    }

    // Documents can have multiple vectors. We store the different vectors
    // into different arroy indexes, we must make sure we don't find the nearest neighbors
    // vectors that correspond to the same document.
    results.sort_unstable_by_key(|(doc_id, _)| doc_id);
    results.dedup_by_key(|(doc_id, _)| doc_id);

    // Sort back the documents by distance
    results.sort_unstable_by_key(|(_, distance)| distance);
    results
}

這些改進背後的設計理念

我們正努力讓 Meilisearch 能夠彈性地滿足每個人的需求。無論您的文件是使用單一的嵌入 (例如 OpenAI 的精巧工具所產生的嵌入)，或是像許多電子商務網站那樣混合使用文字和圖像嵌入，我們都希望您的搜尋體驗能無縫接軌。我們也沒有忘記那些使用來自多模態嵌入器的多個嵌入的進階使用者。我們最新的改進確保每個人都可以逐步更新和微調搜尋索引，使整個過程像奶油般順滑。

非常感謝大家：總結來說，我們要向團隊成員們致上最誠摯的感謝 – @dureuill、 @irevoire 和 @ManyTheFish – 他們的才華和辛勤工作使我們的想法付諸實現。同時請留意 @irevoire 即將發表的文章，他將在文章中解釋我們如何在 Arroy 中實現增量索引—這表示您可以新增向量，而無需從頭開始重建所有內容。更多資訊即將推出！

您可以在 Lobste.rs、 Hacker News、 the Rust Subreddit 或 X (前身為 Twitter) 上評論這篇文章。

Meilisearch 是一個開源的搜尋引擎，不僅為終端使用者提供最先進的體驗，還提供簡單直觀的開發人員體驗。

若想了解更多關於 Meilisearch 的資訊，您可以加入 Discord 社群或訂閱 電子報。您可以查看 產品路線圖並參與 產品討論來深入了解該產品。