[[335094]]

▍1. 背景

在一些推薦系統(tǒng)、圖片檢索、文章去重等場(chǎng)景中，對(duì)基于特征數(shù)據(jù)進(jìn)行 k 近鄰檢索有著廣泛的需求：

•  支持億級(jí)索引的檢索，同時(shí)要求非常高的檢索性能；
•  支持索引的批量實(shí)時(shí)更新；
•  支持多模型、多版本以靈活開(kāi)展 ABTest 實(shí)驗(yàn)；
•  支持過(guò)濾器、過(guò)期刪除以排除不符合特定條件的數(shù)據(jù)。

在經(jīng)過(guò)調(diào)研后，發(fā)現(xiàn)已有的解決方案存在以下問(wèn)題：   

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

基于上述的這些要求以及業(yè)內(nèi)組件的限制，我們借助 WFS 和 Chubby 設(shè)計(jì)并實(shí)現(xiàn)了 SimSvr，它是一個(gè)高性能、功能豐富的特征檢索組件，具有以下特點(diǎn)：

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

SimSvr 目前已廣泛應(yīng)用于微信視頻號(hào)、看一看、搜一搜、微信安全、表情搜索等業(yè)務(wù)，接下來(lái)會(huì)闡述 SimSvr 的設(shè)計(jì)以及如何解決來(lái)自于業(yè)務(wù)的難題。

▍2. 檢索引擎

2.1 引擎的選擇

ANN 問(wèn)題在學(xué)術(shù)界已被長(zhǎng)期研究，并且已有成熟的開(kāi)源 ANN 搜索庫(kù)存在，如 nmslib、hnswlib、faiss 等。在 SimSvr 中，性能及集群的存儲(chǔ)容量是最主要考量的兩個(gè)指標(biāo)，因此選擇了以下兩個(gè)檢索引擎：

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

ANN檢索引擎效果對(duì)比

2.2 巧妙利用資源，提升 50% 的數(shù)據(jù)容納量

•     hnswlib 是單機(jī)檢索引擎，在資源使用方面僅考慮了單模型的情況；而 SimSvr 是提供在線服務(wù)的組件，一般容納了多個(gè)模型；
•     SimSvr 在大部分場(chǎng)景下，擁有讀寫(xiě)分離的特點(diǎn)；  

    基于以上特點(diǎn)，我們?cè)谝?hnswlib 之后，進(jìn)行了資源整合，使得 SimSvr 單機(jī)情況下可以容納更多的模型索引：   

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

• 現(xiàn)網(wǎng)運(yùn)營(yíng)中（以某現(xiàn)網(wǎng)模塊(11臺(tái)實(shí)例機(jī)器，worker 線程 240）為例）：

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

•  HNSW 算法在余弦距離表現(xiàn)優(yōu)秀，但在點(diǎn)乘距離的數(shù)據(jù)集上存在效果差的情況；
•  點(diǎn)乘距離非度量空間（metric space)，不滿足三角不等式，距離比較沒(méi)有傳遞性；
  
  •   維基百科中關(guān)于度量空間的定義:       

• hnswlib 中說(shuō)明點(diǎn)積屬于非度量空間：   

• 而在論文 Non-metric Similarity Graphs for

         Maximum Inner Product Search 中，提到了將點(diǎn)乘距離轉(zhuǎn)換為余弦距離計(jì)算的方法，我們將這種方法簡(jiǎn)稱為 ip2cos；

在 ip2cos 距離轉(zhuǎn)換的理論基礎(chǔ)上，我們使用看一看視頻實(shí)時(shí) DSSM 模型進(jìn)行了實(shí)際召回情況的效果對(duì)比（64 維、ip 距離、100 萬(wàn)索引數(shù)據(jù)量，進(jìn)行 1 萬(wàn)次查詢?nèi)∑骄臅r(shí)），并見(jiàn)證了 ip2cos 的神奇效果：

2.4 如何使用 faiss 省下 2h 的訓(xùn)練時(shí)間并提升 30% 的召回率

