一、背景

隨著交易和社區(qū)搜索業(yè)務(wù)穩(wěn)步快跑，基建側(cè)引擎越來越復(fù)雜，之前搜索底層索引查詢結(jié)構(gòu)已經(jīng)存在較為嚴(yán)重的性能瓶頸。成本和運(yùn)維難度越來越高。在開發(fā)效率上和引擎的穩(wěn)定性上，也暴露出了很多需要解決的運(yùn)維穩(wěn)定性和開發(fā)效率短板。而在引擎的業(yè)務(wù)層部分也需要逐步升級，來解決當(dāng)前引擎中召回層和業(yè)務(wù)層中各個(gè)模塊強(qiáng)耦合，難維護(hù)，迭代效率低下等問題。

二、引擎開發(fā)技術(shù)方案

DSearch1.0索引層整體結(jié)構(gòu)

DSearch1.0的索引結(jié)構(gòu)比較特殊一些，總體上使用了全局rcu的設(shè)計(jì)思想，整體架構(gòu)上單寫多讀，所以實(shí)現(xiàn)了并發(fā)高性能無鎖讀，內(nèi)部數(shù)據(jù)結(jié)構(gòu)都是無鎖數(shù)據(jù)結(jié)構(gòu)，所以查詢性能高。在寫操作上因?yàn)閞cu機(jī)制實(shí)現(xiàn)寫入無鎖。整體上優(yōu)點(diǎn)讀性能高，沒有傳統(tǒng)段合并操作帶來的磁盤抖動(dòng)。缺點(diǎn)是索引地址和操作系統(tǒng)強(qiáng)相關(guān)，運(yùn)維復(fù)雜，熱更新受限。全局地址分配難以并行寫入，構(gòu)建瓶頸明顯。無法對浪費(fèi)的內(nèi)存進(jìn)行回收導(dǎo)致內(nèi)存空間利用率低，索引空間占用大。總體結(jié)構(gòu)如圖所示：

DSearch2.0的索引升級

DSearch2.0分段索引整體設(shè)計(jì)

引擎2.0索引升級采用經(jīng)典段合并架構(gòu)，除了繼承了段合并中優(yōu)異的高性能寫入性能和查詢已經(jīng)索引合并等優(yōu)勢外，針對段合并中頻繁的正排字段更新等帶來的高IO缺點(diǎn)。我們設(shè)計(jì)了新的正排字段原地更新索引，使新的DSearch2.0引擎擁有Redis的高性能寫入和查詢，也擁有l(wèi)ucene的緊湊索引和索引合并帶來的內(nèi)存空間節(jié)省的優(yōu)勢。

※ 索引段結(jié)構(gòu)

1. 每個(gè)索引段包含了文檔文件，用于緊湊存放document中的各個(gè)字段的詳細(xì)信息。字符串池文件是對document中所有的字符串進(jìn)行統(tǒng)一順序存儲，同時(shí)對字符串進(jìn)行ID化，每個(gè)字符串ID就是對應(yīng)于字符串池中的offset偏移。
2. 可變數(shù)組文件是專門存放數(shù)組類型的數(shù)據(jù)，緊湊型連續(xù)存放，當(dāng)字段更新的時(shí)候采用文件追加append進(jìn)行寫。最終內(nèi)存回收通過段之間的compaction進(jìn)行。FST索引文件是專門存放document中全部字符串索引。每個(gè)fst的node節(jié)點(diǎn)存放了該字符串在字符串池中的偏移offset。而通過字符串的offset，能夠快速在倒排termoffset數(shù)組上二分查找定位到term的倒排鏈。
3. 倒排文件是專門存放倒排docid，詞頻信息、位置信息等倒排信息，其中docid倒排鏈數(shù)據(jù)結(jié)構(gòu)會(huì)根據(jù)生成段的時(shí)候計(jì)算docid和總doc數(shù)的密度來做具體判斷，如果密度高于一定閾值就會(huì)使用bitmap數(shù)據(jù)結(jié)構(gòu)，如果小于一定閾值會(huì)使用array的數(shù)據(jù)結(jié)構(gòu)。
4. 標(biāo)記刪除delete鏈主要是用于記錄段中被刪除的document，刪除操作是軟刪除，在最后查詢邏輯操作的時(shí)候進(jìn)行最后的過濾。
5. 實(shí)時(shí)增量的trie樹結(jié)構(gòu)，實(shí)時(shí)增量段中的前綴檢索和靜態(tài)段中的前綴檢索數(shù)據(jù)結(jié)構(gòu)不一樣，trie因?yàn)槟軌蜻M(jìn)行實(shí)時(shí)更新所以在內(nèi)存中使用trie樹。
6. 段中的metadata文件，metadata文件是記錄每個(gè)段中的核心數(shù)據(jù)的地方，主要記錄段內(nèi)doc數(shù)量，段內(nèi)delete文檔比例，實(shí)時(shí)段的metadata會(huì)記錄kafka的offset等核心數(shù)據(jù)。

