[[335094]]

▍1. 背景

在一些推薦系統、圖片檢索、文章去重等場景中，對基于特征數據進行 k 近鄰檢索有著廣泛的需求：

•  支持億級索引的檢索，同時要求非常高的檢索性能；
•  支持索引的批量實時更新；
•  支持多模型、多版本以靈活開展 ABTest 實驗；
•  支持過濾器、過期刪除以排除不符合特定條件的數據。

在經過調研后，發現已有的解決方案存在以下問題：   

•  在學術界中，已經存在有成熟并開源的 ANN 搜索庫，然而這些搜索庫僅僅是作為單機引擎存在，而不能作為高性能、可依賴、可拓展的分布式組件為推薦系統提供服務；
•  在業界中，大多數的組件都是基于 ANN 搜索庫做一層簡單的封裝，在可拓展、高可用上的表現達不到在線系統的要求；而對于少數在實現上已經較為成熟的分布式檢索系統，在功能上卻難以做到緊跟業務發展；
•  而在更新機制上，很多組件都是要么只支持離線更新、要么只支持在線接口更新，無法滿足在微信側小至秒級千數量、大至小時級億數量的索引更新需求，因此需要可以兼顧近實時更新及離線大批量更新的分布式系統。

基于上述的這些要求以及業內組件的限制，我們借助 WFS 和 Chubby 設計并實現了 SimSvr，它是一個高性能、功能豐富的特征檢索組件，具有以下特點：

•  分布式可伸縮的架構，支持億級以上的索引量，以及索引的并發加速查詢，實現了 10ms 以內檢索數億的索引；
•  高性能召回引擎，使用了召回性能極佳的 hnswlib 作為首選召回引擎，大部分請求可在 2ms 內完成檢索；
•  集群化管理，集成了完善的數據調度及動態路由功能；
•  多樣的更新機制，支持任務式更新及自動更新，同時也支持全量更新與增量更新，跨越秒級千數量到小時級億數量的索引更新；
•  讀寫分離的機制，在離線利用龐大的計算資源加速構建索引的同時，不影響在線服務的高性能讀；
•  豐富的功能特性，支持輕量 embedding kv 庫、單表多索引、多版本索引、過濾器、過期刪除等特性。

SimSvr 目前已廣泛應用于微信視頻號、看一看、搜一搜、微信安全、表情搜索等業務，接下來會闡述 SimSvr 的設計以及如何解決來自于業務的難題。

▍2. 檢索引擎

2.1 引擎的選擇

ANN 問題在學術界已被長期研究，并且已有成熟的開源 ANN 搜索庫存在，如 nmslib、hnswlib、faiss 等。在 SimSvr 中，性能及集群的存儲容量是最主要考量的兩個指標，因此選擇了以下兩個檢索引擎：

•  在 ann-benchmarks 中檢索性能最好的 hnswlib，能夠滿足在線服務對召回率及檢索耗時的高要求（大于 90% 召回率的情況下，能在 1ms 內完成召回）；
•  faiss 的 IVFx_HNSWy + PQz 算法，支持將向量壓縮 10 ~ 30 倍，能夠滿足資源有限情況下的高維大數據量的索引要求（億級索引數據，容納在內存 64G 的機器上）。

ANN檢索引擎效果對比

2.2 巧妙利用資源，提升 50% 的數據容納量

•     hnswlib 是單機檢索引擎，在資源使用方面僅考慮了單模型的情況；而 SimSvr 是提供在線服務的組件，一般容納了多個模型；
•     SimSvr 在大部分場景下，擁有讀寫分離的特點；  

    基于以上特點，我們在引入 hnswlib 之后，進行了資源整合，使得 SimSvr 單機情況下可以容納更多的模型索引：   

• 極限情況下（以 worker 線程數 80、部署 10 張 2kw 索引量的表為例）：   

• 現網運營中（以某現網模塊(11臺實例機器，worker 線程 240）為例）：

2.3 點積距離召回率從 62.6% 到 97.8% 的蛻變心路歷程

•  HNSW 算法在余弦距離表現優秀，但在點乘距離的數據集上存在效果差的情況；
•  點乘距離非度量空間（metric space)，不滿足三角不等式，距離比較沒有傳遞性；
  
  •   維基百科中關于度量空間的定義:       

• hnswlib 中說明點積屬于非度量空間：   

• 而在論文 Non-metric Similarity Graphs for

         Maximum Inner Product Search 中，提到了將點乘距離轉換為余弦距離計算的方法，我們將這種方法簡稱為 ip2cos；

在 ip2cos 距離轉換的理論基礎上，我們使用看一看視頻實時 DSSM 模型進行了實際召回情況的效果對比（64 維、ip 距離、100 萬索引數據量，進行 1 萬次查詢取平均耗時），并見證了 ip2cos 的神奇效果：

2.4 如何使用 faiss 省下 2h 的訓練時間并提升 30% 的召回率

