在Rust中用一周時間編寫一個矢量數(shù)據(jù)庫

矢量數(shù)據(jù)庫目前在科技界風(fēng)靡一時，而不僅僅是炒作。由于利用矢量嵌入的人工智能進步，矢量搜索變得越來越重要。這些向量嵌入是單詞嵌入、句子或文檔的向量表示，只需查看向量之間的距離度量，即可為語義接近的輸入提供語義相似性。

word2vec 的規(guī)范示例，其中單詞“king”的嵌入非常接近單詞“queen”、“man”和“woman”的向量的結(jié)果向量，當(dāng)按以下公式排列時：

    king - man + woman ≈ queen

事實上，這對我來說總是很神奇，但如果我們的嵌入空間具有足夠高的維度，它甚至適用于相當(dāng)大的文檔。使用現(xiàn)代深度學(xué)習(xí)方法，您可以獲得復(fù)雜文檔的出色嵌入。

對于 TerminusDB，我們需要一種方法來利用這些類型的嵌入來完成用戶要求的以下任務(wù)：

全文搜索

實體解析（查找可能與重復(fù)數(shù)據(jù)刪除相同的其他文檔）

相似性搜索（相關(guān)內(nèi)容或推薦系統(tǒng)）

聚類

我們決定使用OpenAI的嵌入進行原型設(shè)計，但為了獲得其余的功能，我們需要一個矢量數(shù)據(jù)庫。

我們需要一些不尋常的功能，包括執(zhí)行增量索引的能力，以及索引提交基礎(chǔ)的能力，以便我們準(zhǔn)確地知道索引適用于什么提交。這使我們能夠?qū)⑺饕湃?CI 工作流中。

野外不存在版本化的開源矢量數(shù)據(jù)庫。所以我們寫了一個！

編寫矢量數(shù)據(jù)庫

向量數(shù)據(jù)庫是向量的存儲，能夠使用某些指標(biāo)比較任意兩個向量。度量可以是很多不同的東西，例如歐幾里得距離、余弦相似性、出租車幾何，或者任何遵守定義度量空間所需的三角形不等式規(guī)則的東西。

為了快速做到這一點，您需要有某種索引結(jié)構(gòu)來快速找到已經(jīng)接近比較的候選人。否則，許多操作每次都需要與數(shù)據(jù)庫中的每個內(nèi)容進行比較。

有許多方法可以索引向量空間，但我們使用了HNSW（分層可導(dǎo)航小世界）圖（參見Malkov和Yashunin）。HNSW易于理解，在低尺寸和高尺寸上都具有良好的性能，因此具有靈活性。最重要的是，我們發(fā)現(xiàn)了一個非常清晰的開源實現(xiàn) - 用于 Rust 計算機視覺的 HNSW。

存儲向量

向量存儲在域中。這有助于分離不需要描述相同載體的不同載體存儲。對于TerminusDB，我們有許多不同的提交，它們都與相同的向量有關(guān)，因此將它們?nèi)糠湃胪挥蛑蟹浅Ｖ匾?/p>

矢量存儲是基于頁面的，其中每個緩沖區(qū)都設(shè)計為清晰地映射到操作系統(tǒng)頁面，但適合我們緊密使用的矢量。我們?yōu)槊總€向量分配一個索引，然后我們可以從索引映射到適當(dāng)?shù)捻撁婧推屏俊?/p>

在 HNSW 索引中，我們指的是 .這可確保頁面位于當(dāng)前加載的緩沖區(qū)中，以便我們可以對感興趣的向量執(zhí)行指標(biāo)比較。LoadedVec

一旦最后一個緩沖區(qū)從緩沖區(qū)中刪除，就可以將緩沖區(qū)添加回緩沖池中，以用于加載新頁面。LoadedVec

創(chuàng)建版本化索引

我們?yōu)槊總€（域+提交）對構(gòu)建一個HNSW結(jié)構(gòu)。如果開始一個新索引，我們從一個空的 HNSW 開始。如果從上一次提交啟動增量索引，則從上一次提交加載舊的 HNSW，然后開始索引操作。

新舊的內(nèi)容都保存在TerminusDB中，它知道如何查找提交之間的更改，并可以將它們提交給矢量數(shù)據(jù)庫索引器。索引器只需要知道要求它執(zhí)行的操作（即、、）。InsertDeleteReplace

我們將索引本身維護在 LRU 池中，該池允許我們按需加載或在索引已在內(nèi)存中使用緩存。由于我們只在提交時執(zhí)行破壞性操作，因此此緩存始終是一致的。

當(dāng)我們保存索引時，我們使用原始向量索引作為替代物序列化結(jié)構(gòu)，這有助于保持索引較小。LoadedVec

將來，我們希望使用我們在 TerminusDB 中學(xué)到的一些技巧來保留索引層，這樣就可以添加新層，而無需每個增量索引在序列化時添加副本。但是，與我們存儲的向量相比，索引已經(jīng)足夠小，因此它并不重要。

注意：雖然我們目前進行增量索引，但我們尚未實現(xiàn)刪除和替換操作（一周只有這么多小時！我讀過關(guān)于HNSW的文獻，似乎還沒有很好的描述。

