美團外賣搜索基於 Elasticsearch 的優化實踐

美團外賣搜索工程團隊在 Elasticsearch 的優化實踐中，基於 Location-Based Service（LBS）業務場景對 Elasticsearch 的查詢性能進行優化。該優化基於 Run-Length Encoding（RLE）設計了一款高效的倒排索引結構，使檢索耗時（TP99）降低了 84%。本文從問題分析、技術選型、優化方案等方面進行闡述，並給出最終灰度驗證的結論。

1. 前言

最近十年，Elasticsearch 已經成爲了最受歡迎的開源檢索引擎，其作爲離線數倉、近線檢索、B 端檢索的經典基建，已沉澱了大量的實踐案例及優化總結。然而在高併發、高可用、大數據量的 C 端場景，目前可參考的資料並不多。因此，我們希望通過分享在外賣搜索場景下的優化實踐，能爲大家提供 Elasticsearch 優化思路上的一些借鑑。

美團在外賣搜索業務場景中大規模地使用了 Elasticsearch 作爲底層檢索引擎。其在過去幾年很好地支持了外賣每天十億以上的檢索流量。然而隨着供給與數據量的急劇增長，業務檢索耗時與 CPU 負載也隨之上漲。通過分析我們發現，當前檢索的性能熱點主要集中在倒排鏈的檢索與合併流程中。針對這個問題，我們基於 Run-length Encoding（RLE）[1] 技術設計實現了一套高效的倒排索引，使倒排鏈合併時間（TP99）降低了 96%。我們將這一索引能力開發成了一款通用插件集成到 Elasticsearch 中，使得 Elasticsearch 的檢索鏈路時延（TP99）降低了 84%。

2. 背景

當前，外賣搜索業務檢索引擎主要爲 Elasticsearch，其業務特點是具有較強的 Location Based Service（LBS） 依賴，即用戶所能點餐的商家，是由商家配送範圍決定的。對於每一個商家的配送範圍，大多采用多組電子圍欄進行配送距離的圈定，一個商家存在多組電子圍欄，並且隨着業務的變化會動態選擇不同的配送範圍，電子圍欄示意圖如下：

圖 1 電子圍欄示意圖

考慮到商家配送區域動態變更帶來的問題，我們沒有使用 Geo Polygon[2] 的方式進行檢索，而是通過上游一組 R-tree 服務判定可配送的商家列表來進行外賣搜索。因此，LBS 場景下的一次商品檢索，可以轉化爲如下的一次 Elasticsearch 搜索請求：

POST food/_search
{
   "query": {
      "bool": {
         "must":{
            "term": { "spu_name": { "value": "烤鴨"} }
           //...
         },
         "filter":{
           "terms": {
              "wm_poi_id": [1,3,18,27,28,29,...,37465542] // 上萬
            }
         }
      }
   }
  //...
}

對於一個通用的檢索引擎而言，Terms 檢索非常高效，平均到每個 Term 檢索不到 0.001 ms。因此在早期時，這一套架構和檢索 DSL 可以很好地支持美團的搜索業務——耗時和資源開銷尚在接受範圍內。然而隨着數據和供給的增長，一些供給豐富區域的附近可配送門店可以達到 20000~30000 家，這導致性能與資源問題逐漸凸顯。這種萬級別的 Terms 檢索的性能與耗時已然無法忽略，僅僅這一句檢索就需要 5~10 ms。

3. 挑戰及問題

由於 Elasticsearch 在設計上針對海量的索引數據進行優化，在過去的 10 年間，逐步去除了內存支持索引的功能（例如 RAMDirectory 的刪除）。爲了能夠實現超大規模候選集的檢索，Elasticsearch/Lucene 對 Term 倒排鏈的查詢流程設計了一套內存與磁盤共同處理的方案。

一次 Terms 檢索的流程分爲兩步：分別檢索單個 Term 的倒排鏈，多個 Term 的倒排鏈進行合併。

3.1 倒排鏈查詢流程

1. 從內存中的 Term Index 中獲取該 Term 所在的 Block 在磁盤上的位置。

2. 從磁盤中將該 Block 的 TermDictionary 讀取進內存。

3. 對倒排鏈存儲格式的進行 Decode，生成可用於合併的倒排鏈。

