ES的索引结构与算法解析

es,索引,结构,算法,解析 · 浏览次数 : 262

小编点评

**1. 原数组分词的难点** 在处理海量数据时,原数组的分词会占用大量空间,甚至超过数组的存储空间。因此,在进行分词之前,需要考虑如何降低空间占用。 **2. RBM算法的应用** RBM算法可以有效地降低原数组的分词空间。通过使用RBM算法,可以将原数组的元素分割成多个更小的空间,从而减少原数组的分词空间。 **3. 稀疏数组的处理** 当数据量小的时候,稀疏的数组会占用比直接存储更大的空间。因此,在进行数据处理时,需要考虑如何降低稀疏数组的分词空间。 **4. RBM算法的优缺点** RBM算法的优点是可以有效地降低原数组的分词空间,但是其缺点是当数据量小的时候,稀疏数组的分词效率会下降。 **5. RBM算法的应用场景** RBM算法可以应用于各种数据处理场景,例如: * 在索引中存储连续数字的数组 * 在倒排表中存储索引值 * 在数据压缩中降低数据的压缩效率 **6. 总结** RBM算法是一种在处理海量数据时降低原数组分词空间的方法。通过使用RBM算法,可以有效地降低原数组的分词空间,并降低稀疏数组的分词效率。

正文

作者:京东物流 李洪吉

提到ES,大多数爱好者想到的都是搜索引擎,但是明确一点,ES不等同于搜索引擎。不管是谷歌、百度、必应、搜狗为代表的自然语言处理(NLP)、爬虫、网页处理、大数据处理的全文搜索引擎,还是有明确搜索目的的搜索行为,如各大电商网站、OA、站内搜索、视频网站的垂直搜索引擎,他们或多或少都使用到了ES。

​作为搜索引擎的一部分,ES自然具有速度快、结果准确、结果丰富等特点,那么ES是如何达到“搜索引擎”级别的查询效率呢?首先是索引,其次是压缩算法,接下来我们就一起了解下ES的索引结构和压缩算法

1 结构

1.1 Mysql

Mysql下的data目录存放的文件就是mysql相关数据,mysql文件夹对应的就是数据库mysql。

其中表columns_priv对应了3个文件:columns_priv.frm、columns_priv.MYD、columns_priv.MYI。

.frm:表结构;.MYD:myisam存储引擎原数据;.MYI:myisam存储引擎索引;.ibd:innodb存储引擎数据

1.2 Elasticsearch

cfe为索引文,cfs 为数据文件,cfe文件保存Lucene各文件在.cfs文件的位置信息

cfs、cfe 在segment还很小的时候,将segment的所有文件都存在在cfs中,在cfs逐渐变大时,大小超过shard的10%,则会拆分为其他文件,如tim、dvd、fdt等文件

1.3 存储结构

倒排索引结构分为倒排表、词项字典、词项索引

倒排表包含某个词项的所有id的数据存储了在.doc文件中

词项字典包含了index field的所有经过处理之后的词项数据,最终存储在.tim文件中

1.4 结构对比

我们以某商城的手机为例,左侧为es倒排索引结构,右侧为原始数据。左侧图示只是为了展示倒排索引结构,并不是说es中倒排表就是简单的数组

以上面结构对比示例图为例,假如共有10亿条数据需要存储在ES中(上图右),分词后存储的倒排表(上图左)大概包含分词term以及对应的id数组等,在10亿条数据中,分词“小米”相关的数据有100万条,也就是说分词“小米”对应的数组Posting List长度是100万

id是int类型的有序主键,分词“小米”在数组Posting List中100万int类型数字总长度=100万✖每个int占4字节=400万Byte≈4MB。1个分词占4MB空间,假如10亿条数据有500万个分词,总空间=4MB✖500万=2千万MB,磁盘空间直接爆炸

2 算法

分词对应的数组Posting List实际就是一个个有序数组,而有序数值数组是比较容易进行压缩处理的,而且一般来说压缩效益也不错,如果能对其进行压缩是能够大大节约空间资源的

ES中倒排索引的压缩算法主要有FOR算法(Frame Of Reference)和RBM算法(RoaringBitMap)

2.1 FOR

FOR算法的核心思想是用减法来削减数值大小,从而达到降低空间存储。 假设V(n)表示数组中第n个字段的值,那么经过FOR算法压缩的数值V(n)=V(n)-V(n-1)。也就是说存储的是后一位减去前一位的差值。存储是也不再按照int来计算了,而是看这个数组的最大值需要占用多少bit来计算

我们按照差值计算的方式来保存数据,初始值为1,2与1的差值为1,3与2的差值为1……最终我们就将原始Posting List数据转化为100万个1,每个1我们可以用1bit来记录,总空间=1bit✖100万=100万bit,相比原有400万Byte=3200bit,空间压缩了32倍

