新一代搜索引擎项目 ZeroSearch 设计探索
本文作者：kaelhua，騰訊 WXG 后臺(tái)開(kāi)發(fā)工程師
背景
寫(xiě)這篇文章很大的原因在于不論是內(nèi)網(wǎng)還是外網(wǎng)，分享內(nèi)存檢索引擎設(shè)計(jì)的資料都非常稀少，且存量的資料大多側(cè)重于功能性的介紹。
另一方面，在磁盤(pán)檢索引擎方面，由于開(kāi)源搜索引擎 ES 的盛行，對(duì)于其使用的索引庫(kù) lucence 的分析資料反而較為豐富。
本文意在通過(guò)分享對(duì)于內(nèi)存檢索引擎的認(rèn)識(shí)，核心的解決方案，和一些優(yōu)化方向的思考等等，略微填補(bǔ)一下關(guān)于內(nèi)存檢索引擎設(shè)計(jì)的資料空缺。
需要說(shuō)明的是本人進(jìn)入搜索領(lǐng)域的時(shí)間并不長(zhǎng)，盡管之前搭建過(guò)一些垂類(lèi)搜索系統(tǒng)，但只是站在應(yīng)用層面進(jìn)行使用，真正從事引擎設(shè)計(jì)的工作也是通過(guò)今年 4 月份左右組內(nèi)重新設(shè)計(jì)新一代搜索引擎的項(xiàng)目 ZeroSearch 開(kāi)始，恰巧承擔(dān)了在線檢索的設(shè)計(jì)與開(kāi)發(fā)。因此這并不是一份多么標(biāo)準(zhǔn)的答案，而是我們對(duì)于引擎設(shè)計(jì)的探索，其質(zhì)量還需時(shí)間檢驗(yàn)和調(diào)整。
本文屬于 ZeroSearch 系列分享中的在線檢索設(shè)計(jì)分享。在本文中假定讀者已經(jīng)對(duì)搜索引擎有了基本的了解，至少對(duì)倒排求交，打分排序有基本的概念。
系統(tǒng)認(rèn)知
對(duì)于系統(tǒng)的認(rèn)知深度，會(huì)決定我們?cè)趺慈タ创齼?nèi)存檢索這樣一個(gè)問(wèn)題，以及由此而產(chǎn)生的的設(shè)計(jì)方案。盡管本文要講的是內(nèi)存檢索引擎設(shè)計(jì)，然而我們還是得從對(duì)磁盤(pán)搜索引擎的認(rèn)識(shí)開(kāi)始。
由于 ES 的盛行，以及網(wǎng)頁(yè)搜索(搜索領(lǐng)域的大 boss)體驗(yàn)的存在，大多數(shù)人對(duì)檢索引擎的認(rèn)識(shí)可能都是基于磁盤(pán)檢索引擎來(lái)理解的，即系統(tǒng)的倒排，正排數(shù)據(jù)都位于磁盤(pán)中，只有在執(zhí)行檢索時(shí)，才會(huì)將相關(guān)的數(shù)據(jù) load 到內(nèi)存中。
其整體的流程大概如圖所示:
磁盤(pán)搜索引擎在設(shè)計(jì)的過(guò)程中面臨的主要問(wèn)題為：
同時(shí)兼具計(jì)算密集型與IO密集型任務(wù)
磁盤(pán)與內(nèi)存及CPU存在數(shù)量級(jí)差距的性能GAP，磁盤(pán)資源屬于瓶頸，而計(jì)算量富余。
因此其在設(shè)計(jì)過(guò)程中考慮的核心要素為兩點(diǎn)：
任務(wù)調(diào)度的設(shè)計(jì)，即管理 IO 任務(wù)與計(jì)算任務(wù)
IO 優(yōu)化 如異步 IO 設(shè)計(jì)，IOCache 優(yōu)化，索引壓縮等等
盡管 IO 優(yōu)化也是非常重要的一環(huán)，但我們認(rèn)為磁盤(pán)搜索引擎的核心，本質(zhì)上是一個(gè)任務(wù)調(diào)度的問(wèn)題。
現(xiàn)在回到內(nèi)存搜索引擎的討論上來(lái)。很明顯，內(nèi)存檢索引擎在去除磁盤(pán) IO 后，其要解決的核心問(wèn)題是計(jì)算量的分配問(wèn)題，即如何合理的分配計(jì)算量，能盡可能的讓優(yōu)質(zhì)結(jié)果展現(xiàn)給用戶(hù)。
下面是我們給內(nèi)存檢索引擎制定的核心流程：
可以看到我們對(duì)于計(jì)算量的分配，抽象出了求交，L1 打分，L2 打分等 3 個(gè)邏輯階段。
求交 即根據(jù)查詢(xún)串取出對(duì)應(yīng)的倒排鏈進(jìn)行求交，得到結(jié)果文檔L1打分 求交出來(lái)的文檔均會(huì)送入L1打分L2打分 L1得分Top的文檔才能進(jìn)入L2打分這里為何要將打分分為兩個(gè)階段呢?
1 滿(mǎn)足高求交數(shù)的需要
由于倒排數(shù)據(jù)處在內(nèi)存中，因此單篇文檔的求交消耗較少，限制引擎召回量的瓶頸往往不在求交，而在打分。輕量級(jí)的打分配合高求交數(shù)，可以避免求交截?cái)鄬?dǎo)致的文檔無(wú)法召回問(wèn)題的出現(xiàn)
2 滿(mǎn)足輕量級(jí)業(yè)務(wù)的打分需求
對(duì)于一些排序較簡(jiǎn)單的業(yè)務(wù)，不需要單獨(dú)的精排服務(wù)，可以在引擎的 L2 打分過(guò)程中滿(mǎn)足它的需求。
需要注意的是對(duì)于一些高消耗的模型，我們會(huì)放在更高層次的排序中，并對(duì)其進(jìn)行抽離，放在獨(dú)立的 tf 服務(wù)上執(zhí)行，并不會(huì)放在引擎的 L1、L2 階段來(lái)執(zhí)行。
L0打分在離線索引過(guò)程中我們會(huì)提供接口用于計(jì)算文檔的質(zhì)量分，因此全量文檔計(jì)算都會(huì)進(jìn)行質(zhì)量分的計(jì)算，建立倒排索引過(guò)程中，質(zhì)量分越高的文檔，排序越靠前，以保證被優(yōu)先查找到
核心設(shè)計(jì)
設(shè)計(jì)背景
在講述核心設(shè)計(jì)之前，需要先了解以下幾點(diǎn)背景
1 索引分片分庫(kù)
索引會(huì)先進(jìn)行分片，多個(gè)分片再合并為一個(gè)索引庫(kù)。分片數(shù)一旦指定后便不可更改，但是索引庫(kù)的庫(kù)數(shù)是可以靈活調(diào)整的，可以滿(mǎn)足業(yè)務(wù)數(shù)據(jù)增長(zhǎng)，索引數(shù)據(jù)多集群劃分的需求。在檢索過(guò)程中，索引庫(kù)是檢索的基本單位。這一點(diǎn)與 ES 可做一個(gè)簡(jiǎn)單的對(duì)比，ES 為庫(kù)->分片(多個(gè)庫(kù))->實(shí)例(多個(gè)分片)的設(shè)計(jì)，而我們的設(shè)計(jì)為分片->庫(kù)(多個(gè)分片)->實(shí)例(多個(gè)庫(kù))，即我們將數(shù)據(jù)分片放到了更底層，打開(kāi)了它的數(shù)量限制，同時(shí)對(duì)庫(kù)的數(shù)量進(jìn)行了收斂，原因在于庫(kù)數(shù)越多，引擎性能將越差。關(guān)于索引分片分庫(kù)的詳細(xì)背景和設(shè)計(jì)后續(xù)組內(nèi)會(huì)另有同學(xué)來(lái)進(jìn)行介紹。
2 無(wú) RPC 框架設(shè)計(jì)
引擎自身不攜帶 RPC 框架，我們以組件化的思想來(lái)進(jìn)行設(shè)計(jì)。通俗來(lái)說(shuō)，就是封裝成了一個(gè)庫(kù)，提供了初始化函數(shù)和唯一的檢索入口函數(shù)來(lái)給到外部進(jìn)行使用。這種方式有優(yōu)有劣，優(yōu)勢(shì)為無(wú)須考慮上層的協(xié)議頭，可靈活適配于各種 RPC 框架中，并復(fù)用已有的運(yùn)維體系。劣勢(shì)為對(duì)線程的控制能力較弱，理想情況下引擎自身的工作線程與 RPC 工作線程應(yīng)當(dāng)資源隔離，通過(guò)親緣性各自分配和獨(dú)占 CPU，這一點(diǎn)在組件化里難以實(shí)現(xiàn)。
事實(shí)上我們是面向 Controller-Proxy-Work 這一類(lèi) RPC 框架進(jìn)行設(shè)計(jì)的，典型的如 SPP,Svrkit 等，并且在我們的實(shí)現(xiàn)過(guò)程中，將預(yù)處理和回包處理的邏輯均放到了 RPC-Work 線程中進(jìn)行。
3 以易用性為第一優(yōu)先級(jí)
組內(nèi)上一代的內(nèi)存搜索引擎由于基礎(chǔ)配置項(xiàng)過(guò)多，引擎細(xì)節(jié)暴露過(guò)多，且欠缺配套的 debug 工具/能力，導(dǎo)致它的學(xué)習(xí)和維護(hù)成本都非常高。在新引擎的設(shè)計(jì)過(guò)程中，我們將易用性列為了第一優(yōu)先級(jí)，本質(zhì)上也是以服務(wù)業(yè)務(wù)為第一優(yōu)先級(jí)，即便是性能方面也需要為易用性讓步。易用性方面主要會(huì)體現(xiàn)在以下幾點(diǎn)：
3.1 引擎的學(xué)習(xí)成本應(yīng)具備梯度，滿(mǎn)足快速入門(mén)使用的需求；
3.2 配置項(xiàng)盡可能少，盡可能避免暴露引擎細(xì)節(jié)，盡可能以通俗語(yǔ)言表達(dá)，如內(nèi)存大小，線程數(shù)量等；
3.3 需要有全面的問(wèn)題定位能力，根據(jù)經(jīng)驗(yàn)，維護(hù)垂搜業(yè)務(wù)時(shí)，最常做的事情就是查文檔為什么召不回，如果引擎具備問(wèn)題一鍵定位的能力，那么可以有效的減少運(yùn)維成本。
需要說(shuō)明的是，盡管這里提到了易用性，但是下面的內(nèi)容不會(huì)涉及到我們?yōu)榱颂嵘嬉子眯圆扇〉木唧w做法。這里之所以單獨(dú)拎出來(lái)進(jìn)行強(qiáng)調(diào)，在于根據(jù)我過(guò)往的業(yè)務(wù)開(kāi)發(fā)經(jīng)驗(yàn)，部門(mén)內(nèi)上一代內(nèi)存搜索引擎的學(xué)習(xí)和維護(hù)成本過(guò)高，與業(yè)務(wù)的快速發(fā)展已經(jīng)不匹配，我認(rèn)為作為一個(gè)基礎(chǔ)平臺(tái)，性能 100 分，還是 80 分，甚至是 70 分，只要可以通過(guò)加機(jī)器來(lái)解決，對(duì)于增長(zhǎng)型業(yè)務(wù)來(lái)說(shuō)基本就不太 care 了，而易用性（含可維護(hù)性）才是最優(yōu)先被考量的因素，其對(duì)團(tuán)隊(duì)的整體效率有很大的影響。
在清楚了大概的設(shè)計(jì)背景之后，可以開(kāi)始真正考慮該如何設(shè)計(jì)我們的檢索引擎了。
線程模型設(shè)計(jì)
下圖是我們的檢索組件目前使用的線程模型：
每個(gè)檢索請(qǐng)求到達(dá)時(shí)，會(huì)生成一系列的求交與打分任務(wù)，在召回完成之后，會(huì)生成一個(gè)資源清理任務(wù)進(jìn)行提交，請(qǐng)求完成。
下面對(duì)圖中的主要元素做下簡(jiǎn)單的介紹
1?主線程 即RPC框架的Work線程，在Work線程中，會(huì)完成請(qǐng)求的預(yù)處理和回包處理的邏輯，并且處理求交或者打分任務(wù)完成后的回調(diào)邏輯。2?JoinThreadPool 負(fù)責(zé)處理求交任務(wù)的線程池，在上面已經(jīng)提到過(guò)，索引會(huì)分片分庫(kù)，索引庫(kù)是檢索的基本單位，而一個(gè)求交任務(wù)至少會(huì)處理一個(gè)索引庫(kù)（由于數(shù)據(jù)實(shí)時(shí)更新，系統(tǒng)中會(huì)存在一些小庫(kù)，多個(gè)小庫(kù)可能會(huì)被放到一個(gè)求交任務(wù)里進(jìn)行處理），每個(gè)求交任務(wù)一旦分配到線程，就會(huì)將任務(wù)完整的執(zhí)行完(或者超時(shí))。3?ScoreThreadPool 負(fù)責(zé)處理打分任務(wù)的線程池，打分任務(wù)分為L(zhǎng)1打分任務(wù)和L2打分任務(wù)，但是線程池是共用的一個(gè)。對(duì)于L1打分任務(wù)，當(dāng)一個(gè)求交任務(wù)完成的求交文檔數(shù)量達(dá)到一定程度時(shí)，便會(huì)生成一個(gè)L1打分任務(wù)Push到打分隊(duì)列中。L2打分任務(wù)同理，也是等到L1打分文檔達(dá)到一定數(shù)量才會(huì)生產(chǎn)。4?CleanThreadPool 負(fù)責(zé)處理資源清理任務(wù)的線程池，即資源的清理是異步進(jìn)行的5?求交資源池 負(fù)責(zé)管理求交時(shí)需要的一些數(shù)據(jù)結(jié)構(gòu)，以資源池的形式來(lái)完成復(fù)用可以看到整個(gè)線程模型是以 Task 為調(diào)度粒度的，這種模型有個(gè)比較大的缺陷，每個(gè) Task 的消耗其實(shí)是不一致的。對(duì)于求交任務(wù)而言，每個(gè)任務(wù)會(huì)將一個(gè)索引庫(kù)給求交完(達(dá)到限制或者超時(shí))，而隨之產(chǎn)生的 L1 打分任務(wù)和 L2 打分任務(wù)，每個(gè)任務(wù)其實(shí)都只是求交出來(lái)的部分文檔，因此求交任務(wù)的消耗是非常高的，并且求交任務(wù)在入隊(duì)時(shí)是在一個(gè) for 循環(huán)里集中式的入隊(duì)（直到所有的索引庫(kù)都分配完），為了防止打分任務(wù)餓死，這里劃分了 3 個(gè)線程池以避免這個(gè)問(wèn)題。
然而劃分多個(gè)線程池本身就是問(wèn)題所在，至少存在以下 3 個(gè)方面的問(wèn)題：1 增加了配置項(xiàng)，降低了易用性。
2 其實(shí)業(yè)務(wù)并不知道該如何去對(duì)各個(gè)線程池的線程數(shù)量進(jìn)行配置(盡管引擎會(huì)簡(jiǎn)單的根據(jù) CPU 邏輯核數(shù)量進(jìn)行默認(rèn)設(shè)置)，只能不斷去調(diào)整測(cè)試來(lái)達(dá)到一個(gè)合適值。
3 多個(gè)線程池的方式不論怎么去配置數(shù)量，都不太可能把所有線程都高效利用起來(lái)，必然會(huì)有計(jì)算資源不能充分利用的線程池存在。
盡管存在這么多很容易預(yù)見(jiàn)的問(wèn)題，我們還是先這樣做了，一方面是目前開(kāi)發(fā)人力非常少，在線檢索這塊的開(kāi)發(fā)只有我一個(gè)人在兼職，需要彌補(bǔ)完善的東西還有很多，整體確實(shí)還比較粗糙，另一方面主要也是目前我們還沒(méi)有建立一個(gè)用于質(zhì)量標(biāo)準(zhǔn)評(píng)測(cè)的系統(tǒng)，因此一些優(yōu)化類(lèi)的工作優(yōu)先級(jí)都排的比較低。
關(guān)于有沒(méi)有餓死情況的出現(xiàn)，我們的評(píng)判標(biāo)準(zhǔn)并不是針對(duì)個(gè)例的發(fā)現(xiàn)，而是通過(guò)統(tǒng)計(jì)p99,p995，p999等指標(biāo)來(lái)進(jìn)行評(píng)判。因此嚴(yán)格意義上來(lái)說(shuō)，也并不是真正的餓死，畢竟FIFO隊(duì)列只要入隊(duì)了遲早會(huì)被執(zhí)行，只是等待時(shí)間長(zhǎng)和短的問(wèn)題。正如標(biāo)題是對(duì)于引擎設(shè)計(jì)的探索，這里簡(jiǎn)單分享一下后續(xù)計(jì)劃要嘗試的幾個(gè)線程模型的方向，當(dāng)然下面所有的方向都是只使用一個(gè)線程池。1 繼續(xù)維持 FIFO 的模式這個(gè)很好理解，也就是所有的 Task 都入同一個(gè)先進(jìn)先出的隊(duì)列，其實(shí)這個(gè)改動(dòng)起來(lái)非常簡(jiǎn)單，只是質(zhì)量標(biāo)準(zhǔn)評(píng)測(cè)系統(tǒng)還沒(méi)搭起來(lái)，就暫時(shí)沒(méi)去做對(duì)比測(cè)試了。
2 邏輯越輕量，優(yōu)先級(jí)越高同樣很好理解，即創(chuàng)建一個(gè)特殊的優(yōu)先級(jí)隊(duì)列，對(duì)各類(lèi) Task 根據(jù)邏輯的繁重設(shè)定一個(gè)優(yōu)先級(jí)，設(shè)想的情況是這樣的，優(yōu)先級(jí)從高到低為：
清理Task > L1Task > L2Task > 求交Task在 Push 任務(wù)時(shí)，優(yōu)先級(jí)越高的直接插入到隊(duì)首，但是同類(lèi) Task 之間依然保持先進(jìn)先出的關(guān)系。最終是一個(gè)這樣的隊(duì)列：
為什么要這樣做呢？
可以有效解決由于求交任務(wù)的高消耗和集中入隊(duì)導(dǎo)致其它任務(wù)餓死的問(wèn)題。通俗一點(diǎn)理解，那就是只有當(dāng)所有的打分任務(wù)都完成了才會(huì)去執(zhí)行求交任務(wù)。
從過(guò)程上看，似乎會(huì)有一個(gè)新的問(wèn)題，即便系統(tǒng)有多個(gè)邏輯核，索引庫(kù)之間的求交打分變成了線性的模式(串行)，而非并發(fā)的模式？
但是從結(jié)果上進(jìn)行分析，這種調(diào)度模式是否改變了處理請(qǐng)求時(shí)所需要的計(jì)算量？很明顯，并沒(méi)有。同樣的，單位時(shí)間內(nèi)機(jī)器的算力也并沒(méi)有浪費(fèi)，因?yàn)槌钦?qǐng)求已經(jīng)完成，否則一旦有空閑線程出現(xiàn)，那么必定會(huì)被分配給求交任務(wù)。那么至少?gòu)慕Y(jié)果上來(lái)分析，這種模式應(yīng)該是有效的，當(dāng)然具體效果優(yōu)劣，數(shù)據(jù)表現(xiàn)如何，還需實(shí)驗(yàn)驗(yàn)證。
以邏輯越輕量，優(yōu)先級(jí)越高的優(yōu)先級(jí)隊(duì)列管理任務(wù)似乎會(huì)引入一個(gè)新的問(wèn)題，即求交任務(wù)可能被'餓死'?？?這一點(diǎn)很難評(píng)判，原因在于兩點(diǎn)1 打分任務(wù)其實(shí)是由求交任務(wù)產(chǎn)生，如果求交任務(wù)得不到執(zhí)行，那么也就不會(huì)有打分任務(wù)了。2 單個(gè)打分任務(wù)的文檔數(shù)較少，邏輯相對(duì)較輕，影響較小。具體還是需要實(shí)驗(yàn)驗(yàn)證后才能得出明確結(jié)論。3 以時(shí)間片為調(diào)度粒度徹底改變 Task 為調(diào)度粒度的模式，換為時(shí)間片的模式，同時(shí)繼續(xù)保持 FIFO 的模式，每個(gè) Task 消耗完時(shí)間片后就被丟入隊(duì)尾，直至超時(shí)或完成。
以時(shí)間片為調(diào)度粒度時(shí)，此時(shí)眾生平等，也就不需要關(guān)注 Task 之間的消耗程度孰輕孰重帶來(lái)的餓死情況輕重的問(wèn)題了。 時(shí)間片調(diào)度這種模式其實(shí)還有一個(gè)好處，對(duì)于一些召回?cái)?shù)過(guò)低的請(qǐng)求，大概率在一個(gè)時(shí)間片內(nèi)就能被執(zhí)行完，那么它總體的等待時(shí)間就會(huì)少很多，從它要入隊(duì)時(shí)開(kāi)始分析，等待時(shí)間由：
sum(隊(duì)列Task-處理完成所需耗時(shí)之和)降低到 sum（隊(duì)列 Task-時(shí)間片之和），但這種模式有沒(méi)有被引入的問(wèn)題？
同樣有的，對(duì)于高召回的請(qǐng)求需要多個(gè)時(shí)間片才能執(zhí)行完，由于每次時(shí)間片執(zhí)行完需要重新入隊(duì)，那么它的等待時(shí)間相比 Task 的模式大概率是會(huì)增加的。不過(guò)這個(gè)問(wèn)題相對(duì)來(lái)說(shuō)還比較好解決，至少我們可以從以下兩點(diǎn)來(lái)緩解和解決。
1 增大時(shí)間片的粒度即將時(shí)間片粒度變大，如由原先的 500us，增大為 1ms。從而可變相減少高召回請(qǐng)求的入隊(duì)次數(shù)。當(dāng)然這里也需要控制力度，極端情況下會(huì)退化為 Task 模式。
2 增大高召回請(qǐng)求的時(shí)間片粒度即給高召回請(qǐng)求的分配的時(shí)間片為基礎(chǔ)的時(shí)間片*2，或者*3 等等，這是一種有效解決高召回請(qǐng)求入隊(duì)次數(shù)過(guò)多的方法。但是難點(diǎn)在于我們?nèi)绾巫R(shí)別出高召回請(qǐng)求？這是一件很有挑戰(zhàn)性的事情，不過(guò)這里先不介紹我們?cè)诨I劃的做法，下文中會(huì)提到。事實(shí)上，它不止對(duì)于線程模型調(diào)度的設(shè)計(jì)有直接影響，對(duì)于稍后介紹的任務(wù)模型同樣有影響。
細(xì)心的讀者可能已經(jīng)想到了，高召回請(qǐng)求是從結(jié)果上來(lái)看的，當(dāng)我們從過(guò)程上來(lái)看時(shí)，問(wèn)題就簡(jiǎn)單很多了，即回到了問(wèn)題本身，它是入隊(duì)次數(shù)過(guò)多的請(qǐng)求。那么我們只需要增加每次重新入隊(duì)時(shí)被分配的時(shí)間片即可，一種最簡(jiǎn)單的方式是參考 vector 的內(nèi)存增長(zhǎng)的方式，更高級(jí)的方式這里就不展開(kāi)了，索引數(shù)據(jù)和求交進(jìn)度也是分配的參考項(xiàng)。從而有效解決高召回請(qǐng)求入隊(duì)次數(shù)過(guò)多的問(wèn)題。不過(guò)同樣，這里的增長(zhǎng)也需要控制力度，極端情況下會(huì)退化為 Task 模式。
線程模型的介紹暫時(shí)就到這里了，下面我們看一下任務(wù)模型的設(shè)計(jì)。
任務(wù)模型設(shè)計(jì)
任務(wù)模型與線程模型有什么區(qū)別呢？
線程模型更專(zhuān)注于計(jì)算量(任務(wù))的執(zhí)行，而任務(wù)模型更專(zhuān)注于計(jì)算量(任務(wù))的分配。對(duì)于執(zhí)行者來(lái)說(shuō)，它是任務(wù)無(wú)關(guān)的，而對(duì)于分配者來(lái)說(shuō)，它本身就是任務(wù)的創(chuàng)建者，與任務(wù)是強(qiáng)相關(guān)的。在介紹線程模型時(shí)，其實(shí)我們已經(jīng)大概清楚了，引擎中有以下 4 類(lèi)任務(wù)，分別為清理任務(wù)，求交任務(wù)，L1 打分任務(wù)，L2 打分任務(wù)。其中清理任務(wù)較為獨(dú)立，就不多花筆墨介紹了。
下面直接看我們的求交打分任務(wù)模型：
任務(wù)模型的核心要素為以下 3 點(diǎn)：
1?求交依然維持單庫(kù)單線程求交(小庫(kù)例外，多個(gè)小庫(kù)合并一個(gè)求交任務(wù))2?求交文檔達(dá)到閾值時(shí)生成一個(gè)L1打分任務(wù)3?L1打分文檔達(dá)到一定閾值時(shí)生成一個(gè)L2打分任務(wù)從而可以實(shí)現(xiàn)求交、L1 打分、L2 打分并行執(zhí)行的效果，整體達(dá)到一個(gè)流水線的設(shè)計(jì)，就如上圖所示一樣。組內(nèi)的上一代內(nèi)存搜索引擎對(duì)于求交打分是一個(gè)階段一個(gè)階段的執(zhí)行，整體是一個(gè)串行的模式
求交階段 ---> L1打分階段 ---> L2打分階段在實(shí)際的實(shí)現(xiàn)里，上一代引擎對(duì)于每一個(gè)索引庫(kù)其實(shí)是單線程邊求交邊 L1 打分的（因此本質(zhì)上屬于串行），等全部求交文檔 L1 打分執(zhí)行完畢后，再進(jìn)行一次快速選擇排序選出 TopK 得分的文檔，然后把這部分文檔送入 L2 打分，L2 打分結(jié)束后，進(jìn)行最終的 TopK 排序，然后進(jìn)入回包處理階段。
在新引擎中，我們將求交與 L1 打分進(jìn)行了拆分，并對(duì)打分任務(wù)以 Task 為粒度進(jìn)行調(diào)度。為什么要這樣做呢？當(dāng)然是因?yàn)檫@是一種 CPU 利用率更高的做法。下面我們進(jìn)行一個(gè)討論，在這個(gè)討論里我們先假定引擎的工作線程池只有一個(gè)，這樣的話(huà)更利于分析。
假設(shè)索引庫(kù)數(shù)?=?CPU邏輯核數(shù)1?在一個(gè)線程處理一個(gè)庫(kù)內(nèi)文檔的求交與L1打分的形式下，各個(gè)線程耗時(shí)計(jì)算方式是固定的 |?------------------|-------------------|求交耗時(shí)?+??l1打分耗時(shí) 最終耗時(shí)為:?max(各個(gè)庫(kù)的求交耗時(shí)+l1打分耗時(shí))2?如果我們將求交與打分拆開(kāi)，每次求交部分后，再將這部分送出去進(jìn)行打分，讓打分 獨(dú)立出來(lái)，從而達(dá)到流水線化: |?------------------|求交耗時(shí)|-------------------|打分耗時(shí) |-------------------------|總耗時(shí) 理想情況下，最終耗時(shí)為: sum(各個(gè)庫(kù)的求交耗時(shí)+l1打分耗時(shí))?/?引擎工作線程數(shù)?=?avg(各個(gè)庫(kù)的求交耗時(shí)+l1打分耗時(shí)) 原因是計(jì)算總量雖然并未減少，但是被打散得更均勻了。很明顯這種模式能更好的利用CPU資源假設(shè)索引庫(kù)數(shù)?>?CPU邏輯核數(shù)3 將會(huì)出現(xiàn)一個(gè)線程處理多個(gè)索引庫(kù)，我們可以理解為這多個(gè)索引庫(kù)只是一個(gè)更大的索引庫(kù)，從而問(wèn)題回歸到討論1與討論2中。假設(shè)索引庫(kù)數(shù)?<?CPU邏輯核數(shù)4?老模式下其最終耗時(shí)依然為:max(各個(gè)庫(kù)的求交耗時(shí)+l1打分耗時(shí))新模式下其最終耗時(shí)為: (sum(各個(gè)庫(kù)的求交耗時(shí)+l1打分耗時(shí))?-?非求交線程承擔(dān)的L1打分耗時(shí)?)?/?求交線程數(shù) 該值比avg(各個(gè)庫(kù)的求交耗時(shí)+l1打分耗時(shí))會(huì)更小。盡管拆分后的方式 CPU 利用率更高，但是很明顯，新的方式在總吞吐方面并不會(huì)提高。
計(jì)算基礎(chǔ) 1?單位時(shí)間內(nèi)機(jī)器的算力是固定的2?每個(gè)請(qǐng)求需要消耗的算力并沒(méi)用變因此在極限情況下，吞吐方面確實(shí)沒(méi)有提升。不過(guò)實(shí)際上，在正常情況下，我們都會(huì)保證機(jī)器的負(fù)載在一個(gè)較低的水平，以此來(lái)保證服務(wù)的安全，而當(dāng)機(jī)器負(fù)載未滿(mǎn)時(shí)，新模式下長(zhǎng)尾求交任務(wù)通過(guò)把l1打分邏輯分發(fā)出去可以更充分利用總的CPU資源，從而減少請(qǐng)求的耗時(shí)。我們可以得出以下兩個(gè)結(jié)論：
新模式在極限情況下的總吞吐沒(méi)有提升
相同吞吐情況下，新模式 CPU 利用率更高，因此請(qǐng)求處理平均耗時(shí)會(huì)更少
另外一個(gè)問(wèn)題，為什么我們要維持單庫(kù)單線程求交？簡(jiǎn)單來(lái)說(shuō)，求交不是召回瓶頸，當(dāng)然如果真的發(fā)生了這種事情，求交成為了召回瓶頸時(shí)，我們的建議是減少每個(gè)索引庫(kù)包含的分片數(shù)。
最后，細(xì)心的讀者可能早早就發(fā)現(xiàn)了，求交出來(lái)的文檔是需要都送入 L1 打分的，但是只有 L1 得分 Top 的文檔才能進(jìn)入 L2 打分，整個(gè)任務(wù)模型里的求交-L1 打分-L2 打分的流水線處理應(yīng)該無(wú)法實(shí)現(xiàn)才對(duì)。的確是的，求交結(jié)果進(jìn)入 L1 打分是一個(gè)確定的行為，而 L1 打分結(jié)果是否進(jìn)入 L2 打分是一個(gè)待定的行為。為了滿(mǎn)足流水線的計(jì)算，我們需要將待定行為轉(zhuǎn)為確定行為。
1 文檔預(yù)估
如果我們能夠知道一個(gè)請(qǐng)求能求交得到多少篇文檔，那么當(dāng)求交文檔數(shù) < L1 結(jié)果限制數(shù)（TopK 里的 k 值），那么很明顯，所有完成了 L1 打分的文檔都可以直接進(jìn)入 L2 打分。
1.1 根據(jù)文檔頻率預(yù)估這是一種簡(jiǎn)單粗暴的方式，例如用戶(hù)搜索[蘋(píng)果手機(jī)],它的分詞結(jié)果得[蘋(píng)果 | 手機(jī)]，兩者的關(guān)系為求交，那么這個(gè) query 的預(yù)估召回文檔數(shù)就為：
min（Term(蘋(píng)果)倒排鏈長(zhǎng)度，Term(手機(jī))倒排鏈長(zhǎng)度）如果考慮到蘋(píng)果手機(jī)整體與 iphone 同義，那么其預(yù)估召回文檔數(shù)就為：
max（Term(iphone)倒排鏈長(zhǎng)度，min（Term(蘋(píng)果)倒排鏈長(zhǎng)度，Term(手機(jī))倒排鏈長(zhǎng)度)）即根據(jù)各個(gè) Term 的文檔頻率和其邏輯關(guān)系來(lái)進(jìn)行簡(jiǎn)單的推導(dǎo)。很明顯，實(shí)際求交文檔數(shù)，一定會(huì)小于等于該推導(dǎo)值。
1.2 緩存查表由于一定時(shí)間內(nèi)的索引數(shù)據(jù)是相對(duì)穩(wěn)定的，我們可以通過(guò)緩存檢索 query 和求交數(shù)的映射關(guān)系，每個(gè)請(qǐng)求到達(dá)時(shí)進(jìn)行一次查表來(lái)完成預(yù)估?？赡苡凶x者會(huì)質(zhì)疑，那為什么不直接緩存求交結(jié)果呢?
其實(shí)這是兩個(gè)維度的東西，它們本身也并不沖突，如果在引擎內(nèi)對(duì)結(jié)果緩存會(huì)占用較多的內(nèi)存，我們期望的做法是在更上層對(duì)分頁(yè)后的結(jié)果進(jìn)行緩存，因?yàn)榭梢悦鞔_的一點(diǎn)是首頁(yè)的緩存命中率一定會(huì)顯著高于后續(xù)的結(jié)果頁(yè)。另外引擎內(nèi)進(jìn)行緩存的話(huà)還會(huì)影響系統(tǒng)的時(shí)效性，這一點(diǎn)并不合適。
1.3 模型預(yù)估通過(guò)模型來(lái)對(duì)一個(gè) query 的召回文檔數(shù)進(jìn)行預(yù)估。由于每個(gè)業(yè)務(wù)的數(shù)據(jù)量是相對(duì)穩(wěn)定的，可以通過(guò)在線收集 query 和查 詢(xún)語(yǔ)法樹(shù)的特征以及倒排鏈相關(guān)的特征，離線訓(xùn)練，在線接入，來(lái)完成預(yù)估。
2 預(yù)計(jì)算即選出一部分 L1 打分完成的文檔，先進(jìn)行 L2 打分計(jì)算。目前我們實(shí)現(xiàn)的方式有以下幾種：
2.1 固定篇數(shù)模式取固定的 l1 結(jié)果數(shù)進(jìn)行預(yù)計(jì)算,原則為先完成 l1 打分的文檔將會(huì)被送入，這是因?yàn)橛捎?l0 得分的存在,通常我們認(rèn)為越先被求交出來(lái)的文檔,其質(zhì)量越高
2.2 得分閾值模式l1 得分大于得分閾值的進(jìn)行預(yù)計(jì)算
2.3 得分比例模式l1 得分大于 (已完成 l1 打分的文檔的平均分 * rate) 的文檔進(jìn)行預(yù)計(jì)算，因此其實(shí)這是一種特殊的得分閾值模式，只是它的閾值在不斷調(diào)整。
由于我們目前只有一些較簡(jiǎn)單的離線業(yè)務(wù)接入了新引擎，上面幾種方案的具體效果如何還沒(méi)有得到一個(gè)可信的數(shù)據(jù)。另外后續(xù)也會(huì)考慮不斷加入新的預(yù)計(jì)算方式，例如將固定篇數(shù)模式與得分閾值模式組合起來(lái)使用。
事實(shí)上，預(yù)計(jì)算幾乎肯定會(huì)有浪費(fèi)計(jì)算量的情況出現(xiàn)，即本不能進(jìn)入 L2 打分的文檔卻被執(zhí)行了 L2 打分。其浪費(fèi)率以及耗時(shí)降低的收益需要根據(jù)各個(gè)業(yè)務(wù)自己的需求而定。
需要特別說(shuō)明的是，新引擎在 L1 打分階段完成之后（求交階段已完成，且 L1 打分任務(wù)全部完成），依然會(huì)整體進(jìn)入 L2 打分階段，對(duì) L1 結(jié)果集取 TopK，然后分配 L2 打分任務(wù)，只是每個(gè) L2 打分任務(wù)對(duì)分配到的文檔進(jìn)行打分時(shí)會(huì)先判斷是否已經(jīng)被預(yù)計(jì)算過(guò)了，如果是的話(huà)則直接跳過(guò)。因此預(yù)計(jì)算的存在并不會(huì)導(dǎo)致結(jié)果不穩(wěn)定的問(wèn)題出現(xiàn)。
求交設(shè)計(jì)
求交設(shè)計(jì)分為兩塊，一塊是語(yǔ)法樹(shù)求交設(shè)計(jì)，主要是查詢(xún)語(yǔ)法樹(shù)的設(shè)計(jì)和求交算法。另一塊是查找算法設(shè)計(jì)，主要介紹倒排查找的做法。
語(yǔ)法樹(shù)求交設(shè)計(jì)
對(duì)于求交而言，基本的理解其實(shí)就是取出幾條倒排鏈，然后計(jì)算出倒排鏈中公共的文檔。不過(guò)實(shí)際情況比這個(gè)要復(fù)雜很多。對(duì)于求交設(shè)計(jì)而言，第一步要考慮的是查詢(xún)語(yǔ)法樹(shù)的設(shè)計(jì)，我們從同義詞開(kāi)始，在新引擎的設(shè)計(jì)里，我們采用的 3 層結(jié)構(gòu)語(yǔ)法樹(shù)。假設(shè) [蘋(píng)果手機(jī)] 存在同義詞 [iphone],那么對(duì)于 query [蘋(píng)果手機(jī)回收] 的最終的檢索語(yǔ)法樹(shù)為下圖所示：
這里以寬度優(yōu)先的方式給每個(gè)節(jié)點(diǎn)進(jìn)行了編號(hào)?？梢钥吹竭@是一顆 and-or-and 的語(yǔ)法樹(shù)，可以支持多對(duì)多的同義詞表達(dá)形式,例如這里的節(jié)點(diǎn) 2 下面的兩個(gè)同義詞詞組，就是一個(gè) 2 對(duì) 1 的同義詞組。
現(xiàn)在我們要需要考慮一下這樣的一顆語(yǔ)法樹(shù)如何做召回。一種很直觀的做法是這樣的：
1?節(jié)點(diǎn)6與節(jié)點(diǎn)7的倒排鏈進(jìn)行求交，得到的pageid作為節(jié)點(diǎn)4的pageid2?節(jié)點(diǎn)2的pageid?=?min(節(jié)點(diǎn)4?pageid，節(jié)點(diǎn)5?pageid)3?比較節(jié)點(diǎn)2的pageid與節(jié)點(diǎn)3的pageid3.1?節(jié)點(diǎn)2?pageid?=?節(jié)點(diǎn)3?pageid 則彈出該節(jié)點(diǎn)作為求交結(jié)果，所有節(jié)點(diǎn)對(duì)應(yīng)的倒排鏈后移一位3.2?節(jié)點(diǎn)2?pageid?<?節(jié)點(diǎn)3?pageid 節(jié)點(diǎn)2先內(nèi)部求交得到一個(gè)大于等于節(jié)點(diǎn)3?pageid的文檔3.3?節(jié)點(diǎn)2?pageid?>?節(jié)點(diǎn)3?pageid 節(jié)點(diǎn)3對(duì)應(yīng)的倒排鏈查找第一個(gè)大于等于節(jié)點(diǎn)2?pageid的文檔上述過(guò)程一直持續(xù)有節(jié)點(diǎn)2或者節(jié)點(diǎn)3有節(jié)點(diǎn)到達(dá)了末尾為止。其中節(jié)點(diǎn)2由于是一顆子樹(shù)，它是否到達(dá)末尾，由其子節(jié)點(diǎn)節(jié)點(diǎn)4與節(jié)點(diǎn)5到達(dá)了末尾為止，節(jié)點(diǎn)4同理。關(guān)于pageid 在建索引庫(kù)時(shí)我們會(huì)對(duì)進(jìn)入到該索引庫(kù)的文檔按L0得分排序，從0開(kāi)始重新編號(hào)，當(dāng)然庫(kù)內(nèi)會(huì)有一片區(qū)域保存庫(kù)內(nèi)pageid到原docid的映射關(guān)系。這一點(diǎn)的主要目的是為了保證倒排鏈中的文檔按L0得分排列后依然有序，次要目的是為了對(duì)倒排鏈進(jìn)行壓縮。但是對(duì)于內(nèi)存搜索引擎而言，我們暫時(shí)還沒(méi)有嘗試對(duì)倒排鏈進(jìn)行壓縮，一方面是因?yàn)镃PU同樣是緊張資源，另一方面團(tuán)隊(duì)也還沒(méi)有精力投入到這一塊。因此目前其最大的作用只是保證了倒排鏈中的文檔id有序，以及庫(kù)內(nèi)文檔id的連續(xù)(從而可以根據(jù)庫(kù)內(nèi)文檔id直接下標(biāo)訪問(wèn)文檔數(shù)據(jù))，另外把8字節(jié)的文檔id，轉(zhuǎn)成了4字節(jié)的庫(kù)內(nèi)pageid，省了一半內(nèi)存。本人之前聽(tīng)到過(guò)多次這樣的說(shuō)法：語(yǔ)法樹(shù)的層級(jí)越高，求交的性能就會(huì)越差。如果是按照我上面所述的求交方式的話(huà)，那么的確是的，層級(jí)越高，求交性能就會(huì)越差。原因是什么呢？
原因在于高層級(jí)的語(yǔ)法樹(shù)進(jìn)行求交時(shí)可能會(huì)存在一些不必要的求交行為。以上面的那顆 3 層語(yǔ)法樹(shù)為例，假如節(jié)點(diǎn) 6[蘋(píng)果]和節(jié)點(diǎn) 7[手機(jī)]這兩條倒排鏈中的 pageid 都非常小，而節(jié)點(diǎn) 3 的 pageid 比較大時(shí)，那么有可能節(jié)點(diǎn) 2 所有的求交結(jié)果都來(lái)自節(jié)點(diǎn) 5。
那為什么會(huì)存在一些不必要的求交行為呢？其本質(zhì)在于上面所述的求交方式是一種邏輯先驗(yàn)的求交算法。下面介紹一種邏輯后驗(yàn)的算法。
定義求交基準(zhǔn)為一個(gè)可能的求交結(jié)果1?計(jì)算求交基準(zhǔn)N?=?max(?min(?max(節(jié)點(diǎn)6?pageid,?節(jié)點(diǎn)7?pageid),?節(jié)點(diǎn)5?pageid),?節(jié)點(diǎn)3?pageid)2?所以倒排鏈全部往N靠攏，找到第一個(gè)>=N的位置3 判斷所有倒排鏈當(dāng)前的結(jié)果是否符合求交邏輯關(guān)系，若符合則彈出結(jié)果且相關(guān)節(jié)點(diǎn)后移一位。4?判斷是否求交結(jié)束，如果未結(jié)束則流程回到1，否則退出求交損耗的本質(zhì)為各條倒排鏈的跳躍查找次數(shù)，and/or 等語(yǔ)法只是建立在倒排鏈的跳躍查找之上的邏輯關(guān)系，跳躍查找次數(shù)越少的，性能也就越好。在邏輯后驗(yàn)求交算法里，每次選出的求交基準(zhǔn) N 都是一個(gè)可能的求交結(jié)果，也就是說(shuō)除非我們能找到新的算法可以再次排除一些可能的求交結(jié)果位置，否則不會(huì)有比它性能更好的語(yǔ)法樹(shù)求交算法。
現(xiàn)在嘗試一下將語(yǔ)法樹(shù)打平，看一下打平后的語(yǔ)法樹(shù)具備哪些方面的優(yōu)勢(shì)。這里要介紹的是我們上一代內(nèi)存搜索引擎中將 3 層結(jié)構(gòu)語(yǔ)法樹(shù)轉(zhuǎn)化為 2 層結(jié)構(gòu)語(yǔ)法樹(shù)進(jìn)行求交的做法。
笛卡爾積語(yǔ)法樹(shù)
通過(guò)將 3 層語(yǔ)法樹(shù)結(jié)構(gòu)里的同義詞節(jié)點(diǎn)做笛卡爾積，可得到與其等效的 2 層結(jié)構(gòu)語(yǔ)法樹(shù)，還是以 query [蘋(píng)果手機(jī)回收] 為例，其中 [蘋(píng)果手機(jī)]和[iphone] 互為同義詞,將其轉(zhuǎn)換為笛卡爾積語(yǔ)法樹(shù)后，其結(jié)構(gòu)如下圖所示
其原理為 (A?&&?B)?||?(C?&&?D) =?(A?||?(C?&&?D))?&&?(B?||?(C?&&?D)) =?(A?||?C)?&&?(A?||?D)?&&?(B?||?C)?&&?(B?||?D)當(dāng)然這里的同義詞組更簡(jiǎn)單，為(A && B) || C 的模式。下面我們分析一下笛卡爾積語(yǔ)法樹(shù)與原語(yǔ)法樹(shù)的差別。
求交性能分析
為了能夠更具體一點(diǎn)的了解不同語(yǔ)法樹(shù)之間的性能差異。我們需要對(duì)求交性能做一個(gè)定量的分析。下面對(duì) 3 層結(jié)構(gòu)的原語(yǔ)法樹(shù)和其對(duì)應(yīng)的笛卡爾積語(yǔ)法樹(shù)各自的求交過(guò)程來(lái)進(jìn)行性能分析，依然以蘋(píng)果手機(jī)回收這個(gè) case 為例。
1?原語(yǔ)法樹(shù)求交基準(zhǔn)的計(jì)算公式:(此處直接以Term值來(lái)表示對(duì)應(yīng)Term節(jié)點(diǎn)) max?(?min(蘋(píng)果?&&?手機(jī)??,?iphone)??,?回收)笛卡爾積語(yǔ)法樹(shù)求交基準(zhǔn)的計(jì)算公式: max(?min(蘋(píng)果,iphone)?,?min(手機(jī),iphone)?,??回收)2?給定一個(gè)基準(zhǔn)的前提下:源語(yǔ)法樹(shù)需要操作的語(yǔ)法節(jié)點(diǎn)為4個(gè)，對(duì)應(yīng)為4條倒排鏈笛卡爾積語(yǔ)法樹(shù)需要操作的語(yǔ)法樹(shù)節(jié)點(diǎn)為5個(gè)，對(duì)應(yīng)為5條倒排鏈3?兩種類(lèi)型的語(yǔ)法樹(shù)結(jié)束條件較為相似，都是某一顆子樹(shù)到達(dá)末尾 源語(yǔ)法樹(shù)結(jié)束條件: (End(蘋(píng)果?||?手機(jī))??&&??End(iphone))??||??End(回收) 笛卡爾積語(yǔ)法樹(shù)結(jié)束條件: (End(蘋(píng)果?||?iphone)?||?End(手機(jī)?||?iphone))?||?End(回收) 由于 End(蘋(píng)果?||?手機(jī))??&&??End(iphone)?=?End(蘋(píng)果?||?iphone)?||?End(手機(jī)?||?iphone) 因此結(jié)束條件的位置其實(shí)是一致的。為了簡(jiǎn)化性能評(píng)估，我們假定每次語(yǔ)法節(jié)點(diǎn)的操作損耗相同，則性能評(píng)估的大致公式為:
從公式上來(lái)看，決定性能的因素主要有以下 4 點(diǎn)：
求交基準(zhǔn)總數(shù)
語(yǔ)法節(jié)點(diǎn)個(gè)數(shù)
求交基準(zhǔn)選取損耗
語(yǔ)法樹(shù)節(jié)點(diǎn)操作個(gè)數(shù)
現(xiàn)在我們來(lái)對(duì)比下打平后的笛卡爾積語(yǔ)法樹(shù)和原語(yǔ)法樹(shù)之間的差異。
1 求交基準(zhǔn)總數(shù)由于(A && B) || C = (A || C) && ( B || C),因此兩顆語(yǔ)法樹(shù)的最終邏輯肯定是一致的，只是表現(xiàn)形式不一樣而已，那么僅從公式上，可以知道這兩顆語(yǔ)法樹(shù)的求交基準(zhǔn)個(gè)數(shù)肯定是一樣多的（這句話(huà)其實(shí)是有一些問(wèn)題的，不過(guò)可以先這么理解）。
2 語(yǔ)法樹(shù)節(jié)點(diǎn)個(gè)數(shù)很明顯，笛卡爾積語(yǔ)法樹(shù)的語(yǔ)法節(jié)點(diǎn)數(shù)會(huì)大于原語(yǔ)法樹(shù)的節(jié)點(diǎn)個(gè)數(shù)，(A && B) || C ==> (A || C) && ( B || C)的轉(zhuǎn)換，其實(shí)是析取范式到合取范式的一個(gè)轉(zhuǎn)換，并且恰好屬于轉(zhuǎn)換后會(huì)導(dǎo)致子句指數(shù)型暴漲的情況，即同義詞組的個(gè)數(shù)越多，每個(gè)同義詞的葉子節(jié)點(diǎn)越多，那么轉(zhuǎn)換后的語(yǔ)法樹(shù)節(jié)點(diǎn)就越多，并呈指數(shù)型增長(zhǎng)。語(yǔ)法樹(shù)節(jié)點(diǎn)越多，求交時(shí)的邏輯也就越重。
3 求交基準(zhǔn)選取損耗對(duì)于求交基準(zhǔn)的選取損耗很明顯是跟語(yǔ)法樹(shù)節(jié)點(diǎn)個(gè)數(shù)強(qiáng)相關(guān)的，由于笛卡爾積語(yǔ)法樹(shù)的語(yǔ)法樹(shù)節(jié)點(diǎn)遠(yuǎn)超原語(yǔ)法樹(shù)，因此笛卡爾積語(yǔ)法樹(shù)每次的求交基準(zhǔn)選取損耗都會(huì)大于原語(yǔ)法樹(shù)。
4 語(yǔ)法樹(shù)節(jié)點(diǎn)操作個(gè)數(shù)笛卡爾積語(yǔ)法樹(shù)層數(shù)降低為了 2 層，并且消除了第 3 層的 and 邏輯，整顆語(yǔ)法樹(shù)只剩下最頂層的 and 邏輯。這一點(diǎn)有什么優(yōu)勢(shì)呢？我們?cè)趯?duì) and 節(jié)點(diǎn)下的子節(jié)點(diǎn)進(jìn)行求交的時(shí)候，往往都是一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的操作，因此如果只剩下最頂層的 and 節(jié)點(diǎn)的時(shí)候，一旦發(fā)現(xiàn)有節(jié)點(diǎn)經(jīng)過(guò)跳躍查找后，跟求交基準(zhǔn)的值不一致，可以很方便的提前就結(jié)束掉對(duì)于該求交基準(zhǔn) N 的查找，即可以很方便的提前排除掉求交基準(zhǔn) N。
這一點(diǎn)對(duì)于笛卡爾積語(yǔ)法樹(shù)來(lái)說(shuō)是一個(gè)優(yōu)勢(shì)，可以減少排除一個(gè)基準(zhǔn)的需要操作的節(jié)點(diǎn)個(gè)數(shù)。但是其只是降低了提前結(jié)束求交基準(zhǔn) N 的查找的代碼實(shí)現(xiàn)的復(fù)雜度，對(duì)邏輯后驗(yàn)求交算法進(jìn)行改進(jìn)后同樣可以實(shí)現(xiàn)。
改進(jìn)的邏輯后驗(yàn)求交算法當(dāng)我們得出一個(gè)求交基準(zhǔn)時(shí)，各條倒排鏈都需要進(jìn)行跳躍查找第一個(gè)大于等于求交基準(zhǔn) N 的值，我們可以通過(guò)在查找過(guò)程中就更新求交基準(zhǔn) N 的值，從而減少后續(xù)每條倒排鏈的查找次數(shù)
經(jīng)過(guò)對(duì)比后可以發(fā)現(xiàn)，語(yǔ)法樹(shù)打平之后其實(shí)并沒(méi)有什么優(yōu)勢(shì)，并且會(huì)導(dǎo)致語(yǔ)法節(jié)點(diǎn)數(shù)指數(shù)型增長(zhǎng)，因此我們目前認(rèn)為使用原語(yǔ)法樹(shù)配合邏輯后驗(yàn)求交算法就是內(nèi)存檢索引擎最佳的求交方式。這種想法當(dāng)然有點(diǎn)坐井觀天了，如果有讀者有更好的方式，歡迎指點(diǎn)一二。
在了解完同義詞，以及 3 層結(jié)構(gòu)語(yǔ)法樹(shù)的邏輯后驗(yàn)求交算法后，可以再簡(jiǎn)單了解一下其余的查詢(xún)語(yǔ)法。
1 丟棄詞可設(shè)置 and 節(jié)點(diǎn)下的 term 節(jié)點(diǎn)為丟棄詞，這樣的話(huà)，它不會(huì)參與求交。為什么不在 query 處理環(huán)節(jié)就把它丟棄掉呢？這里存在一些差別，一個(gè) term 節(jié)點(diǎn)即便被設(shè)置丟棄詞，我們依然會(huì)為它設(shè)置文檔的命中信息，這對(duì)于相關(guān)性庫(kù)（文檔打分庫(kù)）來(lái)說(shuō)是有必要的。其實(shí)現(xiàn)方式為不參與邏輯后驗(yàn)以及求交基準(zhǔn)的計(jì)算，但是會(huì)參與對(duì)于求交基準(zhǔn)的倒排鏈跳躍查找。
2 動(dòng)態(tài)非必留與必留詞動(dòng)態(tài)非必留是一種動(dòng)態(tài)求交方式，例如一個(gè) and 節(jié)點(diǎn)下掛了 3 個(gè) term 節(jié)點(diǎn) A,B,C（均不是丟棄詞），動(dòng)態(tài)非必留設(shè)置為 2 個(gè) term 命中即可召回，那么一個(gè)文檔只要 A,B 或者 A,C,或者 B,C 命中即可。
必留詞是指在進(jìn)行動(dòng)態(tài)非必留求交時(shí)，該詞必須是求交元素，一般我們會(huì)設(shè)置在一些核心詞上面。例如 A 設(shè)置為了必留詞的話(huà)，那么一個(gè)文檔只要 A,B 或者 A,C 命中即可召回。動(dòng)態(tài)非必留適用于一些召回不足的場(chǎng)景。其實(shí)現(xiàn)方式為對(duì) and 節(jié)點(diǎn)下的 term 進(jìn)行快速選擇排序，在選取求交基準(zhǔn)時(shí)，不再對(duì)所有 term 節(jié)點(diǎn)取 max，而是取倒數(shù)第[必留個(gè)數(shù)]大的 term 的 pageid 彈出去。
3 位置約束可對(duì)一個(gè) and 節(jié)點(diǎn)下的 term 設(shè)置位置約束。例如一個(gè) and 節(jié)點(diǎn)下掛了 3 個(gè) term 節(jié)點(diǎn) A,B,C(均不是丟棄詞)，我們可以設(shè)置 B 存在 Pos=OneOfPos（A）+1，設(shè)置 C 存在 Pos=OneOfPos(B) + 2。在我們的引擎里，如果是相鄰 term 也設(shè)置了位置約束，那么它們會(huì)作為一個(gè)整體來(lái)進(jìn)行位置約束判斷，有點(diǎn)類(lèi)似于多槽位的模板匹配。其實(shí)現(xiàn)方式為取出相關(guān) term 的 pos 列表做二分查找。
and-or語(yǔ)法，配合丟棄詞的求交方式，特別依賴(lài)于Query處理能力，丟棄詞設(shè)置的好與壞會(huì)決定求交結(jié)果準(zhǔn)確與否。例如對(duì)于Query：[深圳有哪些景點(diǎn)]，如果深圳或者景點(diǎn)被設(shè)置了丟棄詞，那么召回結(jié)果可能會(huì)完全偏移，這種屬于在召回側(cè)結(jié)果集就已經(jīng)偏移，在相關(guān)性上面進(jìn)行排序調(diào)整也十分吃力。 WeakAnd求交方式是我們目前處于計(jì)劃中，但還未實(shí)現(xiàn)的一個(gè)功能，主要原因在于其標(biāo)準(zhǔn)實(shí)現(xiàn)方式與新引擎當(dāng)前的任務(wù)模型有沖突，我們還未能找到方法將其良好的融合進(jìn)去。對(duì)于WeakAnd的實(shí)現(xiàn)方式網(wǎng)上的資料很多，這里不想贅述。我們對(duì)它的認(rèn)識(shí)在于這種求交方式可以緩解對(duì)于Query處理能力的依賴(lài)。查找算法設(shè)計(jì)
正如上面提過(guò)的一樣，求交損耗的本質(zhì)為各條倒排鏈的跳躍查找次數(shù)，跳躍查找次數(shù)越少的，性能也就越好。語(yǔ)法樹(shù)求交設(shè)計(jì)解決的問(wèn)題是盡可能減少跳躍查找次數(shù)，而查找算法設(shè)計(jì)解決的問(wèn)題是盡可能減少每次跳躍查找的消耗。
由于新引擎的倒排索引結(jié)構(gòu)細(xì)節(jié)較多，為了方便闡述這塊的內(nèi)容，這里看一下我們組內(nèi)上一代內(nèi)存檢索引擎的倒排索引結(jié)構(gòu),由于其相對(duì)簡(jiǎn)單，適合拿來(lái)介紹查找算法。
倒排結(jié)構(gòu)整體是先分塊(Block,BLK),每個(gè)塊內(nèi)再保存具體的 page 信息，page 信息主要分為兩部分，一部分自然是 pageid 列表，另一塊是 page info 結(jié)構(gòu)，保存的各個(gè)文檔的 term 級(jí)別的信息，這里就不對(duì)其進(jìn)行介紹了，直接忽略它即可。
關(guān)于分塊設(shè)計(jì)的背景 1?繼承自磁盤(pán)檢索系統(tǒng)，磁盤(pán)分塊讀取2 內(nèi)存分塊，有助于實(shí)時(shí)索引構(gòu)建。相當(dāng)于是說(shuō)對(duì)于實(shí)時(shí)索引數(shù)據(jù)是以塊為單位進(jìn)行加載的，不過(guò)我們的系統(tǒng)并不是這樣實(shí)現(xiàn)的，我們的實(shí)時(shí)索引數(shù)據(jù)依然是以庫(kù)為粒度進(jìn)行加載的，因此在我們的系統(tǒng)中索引數(shù)據(jù)都是分布在連續(xù)內(nèi)存中。以庫(kù)粒度進(jìn)行加載，其索引時(shí)效性如何保障？這個(gè)問(wèn)題暫且擱置，在后續(xù)的ZeroSearch系列文章中會(huì)有解答。上一代引擎在查找某個(gè) pageid 時(shí)（連續(xù)內(nèi)存中），采取的做法是先二分查找到對(duì)應(yīng)塊，然后再在塊內(nèi)進(jìn)行二分查找。
有問(wèn)題么？表面上看，似乎并沒(méi)有什么問(wèn)題。我們對(duì)它簡(jiǎn)單分析一下，假設(shè)某個(gè) term 的倒排鏈長(zhǎng)度為 L，塊長(zhǎng)為 T(即每個(gè) BLK 內(nèi)至多保存 T 個(gè)文檔信息)，則塊數(shù)為 N=L/T，則查找次數(shù)為：logN + logT = logN*T = logL 而不分塊直接對(duì)整條倒排鏈二分查找的查找次數(shù)顯然也是 logL。
因此上一代引擎的索引設(shè)計(jì)以及查找算法其實(shí)并沒(méi)有帶來(lái)查找效率的提升。從一個(gè)有序列表中，找到第一個(gè)大于等于 N 值的位置，二分查找就是最快速的查找方式了，似乎并沒(méi)有優(yōu)化空間了？如果從結(jié)果出發(fā)，站在宏觀的角度來(lái)思考優(yōu)化，那幾乎不可能能得出答案，我們需要以微觀的角度，深入到過(guò)程來(lái)尋找優(yōu)化空間。
對(duì)于倒排查找過(guò)程的思考
1 過(guò)程的連續(xù)性事實(shí)上倒排查找并不是只查找一個(gè) N 值，而是隨著求交過(guò)程，需要不斷的去查找新的 N 值，且 N 值之間滿(mǎn)足嚴(yán)格遞增關(guān)系。即整個(gè)過(guò)程是具備連續(xù)性的。
2 數(shù)據(jù)分布特征索引分片分庫(kù)時(shí)文檔已經(jīng)被打散過(guò)一次（稀疏），這對(duì)倒排鏈(聚集)中的 pageid 分布是否會(huì)有影響，它們的值分布稠密或者稀疏對(duì)于求交是否又有影響。即倒排鏈 pageid 是否可能具備數(shù)據(jù)分布特征。
3 長(zhǎng)鏈與短鏈長(zhǎng)鏈與短鏈對(duì)于求交的影響如何，是否應(yīng)該區(qū)別處理，長(zhǎng)鏈與短鏈該如何去定義。通過(guò)對(duì)求交過(guò)程進(jìn)行分析和思考，得出了這 3 個(gè)點(diǎn)。下面我們以一個(gè)特殊的實(shí)例來(lái)看一下求交過(guò)程。
假設(shè)存在這樣的一條短鏈 L1 和一條長(zhǎng)鏈 L2，它們的 pageid 范圍相近，且前后 pageid 的間距都是固定的(數(shù)據(jù)分布均勻)，其中短鏈的前后 pageid 固定為 d1，長(zhǎng)鏈的前后 pageid 固定為 d2：
現(xiàn)在分析一下存在的求交組合情況，主要從查找消耗和求交基準(zhǔn)兩點(diǎn)進(jìn)行分析。
1?短鏈與短鏈求交 查找消耗:由于本身鏈路短，因此二分查找時(shí)，總的查找范圍較小，查找消耗較低。 求交基準(zhǔn):求交基準(zhǔn)的數(shù)目上限為短鏈長(zhǎng)度L1。 特殊：由于短鏈的間距d1過(guò)大，單個(gè)Block內(nèi)的pageid跨度（范圍）會(huì)更大。下一個(gè)求交基準(zhǔn)落在本block內(nèi)的可能性較高。2?短鏈與長(zhǎng)鏈求交 查找消耗:由于短鏈的間距d1過(guò)大，因此長(zhǎng)鏈在查找過(guò)程中依然適用于二分查找，但是長(zhǎng)鏈查找范圍會(huì)偏大，查找消耗一般 求交基準(zhǔn):求交基準(zhǔn)的數(shù)目上限為短鏈長(zhǎng)度L13?長(zhǎng)鏈與長(zhǎng)鏈求交 查找消耗:長(zhǎng)鏈與長(zhǎng)鏈求交時(shí)，由于長(zhǎng)鏈的間距d2較小，下一個(gè)求交基準(zhǔn)N大概率出現(xiàn)在上一個(gè)基準(zhǔn)附近，因此長(zhǎng)鏈在二分查找時(shí)，查找范圍過(guò)大，資源消耗較高 求交基準(zhǔn):求交基準(zhǔn)數(shù)目上限由長(zhǎng)鏈長(zhǎng)度L2決定現(xiàn)在泛化到多條鏈之間的求交情況分析，即短鏈變?yōu)槎鄺l，或者長(zhǎng)鏈變?yōu)槎鄺l，或者兩者都變?yōu)槎鄺l。由于我們采用的是多哨兵位的求交算法，是從整體進(jìn)行求交，那么在多條倒排鏈（大于 2 條）求交時(shí)，只有以下 3 種情況。
1?全部都為短鏈 問(wèn)題回歸到短鏈與短鏈求交的討論2?同時(shí)存在短鏈與長(zhǎng)鏈 問(wèn)題回歸到短鏈與長(zhǎng)鏈求交的討論3?全部都為長(zhǎng)鏈 問(wèn)題回歸到長(zhǎng)鏈與長(zhǎng)鏈求交的討論現(xiàn)在考慮數(shù)據(jù)分布不均勻情況下的求交特點(diǎn)。數(shù)據(jù)分布不均勻時(shí)，將存在稠密區(qū)域與非稠密區(qū)域，稠密區(qū)域內(nèi) pageid 的值分布集中，間距較小，而非稠密區(qū)域 pageid 的值分布較為分散，間距較大。同樣存在以下 3 種組合情況
1?非稠密區(qū)域與非稠密區(qū)域的查找，與短鏈與短鏈的查找特點(diǎn)相似2?非稠密區(qū)域與稠密區(qū)域的查找，與短鏈與長(zhǎng)鏈的查找特點(diǎn)相似3?稠密區(qū)域與稠密區(qū)域的查找，與長(zhǎng)鏈與長(zhǎng)鏈的查找特點(diǎn)相似盡管問(wèn)題又得到了回歸，但是數(shù)據(jù)分布均勻與否依然有著顯著的差異，即數(shù)據(jù)分布均勻的情況下，它的求交特點(diǎn)是穩(wěn)定的，而數(shù)據(jù)分布不均勻時(shí)，求交特點(diǎn)是變化的，可能上一次查找屬于非稠密區(qū)域與非稠密區(qū)域的查找，下一次查找時(shí)就落入了稠密區(qū)域與稠密區(qū)域的查找了，甚至隨著求交過(guò)程，長(zhǎng)鏈與短鏈的相對(duì)關(guān)系也在變化。
關(guān)于如何去評(píng)判一條倒排鏈的數(shù)據(jù)分布情況，計(jì)劃采用的方式是通過(guò)計(jì)算間距的平均值和方差來(lái)進(jìn)行評(píng)判，因此實(shí)際上當(dāng)前我們對(duì)于這一點(diǎn)也還屬于還未開(kāi)工的探索階段，暫且無(wú)法得到數(shù)據(jù)分布特征的一些數(shù)據(jù)。
不管怎樣，問(wèn)題總算是得到了回歸，至少我們可以得到以下兩點(diǎn)結(jié)論和一個(gè)猜想：1 多條倒排鏈求交時(shí)，其耗時(shí)主要由短鏈的長(zhǎng)度決定,原因是求交基準(zhǔn)的數(shù)目上限由短鏈決定。
2 多條長(zhǎng)鏈求交時(shí)，長(zhǎng)鏈每次查找范圍過(guò)大，因此查找消耗較大。
3 猜想:不論是對(duì)于長(zhǎng)鏈還是短鏈，下一個(gè)求交基準(zhǔn)大概率落在近鄰 Block 內(nèi)
以這 3 點(diǎn)為基礎(chǔ)，可以給我們的查找算法帶來(lái)一些新的思路。下面介紹求交優(yōu)化的做法。
1 倒排鏈查找優(yōu)化根據(jù)猜想：下一個(gè)求交基準(zhǔn)大概率落在近鄰 Block 內(nèi)。我們將先使用步長(zhǎng)增長(zhǎng)查找的方式對(duì)近鄰 Block 進(jìn)行查找，未找到再二分查找剩余 Block，Block 內(nèi)依然使用二分查找。
步長(zhǎng)增長(zhǎng)查找：每次向后查找的 Block 數(shù)量為 2^(n-1)，確定目標(biāo)位置后，再在該 2^(n-1)個(gè) Block 內(nèi)進(jìn)行二分查找。
了解到這種查找方式其實(shí)有個(gè)專(zhuān)有名詞叫：Galloping Search，其實(shí)是很輕松就能想到的方式。
需要注意的是，在這里我們需要對(duì)長(zhǎng)鏈和短鏈區(qū)分處理，簡(jiǎn)單來(lái)說(shuō)就是短鏈查找的近鄰 Block 較少，長(zhǎng)鏈查找的近鄰 Block 較多。具體下文會(huì)分析。
2 bitmap對(duì)于超長(zhǎng)鏈，其倒排結(jié)構(gòu)使用 bitmap 進(jìn)行存儲(chǔ)，bitmap 具備快速求交、快速求并、快速查找等特性，然而 bitmap 在 bit 位稀疏時(shí)的順序迭代訪問(wèn)性能較差，而求交基準(zhǔn)在選取時(shí)是需要獲取每個(gè)節(jié)點(diǎn)當(dāng)前指向的 pageid 的，對(duì)于 bitmap 來(lái)說(shuō)，需要通過(guò)順序迭代訪問(wèn)來(lái)找到第一個(gè)非零 bit 位。因此超長(zhǎng)鏈的定義將主要由 bitmap 帶來(lái)的收益和迭代性能來(lái)決定，僅從空間使用率上來(lái)看，未壓縮的情況下其實(shí)一條倒排鏈只需要滿(mǎn)足長(zhǎng)度大于等于索引庫(kù)文檔總數(shù)/32（pageid 采用 4 字節(jié)存儲(chǔ)）即可，當(dāng)然這個(gè)標(biāo)準(zhǔn)在性能上肯定是不行的。
3 語(yǔ)法樹(shù)查詢(xún)優(yōu)化
3.1 短鏈優(yōu)先查找由于短鏈節(jié)點(diǎn)查找消耗更低，單次查找更快，因此短鏈節(jié)點(diǎn)優(yōu)先查找，用于快速更新求交基準(zhǔn)，減少后續(xù)倒排鏈的查找次數(shù)，同時(shí) pageid 值的間距更大的可能性較高，利于快速增長(zhǎng)求交基準(zhǔn) N。
需要注意的是，隨著求交過(guò)程的不斷執(zhí)行，長(zhǎng)鏈，短鏈的相對(duì)關(guān)系可能會(huì)發(fā)生變化，這里的短鏈優(yōu)先查找是在求交開(kāi)始之前就對(duì)查詢(xún)節(jié)點(diǎn)的查詢(xún)順序進(jìn)行調(diào)整，后續(xù)不會(huì)再進(jìn)行調(diào)整。
3.2 同義詞子樹(shù)置后查找與短鏈節(jié)點(diǎn)優(yōu)先查找對(duì)應(yīng)，由于同義詞子樹(shù)一次查找需要對(duì)多個(gè) Term 節(jié)點(diǎn)進(jìn)行倒排查找，因此在評(píng)估單次查找消耗時(shí)，需要以整顆子樹(shù)進(jìn)行考慮，其查找消耗是該子樹(shù)下所有 Term 節(jié)點(diǎn)之和。最終的效果會(huì)導(dǎo)致同義詞子樹(shù)被置后查找。同樣的，這里的調(diào)整是在求交開(kāi)始之前就完成，后續(xù)不會(huì)再進(jìn)行調(diào)整。
3.3 bitmap 合并bitmap 語(yǔ)法節(jié)點(diǎn)合并，對(duì)于有多個(gè) bitmap 子節(jié)點(diǎn)的父節(jié)點(diǎn)，可對(duì)其新增一個(gè)虛擬語(yǔ)法節(jié)點(diǎn)，對(duì) or 節(jié)點(diǎn)下的 bitmap 節(jié)點(diǎn)進(jìn)行求并，對(duì) and 節(jié)點(diǎn)下的 bitmap 節(jié)點(diǎn)進(jìn)行求交。
3.4 重復(fù)詞節(jié)點(diǎn)合并對(duì)于語(yǔ)法樹(shù)中的每個(gè) Term 節(jié)點(diǎn)，我們只會(huì)創(chuàng)建一個(gè)倒排訪問(wèn)對(duì)象，簡(jiǎn)稱(chēng)游標(biāo)(Cursor)。在邏輯后驗(yàn)算法里，所有倒排鏈都在往求交基準(zhǔn) N 查找，因此對(duì)于相同的 Term 節(jié)點(diǎn)，它們可以共享同一個(gè)游標(biāo)。
4 指令集優(yōu)化經(jīng)組內(nèi)同事 sen 指點(diǎn)，在求交過(guò)程中可以利用 SSE 指令集(需要硬件支持)中的 XMM(128bit)、YMM(256bit)等大長(zhǎng)度寄存器，使用單指令多數(shù)據(jù)流的方法一次比較多個(gè)整形元素，來(lái)達(dá)到求交加速的效果。這類(lèi)寄存器的使用跟步長(zhǎng)增長(zhǎng)查找的方式恰好十分匹配，這一點(diǎn)屬于我們后續(xù)打算嘗試的一個(gè)方向。
那么遺留下來(lái)的問(wèn)題就是如何定義短鏈，長(zhǎng)鏈，以及超長(zhǎng)鏈了。
短鏈長(zhǎng)鏈與超長(zhǎng)鏈
其中超長(zhǎng)鏈的定義相對(duì)簡(jiǎn)單一些，設(shè)定一個(gè)閾值 X，當(dāng)且僅當(dāng)：倒排鏈長(zhǎng)度 / max（倒排鏈的 pageid) >= X 則倒排鏈?zhǔn)褂?bitmap 進(jìn)行存儲(chǔ)。X 的考慮主要是 bitmap 收益與順序迭代訪問(wèn)損耗的一個(gè)折中，這一點(diǎn)需要通過(guò)業(yè)務(wù)數(shù)據(jù)來(lái)實(shí)際驗(yàn)證后才能明確。
那么短鏈和長(zhǎng)鏈又該如何定義。短鏈與長(zhǎng)鏈的區(qū)別對(duì)待體現(xiàn)在近鄰查找時(shí)的 Block 數(shù)量上，在這里我們需要先簡(jiǎn)單分析一下步長(zhǎng)增長(zhǎng)查找方式與二分查找在性能上的差異。
條件：假設(shè)倒排鏈總長(zhǎng)度為 n，塊長(zhǎng)為 T，塊數(shù)為 N。二分查找的時(shí)間復(fù)雜度為：
logN + logT = logn需要注意的是由于倒排查找過(guò)程中要找的是第一個(gè)大于等于求教基準(zhǔn) N 值的位置，因此每一次二分查找，其查找次數(shù)不多不少，都是 logn（n 為還未查找過(guò)的文檔數(shù)量）。如果以倒排鏈長(zhǎng)度為 X 軸，時(shí)間復(fù)雜度為 Y 軸，那么二分查找的時(shí)間復(fù)雜度就是一條直線。
當(dāng)使用步長(zhǎng)增長(zhǎng)查找方式時(shí)，假設(shè)第 X 次確定了目標(biāo)位置，那么其時(shí)間復(fù)雜度為
X + log2^(X-1) * T = 2X + logT - 1，其中1 <= X <= log(N+1)其最小值約等于 logT，最大值約等于 logN + logn，如果以倒排鏈長(zhǎng)度為 X 軸，時(shí)間復(fù)雜度為 Y 軸，那么很明顯，步長(zhǎng)增長(zhǎng)查找方式的時(shí)間復(fù)雜度為一條曲線。
從步長(zhǎng)增長(zhǎng)查找的復(fù)雜度公式里的最小值和最大值可以知道，越在前面找到下一個(gè)求交基準(zhǔn)的位置，那么步長(zhǎng)增長(zhǎng)查找?guī)?lái)的提升就越大，再往后，其性能就開(kāi)始落后于二分查找了?，F(xiàn)在可以開(kāi)始考慮短鏈與長(zhǎng)鏈了。假設(shè)存在閾值 K，Block 數(shù)目大于 K 的就是長(zhǎng)鏈，小于 K 的就是短鏈，我們希望的最理想的效果是使用步長(zhǎng)增長(zhǎng)查找時(shí)的平均復(fù)雜度小于等于使用二分查找的平均時(shí)間復(fù)雜度。
由于二分查找的時(shí)間復(fù)雜度固定為 logn，因此其平均復(fù)雜度也就是 logn 了。而步長(zhǎng)增長(zhǎng)查找的平均時(shí)間復(fù)雜度的計(jì)算要麻煩許多，假定求交基準(zhǔn)落在每一個(gè) Block 的概率是相等的話(huà)，那么其平均時(shí)間復(fù)雜度為：
乍一看好像挺復(fù)雜的，完全誤會(huì)了，本人數(shù)學(xué)底子非常渣。這里其實(shí)就是對(duì)于每一個(gè) X，都乘了一下[當(dāng)前 X 所覆蓋的 Block 數(shù)量 / 總 Block 數(shù)量]的比例值，得到的平均時(shí)間復(fù)雜度的公式。
總之，由于本人的數(shù)學(xué)底子非常渣的原因，我這里就直接給出我們這邊計(jì)劃嘗試的 K 值了，K=15。怎么得出來(lái)的呢？通過(guò)計(jì)算 k=3，7，15，31，63 等等情況下的兩者的平均時(shí)間復(fù)雜度，發(fā)現(xiàn) k 值越大，步長(zhǎng)增長(zhǎng)查找的平均時(shí)間復(fù)雜度就越高(但其實(shí)算法實(shí)現(xiàn)的時(shí)候會(huì)發(fā)現(xiàn)，當(dāng)我們限定了只查找多少個(gè) Block 時(shí)，步長(zhǎng)增長(zhǎng)查找方式的邏輯會(huì)輕很多，盡管查找次數(shù)上并不占優(yōu))。最后因?yàn)槿缦?2 點(diǎn)原因選擇了 15:
1 越靠近的Block，命中下一個(gè)求交基準(zhǔn)的概率就越高(僅僅是猜想，還未有實(shí)際業(yè)務(wù)驗(yàn)證)，雖然k=15時(shí)平均復(fù)雜度已經(jīng)比二分高了，但如果越靠前的Block命中概率越高的話(huà)，靠前的Block區(qū)域加權(quán)因子變大，靠后的Block區(qū)域加權(quán)因子變小，那么其平均復(fù)雜度可能并不會(huì)比二分高。2 XMM寄存器一次可比較4個(gè)32bit的整數(shù)，與步長(zhǎng)增長(zhǎng)查找15個(gè)Block剛好對(duì)應(yīng)。如果XMM的使用確實(shí)帶來(lái)了優(yōu)化，那么我們后續(xù)也會(huì)對(duì)YMM進(jìn)行測(cè)試。這一點(diǎn)才是主要考慮的原因，為后續(xù)指令集優(yōu)化埋下伏筆。即在我們的引擎里，Block 數(shù)量大于等于 15 的則為長(zhǎng)鏈，小于 15 的則為短鏈。對(duì)于長(zhǎng)鏈，在近鄰搜索時(shí)最多查找 15 個(gè) Blcok（含當(dāng)前 Block），對(duì)于短鏈，我們只與當(dāng)前 Block 的最大值進(jìn)行比較一次。
需要再次說(shuō)明的是以上的討論都是建立在猜想：越靠近的 Block，命中下一個(gè)求交基準(zhǔn)的概率就越高。原因在于文檔在索引分片分庫(kù)時(shí)已經(jīng)被打散(稀疏)過(guò)一次，同時(shí)一個(gè) Block 內(nèi)保存的是多個(gè) pageid，被稀疏過(guò)后的文檔又緊密存儲(chǔ)(聚集)在一起。
如果猜想不成立呢？
計(jì)劃用質(zhì)量標(biāo)準(zhǔn)系統(tǒng)統(tǒng)計(jì)一下長(zhǎng)鏈在求交過(guò)程中命中下一個(gè)求交基準(zhǔn)的 Block 與上一個(gè)位置所處的 Block 的距離。例如如果有 90%以上是落在 X 個(gè) Block 內(nèi)的話(huà)，那么依然還是有價(jià)值先對(duì)這 X 個(gè) Block 進(jìn)行查找的。
另外當(dāng)我們確定要對(duì) X 個(gè) Block 進(jìn)行查找時(shí)，是有多種查找方式可以使用的，例如從前往后查，或者從后往前查，恒定步長(zhǎng)的查找方式，步長(zhǎng)增長(zhǎng)的查找方式等等。具體如何使用還是需要視數(shù)據(jù)分布特征而定。
關(guān)于近鄰查找的篇幅顯得有點(diǎn)啰嗦了，最后再簡(jiǎn)單總結(jié)一下：由于文檔在索引分片分庫(kù)的過(guò)程中被稀疏和聚集過(guò)一次，求交過(guò)程的連續(xù)性，以及索引數(shù)據(jù)相對(duì)穩(wěn)定的特點(diǎn)，我們嘗試去尋找一些特征來(lái)幫助我們加速整個(gè)倒排查找過(guò)程。
如果把兩種查找方式的時(shí)間復(fù)雜度相減，即2X?+?logT?-?1?-?logn，由于T和n都是常數(shù)，因此它們的差值為 f(x)?=?2x?+?logT?-?1?-?logn 當(dāng)f(x)大于0時(shí)，表示對(duì)近鄰Block進(jìn)行搜索時(shí)，步長(zhǎng)增長(zhǎng)方式的查找消耗更高 當(dāng)f(x)小于0時(shí)，表示對(duì)近鄰Block進(jìn)行搜索時(shí)，步長(zhǎng)增長(zhǎng)方式的查找消耗更低 很明顯，在二元坐標(biāo)軸里，f(x)是一根斜向上的直線，當(dāng)f(x)?=?0時(shí) x?=?(1?+?logn?-?logT)?/?2 x?=?(1?+?log(n/T))?/?2 x?=?(1?+?logN)?/?2 即只有當(dāng)x <?(1 + logN)?/ 2 時(shí)，步長(zhǎng)增長(zhǎng)查找方式性能才會(huì)比二分查找性能會(huì)好。需要注意的是這里的f(x)中x的定義，其定義為步長(zhǎng)增長(zhǎng)式查找時(shí)確認(rèn)到了目標(biāo)位置時(shí)的查找次數(shù)。引擎組件化
在文章的開(kāi)頭提到過(guò)，我們以組件化的思想來(lái)進(jìn)行設(shè)計(jì)，在線檢索能力被封裝成了一個(gè)庫(kù)，相比于攜帶 RPC 框架的引擎，檢索庫(kù)的形式可較好的融入已有的開(kāi)發(fā)體系和運(yùn)維體系。既然是以庫(kù)的形式存在，就需要有合適的接口暴露出來(lái)，讓使用者能嵌入業(yè)務(wù)邏輯和業(yè)務(wù)數(shù)據(jù)。對(duì)于組件化設(shè)計(jì)，核心的設(shè)計(jì)點(diǎn)如下
1 在線檢索過(guò)程中檢索邏輯與數(shù)據(jù)需要進(jìn)行分離，一個(gè)請(qǐng)求相關(guān)的所有數(shù)據(jù)都是通過(guò)檢索 Session 來(lái)進(jìn)行管理
2 業(yè)務(wù)數(shù)據(jù)的嵌入通過(guò)檢索入口傳入，之后交由檢索 Session 管理,在這里可以簡(jiǎn)單看下我們提供的唯一檢索入口:
int32_t?Retrieve(const?RetrieveOptions*?retrieve_options,void*?business_session)@arg1?retrieve_options?:?檢索協(xié)議(pb格式) @arg2?business_session?:?業(yè)務(wù)session數(shù)據(jù)3 對(duì)整個(gè)檢索流程中的各個(gè)環(huán)節(jié)暴露出接口封裝成類(lèi)進(jìn)行管理，業(yè)務(wù)邏輯的嵌入通過(guò)反射的形式來(lái)實(shí)現(xiàn)注入
4 相關(guān)性接口同樣封裝成類(lèi)，業(yè)務(wù)通過(guò)反射的形式來(lái)實(shí)現(xiàn)注入
整體如下圖所示：
在進(jìn)行組件化設(shè)計(jì)之后，檢索的細(xì)節(jié)都被封裝在庫(kù)里。這里對(duì) SearcherStage 設(shè)計(jì)和相關(guān)性接口設(shè)計(jì)再簡(jiǎn)單介紹一下。
Searcher 是在線檢索組件的名稱(chēng)，Stage 是我以我拙劣的英文水平選的一個(gè)詞，意為階段。在大環(huán)節(jié)上面，檢索流程分為預(yù)處理，核心處理，回包 3 個(gè)環(huán)節(jié)，我們?cè)诿總€(gè)大環(huán)節(jié)的開(kāi)始和結(jié)束階段都暴露了接口，并把所有接口放到了 SearcherStage 類(lèi)中進(jìn)行管理。對(duì)于任何想使用 Searcher 來(lái)作為部門(mén)內(nèi)通用搜索引擎的用戶(hù)來(lái)說(shuō)，它必須通過(guò)繼承并實(shí)現(xiàn) SearcherStage 類(lèi)的相關(guān)接口來(lái)實(shí)現(xiàn)自己的通用搜索引擎，一般來(lái)說(shuō)，至少需要通過(guò) SearcherStage 類(lèi)完成以下 2 件事情。
1?在AfterHandleResponse中將索引數(shù)據(jù)轉(zhuǎn)化為業(yè)務(wù)數(shù)據(jù) 2 在RetrieveKPIReport中對(duì)本次請(qǐng)求的檢索情況進(jìn)行上報(bào)，如檢索狀態(tài)，各個(gè)階段的文檔數(shù)量，耗時(shí)等等。需要再次說(shuō)明的是，每一個(gè) SearcherStage 對(duì)象都是一個(gè)獨(dú)立的通用搜索引擎，例如在搜一搜這邊，也只是存在一個(gè) S1SSearcherStage 類(lèi)，并以它為基礎(chǔ)封裝為了搜一搜的檢索庫(kù)，其余的所有垂搜業(yè)務(wù)都是鏈接該檢索庫(kù)，而非 Searcher 組件。
下面再簡(jiǎn)單介紹一下相關(guān)性接口的設(shè)計(jì)。相關(guān)性接口設(shè)計(jì)的總體原則：控制復(fù)雜度。其體現(xiàn)為以下兩點(diǎn)
人性化的相關(guān)性輸入信息
合理的邏輯拆分
關(guān)于人性化的相關(guān)性輸入信息，本文暫且不提，這里簡(jiǎn)單介紹下邏輯拆分的背景。相關(guān)性接口的執(zhí)行場(chǎng)景分為全局初始化、請(qǐng)求級(jí)別初始化及各打分環(huán)節(jié)初始化、文檔打分 3 個(gè)，在我們的上一代內(nèi)存檢索引擎中，所有的相關(guān)性接口都集中在了一個(gè)類(lèi)中，該設(shè)計(jì)客觀上導(dǎo)致了當(dāng)前所有業(yè)務(wù)的打分主邏輯都集中了一個(gè)類(lèi)的實(shí)現(xiàn)里，臃腫，多個(gè)場(chǎng)景/環(huán)節(jié)的變量和邏輯交織在一起，容易出錯(cuò)，另一方面所有的代碼都集中了一個(gè).h 和.cc 文件中，可讀性差，難以管理和協(xié)作開(kāi)發(fā)。也因此，在新引擎中，我們對(duì)各個(gè)過(guò)程進(jìn)行了拆分，抽象為了獨(dú)立的類(lèi)，類(lèi)之間以組合的形式進(jìn)行訪問(wèn)。拆分之后還有一個(gè)好處在于，由于每個(gè)文檔都有獨(dú)立的打分對(duì)象，文檔的打分從無(wú)狀態(tài)變?yōu)榱擞袪顟B(tài)。
末尾
大概的內(nèi)容就是這樣了，在引擎的整個(gè)設(shè)計(jì)過(guò)程中，很多關(guān)鍵的設(shè)計(jì)點(diǎn)都是跟組內(nèi)同事 sen 進(jìn)行探討后得到，sen 給了我很多指導(dǎo)和把控。我們整體的設(shè)計(jì)原則其實(shí)非常簡(jiǎn)單：
1 充分考慮易用性以服務(wù)業(yè)務(wù)為第一優(yōu)先級(jí)，易用性將決定業(yè)務(wù)的服務(wù)舒適度
2 還是要像一個(gè)內(nèi)存搜索引擎設(shè)計(jì)方案上還是不能太糟糕，不能存在明顯的設(shè)計(jì)問(wèn)題
本文取名為關(guān)于內(nèi)存檢索引擎設(shè)計(jì)的探索，實(shí)則也是我之前想寫(xiě)的檢索初階系列中的第二篇:內(nèi)存檢索引擎設(shè)計(jì)。之前檢索初階(一)和(三)都早早就發(fā)出來(lái)了，但其實(shí)那會(huì)對(duì)檢索引擎的理解還比較淺，這篇雖然是(二)，不過(guò)是作為收官之作來(lái)寫(xiě)的。
組內(nèi)這次開(kāi)發(fā)的新引擎（ZeroSearch）后續(xù)也會(huì)準(zhǔn)備對(duì)公司內(nèi)部開(kāi)源，時(shí)間點(diǎn)應(yīng)該要到明年了，其實(shí)目前已經(jīng)完成了一個(gè)比較粗糙的版本，目前正處于推動(dòng)業(yè)務(wù)升級(jí)的階段，但是還有大量的 TODO 和方向還沒(méi)去嘗試。不過(guò)在那之前，組內(nèi)后續(xù)還會(huì)有同學(xué)分別介紹 ZeroSearch 的分布式索引系統(tǒng)設(shè)計(jì)，索引庫(kù)構(gòu)建流程設(shè)計(jì)，索引結(jié)構(gòu)設(shè)計(jì)等等一系列的文章 ，讓我們一起為內(nèi)存檢索引擎設(shè)計(jì)的資料空缺出把力吧。
最后打一個(gè)小廣告，微信搜索誠(chéng)招 C++后臺(tái)開(kāi)發(fā)，如有搜索開(kāi)發(fā)經(jīng)驗(yàn)或大廠工作經(jīng)驗(yàn)者更佳，誠(chéng)邀有志之士，共襄大業(yè)。有興趣的同學(xué)可與本人郵件聯(lián)系：scut_huajian@qq.com
歡迎關(guān)注我們的視頻號(hào)：騰訊程序員
最新視頻：如果程序員媽是產(chǎn)品經(jīng)理
騰訊技術(shù)官方交流微信群已經(jīng)開(kāi)放
進(jìn)群添加微信：journeylife1900
（備注：騰訊技術(shù)）
總結(jié)
以上是生活随笔為你收集整理的新一代搜索引擎项目 ZeroSearch 设计探索的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 从无盘启动看 Linux 启动原理
- 下一篇： 我在 MySQL 的那些年