您现在的位置是:首页 > 文章详情

基于Lucene查询原理分析Elasticsearch的性能

日期:2018-10-30点击:455

前言

Elasticsearch是一个很火的分布式搜索系统,提供了非常强大而且易用的查询和分析能力,包括全文索引、模糊查询、多条件组合查询、地理位置查询等等,而且具有一定的分析聚合能力。因为其查询场景非常丰富,所以如果泛泛的分析其查询性能是一个非常复杂的事情,而且除了场景之外,还有很多影响因素,包括机型、参数配置、集群规模等等。本文主要是针对几种主要的查询场景,从查询原理的角度分析这个场景下的查询开销,并给出一个大概的性能数字,供大家参考。

Lucene查询原理

本节主要是一些Lucene的背景知识,了解这些知识的同学可以略过。

Lucene的数据结构和查询原理

Elasticsearch的底层是Lucene,可以说Lucene的查询性能就决定了Elasticsearch的查询性能。关于Lucene的查询原理大家可以参考以下这篇文章:

Lucene查询原理

Lucene中最重要的就是它的几种数据结构,这决定了数据是如何被检索的,本文再简单描述一下几种数据结构:

  1. FST:保存term字典,可以在FST上实现单Term、Term范围、Term前缀和通配符查询等。
  2. 倒排链:保存了每个term对应的docId的列表,采用skipList的结构保存,用于快速跳跃。
  3. BKD-Tree:BKD-Tree是一种保存多维空间点的数据结构,用于数值类型(包括空间点)的快速查找。
  4. DocValues:基于docId的列式存储,由于列式存储的特点,可以有效提升排序聚合的性能。

组合条件的结果合并

了解了Lucene的数据结构和基本查询原理,我们知道:

  1. 对单个词条进行查询,Lucene会读取该词条的倒排链,倒排链中是一个有序的docId列表。
  2. 对字符串范围/前缀/通配符查询,Lucene会从FST中获取到符合条件的所有Term,然后就可以根据这些Term再查找倒排链,找到符合条件的doc。
  3. 对数字类型进行范围查找,Lucene会通过BKD-Tree找到符合条件的docId集合,但这个集合中的docId并非有序的。

现在的问题是,如果给一个组合查询条件,Lucene怎么对各个单条件的结果进行组合,得到最终结果。简化的问题就是如何求两个集合的交集和并集。

1. 对N个倒排链求交集

上面Lucene原理分析的文章中讲过,N个倒排链求交集,可以采用skipList,有效的跳过无效的doc。

2. 对N个倒排链求并集

处理方式一:仍然保留多个有序列表,多个有序列表的队首构成一个优先队列(最小堆),这样后续可以对整个并集进行iterator(堆顶的队首出堆,队列里下一个docID入堆),也可以通过skipList的方式向后跳跃(各个子列表分别通过skipList跳)。这种方式适合倒排链数量比较少(N比较小)的场景。

处理方式二:倒排链如果比较多(N比较大),采用方式一就不够划算,这时候可以直接把结果合并成一个有序的docID数组。

处理方式三:方式二中,直接保存原始的docID,如果docID非常多,很消耗内存,所以当doc数量超过一定值时(32位docID在BitSet中只需要一个bit,BitSet的大小取决于segments里的doc总数,所以可以根据doc总数和当前doc数估算是否BitSet更加划算),会采用构造BitSet的方式,非常节约内存,而且BitSet可以非常高效的取交/并集。

3. BKD-Tree的结果怎么跟其他结果合并

通过BKD-Tree查找到的docID是无序的,所以要么先转成有序的docID数组,或者构造BitSet,然后再与其他结果合并。

查询顺序优化

如果采用多个条件进行查询,那么先查询代价比较小的,再从小结果集上进行迭代,会更优一些。Lucene中做了很多这方面的优化,在查询前会先估算每个查询的代价,再决定查询顺序。

结果排序

默认情况下,Lucene会按照Score排序,即算分后的分数值,如果指定了其他的Sort字段,就会按照指定的字段排序。那么,排序会非常影响性能吗?首先,排序并不会对所有命中的doc进行排序,而是构造一个堆,保证前(Offset+Size)个数的doc是有序的,所以排序的性能取决于(Size+Offset)和命中的文档数,另外就是读取docValues的开销。因为(Size+Offset)并不会太大,而且docValues的读取性能很高,所以排序并不会非常的影响性能。