Document文檔和索引結(jié)構(gòu)

※ Document文檔數(shù)據(jù)結(jié)構(gòu)

1. Document文檔使用緊湊型存儲，其中array和字符串類型單獨(dú)存放，其他字段連續(xù)存放，string和array字段存放。
2. array字段類型數(shù)據(jù)直接存放在可變數(shù)組文件區(qū)，連續(xù)追加寫。
3. string字符串池對所有字符串進(jìn)行連續(xù)存放，多個(gè)doc中同一個(gè)字符串引用同一個(gè)字符串地址，節(jié)省大量字符串存放空間。

※ 倒排索引文件結(jié)構(gòu)

1. 倒排索引文件存放docid倒排和Tf以及位置position數(shù)據(jù)。其中內(nèi)存實(shí)時(shí)段中的倒排索引數(shù)據(jù)結(jié)構(gòu)是固定一種類型array類型。而內(nèi)存實(shí)時(shí)段固化為靜態(tài)段的時(shí)候，倒排數(shù)據(jù)結(jié)構(gòu)會(huì)根據(jù)docid中的密度進(jìn)行選擇array和bitmap存儲。當(dāng)docid密度大于一定閾值是bitmap，反之是array結(jié)構(gòu)。
2. Tf數(shù)據(jù)結(jié)構(gòu)是一個(gè)uint16的數(shù)組，數(shù)組長度和docid的數(shù)組長度一致，所以當(dāng)確定了某個(gè)docid時(shí)候，也隨即確定了它的tf信息。
3. postion信息存儲是一個(gè)二維數(shù)組的格式，第一層數(shù)組存放的是對應(yīng)于term的在字符串池的offset，因?yàn)閠erm在字符串池中已經(jīng)ID化，所以offset可以表示唯一term。第二層數(shù)組是該term在字段中多次出現(xiàn)的位置，使用uint16存儲。

※ 前綴檢索文件

1. FST靜態(tài)段文件
   a. 靜態(tài)段中前綴是fst的數(shù)據(jù)結(jié)構(gòu)，因?yàn)閒st一旦建立是不能夠進(jìn)行修改的，所以在段合并的時(shí)候需要對所有term進(jìn)行排序然后再構(gòu)建fst結(jié)構(gòu)。
   b. fst的node節(jié)點(diǎn)存放了對應(yīng)于term的字符串池的offset。當(dāng)需要查詢一個(gè)term的倒排結(jié)構(gòu)時(shí)候，需要先查詢該term的字符串池的offset，然后拿該offset去倒排的termoffset文件中二分查找找到對應(yīng)的倒排positionlist結(jié)構(gòu)拿到對應(yīng)倒排。所以一次term到倒排的查詢需要查詢一次fst+一次二分查詢。
   c. term到倒排的查詢一次fst+一次二分查找效率不高，所以針對term到倒排查詢，新增了第二種HashMap索引，直接通過term到倒排的offset索引，這個(gè)選項(xiàng)在建表的時(shí)候可以配置。
