作者｜ 楊逸
58 同城作為中國最大的分類信息網站，提供了房產、招聘、黃頁和二手交易等多方面的生活服務信息，信息數據量和訪問量逐年增長，列表頁排序需求也時常變化。在這樣的背景下，58 搜索技術部使用 C++ 語言自主研發了 ESearch 搜索內核，取代之前使用的 Solr，大幅提高了性能和可定製性。
經過多年的實踐和優化，ESearch 已發展成為一個功能完善、性能優異、運行穩定的搜索內核，如今作為一個核心組件，承擔了 58 集團（包括 58 同城、趕集、安居客等）所有搜索業務，承載每天幾十億的查詢流量。ESearch 的主要特性包括：
秒級實時索引：從文檔發佈到能檢索出該文檔，可以做到平均一秒的時間延遲。
大數據量、高併發、低延遲：基於本地緩存、自定義內存池、自動 Query 改寫等多種性能優化措施，可達到單機千萬級文檔、8000 QPS、毫秒級平均延遲。
功能豐富：支持複合條件查詢、空間查詢、Facet 查詢、分組查詢、結果去重等功能。
業務可定製：支持 SKU 查詢、一一抽取、在線用戶實時過濾等個性化功能。
可擴展、易複用的排序框架：支持簡單的線性加權、自定義的打分表達式、基於機器學習的邏輯迴歸、多決策樹等模型，以及多模型融合等多種排序方式。
本文將介紹 ESearch 的整體架構，並重點說明其中實時索引的設計和實現細節。
一、整體架構
上圖是 58 搜索系統的整體架構，分為應用層和內核層兩大部分，應用層包括 Proxy 和 Builder 兩個模塊，負責與業務相關的邏輯，內核層就是本文重點介紹的 ESearch，包括 Merger 和 Searcher 兩個模塊，負責通用的檢索功能。各個模塊的具體功能如下：
Proxy：查詢代理，接收前端查詢請求，進行意圖識別和查詢改寫等工作，然後發送請求到 Merger，獲取檢索結果。
Merger：基於一致性哈希算法將請求分發到多個 Searcher，然後合併結果，並進行一些排序調整。
Searcher：包含索引數據和排序模型，負責實時建索引並執行召回、打分、排序等檢索流程。
Builder：接收外部請求進行進行文檔構建，並將文檔發給 Searcher。
二、實時索引
實時索引的設計主要需要考慮兩個需求：
文檔更新能在秒級時間內生效：用戶信息發佈或者修改更新之後，需要能儘快被檢索到。
文檔更新時不影響查詢效率：在大數據量大更新量的情況下，不能影響查詢延時。
從查詢效率出發，業界通常採用讀寫分離的設計，即索引不提供更新功能，避免更新操作阻塞查詢線程。接收到新文檔之後，先與原索引數據合併為新索引，然後替換掉舊索引，從而使新文檔生效。但在文檔更新量比較大，並且索引量隨時間逐漸增大的情況下，合併時間會變得很長，導致新文檔長時間無法生效。此外還有一些搜索引擎採用了無鎖數據結構，支持索引的高併發讀寫，但實現相對複雜。
ESearch 也採用了讀寫分離設計，為了克服合併時間過長的問題，對合並機制做了改進設計：對每個檢索節點的索引數據按生命週期分為多段，每段是一份完整的小索引，包含獨立的倒排和正排索引等數據。新增的文檔數據只和最小的索引段合併，確保了索引的更新速度。
在實際的應用層面，根據自身數據量和業務特點，我們採取了以下方案：每個節點上索引按生命週期分為 3 秒、15 分鐘、6 小時、1 天、1 個月、1 個月以前等 6 級。
實時索引每 3 秒接收一批新文檔數據，然後建成一個生命週期為 3 秒的小段，此時這批文檔立即生效，能被查詢線程召回。3 秒後，該段到達生命週期終點，由一個專門負責索引段合併的線程將其與 15 分鐘生命週期的段合併。由於 15 分鐘索引段最多隻包含了 15 分鐘內的新增文檔，數據量較少，所以合併速度非常快，可以達到毫秒級。同理，15 分鐘、6 小時等其他週期的段，到達各自的生命週期終點後，都會向上一級索引段合併。
生命週期在 1 天以上的段，數據量較多，合併時間較長，但其合併頻率較低，每天最多一次，可以指定其在每天凌晨進行，這是一天中訪問量和數據更新最少的時間段，因此對系統性能影響不大。若 1 個月週期的數據量太大，可以在線下定期將其與 1 個月以前的索引合併，合併好後推送到檢索節點，避免影響系統性能。
在這種分段設計下，查詢處理器可以為每個查詢分配多個線程，每個線程檢索一個段，最終將結果合併。因此分段設計也便於利用併發能力降低查詢延時。
如果文檔的更新和查詢的召回條件或排序均遵循時間序（例如日誌索引），那麼可以只檢索與查詢中的時間段相關的索引段，提升檢索效率，因此這種設計很適合以時間序為主要排序需求的搜索系統。
三、索引結構
上一節介紹了實時索引整體的設計，本節介紹索引段內的具體結構。
在 ESearch 中，每個索引段包含四種索引結構：主鍵索引、刪除表、倒排索引和正排索引。
3.1、主鍵索引
為了便於高效計算，索引內部為整個文檔集分配了從 0 開始遞增的 doc id，倒排和正排索引均基於 doc id 來組織，而不使用文檔的原始主鍵。為了能從文檔的原始主鍵查找到對應的索引數據，必須先將主鍵映射為 doc id，主鍵索引就是為此而存在的，它本質上是一個從主鍵映射到 doc id 的哈希表。
3.2、刪除表
倒排索引是為查詢優化的，不利於原地更新和刪除，因此當文檔被刪除時，我們需要一個刪除表來標記文檔的刪除狀態，它本質上是一個 bitmap。
3.3、倒排索引
倒排索引用於根據 term 快速查找包含該 term 的所有文檔。由於採用了讀寫分離設計，ESearch 的倒排索引數據結構不需要支持更新，每個 term 對應的 doc id 集合以有序數組的形式存儲即可。對於文本域，倒排數據還包含詞頻、詞權、位置等信息。
58 的關鍵詞查詢通常需要在多個文本域中查詢，比如“title: 租房 OR content: 租房”，需要召回 title 或者 content 這兩個域中包含租房的文檔。為了優化這類常見查詢的性能，同時也讓文本相關性計算更方便，ESearch 支持倒排域打包功能（或稱聯合域），即自動把同一個 term 在多個文本域中的文檔集合併到同一個倒排鏈（Posting List）中，此功能只需在 schema 中稍作配置即可啟用。如此，相當於在索引中對每個 term 預計算了多個域的並集。另外，由於不同文本域的權重不同，進行文本相關性打分時需要識別出一個 term 命中了哪些文本域，因此聯合域倒排鏈中的每個 doc id 還必須附帶一個微型 bitmap 來標記其所命中的域。
下圖為把 Title 域和 Content 域合併為 Fulltext 域的例子：
3.4、正排索引
正排索引是從 doc id 到文檔屬性值的映射。在 58 的搜索系統中，正排索引除了存儲必要的文檔屬性以外，也存儲用於打分的文檔特徵。在檢索過程中，也有可能讀取某些正排域來進行文檔過濾。
ESearch 的正排索引採用列存儲設計，即不同正排域的數據分開存儲。
針對 58 文檔的特性，ESearch 提供了正排域的多種存儲形式。58 是一個分類信息網站，所有類目的信息都存在同一個數據庫中。類目不同，信息的字段差異也很大，譬如房產信息包含樓層、戶型等字段，二手交易信息包含品牌、型號等字段。這些差異化的字段按統一格式合併存儲在同一個數據庫字段，在建索引的時候，仍會分別建到各自的倒排、正排域中。但同時各類目信息也有不少通用字段，例如標題、城市 ID、類目 ID 等。
這意味著有些域的值分佈是稀疏的，例如在所有信息中，包含“手機品牌”這個字段的信息的佔比可能遠低於 50%，而有些域的值分佈是緊密的，例如幾乎 100% 的信息都包含“類目 ID”這個字段。
針對緊密型的正排域，我們使用數組作為存儲形式，而針對稀疏型正排域，使用哈希表作為存儲形式，這樣能夠避免浪費空間，也都保證了 O(1) 的平均查找時間複雜度。
此外，對於布爾型的正排域，我們直接採用 Bitmap 作為存儲形式。
列存儲的一個缺陷是缺乏空間局部性，可能影響 CPU 緩存命中率。例如在給一個文檔打分時，通常會從正排索引讀取多個特徵值進行計算，因此需要進行多次查找和多處內存訪問。針對此問題，可以考慮使用聯合正排域，將經常需要同時訪問的多個字段合併建到一個正排域中。
四、緩存與二次排序
為了降低檢索服務響應時間，對檢索結果進行緩存是必需的，但緩存也會導致文檔字段和排序特徵的更新無法立刻生效，影響實時性。本節介紹 ESearch 在使用了緩存的情況下如何保證召回結果和排序結果得到實時更新。
4.1、召回結果
在實時索引中，如前文所述，文檔更新時會被建入新的小索引段中。如果舊的索引段也包含此文檔，那麼此文檔在舊段中會被標記刪除。
ESearch 為每一個段分配了獨立的緩存，每個段各自將檢索結果從緩存中取出後，會用刪除表過濾掉已刪除的文檔，從而確保只有更新後的文檔能被檢索出來。
4.2、排序結果
為了便於打分排序，我們會把一些文檔特徵值存儲在索引中。這些特徵值不會作為召回條件，因此只建在正排索引中。對這類文檔屬性的更新可以不走前文所述的生成新段 - 段合併的更新流程，而是直接在正排索引中原地刷新，因此特徵值刷新的性能遠高於正常文檔更新，從而允許我們實時調整排序結果。
為了使特徵值的改變能夠實時影響排序結果，我們在從緩存中取出檢索結果後，對檢索結果會做第二次打分排序。由於緩存中的結果一般只包含 Top 幾百的文檔，因此第二次排序耗時有限，不影響整體性能。
除了保證實時性以外，這種兩階段排序也便於我們在 58 主站大規模應用複雜的機器學習排序模型。
複雜的排序策略通常比較耗時，因此業界在處理海量數據的排序時，通常用“粗排 - 精排”兩階段排序的方式，在效果和性能之間做一個合理折中，即先對海量數據進行低代價的粗排，然後對粗排的 TopN 結果進行代價較大的精排，最終整個處理過程耗時不會太大。
58 分類信息的特點也很適合這種模式，很多類目（例如租房）的信息注重時效性，時間序是主要排序因素。在信息發佈時間相近的前提下，需要根據信息質量、轉化率等其他因素進行更精細的排序。二次排序恰好可以用來實現這樣的流程：第一次排序對全量文檔按時間序求出 TopN 結果集保存在緩存中，第二次排序使用複雜的機器學習模型來對 TopN 結果打分重排。
五、總結
本文介紹了在 58 搜索內核 ESearch 中，如何根據 58 的數據和搜索特點來設計實時索引以及進行索引存儲和查詢流程方面的優化。隨著業務的不斷髮展，我們也將繼續在檢索性能、資源利用率、排序等方面持續優化，也歡迎感興趣的同學和我們一起交流。
閱讀更多 InfoQ 的文章