在实际生产中,不可能出现一个term的Posting List是这种差值均为1的情况,所以我们以通用示例举例。假如原数据为[73,300,302,332,343,372],数组中6个数字占据总空间为24字节。按照差值方式记录,数组转化为[73,227,2,30,11,29],最大数字为227,大于2的7次方128,小于2的8次方256,所以每个数字可以使用8bit即1Byte来保存,占据总空间为1Byte*6 + 1Byte=7Byte

在此基础上,我们将差值数组按照密集度划分为[73,227]和[2,30,11,29],其中[73,227]中最大值227介于2的7次方和2的8次方之间,所以用8bit=1Byte作为切割分段,[2,30,11,29]中最大数30介于2的4次方和2的5次方之间,所以用5bit作为切割分段。

数组[73,227]占据总空间为8bit✖2个=16bit=2Byte

数组[2,30,11,29]占据总空间为5bit✖4个=20bit=3Byte

为什么20bit=3Byte呢?因为8bit=1Byte,小于8bit也会占据1个字节空间,所以17bit到24bit均为3Byte

所以,最终占据总空间=1+2+1+3=7Byte

疑问一:既然原数组[73,300,302,332,343,372]要按照密集度拆分为[73,227]和[2,30,11,29]两个数组,那为什么不继续往下拆分,直接拆分到每个数字是一个数组,这样使用bit记录时占据总空间会更少?

答:如果继续拆分数组,空间确实会使用更少,但是,之前我们提到搜索引擎速度快的方式有两种:高效的压缩算法和快速的编码解码速度,单个数字存储确实压缩了空间,但是我们无法再通过解码的方式将源数据还原

疑问二:为什么源数据使用差值记录占据6Byte,拆分数组后占据7Byte,拆分后占据空间不变,有时候甚至会变大,为什么?

答:数据量小的情况下确实会出现该情况,因为我们需要拆分数组并记录拆分数组的长度(如上面示例中的8bit和5bit),在原数据存储空间基础上还要存储拆分长度,所以数据量小的情况下会出现比直接存储占据空间大的情况。但是不管是搜索引擎还是Elasticsearch更多处理的是海量数据,数据量越多,差值数组拆分的方式节省空间越明显

2.2 RBM

我们已经了解了FOR压缩算法,算法核心是将PostingList按照差值密集度转化成两个差值数组。在这里我们要考虑一种情况就是:在大数据中,10亿条数据分词500万个,如果分词“小米”所在PostList比较分散且差值很大,此时使用FOR算法效果就会大打折扣。所以稀疏的数组,不适合使用FOR算法

在这里我们以[1000,62101,131385,132052,191173,196658]为例,如果按照FOR算法,转化成的差值数组为[1000,61101,69284,667,59121,5485]密集度很低。我们采用RBM算法

源数据PostingList是由int类型组成的数组,int类型=4Byte=32bit,最大值=2的32次方-1=4294967295≈43亿。当数据较大且稀疏时,我们将32bit拆分为16bit和16bit,16bit最大值=65535,前16bit存放,后16bit存放余数,所以商和余数都不会超过65535.我们将源数组的值除以65536,得到的商和余数分别存放在前16bit和后16bit。

以数字196658为例,转化为2进制,前16位=3,后16位=50

得到的结果以K-V存放。Key最大值为16bit,所以以short[]数组存放,Value以Container存放。

由于源数组为有序数组,所以按照高低16位转化后,商和余数都是从小到大排列

通过看Container源码,我们可以看到Container有3种:ArrayContainer、BitmapContainer、RunContainer。

  1. ArrayContainer本质为集合,所以随着数组中数量越多,占用空间越多,呈正向增长。

当数组种数量为4096时,占据总空间=4096个✖16bit(即2Byte)➗1024=8KB

当数组种数量为65536时,占据总空间=65536个✖16bit(即2Byte)➗1024=128KB

  1. BitmapContainer位图,核心就是将原有存储数值转化成该数值在哪个位置上存在

由于余数最大值为65535,所以我们需要65536位位图,数值是多少,在位图上对应的位置就是多少。数值等于4096,则位图上4096位值为1;数值等于65535,则位图上65535位值为1。每个位置上的数都占用8KB空间(8KB=65536bit)

  • RunContainer用法相对狭隘,这种类型是Lucene 5之后新增的类型,主要应用在连续数字的存储商,比如倒排表中存储的数组为 [1,2,3…100W] 这样的连续数组,如果使用RunContainer,只需存储开头和结尾两个数字:1和100W,即占用8个字节。这种存储方式的优缺点都很明显,它严重收到数字连续性的影响,连续的数字越多,它存储的效率就越高
  • 如果数组是如下形式 [1,2,3,4,5,100,101,102,999,1000,1001] 就会被拆分为三段:[1,5],[100,102],[999,1001]