• 在 faiss 中增加了 batch kmeans 聚類方法，在保證較好聚類效果的同時(shí)大幅加快訓(xùn)練速度。IVF 系類方法訓(xùn)練耗時(shí)主要體現(xiàn)在需要從數(shù)據(jù)中學(xué)習(xí) nlist 個(gè)聚類中心，對(duì)于千萬(wàn)級(jí)數(shù)據(jù) nlist 的大小在 20 萬(wàn)以上，在 cpu 上使用傳統(tǒng) kmeans 方法訓(xùn)練會(huì)非常耗時(shí)，下面展示在 128 維、IP 距離、1000 萬(wàn)條數(shù)據(jù)的情況下 batch kmeans 對(duì)訓(xùn)練速度的加速效果：

從結(jié)果中可以看到，在相同迭代輪次下，不使用 batch kmeans 的方法訓(xùn)練耗時(shí)更長(zhǎng)，且沒(méi)有很好收斂，導(dǎo)致召回率不高。

▍3. 總體設(shè)計(jì)

3.1 數(shù)據(jù)結(jié)構(gòu) - 為達(dá)成一個(gè)小目標(biāo)，需要做出怎樣的改變

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

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

在 SimSvr 中，我們將一個(gè) shardi_sectj 稱之為一個(gè) container，這是 SimSvr 中最小的數(shù)據(jù)調(diào)度和加載單位。

3.2 系統(tǒng)架構(gòu) - 如何支撐億級(jí)索引、5毫秒級(jí)的檢索

SimSvr 架構(gòu)

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

3.3 數(shù)據(jù)調(diào)度 - 雞蛋怎么放在多個(gè)籃子中

•     SimSvr 在每張表創(chuàng)建時(shí)就指定了 sharding 數(shù) n 及 sect 數(shù) m，因此這張表?yè)碛辛?n * m 個(gè) Conatiner 以供 master 調(diào)度；
•     master 會(huì)根據(jù) worker 的健康情況及資源使用情況進(jìn)行數(shù)據(jù)的調(diào)度及路由表的生成；
•     路由表帶有遞增的版本號(hào)，可根據(jù)版本號(hào)感知路由的變化。   

•  worker 定期輪詢 Chubby 獲取數(shù)據(jù)的調(diào)度情況及最新的路由表信息；
•  client 首次請(qǐng)求時(shí)，將隨機(jī)請(qǐng)求一臺(tái) worker 獲取最新的路由表信息并將其緩存在本地；
•  client 在本地有路由表的情況下，將根據(jù)表的數(shù)據(jù)分布情況，帶上版本號(hào)并發(fā)地向目標(biāo) worker 發(fā)起請(qǐng)求，最終合并所有 sharding 的結(jié)果，將其返回給業(yè)務(wù)端。

3.4 系統(tǒng)拓展 - 籃子裝滿了該怎么辦

•  SimSvr 將表拆分成了更小粒度的數(shù)據(jù)調(diào)度單位，且不要求每臺(tái)機(jī)器上的數(shù)據(jù)一樣，因此可以用拓展機(jī)器的方式，將集群的存儲(chǔ)容量擴(kuò)大；
•  對(duì)于單表而言，當(dāng)讀能力達(dá)到瓶頸時(shí)，可以單獨(dú)擴(kuò)展此表的讀副本數(shù)；

▍4. 近實(shí)時(shí)增量更新的挑戰(zhàn) - 十秒內(nèi)完成索引的更新

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

增量持久化

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

增量更新

▍5. 豐富的功能特性

5.1 支持額外的特征存儲(chǔ)庫(kù)

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

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

•  在推薦系統(tǒng)中，ABTest 是非常常見(jiàn)的，多個(gè)模型的實(shí)驗(yàn)往往也是需要同時(shí)進(jìn)行的；
•  另外，在某些場(chǎng)景下，同一個(gè)模型會(huì)產(chǎn)生不同的索引數(shù)據(jù)，在線上使用時(shí)要求同模型的索引要同時(shí)生效；
•  對(duì)于以上兩種情況，如果使用多表支持多模型，在索引更新上存在生效時(shí)間的差異從而無(wú)法支持；
•  SimSvr 對(duì)于這種情況，支持了同一張表多份索引的原子性更新，保證了索引能夠同時(shí)生效。