我們有一個刪除和替換操作的設(shè)計，我們認(rèn)為它可以很好地與HNSW配合使用，并希望在技術(shù)人員有想法的情況下進行解釋：

如果我們在 HNSW 的上層，那么只需忽略刪除 - 這應(yīng)該無關(guān)緊要，因為大多數(shù)向量不在上層，而那些只是為了導(dǎo)航。

如果我們在零層但不在上層，請從索引中刪除節(jié)點，同時嘗試根據(jù)接近度替換已刪除鏈接的所有鄰居之間的鏈接。

如果我們在零層但也在上面，將節(jié)點標(biāo)記為已刪除，并將其用于導(dǎo)航，但不將此節(jié)點存儲在候選池中。

查找嵌入

我們使用OpenAI來定義我們的嵌入，在向TerminusDB發(fā)出索引請求后，我們將每個文檔提供給OpenAI，OpenAI以JSON形式返回浮點向量列表。

事實證明，嵌入對上下文非常敏感。我們最初嘗試只提交TerminusDB JSON文檔，結(jié)果并不好。

但是，我們發(fā)現(xiàn)，如果我們定義一個 GraphQL 查詢 + Handlebars 模板，我們可以創(chuàng)建非常高質(zhì)量的嵌入。因為在《星球大戰(zhàn)》中，在我們的模式中定義的這對看起來像這樣：People

				杰倫

							?

											?

											?

											?
{
    "embedding": {
        "query": "query($id: ID){ People(id : $id) { birth_year, created, desc, edited, eye_color, gender, hair_colors, height, homeworld { label }, label, mass, skin_colors, species { label }, url } }",
        "template": "The person's name is {{label}}.{{#if desc}} They are described with the following synopsis: {{#each desc}} *{{this}} {{/each}}.{{/if}}{{#if gender}} Their gender is {{gender}}.{{/if}}{{#if hair_colors}} They have the following hair colours: {{hair_colors}}.{{/if}}{{#if mass}} They have a mass of {{mass}}.{{/if}}{{#if skin_colors}} Their skin colours are {{skin_colors}}.{{/if}}{{#if species}} Their species is {{species.label}}.{{/if}}{{#if homeworld}} Their homeworld is {{homeworld.label}}.{{/if}}"
    }
}

							?

對象中每個字段的含義都呈現(xiàn)為文本，這有助于OpenAI理解我們的意思，提供更好的語義。People

最終，如果我們能從模式文檔和模式結(jié)構(gòu)的組合中猜出這些句子，那就太好了，這可能也可以使用 AI 聊天！但就目前而言，這非常有效，不需要太多的技術(shù)復(fù)雜性。

為星球大戰(zhàn)編制索引

那么當(dāng)我們實際運行這個東西時會發(fā)生什么？好吧，我們在《星球大戰(zhàn)》數(shù)據(jù)產(chǎn)品上進行了嘗試，看看會發(fā)生什么。

首先，我們發(fā)出一個索引請求，我們的索引器從 TerminusDB 獲取信息：

curl 'localhost:8080/index?commit=o2uq7k1mrun1vp4urktmw55962vlpto&domain=admin/star_wars'

這將返回一個任務(wù) ID，我們可以使用它來輪詢端點以完成。

域和提交的索引文件和向量文件顯示為：和。admin/star_warso2uq7k1mrun1vp4urktmw55962vlptoadmin%2Fstar_wars@o2uq7k1mrun1vp4urktmw55962vlpto.hnswadmin%2Fstar_wars.vecs

現(xiàn)在，我們可以在指定的提交時向語義索引服務(wù)器詢問我們的文檔。

curl 'localhost:8080/search?commit=o2uq7k1mrun1vp4urktmw55962vlpto&domain=admin/star_wars' -d "Who are the squid people"

我們以 JSON 的形式返回許多結(jié)果，如下所示：

[{"id":"terminusdb:///star-wars/Species/8","distance":0.09396297}, ...]

但是我們用來產(chǎn)生這個結(jié)果的嵌入字符串是什么？以下是 id 的文本呈現(xiàn)方式：Species/8

				杰倫

											?

											?

											?
"The species name is Mon Calamari. They have the following hair colours: 
none. Their skin colours are red, blue, brown, magenta. They speak the 
Mon Calamarian language."

							?

了不起！請注意，它從不在任何地方說魷魚！我們的嵌入在這里做了一些非常驚人的工作。

讓我們再試一次：

curl 'localhost:8080/search?commit=o2uq7k1mrun1vp4urktmw55962vlpto&domain=admin/star_wars' -d "Wise old man"

				杰倫

											?

											?

											?
"The person's name is Yoda. They are described with the following synopsis:
Yoda is a fictional character in the Star Wars franchise created by George 
Lucas, first appearing in the 1980 film The Empire Strikes Back. In the 
original films, he trains Luke Skywalker to fight against the Galactic 
Empire. In the prequel films, he serves as the Grand Master of the Jedi 
Order and as a high-ranking general of Clone Troopers in the Clone Wars. 
Following his death in Return of the Jedi at the age of 900, Yoda was the 
oldest living character in the Star Wars franchise in canon, until the 
introduction of Maz Kanata in Star Wars: The Force Awakens. Their gender 
is male. They have the following hair colours: white. They have a mass of 
17. Their skin colours are green."

							?