Elasticsearch：普通檢索和向量檢索的異同？

語言: CN / TW / HK
時間 2022-01-19 20:24:07

1、引言

《 Elasticsearch 向量搜尋的工程化實戰 》文章一經發出，收到很多留言。讀者對向量檢索和普通檢索的區別充滿了好奇，所以就有了今天的文章。

2、普通搜尋 VS 向量搜尋

向量搜尋已經在黑暗中成長了有些年頭了，但是隨著近幾年機器學習和深度學習的蓬勃發展，“特別是萬物皆可 embedding“的觀點越來越流行之後，向量搜尋才逐漸從小眾的技術走入人們的視野之中。相較於普通搜尋（基於詞元和倒排索引），向量搜尋會成為一個革命者代替它（們）的位置，還是會與它互補，並有機的整合在一起呢？

2.1 overview

首先，我們先來了解一下這兩種搜尋方案的特點以及各自的優缺點

2.1.1 普通搜尋

以廣泛被使用的 Lucene 、 Elasticsearch 、 Solr ，以及最近出來的一些類似 MeiliSearch 、 Redisearch 等為代表，基於詞元和倒排索引所構建的普通搜尋，是建立在準確的搜尋內容和檢索語句上的，他們往往通過各種方式對文件進行分詞（ analyze ），通過諸如 BKD tree 等資料結構，將拆解出來的詞元（ token ）進行倒排索引，在檢索時也會對檢索語句進行同樣的分詞處理，通過相同詞元的匹配進行召回，再通過文字相關性的演算法（如 TF/IDF 、 BM25 等）對結果進行打分排序，最終返回結果。

因此，他們大多具有以下的特點：

  1. 具有較高的索引速度

  2. 中等的索引大小

  3. 較高的查詢速度（在大資料量的場景）

  4. 良好的縮放比例

  5. （對於精確匹配）具有完美的精度

  6. 精確且無損的詞元和片語搜尋

  7. 只能通過詞元的精確匹配做召回

  8. 無法捕獲語義與相似性

    1. ES 的 synonym 是類似在同一個位置把所有預先定義的同義詞同時索引來實現的

2.1.2 向量搜尋

如果你在搜尋時不知道確切的 query 詞元 ，或者你希望能對更廣泛的同/近義詞所指向的內容進行召回，可以考慮通過向量搜尋來完成。目前市面上比較流行的向量搜尋解決方案，無論是業界流行的 Faiss 、 ScANN 庫，還是工業級的開源解決方案 Milvus 、 Jina ，或者 Elasticsearch 及其衍生品 Elastiknn 、 OpenDistro Elasticsearch KNN ，多少會通過 KNN （ K nearest neighbors ）對向量進行預聚類的方式進行存取加速。（參考的benchmark）

所以，他們大多會具有以下一些特點：

  1. 較慢的索引速度

  2. 較大的索引大小

  3. 較慢的查詢速度（在大資料量的場景）

  4. 有限的縮放比例

  5. （對於精確匹配）具有較低的精度

  6. 較差的詞元和片語的搜尋能力

  7. 通過向量（某些解決方案中可以包含一部分標量欄位）進行召回

  8. 對近似語義的捕獲程度較高，可以很好的處理同/近義詞

2.1.3 小結

通過普通搜尋或者向量搜尋構建個簡單的搜尋引擎系統並不難，但是隨著資料量的增長、併發請求的增加、資料使用場景的變化，搜尋引擎系統需要更多的元件一同完成其功能，如搜尋前的資料預處理，到搜尋過程中的query理解、改寫、自動補全，快取，分數計算，地理位置資訊計算，到返回結果前的結果排序和過濾，結果分頁等。

2.2 資料結構與搜尋演算法

之所以普通搜尋和向量搜尋會存在上面那些特點和差異，是因為他們構建資料的索引的資料結構以及召回算分的演算法有很大差異，我們分別來看他們。

2.2.1 普通搜尋

2.2.1.1 倒排索引

