向量搜索引擎是數據庫一個重要的新增功能，它面臨著擴展性、垃圾回收、并發性、磁盤利用效率和組合能力等多方面的架構挑戰。本文將介紹DataStax如何在Astra DB和Apache Cassandra中添加這些功能。

譯自 5 Hard Problems in Vector Search， and How Cassandra Solves Them 。

向量搜索是生成式AI工具的關鍵組成部分，因為像FLARE這樣的檢索增強生成(RAG)可以幫助大語言模型在避免混淆的同時融入最新、定制化的信息。與此同時，向量搜索是一個功能而不是一個獨立的產品——您需要查詢向量與數據集其他部分的關聯，而不僅僅是隔離查詢，并且您不應該需要構建管道來同步向量存儲中的其他數據。

今年，我們看到向量搜索產品和項目數量爆炸式增長，這使得在眾多選擇中選取成為一項嚴峻的工作。在研究可選方案時，您需要考慮以下難題以及解決它們的不同方法。本文將介紹DataStax如何在設計Astra DB和Apache Cassandra的向量搜索實現時解決這些挑戰。

維度的詛咒

這些難題的核心在于研究人員所說的“維度的詛咒”。這在實踐中意味著，在2D或3D空間中仍然可用的算法，如k-d trees，當向量的維度達到10、100或1000時就會崩潰。結果是，使用高維向量進行精確相似性搜索沒有捷徑；為了獲得對數時間復雜度的結果，我們需要使用近似最近鄰(ANN)算法，這帶來了以下領域的挑戰。

問題1: 橫向擴展

許多向量搜索算法是為適應單機內存的數據集而設計的，ann-benchmarks的測試也僅限于此場景。對于學術界處理百萬級文檔或行數據這可能還行，但這距離真實世界的工作負載要求還有很大差距。

與任何其它領域一樣，橫向擴展需要復制和分區，以及處理失敗復制、網絡分區后的修復等子系統。

這對我們來說是一個簡單的問題：擴展式復制是Cassandra的強項，將其與Cassandra 5.0中的SAI(存儲連接索引 —— 參見CEP-7了解其工作原理，參見SAI文檔了解如何使用它)結合，使我們的向量搜索實現幾乎零成本地獲得了強大的橫向擴展能力。

圖片

問題2: 高效的垃圾回收

這里的“垃圾回收”是指從索引中刪除陳舊信息，包括清理已刪除的行和處理索引向量值已更改的行。這可能看起來微不足道——在關系數據庫世界中，這在40年前就已經成為一個基本解決的問題——但向量索引具有獨特性。

關鍵問題是，我們目前所知提供低延遲搜索和高召回率結果的所有算法都是基于圖的。還有許多其他向量索引算法可以使用——FAISS實現了其中許多——但要么構建太慢，要么搜索太慢，要么召回率太低(有時兼具三者)無法作為通用解決方案。這就是目前我所知生產環境中的向量數據庫都使用基于圖的索引的原因，最簡單的就是HNSW。HNSW(分層導航小世界圖)由Yury Malkov等人在2016年提出；這篇論文非常易讀，我強烈推薦。關于HNSW的更多內容見下文。

圖形索引的挑戰在于，當行或文檔發生更改時，您不能簡單地將舊的(向量關聯)節點移除；如果您這樣做多次，您的圖將不再能夠執行其目的，即引導廣度優先搜索快速定位包含所有相似向量的底層區域。

所以您需要定期重建索引以執行垃圾回收，但如何安排時間和組織重建呢？如果您每次更改時都重建全部，您將大大增加物理寫入量；這稱為寫入放大。另一方面，如果從不重建則會在查詢時額外過濾掉大量陳舊信息，形成“讀取放大”。

這是Cassandra多年來一直在研究解決的問題空間。由于SAI索引與主存儲生命周期綁定，它們也會參與Cassandra的壓縮過程，這以對數方式增加存儲單元大小，在讀取和寫入之間提供更好的平衡。

圖片

邊車: 云應用程序工作負載