• 在 faiss 中增加了 batch kmeans 聚類方法，在保證較好聚類效果的同時大幅加快訓練速度。IVF 系類方法訓練耗時主要體現在需要從數據中學習 nlist 個聚類中心，對于千萬級數據 nlist 的大小在 20 萬以上，在 cpu 上使用傳統 kmeans 方法訓練會非常耗時，下面展示在 128 維、IP 距離、1000 萬條數據的情況下 batch kmeans 對訓練速度的加速效果：

從結果中可以看到，在相同迭代輪次下，不使用 batch kmeans 的方法訓練耗時更長，且沒有很好收斂，導致召回率不高。

▍3. 總體設計

3.1 數據結構 - 為達成一個小目標，需要做出怎樣的改變

為了滿足單模塊多模型的需求，SimSvr 使用了表的概念進行多模型的管理；另外，為支持億級以上 HNSW 索引的表，并且希望能夠并發加速構建索引，我們根據單表的數據情況，將一張表分成了多個 sharding，使得每個 sharding 承擔表數據的其中一部分：

tablei 的索引，由 shard0、shard1、…、shardn 構成一份完整的索引數據；而 sect 的數量則決定了表的副本數（可用于伸縮讀能力、提供容災等）。

在 SimSvr 中，我們將一個 shardi_sectj 稱之為一個 container，這是 SimSvr 中最小的數據調度和加載單位。

3.2 系統架構 - 如何支撐億級索引、5毫秒級的檢索

SimSvr 架構

•  SimSvr 與 FeatureKV 一樣，涉及的外部依賴也是三個：
  
  •   Chubby：用來保存元數據、路由信息、worker 資源信息等；SimSvr 中的數據協同、分布式任務執行均是依賴于 Chubby；
  •   USER_FS：業務側存放原始數據的分布式文件系統，可以是 WFS/HDFS，該文件系統的路徑及信息保存在表/任務的元信息中；
  •   SimSvr_FS：Simsvr 使用的分布式文件系統，用于存放生成的索引文件或者原始的增量數據文件。
•  worker
  
  •   負責對外提供檢索服務，通過對 Chubby 的輪詢檢查索引的更新，進而將索引加載至本機以提供服務；
  •   每臺 worker 負責的數據，由 master 進行調度，worker 根據 master 保存在 Chubby 上的分配信息進行數據的加載/卸載；
  •   worker 的數據是根據 master 分配得來的，除此之外沒有其他狀態的差別，因此 worker 是易于擴縮容的。
•  master
  
  •   數據調度：通過表的元信息及 worker 狀態，將未分配的數據或者失效 worker 上的數據調度給其他有效的 worker；
  •   生成路由表：根據 worker 的數據加載情況及狀態，生成集群的路由表；
  •   感知數據更新：檢查表的自動更新目錄，若最大數字目錄發生了增長，則建一個任務以供 trainer 進行索引的構建；
  •   master 是一個無狀態的服務，通過 Chubby 提供的分布式鎖保證數據調度以及路由生成的唯一執行。
•  trainer
  
  •   負責構建表的索引及資源回收；
  •   trainer 單次可構建一張表中一個 sharding 的索引，因此如果表有多個 sharding 時，可通過增加 trainer 的個數實現構建索引的并發加速；
  •   trainer 是無狀態的服務，通常部署在微信 Yard 系統上，充分了利用微信閑置機器上的資源。
•  數據自動更新
  
  •   在建表時，對其指定了一個 fs 的目錄，該目錄下，是一系列數字遞增的目錄；
  •   當業務側需要更新索引時，將最新的數據 dump 到更大的數字目錄中；
  •   master 感知最大數字目錄的更新，從而更新了元信息；
  •   trainer 感知元信息的更新并觸發建索引；
  •   worker 加載索引完成索引的更新。
•  數據任務式更新
  
  •   由業務側主動通過接口的調用，創建一個索引任務；
  •   在索引任務中，指定了數據的配置信息（如 fs 信息及路徑等）；
  •   trainer 按照表的任務序列，執行任務并構建索引；
  •   worker 加載索引完成索引的更新。

3.3 數據調度 - 雞蛋怎么放在多個籃子中

•     SimSvr 在每張表創建時就指定了 sharding 數 n 及 sect 數 m，因此這張表擁有了 n * m 個 Conatiner 以供 master 調度；
•     master 會根據 worker 的健康情況及資源使用情況進行數據的調度及路由表的生成；
•     路由表帶有遞增的版本號，可根據版本號感知路由的變化。   

•  worker 定期輪詢 Chubby 獲取數據的調度情況及最新的路由表信息；
•  client 首次請求時，將隨機請求一臺 worker 獲取最新的路由表信息并將其緩存在本地；
•  client 在本地有路由表的情況下，將根據表的數據分布情況，帶上版本號并發地向目標 worker 發起請求，最終合并所有 sharding 的結果，將其返回給業務端。

3.4 系統拓展 - 籃子裝滿了該怎么辦

•  SimSvr 將表拆分成了更小粒度的數據調度單位，且不要求每臺機器上的數據一樣，因此可以用拓展機器的方式，將集群的存儲容量擴大；
•  對于單表而言，當讀能力達到瓶頸時，可以單獨擴展此表的讀副本數；

