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

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

向量搜索是生成式AI工具的關(guān)鍵組成部分，因?yàn)橄馞LARE這樣的檢索增強(qiáng)生成(RAG)可以幫助大語(yǔ)言模型在避免混淆的同時(shí)融入最新、定制化的信息。與此同時(shí)，向量搜索是一個(gè)功能而不是一個(gè)獨(dú)立的產(chǎn)品——您需要查詢向量與數(shù)據(jù)集其他部分的關(guān)聯(lián)，而不僅僅是隔離查詢，并且您不應(yīng)該需要構(gòu)建管道來(lái)同步向量存儲(chǔ)中的其他數(shù)據(jù)。

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

維度的詛咒

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

問(wèn)題1: 橫向擴(kuò)展

許多向量搜索算法是為適應(yīng)單機(jī)內(nèi)存的數(shù)據(jù)集而設(shè)計(jì)的，ann-benchmarks的測(cè)試也僅限于此場(chǎng)景。對(duì)于學(xué)術(shù)界處理百萬(wàn)級(jí)文檔或行數(shù)據(jù)這可能還行，但這距離真實(shí)世界的工作負(fù)載要求還有很大差距。

與任何其它領(lǐng)域一樣，橫向擴(kuò)展需要復(fù)制和分區(qū)，以及處理失敗復(fù)制、網(wǎng)絡(luò)分區(qū)后的修復(fù)等子系統(tǒng)。

這對(duì)我們來(lái)說(shuō)是一個(gè)簡(jiǎn)單的問(wèn)題：擴(kuò)展式復(fù)制是Cassandra的強(qiáng)項(xiàng)，將其與Cassandra 5.0中的SAI(存儲(chǔ)連接索引 —— 參見(jiàn)CEP-7了解其工作原理，參見(jiàn)SAI文檔了解如何使用它)結(jié)合，使我們的向量搜索實(shí)現(xiàn)幾乎零成本地獲得了強(qiáng)大的橫向擴(kuò)展能力。

圖片

問(wèn)題2: 高效的垃圾回收

這里的“垃圾回收”是指從索引中刪除陳舊信息，包括清理已刪除的行和處理索引向量值已更改的行。這可能看起來(lái)微不足道——在關(guān)系數(shù)據(jù)庫(kù)世界中，這在40年前就已經(jīng)成為一個(gè)基本解決的問(wèn)題——但向量索引具有獨(dú)特性。

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

圖形索引的挑戰(zhàn)在于，當(dāng)行或文檔發(fā)生更改時(shí)，您不能簡(jiǎn)單地將舊的(向量關(guān)聯(lián))節(jié)點(diǎn)移除；如果您這樣做多次，您的圖將不再能夠執(zhí)行其目的，即引導(dǎo)廣度優(yōu)先搜索快速定位包含所有相似向量的底層區(qū)域。

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

這是Cassandra多年來(lái)一直在研究解決的問(wèn)題空間。由于SAI索引與主存儲(chǔ)生命周期綁定，它們也會(huì)參與Cassandra的壓縮過(guò)程，這以對(duì)數(shù)方式增加存儲(chǔ)單元大小，在讀取和寫(xiě)入之間提供更好的平衡。

圖片

邊車: 云應(yīng)用程序工作負(fù)載

DataStax Astra DB 建立在Apache Cassandra之上，為云應(yīng)用程序工作負(fù)載提供一個(gè)平臺(tái)。這意味著以下工作負(fù)載:

