微信搜一搜在线检索技术演进复盘
作者：kaelhua，騰訊 WXG 后臺開發工程師
背景
2020 年下半年我們(搜一搜工程團隊)開發了一個新的內存檢索引擎 ZeroSearch，并開始對搜一搜背后的大量垂直搜索系統進行升級，隨著升級過程中遇到的各種問題和新的需求，以及半年多來我們自身認識的提高，在線檢索引擎在各個方面都取得了長足的進步。在本文中，我會對我們團隊做過的一些主要事件進行經驗的分享，全文較長，約 2 萬 2 千字，內容涵蓋評測體系介紹，倒排查找算法優化，線程模型優化，索引壓縮原則，wand 檢索實踐，向量融合方案，以及性能優化方面的工作。
本文與前文(ZeroSearch 在線檢索設計)的目的一致，并不是因為覺得自己做得比較好，而是因為網絡上關于搜索領域的工程技術文章實在太少了，幾乎都是從大的方案架構上進行介紹，然而從目前了解到的信息來看大家其實都大同小異，而稍微細化一點介紹具體實現的資料卻幾乎沒有。本文意圖略微填補一下關于檢索引擎詳細設計的資料空缺，搜一搜正在招聘后臺開發和運營開發工程同學，如果閣下對搜索引擎或者搜索系統感興趣，也歡迎聯系我們。下面開始正文。
在線檢索評測體系
工欲善其事必先利其器，為了能夠在版本迭代以及特性開發過程中，確保每次變更的質量以及量化其收益，我們先建立了一套在線檢索評測體系，該體系主要由以下幾方面構成：
1 評測 Query 集
2 評測文檔集
3 評測工具
4 評測指標
我們先從搜一搜的搜索日志里隨機篩選出了一批 Query，并經過一定的加工篩選后，得到了我們的評測 Query 集，同時從長文本業務中，隨機抽取了一批文檔，作為我們的評測文檔集。評測工具主要是通過設定 Query 集，并發數，評測時間，以及收集引擎返回的 kpi 信息(下文會介紹)進行統計，并輸出相關報告。評測指標主要分為以下幾個方面。
引擎 kpi
每次 Query 檢索過程中其召回篇數信息，耗時信息，以及打分信息引擎都會進行記錄，并隨檢索結果一起返回給上游，便于上游進行統計，上游通過統計 Query 集的信息后，得到我們最終的引擎 kpi，目前引擎 kpi 主要由以下指標構成：
全局指標
統計成功總數，失敗總數，空結果率，QPS 等指標。
召回結果指標
統計各個環節的篇數信息，如平均召回篇數，平均求交篇數，平均 L1 打分篇數，平均 L2 打分篇數等指標。
耗時指標
統計各個環節的耗時信息，如平均總耗時，平均求交耗時，平均 L1 耗時，平均 Join&L1 耗時，平均 L2 耗時，平均打分耗時，平均 Join&Score 耗時等指標。
耗時分布指標
統計最終耗時和各個環節耗時的耗時水位信息，如 99 分位耗時，99.9 分位耗時等指標。
打分指標
統計文檔的打分信息，如平均 L1 得分，平均 L2 得分等指標。
程序熱點
通過 perf 及其配套工具生成程序火焰圖，用于熱點分析，另外火焰圖也能方便我們了解程序全局的算力分配情況。
細粒度程序性能指標
perf stat 中的軟硬件統計指標，如 CPU 利用率，內存利用率，IPC(insns per cycle)，cache 命中率，分支預測失敗率, context 上下文切換次數和 CPU 遷移次數等等細粒度指標。
得益于 BG 完備的運維體系，上面很多指標都有現成的運維監控系統可以統計到，包括程序的火焰圖也可以一鍵抓取。評測體系建立完成后，我們每次有重要特性合入時，都會進行一輪評測，獲取引擎的全面信息，除了上面說的質量保證和收益量化，該評價體系對我們的工作方向同樣具有指導作用。
細粒度統計指標中，實際上真正對我們的工作產生指導性作用的，只有 IPC,cache 命中率，分支預測失敗率。
關于倒排查找
在最初的設計里，我們的倒排查找實現非常簡單，由于每個 term 的倒排鏈都位于連續內存中，并且當時的索引結構也未進行壓縮，可以簡單理解為每條倒排鏈就是一個 uint32 類型的有序數組，因此我們是直接通過二分查找來定位某個文檔 id 的。
=注:經過半年多的迭代，目前索引結構已經發生了很大變化，不過并不影響本節內容。
這里其實是有個先入為主的問題，談到倒排查找的時候，我們(包括筆者)往往都會聯想到跳表，這可能是因為談到搜索引擎的時候，大家接觸過的或者想到的都是磁盤搜索引擎。基于這種刻板的認知，我們直接使用了二分搜索，因為在我們看來，跳表本質上實現的是一個在不連續內存上進行二分搜索的方式(這種認知也是有偏差的，實際上在磁盤檢索上其更多是從磁盤 IO 的角度來考慮的，且其比二分更能利用局部性優勢)。
稍作細想，我們可以想到，除了二分查找的方式，還有順序遍歷，Galloping Search 等方式。為了明確各種查找方式的一個性能對比，我們比較了以下四種倒排查找算法(基于 k-way 求交算法下，詳細見 ZeroSearch 在線檢索設計一文)的性能數據，結果出乎意料，這是部分數據的一個對比：
表格中的結論為：順序遍歷 > Galloping Search(區間內順序遍歷) > 大于 Galloping Search(區間內二分查找) > 二分查找。
注:檢索過程中會有多個庫并發進行求交，這里的求交耗時是把所有庫求交完所花耗時的累加值。根據不同的測試數據集和測試 Query 集，各個查找算法的消耗會有不同的表現，以上和以下數據均是以我們的測試數據集為準進行測試的，該測試數據集來源為搜一搜中較大的一個長文本搜索業務，測試數據集的文檔規模與真實的線上環境基本一致。
倒排查找統計
目前我們的倒排查找過程，分為以下兩個階段:
1 塊間查找
2 塊內查找
我們首先通過火焰圖觀察到塊間查找的消耗僅占 0.05%，幾乎可以忽略不計，因此對上面的結論造成影響的因素基本全部來自塊內查找。為了進一步明確塊內查找的消耗情況，我們對倒排查找函數內部的執行狀況進行了統計，以下為 Block Size 固定為 1024 時，需要向后查找 PageId 時的統計數據。
為什么我們之前 block size 采用了固定 1024 呢？主要是當時還未考慮索引壓縮，block size 太小的話，內存占用會變多(事實上這個考慮是多余的)，而最終選用 1024，其實是因為 1024 是一個比較程序員的數字，一開始打算先用它試試，后面沒再花精力調整了。
1 Block Gap 統計
統計下一個目標 PageId 所在 Block 與當前 Block 的在倒排鏈上的距離：
表格中的結論為：1 100%的查找落在本 Block 和鄰接 1 Block 內，說明 k-way 求交算法下由于求交連續性，目標文檔幾乎都在近鄰 Block 內查找。2 解釋了火焰圖中塊間查找函數占比極低的原由。
2 目標 PageId 位置 Gap 統計
統計下一個目標 PageId 與當前游標指向的 PageId 在倒排鏈上的距離。
餅狀圖中的數字 2，4，8，16 等等是指統計區間的上限，如 2 指的是距離位于[0,2)，4 指的是[2,4),8 指的是[4,8)
餅狀圖中的結論為：1 求交的連續性帶來了查找的局部性，離游標當前位置越接近的文檔，其作為下一個目標文檔 id 的可能性就越高。
2 解釋了二分查找性能最差的原因，由于二分查找的查找次數固定，其只適合目標文檔 id 均勻分布的情況，無法利用局部性優勢。
3 倒排鏈長度分布統計
我們對索引庫中倒排鏈長度的分布同樣進行過統計，結論為絕大多數倒排鏈都是短鏈，長鏈占比極低(但是與之相反的是，長鏈的累加長度遠高于短鏈，即倒排鏈的內存消耗反而主要是長鏈帶來的)，這是最基礎的數據分布特征，我們認為這也是查找行為的局部性特征的重要原因之一，該統計數據對索引結構設計，索引壓縮方案同樣具備指導性價值。在 ZeroSearch 設計一文中，我們提到過索引數據會進行分片分庫，即數據是被稀疏過多次的，一般最終到一個索引庫內的文檔數已經降低到百萬級別了，這是造成倒排鏈長度的數據分布特征的一個原因。
不過這里還是得再強調一遍，本文中所有的統計數據都是基于我們選取的一個長文本業務(業務量較大)的數據統計得到，不同的數據源，是完全可能具有不同的數據結論的。
k-way 求交算法與倒排查找
通過上述的多個倒排查找算法的性能數據以及倒排查找中的 Gap 統計數據，可能會直接得出結論：順序遍歷在我們的評測體系中具有最佳的性能表現。但深入思考一下，我們會發現存在以下問題：
1 盡管 Gap 越大的位置，其占比越低，但是其要花費的查找代價也是成倍上漲的。
2 記第 i 條倒排鏈為 Pi，在倒排求交中一種常見的查詢優化手段是讓短鏈優先查找，即在初始階段，我們會對查詢語法樹進行處理，最終會存在這樣一個關系：
Len(?P(n+1)?)?>=?Len(?P(n)?)由于短鏈節點查找消耗更低，單次查找更快，因此短鏈節點優先查找，可快速更新求交基準，有利于提前結束求交行為。在 k-way 求交算法下，第 n+1 條倒排鏈，其進行第 x 次查找時，其要查找的位置，是前 n 條倒排鏈已經查找到的第 x 個交集元素， 即:
P(n+1)x?=?(?P(1)??∩??P(2)??∩??P(3)??.....??P(n)?)x即長鏈查找的次數一定是小于短鏈的(我們認為這也是局部性特征的重要原因之一)。如果數據分布均勻的話，那么毫無疑問，對長鏈而言，大概率前后要查找的兩個位置的 Gap 較大，這在一定程度上幫助我們分析了 Gap 統計數據中高 Gap 值的來源的問題。需要說明的是，這一點只是猜想，我們并沒有去進行精確測量。
動態調整
通過上面的分析，可以推測沒有最優的倒排查找算法，只有針對具體的場景最合適的倒排查找算法。因此在應對不同的語法樹時，我們會對語法樹中每一個 term 節點，通過該 term 節點在優化后的語法樹中的位置，該 term 節點對應的倒排鏈長度，該 term 節點的起始文檔和結束文檔的覆蓋范圍，以及其它 term 節點的相關信息等特征，我們可以從全局的角度進行考慮，來為每個 term 節點選取最佳的查找算法，以逼近理論最優值。
在我們的評測體系下，與其它的單一的查找算法相比，動態選取方式生效的查找行為比統一的查找算法速度提升了25%，但由于并不是所有的查詢語法樹都需要動態調整，因此其生效比例并不高，在評測集最終整體的平均查找耗時的優化效果上大打折扣。
在動態調整的應用過程中，我們曾一度預期 Galloping Search+循環查找的方式性能可能最好，因為我們做過 Gap 統計，k-way 求交算法下，查找是具有局部性特征的，那么 Galloping Search 會比二分搜索更適合。但通過大量的測試，在我們的測試集下，測試數據又一次證明預期是錯誤的，結論為二分搜索是比 Galloping Search 更合適的大 Gap 下的查找算法。我們曾試圖過去尋找一些原因，不過淺嘗輒止，一種簡單的數學上的印象是這樣的：在大 Gap 下，如果我們新打開了一個 Block，那么查找位置，落在該 Block 中的所有位置的概率是均勻 的(盡管局部性的存在導致并不是這樣的)，那么通過計算查找消耗的數學期望可以知道，二分的數學期望是最小的。即在 BlockSize 為 1024 的倒排查找中，我們完全棄用了 Galloping Search。
多級倒排表設計
通過上面的數據分析已經知道，在一定的索引特征和 k-way 求交算法下，求交行為具有局部性特征。其實倒排鏈分塊(一級索引)本身就已經充分利用了局部性了(保證了我們能夠在近鄰塊內進行查找，而不是整條鏈查找)，這里存在一個設計問題，即倒排表應該分多少級?例如一級索引，二級索引，三級索引等等。這個問題其實也顯而易見了，由局部性特征及其統計數據可以知道，一級索引已經足夠了，繼續增加只會徒增 IO 和計算邏輯，這點我們認為不論是對磁盤搜索引擎還是內存搜索引擎都沒有區別，不過這條結論是由我們的測試數據集和測試 Query 集得到，且只是單純的文本檢索，我們只能確保目前在搜一搜內該結論有效。
算力分配問題
正如之前在 ZeroSearch 設計一文中提到過的，我們認為內存搜索引擎要解決的核心問題是計算量的分配問題，即如何合理的分配計算量，能盡可能的讓優質結果展現給用戶。解決量與分配的關系關鍵在于對檢索流程進行標準化，而標準化的意圖在于量化算力。為此我們抽象出了求交任務，L1 打分任務，L2 打分任務，資源清理任務等四個邏輯任務，并設計了任務的流水線模式。在 ZeroSearch 里，每一個邏輯任務就是對于計算量的一個抽象，而量化的尺度為各任務的文檔篇數與超時時間。
我們會發現量化似乎是資源類應用設計的通用準則，例如從硬件層面看，其對于算力的量化標準為 CPU 頻率，功能單元容量，延遲，發射周期等性能指標，從機器運維的角度看，其量化標準為機器的 CPU 使用率，而我們要做的事情（CPU 密集型服務）其實就是將 CPU 使用率合理的轉化為我們的量化標準，我們希望每一分 CPU(在篇數與超時時間不變的情況下)都可以對應到具體的 QPS。
在我們最初的設計里，每個任務一旦被調度到，就會運行到結束或者超時。考慮到不同任務的計算量消耗是不一樣的，以及單庫單線程求交設計中，求交任務消耗最嚴重，為了避免餓死其它線程，我們進行了拆分多個線程池，即整體如下圖所示:
按照最初我們的預期，假設求交線程數為 x，打分線程數為 y，會存在一組參數(x，y)，且 x + y = CPU 邏輯核數時，其性能最佳，引擎吞吐量最大。但是經過大量測試，出現了反預期的現象：
各線程池的線程數均較多時(超越核數)，吞吐量反而更高。
為了找到線程數與吞吐量的關系，我們先固定了 x:y=1:1,通過調整引擎的線程總數**(線程總數=線程系數*CPU 邏輯核數量**)，對多組參數進行測試和統計，得到了下圖：
說明：在達到最大吞吐時，各組測試參數下的服務 CPU 均已達到 90%多，快接近 100%，圖中的吞吐能力可以簡單理解為最大 QPS。
散點圖的縱軸表示吞吐能力，橫軸表示線程系數，可以看到在剔除了線程系數為 1 的數據后，整體的波動就比較明確了，大體上呈拋物線，先緩慢上升，后緩慢下降，整體上還是穩定的。我們通過對比測試過程中得到的統計數據對此進行了分析。
上升階段
線程系數由 1.5 遞增到 3.5 時，整體上升，上升趨勢逐步收斂。
分析：大多數請求召回篇數較低，甚至空召回，增加各線程池的線程數量，本質上是增加了各任務階段并發度。低(空)召回請求可以更快得到處理，請求平均等待耗時下降，最終檢索平均耗時下降
下降階段
繼續增大線程系數，當線程系數超過 3.5 后，吞吐開始下降，下降趨勢逐步收斂。
分析：通過統計數據我們觀測到 sys 部分 CPU 在上升，推測是內損消耗變大(如線程上下文切換，線程之間的競爭等)，帶來的收益小于增加的成本
同時我們對性能最優的這組線程數據(線程系數 3.5)，以遞增的壓力進行壓測，并統計不同壓力下的吞吐，得到了以下數據：
當壓測系數超過一定閾值時，其吞吐能力直接下降了一截，可以知道這種模式的穩定性較差，并且當我們繼續增大并發壓力時，其吞吐還在緩慢下降。
新的方案
多線程池任務粒度調度模式的設計存在以下兩方面的問題
1?業務很難配置出一個得到最佳性能的參數2?服務的穩定性較差，壓力過大時可能導致雪崩因此新的方案中我們舍棄了多線程池的設計，因為我們認為這是導致服務穩定性較差的重要原因。
另一方面，任務為粒度的調度單位太大了，長尾請求容易持續占用 CPU，最終導致算力分配不夠均衡，因此我們重新實現了調度機制，不再以任務為粒度，而是以時間片為粒度，最終方案采用了單線程池設計 + 時間片粒度調度設計。程序被分配了多少個核，我們就創建多少個引擎工作線程，并分別綁定 CPU 核。
但需要強調的是，時間片粒度調度方案的設計初衷是為了保障在低線程數的情況下，依然保持較低的任務平均隊列等待耗時，而不是最大吞吐量和服務穩定性。但是該項收益在我們的測試集中并不明顯，因此在下文中我們依然是以最大吞吐和穩定性兩個維度進行對比和分析。
關于任務平均隊列等待耗時假設我們有3個任務A,B,C， A 需要執行3個時間單位，B和C分別需要執行1個時間單位，現在我們有一個CPU核，在任務粒度調度里，假設我們按A,B,C的順序進行執行，各個任務從入隊到執行完畢所花的時間如下：A任務?3?時間單位 B任務?4?時間單位(隊列等待3時間單位) C任務?5?時間單位(隊列等待4時間單位)任務平均耗時(3?+?4?+?5)?/?3?=?4?時間單位假設我們按C,B,A的順序進行執行，則各個任務所花時間為：C任務?1?時間單位 B任務?2?時間單位(隊列等待1時間單位) A任務?5?時間單位(隊列等待2時間單位)任務平均耗時(1?+?2?+?5)?/?3?~=?2.67?時間單位即時間片調度的一個直觀收益在于，其可以減少平均隊列等待耗時。但這點如何驗證呢？以下兩種方式都可以驗證得到 1?通過固定QPS請求服務，統計平均耗時相關的指標 2?通過固定并發數請求服務，統計服務的QPS指標 不過在我們的測試數據集中，我們對測試集本身卡了空結果率，保證測試集的空結果率在1.5%以下，實際上線上業務的空結果率遠高于此值，而在空結果率高的情況下，時間片輪轉調度的收益才會更高同樣的，在我們實現完該方案后，我們對多組參數進行了測試和統計，得到了以下數據。
通過多組測試，在最大吞吐量方面，時間片調度方案與任務粒度調度方案幾乎相等。在引入時間片調度后，會增加以下成本:
1?增加了各任務的入隊出隊次數2?由于業務相關性的一些需要，相關性庫在每個任務的開始函數和結束函數的調用會變為多次（任務粒度的調度則只有一次）如果將上述第 2 點也改為一次的話，在測試數據集中，最大吞吐量的收益穩定在 1-2%，不顯著。
由于時間片調度會增加一些成本，因此我們最初預期是最大吞吐會有所下降，但測試結果是基本持平，甚至略有提高。
理論上，除非我們減少了長尾請求的算力占用，否則時間片調度方案不應該有最大吞吐量的收益。這是因為一個請求在沒有超時的情況下，其消耗的算力是固定的。而單位時間下，機器擁有的算力也是固定的，兩者相除即得到服務的最大吞吐量。我們通過統計數據觀察到，不論是在時間片調度還是任務粒度調度方案里，有任意環節超時的請求數均為0，即每個請求的算力消耗是一致的。時間片調度方案相比任務調度方案的最大吞吐收益來源其實分為兩部分，一部分來自sys部分(該部分占用恒定且非常低)，另一部分是時間片調度是唯一一個可以完全榨干算力，CPU占用一直保持100%的方案。雖然在最大吞吐量上的收益不明顯，但是服務的穩定性大大增強，當吞吐達到最大值后，即便我們繼續增加壓測壓力，服務也只是各階段的平均耗時在上升，但是吞吐保持了穩定。
同時，單線程池的設計也可以簡化引擎的參數配置，業務不再需要理解和配置各個線程池的線程數量，降低了使用門檻。
??當以時間片粒度調度時，如果時間片足夠大，將退化為任務粒度調度，我們同樣測試過這種情況，在我們的測試數據集中，其穩定性，以及最大吞吐量都比小粒度時間片要差。即小粒度時間片方案在輸入差異的情況下，還可以保證在一個周期內具備比較恒定的輸出。另一方面，我們還未對任務調度進行過多優化，目前整體為一個簡單的優先級隊列。改為時間片粒度調度后，由于任務重復入隊，如果服務的并發壓力過高的話，那么服務同樣會面臨雪崩的問題，這也是后續我們計劃優化的一個方向。不過某種程度上這其實是一個偽命題，由于組件化的設計，我們的在線檢索服務?=?在線檢索組件?+?任意支持線程模式的RPC框架，即檢索服務中存在兩個線程池，一個是RPC框架的工作線程池，一個是在線檢索組件的工作線程池，即最大并發壓力=RPC框架的工作線程數量。因此RPC框架的工作線程數量幫我們限制住了服務的最大并發壓力，在達到最大并發壓力之前，CPU早早就達到100%，觸發擴容機制了。另一方面通過優化任務調度的策略，我們也可以進一步減少平均任務隊列等待耗時。對于算力分配問題，其實我們的完整解決思路是從分配高效和分配均衡兩點下手，對應的解決方案分別為任務流水線設計以及單線程池時間片調度，由于任務流水線設計已經在 ZeroSearch 設計一文中提過了，因此本文就不再重復了。
關于索引壓縮
索引壓縮部分主要由我們團隊的 agan 負責，后續將有獨立的分享，本文中只談一下我們對于索引壓縮的粗淺認識。
空間與性能的權衡
當談到索引壓縮時，按照思維的慣性，我們可能會想到倒排鏈的各種壓縮算法。依瓢畫葫蘆的確是一件比較輕松的事情，但如果深入思考的話，我們會發現倒排鏈的壓縮對內存搜索引擎來說，其收益是比較局限的。
壓縮的本質是時間換空間，但是在內存搜索引擎里，CPU 與內存都是緊缺資源，導致倒排鏈的壓縮變成了性能與空間的一項權衡，即我們會傾向于訪問頻率越高的數據，其壓縮的必要性越低，或者是解壓效率越重要(當然不壓縮的時候解壓效率是最高的)，很遺憾倒排鏈恰恰是訪問頻率最高的。不過在磁盤搜索引擎里這點是毋庸置疑的，由于磁盤 IO 的存在，其不止換到了空間，還省了時間，一本萬利。(注:這里的磁盤 IO 特指 hdd，非 ssd)。
事實上，在我們開啟索引壓縮工作前，我們先選取了一個文檔量較大的核心業務的索引庫，對引擎內的各部分索引結構的空間占用進行了精確測量和統計，我們希望能夠對我們要做的事情先有一個全局的認識和掌控，并盡可能提前量化好工作收益，再以此為指導進行工作的展開。
在得出具體的統計數據之后，我們做的第一件事不是索引的壓縮，而是索引結構的重新設計，在我們的收益預估中，索引結構的重新設計，其性價比(空間優化幅度 / 性能降低幅度)比倒排壓縮更高。
另一方面，我們通過對已有業務進行統計，真正占用了內存消耗大頭的，反而是文檔的正排數據(含文檔的 Pos 數據)。因此對于倒排鏈的壓縮，我們只采用了一些非常輕量的壓縮方式，一方面倒排數據是檢索過程中訪問最頻繁的索引數據，另一方面倒排數據在索引數據中的占比并不高，沒有必要為了倒排的內存空間收益而放棄 CPU 和性能。
關于 weakand 的落地應用
長期以來，在文本檢索這塊，搜一搜使用的都是嚴格的布爾檢索形式。例如用戶輸入 Query:[廣州機場附近有啥玩的地方]，我們通過分詞環節，可能會得到[廣州，機場，附近，有，啥，玩，的，地方]這樣一個 term 列表，一種理所當然的做法是將各個 term 對應的倒排鏈取出來，求其交集，得到我們的召回結果，即語法表達形式如下:
(廣州 and 機場 and 附近 and 有 and 啥 and 玩 and 的 and 地方)在 Query 處理過程中，分詞之后，還有很關鍵的一步，就是對這個 term 列表中的 term 設置必留（必須命中）或者丟棄（可選命中）屬性。例如我們可能會對[有，啥]兩個 term 設置丟棄詞屬性，就算文檔沒命中這兩個 term 也可以進行召回，即語法表達形式如下:
(廣州 and 機場 and 附近 maybe 有 maybe 啥 and 玩 and 的 and 地方)當然，在這個例子中我描述的很簡單，但實際上在長 Query 下，必留或者丟棄屬性的設置要做到比較精確是非常困難的，這里一部分原因是語言自身的復雜度，另一部分原因是搜一搜背后存在大量的垂直搜索引擎，各個垂類搜索引擎的必留/丟棄屬性的設置標準是不一樣的，Query 處理環節中，不可能滿足所有需求。
正如 ZeroSearch 設計一文中提到的，我們對 weakand 的認識在于這種求交方式可以緩解對于 Query 處理能力的依賴，這恰好是搜一搜所需要的。通過相關論文對 wand 有一定了解后，我們最終在引擎內采用了 block-max-weakand 的實現方式，并對其性能，召回效果方面有了一定的應用經驗。
block-max-weakand 實現的主要參考論文：[Efficient_query_evaluation_using_a_two-level_retrieval_process][7]
wand召回方式是以召回相關性得分TopK的文檔作為召回目標，假設我們存在一個Query：ABCD，其分詞結果為A，B，C，D，在布爾檢索中，其召回集的size為:A?∩?B?∩?C?∩?D在動態非必留中，其召回集的size為下面的區間：[?A?∩?B?∩?C?∩?D,????(A?∪?B?∪?C?∪?D?)?/?N?]?，?N?為要求的最低命中term數在weakand中，其召回集的size為:A?∪?B?∪?C?∪?D很明顯，weakand的召回集的size是最大的，為所有相關的倒排鏈的并集，我們記為S。weakand的召回方式為從S中選取出相關性評分TopK的文檔出來，然后進行召回，這種召回方式與布爾檢索或者動態非必留是完全不同的。在布爾檢索和動態非必留中，本質上召回的文檔是滿足命中關系的L0得分TopK的文檔。量化單位
(我們認為)搜索引擎的設計標準之一：讓算力變得透明，可量化。因此引入 wand 第一個要考慮的問題是如何去量化 wand 召回行為，篇數與超時依然是我們的量化尺度。在超時上，wand 屬于召回環節里的不同召回方式，因此超時機制可以直接復用。在篇數上，wand 的召回方式為選取相關性評估得分 TopK 的文檔進行召回，不過這是在滿求交下才能得到的理想結果，為了與原有篇數配置兼容，我們新增了一個求交膨脹系數。即在 wand 召回中，其求交篇數為原有的求交篇數配置*求交膨脹系數，然后再從這些文檔中，選出相關性 TopK 的文檔進行召回。
在召回篇數未達到 K 時，文檔將按 did 從小到大順序依次入堆，當堆滿之后才開始裁剪邏輯，因此減小求交篇數配置值可以更快速的開始裁剪。而增加求交膨脹系數后引擎將求交出更多的文檔，即在更多的文檔中選出 bm25 得分 TopK 的文檔，從而得到一個更優質的召回結果集，但其代價為消耗更多的算力。
在固定求交篇數的條件下，假設引擎固定求交 10W 篇，即:
求交篇數配置?*?(?1?+?求交膨脹系數?)?=?10W我們對多組參數進行過測試，求交膨脹系數越大，求交篇數越小，召回過程就越快，原因在于其能更快速的進入到裁剪過程，且裁剪過程將得到加速。
另一方面，理論上求交膨脹系數越大，求交篇數配置越小，最終召回結果將會越優質，原因在于其裁剪規模將越大(未滿求交的前提下)。使用者可以根據自身需求，綜合考慮召回篇數，召回效果以及性能損耗。
內存 or 算力
在我們的 wand 實現里，采用了各個字段的 bm25 得分加權求和來作為文檔的相關性評分。bm25 得分的計算項主要是兩部分，一部分是計算 Term 權重，另一部分是計算 Term 與文檔的相關性評分。
其中 Term 權重是固定的，一個索引庫內的每個 term 只需要計算一次，其空間占用較小，因此我們放在了離線索引階段來計算。還有一部分原因是搜一搜中大多數業務的倒排鏈目前不是按 field 粒度來建的，而是按文檔粒度建的，在線計算的話無法分 field 來計算。
但是 Term 與文檔的相關性評分，屬于 Term-Doc 維度的得分，如果在檢索階段，對每篇求交出來的文檔都計算一遍，這部分的 CPU 消耗不可忽略。因此其實現方式有兩種，分別為在線計算或者離線計算 Term 與文檔的相關性評分。采用離線計算時，依據業務的不同，內存大概增長 20-30%，適用于業務體量較小的業務，例如帳號搜索系統。而采用在線計算時，CPU 大概增長 10%，適用于業務體量較大的業務，例如長文本搜索系統。
初始閾值
在 wand 召回里，當召回篇數小于 K 篇時，文檔將直接入堆，原因在于我們需要先求交出 K 篇文檔，才能選舉出裁剪閾值，然后執行裁剪邏輯，并在隨后的過程中不斷更新閾值，而閾值越高時，裁剪規模也會越大，整個求交過程會處于不斷加速的過程中，類似于滾雪球，越滾越快。
根據統計得到，直接入堆的文檔得分一般都較低，在后續的求交過程中也會被丟掉，從而浪費了算力。因此我們提供了讓業務設置初始閾值的能力，提前開啟裁剪邏輯，確保初始入堆的文檔質量。另外一方面，業務也可以通過給與一個較高的初始閾值，從而加速整個求交過程，在固定求交篇數下，較高的初始閾值可以保證遍歷到更多的文檔(即滿求交率更高)，進而提升最終的召回文檔的質量。但是閾值給的過高時，可能導致欠召回問題產生。
出于性能的考慮，我們也會根據文檔頻率，以及查詢 term 列表的特征信息，提供一個默認的保守計算初始閾值的選項。
計算規模裁剪
在布爾檢索中，檢索串越長其召回集越低(召回集為 term list 的交集)，但是在 wand 求交方式里，檢索串越長，其召回集就越大(召回集為 term list 的并集)，參與到 wand 計算的 term 就越多，其性能損耗也將越大。
但是 wand 召回方式本身就天然適用于解決長串的召回問題，為了加速 wand 召回方式里長串的檢索速度。我們支持布爾檢索與 wand 召回結合的檢索方式，即可以從長串中抽離出核心詞或丟棄詞，對于核心詞采用嚴格 and-or 語義求交，對于丟棄詞則直接不參與求交。最后剩下的 term 才參與到 weakand 的計算中來，最終達到減少 wand 計算規模的效果。
初始閾值是一種通過加速裁剪過程來完成加速召回的方式。而抽離核心詞做布爾檢索則是通過減小計算規模(召回集大小，wand 計算的 term 數量)來完成加速召回的方式。
適用場景與效果
wand 召回方式可緩解搜索系統對于 NLP 能力的依賴，因此其天然適用于長串的檢索召回。在搜索系統中，長串的檢索召回相比短串要困難很多，一方面是 Query 處理過程中很難精確設置必留/丟棄詞，即容易出現召回偏移和欠召回問題。另一方面，相關性計算方面也容易出現結果漂移。我們這邊有獨立的相關性計算流程，因此對于 wand 主要用于解決召回偏移和欠召回的問題。我們對長文本業務做過一個召回覆蓋率的評測，評測結論為：增加一路 wand 召回隊列，大約可以提升 12%絕對值的召回覆蓋率。
關于向量融合
向量檢索及其優化主要由我們團隊的 willen 和 jingwen 負責，后續將有獨立的分享。本文中主要介紹我們處理向量檢索結果和文本檢索結果的多隊列結果融合方案的實現。
問題背景
引擎進行文本召回時，本質上是對多個有序列表求其交集，同時整個過程是流式的，因此隨著求交不斷進行，彈出來的 did 是有序的，整體是 did 從小到大進行召回。由于 L0 得分越高，did 越小，因此文本召回的結果集一方面是 did 有序，另一方面它是質量分從高到低的一個結果列表。
注意：此處的 did 特指引擎內部給文檔賦予的 id，與業務層面的文檔 id 不一樣。引擎內部對文檔進行 id 賦值時，標準為 L0 得分(離線計算得到的文檔質量分)越高，則其 id 越小，保證在倒排鏈的前面，能被優先求交出來。
引擎進行向量召回時，將搜索與檢索條件中的向量距離最接近的文檔，即向量得分越高的文檔進行返回，其整個過程其實也是流式的。向量召回的結果集，為向量距離從小到大的結果列表，或者說是向量得分從高到低的結果列表。但 did 是無序的。
在相關性特征輸入信息方面，文本隊列的只有文本命中信息，而向量隊列的只有向量得分信息。由于我們希望將結果的融合放在引擎內部實現，因此不論文檔是從文本隊列召回還是向量隊列召回，我們在給到相關性庫打分時，其相關性特征輸入信息應該保持一致，否則相關性庫無法以一個統一的標準來對文檔進行相關性評分。
當文本召回和向量召回同時進行時會面臨一個問題，即在什么時候進行結果融合？一種方案是召回過程中進行融合，但是文本召回需要保證 did 有序，否則倒排求交就沒法進行下去了，而向量召回結果為 did 無序，因此我們需要將其轉化為有序。
另一種方案是召回階段結束后融合，首先兩個隊列出來的結果集幾乎可以肯定是不一致的，兩者的結果集沒法完美合并掉，那么我們還需要將其特征進行對齊。
引擎底層融合，比讓業務自己在上層融合具備更多優勢，其一是更低的開發成本，其二是融合排序會更加容易且自然。如果文本檢索和向量檢索是獨立系統的話，那么引擎底層融合與之相比，還可以減少維護成本，同時規避掉多套檢索系統帶來的數據冗余和一致性的問題。
召回隊列與召回比例
遵循算力可量化的標準，我們先對引擎的檢索輸入信息做了多隊列召回支持的改造，支持使用者設置多條隊列的檢索條件，并給每條隊列設置一個召回比例。各個隊列的召回篇數=求交篇數配置項 * 隊列召回比例的百分比。
融合召回方案
在 ZeroSearch 中，一次檢索行為，會經歷三個階段:
求交階段?--->?L1打分階段?--->?L2打分階段對于融合召回，我們最初采取的解決方案是在求交階段通過控制各條召回隊列的召回比例來進行混合召回完成的。那么我們需要解決的是向量隊列 did 無序返回的問題，我們的思路也很簡單，直接讓向量隊列先完成召回，然后再 sort 一遍后與文本隊列融合。整體設計如下圖所示：
整體流程為:
1?求交任務先進行向量召回2?對向量召回結果進行sort，按did從小到大排列3?求交任務進行文本召回，并與向量召回結果融合4?求交結束，進入打分階段該方案的優勢為:
1?結果融合時可保證文本隊列的召回結果與向量隊列的召回結果不重復由于求交任務中的向量召回隊列先進行，引擎給與了向量召回結果更高的召回優先級，因此可保證文本召回與向量召回結果不重復，但是向量召回隊列之間還是可能存在結果重復2?向量召回結果可獲取到文本命中特征倒排鏈的組織形式為按did從小到大排列，因此文本召回過程中，可通過將查詢串的各條倒排鏈的游標移動到向量召回結果的did位置處，來獲取向量召回結果的文本命中信息該方案同時具備以下缺陷:
1?文本召回和向量召回實際上是在同一個求交任務下串行進行，導致最終耗時和召回耗時下限都比較高2 文本召回的結果獲取不到向量特征（向量得分），這是因為實際業務場景中，文本隊列的召回比例往往非常高，一方面我們需要尋址和讀取該文檔的向量信息，另一方面高維向量的一次歐拉距離或者內積計算的消耗同樣不可忽略，由于可能存在多條向量隊列同時召回，如果對每個文本隊列的結果單獨計算多次向量分，但進入L2打分階段卻只有L1得分TopK的結果，這里會存在較多的算力浪費的現象。獨立召回方案
為了解決融合召回方案中的缺陷，我們重新思考了結果融合這個問題，總體思路為忽略非必要的缺陷，解決核心需求點。通過結合實際場景分析，向量召回的結果一般用于補充文本召回的結果，且其召回量相對較低，向量召回結果與文本召回結果存在適量重復是可以接受的。而召回耗時增加，以及多條隊列的召回結果，其文本/向量特征不完全統一的情況對于打分階段是難以接受的，基于此我們提出了新的多隊列獨立召回方案，新方案的整體設計如下圖所示：
其整體流程為:
1?文本召回由獨立的求交任務和L1打分任務進行2?向量召回由獨立的求交任務和L1打分任務進行3?兩條召回隊列的結果在L1打分結束后進行融合，統一文檔特征4?將特征統一后的最終L1打分結果送入L2打分結果其核心設計點為：
1?特征統一放在了L2打分階段之前進入L2之前如果在L1打分階段進行特征統一，對一篇文檔的特征進行統一的消耗較大，而求交階段的召回結果較多，性能消耗較大，因此該方案被舍棄2?向量隊列結果可直接進入L2打分向量隊列召回的結果本身就是向量得分TopK的結果，沒有必要再進行L1打分篩選一遍TopK，從而規避掉了與文本隊列結果一起進入L1篩選TopK的問題該方案其實依賴于雙打分流程(L1Score ---> L2Score)的設計。但在 ZeroSearch 設計之初，其實我們也沒有意識到雙打分流程在多隊列召回中也能起到關鍵性作用。
這里想說點題外話，雖然我們讓引擎支持了 wand 召回方式，也支持了引擎同時進行文本和向量檢索，且尋找到了一條至少看似合理的路徑實現了結果的融合。但是于個人來說，做這些事情的過程和結果并不是最重要的，重要的是做完這些事情后，它們本身給我們帶來了新的思考，即：作為一名成熟的搜索工程同學，其職業成長的方向會在哪里？一種顯而易見的想法當然是引擎平臺化，技術產品化，那么圍繞這兩點進行工作方向的展開即可。
盡管要做到這兩點已經非常困難，事實上能做到的公司鳳毛麟角，但這只是我們的次要目標，因為我們還有更重要的業務目標。長久以來我們對信息檢索的認識就是分詞，索引，倒排求交，打分，排序這樣一套模板，即便平臺化后，也不過是模板通用化了，可以批量生產了，但實際上我們并沒有在這個領域取得進步，搜索最終依然是 NLP 能力的體現，這有點類似于三體中基礎科學被智子鎖死后地球科技的發展。而 wand 和向量檢索與融合則不同，它們重構了信息檢索過程，并分別在一定程度上減輕了對 NLP 能力的依賴，最終卻能在一些 case 下達到一個更好的檢索效果，這也會是我們后續的一個思考方向。
關于性能優化
性能優化是一個非必須，但是又避不開的話題，一方面引擎性能不能太拉垮，但是比性能更值得去建設的事情又太多了，其重要性也就大打折扣了，另一方面，性能優化是一個長期持續的事情，從我們開始這部分工作以來，引擎的召回性能相比最初的版本已經提升了近 50%(最大吞吐能力)。由于搜索引擎是一個比較特殊的 CPU 密集型的服務，其性能優化的思路與一般的業務場景會有所差異，畢竟對大多數業務場景而言，再多的優化方法可能都沒有一次緩存命中的效果好，下面簡要介紹我們在搜索引擎上應用過的優化方法。
搜索引擎進行召回時，需要召回多篇文檔，因此本身就處在一個大的循環的場景中，存在部分代碼段調用時機極為頻繁，即自身存在優化基礎，另一方面，在短平快開發模式下，無法寫出具備較優性能的代碼，也因此引擎在代碼性能方面存在優化空間。
首先是優化位置的定位，引擎本身的代碼大概分為以下幾個場景：
1?程序生命周期級別 2?請求級別 3?請求-文檔級別 4?請求-文檔-字段級別 5?請求-文檔-語法節點級別原則上我們只關注高頻調用的邏輯，即大循環體內，文檔級別以下的場景，另外火焰圖也可以幫助我們定位到熱點函數。
榨取算力
simd 應用的優化效果一般，建議參考。
simd 應用
simd 是通過擴寬單條指令處理的數據流來實現算力的榨取。目前公司的生產環境基本都支持 sse 和 avx256 指令集，倒排查找過程中，Galloping Search 及其變體實現(與 simd 結合后，我們的做法是通過一次 simd 比較就確定查找區間)，以及順序遍歷的查找方式與 simd 的使用剛好是匹配的。通過對倒排查找函數進行 simd 改造，使得整體的查找效率得到了一定幅度的提升。關于 simd 在倒排查找算法上的應用，網上已經有非常多的資料，這里就不再展開講解了，附上在我們的引擎中以及對應的評測數據下，不同倒排查找算法，經 simd 改造后的耗時對比數據，該數據為 block size 為 1024，且索引未壓縮的數據，僅供參考：
遍歷：指順序遍歷查找方式
SSE:指順序遍歷查找方式，使用128bit寄存器及相關的指令集實現版本
AVX:指順序遍歷查找方式，使用256bit寄存器及相關的指令集實現版本
GP: 標準的Galloping Search查找方式（非simd實現方式）
GP + xx：先通過GP確定查找區間，區間內使用xx查找方式
可以看到遍歷是 simd 應用前最佳的查找方式。另外 AVX 相比二分，倒排查找耗時降低了約 26%，由于對于召回模塊而言，倒排查找的消耗只占其中一部分，因此對最終的性能提升的貢獻一般。
不過值得一提的是，由于索引壓縮的需求，我們后續的索引結構里，block size 調整到了 128 附近浮動，這里出現過一個反預期的現象：
在索引不壓縮的情況下，SSE,AVX 等指令集反而是負優化，速度最快的是順序遍歷。
通過分析，我們認為整個倒排查找過程的性能消耗主要由以下兩方面決定：
1?CPU計算2?Memory?Load(L1Cache與寄存器)我們推測，由于在局部性特征的存在，在我們的評測數據下:
1 block size在1024時，引入了太多無效的CPU計算，因此simd指令集應用可以加速整個過程。 2 block size在128附近浮動時，simd指令集引入了太多無效的Memory Load操作，從而導致在不壓縮情況下，反而成為了負優化。指令并發
與 simd 不同，另一種算力榨取的方式為增加單個時間周期里 CPU 處理的指令條數，對應到我們評測體系中的 IPC 指標。深入理解計算機系統一書中對指令并發進行過介紹，其最常見的手段就是循環展開，以及解除指令流中的數據依賴。我們曾經試圖過對此進行應用，場景集中在索引數據的解析中，但最終基本沒什么效果，或者說處在誤差范圍之內。這里很大部分原因在于我們當時的索引結構還未進行過壓縮，沒有找到較合適的應用場景，在解壓操作中該優化方式的優化空間應該會比較大，不過對于新版的索引結構我們還沒有投入時間去針對性優化(目前索引層接口設計歸屬在離線工作中)，因此這方面的最新數據暫時還欠缺。
引擎一直采用的 02 的優化等級，我們也用過 O3 的優化等級去編譯，例如循環展開，函數內聯優化等手段，在 O3 等級中編譯器就會開啟，但是經測試，02 和 03 優化的二進制在性能上沒有差異。原因可能是多方面的，例如引擎內部邏輯比較復雜，在代碼編寫過程中已經很注重使用 inline 了，編譯器的循環展開，內聯優化等手段可能影響很小，也可能是代碼段的膨脹抵銷了收益。
另外 inline 雖然是建議內聯，但是經實踐，O2 優化之下，編譯器會將相關函數都內聯掉。另外類的成員函數如果是 private 方法的話，即便聲明和實現分別在.h 和.cc 文件中，也可以通過 inline 實現內聯。這里強調 private 的原因是，非 private 方法一般會在別的 object 文件中被引用，如果聲明和實現分離，內聯后會導致找不到符號。
內存優化
內存優化的優化效果顯著，強烈建議參考。
內存引用優化
引擎檢索時會涉及到大量的索引數據操作，內部使用了較多的指針，所謂內存引用優化，指的是減少間接尋址的次數。其最簡單的應用為將需要多次訪問的地址(可能在不同函數中訪問)，使用臨時變量將該地址下的值給保存起來，從而避免多次解指針。這一點經實踐確實有效，不過借鑒經驗不大，因為引擎這里還存在一些隱藏屬性，首先索引數據不是內存對齊的，另一點是索引數據比較大，例如我們的評測體系中機器的內存空間占用幾乎達到了 80%，在 NUMA 架構下，內存分為本地內存和非本地內存，如果索引數據處于非本地內存，其訪問速度要慢很多。
我們甚至做過一些測試，將一些索引數據的讀取直接改成了 memcpy，結果發現兩者性能差距可忽略不計，內存訪問對于性能的影響可見一斑。
內存分配優化
檢索過程中會涉及到大量的復雜數據結構的使用，最突出的一點就是文檔的相關性信息中命中信息的存儲。文檔相關性命中信息是一個非常復雜的結構，多層 struct 嵌套，且里面包含大量指針，涉及到堆內存的申請和釋放。所謂的分配優化，并不是單純指減少內存分配函數的調用次數(特別是程序在鏈接上 jemalloc 后，內存分配的開銷已經被弱化過一次),而是指我們試圖讓一次檢索行為涉及到的核心數據結構的內存都處于連續的內存空間。
注：由于 ZeroSearch 本身是多線程環境，且內部存在頻繁的小內存申請和釋放，因此我們目前先選用了 jemalloc 來負責內存管理
內存分配優化給引擎整體的性能帶來了肉眼可見的提升。一種顯而易見的優勢是連續內存分配可以充分利用局部性原理，例如提高程序的 cache 命中率，但經測試這一點的收益占比非常小，其真正的收益在于加速了引擎的資源清理，內存塊的釋放是一種更徹底的析構調用。
不過我們目前在連續內存分配上還沒有做的非常徹底，當前索引層的接口設計里面還大量使用了智能指針來進行內存管理。即便合理運用智能指針和右值引用，當其使用量較大時，其性能損耗依然較高(主要消耗在析構)，下一步我們計劃將在線的內存管理機制滲透進去，預期這里還將帶來可觀的收益。
由于用戶層使用的是虛擬內存空間，用戶層的連續內存分配是無法保證物理上連續的，因此我們并未采取預申請大內存的方案，而是采用鏈表來管理。整個內存管理方案也非常簡單，整體如下圖所示:
默認情況下，單個 Memory Block 的大小為一個(一倍)頁面大小，根據使用場景可自行調整倍數。如果單次申請超出了頁面大小的話，則使用傳入的參數值。釋放的時候，遍歷 Block 鏈表，逐塊釋放即可。但同樣的，內存分配時依然需要注意保持內存對齊的原則，我們的做法也很簡單，保證每次分配的內存塊均為 8 字節的倍數即可。
分支優化
分支優化的優化效果不明顯，略高于誤差范圍，不建議參考。
條件傳送
現代 CPU 多級流水線的實現，一旦分支預測失敗，將導致流水線沖刷，從而帶來性能上的損耗，將一些簡單的條件控制語句轉為條件傳送語句，可有效減少程序分支，從而規避掉該問題。與條件控制語句不同，條件傳送語句將會同時計算兩個分支的結果，最后根據控制條件的結果來選擇計算結果，其最常應用的場景就是賦值運算的代碼塊。例如引擎中存在一些循環代碼塊，形式如下圖所示的代碼：
val_1?=?x，?val_2?=?y; for?(auto?it?:?list) {loop_val?=?it->doSomeThing(args);if?(expr(loop_val)){val_1?=?expr(loop_val);val_2?=?expr(val_1);} }其優化實現為：
val_1?=?x，?val_2?=?y; flag?=?false; for?(auto?it?:?list) {loop_val?=?it->doSomeThing(args);flag?=?expr(loop_val);val_1?=?flag???expr(loop_val)?:?val_1;val_2?=?flag???expr(val_1)?:?val_2; }通過對這兩種形式的代碼塊的匯編代碼進行比較，我們可以發現其中蹊蹺，經 O2 優化之后，三元操作符下，使用的是 cmov 類型的指令，根據 cmp 的計算結果選擇傳值，不會破壞流水線，而 if 分支下使用的是 je 類型的指令，即需要跳轉，一旦預測失敗將導致流水線沖刷。
分支預測
使用 likely,unlikely 等標記也是 coding 級別優化中的常見手段，其作用為將開發者認為更可能被預測為成功的分支的代碼塊移動到前面來，從而提升指令的 cache 命中率，給程序帶來更高的性能。這點在程序的 cache-misses 和 L1-icache-load-misses 指標上會有明顯的體現。但是最終帶來的性能收益并不高。
談到分支預測優化，可能很多人還會想到如何提高分支預測率，但是在不改變程序邏輯的前提下，分支預測率是無法提高的，其基本是由 CPU 自身的分支預測器決定，不過現代 CPU 的分支預測器已經做的足夠好了，正常情況下其正確率都能達到 99%以上。
引擎的代碼在經過多輪優化之后，在分支預測率方面的確也有提升，與最初的版本相比，下降了約 50%(降幅，非絕對值)，它的提升在于兩點，一是整體減少了分支語句，二是編寫了更符合場景規律的代碼。
索引設計
背景：索引設計被劃入在離線的工作中，原先對索引設計的認知是很粗淺的，停留在依葫蘆畫瓢階段，我們先規劃出了，索引數據分為哪些類型，然后針對每種類型的索引數據進行了結構的設計，并獨立存儲。
事實證明，當時的想法是稚嫩的，表面上看，索引設計似乎并不需要遵循什么準則。但是從在線的性能角度去看，把一次操作需要讀取的數據放在一片連續內存，一次性讀出，會比分成多片索引區域，分開讀取性能要好（這一點在磁盤檢索引擎中應該是共識，因為能減少磁盤 IO 次數。但是內存的隨機存取特性讓我們最初設計內存檢索引擎時忽略了這點）。
其收益來自于兩方面，一方面是連續內存讀取將帶來局部性優勢,另一方面是，在每片索引區域讀取一篇文檔的數據的時候，我們都需要一次索引讀取操作以及對應的索引解析操作(雖然大多數時候都是可以直接根據 did 直接內存尋址的)，而分成多片索引區域時需要執行多次這樣的操作。
索引設計的另一準則為盡量保證定長數據的內存對齊，包括適當的內存 padding 的使用，正如內存優化小節提到的，非內存對齊數據的訪問其開銷比我們想像中要大很多。而根據我們的經驗，對于內存搜索引擎來說，其消耗就是由 CPU 消耗和 Memory Load 消耗構成的。
提高緩存命中率其實在絕大部分時候都是一句正確的廢話，其應用場景非常少，即便程序內存 IO 非常龐大時(內存檢索引擎恰恰就是內存 IO 頻繁且龐大的場景)，這一點的收益經實踐也非常小。就像上面內存優化里提的一樣，連續內存最大的優勢在于能夠快速清理。
關于磁盤檢索
盡管我們當前做的是內存檢索引擎，但磁盤檢索引擎的實現其實并不困難。隨著硬件的升級，磁盤檢索引擎的實現難度已經大大降低，例如使用 nvme 通信接口的 ssd 盤，其吞吐速率已經能接近內存的 1/10，每秒吞吐量能達到 GB 級別。由于在線召回架構已經對檢索請求進行了任務粒度的拆分和調度，我們只需要給任務增加一個 IO 狀態便可以完美嵌入到當前的召回架構中。當然，索引結構也需要進行一些細微調整，以進一步減少磁盤 IO 次數。
最后
通過半年多來的追趕，ZeroSearch 完成了從田間燕雀到雛鷹的轉變，以前想過在公司內部開源，現在反而越覺得欠缺的還太多，半成品的東西沒法開源。以前在樂問里看到一句話十分認同：我們總是高估技術的短期效應，而低估它們的長期影響力。我們做的事情其實不如多加一些詞表，多寫一些 if-else 策略的收益來得快，它的價值會由時間來證明，萬丈高樓的搭建需要堅實的地基，在我看來我們做的就是這樣一件事情。
對于引擎設計，其實還有一些想寫的內容，例如 everything online 的設計理念，支持通過請求參數來控制引擎的全部檢索行為，不論是篇數，耗時，還是召回方式的選取上，這樣可以讓業務在召回策略上面進行靈活組織，例如組件化設計，將檢索內核與業務特性模塊隔離，管理好引擎的復雜度，例如召回架構的雙層語法樹設計，支持任意索引類型數據的求交求并，例如引擎內部的問題診斷能力的建設，例如多文本同時檢索等等，限于本文篇幅已經比較長了。
但話說回來，我們做的很多事情其實跟我們當前的索引規模也有很大的關系，由于相比網頁搜索的索引規模少了一個數量級，因此很多事情我們都還不需要考慮，或者側重點不一樣，例如數據量到達一定程度后，索引壓縮比，篇數截斷限制下的倒排求交設計，結果多樣性保障等等都需要提上議程。
本文的內容稍顯雜亂，其實近一年來的時間，所有的工作的展開，我們基于對搜索領域挑戰的認知，背后是有思考在里面的，整體分為 3 個階段：
1 基礎能力建設
搜索引擎首先是一個工程的問題，基礎能力的夯實，將為后續各種基礎設施和檢索能力的建設打下堅實的基礎.
1.1 迭代質量保障
建立了一套全面的評測體系來對引擎質量進行評估，確保持續迭代過程中的版本質量保障.
1.2 工程核心問題解決
算力分配是內存搜索引擎在工程方面的核心問題，我們采用了流水線設計(分配高效)+時間片調度(分配均衡)方案來解決.
1.3 復雜度管理
通過組件化設計，實現了清晰的軟件分層架構，同時保證了檢索內核的獨立性和開放性.
1.4 性能優化專項
從倒排查找算法優化，算力榨取，內存優化，分支優化多個角度進行召回性能優化.
2 進階能力建設
搜索系統的比拼最終會落在 NLP 能力的比拼上面，站在工程這個崗位上，我們的思路是對檢索引擎擴展出豐富的檢索特性，靈活的檢索控制能力，高效的運營/調試能力，最終給與業務同學更大更靈活，以及更高效的操作空間.
2.1 召回架構設計
通過雙層級語法樹設計，兼容多索引類型檢索，支持不同類型索引任意組合的求交求并。
通過原語法樹求交實現，拒絕二項式變換，保留原始檢索語義，進而實現多種召回方式。
2.2 診斷能力建設
衡量大型分布式系統的復雜度管理的標準之一：是否具備高效的運營效率。其最終影響的是整個團隊的迭代效率
2.3 索引實驗能力建設
提供靈活的數據評測手段，如召回實驗，正排實驗。
2.4 Everything Online 的設計理念
讓檢索引擎的一切行為都可以通過請求參數實時控制，讓業務同學可靈活組織其召回策略。
3 團隊效能建設
團隊越大，業務分工越細，每位開發同學對于業務目標達成的邊際效應將越明顯，站在工程這個崗位上，我們的思路是建立必要的公共技術體系，例如將業務目標抽煉為一些公共且必要的技術框架，重新組織和聚合每位開發同學的開發成果，讓其能發光至全部業務。
3.1 公共相關性庫的建設
搭建了一套相關性開發框架，定義了標準開發流程，可靈活組裝，應用范圍能覆蓋搜一搜內部的全部場景。我們希望能將各個小團隊的相關性開發成果組織起來，聚集為大團隊的開發成果，再轉而服務全部業務。
整體來看目前我們比較欠缺的是在接入優化，引擎易用性等方面，這兩塊的投入和建設非常少，不過主要也是人力所限了，歡迎對在線召回感興趣的同學加入我們一起建設。關于搜索引擎工程設計的分享文章就此為止，后續應該不會再寫了。非常感謝老大能給到機會和時間，能脫離業務摸魚一年，還好勉勉強強完成了預期目標，不然只能給擁堵的濱海大廈騰出工位了。最近一年，應該也是職業生涯里寫出最多 BUG 的一年，非常感謝 jacky，sigma, sings，change，jaye，lie，yixiang，leol，levi ... 等等搜索技術中心的同事，在引擎各方面建設還不足并且有坑的時候，就開始接入使用，嚴格來講，搜一搜的技術演進是他們在推動進行的。
后話
回過頭來看 ZeroSearch 第一版在線系統的設計還是比較稚嫩的，當時有幸在騰訊技術工程公眾號上發表過，小編同學還起了個很唬人的標題：新一代搜索引擎設計... 當時看到這個標題時，心情真的十分復雜。
從項目立項開始，這一年來的工程實踐，整個過程更像是一個不斷"破圈"的過程，當我們在圈 A 時，我們看到了圈 B，而當我們到達圈 B 時，我們看到了更廣大的圈 C。以前我們看山是山，認為檢索引擎只是一個工程問題，專注在引擎工程架構的建設上，現在我們看山才是山，專注在業務長遠價值的建設上。
但幫助我們快速實現破圈的其實是落地應用，當技術落地應用后，問題才會凸顯出來，從而彌補我們自身的認知缺陷，最終也反向推動技術應用變得更加成熟，這是一個互相成就的過程。
總結下來是兩句話：
1 做工程技術需要腳踏實地，心懷敬意，直面問題，解決問題。其實不需要什么高端理念指導，也沒有所謂方法論，或者說方法論就是找準問題，用心做事；
2 工程技術是很難實現自突破的，需要伴隨著相應的應用場景，與其一起成長進化。
本人自認為分享過的所有文章都還是比較純粹樸實的，不會有什么空洞的字眼，唬人的概念，力求干貨，正如我所在的團隊的做事風格，純粹務實。搜一搜正在招聘后臺開發和運營開發工程同學，我們致力于通過技術能力將微信生態內的海量精品內容和服務精準觸達到每一位用戶。這是一件極具挑戰但富有意義的事情，很多程序員都可能曾經拷問過自己當初來到互聯網世界的初衷是什么，我相信這件事情足夠我們在回首往事時用來取悅自己。
騰訊程序員視頻號最新視頻
歡迎點贊
總結
以上是生活随笔為你收集整理的微信搜一搜在线检索技术演进复盘的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Mdebug：基于React开发的移动w
- 下一篇： MongoDB 基础浅谈