各场景查询性能分析

上一节讲了一些查询相关的理论知识,那么本节就是理论结合实践,通过具体的一些测试数字来分析一下各个场景的性能。测试采用单机单Shard、64核机器、SSD磁盘,主要分析各个场景的计算开销,不考虑操作系统Cache的影响,测试结果仅供参考。

单Term查询

ES中建立一个Index,一个shard,无replica。有1000万行数据,每行只有几个标签和一个唯一ID,现在将这些数据写入这个Index中。其中Tag1这个标签只有a和b两个值,现在要从1000万行中找到一条Tag1=a的数据(约500万)。给出以下查询,那么它耗时如何呢: 请求: { "query": { "constant_score": { "filter": { "term": { "Tag1": "a" } } } }, "size": 1 }' 响应: {"took":233,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5184867,"max_score":1.0,"hits":...}

这个请求耗费了233ms,并且返回了符合条件的数据总数:5184867条。

对于Tag1="a"这个查询条件,我们知道是查询Tag1="a"的倒排链,这个倒排链的长度是5184867,是非常长的,主要时间就花在扫描这个倒排链上。其实对这个例子来说,扫描倒排链带来的收益就是拿到了符合条件的记录总数,因为条件中设置了constant_score,所以不需要算分,随便返回一条符合条件的记录即可。对于要算分的场景,Lucene会根据词条在doc中出现的频率来计算分值,并取分值排序返回。

目前我们得到一个结论,233ms时间至少可以扫描500万的倒排链,另外考虑到单个请求是单线程执行的,可以粗略估算,一个CPU核在一秒内扫描倒排链内doc的速度是千万级的。

我们再换一个小一点的倒排链,长度为1万,总共耗时3ms。

