关于美团:美团外卖搜索基于Elasticsearch的优化实践

38次阅读

共计 12261 个字符，预计需要花费 31 分钟才能阅读完成。

美团外卖搜寻工程团队在 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）依赖，即用户所能点餐的商家，是由商家配送范畴决定的。对于每一个商家的配送范畴，大多采纳多组电子围栏进行配送间隔的圈定，一个商家存在多组电子围栏，并且随着业务的变动会动静抉择不同的配送范畴，电子围栏示意图如下：

思考到商家配送区域动静变更带来的问题，咱们没有应用 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 热点图中的反映也是如此：无论是查问倒排链、还是读取、合并倒排链都相当耗费资源，并且能够预感的是，在供应越来越多的状况下，这三个阶段的耗时还会持续增长。

能够明确，咱们须要针对倒排链查问、倒排链合并这两个问题予以优化。

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> 的键值对来结构数据，对其空间及性能进行了比照，后果如下：

内存占用 10 万个 Key 的查问工夫
FST 481kB 63ms
HashMap 9048kB 3.5ms
LongObjectHashMap 5545kB 1ms
论断 FST >> LongObjectHashMap > HashMap LongObjectHashMap > HashMap >> FST

能够看到，在内存占用上 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。

这两种 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 为例：

如上示例所示：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 咱们进行了如下革新。

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] 进行排序，并将排序后的后果合并为一个数组。那么咱们将原工夫复杂度为 $O(K * M + log(K * M))$ 的合并流程，革新为复杂度为 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 编码）进行存储的示意图：

能够看到：在 SparseRoaringDocIdSet 实现下，所有不为空的 bucket 被严密的排列在了一起，并在 index [] 中记录了其原始 bucket 的索引，这就防止了大量 bucket 被空置的状况。另外，在进行倒排链的合并时，就能够间接对严密排列的 denseSet 进行遍历，并从 index [] 取得其对应的原始 bucket location，这就防止了大量的空置 bucket 在合并时带来的性能节约。

咱们别离对以下 4 个场景进行了压测：原生的 TermInSetQuery 对倒排链的合并逻辑、基于 FixedBitSet 的批量合并、RLE based RoaringBitmap、RLE based Dense RoaringBitmap。对 10000 个均匀长度为 100 的倒排链进行合并压测，压测后果如下：

咱们实现的 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]。

  1. 由协调节点进行申请的散发，发送到各个检索节点上。
  2. 每个数据节点的各自进行检索，并返回检索后果给协调节点，这一段各个数据节点的耗时即“数据节点查问耗时”。
  3. 协调节点期待所有数据节点的返回，协调节点选取 Top K 后进行 fetch 操作。1～3 步的残缺耗时为“残缺链路查问耗时”。

咱们将上述改变（Index Sorting + Dense Roaring Bitmap + RLE）上线到生产环境的商品索引后，性能如下：

至此，咱们胜利将全链路的检索时延（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. 集成验证最终成果。

咱们最终实现的关键点：

  • 应用哈希表来实现索引 Term 的准确查找，以此缩小倒排链的查问与读取的工夫。
  • 选取 RoaringBitmap 作为存储倒排链的数据结构，并与 RLE Container 相结合，实现对倒排链的压缩存储。当然，最重要的是，RLE 编码将倒排链的合并问题转换成了排序问题，实现了批量合并，从而大幅度缩小了合并的性能耗费。

当然，咱们的计划也还具备一些能够持续摸索优化的中央。咱们进行具体计划开发的时候，次要思考解决咱们特定场景的问题，做了一些定制化，以获得最大的性能收益。在一些更通用的场景上，也能够通过 RLE 倒排取得收益，例如依据数据的散布，主动抉择 bitmap/array/RLE 容器，反对倒排链重叠的状况下的数据合并。

咱们在发现也有论文与咱们的想法不约而同，有趣味理解能够参考具体论文 [9]。另外，在增量索引场景下，如果增量索引的变更量十分大，那么势必会遇到频繁更新内存 RLE 倒排的状况，这对内存和性能的耗费都不小，基于性能的考量，也能够间接将 RLE 倒排索引的构造固化到文件中，即在写索引时就实现对倒排链的编码，这样就能防止这一问题。

7. 作者简介

泽钰、张聪、晓鹏等，均来自美团到家事业群 / 搜寻举荐技术部 - 搜寻工程团队。

8. 参考文献

[1] https://en.wikipedia.org/wiki…

[2] https://www.elastic.co/guide/…

[3] https://en.wikipedia.org/wiki…

[4] Frame of Reference and Roaring Bitmaps

[5] https://www.elastic.co/cn/blo…

[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/…

[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.

浏览美团技术团队更多技术文章合集

前端 | 算法 | 后端 | 数据 | 平安 | 运维 | iOS | Android | 测试

| 在公众号菜单栏对话框回复【2021 年货】、【2020 年货】、【2019 年货】、【2018 年货】、【2017 年货】等关键词，可查看美团技术团队历年技术文章合集。

| 本文系美团技术团队出品，著作权归属美团。欢送出于分享和交换等非商业目标转载或应用本文内容，敬请注明“内容转载自美团技术团队”。本文未经许可，不得进行商业性转载或者应用。任何商用行为，请发送邮件至 tech@meituan.com 申请受权。

正文完
美团
发表至： 美团
2022-11-18
 0
关于美团:提升资源利用率与保障服务质量鱼与熊掌如何兼得
关于美团:多场景多任务学习在美团到店餐饮推荐的实践
关于美团:美团无人车引擎在仿真中的实践
关于美团:TensorFlow在推荐系统中的分布式训练优化实践