可以看到，這一查詢流程非常複雜且耗時，且各個階段的複雜度都不容忽視。所有的 Term 在索引中有序存儲，通過二分查找找到目標 Term。這個有序的 Term 列表就是 TermDictionary ，二分查找 Term 的時間複雜度爲 O(logN) ，其中 N 是 Term 的總數量 。Lucene 採用 Finite State Transducer[3]（FST）對 TermDictionary 進行編碼構建 Term Index。FST 可對 Term 的公共前綴、公共後綴進行拆分保存，大大壓縮了 TermDictionary 的體積，提高了內存效率，FST 的檢索速度是 O(len(term))，其對於 M 個 Term 的檢索複雜度爲 O(M * len(term))。

3.2 倒排鏈合併流程

在經過上述的查詢，檢索出所有目標 Term 的 Posting List 後，需要對這些 Posting List 求並集（OR 操作）。在 Lucene 的開源實現中，其採用 Bitset 作爲倒排鏈合併的容器，然後遍歷所有倒排鏈中的每一個文檔，將其加入 DocIdSet 中。

僞代碼如下：

Input:  termsEnum: 倒排表；termIterator：候選的term
Output: docIdSet : final docs set
for term in termIterator:
  if termsEnum.seekExact(term) != null:
     docs = read_disk()  // 磁盤讀取
     docs = decode(docs) // 倒排鏈的decode流程
     for doc in docs:
        docIdSet.or(doc) //代碼實現爲DocIdSetBuilder.add。
end for
docIdSet.build()//合併，排序，最終生成DocIdSetBuilder，對應火焰圖最後一段。

假設我們有 M 個 Term，每個 Term 對應倒排鏈的平均長度爲 K，那麼合併這 M 個倒排鏈的時間複雜度爲：O(K * M + log(K * M))。可以看出倒排鏈合併的時間複雜度與 Terms 的數量 M 呈線性相關。在我們的場景下，假設一個商家平均有一千個商品，一次搜索請求需要對一萬個商家進行檢索，那麼最終需要合併一千萬個商品，即循環執行一千萬次，導致這一問題被放大至無法被忽略的程度。

我們也針對當前的系統做了大量的調研及分析，通過美團內部的 JVM Profile 系統得到 CPU 的火焰圖，可以看到這一流程在 CPU 熱點圖中的反映也是如此：無論是查詢倒排鏈、還是讀取、合併倒排鏈都相當消耗資源，並且可以預見的是，在供給越來越多的情況下，這三個階段的耗時還會持續增長。

圖 2 profile 火焰圖

可以明確，我們需要針對倒排鏈查詢、倒排鏈合併這兩個問題予以優化。

4. 技術探索與實踐

4.1 倒排鏈查詢優化

通常情況下，使用 FST 作爲 Term 檢索的數據結構，可以在內存開銷和計算開銷上取得一個很好的平衡，同時支持前綴檢索、正則檢索等多種多樣的檢索 Query，然而在我們的場景之下，FST 帶來的計算開銷無法被忽視。

考慮到在外賣搜索場景有以下幾個特性：

• Term 的數據類型爲 long 類型。

• 無範圍檢索，均爲完全匹配。

• 無前綴匹配、模糊查找的需求，不需要使用前綴樹相關的特性。

• 候選數量可控，每個商家的商品數量較多，即 Term 規模可預期，內存可以承載這個數量級的數據。

因此在我們的應用場景中使用空間換取時間是值得的。

對於 Term 查詢的熱點：可替換 FST 的實現以減少 CPU 開銷，常見的查找數據結構中，哈希表有 O(1) 的查詢複雜度，將 Term 查找轉變爲對哈希表的一次查詢。

對於哈希表的選取，我們主要選擇了常見的 HashMap 和 LongObjectHashMap。

我們主要對比了 FST、HashMap 和 LongObjectHashMap（哈希表的一種高性能實現）的空間和時間效率。

• 在內存佔用上：FST 的內存效率極佳。而 HashMap/LongObjectHashMap 都有明顯的劣勢；

• 在查詢時間上：FST 的查詢複雜度在 O (len(term))，而 Hash/LongObjectHashMap 有着 O(1) 的查詢性能；

注：檢索類型雖然爲 Long，但是我們將底層存儲格式進行了調整，沒有使用開源的 BKD Tree 實現，使用 FST 結構，僅與 FST 進行對比。BKD Tree 在大批量整數 terms 的場景下劣勢更爲明顯。