{"took":3,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":10478,"max_score":1.0,"hits":...}

Term组合查询

首先考虑两个Term查询求交集:

对于一个Term的组合查询,两个倒排链分别为1万和500万,合并后符合条件的数据为5000,查询性能如何呢? 请求: { "size": 1, "query": { "constant_score": { "filter": { "bool": { "must": [ { "term": { "Tag1": "a" // 倒排链长度500万 } }, { "term": { "Tag2": "0" // 倒排链长度1万 } } ] } } } } } 响应: {"took":21,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5266,"max_score":2.0,"hits":...}

这个请求耗时21ms,主要是做两个倒排链的求交操作,因此我们主要分析skipList的性能。

这个例子中,倒排链长度是1万、500万,合并后仍有5000多个doc符合条件。对于1万的倒排链,基本上不进行skip,因为一半的doc都是符合条件的,对于500万的倒排链,平均每次skip1000个doc。因为倒排链在存储时最小的单位是BLOCK,一个BLOCK一般是128个docID,BLOCK内不会进行skip操作。所以即使能够skip到某个BLOCK,BLOCK内的docID还是要顺序扫描的。所以这个例子中,实际扫描的docID数粗略估计也有几十万,所以总时间花费了20多ms也符合预期。

对于Term查询求并集呢,将上面的bool查询的must改成should,查询结果为:

{"took":393,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5190079,"max_score":1.0,"hits":...}

花费时间393ms,所以求并集的时间是多于其中单个条件查询的时间。

字符串范围查询

RecordID是一个UUID,1000万条数据,每个doc都有一个唯一的uuid,从中查找0~7开头的uuid,大概结果有500多万个,性能如何呢? 请求: { "query": { "constant_score": { "filter": { "range": { "RecordID": { "gte": "0", "lte": "8" } } } } }, "size": 1 } 响应: {"took":3001,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5185663,"max_score":1.0,"hits":...} 查询a开头的uuid,结果大概有60多万,性能如何呢? 请求: { "query": { "constant_score": { "filter": { "range": { "RecordID": { "gte": "a", "lte": "b" } } } } }, "size": 1 } 响应: {"took":379,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":648556,"max_score":1.0,"hits":...}

这个查询我们主要分析FST的查询性能,从上面的结果中我们可以看到,FST的查询性能相比扫描倒排链要差许多,同样扫描500万的数据,倒排链扫描只需要不到300ms,而FST上的扫描花费了3秒,基本上是慢十倍的。对于UUID长度的字符串来说,FST范围扫描的性能大概是每秒百万级。

字符串范围查询加Term查询

字符串范围查询(符合条件500万),加上两个Term查询(符合条件5000),最终符合条件数目2600,性能如何? 请求: { "query": { "constant_score": { "filter": { "bool": { "must": [ { "range": { "RecordID": { "gte": "0", "lte": "8" } } }, { "term": { "Tag1": "a" } }, { "term": { "Tag2": "0" } } ] } } } }, "size": 1 } 结果: {"took":2849,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":2638,"max_score":1.0,"hits":...}

这个例子中,查询消耗时间的大头还是在扫描FST的部分,通过FST扫描出符合条件的Term,然后读取每个Term对应的docID列表,构造一个BitSet,再与两个TermQuery的倒排链求交集。

数字Range查询

对于数字类型,我们同样从1000万数据中查找500万呢? 请求: { "query": { "constant_score": { "filter": { "range": { "Number": { "gte": 100000000, "lte": 150000000 } } } } }, "size": 1 } 响应: {"took":567,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5183183,"max_score":1.0,"hits":...}

这个场景我们主要测试BKD-Tree的性能,可以看到BKD-Tree查询的性能还是不错的,查找500万个doc花费了500多ms,只比扫描倒排链差一倍,相比FST的性能有了很大的提升。地理位置相关的查询也是通过BKD-Tree实现的,性能很高。

数字Range查询加Term查询

这里我们构造一个复杂的查询场景,数字Range范围数据500万,再加两个Term条件,最终符合条件数据2600多条,性能如何? 请求: { "query": { "constant_score": { "filter": { "bool": { "must": [ { "range": { "Number": { "gte": 100000000, "lte": 150000000 } } }, { "term": { "Tag1": "a" } }, { "term": { "Tag2": "0" } } ] } } } }, "size": 1 } 响应: {"took":27,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":2638,"max_score":1.0,"hits":...}

这个结果出乎我们的意料,竟然只需要27ms!因为在上一个例子中,数字Range查询耗时500多ms,而我们增加两个Term条件后,时间竟然变为27ms,这是为何呢?

实际上,Lucene在这里做了一个优化,底层有一个查询叫做IndexOrDocValuesQuery,会自动判断是查询Index(BKD-Tree)还是DocValues。在这个例子中,查询顺序是先对两个TermQuery求交集,得到5000多个docID,然后读取这个5000多个docID对应的docValues,从中筛选符合数字Range条件的数据。因为只需要读5000多个doc的docValues,所以花费时间很少。

简单结论

  1. 总体上讲,扫描的doc数量越多,性能肯定越差。
  2. 单个倒排链扫描的性能在每秒千万级,这个性能非常高,如果对数字类型要进行Term查询,也推荐建成字符串类型。
  3. 通过skipList进行倒排链合并时,性能取决于最短链的扫描次数和每次skip的开销,skip的开销比如BLOCK内的顺序扫描等。
  4. FST相关的字符串查询要比倒排链查询慢很多(通配符查询更是性能杀手,本文未做分析)。
  5. 基于BKD-Tree的数字范围查询性能很好,但是由于BKD-Tree内的docID不是有序的,不能采用类似skipList的向后跳的方式,如果跟其他查询做交集,必须先构造BitSet,这一步可能非常耗时。Lucene中通过IndexOrDocValuesQuery对一些场景做了优化。

最后结尾再放一个彩蛋,既然扫描数据越多,性能越差,那么能否获取到足够数据就提前终止呢,下一篇文章我会介绍一种这方面的技术,可以极大的提高很多场景下的查询性能。

阿里云双十一1折拼团活动:已满6人,都是最低折扣了
【满6人】1核2G云服务器99.5元一年298.5元三年 2核4G云服务器545元一年 1227元三年
【满6人】1核1G MySQL数据库 119.5元一年
【满6人】3000条国内短信包 60元每6月
参团地址:http://click.aliyun.com/m/1000020293/

作者: 亦征
原文链接
本文为云栖社区原创内容,未经允许不得转载。

原文链接:https://my.oschina.net/yunqi/blog/2254806
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章