5.3 多版本索引

•  在 ABTest 場(chǎng)景下，除了有多模型間的實(shí)驗(yàn)，還有相同模型不同版本數(shù)據(jù)的實(shí)驗(yàn)；
•  在相同模型中，版本迭代/不同版本進(jìn)行實(shí)驗(yàn)的場(chǎng)景是廣泛存在的；
•  如果使用多表支持這樣的多版本索引，不管在業(yè)務(wù)方的使用上，還是在 SimSvr 的管理上，都顯得不是那么地優(yōu)雅；
•  對(duì)此，SimSvr 支持了同一張表的多版本管理，并且多版本支持在現(xiàn)網(wǎng)下同時(shí)進(jìn)行服務(wù)，業(yè)務(wù)可以按需請(qǐng)求目標(biāo)版本，進(jìn)行靈活的實(shí)驗(yàn)。

5.4 支持布隆過(guò)濾器、閾值過(guò)濾器等

•  在視頻號(hào)場(chǎng)景中，業(yè)務(wù)使用 SimSvr 對(duì)視頻進(jìn)行索引；
•  在使用某個(gè)用戶的特征進(jìn)行召回時(shí)，常常召回了許多用戶已看過(guò)的視頻，影響用戶體驗(yàn)；
•  通過(guò)增加召回結(jié)果并在結(jié)果中進(jìn)行過(guò)濾，對(duì)于重度用戶，一樣存在上述問(wèn)題，并且還會(huì)導(dǎo)致不必要的性能開(kāi)銷；
•  SimSvr 改造 hnswlib，嵌入了過(guò)濾器的邏輯，使得其支持在檢索過(guò)程中實(shí)時(shí)對(duì)符合特定條件的 key 進(jìn)行過(guò)濾，保證了召回結(jié)果的有效性。

5.5 支持過(guò)期刪除

•  對(duì)于一些推薦系統(tǒng)來(lái)說(shuō)，對(duì)于數(shù)據(jù)的時(shí)效性要求是非常高的，在數(shù)據(jù)過(guò)了其最佳召回時(shí)間段之后，就不應(yīng)該出現(xiàn)在召回結(jié)果中，以免出現(xiàn)不合時(shí)宜的尷尬；
•  SimSvr 支持導(dǎo)入帶過(guò)期時(shí)間的數(shù)據(jù)，在現(xiàn)網(wǎng)召回過(guò)程中，實(shí)時(shí)淘汰過(guò)期的 key 以達(dá)到準(zhǔn)確的召回要求。

▍6. 現(xiàn)網(wǎng)運(yùn)營(yíng)情況

•  SimSvr 目前已部署 160+ 個(gè)模型索引，使用邏輯核 8000+，總索引量超過(guò) 20 億特征向量，廣泛應(yīng)用于視頻號(hào)、看一看、搜一搜等推薦業(yè)務(wù)中。
•  搜一搜基于 SimSvr 建立小程序優(yōu)質(zhì)文章的向量索引，提升小程序文章搜索的優(yōu)質(zhì)結(jié)果召回率。新方案相比舊方案，優(yōu)質(zhì)結(jié)果召回率提升 7%；
•  搜一搜使用 SimSvr 檢索視頻指紋，進(jìn)行相似視頻去重；單表索引量高達(dá) 1.7 億 * 128 維，檢索平均耗時(shí)小于 8ms，日檢索量 12.5 億。

▍7. 總結(jié)

隨著推薦系統(tǒng)的強(qiáng)勢(shì)發(fā)展，特征檢索的使用場(chǎng)景越來(lái)越廣泛。而作為基礎(chǔ)組件，除了要擁有支持億級(jí)索引的基本素養(yǎng)外，在功能特性上也需要不斷迎合業(yè)務(wù)的發(fā)展。因此我們開(kāi)發(fā)了 SimSvr，搭配特征存儲(chǔ) FeatureKV，在視頻號(hào)、看一看、搜一搜等推薦系統(tǒng)中發(fā)揮了重要的作用。