我們使用十萬個 <Long, Long> 的鍵值對來構造數據，對其空間及性能進行了對比，結果如下：

可以看到， 在內存佔用上 FST 要遠優於 LongObjectHashMap 和 HashMap。而在查詢速度上 LongObjectHashMap 最優。

我們最終選擇了 LongObjectHashMap 作爲倒排鏈查詢的數據結構。

4.2 倒排鏈合併

基於上述問題，我們需要解決兩個明顯的 CPU 熱點問題：倒排鏈讀取 & 倒排鏈合併。我們需要選擇合適的數據結構緩存倒排鏈，不再執行磁盤 /page cache 的 IO。數據結構需要必須滿足以下條件：

• 支持批量 Merge，減少倒排鏈 Merge 耗時。

• 內存佔用少，需要處理千萬數量級的倒排鏈。

在給出具體的解決方案之前，先介紹一下 Lucene 對於倒排合併的原生實現、RoaringBitMap、Index Sorting。

4.2.1 原生實現

Lucene 在不同場景上使用了不同的倒排格式，提高整體的效率（空間 / 時間），通過火焰圖可以發現，在我們的場景上，TermInSetQuery 的倒排合併邏輯開銷最大。

TermInSetQuery 的倒排鏈合併操作分爲兩個步驟：倒排鏈讀取和合並。

1. 倒排鏈讀取：

Lucene 倒排鏈壓縮存儲在索引文件中，倒排鏈讀取需要實時解析，其對外暴露的 API 爲迭代器結構。

2. 倒排鏈合併：

倒排鏈合併主要由 DocIdSetBuilder 合併生成倒排鏈，先使用稀疏結構存儲 Doc ID，當  Doc ID 個數超過一定閾值時，升級到稠密結構（FixedBitSet）存儲，實現方式如下（對應代碼 IntArrayDocIdSet/BitDocIdSet）：

• 稀疏數據：存儲採用 List<int[]> array 方式存儲 Doc ID，最終經過 Merge 和排序形成一個有序數組 int[]，耗時主要集中在數組申請和排序。

• 稠密數據：基於 long[] 實現的 bitmap 結構（FixedBitSet），耗時主要集中在 FixedBitSet 的插入過程，由於倒排鏈需要實時 Decode 以及 FixedBitSet 的底層實現，無法實現批量 Merge，只能循環單個 Doc ID 插入，數據量大的情況下，耗時明顯。

我們採用線上流量和數據壓測發現該部分平均耗時約 7 ms。

4.2.2 RoaringBitmap

當前 Elasticsearch 選擇 RoaringBitMap 做爲 Query Cache 的底層數據結構緩存倒排鏈，加快查詢速率。

RoaringBitmap 是一種壓縮的位圖，相較於常規的壓縮位圖能提供更好的壓縮，在稀疏數據的場景下空間更有優勢。以存放 Integer 爲例，Roaring Bitmap 會對存入的數據進行分桶，每個桶都有自己對應的 Container。在存入一個 32 位的整數時，它會把整數劃分爲高 16 位和低 16 位，其中高 16 位決定該數據需要被分至哪個桶，我們只需要存儲這個數據剩餘的低 16 位，將低 16 位存儲到 Container 中，若當前桶不存在數據，直接存儲 null 節省空間。RoaringBitmap 有不同的實現方式，下面以 Lucene 實現（RoaringDocIdSet）進行詳細講解：

如原理圖中所示，RoaringBitmap 中存在兩種不同的 Container：Bitmap Container 和 Array Container。

圖 3 Elasticsearch 中 Roaringbitmap 的示意圖

這兩種 Container 分別對應不同的數據場景——若一個 Container 中的數據量小於 4096 個時，使用 Array Container 來存儲。當 Array Container 中存放的數據量大於 4096 時，Roaring Bitmap 會將 Array Container 轉爲 Bitmap Container。即 Array Container 用於存放稀疏數據，而 Bitmap Container 用於存放稠密數據，這樣做是爲了充分利用空間。下圖給出了隨着容量增長 Array Container 和 Bitmap Container 的空間佔用對比圖，當元素個數達到 4096 後（每個元素佔用 16 bit ），Array Container 的空間要大於 Bitmap Container。