倒排索引是一個類似 hashmap 的資料結構，它的 key 是每個詞元，而 value 是一個包含這個詞元的所有文件的 id 列表（也可能是 hashset 、連結串列等結構），這樣的資料結構的好處在於對於一個詞元，可以用接近 O(1) 的代價來找到包含它的文章。有時倒排索引中也會包含詞元在文件中的位置資訊，這是為了能在搜尋時，在考慮了 query 中的詞元資訊之外，也把詞元的順序也一併考慮進去。

2.2.1.2 LSM樹

LSM 樹(Log-Structured Merge-Tree)，或稱為日誌結構合併樹，被廣泛運用於以 hbase 為代表的類資料庫儲存中，它的特點在於犧牲部分讀的效能換取強大的寫入效能，因為它作為一種基於硬碟的資料結構，可以明顯的減少硬碟磁碟臂的開銷，並能在較長的時間內提供檔案的高速插入和刪除。一般的倒排索引會構建在記憶體中，但隨著資料量增加，我們可能需要通過磁碟來幫忙儲存一部分資料，這就用到了 LSM樹 ，因為硬碟（無論 SSD 還是 HDD 都比 RAM 慢的好幾個數量級），而 LSM樹 可以在寫資料的時候先把資料快取在記憶體中，等積累一定量之後再通過歸併排序的方式將資料追加到磁碟隊尾，以提高寫入速度。

2.2.1.3 帶版本的資料提交

LSM樹 只解決了資料插入的問題，搜尋引擎中還會存在大量的更新操作，這就涉及到了隨機讀寫了，我們知道隨機讀寫會比順序讀寫慢得多，特別是在 HDD 硬碟上的讀寫，這時就需要使用帶版本的資料提交操作了。由上一節可知，資料寫入時會先寫記憶體中的緩衝區（ ES 的 translog 等）再通過定時提交的方式追加到磁碟中，在更新操作時也是一樣的，不同的是搜尋引擎往往會在記憶體中保留資料的指標，每次的更新（刪除）操作作用在硬碟上也是追加操作，不同的是會將資料版本 +1，同時將指標指向新的地址，在召回時訪問資料只訪問最新版本的資料，同時定時對磁碟中的資料進行 merge 操作，清理掉過期的舊版本的資料，從而釋放磁碟空間。

2.2.1.4   升級和調優

儲存：

  1. Size-tiered compaction

  2. Leveled compaction

  3. Sharded compaction

索引：

  1. zstd（Zstandard）壓縮

  2. Elias-Fano 編碼

  3. 停止詞

  4. 詞幹

  5. ngram 索引

2.2.2 向量搜尋

向量搜尋就完全不一樣了，由於他們索引的不是【詞元 - 文件】的資訊而是向量，所以他們會在索引構建的時候會嘗試通過聚類而非倒排索引的方式構建。

市面上大部分的向量搜尋引擎是靠 KNN 配合距離計算來進行儲存的，差別可能會是距離計算公式以及儲存結構的優化。常見的距離計算如：

  1. 歐式距離 [euclidian distance] https://en.wikipedia.org/wiki/Euclidean_distance

  2. 點積 [dot product] https://en.wikipedia.org/wiki/Dot_product

  3. cosine 相似度[cosine similarity] https://en.wikipedia.org/wiki/Dot_product

2.2.2.1 索引資料

向量搜尋的資料索引不同於普通搜尋的分詞，他們會需要先通過各種 machine learning 、 deep learning 技術將文件、句子、片語等轉化成向量存進搜尋引擎，搜尋引擎會根據配置使用距離計算模組對向量進行聚類儲存。

常見的向量化（嵌入）的演算法：

  1. [Word2Vec] https://en.wikipedia.org/wiki/Word2vec

  2. [GloVe] https://en.wikipedia.org/wiki/GloVe_(machine_learning)

  3. [fastText] https://en.wikipedia.org/wiki/FastText

  4. [BERT] https://github.com/google-research/bert

  5. Word level embeddings from BERT

  6. Sentence level embeddings from BERT