• 大規(guī)模并發(fā) 每秒處理數(shù)千到數(shù)百萬(wàn)個(gè)請(qǐng)求，通常每個(gè)只檢索幾行。這就是為什么即使你能付得起Snowflake的費(fèi)用，也無(wú)法在其上運(yùn)行Netflix的原因:Snowflake和類似的分析系統(tǒng)只設(shè)計(jì)為處理每個(gè)運(yùn)行數(shù)秒到數(shù)分鐘甚至更長(zhǎng)的幾個(gè)并發(fā)請(qǐng)求。
• 大于內(nèi)存 如果您的數(shù)據(jù)集適合單臺(tái)機(jī)器上的內(nèi)存，那么使用什么工具都沒(méi)關(guān)系。SQLite、MongoDB、MySQL都可以很好地工作。當(dāng)情況不是這樣時(shí)，事情會(huì)更具挑戰(zhàn)性 —— 壞消息是向量嵌入通常每個(gè)幾KB，比典型數(shù)據(jù)庫(kù)文檔大約一個(gè)數(shù)量級(jí)，所以您會(huì)相對(duì)快速地進(jìn)入大于內(nèi)存的規(guī)模。
• 應(yīng)用的核心 如果您不介意丟失數(shù)據(jù)，無(wú)論是因?yàn)閿?shù)據(jù)不重要，還是因?yàn)槟梢詮挠涗浀膶?shí)際源重建數(shù)據(jù)，那么同樣，使用什么工具都無(wú)關(guān)緊要。像Cassandra和Astra DB這樣的數(shù)據(jù)庫(kù)被構(gòu)建為無(wú)論發(fā)生什么，都會(huì)保持您的數(shù)據(jù)可用和持久。

問(wèn)題3: 并發(fā)性

我之前提到，著名的ann-benchmarks比較將所有算法限制為單個(gè)內(nèi)核。雖然這營(yíng)造了公平的比較環(huán)境，但它也削弱了那些可以利用過(guò)去20年來(lái)硬件改進(jìn)的主要來(lái)源(并行計(jì)算)的算法的優(yōu)勢(shì)。

一個(gè)相關(guān)的問(wèn)題是，ann-benchmarks只執(zhí)行一種類型的操作: 首先構(gòu)建索引，然后查詢索引。處理與搜索交錯(cuò)的更新是可選的——事實(shí)上這可能是一種劣勢(shì)；如果您知道不需要處理更新，您可以做出在人工基準(zhǔn)測(cè)試上表現(xiàn)良好但不實(shí)用的簡(jiǎn)化假設(shè)。

如果您關(guān)心能夠并發(fā)執(zhí)行多種操作，或者需要在構(gòu)建后繼續(xù)更新索引，那么您就需要更深入地了解算法的工作原理和所涉及的權(quán)衡取舍。

首先，我所知道的所有通用向量數(shù)據(jù)庫(kù)都使用基于圖的索引。這是因?yàn)槟梢栽诓迦氲谝粋€(gè)向量后立即開(kāi)始查詢圖形索引。大多數(shù)其他選項(xiàng)要求您在查詢索引之前構(gòu)建完整的索引，或者至少預(yù)先掃描數(shù)據(jù)以學(xué)習(xí)某些統(tǒng)計(jì)屬性。

但是，即使在圖形索引類別內(nèi)，實(shí)現(xiàn)細(xì)節(jié)也非常重要。例如，我們最初以為我們可以使用Lucene的HNSW索引實(shí)現(xiàn)來(lái)節(jié)省時(shí)間，正如MongoDB、Elastic和Solr所做的那樣。但我們很快了解到，Lucene只提供單線程的非并發(fā)索引構(gòu)建。也就是說(shuō)，您既不能在構(gòu)建過(guò)程中查詢它(這本應(yīng)該是使用該數(shù)據(jù)結(jié)構(gòu)的主要原因之一!)，也不能允許多線程并發(fā)構(gòu)建。

HNSW論文中建議使用細(xì)粒度鎖可以解決問(wèn)題，但我們做得更好，實(shí)現(xiàn)了一個(gè)非阻塞索引，在JVector中開(kāi)源。

JVector可以線性擴(kuò)展到至少32個(gè)線程的并發(fā)更新。圖中x軸和y軸均為對(duì)數(shù)縮放，顯示線程數(shù)加倍可以使構(gòu)建時(shí)間減半。

圖片

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

圖片

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

圖片

問(wèn)題4: 有效利用磁盤

我們最初采用HNSW圖形索引算法，因?yàn)樗鼧?gòu)建索引快、查詢快、準(zhǔn)確性高，并且易于實(shí)現(xiàn)。但是，它有一個(gè)眾所周知的缺點(diǎn): 需要大量?jī)?nèi)存。

HNSW索引由多層組成，其中每一上層節(jié)點(diǎn)數(shù)約為前一層的10%。這使上層可以充當(dāng)跳表，允許搜索快速定位包含所有向量的底層區(qū)域。

圖片