備註：Roaring Bitmap 可參考官方博客 [4]。

4.2.3 Index Sorting

Elasticsearch 從 6.0 版本開始支持 Index Sorting[5] 功能，在索引階段可以配置多個字段進行排序，調整索引數據組織方式，可以調整文檔所對應的 Doc ID。以 city_id，poi_id 爲例：

圖 4 Index Sorting 示意圖

如上示例所示：Index Sorting 會將給定的排序字段（如上圖的 city_id 字段）的文檔排序在一起，相同排序值的文檔的 Doc ID 嚴格自增，對該字段建立倒排，那麼其倒排鏈爲自增數列。

4.3 基於 RLE 的倒排格式設計

基於以上的背景知識以及當前 Elasticsearch/Lucene 的解決方案，可以明確目前有 2 個改造點需要考慮。

• 合適的倒排結構，用於存儲每個 Term 的倒排鏈。

• 合適的中間結構，用於存儲多個 Term 合併後的倒排鏈。

對於索引倒排格式 PostingsEnum，支持接口爲：

public abstract class DocIdSetIterator {
  public abstract int docID();
  public abstract int nextDoc();
  public abstract int advance(int target);
}

倒排僅支持單文檔循環調用，不支持批量讀取，因此需要爲倒排增加批量順序讀取的功能。

對於多倒排鏈的合併，由於原結構 DocIdSetBuilder 的實現也不支持批量對數據進行合併，我們探索了評估了 Elasticsearch 用於緩存 Query Cache 的數據結構 RoaringBitMap，然而其實現 RoaringDocIdSet 也無法滿足我們對緩存數據結構特性需求，主要問題：

• 原生 RoaringDocIdSet 在構建時，只能支持遞增的添加 Doc ID。而在實際生產中每一個商家的商品的 Doc ID 都是離散的。這就限制了其使用範圍。

• 原生 RoaringDocIdSet 的底層存儲結構 Bitmap Container 和 Array Container 均不支持批量合併，這就無法滿足我們對倒排鏈合併進行優化的需求。

在明確這個問題的場景下，我們可以考慮最簡單的改造，支持索引倒排格式 PostingsEnum 的批量讀取。並考慮瞭如下幾種場景：

• 在支持批量讀取倒排的情況下，直接使用原結構 DocIdSetBuilder 進行批量的合併。

• 在支持批量讀取倒排的情況下，使用 RoaringBitMap 進行批量合併。

然而我們發現即使對 bitset 進行分段合併，直接對數據成段進行 OR 操作，整體開銷下降並不明顯。其原因主要在於：對於讀取的批量結果，均爲稀疏分佈的 Doc ID，僅減少倒排的循環調用無法解決性能開銷問題。

那麼問題需要轉化爲如何解決 Doc ID 分佈稀疏的問題。在上文提及的 Index Sorting 即一個絕佳的解決方案。並且由於業務 LBS 的特點，一次檢索的全部結果集均集中在某個地理位置附近，以及我們檢索僅針對門店列表 ID 的特殊場景，我們最終選擇對城市 ID、 Geohash、門店 ID 進行排序，從而讓稀疏分佈的 Doc ID 形成連續分佈。在這樣的排序規則應用之後，我們得到了一組絕佳的特性：每一個商家所對應的商品，其 Doc ID 完全連續。

4.3.1 Run-Length Encoding

Run-Length Encoding[3]（RLE）技術誕生於 50 年前，最早應用於連續的文本壓縮及圖像壓縮。在 2014 年，第一個開源在 GitHub 的 RoaringBitmap 誕生 [6]，2016 年，在 RoaringBitMap 的基礎上增加了對於自增序列的 RLE 實現 [7]，並應用在 bitmap 這一場景上。

在 bitmap 這一場景之下，主要通過壓縮連續區間的稠密數據，節省內存開銷。以數組 [1, 2, 3, ..., 59, 60, 89, 90, 91, ..., 99, 100] 爲例（如下圖上半部分）：使用 RLE 編碼之後就變爲 [1, 60, 89, 12]——形如 [start1, length1, start2, length2, ...] 的形式，其中第一位爲連續數字的起始值，第二位爲其長度。