2. 實(shí)時(shí)段RcuTrie樹索引
   a. 實(shí)時(shí)段中需要支持邊寫邊讀，前綴檢索需要支持并發(fā)讀寫。引擎中trie樹是rcu實(shí)現(xiàn)，單線程更新，多線程并發(fā)讀，trie樹寫更新節(jié)點(diǎn)內(nèi)存延遲回收。

倒排索引和查詢樹邏輯

※ 倒排鏈優(yōu)化

1. DSearch1.0的roaringbimap倒排索引在低密度數(shù)據(jù)量上存在一些瓶頸，比如對于倒排鏈比較短的情況下，roaringbitmap的container大部分都是array結(jié)構(gòu)，在倒排鏈查詢和合并都會(huì)進(jìn)行一次二分查找，在大面積的倒排鏈合并中是個(gè)相當(dāng)大的性能瓶頸。
2. 針對上面所說的情況對roaringbitmap進(jìn)行了精簡，只存array或者bitmap合并的時(shí)候不需要查找，直接鏈?zhǔn)胶喜ⅰ?/span>

※ 邏輯樹合并優(yōu)化

1. DSearch2.0重點(diǎn)從邏輯語法樹和倒排入手，優(yōu)化語法樹，減少合并樹高，從二叉樹合并變成單層合并。
2. 優(yōu)化倒排鏈合并方式，采用原地倒排鏈合并，消除倒排合并臨時(shí)對象，同時(shí)引入多線程并行合并，減少長尾提高性能。

增量更新邏輯

※ 增量實(shí)時(shí)寫入邏輯

1. 引擎支持多個(gè)并發(fā)實(shí)時(shí)段，這個(gè)由配置文件通過配置來進(jìn)行配置。多個(gè)實(shí)時(shí)段能夠提升并發(fā)寫入的性能。
2. 每個(gè)實(shí)時(shí)段對應(yīng)一個(gè)寫入隊(duì)列，提高并發(fā)寫入吞吐。
3. 每個(gè)段真實(shí)寫入一條信息會(huì)同步原子更新消費(fèi)的kafka的offset，用于對后面進(jìn)程重啟等恢復(fù)數(shù)據(jù)做準(zhǔn)備。
4. 當(dāng)進(jìn)程重啟或者異常退出時(shí)候，會(huì)讀取metadata文件中的最后一條kafka offset進(jìn)行重新消費(fèi)增量在內(nèi)存中重新構(gòu)建新的正排、文檔和倒排等信息，完成數(shù)據(jù)的恢復(fù)。

實(shí)時(shí)段固化和段合并策略

※ 實(shí)時(shí)段固化邏輯：

1. 當(dāng)實(shí)時(shí)段內(nèi)隨著增量寫，doc文件大小超過128M時(shí)候會(huì)進(jìn)行內(nèi)存實(shí)時(shí)段固化操作。
2. 固化操作開始時(shí)，會(huì)先生成新的內(nèi)存實(shí)時(shí)段，老的內(nèi)存實(shí)時(shí)段會(huì)變成只讀內(nèi)存段。
3. 遍歷按整個(gè)只讀內(nèi)存段，構(gòu)建新的索引和新的正排結(jié)構(gòu)生成新的靜態(tài)段。

※ 段合并策略：

1. 實(shí)時(shí)段固化的小靜態(tài)段因?yàn)榇笮”容^小，會(huì)優(yōu)先和之前固化后的小段進(jìn)行合并，按照1，2，4，8進(jìn)行合并，逐步合并成靜態(tài)段最大的上限。
2. 靜態(tài)段的合并觸發(fā)策略是當(dāng)靜態(tài)段中delete的doc比例超過了30%會(huì)觸發(fā)靜態(tài)段之間的合并，合并會(huì)按照近鄰合并原則，從左右近鄰中選取一個(gè)最小doc數(shù)的段進(jìn)行合并，進(jìn)而新生成一個(gè)新的段。

查詢和更新中的并發(fā)控制

※ 查詢流程

引擎查詢時(shí)候，先遍歷查詢實(shí)時(shí)段，然后再查詢靜態(tài)段。實(shí)時(shí)段查詢存在最大增量查詢截?cái)?，?dāng)實(shí)時(shí)段查詢到最大增量截?cái)鄷r(shí)實(shí)時(shí)段停止查詢。