2.2.2.2 召回資料

向量搜尋的召回和索引一樣是基於向量距離的，從簡單到複雜可以大致分為線性搜尋、分級導航（Hierarchical Navigable Small Worlds (HNSW)）、索引分塊及聚類等

  1. 線性搜尋

    1. 顧名思義，線性搜尋就是將 query 向量和索引中所有的向量依次比較，再按距離排序
    2. ES 對 Dense Vector 欄位的處理就是線性搜尋

    3. 這是最簡單也是最慢的方式，而且隨著索引資料量的上升，召回時間也會隨之大幅上升

  2. 分級導航

    1. 介紹 CN

      http://d0evi1.com/hnsw/

    2. 介紹 EN https://www.pinecone.io/learn/hnsw/

    3. 通過近似圖遍歷的方式找到更接近的向量進行距離計算

  3. 索引分塊及聚類

    1. K中心聚類 [k-medoids clustering] https://en.wikipedia.org/wiki/K-medoids

    2. 圍繞中心分割槽（Partitioning Around Medoids (PAM)）

    3. Correlated-Sequential-Halving

    4. Voronoi iteration with Voronoi cells (Dirichlet tessellation)

    5. K中值聚類[k-medians clustering] https://en.wikipedia.org/wiki/K-medians_clustering

    6. Kmeans聚類 [k-means/k-centroids clustering] https://en.wikipedia.org/wiki/K-means_clustering

    7. [Locality Sensitive Hashing] https://en.wikipedia.org/wiki/Locality-sensitive_hashing

    8. [Support Vector machines] https://de.wikipedia.org/wiki/Support_Vector_Machine

    9. 是向量搜尋中較為常用的方式，通過預先配置的引數對向量進行 KNN 聚類的方式進行索引
    10. 召回時會通過尋找較近的核向量的方式來找到 topK 的向量進行

    11. 主要包含的一些方式：

2.2.2.3 升級和調優

其他一些可用的開源庫

  1. [NGT] https://github.com/yahoojapan/NGT

  2. [ANNOY] https://github.com/spotify/annoy

  3. [RNSG] https://arxiv.org/abs/1707.00143

  4. [ScaNN] https://ai.googleblog.com/2020/07/announcing-scann-efficient-vector.html

  5. 更多

    1. [ann-benchmarks] https://github.com/erikbern/ann-benchmarks

    2. [awesome-vector-search] https://github.com/currentsapi/awesome-vector-search

索引優化：

  1. 用zstd對文件進行壓縮

  2. 向量優化（vector quantization (VQ)）

  3. 主成分分析（[Principal component analysis (PCA)] https://en.wikipedia.org/wiki/Principal_component_analysis

    1. 主要用於降維，把向量維度減少，通過損失部分精度來獲取更小儲存體積

  4. 乘積量化（Product Quantization (PQ)）

    1. 用於壓縮和儲存大維向量

  5. Optimized Product Quantization (OPQ)

  6. CPU 和/或 GPU 的硬體加速

針對性能和準確性的權衡：

  1. 在相同的搜尋場景中，準確性往往意味著更高維更高精度的向量，但是這些向量的計算（無論是線性還是聚類）中，單個向量間的計算成本會隨之上升，使得整個召回過程效能下降

  2. 同時可以通過 nlist 、 nprobe 以及其他聚類、距離計算公式的調整來調整精度和效能

作者介紹

死敵wen，Elastic 認證工程師，搜尋架構師，10年+工作經驗，畢業於復旦大學。

部落格： https://blog.csdn.net/weixin_40601534

Github： https://github.com/godlockin

說明

上個月，死磕 Elasticsearch 知識星球搞了： “群智湧現”杯輸出倒逼輸入——Elastic乾貨輸出活動。

後續會不定期逐步推出系列文章，目的： 以文會友，“輸出倒逼輸入”。

更 短時間 更 快習得 更 多幹貨！

已帶領 88 位 球友 通過 Elastic 官方認證！

比同事 搶先 一步學習進階乾貨 ！

「」
「」