一、背景

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

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

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

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

DSearch2.0的索引升級

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

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

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

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

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

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

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

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

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

※ 前綴檢索文件

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

倒排索引和查詢樹邏輯

※ 倒排鏈優(yōu)化

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

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

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

增量更新邏輯

※ 增量實時寫入邏輯

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

實時段固化和段合并策略

※ 實時段固化邏輯：

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

※ 段合并策略：

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

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

※ 查詢流程

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

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

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

※ 更新并發(fā)控制

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

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

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

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

※ 引擎主要改造：

1. 列式數(shù)據(jù)共享優(yōu)化：算子交換數(shù)據(jù)全部存放在Table列中，Table中全部共享列式數(shù)據(jù)，省去大面積數(shù)據(jù)拷貝，大幅提升引擎業(yè)務(wù)執(zhí)行性能。
2. 兼容引擎索引中doc數(shù)據(jù)：引擎索引中doc行式存儲有很多優(yōu)點，比如多字段訪問效率高等，Table設(shè)計中考慮了行式存儲優(yōu)點，不僅存高頻的列字段也儲存了引擎內(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è)計內(nèi)部數(shù)據(jù)列和FlatBuffer內(nèi)部的數(shù)據(jù)列互轉(zhuǎn)互通，節(jié)省大量內(nèi)部拷貝同時避免了字段兼容等問題。
4. 支持原地排序和標(biāo)記刪除：Table數(shù)據(jù)表，支持原地sort操作和標(biāo)記刪除操作，節(jié)省數(shù)據(jù)排序時大量數(shù)據(jù)的拷貝和刪除操作中導(dǎo)致的數(shù)據(jù)重排等拷貝操作，提升性能。

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

※ 引擎主要改造：

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

三、性能和效果提升

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

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

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

索引更新優(yōu)化超預(yù)期：社區(qū)和交易主表更新時間提升接近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ā)展做出了重要的貢獻，后續(xù)DSearch會圍繞著通用化、自迭代、高性能等多個方向繼續(xù)升級，將DSearch引擎迭代到業(yè)界領(lǐng)先的引擎。