實(shí)時(shí)段查詢后，查詢靜態(tài)段。靜態(tài)段中包含了全量構(gòu)建索引的全量最大offset記錄同時(shí)全量的doc是通過質(zhì)量分進(jìn)行排序，所以在全量段查詢的時(shí)候，先遍歷質(zhì)量分最大的全量段，逐步往后面靜態(tài)段查詢，直到查詢到全量截?cái)唷?/span>

實(shí)時(shí)段查詢和靜態(tài)段查詢結(jié)果進(jìn)行merge作為最終的查詢結(jié)果。

※ 更新并發(fā)控制

因?yàn)镈Search2.0的索引更新是直接在實(shí)時(shí)段或者靜態(tài)段進(jìn)行更新，所以存在多線程讀寫問題。尤其是正排字段更新寫入量大更新頻繁。同時(shí)更新涉及到所有的實(shí)時(shí)段和靜態(tài)段，較為復(fù)雜。

為了解決正排字段和倒排的更新問題，新版本引擎引入了document文檔鎖池，對每個(gè)doc進(jìn)行hash計(jì)算落到鎖池中具體一個(gè)鎖上來減少鎖沖突，當(dāng)前鎖池內(nèi)有多個(gè)個(gè)文檔鎖。文檔鎖在文檔進(jìn)行拷貝和更新的時(shí)候會(huì)進(jìn)行鎖住。

DSearch3.0搜索核心升級

異步非阻塞圖調(diào)度框架

※ 引擎主要改造：

1. 圖框架支持RPC異步非阻塞請求：引擎圖框架RpcServer服務(wù)使用brpc的異步處理無需同步阻塞等待調(diào)度完成，只需框架調(diào)度完算子返回結(jié)果，不阻塞RpcServer線程，例如：當(dāng)前引擎調(diào)用neuron服務(wù)是同步調(diào)用，當(dāng)neuron服務(wù)負(fù)載高阻塞時(shí)，同步調(diào)用會(huì)導(dǎo)致拖住引擎RpcServer處理線程，新的異步非阻塞模式引擎client在調(diào)用引擎后已經(jīng)返回，等待引擎RpcServer中異步調(diào)度框架中remote異步算子回調(diào)，減少外部服務(wù)影響引擎。
2. 減少線程切換：圖框架調(diào)度器會(huì)優(yōu)先調(diào)度當(dāng)前運(yùn)行線程，同時(shí)使用M:N類型的bthread線程池，線程切換會(huì)更小，執(zhí)行效率高。
3. RPC服務(wù)和框架算子獨(dú)立：引擎RPC服務(wù)和框架算子完全解耦，跨集群部署算子服務(wù)無需任何改造，實(shí)現(xiàn)算子脫離運(yùn)行環(huán)境。
4. 高效的算子異常處理和超時(shí)機(jī)制：每個(gè)算子維護(hù)自己的運(yùn)行超時(shí)時(shí)間和請求到算子調(diào)度執(zhí)行的超時(shí)時(shí)間，對整個(gè)請求流程中各算子執(zhí)行更加精準(zhǔn)。 
5. 動(dòng)態(tài)圖支持：圖框架支持靜態(tài)圖和動(dòng)態(tài)圖業(yè)務(wù)組合式調(diào)用。支持靜態(tài)子圖和動(dòng)態(tài)子圖調(diào)用等復(fù)雜業(yè)務(wù)組合。
6. 復(fù)雜子圖支持：圖框架支持嵌套子圖，支持自調(diào)用模型，可以實(shí)現(xiàn)復(fù)雜單節(jié)點(diǎn)多功能調(diào)用。

算子間數(shù)據(jù)交換Table設(shè)計(jì)

※ 引擎主要改造：

