1、引言

《Elasticsearch 向量搜索的工程化實戰(zhàn)》文章一經(jīng)發(fā)出，收到很多留言。讀者對向量檢索和普通檢索的區(qū)別充滿了好奇，所以就有了今天的文章。

2、普通搜索 VS 向量搜索

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

2.1 overview

首先，我們先來了解一下這兩種搜索方案的特點以及各自的優(yōu)缺點

2.1.1 普通搜索

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

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

1. 具有較高的索引速度
2. 中等的索引大小
3. 較高的查詢速度（在大數(shù)據(jù)量的場景）
4. 良好的縮放比例
5. （對于精確匹配）具有完美的精度
6. 精確且無損的詞元和詞組搜索
7. 只能通過詞元的精確匹配做召回
8. 無法捕獲語義與相似性
1. ES 的 synonym 是類似在同一個位置把所有預先定義的同義詞同時索引來實現(xiàn)的

2.1.2 向量搜索

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

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

1. 較慢的索引速度
2. 較大的索引大小
3. 較慢的查詢速度（在大數(shù)據(jù)量的場景）
4. 有限的縮放比例
5. （對于精確匹配）具有較低的精度
6. 較差的詞元和詞組的搜索能力
7. 通過向量（某些解決方案中可以包含一部分標量字段）進行召回
8. 對近似語義的捕獲程度較高，可以很好的處理同/近義詞

2.1.3 小結

通過普通搜索或者向量搜索構建個簡單的搜索引擎系統(tǒng)并不難，但是隨著數(shù)據(jù)量的增長、并發(fā)請求的增加、數(shù)據(jù)使用場景的變化，搜索引擎系統(tǒng)需要更多的組件一同完成其功能，如搜索前的數(shù)據(jù)預處理，到搜索過程中的query理解、改寫、自動補全，緩存，分數(shù)計算，地理位置信息計算，到返回結果前的結果排序和過濾，結果分頁等。

2.2 數(shù)據(jù)結構與搜索算法

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

2.2.1 普通搜索

2.2.1.1 倒排索引

倒排索引是一個類似 hashmap 的數(shù)據(jù)結構，它的 key 是每個詞元，而 value 是一個包含這個詞元的所有文檔的 id 列表（也可能是 hashset、鏈表等結構），這樣的數(shù)據(jù)結構的好處在于對于一個詞元，可以用接近 O(1) 的代價來找到包含它的文章。有時倒排索引中也會包含詞元在文檔中的位置信息，這是為了能在搜索時，在考慮了 query 中的詞元信息之外，也把詞元的順序也一并考慮進去。

2.2.1.2 LSM樹

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

2.2.1.3 帶版本的數(shù)據(jù)提交

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

2.2.1.4 ? 升級和調優(yōu)

存儲：

1. Size-tiered compaction
2. Leveled compaction
3. Sharded compaction

索引：

1. zstd（Zstandard）壓縮
2. Elias-Fano 編碼
3. 停止詞
4. 詞干
5. ngram 索引

2.2.2 向量搜索

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

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

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 索引數(shù)據(jù)

向量搜索的數(shù)據(jù)索引不同于普通搜索的分詞，他們會需要先通過各種 machine learning、deep learning 技術將文檔、句子、詞組等轉化成向量存進搜索引擎，搜索引擎會根據(jù)配置使用距離計算模塊對向量進行聚類保存。

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

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 召回數(shù)據(jù)

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

1. 線性搜索
1. 顧名思義，線性搜索就是將 query 向量和索引中所有的向量依次比較，再按距離排序
2. ES 對 Dense Vector 字段的處理就是線性搜索
3. 這是最簡單也是最慢的方式，而且隨著索引數(shù)據(jù)量的上升，召回時間也會隨之大幅上升
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. 圍繞中心分區(qū)（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. 是向量搜索中較為常用的方式，通過預先配置的參數(shù)對向量進行 KNN 聚類的方式進行索引
10. 召回時會通過尋找較近的核向量的方式來找到 topK 的向量進行
11. 主要包含的一些方式：

2.2.2.3 升級和調優(yōu)

其他一些可用的開源庫

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

索引優(yōu)化：

1. 用zstd對文檔進行壓縮
2. 向量優(yōu)化（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年+工作經(jīng)驗，畢業(yè)于復旦大學。

博客：https://blog.csdn.net/weixin_40601534

Github：https://github.com/godlockin

說明

上個月，死磕 Elasticsearch 知識星球搞了：“群智涌現(xiàn)”杯輸出倒逼輸入——Elastic干貨輸出活動。

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

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

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