ES5.x

ES5.x

number?keyword?傻傻分不清楚

Elasticsearchkennywu76 发表了文章 • 6 个评论 • 2993 次浏览 • 2018-01-09 00:46 • 来自相关话题

【携程旅行网 吴晓刚】

上周,在某多多搬砖的一位朋友在微信上找我咨询,说他们公司一个ES集群从2.4升级到5.5以后,一个很简单的Query查询耗时突然从几十毫秒,变成800-1000毫秒,几十倍的性能下降!原始问题链接:# Why my search slow?

这个查询非常简单,就是3个过滤条件求并集而已:

{
      "from": 0,
      "size": 10,
      "query": {
      "bool": {
      "filter": [
        {
          "terms": {
            "goods_id": [
              "262628158"
            ],
            "boost": 1.0
          }
        },
        {
          "terms": {
            "status": [
              "2",
              "4"
            ],
            "boost": 1.0
          }
        },
        {
          "range": {
            "create_time": {
              "from": "1514027649",
              "to": "1514632449",
              "include_lower": true,
              "include_upper": true,
              "boost": 1.0
            }
          }
        }
      ],
      "disable_coord": false,
      "adjust_pure_negative": true,
      "boost": 1.0
    }
  },
  "sort": [
    {
      "create_time": {
        "order": "desc"
      }
    }
  ]
}

通过profile查看,发现耗时主要在status字段的build_scorer这个阶段。

对方同时提到,只要去掉"status":["2", "4"]这个查询条件,速度就会恢复正常。进一步询问后得知,查询的索引文档总量相当巨大,达到16亿条,而status字段只有几个不同的数字,在mapping里被定义为数值型short

我的第一反应,status只有几个值,意味着该字段的filter得到的结果集是海量的。可能是处理这个大结果集的代价很高造成的缓慢,但是具体什么原因我一时也说不上来。