1. 列式數(shù)據(jù)共享優(yōu)化：算子交換數(shù)據(jù)全部存放在Table列中，Table中全部共享列式數(shù)據(jù)，省去大面積數(shù)據(jù)拷貝，大幅提升引擎業(yè)務(wù)執(zhí)行性能。
2. 兼容引擎索引中doc數(shù)據(jù)：引擎索引中doc行式存儲有很多優(yōu)點(diǎn)，比如多字段訪問效率高等，Table設(shè)計(jì)中考慮了行式存儲優(yōu)點(diǎn)，不僅存高頻的列字段也儲存了引擎內(nèi)部的doc*以及對應(yīng)FieldDef*，能直接方便訪問索引數(shù)據(jù)，接口統(tǒng)一，易于迭代。
3. 打通FlatBuffer序列化協(xié)議：當(dāng)前引擎FlatBuffer序列化傳輸協(xié)議和引擎內(nèi)部數(shù)據(jù)出口需要多次遍歷轉(zhuǎn)換，需要拷貝很多數(shù)據(jù)，新Table的設(shè)計(jì)內(nèi)部數(shù)據(jù)列和FlatBuffer內(nèi)部的數(shù)據(jù)列互轉(zhuǎn)互通，節(jié)省大量內(nèi)部拷貝同時(shí)避免了字段兼容等問題。
4. 支持原地排序和標(biāo)記刪除：Table數(shù)據(jù)表，支持原地sort操作和標(biāo)記刪除操作，節(jié)省數(shù)據(jù)排序時(shí)大量數(shù)據(jù)的拷貝和刪除操作中導(dǎo)致的數(shù)據(jù)重排等拷貝操作，提升性能。

算子間數(shù)據(jù)交換Table設(shè)計(jì)

※ 引擎主要改造：

1.  動(dòng)態(tài)圖支持：DSsearch3.0支持動(dòng)態(tài)圖編排，主要通過業(yè)務(wù)方通過動(dòng)態(tài)編排請求來組織對應(yīng)的算子編排邏輯，實(shí)現(xiàn)業(yè)務(wù)方自主編排調(diào)度邏輯，方便整體業(yè)務(wù)開發(fā)。
2. Remote遠(yuǎn)程調(diào)用支持：通過開發(fā)遠(yuǎn)程異步調(diào)用算子，支持DSearch3.0跨集群調(diào)用，實(shí)現(xiàn)多機(jī)算子化互聯(lián)互通。提高引擎的整體縱向拓展能力。
3. 引擎算子庫復(fù)用：通過設(shè)計(jì)統(tǒng)一的算子接口，開發(fā)基礎(chǔ)的可復(fù)用框架算子，支持配置化組合運(yùn)行圖，實(shí)現(xiàn)業(yè)務(wù)邏輯快速復(fù)用和開發(fā)，提高整體引擎開發(fā)效率。

三、性能和效果提升

DSearch在2024年Q1季度索引升級開發(fā)完成后逐步推全到交易和社區(qū)等各個(gè)主場景業(yè)務(wù)中，最后拿到了很多超預(yù)期結(jié)果：

索引內(nèi)存優(yōu)化超出預(yù)期：社區(qū)搜索和交易搜索總索引單分片優(yōu)化60%。

構(gòu)建和寫入性能優(yōu)化超出預(yù)期：社區(qū)搜索和交易搜索主表寫入性能提升10倍。

索引更新優(yōu)化超預(yù)期：社區(qū)和交易主表更新時(shí)間提升接近10倍。

性能優(yōu)化符合預(yù)期：社區(qū)搜索平均rt降低一倍，P99晚高峰降低2倍。

四、總結(jié)

DSearch引擎從開始的DSearch1.0的搜索引擎逐步經(jīng)歷了DSearch2.0的分段式索引改造升級，又經(jīng)歷了DSearch3.0的全圖化引擎升級。逐步將DSearch引擎升級到業(yè)界較為領(lǐng)先的支持內(nèi)存型、磁盤型多段式搜索引擎，為支持得物業(yè)務(wù)的發(fā)展做出了重要的貢獻(xiàn)，后續(xù)DSearch會(huì)圍繞著通用化、自迭代、高性能等多個(gè)方向繼續(xù)升級，將DSearch引擎迭代到業(yè)界領(lǐng)先的引擎。