58同城作為中國(guó)最大的分類信息網(wǎng)站傻挂，提供了房產(chǎn)乘碑、招聘、黃頁(yè)和二手交易等多方面的生活服務(wù)信息金拒，信息數(shù)據(jù)量和訪問量逐年增長(zhǎng)兽肤，列表頁(yè)排序需求也時(shí)常變化。在這樣的背景下殖蚕，58搜索技術(shù)部使用C++語(yǔ)言自主研發(fā)了ESearch 搜索內(nèi)核轿衔，取代之前使用的 Solr，大幅提高了性能和可定制性睦疫。
經(jīng)過多年的實(shí)踐和優(yōu)化，ESearch 已發(fā)展成為一個(gè)功能完善鞭呕、性能優(yōu)異蛤育、運(yùn)行穩(wěn)定的搜索內(nèi)核，如今作為一個(gè)核心組件，承擔(dān)了58集團(tuán)（包括58同城瓦糕、趕集底洗、安居客等）所有搜索業(yè)務(wù)，承載每天幾十億的查詢流量咕娄。ESearch的主要特性包括：
秒級(jí)實(shí)時(shí)索引：從文檔發(fā)布到能檢索出該文檔亥揖，可以做到平均一秒的時(shí)間延遲。
大數(shù)據(jù)量圣勒、高并發(fā)费变、低延遲：基于本地緩存、自定義內(nèi)存池圣贸、自動(dòng)Query改寫等多種性能優(yōu)化措施挚歧，可達(dá)到單機(jī)千萬級(jí)文檔、8000 QPS吁峻、毫秒級(jí)平均延遲滑负。
功能豐富：支持復(fù)合條件查詢、空間查詢用含、Facet查詢矮慕、分組查詢、結(jié)果去重等功能啄骇。
業(yè)務(wù)可定制：支持SKU查詢凡傅、一一抽取、在線用戶實(shí)時(shí)過濾等個(gè)性化功能肠缔。
可擴(kuò)展夏跷、易復(fù)用的排序框架：支持簡(jiǎn)單的線性加權(quán)、自定義的打分表達(dá)式明未、基于機(jī)器學(xué)習(xí)的邏輯回歸槽华、多決策樹等模型，以及多模型融合等多種排序方式趟妥。
本文將介紹 ESearch 的整體架構(gòu)猫态，并重點(diǎn)說明其中實(shí)時(shí)索引的設(shè)計(jì)和實(shí)現(xiàn)細(xì)節(jié)。
一披摄、整體架構(gòu)
上圖是 58 搜索系統(tǒng)的整體架構(gòu)亲雪，分為應(yīng)用層和內(nèi)核層兩大部分，應(yīng)用層包括 Proxy 和 Builder 兩個(gè)模塊疚膊，負(fù)責(zé)與業(yè)務(wù)相關(guān)的邏輯义辕，內(nèi)核層就是本文重點(diǎn)介紹的 ESearch，包括 Merger 和 Searcher 兩個(gè)模塊寓盗，負(fù)責(zé)通用的檢索功能灌砖。各個(gè)模塊的具體功能如下：
Proxy：查詢代理璧函，接收前端查詢請(qǐng)求，進(jìn)行意圖識(shí)別和查詢改寫等工作基显，然后發(fā)送請(qǐng)求到 Merger蘸吓，獲取檢索結(jié)果。
Merger：基于一致性哈希算法將請(qǐng)求分發(fā)到多個(gè) Searcher撩幽，然后合并結(jié)果库继，并進(jìn)行一些排序調(diào)整。
Searcher：包含索引數(shù)據(jù)和排序模型窜醉，負(fù)責(zé)實(shí)時(shí)建索引并執(zhí)行召回宪萄、打分、排序等檢索流程酱虎。
Builder：接收外部請(qǐng)求進(jìn)行進(jìn)行文檔構(gòu)建雨膨，并將文檔發(fā)給 Searcher。
二读串、實(shí)時(shí)索引
實(shí)時(shí)索引的設(shè)計(jì)主要需要考慮兩個(gè)需求：
文檔更新能在秒級(jí)時(shí)間內(nèi)生效：用戶信息發(fā)布或者修改更新之后聊记，需要能盡快被檢索到。
文檔更新時(shí)不影響查詢效率：在大數(shù)據(jù)量大更新量的情況下恢暖，不能影響查詢延時(shí)排监。
從查詢效率出發(fā)，業(yè)界通常采用讀寫分離的設(shè)計(jì)杰捂，即索引不提供更新功能舆床，避免更新操作阻塞查詢線程。接收到新文檔之后嫁佳，先與原索引數(shù)據(jù)合并為新索引挨队，然后替換掉舊索引，從而使新文檔生效蒿往。但在文檔更新量比較大盛垦，并且索引量隨時(shí)間逐漸增大的情況下，合并時(shí)間會(huì)變得很長(zhǎng)瓤漏，導(dǎo)致新文檔長(zhǎng)時(shí)間無法生效腾夯。此外還有一些搜索引擎采用了無鎖數(shù)據(jù)結(jié)構(gòu)，支持索引的高并發(fā)讀寫蔬充，但實(shí)現(xiàn)相對(duì)復(fù)雜蝶俱。
ESearch 也采用了讀寫分離設(shè)計(jì)，為了克服合并時(shí)間過長(zhǎng)的問題饥漫，對(duì)合并機(jī)制做了改進(jìn)設(shè)計(jì)：對(duì)每個(gè)檢索節(jié)點(diǎn)的索引數(shù)據(jù)按生命周期分為多段榨呆，每段是一份完整的小索引，包含獨(dú)立的倒排和正排索引等數(shù)據(jù)趾浅。新增的文檔數(shù)據(jù)只和最小的索引段合并愕提，確保了索引的更新速度馒稍。
在實(shí)際的應(yīng)用層面皿哨，根據(jù)自身數(shù)據(jù)量和業(yè)務(wù)特點(diǎn)浅侨，我們采取了以下方案：每個(gè)節(jié)點(diǎn)上索引按生命周期分為 3秒、15分鐘证膨、6小時(shí)如输、1天、1個(gè)月央勒、1個(gè)月以前等6級(jí)不见。
實(shí)時(shí)索引每3秒接收一批新文檔數(shù)據(jù)，然后建成一個(gè)生命周期為3秒的小段崔步，此時(shí)這批文檔立即生效稳吮，能被查詢線程召回。3秒后井濒，該段到達(dá)生命周期終點(diǎn)灶似，由一個(gè)專門負(fù)責(zé)索引段合并的線程將其與15分鐘生命周期的段合并。由于15分鐘索引段最多只包含了15分鐘內(nèi)的新增文檔瑞你，數(shù)據(jù)量較少酪惭，所以合并速度非常快者甲，可以達(dá)到毫秒級(jí)春感。同理，15分鐘虏缸、6小時(shí)等其他周期的段鲫懒，到達(dá)各自的生命周期終點(diǎn)后，都會(huì)向上一級(jí)索引段合并刽辙。
生命周期在1天以上的段窥岩，數(shù)據(jù)量較多，合并時(shí)間較長(zhǎng)扫倡，但其合并頻率較低谦秧，每天最多一次，可以指定其在每天凌晨進(jìn)行撵溃，這是一天中訪問量和數(shù)據(jù)更新最少的時(shí)間段疚鲤，因此對(duì)系統(tǒng)性能影響不大。若1個(gè)月周期的數(shù)據(jù)量太大缘挑，可以在線下定期將其與1個(gè)月以前的索引合并集歇，合并好后推送到檢索節(jié)點(diǎn)，避免影響系統(tǒng)性能语淘。
在這種分段設(shè)計(jì)下诲宇，查詢處理器可以為每個(gè)查詢分配多個(gè)線程际歼，每個(gè)線程檢索一個(gè)段，最終將結(jié)果合并姑蓝。因此分段設(shè)計(jì)也便于利用并發(fā)能力降低查詢延時(shí)鹅心。
如果文檔的更新和查詢的召回條件或排序均遵循時(shí)間序（例如日志索引），那么可以只檢索與查詢中的時(shí)間段相關(guān)的索引段纺荧，提升檢索效率旭愧，因此這種設(shè)計(jì)很適合以時(shí)間序?yàn)橹饕判蛐枨蟮乃阉飨到y(tǒng)。
三宙暇、索引結(jié)構(gòu)
上一節(jié)介紹了實(shí)時(shí)索引整體的設(shè)計(jì)输枯，本節(jié)介紹索引段內(nèi)的具體結(jié)構(gòu)。
在 ESearch 中占贫，每個(gè)索引段包含四種索引結(jié)構(gòu)：主鍵索引桃熄、刪除表、倒排索引和正排索引型奥。
3.1瞳收、主鍵索引
為了便于高效計(jì)算，索引內(nèi)部為整個(gè)文檔集分配了從0開始遞增的doc id桩引，倒排和正排索引均基于doc id來組織缎讼，而不使用文檔的原始主鍵。為了能從文檔的原始主鍵查找到對(duì)應(yīng)的索引數(shù)據(jù)坑匠，必須先將主鍵映射為doc id血崭，主鍵索引就是為此而存在的，它本質(zhì)上是一個(gè)從主鍵映射到doc id的哈希表厘灼。
3.2夹纫、刪除表
倒排索引是為查詢優(yōu)化的，不利于原地更新和刪除设凹，因此當(dāng)文檔被刪除時(shí)舰讹，我們需要一個(gè)刪除表來標(biāo)記文檔的刪除狀態(tài)，它本質(zhì)上是一個(gè)bitmap闪朱。
3.3月匣、倒排索引
倒排索引用于根據(jù)term快速查找包含該term的所有文檔。由于采用了讀寫分離設(shè)計(jì)奋姿，ESearch的倒排索引數(shù)據(jù)結(jié)構(gòu)不需要支持更新锄开，每個(gè)term對(duì)應(yīng)的doc id集合以有序數(shù)組的形式存儲(chǔ)即可。對(duì)于文本域称诗，倒排數(shù)據(jù)還包含詞頻萍悴、詞權(quán)、位置等信息。
58的關(guān)鍵詞查詢通常需要在多個(gè)文本域中查詢癣诱，比如“title:租房 OR content:租房”计维，需要召回title或者content這兩個(gè)域中包含租房的文檔。為了優(yōu)化這類常見查詢的性能撕予，同時(shí)也讓文本相關(guān)性計(jì)算更方便鲫惶，ESearch支持倒排域打包功能（或稱聯(lián)合域），即自動(dòng)把同一個(gè)term在多個(gè)文本域中的文檔集合并到同一個(gè)倒排鏈（Posting List）中嗅蔬，此功能只需在schema中稍作配置即可啟用剑按。如此疾就，相當(dāng)于在索引中對(duì)每個(gè)term預(yù)計(jì)算了多個(gè)域的并集澜术。另外，由于不同文本域的權(quán)重不同猬腰，進(jìn)行文本相關(guān)性打分時(shí)需要識(shí)別出一個(gè)term命中了哪些文本域鸟废，因此聯(lián)合域倒排鏈中的每個(gè)doc id 還必須附帶一個(gè)微型 bitmap 來標(biāo)記其所命中的域。
下圖為把Title域和Content域合并為Fulltext域的例子：
3.4姑荷、正排索引
正排索引是從doc id到文檔屬性值的映射盒延。在58的搜索系統(tǒng)中，正排索引除了存儲(chǔ)必要的文檔屬性以外鼠冕，也存儲(chǔ)用于打分的文檔特征添寺。在檢索過程中，也有可能讀取某些正排域來進(jìn)行文檔過濾懈费。
ESearch 的正排索引采用列存儲(chǔ)設(shè)計(jì)计露，即不同正排域的數(shù)據(jù)分開存儲(chǔ)。
針對(duì)58文檔的特性憎乙，ESearch 提供了正排域的多種存儲(chǔ)形式票罐。58是一個(gè)分類信息網(wǎng)站，所有類目的信息都存在同一個(gè)數(shù)據(jù)庫(kù)中泞边。類目不同该押，信息的字段差異也很大，譬如房產(chǎn)信息包含樓層阵谚、戶型等字段蚕礼，二手交易信息包含品牌、型號(hào)等字段梢什。這些差異化的字段按統(tǒng)一格式合并存儲(chǔ)在同一個(gè)數(shù)據(jù)庫(kù)字段奠蹬，在建索引的時(shí)候，仍會(huì)分別建到各自的倒排绳矩、正排域中罩润。但同時(shí)各類目信息也有不少通用字段，例如標(biāo)題翼馆、城市ID割以、類目ID等金度。
這意味著有些域的值分布是稀疏的，例如在所有信息中严沥，包含“手機(jī)品牌”這個(gè)字段的信息的占比可能遠(yuǎn)低于50%猜极，而有些域的值分布是緊密的，例如幾乎100%的信息都包含“類目ID”這個(gè)字段消玄。
針對(duì)緊密型的正排域跟伏，我們使用數(shù)組作為存儲(chǔ)形式，而針對(duì)稀疏型正排域翩瓜，使用哈希表作為存儲(chǔ)形式受扳，這樣能夠避免浪費(fèi)空間，也都保證了O(1)的平均查找時(shí)間復(fù)雜度兔跌。
此外勘高，對(duì)于布爾型的正排域，我們直接采用Bitmap 作為存儲(chǔ)形式坟桅。
列存儲(chǔ)的一個(gè)缺陷是缺乏空間局部性华望，可能影響CPU緩存命中率。例如在給一個(gè)文檔打分時(shí)仅乓，通常會(huì)從正排索引讀取多個(gè)特征值進(jìn)行計(jì)算赖舟，因此需要進(jìn)行多次查找和多處內(nèi)存訪問。針對(duì)此問題夸楣，可以考慮使用聯(lián)合正排域，將經(jīng)常需要同時(shí)訪問的多個(gè)字段合并建到一個(gè)正排域中裕偿。
四、緩存與二次排序
為了降低檢索服務(wù)響應(yīng)時(shí)間劲腿，對(duì)檢索結(jié)果進(jìn)行緩存是必需的鸟妙，但緩存也會(huì)導(dǎo)致文檔字段和排序特征的更新無法立刻生效，影響實(shí)時(shí)性花椭。本節(jié)介紹 ESearch在使用了緩存的情況下如何保證召回結(jié)果和排序結(jié)果得到實(shí)時(shí)更新房午。
4.1、召回結(jié)果
在實(shí)時(shí)索引中袋倔，如前文所述，文檔更新時(shí)會(huì)被建入新的小索引段中批狐。如果舊的索引段也包含此文檔嚣艇，那么此文檔在舊段中會(huì)被標(biāo)記刪除华弓。
ESearch 為每一個(gè)段分配了獨(dú)立的緩存，每個(gè)段各自將檢索結(jié)果從緩存中取出后该抒，會(huì)用刪除表過濾掉已刪除的文檔凑保，從而確保只有更新后的文檔能被檢索出來涌攻。
4.2、排序結(jié)果
為了便于打分排序恳谎，我們會(huì)把一些文檔特征值存儲(chǔ)在索引中因痛。這些特征值不會(huì)作為召回條件，因此只建在正排索引中鸵膏。對(duì)這類文檔屬性的更新可以不走前文所述的生成新段-段合并的更新流程谭企，而是直接在正排索引中原地刷新，因此特征值刷新的性能遠(yuǎn)高于正常文檔更新债查，從而允許我們實(shí)時(shí)調(diào)整排序結(jié)果盹廷。
為了使特征值的改變能夠?qū)崟r(shí)影響排序結(jié)果，我們?cè)趶木彺嬷腥〕鰴z索結(jié)果后，對(duì)檢索結(jié)果會(huì)做第二次打分排序剥汤。由于緩存中的結(jié)果一般只包含Top幾百的文檔排惨，因此第二次排序耗時(shí)有限暮芭，不影響整體性能。
除了保證實(shí)時(shí)性以外畜晰，這種兩階段排序也便于我們?cè)?8主站大規(guī)模應(yīng)用復(fù)雜的機(jī)器學(xué)習(xí)排序模型瑞筐。
復(fù)雜的排序策略通常比較耗時(shí)聚假，因此業(yè)界在處理海量數(shù)據(jù)的排序時(shí)，通常用“粗排-精排”兩階段排序的方式膘格，在效果和性能之間做一個(gè)合理折中瘪贱，即先對(duì)海量數(shù)據(jù)進(jìn)行低代價(jià)的粗排，然后對(duì)粗排的TopN結(jié)果進(jìn)行代價(jià)較大的精排甜害，最終整個(gè)處理過程耗時(shí)不會(huì)太大球昨。
58分類信息的特點(diǎn)也很適合這種模式，很多類目（例如租房）的信息注重時(shí)效性闹获，時(shí)間序是主要排序因素河哑。在信息發(fā)布時(shí)間相近的前提下，需要根據(jù)信息質(zhì)量沙庐、轉(zhuǎn)化率等其他因素進(jìn)行更精細(xì)的排序。二次排序恰好可以用來實(shí)現(xiàn)這樣的流程：第一次排序?qū)θ课臋n按時(shí)間序求出 TopN 結(jié)果集保存在緩存中棉安，第二次排序使用復(fù)雜的機(jī)器學(xué)習(xí)模型來對(duì) TopN 結(jié)果打分重排铸抑。
五、總結(jié)
本文介紹了在 58 搜索內(nèi)核 ESearch 中蒲赂，如何根據(jù) 58 的數(shù)據(jù)和搜索特點(diǎn)來設(shè)計(jì)實(shí)時(shí)索引以及進(jìn)行索引存儲(chǔ)和查詢流程方面的優(yōu)化刁憋。隨著業(yè)務(wù)的不斷發(fā)展至耻，我們也將繼續(xù)在檢索性能、資源利用率走触、排序等方面持續(xù)優(yōu)化泥耀，也歡迎感興趣的同學(xué)和我們一起交流。