脑子里开始翻查ES 2.x -> 5.x升级对于数值类型和Term Query有何重大变化?想起来两点:

  1. Lucene6.0引入了重新设计的数值类型的索引结构,不再采用倒排索,而是使用了更适合范围查找的Block K-d Tree。 ES从5.0开始引入这种新结构。(参考: searching-numb3rs-in-5.0
  2. Term Query由于通常非常快,从5.1.1开始不再被缓存到Query Cache

显然这个status字段不用于范围查找,字段类型设置上keyword比number更合理。 但我也没想明白为何number在这场景下查询会慢这么多,所以我也稍稍有些怀疑2.x缓存了Term Query是造成性能差异的原因。 当时让朋友做了个测试,将TermQuery换成RangeQuery,被告知速度飞快,只要几十个毫秒,并且多执行几次后更是快到只有几个毫秒了。(因为RangeQuery反复执行会被Cache起来)。

隔天,朋友根据建议将status先改为keyword,重新索引数据后,查询性能奇迹般的恢复到正常,所以基本可以确定和缓存无关了。

恰巧社区也有人在经历同样的问题: Elastic对类似枚举数据的搜索性能优化 ,看起来是个普遍现象,值得研究找出问题根源。

花了几天的时间参阅技术文档,也粗略读了一下ES/Lucene相关代码后,总算搞清楚了问题的来龙去脉。 本文将对相关技术细节做分析,然后回答下面3个问题:

  1. 为什么ES5.x里对数值型字段做TermQuery可能会很慢?
  2. 为何Profile里显示的耗时几乎全部在build_scorer?
  3. 为什么对同样的数值型字段做RangeQuery却又很快了?

为更好的理解这个问题,先谈一下几点预备知识:

  • ES2.x和5.x的数值类型分别是如何索引的
  • Block k-d tree的基本概念和Lucene实现
  • Queries/filters执行的先后顺序及结果合并是怎样做的

ES2.x和5.x的数值类型分别是如何索引的

ES5.x之前用到的Lucene版本,实际上只能够索引文本类型的数据,表面上被定义为数值类型的字段,在暗地里都被转换成了字符串,编排成了倒排索引。例如:

Term Postings List
2 [doc3, doc5, doc10 ...]
5 [doc1, doc3, doc9 ... ]
... ...
90 [doc2, doc3, doc8 ...]
99 [doc3, doc5, doc20 ...]
... ...

这种结构对于精确的数值查询速度还是比较快的,直接从倒排索引根据查找的term拿到postings list就好了。 但类似range: [50, 100]这样的范围查找就比较麻烦了,Lucene在找到对应的term后,只能将其转换成类似50 OR 51 OR 52 ... OR 100这样的Bool查询。可想而知,这个多条件OR查询开销很高,执行很慢。所以Lucene在创建索引的时候,会自动产生一些类似50x75 这样的特殊Term,指向包含在该范围的文档列表,从而可以将查询优化成类似50x75 OR 76x99 OR 100 这种形式。但是这种优化在字段的不同值很多,查询范围很大的时候,依然很无力。 因此早期版本的Lucene和ES的范围查询性能一直被诟病。

Lucene从6.0开始引入了Block k-d tree来重新设计数值类型的索引结构,其目标是让数值型数据索引的结构更紧凑,搜索速度更快。这种数据结构是为多维数值字段设计的,可以高效的用于诸如地理位置这类数据的快速过滤,但同样适用于单维度的数值型。


Block k-d tree的基本概念和Lucene实现

基本思想就是将一个N维的数值空间,不断选定包含值最多的维度做2分切割,反复迭代,直到切分出来的空间单元(cell)包含的数据点数量小于某个数值。 对于单维度的数据,实际上就是简单的对所有值做一个排序,然后反复从中间做切分,生成一个类似于B-tree这样的结构。和传统的B-tree不同的是,他的叶子结点存储的不是单值,而是一组值的集合,也就是是所谓的一个Block。每个Block内部包含的值数量控制在512- 1024个,保证值的数量在block之间尽量均匀分布。 其数据结构大致看起来是这样的:

block b-tree.jpg

Lucene将这颗B-tree的非叶子结点部分放在内存里,而叶子结点紧紧相邻存放在磁盘上。当作range查询的时候,内存里的B-tree可以帮助快速定位到满足查询条件的叶子结点块在磁盘上的位置,之后对叶子结点块的读取几乎都是顺序的。

要注意一点,不是简单的将拿到的所有块合并就可以得到想要的docID结果集,因为查询的上下边界不一定刚好落在两端block的上下边界上。 所以如果需要拿到range filter的结果集,就要对于两端的block内的docid做扫描,将他们的值和range的上下边界做比较,挑选出match的docid集合。


Queries/filters执行的先后顺序及结果合并是怎样做的

ES的Queries/filters执行顺序比较复杂,并非按照Query里条件的排列顺序来挨个执行;也不是某些人想象的那样,每个filter/Query都独立执行,拿到各自的结果集以后,再做结果集的合并。 在elasticsearch-query-execution-order 这篇博客里对这个主题做了比较详细的介绍。

简单来说,ES会先通过调用每个查询的cost()函数估算一下该查询的代价,然后选择代价最小的查询作为起点,在其圈定的docid集合上生成一个迭代器。然后反复迭代,根据和其他条件之间是AND还是OR的关系,再去决定结果集合并的方式。

这个结果集的迭代,以及合并,就是上面链接里提到的nextdoc()advance()等操作。 比较复杂的地方是这些操作根据数据类型的不同和查询类型的不同,ES都有针对性的进行操作优化,同样的操作有些可能是在内存中进行,有些则可能直接在磁盘上进行。

以最常见的keyword字段做TermQuery为例,其cost就是Term Frequency,这个值可以直接从倒排索引读取。 Frequency越高的Term,其postings list就越长,迭代起来的代价就越高。 所以如果对多个TermQuery做AND合并,就会选择Frequency最低的Term,以其postings list为起点做迭代(nextdoc)。 Postings list是按照docid顺序存放的,并且在数据结构上还增加了跳表来加快advance()操作。因此多个postings list的合并可以直接操作磁盘上的数据而不会引起过多的随机IO,加上ES5.0以后对于索引数据采取了mmap file的方式访问,热数据读取引发的磁盘IO愈发的少。 这也是为什么5.1.1之后取消了TermQuery的cache,因为在跳表和OS page cache的加持下,直接合并磁盘上的postings list已经非常快了。 取消对其cache后,可以减少构造cache的开销,并且将宝贵的cache空间留给代价更高的filter,一定程度上可以提升ES整体性能。


有了这些预备知识,再来解答文首抛出的3个问题。

1. 为什么ES5.x里对数值型字段做TermQuery可能会很慢?

首先,用户范例查询里还有其他更加结果集更小的TermQuery,cost更低,因此迭代器从选择从这个低代价的Query作为起点开始执行; 其次,因为数值型字段在5.x里没有采用倒排表索引, 而是以value为序,将docid切分到不同的block里面。对应的,数值型字段的TermQuery被转换为了PointRangeQuery。这个Query利用Block k-d tree进行范围查找速度非常快,但是满足查询条件的docid集合在磁盘上并非向Postlings list那样按照docid顺序存放,也就无法实现postings list上借助跳表做蛙跳的操作。 要实现对docid集合的快速advance操作,只能将docid集合拿出来,做一些再处理。 这个处理过程在org.apache.lucene.search.PointRangeQuery#createWeight这个方法里可以读取到。 这里就不贴冗长的代码了,主要逻辑就是在创建scorer对象的时候,顺带先将满足查询条件的docid都选出来,然后构造成一个代表docid集合的bitset,这个过程和构造Query cache的过程非常类似。 之后advance操作,就是在这个bitset上完成的。

2. 为何Profile里显示的耗时几乎全部在build_scorer?

回答第一个问题的时候提到了,如果查看PointRangeQuery的源码,构造scorer对象的构造过程包含了bitset的生成过程,所以耗时的实际上是构造一个巨大的bitset并在上面生成一个迭代器。

3. 为什么对同样的数值型字段做RangeQuery却又很快了?

从上面数值型字段的Block k-d tree的特性可以看出,rangeQuery的结果集比较小的时候,其构造bitset的代价很低,不管是从他开始迭代做nextdoc(),或者从其他结果集开始迭代,对其做advance,都会比较快。 但是如果rangeQuery的结果集非常巨大,则构造bitset的过程会大大延缓scorer对象的构造过程,造成结果合并过程缓慢。
这个问题官方其实早已经意识到了,所以从ES5.4开始,引入了indexOrDocValuesQuery作为对RangeQuery的优化。(参考: better-query-planning-for-range-queries-in-elasticsearch)。 这个Query包装了上面的PointRangeQuerySortedSetDocValuesRangeQuery,并且会根据Rang查询的数据集大小,以及要做的合并操作类型,决定用哪种Query。 如果Range的代价小,可以用来引领合并过程,就走PointRangeQuery,直接构造bitset来进行迭代。 而如果range的代价高,构造bitset太慢,就使用SortedSetDocValuesRangeQuery。 这个Query利用了DocValues这种全局docID序,并包含每个docid对应value的数据结构来做文档的匹配。 当给定一个docid的时候,一次随机磁盘访问就可以定位到该id对应的value,从而可以判断该doc是否match。 因此它非常适合从其他查询条件得到的一个小结果集作为迭代起点,对于每个docid依次调用其内部的matches()函数判断匹配与否。也就是说, 5.4新增的indexOrDocValuesQuery将Range查询过程中的顺序访问任务扔给Block k-d Tree索引,将随机访任务交给doc values。 值得注意的是目前这个优化只针对RangeQuery!对于TermQuery,因为实际的复杂性,还未做类似的优化,也就导致对于数值型字段,Term和Range Query的性能差异极大。


小结:

  1. 在ES5.x里,一定要注意数值类型是否需要做范围查询,看似数值,但其实只用于Term或者Terms这类精确匹配的,应该定义为keyword类型。典型的例子就是索引web日志时常见的HTTP Status code。
  2. 如果RangeQuery的结果集很大,并且还需要和其他结果集更小的查询条件做AND的,应该升级到ES5.4+,该版本在底层引入的indexOrDocValuesQuery,可以极大提升该场景下RangeQuery的查询速度。

number?keyword?傻傻分不清楚

Elasticsearchkennywu76 发表了文章 • 6 个评论 • 2993 次浏览 • 2018-01-09 00:46 • 来自相关话题

【携程旅行网 吴晓刚】

上周,在某多多搬砖的一位朋友在微信上找我咨询,说他们公司一个ES集群从2.4升级到5.5以后,一个很简单的Query查询耗时突然从几十毫秒,变成800-1000毫秒,几十倍的性能下降!原始问题链接:# Why my search slow?

这个查询非常简单,就是3个过滤条件求并集而已:

{
      "from": 0,
      "size": 10,
      "query": {
      "bool": {
      "filter": [
        {
          "terms": {
            "goods_id": [
              "262628158"
            ],
            "boost": 1.0
          }
        },
        {
          "terms": {
            "status": [
              "2",
              "4"
            ],
            "boost": 1.0
          }
        },
        {
          "range": {
            "create_time": {
              "from": "1514027649",
              "to": "1514632449",
              "include_lower": true,
              "include_upper": true,
              "boost": 1.0
            }
          }
        }
      ],
      "disable_coord": false,
      "adjust_pure_negative": true,
      "boost": 1.0
    }
  },
  "sort": [
    {
      "create_time": {
        "order": "desc"
      }
    }
  ]
}

通过profile查看,发现耗时主要在status字段的build_scorer这个阶段。

对方同时提到,只要去掉"status":["2", "4"]这个查询条件,速度就会恢复正常。进一步询问后得知,查询的索引文档总量相当巨大,达到16亿条,而status字段只有几个不同的数字,在mapping里被定义为数值型short

我的第一反应,status只有几个值,意味着该字段的filter得到的结果集是海量的。可能是处理这个大结果集的代价很高造成的缓慢,但是具体什么原因我一时也说不上来。

脑子里开始翻查ES 2.x -> 5.x升级对于数值类型和Term Query有何重大变化?想起来两点:

  1. Lucene6.0引入了重新设计的数值类型的索引结构,不再采用倒排索,而是使用了更适合范围查找的Block K-d Tree。 ES从5.0开始引入这种新结构。(参考: searching-numb3rs-in-5.0
  2. Term Query由于通常非常快,从5.1.1开始不再被缓存到Query Cache

显然这个status字段不用于范围查找,字段类型设置上keyword比number更合理。 但我也没想明白为何number在这场景下查询会慢这么多,所以我也稍稍有些怀疑2.x缓存了Term Query是造成性能差异的原因。 当时让朋友做了个测试,将TermQuery换成RangeQuery,被告知速度飞快,只要几十个毫秒,并且多执行几次后更是快到只有几个毫秒了。(因为RangeQuery反复执行会被Cache起来)。

隔天,朋友根据建议将status先改为keyword,重新索引数据后,查询性能奇迹般的恢复到正常,所以基本可以确定和缓存无关了。

恰巧社区也有人在经历同样的问题: Elastic对类似枚举数据的搜索性能优化 ,看起来是个普遍现象,值得研究找出问题根源。

花了几天的时间参阅技术文档,也粗略读了一下ES/Lucene相关代码后,总算搞清楚了问题的来龙去脉。 本文将对相关技术细节做分析,然后回答下面3个问题:

  1. 为什么ES5.x里对数值型字段做TermQuery可能会很慢?
  2. 为何Profile里显示的耗时几乎全部在build_scorer?
  3. 为什么对同样的数值型字段做RangeQuery却又很快了?

为更好的理解这个问题,先谈一下几点预备知识:

  • ES2.x和5.x的数值类型分别是如何索引的
  • Block k-d tree的基本概念和Lucene实现
  • Queries/filters执行的先后顺序及结果合并是怎样做的

ES2.x和5.x的数值类型分别是如何索引的

ES5.x之前用到的Lucene版本,实际上只能够索引文本类型的数据,表面上被定义为数值类型的字段,在暗地里都被转换成了字符串,编排成了倒排索引。例如:

Term Postings List
2 [doc3, doc5, doc10 ...]
5 [doc1, doc3, doc9 ... ]
... ...
90 [doc2, doc3, doc8 ...]
99 [doc3, doc5, doc20 ...]
... ...

这种结构对于精确的数值查询速度还是比较快的,直接从倒排索引根据查找的term拿到postings list就好了。 但类似range: [50, 100]这样的范围查找就比较麻烦了,Lucene在找到对应的term后,只能将其转换成类似50 OR 51 OR 52 ... OR 100这样的Bool查询。可想而知,这个多条件OR查询开销很高,执行很慢。所以Lucene在创建索引的时候,会自动产生一些类似50x75 这样的特殊Term,指向包含在该范围的文档列表,从而可以将查询优化成类似50x75 OR 76x99 OR 100 这种形式。但是这种优化在字段的不同值很多,查询范围很大的时候,依然很无力。 因此早期版本的Lucene和ES的范围查询性能一直被诟病。

Lucene从6.0开始引入了Block k-d tree来重新设计数值类型的索引结构,其目标是让数值型数据索引的结构更紧凑,搜索速度更快。这种数据结构是为多维数值字段设计的,可以高效的用于诸如地理位置这类数据的快速过滤,但同样适用于单维度的数值型。


Block k-d tree的基本概念和Lucene实现

基本思想就是将一个N维的数值空间,不断选定包含值最多的维度做2分切割,反复迭代,直到切分出来的空间单元(cell)包含的数据点数量小于某个数值。 对于单维度的数据,实际上就是简单的对所有值做一个排序,然后反复从中间做切分,生成一个类似于B-tree这样的结构。和传统的B-tree不同的是,他的叶子结点存储的不是单值,而是一组值的集合,也就是是所谓的一个Block。每个Block内部包含的值数量控制在512- 1024个,保证值的数量在block之间尽量均匀分布。 其数据结构大致看起来是这样的:

block b-tree.jpg

Lucene将这颗B-tree的非叶子结点部分放在内存里,而叶子结点紧紧相邻存放在磁盘上。当作range查询的时候,内存里的B-tree可以帮助快速定位到满足查询条件的叶子结点块在磁盘上的位置,之后对叶子结点块的读取几乎都是顺序的。

要注意一点,不是简单的将拿到的所有块合并就可以得到想要的docID结果集,因为查询的上下边界不一定刚好落在两端block的上下边界上。 所以如果需要拿到range filter的结果集,就要对于两端的block内的docid做扫描,将他们的值和range的上下边界做比较,挑选出match的docid集合。


Queries/filters执行的先后顺序及结果合并是怎样做的

ES的Queries/filters执行顺序比较复杂,并非按照Query里条件的排列顺序来挨个执行;也不是某些人想象的那样,每个filter/Query都独立执行,拿到各自的结果集以后,再做结果集的合并。 在elasticsearch-query-execution-order 这篇博客里对这个主题做了比较详细的介绍。

简单来说,ES会先通过调用每个查询的cost()函数估算一下该查询的代价,然后选择代价最小的查询作为起点,在其圈定的docid集合上生成一个迭代器。然后反复迭代,根据和其他条件之间是AND还是OR的关系,再去决定结果集合并的方式。

这个结果集的迭代,以及合并,就是上面链接里提到的nextdoc()advance()等操作。 比较复杂的地方是这些操作根据数据类型的不同和查询类型的不同,ES都有针对性的进行操作优化,同样的操作有些可能是在内存中进行,有些则可能直接在磁盘上进行。

以最常见的keyword字段做TermQuery为例,其cost就是Term Frequency,这个值可以直接从倒排索引读取。 Frequency越高的Term,其postings list就越长,迭代起来的代价就越高。 所以如果对多个TermQuery做AND合并,就会选择Frequency最低的Term,以其postings list为起点做迭代(nextdoc)。 Postings list是按照docid顺序存放的,并且在数据结构上还增加了跳表来加快advance()操作。因此多个postings list的合并可以直接操作磁盘上的数据而不会引起过多的随机IO,加上ES5.0以后对于索引数据采取了mmap file的方式访问,热数据读取引发的磁盘IO愈发的少。 这也是为什么5.1.1之后取消了TermQuery的cache,因为在跳表和OS page cache的加持下,直接合并磁盘上的postings list已经非常快了。 取消对其cache后,可以减少构造cache的开销,并且将宝贵的cache空间留给代价更高的filter,一定程度上可以提升ES整体性能。


有了这些预备知识,再来解答文首抛出的3个问题。

1. 为什么ES5.x里对数值型字段做TermQuery可能会很慢?

首先,用户范例查询里还有其他更加结果集更小的TermQuery,cost更低,因此迭代器从选择从这个低代价的Query作为起点开始执行; 其次,因为数值型字段在5.x里没有采用倒排表索引, 而是以value为序,将docid切分到不同的block里面。对应的,数值型字段的TermQuery被转换为了PointRangeQuery。这个Query利用Block k-d tree进行范围查找速度非常快,但是满足查询条件的docid集合在磁盘上并非向Postlings list那样按照docid顺序存放,也就无法实现postings list上借助跳表做蛙跳的操作。 要实现对docid集合的快速advance操作,只能将docid集合拿出来,做一些再处理。 这个处理过程在org.apache.lucene.search.PointRangeQuery#createWeight这个方法里可以读取到。 这里就不贴冗长的代码了,主要逻辑就是在创建scorer对象的时候,顺带先将满足查询条件的docid都选出来,然后构造成一个代表docid集合的bitset,这个过程和构造Query cache的过程非常类似。 之后advance操作,就是在这个bitset上完成的。

2. 为何Profile里显示的耗时几乎全部在build_scorer?

回答第一个问题的时候提到了,如果查看PointRangeQuery的源码,构造scorer对象的构造过程包含了bitset的生成过程,所以耗时的实际上是构造一个巨大的bitset并在上面生成一个迭代器。

3. 为什么对同样的数值型字段做RangeQuery却又很快了?

从上面数值型字段的Block k-d tree的特性可以看出,rangeQuery的结果集比较小的时候,其构造bitset的代价很低,不管是从他开始迭代做nextdoc(),或者从其他结果集开始迭代,对其做advance,都会比较快。 但是如果rangeQuery的结果集非常巨大,则构造bitset的过程会大大延缓scorer对象的构造过程,造成结果合并过程缓慢。
这个问题官方其实早已经意识到了,所以从ES5.4开始,引入了indexOrDocValuesQuery作为对RangeQuery的优化。(参考: better-query-planning-for-range-queries-in-elasticsearch)。 这个Query包装了上面的PointRangeQuerySortedSetDocValuesRangeQuery,并且会根据Rang查询的数据集大小,以及要做的合并操作类型,决定用哪种Query。 如果Range的代价小,可以用来引领合并过程,就走PointRangeQuery,直接构造bitset来进行迭代。 而如果range的代价高,构造bitset太慢,就使用SortedSetDocValuesRangeQuery。 这个Query利用了DocValues这种全局docID序,并包含每个docid对应value的数据结构来做文档的匹配。 当给定一个docid的时候,一次随机磁盘访问就可以定位到该id对应的value,从而可以判断该doc是否match。 因此它非常适合从其他查询条件得到的一个小结果集作为迭代起点,对于每个docid依次调用其内部的matches()函数判断匹配与否。也就是说, 5.4新增的indexOrDocValuesQuery将Range查询过程中的顺序访问任务扔给Block k-d Tree索引,将随机访任务交给doc values。 值得注意的是目前这个优化只针对RangeQuery!对于TermQuery,因为实际的复杂性,还未做类似的优化,也就导致对于数值型字段,Term和Range Query的性能差异极大。


小结:

  1. 在ES5.x里,一定要注意数值类型是否需要做范围查询,看似数值,但其实只用于Term或者Terms这类精确匹配的,应该定义为keyword类型。典型的例子就是索引web日志时常见的HTTP Status code。
  2. 如果RangeQuery的结果集很大,并且还需要和其他结果集更小的查询条件做AND的,应该升级到ES5.4+,该版本在底层引入的indexOrDocValuesQuery,可以极大提升该场景下RangeQuery的查询速度。