在數組完全連續場景下中，對 32768 個 id (short) 進行存儲，數組存儲需要 64 kB，Bitmap 存儲需要使用 4 kB，而 RLE 編碼後直接存儲僅需要 4 byte。在這一特性下，如果商家倒排鏈完全有序，那麼商家的倒排鏈，可被壓縮到最低僅需要兩個整數即可表示。

當然 RLE 並不適用所有情況，在目標序列完全不連續的場景下，如 [1, 3, 5, 7, ... , M]，RLE 編碼存儲需要使用 2 * M byte 的空間，比數組直接存儲的空間效率差一倍。

爲了和 Elasticsearch 的實現保持一致，我們決定使用 RoaringBitMap 作爲倒排存儲的結構，以及中間結果合併的數據結構。針對 RoaringDocIdSet 我們進行了如下改造。

圖 5 倒排鏈 Merge 方式的演進

4.3.2 RLE Container 的實現

在對商家 ID 字段開啓 Index Sorting 之後，同商家的商品 ID 已經連續分佈。那麼對於商家字段的倒排鏈就是嚴格自增且無空洞的整數序列。我們採用 RLE 編碼對倒排鏈進行編碼存儲。由於將倒排鏈編碼爲 [start1, length1, start2, length2, ...]，更特殊的，在我們場景下，一個倒排鏈的表示爲  [start, length]，RLE 編碼做到了對倒排鏈的極致壓縮，假設倒排鏈爲 [1, 2, ...., 1000]， 用 ArrayContainer 存儲，內存空間佔用爲 16 bit * 100 = 200 Byte, RLE 編碼存儲只需要 16 bit * 2 = 4 Byte。考慮到具體的場景分佈，以及其他場景可能存在多段有序倒排的情況，我們最終選擇了 [start1, length1, start2, length2, ...] 這樣的存儲格式，且 [start,  start + length] 之間兩兩互不重疊。

對於多個商家的倒排合併流程，對於該格式的合併，我們並不需要對 M 個倒排鏈長度爲 K 進行循環處理，這個問題轉變爲：如何對多組分段 [start, length] 進行排序，並將排序後的結果合併爲一個數組。那麼我們將原時間複雜度爲 HwGdnD 的合併流程，改造爲複雜度爲 O(M * logM) 的合併流程，大大降低了合併的計算耗時，減少了 CPU 的消耗。

4.3.3 SparseRoaringDocIdSet 實現

我們在 RoaringDocIdSet 的基礎上增加了 RLE Container 後，性能已經得到了明顯的提升，加速了 50%，然而依然不符合我們的預期。我們通過對倒排鏈的數據分析發現：倒排鏈的平均長度不大，基本在十萬內。但是其取值範圍廣 [0, Integer.MAX-1]。這些特徵說明，如果以 RoaringDocIdSet 按高 16 位進行分桶的話，大部分數據將集中在其中連續的幾個桶中。

在 Elasticsearch 場景上，由於無法預估數據分佈，RoaringDocIdSet 在申請 bucket 容器的數組時，會根據當前 Segment 中的最大 Doc ID 來申請，計算公式爲：(maxDoc + (1 << 16) -  1) >>> 16。這種方式可以避免每次均按照 Integer.MAX-1 來創建容器帶來的無謂開銷。然而，當倒排鏈數量偏少且分佈集中時，這種方式依然無法避免大量 bucket 被空置的空間浪費；另一方面，在對倒排鏈進行合併時，這些空置的 bucket 也會參與到遍歷中，即使它被置爲了空。這就又造成了性能上的浪費。我們通過壓測評估證實了這一推理，即空置的 bucket 在合併時也會佔用大量的 CPU 資源。

針對這一問題，我們設計了一套用於稀疏數據的方案，實現了 SparseRoaringDocIdSet，同時保持接口與 RoaringDocIdSet 一致，可在各場景下進行復用，其結構如下：

class SparseRoaringDocIdSet {
   int[] index;       // 記錄有 container 的 bucket Index
   Container[] denseSets;  // 記錄緊密排列的倒排鏈
}

保存倒排鏈的過程與 RoaringDocIDSet 保持一致，在確認具體的 Container 的分桶時，我們額外使用一組索引記錄所有有值的 bucket 的 location。

下圖是一組分別使用 RLE based RoaringDocIdSet 和 SparseRoaringDocIdSet 對 [846710, 100, 936858, 110] 倒排鏈（RLE 編碼）進行存儲的示意圖：

圖 6 SparseRoaringDocIdSet 編排

