總結
本文將介紹 Milvus 如何實現刪除功能。作為很多用戶期待已久的功能,刪除功能被引入到 Milvus v0.7.0。我們並沒有直接在 FAISS 中呼叫 remove_ids,而是想出了一個全新的設計,讓刪除更有效率,並支援更多的索引類型。
在《Milvus 如何實現動態資料更新與查詢》一文中,我們介紹了從插入資料到刷新資料的整個過程。讓我們重溫一些基本知識。MemManager 管理所有插入緩衝區,每個 MemTable 對應一個集合(我們在 Milvus v0.7.0 中將 "table「 改名為 」collection")。Milvus 會自動將插入記憶體的資料分割成多個 MemTableFiles。當資料刷新到磁碟時,每個 MemTableFile 會序列化成原始檔案。在設計刪除函式時,我們保留了這個架構。
我們將 delete 方法的功能定義為刪除特定集合中與指定實體 ID 相對應的所有資料。在開發這個函式時,我們設計了兩種情況。第一種是刪除仍在插入緩衝區中的資料,第二種是刪除已刷新到磁碟上的資料。第一種情況比較直覺。我們可以找到與指定 ID 對應的 MemTableFile,直接刪除記憶體中的資料(圖 1)。由於刪除和插入資料不能同時進行,而且在刷新資料時,MemTableFile 會由可變變為不可變的機制,因此刪除只能在可變緩衝區中進行。如此一來,刪除作業就不會與資料刷新發生衝突,從而確保資料的一致性。
1-delete-request-milvus.jpg
第二種情況比較複雜,但也比較常見,因為在大多數情況下,資料會先在插入緩衝區中短暫停留,然後才刷新到磁碟上。由於將刷新的資料載入記憶體進行硬刪除的效率非常低,因此我們決定採用軟刪除這種更有效率的方式。軟刪除不是實際刪除刷新的資料,而是將已刪除的 ID 儲存在單獨的檔案中。如此一來,我們就可以在讀取作業(例如搜尋)時篩選出那些已刪除的 ID。
說到實作,我們有幾個問題需要考慮。在 Milvus 中,資料只有在刷新到磁碟上時才會可見,或者換句話說,才可以復原。因此,刷新的資料不會在刪除方法呼叫中刪除,而是在下一次刷新作業中刪除。原因是已刷新到磁碟的資料檔案將不會再包含新資料,因此軟刪除不會影響已刷新的資料。呼叫 delete 時,可以直接刪除仍在插入緩衝區中的資料,而對於已沖洗的資料,則需要在記憶體中記錄刪除資料的 ID。當將資料刷新到磁碟時,Milvus 會將刪除的 ID 寫入 DEL 檔案,以記錄相對應區段中的哪個實體被刪除。只有在資料刷新完成後,這些更新才會顯現。這個過程如圖 2 所示。在 v0.7.0 之前,我們只有自動沖洗機制;也就是 Milvus 每秒將插入緩衝區中的資料序列化。在我們的新設計中,我們加入了一個 flush 方法,允許開發人員在 delete 方法之後呼叫,確保新插入的資料是可見的,而刪除的資料則無法再復原。
2-delete-request-milvus.jpg
第二個問題是原始資料檔案和索引檔案在 Milvus 中是兩個獨立的檔案,在 metadata 中也是兩個獨立的記錄。在刪除指定 ID 時,我們需要找到與 ID 相對應的原始檔案和索引檔案,並將它們一起記錄下來。因此,我們引入了段的概念。一個段包含原始檔案(其中包括原始向量檔案和 ID 檔案)、索引檔案和 DEL 檔案。在 Milvus 中,段是讀取、寫入和搜尋向量的最基本單位。一個集合(圖 3)是由多個段組成的。因此,磁碟中一個 collection 資料夾下有多個 segment 資料夾。由於我們的元資料是以關係資料庫(SQLite 或 MySQL)為基礎,因此記錄段內的關係非常簡單,刪除操作也不再需要分開處理原始檔案和索引檔案。
3-delete-request-milvus.jpg
第三個問題是如何在搜尋過程中篩選出已刪除的資料。實際上,DEL 記錄的 ID 是段中儲存的相應資料的偏移量。由於刷新的區段不包含新資料,因此偏移量不會改變。DEL 的資料結構是記憶體中的位元圖,其中有效位元代表刪除的偏移量。我們也相應更新了 FAISS:當您在 FAISS 中搜尋時,活動位元對應的向量將不再包含在距離計算中(圖 4)。FAISS 的變更在此不做詳細說明。
4-delete-request-milvus.jpg
最後一個問題是關於效能改善。刪除已刷新的資料時,首先需要找出被刪除的 ID 位於集合的哪個區段,然後記錄其偏移量。最直接的方法是搜尋每一段中的所有 ID。我們所考慮的最佳化方法是在每個區段中加入 Bloom 過濾器。Bloom 過濾器是一種隨機資料結構,用來檢查元素是否為集合的成員。因此,我們可以只載入每個區段的 Bloom 過濾器。只有當 bloom filter 斷定被刪除的 ID 在目前的區段中,我們才能在區段中找到對應的偏移量;否則,我們可以忽略這個區段 (圖 5)。我們選擇 bloom 過濾器的原因,是因為它使用較少的空間,而且搜尋效率比許多同級產品 (例如哈希表) 更高。雖然 bloom filter 有一定的誤判率,但我們可以將需要搜尋的區段減少到理想的數量來調整這個概率。同時,bloom filter 也需要支援刪除功能。否則,已刪除的實體 ID 仍然可以在 bloom filter 中找到,導致假陽性率增加。因此,我們使用計數 bloom filter,因為它支援刪除。在這篇文章中,我們不會詳細說明 bloom filter 如何運作。如果您有興趣,可以參考 Wikipedia。
5-delete-request-milvus.jpg
總結
到目前為止,我們已經簡單介紹了 Milvus 如何依 ID 刪除向量。大家都知道,我們使用軟刪除來刪除刷新的資料。隨著刪除資料的增加,我們需要壓縮集合中的段來釋放被刪除資料佔用的空間。此外,如果某個區段已經建立索引,compact 也會刪除先前的索引檔案,並建立新的索引。目前,開發人員需要呼叫 compact 方法來壓縮資料。展望未來,我們希望能引入檢查機制。例如,當刪除的資料量達到某個臨界值,或是刪除後的資料分佈發生了變化,Milvus 就會自動壓縮該區段。
現在我們介紹了刪除函式背後的設計理念及其實作。我們肯定還有改進的空間,歡迎您提出任何意見或建議。
了解 Milvus:https://github.com/milvus-io/milvus。您也可以加入我們的社群Slack進行技術討論!
Try Managed Milvus for Free
Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.
Get StartedLike the article? Spread the word