美团外卖搜寻工程团队在Elasticsearch的优化实际中，基于Location-Based Service（LBS）业务场景对Elasticsearch的查问性能进行优化。该优化基于Run-Length Encoding（RLE）设计了一款高效的倒排索引构造，使检索耗时（TP99）升高了84%。本文从问题剖析、技术选型、优化计划等方面进行论述，并给出最终灰度验证的论断。
最近十年，Elasticsearch 曾经成为了最受欢迎的开源检索引擎，其作为离线数仓、近线检索、B端检索的经典基建，已积淀了大量的实际案例及优化总结。然而在高并发、高可用、大数据量的 C 端场景，目前可参考的材料并不多。因而，咱们心愿通过分享在外卖搜寻场景下的优化实际，能为大家提供 Elasticsearch 优化思路上的一些借鉴。
美团在外卖搜寻业务场景中大规模地应用了 Elasticsearch 作为底层检索引擎。其在过来几年很好地反对了外卖每天十亿以上的检索流量。然而随着供应与数据量的急剧增长，业务检索耗时与 CPU 负载也随之上涨。通过剖析咱们发现，以后检索的性能热点次要集中在倒排链的检索与合并流程中。针对这个问题，咱们基于 Run-length Encoding（RLE）[1] 技术设计实现了一套高效的倒排索引，使倒排链合并工夫（TP99）升高了 96%。咱们将这一索引能力开发成了一款通用插件集成到 Elasticsearch 中，使得 Elasticsearch 的检索链路时延（TP99）升高了 84%。
以后，外卖搜寻业务检索引擎次要为 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。
因为 Elasticsearch 在设计上针对海量的索引数据进行优化，在过来的 10 年间，逐渐去除了内存反对索引的性能（例如 RAMDirectory 的删除）。为了可能实现超大规模候选集的检索，Elasticsearch/Lucene 对 Term 倒排链的查问流程设计了一套内存与磁盘独特解决的计划。
一次 Terms 检索的流程分为两步：别离检索单个 Term 的倒排链，多个 Term 的倒排链进行合并。
能够看到，这一查问流程非常复杂且耗时，且各个阶段的复杂度都不容忽视。所有的 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))。
在通过上述的查问，检索出所有指标 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 热点图中的反映也是如此：无论是查问倒排链、还是读取、合并倒排链都相当耗费资源，并且能够预感的是，在供应越来越多的状况下，这三个阶段的耗时还会持续增长。
能够明确，咱们须要针对倒排链查问、倒排链合并这两个问题予以优化。
通常状况下，应用 FST 作为 Term 检索的数据结构，能够在内存开销和计算开销上获得一个很好的均衡，同时反对前缀检索、正则检索等多种多样的检索 Query，然而在咱们的场景之下，FST 带来的计算开销无奈被忽视。
思考到在外卖搜寻场景有以下几个个性：
因而在咱们的利用场景中应用空间换取工夫是值得的。
对于 Term 查问的热点：可替换 FST 的实现以缩小 CPU 开销，常见的查找数据结构中，哈希表有 O(1) 的查问复杂度，将 Term 查找转变为对哈希表的一次查问。
对于哈希表的选取，咱们次要抉择了常见的 HashMap 和 LongObjectHashMap。
咱们次要比照了 FST、HashMap 和 LongObjectHashMap（哈希表的一种高性能实现）的空间和工夫效率。
注：检索类型尽管为 Long，然而咱们将底层存储格局进行了调整，没有应用开源的 BKD Tree 实现，应用 FST 构造，仅与 FST 进行比照。BKD Tree 在大批量整数 terms 的场景下劣势更为显著。
咱们应用十万个
| 内存占用 | 10 万个 Key 的查问工夫 | |
|---|---|---|
| FST | 481kB | 63ms |
| HashMap | 9048kB | 3.5ms |
| LongObjectHashMap | 5545kB | 1ms |
| 论断 | FST >> LongObjectHashMap > HashMap | LongObjectHashMap > HashMap >> FST |
能够看到， 在内存占用上 FST 要远优于 LongObjectHashMap 和 HashMap。而在查问速度上 LongObjectHashMap 最优。
咱们最终抉择了 LongObjectHashMap 作为倒排链查问的数据结构。
基于上述问题，咱们须要解决两个显著的 CPU 热点问题：倒排链读取 & 倒排链合并。咱们须要抉择适合的数据结构缓存倒排链，不再执行磁盘 /page cache 的 IO。数据结构须要必须满足以下条件：
在给出具体的解决方案之前，先介绍一下 Lucene 对于倒排合并的原生实现、RoaringBitMap、Index Sorting。
Lucene在不同场景上应用了不同的倒排格局，进步整体的效率（空间/工夫），通过火焰图能够发现，在咱们的场景上，TermInSetQuery 的倒排合并逻辑开销最大。
TermInSetQuery 的倒排链合并操作分为两个步骤：倒排链读取和合并。
倒排链读取：
Lucene 倒排链压缩存储在索引文件中，倒排链读取须要实时解析，其对外裸露的 API 为迭代器构造。
倒排链合并：
倒排链合并次要由 DocIdSetBuilder 合并生成倒排链，先应用稠密构造存储 Doc ID，当 Doc ID 个数超过肯定阈值时，降级到浓密构造（FixedBitSet）存储，实现形式如下（对应代码 IntArrayDocIdSet/BitDocIdSet）：
咱们采纳线上流量和数据压测发现该局部均匀耗时约 7 ms。
以后 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]。
Elasticsearch 从 6.0 版本开始反对 Index Sorting[5] 性能，在索引阶段能够配置多个字段进行排序，调整索引数据组织形式，能够调整文档所对应的 Doc ID。以 city_id，poi_id 为例：
如上示例所示：Index Sorting 会将给定的排序字段（如上图的 city_id 字段）的文档排序在一起，雷同排序值的文档的 Doc ID 严格自增，对该字段建设倒排，那么其倒排链为自增数列。
基于以上的背景常识以及以后 Elasticsearch/Lucene 的解决方案，能够明确目前有 2 个革新点须要思考。
对于索引倒排格局 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 也无奈满足咱们对缓存数据构造个性需要，次要问题：
在明确这个问题的场景下，咱们能够思考最简略的革新，反对索引倒排格局 PostingsEnum 的批量读取。并思考了如下几种场景：
然而咱们发现即便对 bitset 进行分段合并，间接对数据成段进行 OR 操作，整体开销降落并不显著。其起因次要在于：对于读取的批量后果，均为稠密散布的 Doc ID，仅缩小倒排的循环调用无奈解决性能开销问题。
那么问题须要转化为如何解决 Doc ID 散布稠密的问题。在上文提及的 Index Sorting 即一个绝佳的解决方案。并且因为业务 LBS 的特点，一次检索的全副后果集均集中在某个地理位置左近，以及咱们检索仅针对门店列表 ID 的非凡场景，咱们最终抉择对城市 ID、 Geohash、门店 ID 进行排序，从而让稠密散布的 Doc ID 造成间断散布。在这样的排序规定利用之后，咱们失去了一组绝佳的个性：每一个商家所对应的商品，其 Doc ID 齐全间断。
Run-Length Encoding[3]（RLE）技术诞生于50年前，最早利用于间断的文本压缩及图像压缩。在 2014 年，第一个开源在 GitHub 的 RoaringBitmap 诞生[6]，2016年，在 RoaringBitMap 的根底上减少了对于自增序列的 RLE 实现[7]，并利用在 bitmap 这一场景上。
在 bitmap 这一场景之下，次要通过压缩间断区间的浓密数据，节俭内存开销。以数组 [1, 2, 3, &＃8230;, 59, 60, 89, 90, 91, &＃8230;, 99, 100] 为例（如下图上半局部）：应用 RLE 编码之后就变为 [1, 60, 89, 12]——形如 [start1, length1, start2, length2, &＃8230;] 的模式，其中第一位为间断数字的起始值，第二位为其长度。
在数组齐全间断场景下中，对 32768 个 id (short) 进行存储，数组存储须要 64 kB，Bitmap 存储须要应用 4 kB，而 RLE 编码后间接存储仅须要 4 byte。在这一个性下，如果商家倒排链齐全有序，那么商家的倒排链，可被压缩到最低仅须要两个整数即可示意。
当然 RLE 并不实用所有状况，在指标序列齐全不间断的场景下，如 [1, 3, 5, 7, &＃8230; , M]，RLE 编码存储须要应用 2 * M byte的空间，比数组间接存储的空间效率差一倍。
为了和 Elasticsearch 的实现保持一致，咱们决定应用 RoaringBitMap 作为倒排存储的构造，以及两头后果合并的数据结构。针对 RoaringDocIdSet 咱们进行了如下革新。
在对商家 ID 字段开启 Index Sorting 之后，同商家的商品 ID 曾经间断散布。那么对于商家字段的倒排链就是严格自增且无空洞的整数序列。咱们采纳RLE编码对倒排链进行编码存储。因为将倒排链编码为 [start1, length1, start2, length2, &＃8230;]，更非凡的，在咱们场景下，一个倒排链的示意为 [start, length]，RLE编码做到了对倒排链的极致压缩，假如倒排链为 [1, 2, &＃8230;., 1000]， 用 ArrayContainer 存储，内存空间占用为 16 bit 100 = 200 Byte, RLE 编码存储只须要 16 bit 2 = 4 Byte。思考到具体的场景散布，以及其余场景可能存在多段有序倒排的状况，咱们最终抉择了 [start1, length1, start2, length2, &＃8230;] 这样的存储格局，且 [start, start + length] 之间两两互不重叠。
对于多个商家的倒排合并流程，对于该格局的合并，咱们并不需要对 M 个倒排链长度为 K 进行循环解决，这个问题转变为：如何对多组分段 [start, length] 进行排序，并将排序后的后果合并为一个数组。那么咱们将原工夫复杂度为 $O(K * M + log(K * M))$ 的合并流程，革新为复杂度为 O(M * logM) 的合并流程，大大降低了合并的计算耗时，缩小了 CPU 的耗费。
咱们在 RoaringDocIdSet 的根底上减少了 RLE Container 后，性能曾经失去了显著的晋升，减速了 50%，然而仍然不合乎咱们的预期。咱们通过对倒排链的数据分析发现：倒排链的均匀长度不大，根本在十万内。然而其取值范围广 [ 0, Integer.MAX-1 ]。这些特色阐明，如果以 RoaringDocIdSet 按高 16 位进行分桶的话，大部分数据将集中在其中间断的几个桶中。
在 Elasticsearch 场景上，因为无奈预估数据分布，RoaringDocIdSet 在申请 bucket 容器的数组时，会依据以后 Segment 中的最大 Doc ID 来申请，计算公式为：(maxDoc + (1 <<16) &＃8211; 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）。
至此，外围的倒排索引问题曾经解决，后续次要为工程问题：如何在 Elasticsearch 零碎中集成基于 RLE 的倒排格局。对于高吞吐高并发的C端在线场景，咱们心愿尽可能保障线上的稳固，对开源数据格式的兼容，保障前向的兼容，做到随时可降级。
工程局部次要分为两局部：倒排索引的集成和在线检索链路。以下次要介绍全量索引局部的链路设计。
倒排索引格局的革新，个别状况下，须要实现一套 PostingsFormat，并实现对应的 Reader、Writer。为了保障对原有检索语句的兼容，反对多种场景的检索，以及为了将来可能无缝的配合 Elasticsearch 的版本升级，咱们并没有抉择间接实现一组新的 PostingsFormat，避免出现不兼容的状况导致无奈降级版本。咱们抉择了基于现有的倒排格局，在服务加载前后初始化 RLE 倒排，并思考到业务场景，咱们决定将 RLE 倒排全量放入内存中，以达到极致的性能。具体的解决方案为：
为了防止内存透露，咱们也将索引删除，segment 变更的场景进行了相应的解决。
在线检索链路也采纳了无侵入兼容的实现，咱们实现了一套新的检索语句，并且在索引无 RLE 倒排的状况下，能够降级回原生的检索类型，更加平安。
咱们基于 Elasticsearch 的插件机制，生成一组新的 Query，实现了其 AbstractQueryBuilder，实现对 Query 的解析与改写，并将 Query 与 RLE 倒排进行关联，咱们通过改写具体的检索实现，将整个链路集成到 Elasticsearch 中。
对于 Elasticsearch 而言，一次检索分为这么几个阶段，可参考下图[8]。
咱们将上述改变（Index Sorting + Dense Roaring Bitmap + RLE）上线到生产环境的商品索引后，性能如下：
至此，咱们胜利将全链路的检索时延（TP99）升高了 84%（100 ms 降落至 16 ms），解决了外卖搜寻的检索耗时问题，并且线上服务的 CPU 也大大降低。
本文次要针对搜寻业务场景中遇到的问题，进行问题剖析、技术选型、压测、抉择适合的解决方案、集成、灰度验证。咱们最终实现了一套基于 RLE 倒排格局，作为一种新型的倒排格局，彻底解决了这个场景上的性能瓶颈，从剖析至上线的流程长达数月。本文心愿能提供一个思路，让其他同学在遇到 Elasticsearch 相干的性能问题时，也能遵循雷同的门路，解决业务上的问题。
个别的，咱们剖析问题能够遵循这样的门路：
咱们最终实现的关键点：
当然，咱们的计划也还具备一些能够持续摸索优化的中央。咱们进行具体计划开发的时候，次要思考解决咱们特定场景的问题，做了一些定制化，以获得最大的性能收益。在一些更通用的场景上，也能够通过 RLE 倒排取得收益，例如依据数据的散布，主动抉择 bitmap/array/RLE 容器，反对倒排链重叠的状况下的数据合并。
咱们在发现也有论文与咱们的想法不约而同，有趣味理解能够参考具体论文[9]。另外，在增量索引场景下，如果增量索引的变更量十分大，那么势必会遇到频繁更新内存 RLE 倒排的状况，这对内存和性能的耗费都不小，基于性能的考量，也能够间接将 RLE 倒排索引的构造固化到文件中，即在写索引时就实现对倒排链的编码，这样就能防止这一问题。
泽钰、张聪、晓鹏等，均来自美团到家事业群/搜寻举荐技术部-搜寻工程团队。
[1] https://en.wikipedia.org/wiki&＃8230;
[2] https://www.elastic.co/guide/&＃8230;
[3] https://en.wikipedia.org/wiki&＃8230;
[4] Frame of Reference and Roaring Bitmaps
[5] https://www.elastic.co/cn/blo&＃8230;
[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/&＃8230;
[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申请受权。
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有