当前位置: 首页 > 科技观察

为什么ElasticSearch使用倒排索引?

时间:2023-03-15 09:12:10 科技观察

【.com原稿】一提到ES,大家就会想到它的倒排索引。很多人都知道ES因为有倒排索引所以可以快速查询。图片来自宝途网但ES只有倒排索引吗?ES有前向索引吗?大量的ES数据放在内存中。它有什么优化策略吗?倒排索引和正向索引是为了防止有些同学不知道倒排索引,我们简单介绍一下正向索引和倒排索引。所谓正向索引很简单,就是一种更适合我们人脑记忆的数据结构。比如背古诗,当有人问我们这首诗《静夜思》时,我们可以很轻松的背出完整的诗句。但是如果有人问我们哪首诗里有爽字,我们很难想到《静夜思》这首诗。因为我们的大脑在背诵古诗词的时候会建立一个积极的指数。静夜思→窗前月光,疑是地上霜,抬头看明月,低头思故乡。倒排索引与这种数据结构相反。有一种游戏从古至今流传至今,叫做《飞花令》。规则是能说出含有“花”的诗句,谁说得多谁赢。能够在这样的比赛中取胜,关键就看谁能在脑海中建立起花的倒排索引。举个例子:总结一下,这就是倒排索引,但是ES的倒排索引更加复杂。为了计算分数,ES会添加一些关于term的统计信息。DocValues①为什么需要docvalues分析?ES中的倒排索引如下。假设有3个文档,每个文档都有一个字段。那么三个文档如下:那么根据名字建立的倒排索引如下图所示:现在,假设我们要做这样一个查询:查询名字中包含brown的文档,并对其进行排序按年龄。查询分析:因为我们有name的倒排索引,所以我们直接看上面的倒排索引可以很快知道命中的倒排索引是Doc_1和Doc_2。之后需要按照年龄排序,请问有什么办法吗?首先回想一下,我们需要什么才能进行排序?很简单,我们需要知道待排序文档的每个文档的文档id及其对应的age。也就是说,我们需要有doc_id→age这样的映射关系,那么问题就转化了。怎么才能得到这个映射关系呢?方法一共有三种:方法一:在上面的查询中,我们过滤掉了待排序的文档是Doc_1和Doc_2,那么我们就可以访问磁盘来检索这两个文档的数据,这样就可以建立映射关系了doc_id→年龄。缺点:例子中我们只命中了两个文档,但是在实际业务场景中,我们可能会命中很多文档。比如我们查询的文档是中国14亿人口,按性别筛选,然后按年龄排序,那么我们要检索的文档数量会达到7亿文档,那么检索的数据量就太大了。而且,可以想象,要检索的文档属于随机IO。在这种情况下,这种方案对IO、CPU、内存的压力都很大,响应时间更是难以想象。结合方法一的缺点,我们发现访问源数据是很不友好的,那么如果我们不需要访问源数据,使用已有的资源怎么办呢?方法二:读取已有的倒排索引,利用倒排索引Index建立doc_id→age的映射关系。根据倒排索引的数据结构,我们的操作变为:遍历整个倒排索引的所有term,从而建立完整的doc_id→age映射关系。缺点:每次排序都需要遍历倒排索引。倒排索引项少的时候还好,倒排索引项多的时候速度会变慢。并且每次根据不同的查询条件,我们建立的doc_id→age的映射关系是不同的。我们需要查询遍历一次,建立映射关系。总之,缺点是:建立映射比较麻烦,复用性不高。在方法2的基础上进一步分析,我们希望更快的获取doc_id→age的映射关系,并在查询时复用。对于doc_id→age的映射关系,我们必须要建立起来。既然这一步是必不可少的,那我们能不能分解这一步呢?也就是分解成文档插入的时候(官方文档中,文档插入描述为文档被索引,笔者看了很多官方文档,其实是用来描述为被索引,但这里说是被插入,以免被误解),它是和倒排索引一起创建的。方法三:在插入文档时建立doc_id→age映射关系。当需要排序和聚合时,我们只需要直接读取即可。以上分析引出ES的doc值,世人称之为positiveindex。②深入理解Docvalues经过一番啰嗦的分析,终于引出了docvalues,下面让我们对docvalues有更深入的了解。(1)生成时机:插入文档时与倒排索引同时生成。(2)数据结构:docvalues其实就是倒排索引的转置。大致结构如下:(3)存储位置:磁盘。(4)docvalues以什么粒度生成:基于每个segment(ES索引数据在每个segment中一个一个地划分成segment,每个segment最多可以存储2^31-1个documents)生成独立的,并且像倒排索引和段一样是不可变的(为什么不可变以及它如何响应文档变化是一个很长很长的故事,敬请期待)。(5)默认是开启的,所以我们不用管,但是如果我们很清楚某个字段不会用于排序和聚合,我们可以在创建的时候关闭docvalues来节省资源。(6)使用方法:读回记忆。(7)不适用于文本类型的字段。这里插入doc_id的意思是文档存放在segment中,一个segment在doc数组中。doc_id指的是每个文档在segment中的索引,并不是很多人认为的_id。那么,结束了吗?这不,有意想不到的事情。对于特性5和6,ES做了一些其他的努力,使查询速度更快,资源消耗更少,并防止ES节点因OOM问题而看到Max。看上面的第5点。从docvalues读取的数据放在内存中。这个内存是申请内存还是系统内存?答案是系统内存,因为可以充分利用操作系统的虚拟内存技术,也就是说,doc值是放在内存中的,并不由JVM管理。当系统内存足够时,会放到系统内存中。当系统内存不足时,利用操作系统的虚拟存储技术与docvalues文件建立映射关系,只在内存中读取部分docvalues数据。根据内存的淘汰策略进行读入和淘汰。这也引出了ES官方关于ES节点内存分配策略的一个规划:另外,为了读写速度更快,有没有办法让docvalues占用的内存更小?这是ESup的众多数据压缩方式之一。查看上面docvalues的数据示例,我们发现示例中对应的term是数字,最小的数字是100,最大的是4200。为了存储这些数字,我们需要多少内存空间为每个号码分配?为了容纳4200,因为2^12<4200<2^13,我们需要为每个term分配至少13位的空间,example一共有7个doc,至少需要7*13=91位。有没有什么办法,在这种情况下,ES的压缩方法是:找到这些数的最大公约数为100,然后将这些数除以它们的最大公约数。结果如下:在此之后,数据范围变为1-42。为了存储42,我们需要2^5<42<2^6。换句话说,我们只需要6位来存储每个数字。最后存储7个数需要6*7=42bit,压缩了一倍。这是ES对doc值的数据压缩方式之一。数字的总压缩方式是:那么另一个问题来了:上面介绍的压缩方式都是数字的,但是如果我的项目是字符串文本呢??我们不能将字符串转换为数字吗?看官网的解释:FieldData写到这里为止,让我们回忆一下doc值的特性6:不适用于文本数据类型。那么,如果文本类型的文本字段需要排序或者聚合,应该如何调整呢?于是就有了一个新东西:fielddata。Fielddata的数据结构可以理解为文本类型字段的正向索引结构,解决了doc值不支持多值字符串的问题。除此之外,它还有其他的区别:内存管理和生成,常驻内存:fielddata不同于docvalues,它的生成和管理是在内存中生成的,一般不会释放,因为构建它的成本非常昂贵,所以我们使其永久化。占用内存较多:分析textfield中的数据,生成fielddata的过程中会产生很多term,会占用大量内存Lazyloading:第一次聚合前开启了fielddata:true的字段isFielddata不会生成。满载:这里有一个惊喜。假设您的查询是高度选择性的并且只返回100次匹配。大多数人认为fielddata只加载100个文档。实际发生的是fielddata加载索引中的所有文档(针对该特定字段),而不管查询的特殊性。逻辑是这样的:如果一个查询访问文档X、Y和Z,很有可能在下一个查询中访问其他文档。和docvalues一样,倒排索引是基于段而不是整个索引来构建的。默认情况下禁用。如果启用,则需要手动启用。使用字段数据:true。基于上面的前两个特点,衍生出以下问题:慢生成和占用空间问题1解决方法:对于慢生成,会导致这样的问题:第一次查询使用某个字段的fielddata,速度会会很慢,如果对于这个点不能忍受,可以预加载那个字段的fielddata。只需在field的mappings下添加如下内容即可:问题2解决方案:除了数据压缩之外,为了放置我们的ES因为loading过多的fielddata而OOMcrash。我们需要对fielddata的数据做一些限制:indices.fielddata.cache.size:限制fielddata使用的空间,控制分配给fielddata的堆空间大小。当fielddata占用的内存大小超过这个限制时,就会触发fielddata的内存回收,回收策略LRU。可以是20%的百分比或5gb的特定值;使用此设置,最近最少使用的(LRU)字段数据将被回收以为新数据腾出空间。indices.breaker.fielddata.limit:fielddata内存使用断路器,断路器默认以heap的60%作为fielddata大小的上限。超过此限制将触发异常。当我们用完内存indices.breaker.request.limit:请求断路器估计需要完成请求的其他部分的结构的大小,例如创建聚合桶。默认限制是堆内存的40%。indices.breaker.total.limit:total结合了request和fielddata断路器,保证两者结合不会使用超过70%的堆内存。注意:indices.fielddata.cache.size和indices.breaker.fielddata.limit之间的关系非常重要。如果断路器的限制低于缓存大小,则不会驱逐任何数据。为了正常工作,断路器的限制必须高于缓存大小。Fielddata过滤:另外还有一种方案可以减少fielddata的数据大小,即数据过滤,过滤掉不需要放入fielddata的数据。比如我们把1,000,000首歌曲按照标签分组,取前10名,那么摇滚、嘻哈、流行之类的就会排在第一位,还会有一些标签,比如“超过20分钟”.这样的小众标签是很难被查询和聚合的。那么这部分数据可以不用加载fielddata就可以保存下来。甚至可以说,很多数据可能是符合正态分布的。通常只有一小部分数据用于聚合,而许多其他数据与极少数文档相关联。过滤是这样工作的:fielddata关键字允许我们配置fielddata如何处理该字段。频率过滤器允许我们根据项目频率过滤加载的字段数据。仅加载出现在本段文档中至少1%的那些项目。任何少于500个文档的段都将被忽略。太小的段中关键词比例失衡。PUT/music/_mapping/song{"properties":{"tag":{"type":"string","fielddata":{(1)"filter":{"frequency":{(2)"min":0.01,(3)"min_segment_size":500(4)}}}}}}全局序号介绍完docvalues和fielddata后,我们再介绍一个更快的docvalues和fielddata在ESMeans中的使用;全球序列号。什么是全球序列号?为什么需要全球序列号?有一个10亿文档的索引,每个文档都有一个字段status,这个status只有3个枚举值TOEXCURE、EXCUTING、FINISHED。为了方便,我设置的3个枚举值都是8个字符。那么当我们直接存储这三个枚举值的时候,需要用到8byte*10亿的空间,如果我们对它们使用序号,012来引用,我们可以用1bit来存储每个枚举值。TOEXCURE->0EXCUTING->1FINISHED->2只需要用到1/8字节*10亿。压缩比:只需要原来存储空间的1/64,真是小聪明。但是,我们知道fielddata和doc值是基于每个segment建立的,所以有些segment可能有TOEXCUTE和FINISHED两个枚举值,用0和1映射。有些segment有EXCUTING+FINISHED两个枚举值,在该段中也映射为0和1,这可能会导致问题。我们用来替换它们的序列号必须是全球唯一的。这个东西叫做全球序列号。如何获取全球序列号?方法如下:方法一:读取所有段,进行聚合操作,返回所有枚举值,然后生成全局序号。缺点:对所有段的所有数据项进行操作,耗时、耗内存、CPU密集。方法二:通过fielddata和docvalues进行构造----ES的方案完全一样。特点:构建和刷新全局序号的时机:添加或删除段时,需要重建全局序号,添加或删除段需要重建,因为枚举值可能发生变化,重建需要读取每个段对于段的每个唯一项,基数越高(即存在的唯一项越多),这个过程就会越长。与字段数据加载一样,全局序数默认情况下是延迟构建的。总结本文主要分析ES为了应对排序和聚合场景,对于未分析的字段(非文本)使用doc值,对于text文本字段使用fielddata。重点主要是为什么要使用这两种技术,使用这两种技术时需要做什么,会导致什么问题,ES为了避免这些问题做了哪些权衡和优化。在使用ES的时候,我们只需要知道,为了更快的排序和聚合,我们需要为分析字段开启docvalues(默认开启),对于text类型的分析字段我们需要开启fielddata。但是我们应该知道它并且知道为什么。只有这样,我们才能从知识的学习中感受到快乐。探索未知,认识世界,你我共勉。作者:JackHu简介:水滴健康基础设施高级技术专家编辑:陶佳龙征稿:有意投稿或寻求报告,请联系editor@51cto.com【原创稿件请注明原作者及来源为.com]