可以看到：在 SparseRoaringDocIdSet 實現下，所有不爲空的 bucket 被緊密的排列在了一起，並在 index [] 中記錄了其原始 bucket 的索引，這就避免了大量 bucket 被空置的情況。另外，在進行倒排鏈的合併時，就可以直接對緊密排列的 denseSet 進行遍歷，並從 index [] 獲得其對應的原始 bucket location，這就避免了大量的空置 bucket 在合併時帶來的性能浪費。

我們分別對以下 4 個場景進行了壓測：原生的 TermInSetQuery 對倒排鏈的合併邏輯、基於 FixedBitSet 的批量合併、RLE based  RoaringBitmap、RLE based Dense RoaringBitmap。對 10000 個平均長度爲 100 的倒排鏈進行合併壓測，壓測結果如下：

圖 7 倒排鏈 Merge 性能比對

我們實現的 RLE based Dense RoaringBitmap，相比官方的基準實現耗時降低了 96%（TP99 13 ms 下降至 0.5 ms）。

4.4 功能集成

至此，核心的倒排索引問題已經解決，後續主要爲工程問題：如何在 Elasticsearch 系統中集成基於 RLE 的倒排格式。對於高吞吐高併發的 C 端在線場景，我們希望儘可能保障線上的穩定，對開源數據格式的兼容，保障前向的兼容，做到隨時可降級。

工程部分主要分爲兩部分：倒排索引的集成和在線檢索鏈路。以下主要介紹全量索引部分的鏈路設計。

4.4.1 倒排索引集成

倒排索引格式的改造，一般情況下，需要實現一套 PostingsFormat，並實現對應的 Reader、Writer。爲了保證對原有檢索語句的兼容，支持多種場景的檢索，以及爲了未來能夠無縫的配合 Elasticsearch 的版本升級，我們並沒有選擇直接實現一組新的 PostingsFormat，避免出現不兼容的情況導致無法升級版本。我們選擇了基於現有的倒排格式，在服務加載前後初始化 RLE 倒排，並考慮到業務場景，我們決定將 RLE 倒排全量放入內存中，以達到極致的性能。具體的解決方案爲：

1. 索引加載過程中增加一組 Hook，用於獲取現有的 InternalEngine（ Elasticsearch 中負責索引增刪改查的主要對象 ）。

2. 對所有的 semgents 遍歷讀取數據，解析倒排數據。

3. 對所有配置了 RLE 倒排優化的字段，生成 RLE 倒排表。

4. 將 RLE 倒排表與 segment 做關聯，保證後續的檢索鏈路中能獲取到倒排表。

爲了避免內存泄漏，我們也將索引刪除，segment 變更的場景進行了相應的處理。

4.4.2 在線檢索鏈路

在線檢索鏈路也採用了無侵入兼容的實現，我們實現了一套新的檢索語句，並且在索引無 RLE 倒排的情況下，可以降級回原生的檢索類型，更加安全。

我們基於 Elasticsearch 的插件機制，生成一組新的 Query，實現了其 AbstractQueryBuilder，實現對 Query 的解析與改寫，並將 Query 與 RLE 倒排進行關聯，我們通過改寫具體的檢索實現，將整個鏈路集成到 Elasticsearch 中。

5. 性能收益

對於 Elasticsearch 而言，一次檢索分爲這麼幾個階段，可參考下圖 [8]。

圖 8 Elasticsearch 的檢索過程

1. 由協調節點進行請求的分發，發送到各個檢索節點上。

2. 每個數據節點的各自進行檢索，並返回檢索結果給協調節點，這一段各個數據節點的耗時即 “數據節點查詢耗時”。

3. 協調節點等待所有數據節點的返回，協調節點選取 Top K 後進行 fetch 操作。1～3 步的完整耗時爲 “完整鏈路查詢耗時”。

我們將上述改動（Index Sorting + Dense Roaring Bitmap + RLE）上線到生產環境的商品索引後，性能如下：

圖 9 數據節點查詢耗時圖 10 完整鏈路查詢耗時

至此，我們成功將全鏈路的檢索時延（TP99）降低了 84%（100 ms 下降至 16 ms），解決了外賣搜索的檢索耗時問題，並且線上服務的 CPU 也大大降低。

6. 總結與展望