至于每次存储采用什么容器,需要进行一下判定,比如ArrayContainer,当存储的元素少于4096个时,他会比BitmapContainer占用更少空间,而当大于4096个元素时,采用ArrayContainer所需要的空间就会大于8kb,那么采用BitmapContainer就会占用更少空间

3 总结

ES在处理海量数据时通过其独到的结构和压缩算法,将索引效率尽可能的提升。虽然在实际业务处理中我们极少遇到海量数据处理的情况,但是通过了解ES的原理,能够帮我们开阔下视野,了解数字之美,算法之美。

与ES的索引结构与算法解析相似的内容:

ES的索引结构与算法解析

作为搜索引擎的一部分,ES自然具有速度快、结果准确、结果丰富等特点,那么ES是如何达到“搜索引擎”级别的查询效率呢?首先是索引,其次是压缩算法,接下来我们就一起了解下ES的索引结构和压缩算法

深入了解Elasticsearch搜索引擎篇:倒排索引、架构设计与优化策略

首先,我们介绍了Elasticsearch(ES)的倒排索引,这是一种用于快速检索的数据结构。其次,我们了解了ES集群的架构,包括主节点、数据节点和协调节点的功能和作用。然后,我们探讨了中文分词器的选择,其中包括IK、HanLP和Jieba等常用的分词工具。接着,我们解释了写入数据和查询数据的工作原理,包括请求的分配和预处理,数据的存储和查询结果的处理过程。最后,我们讨论了ES部署的优化方法,包括调整JVM内存、分片布局和数量、节点身份设计以及配置Ingest节点等方面的策略。

ElasticSearch 实现分词全文检索 - Java SpringBoot ES 索引操作

//1. 准备索引的 settings Settings.Builder settings = Settings.builder() //2. 准备索引的结构 Mappings XContentBuilder mappings = JsonXContent.contentBuilder() //3. 将 Settings 和 Mappings 封装到一个Request 对象中

[转帖]Elasticsearch 技术分析(七): Elasticsearch 的性能优化

https://www.cnblogs.com/jajian/p/10176604.html 硬件选择# Elasticsearch(后文简称 ES)的基础是 Lucene,所有的索引和文档数据是存储在本地的磁盘中,具体的路径可在 ES 的配置文件../config/elasticsearch.ym

Elasticsearch如何聚合查询多个统计值,如何嵌套聚合?并相互引用,统计索引中某一个字段的空值率?语法是怎么样的?

Elasticsearch聚合查询是一种强大的工具,允许我们对索引中的数据进行复杂的统计分析和计算。本文将详细解释一个聚合查询示例,该查询用于统计满足特定条件的文档数量,并计算其占总文档数量的百分比。这里回会分享如何统计某个字段的空值率,然后扩展介绍ES的一些基础知识。

es mysql 适用场景对比

# es mysql 适用场景对比 ## 问题一 ### 全文检索毫无疑问直接上es,那么除了这种场景,什么时候该选es?为啥mysql不行? #### 对枚举字段的搜索 mysql创建索引的原则是对于那些区别度高字段建立索引,区别度越高的索引,在数据量大的情况下,索引效果越好。 因为mysql建立

es针对nested类型数据无法进行过滤查询的问题记录

问题描述 es中存在有一个名为task_data_1的索引,其字段映射关系如下所示: { "task_data_1" : { "mappings" : { "dynamic_templates" : [ { "dates" : { "match_mapping_type" : "date", "ma

[转帖]Elasticsearch 的 30 个调优最佳实践!

Elasticsearch 的 30 个调优最佳实践! https://zhuanlan.zhihu.com/p/406264041 ES 发布时带有的默认值,可为 es 的开箱即用带来很好的体验。全文搜索、高亮、聚合、索引文档 等功能无需用户修改即可使用,当你更清楚的知道你想如何使用 es 后,你

ElasticSearch 实现分词全文检索 - SpringBoot 完整实现 Demo 附源码【完结篇】

搜素关键字自动补全(suggest),分词全文搜索 系统初始化,ElasticSearch ES 创建索引(EsIndexTest.createIndexTest) 模拟后台管理员,在添加文章时,将要检查的字段内容,同步到ES中(EsIndexTest.addArticleTest) 模拟用户搜索,在搜索框中查关键词“人工”(EsIndexTest.earchTest)

聊聊ElasticeSearch并发写的乐观锁机制

### 概述 ES的多客户端并发更新是基于乐观并发控制,通过版本号机制来实现冲突检测。 ### 关键对象 ES的老版本是用过`_version`字段的版本号实现乐观锁的。现在新版增加了基于`_seq_no`与`_primary_term`字段,三个字段做乐观锁并发控制。 ![image](https