▍4. 近實時增量更新的挑戰 - 十秒內完成索引的更新

•  數據一致性與持久化
  
  •   對于大多數的分布式存儲組件來說，都是使用 raft 或者 paxos 等一致性協議保證數據一致性并持久化至本機上；
  •   對于 SimSvr 來說，每張表會被分為多個 sharding，且 sharding 數不保證為奇數；
  •   在 worker 中加入一致性組件及額外的存儲引擎，會使得整體的結構變得復雜；
  •   最終在考量后，結合業務的批量增量更新的特點，選擇了先將數據落地 fs，再由 worker 拉取數據加載的方案；在這種方案下，1000 以內數量的 key 插入，能夠在 10s 內完成，達到了業務的要求。

增量持久化

•  增量更新的性能保障
  
  •   由于在線建索引是非常消耗 cpu 資源的過程，因此為了不影響現網的讀服務，worker 僅提供少量的 cpu 資源用于增量數據的更新；
  •   對于小批量的增量數據，worker 可以直接加載存放在 fs 上的數據并直接進行索引的在線插入；
  •   對于大批量的增量數據，為了避免影響讀服務及大增量更新慢的問題，SimSvr 將大批量數據在 trainer 進行合并且并發重建索引，最后再由 worker 直接加載建好的索引。

增量更新

▍5. 豐富的功能特性

5.1 支持額外的特征存儲庫

•  在推薦系統中，同一個模型，產生的數據除了用于檢索的索引庫，常常還有視頻特征/用戶畫像的特征數據；
•  這類數據，僅僅只需要查詢的功能，并且與同個模型同個版本產出的索引庫相互作用，產生正確的召回效果；
•  基于這種原子性更新的特性，SimSvr 支持了額外的特征存儲庫，用于存儲與模型一同更新且僅用于查詢的特征數據，幫助業務省去了數據同步與對齊的煩惱。

5.2 支持原子性更新的單表多索引

•  在推薦系統中，ABTest 是非常常見的，多個模型的實驗往往也是需要同時進行的；
•  另外，在某些場景下，同一個模型會產生不同的索引數據，在線上使用時要求同模型的索引要同時生效；
•  對于以上兩種情況，如果使用多表支持多模型，在索引更新上存在生效時間的差異從而無法支持；
•  SimSvr 對于這種情況，支持了同一張表多份索引的原子性更新，保證了索引能夠同時生效。

5.3 多版本索引

•  在 ABTest 場景下，除了有多模型間的實驗，還有相同模型不同版本數據的實驗；
•  在相同模型中，版本迭代/不同版本進行實驗的場景是廣泛存在的；
•  如果使用多表支持這樣的多版本索引，不管在業務方的使用上，還是在 SimSvr 的管理上，都顯得不是那么地優雅；
•  對此，SimSvr 支持了同一張表的多版本管理，并且多版本支持在現網下同時進行服務，業務可以按需請求目標版本，進行靈活的實驗。

5.4 支持布隆過濾器、閾值過濾器等

•  在視頻號場景中，業務使用 SimSvr 對視頻進行索引；
•  在使用某個用戶的特征進行召回時，常常召回了許多用戶已看過的視頻，影響用戶體驗；
•  通過增加召回結果并在結果中進行過濾，對于重度用戶，一樣存在上述問題，并且還會導致不必要的性能開銷；
•  SimSvr 改造 hnswlib，嵌入了過濾器的邏輯，使得其支持在檢索過程中實時對符合特定條件的 key 進行過濾，保證了召回結果的有效性。

5.5 支持過期刪除

•  對于一些推薦系統來說，對于數據的時效性要求是非常高的，在數據過了其最佳召回時間段之后，就不應該出現在召回結果中，以免出現不合時宜的尷尬；
•  SimSvr 支持導入帶過期時間的數據，在現網召回過程中，實時淘汰過期的 key 以達到準確的召回要求。

▍6. 現網運營情況

•  SimSvr 目前已部署 160+ 個模型索引，使用邏輯核 8000+，總索引量超過 20 億特征向量，廣泛應用于視頻號、看一看、搜一搜等推薦業務中。
•  搜一搜基于 SimSvr 建立小程序優質文章的向量索引，提升小程序文章搜索的優質結果召回率。新方案相比舊方案，優質結果召回率提升 7%；
•  搜一搜使用 SimSvr 檢索視頻指紋，進行相似視頻去重；單表索引量高達 1.7 億 * 128 維，檢索平均耗時小于 8ms，日檢索量 12.5 億。

▍7. 總結

隨著推薦系統的強勢發展，特征檢索的使用場景越來越廣泛。而作為基礎組件，除了要擁有支持億級索引的基本素養外，在功能特性上也需要不斷迎合業務的發展。因此我們開發了 SimSvr，搭配特征存儲 FeatureKV，在視頻號、看一看、搜一搜等推薦系統中發揮了重要的作用。