DataStax Astra DB 建立在Apache Cassandra之上，為云應用程序工作負載提供一個平臺。這意味著以下工作負載:

• 大規模并發 每秒處理數千到數百萬個請求，通常每個只檢索幾行。這就是為什么即使你能付得起Snowflake的費用，也無法在其上運行Netflix的原因:Snowflake和類似的分析系統只設計為處理每個運行數秒到數分鐘甚至更長的幾個并發請求。
• 大于內存 如果您的數據集適合單臺機器上的內存，那么使用什么工具都沒關系。SQLite、MongoDB、MySQL都可以很好地工作。當情況不是這樣時，事情會更具挑戰性 —— 壞消息是向量嵌入通常每個幾KB，比典型數據庫文檔大約一個數量級，所以您會相對快速地進入大于內存的規模。
• 應用的核心 如果您不介意丟失數據，無論是因為數據不重要，還是因為您可以從記錄的實際源重建數據，那么同樣，使用什么工具都無關緊要。像Cassandra和Astra DB這樣的數據庫被構建為無論發生什么，都會保持您的數據可用和持久。

問題3: 并發性

我之前提到，著名的ann-benchmarks比較將所有算法限制為單個內核。雖然這營造了公平的比較環境，但它也削弱了那些可以利用過去20年來硬件改進的主要來源(并行計算)的算法的優勢。

一個相關的問題是，ann-benchmarks只執行一種類型的操作: 首先構建索引，然后查詢索引。處理與搜索交錯的更新是可選的——事實上這可能是一種劣勢；如果您知道不需要處理更新，您可以做出在人工基準測試上表現良好但不實用的簡化假設。

如果您關心能夠并發執行多種操作，或者需要在構建后繼續更新索引，那么您就需要更深入地了解算法的工作原理和所涉及的權衡取舍。

首先，我所知道的所有通用向量數據庫都使用基于圖的索引。這是因為您可以在插入第一個向量后立即開始查詢圖形索引。大多數其他選項要求您在查詢索引之前構建完整的索引，或者至少預先掃描數據以學習某些統計屬性。

但是，即使在圖形索引類別內，實現細節也非常重要。例如，我們最初以為我們可以使用Lucene的HNSW索引實現來節省時間，正如MongoDB、Elastic和Solr所做的那樣。但我們很快了解到，Lucene只提供單線程的非并發索引構建。也就是說，您既不能在構建過程中查詢它(這本應該是使用該數據結構的主要原因之一!)，也不能允許多線程并發構建。

HNSW論文中建議使用細粒度鎖可以解決問題，但我們做得更好，實現了一個非阻塞索引，在JVector中開源。

JVector可以線性擴展到至少32個線程的并發更新。圖中x軸和y軸均為對數縮放，顯示線程數加倍可以使構建時間減半。

圖片

更重要的是，JVector的非阻塞并發對混合搜索和更新的更實際的工作負載也有益處。這里比較了Astra DB(使用JVector)與Pinecone在不同數據集上的性能。盡管Astra DB在靜態數據集上比Pinecone快約10%，但在同時索引新數據的情況下，它的速度要快8到15倍。我們根據Pinecone建議選擇了他們提供的最佳Pod配置(Pod類型:p2 和 Pod 大小:x8，每個副本有兩個Pod)，以追求更高吞吐量和更低延遲。Pinecone沒有透露這對應于哪些物理資源。Astra DB方面，我們選擇了默認的按用計費部署模式，不必擔心資源選擇，因為它是無服務器的。測試使用NoSQLBench執行。

圖片

Astra DB在實現更高性能的同時還能保持更高的召回率和精確度(F1值為召回率和精確度的組合)。

圖片

問題4: 有效利用磁盤

我們最初采用HNSW圖形索引算法，因為它構建索引快、查詢快、準確性高，并且易于實現。但是，它有一個眾所周知的缺點: 需要大量內存。

HNSW索引由多層組成，其中每一上層節點數約為前一層的10%。這使上層可以充當跳表，允許搜索快速定位包含所有向量的底層區域。

圖片

