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，在視頻號、看一看、搜一搜等推薦系統中發揮了重要的作用。

作者：sauronzhang、flashlin、fengshanliu，微信后臺開發工程師