然而，這種設(shè)計(jì)意味著(與所有圖形索引一樣)您不能簡(jiǎn)單依靠“磁盤緩存就能解決問(wèn)題”，因?yàn)榕c普通數(shù)據(jù)庫(kù)查詢不同，圖中的每個(gè)向量對(duì)搜索的相關(guān)性幾乎相等(上層是一個(gè)例外，我們可以并且的確緩存上層)。

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

為解決這個(gè)問(wèn)題，我們實(shí)現(xiàn)了一種更高級(jí)的算法DiskANN，并作為獨(dú)立的嵌入式向量搜索引擎JVector開(kāi)源(具體來(lái)說(shuō)，JVector實(shí)現(xiàn)了DiskANN論文中描述的增量DiskANN算法)。簡(jiǎn)而言之，DiskANN使用比HNSW更長(zhǎng)的單層圖邊、優(yōu)化的向量和鄰居布局來(lái)減少磁盤IOPS，并保持向量的壓縮表示在內(nèi)存中以加速相似性計(jì)算。這使Wikipedia工作負(fù)載的吞吐量提高了兩倍以上。

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

圖片

問(wèn)題5: 組合能力

在數(shù)據(jù)庫(kù)系統(tǒng)背景下，組合能力指無(wú)縫集成各種功能和能力的能力。當(dāng)討論集成新類別的功能(如向量搜索)時(shí)尤其重要。實(shí)際應(yīng)用除了需要經(jīng)典的CRUD數(shù)據(jù)庫(kù)功能，還需要向量搜索。

考慮Astra DB的簡(jiǎn)單AI聊天機(jī)器人應(yīng)用示例。這是一個(gè)關(guān)于RAG的最純粹的應(yīng)用，它使用向量搜索為大語(yǔ)言模型提供適當(dāng)?shù)奈臋n，以回答用戶的問(wèn)題。但是，即使是一個(gè)簡(jiǎn)單的演示，它仍需要對(duì)Astra DB執(zhí)行“正?！钡姆窍蛄坎樵儯瑏?lái)檢索對(duì)話歷史，因?yàn)閷?duì)話歷史也必須隨每個(gè)請(qǐng)求一起發(fā)送給大語(yǔ)言模型，以便它可以“記住”之前發(fā)生的事。所以關(guān)鍵查詢包括:

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

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

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

當(dāng)前這個(gè)領(lǐng)域尚在發(fā)展階段，主流做法是嘗試在“普通”數(shù)據(jù)庫(kù)中執(zhí)行經(jīng)典查詢，在向量數(shù)據(jù)庫(kù)中執(zhí)行向量查詢，然后當(dāng)兩者同時(shí)需要時(shí)，以一種特殊方式將它們拼接。這種方式容易出錯(cuò)、低效且昂貴；它的唯一優(yōu)點(diǎn)是在有更好解決方案之前，可以讓它工作。

在Astra DB中，我們?cè)贑assandra SAI之上構(gòu)建(并開(kāi)源)了一個(gè)更好的解決方案。因?yàn)镾AI允許創(chuàng)建自定義索引類型，所有的索引都綁定到Cassandra SSTable和壓縮生命周期，所以Astra DB可以輕松地允許開(kāi)發(fā)人員無(wú)縫混合使用布爾邏輯、基于詞條的搜索和向量搜索，而無(wú)需管理和同步獨(dú)立系統(tǒng)的額外開(kāi)銷。這為構(gòu)建生成式AI應(yīng)用的開(kāi)發(fā)者提供了更高級(jí)的查詢功能，可以提高生產(chǎn)力并縮短上市時(shí)間。

結(jié)論

向量搜索引擎是數(shù)據(jù)庫(kù)的一個(gè)重要新增功能，它面臨著擴(kuò)展性、垃圾回收、并發(fā)性、磁盤利用效率和組合能力等多方面的架構(gòu)挑戰(zhàn)。我認(rèn)為，通過(guò)為Astra DB構(gòu)建向量搜索，我們能夠發(fā)揮Cassandra的優(yōu)勢(shì)，為生成式AI應(yīng)用開(kāi)發(fā)者提供一流的用戶體驗(yàn)。欲了解更多Astra DB信息，請(qǐng)點(diǎn)擊此處；如果您想深入了解向量搜索算法，請(qǐng)查看JVector。