然而，這種設計意味著(與所有圖形索引一樣)您不能簡單依靠“磁盤緩存就能解決問題”，因為與普通數據庫查詢不同，圖中的每個向量對搜索的相關性幾乎相等(上層是一個例外，我們可以并且的確緩存上層)。

Cassandra大部分時間都在等待從磁盤讀取向量。

為解決這個問題，我們實現了一種更高級的算法DiskANN，并作為獨立的嵌入式向量搜索引擎JVector開源(具體來說，JVector實現了DiskANN論文中描述的增量DiskANN算法)。簡而言之，DiskANN使用比HNSW更長的單層圖邊、優化的向量和鄰居布局來減少磁盤IOPS，并保持向量的壓縮表示在內存中以加速相似性計算。這使Wikipedia工作負載的吞吐量提高了兩倍以上。

下圖顯示了純嵌入式場景下，不包含客戶端/服務器組件的情況下，HNSW與DiskANN的對比。這測量了在Lucene(HNSW)和JVector(DiskANN)下搜索Deep100M數據集的速度。Lucene索引為55GB，包括索引和原始向量。JVector索引為64GB。測試環境為僅有24GB內存的MacBook，約為完整保存索引所需內存的三分之一。

圖片

問題5: 組合能力

在數據庫系統背景下，組合能力指無縫集成各種功能和能力的能力。當討論集成新類別的功能(如向量搜索)時尤其重要。實際應用除了需要經典的CRUD數據庫功能，還需要向量搜索。

考慮Astra DB的簡單AI聊天機器人應用示例。這是一個關于RAG的最純粹的應用，它使用向量搜索為大語言模型提供適當的文檔，以回答用戶的問題。但是，即使是一個簡單的演示，它仍需要對Astra DB執行“正?！钡姆窍蛄坎樵?，來檢索對話歷史，因為對話歷史也必須隨每個請求一起發送給大語言模型，以便它可以“記住”之前發生的事。所以關鍵查詢包括:

• 為用戶問題找到最相關文檔(或文檔片段)
• 檢索用戶對話的最后20條消息

在一個更實際的用例中，我們的一位解決方案工程師最近與一家亞洲公司合作，他們希望為產品目錄添加語義搜索，但也希望啟用基于詞條的匹配。例如，如果用戶搜索“紅色球閥”，則希望將搜索限制在描述中匹配“紅色”詞條的產品，不管向量嵌入的語義相似度如何。那么除了經典功能比如會話管理、訂單歷史、購物車更新等，新的關鍵查詢是：限制產品為包含所有引號內詞條的產品，然后在結果中找到與用戶查詢最相似的。

從這個第二個例子可以清楚看出，應用不僅需要經典查詢功能和向量搜索，而且它們經常需要在同一個查詢中使用兩者。

當前這個領域尚在發展階段，主流做法是嘗試在“普通”數據庫中執行經典查詢，在向量數據庫中執行向量查詢，然后當兩者同時需要時，以一種特殊方式將它們拼接。這種方式容易出錯、低效且昂貴；它的唯一優點是在有更好解決方案之前，可以讓它工作。

在Astra DB中，我們在Cassandra SAI之上構建(并開源)了一個更好的解決方案。因為SAI允許創建自定義索引類型，所有的索引都綁定到Cassandra SSTable和壓縮生命周期，所以Astra DB可以輕松地允許開發人員無縫混合使用布爾邏輯、基于詞條的搜索和向量搜索，而無需管理和同步獨立系統的額外開銷。這為構建生成式AI應用的開發者提供了更高級的查詢功能，可以提高生產力并縮短上市時間。

結論

向量搜索引擎是數據庫的一個重要新增功能，它面臨著擴展性、垃圾回收、并發性、磁盤利用效率和組合能力等多方面的架構挑戰。我認為，通過為Astra DB構建向量搜索，我們能夠發揮Cassandra的優勢，為生成式AI應用開發者提供一流的用戶體驗。欲了解更多Astra DB信息，請點擊此處；如果您想深入了解向量搜索算法，請查看JVector。