本文主要針對搜索業務場景中遇到的問題，進行問題分析、技術選型、壓測、選擇合適的解決方案、集成、灰度驗證。我們最終實現了一套基於 RLE 倒排格式，作爲一種新型的倒排格式，徹底解決了這個場景上的性能瓶頸，從分析至上線的流程長達數月。本文希望能提供一個思路，讓其他同學在遇到 Elasticsearch 相關的性能問題時，也能遵循相同的路徑，解決業務上的問題。

一般的，我們分析問題可以遵循這樣的路徑：

1. 明確性能問題後，首先通過流量錄製，獲得一個用於後續基準壓測的測試集合。

2. 通過相關的性能分析工具，先明確是否存在 CPU 的熱點或 IO 問題，對於 Java 技術棧，有很多常見的可用於分析性能的工具，美團內部有 Scaple 分析工具，外部可以使用 JProfiler、Java Flight Recorder、Async Profiler、Arthas、perf 這些工具。

3. 對分析火焰圖進行分析，配合源代碼，進行數據分析和驗證。

4. 此外在 Elasticsearch 中還可以通過 Kibana 的 Search Profiler 用於協助定位問題。在錄製大量的流量，抽樣分析後，以我們的場景爲例，進行 Profiler 後可以明確 TermInSetQuery 佔用了一半以上的耗時。

5. 明確問題後從索引、檢索鏈路兩側進行分析，評估問題，進行多種解決方案的設計與嘗試，通過 Java Microbenchmark Harness（JMH）代碼基準測試工具，驗證解決方案的有效性。

6. 集成驗證最終效果。

圖 11 Kibana 中的 Search Profiler 示例

我們最終實現的關鍵點：

• 使用哈希表來實現索引 Term 的精確查找，以此減少倒排鏈的查詢與讀取的時間。

• 選取 RoaringBitmap 作爲存儲倒排鏈的數據結構，並與 RLE Container 相結合，實現對倒排鏈的壓縮存儲。當然，最重要的是，RLE 編碼將倒排鏈的合併問題轉換成了排序問題，實現了批量合併，從而大幅度減少了合併的性能消耗。

當然，我們的方案也還具有一些可以繼續探索優化的地方。我們進行具體方案開發的時候，主要考慮解決我們特定場景的問題，做了一些定製化，以取得最大的性能收益。在一些更通用的場景上，也可以通過 RLE 倒排獲得收益，例如根據數據的分佈，自動選擇 bitmap/array/RLE 容器，支持倒排鏈重疊的情況下的數據合併。

我們在發現也有論文與我們的想法不謀而合，有興趣瞭解可以參考具體論文 [9]。另外，在增量索引場景下，如果增量索引的變更量非常大，那麼勢必會遇到頻繁更新內存 RLE 倒排的情況，這對內存和性能的消耗都不小，基於性能的考量，也可以直接將 RLE 倒排索引的結構固化到文件中，即在寫索引時就完成對倒排鏈的編碼，這樣就能避免這一問題。

7. 作者簡介

澤鈺、張聰、曉鵬等，均來自美團到家事業羣 / 搜索推薦技術部 - 搜索工程團隊。

8. 參考文獻

[1] https://en.wikipedia.org/wiki/Run-length_encoding

[2] https://www.elastic.co/guide/en/elasticsearch/reference/7.10/query-dsl-geo-polygon-query.html

[3] https://en.wikipedia.org/wiki/Finite-state_transducer

[4] Frame of Reference and Roaring Bitmaps

[5] https://www.elastic.co/cn/blog/index-sorting-elasticsearch-6-0

[6] Chambi S, Lemire D, Kaser O, et al. Better bitmap performance with roaring bitmaps[J]. Software: practice and experience, 2016, 46(5): 709-719.

[7] Lemire D, Ssi‐Yan‐Kai G, Kaser O. Consistently faster and smaller compressed bitmaps with roaring[J]. Software: Practice and Experience, 2016, 46(11): 1547-1569.

[8] 檢索兩階段流程：https://www.elastic.co/guide/cn/elasticsearch/guide/current/_fetch_phase.html#_fetch_phase

[9] Arroyuelo D, González S, Oyarzún M, et al. Document identifier reassignment and run-length-compressed inverted indexes for improved search performance[C]//Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval. 2013: 173-182.

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/6k8THshasaYfSaLr58O1NA