【Elacticsearch】原理/数据结构/面试经典问题整理-Toy模板网

这篇具有很好参考价值的文章主要介绍了【Elacticsearch】原理/数据结构/面试经典问题整理。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

对Elacticsearch 原理/数据结构/面试经典问题整理的文章；

映射 | Elasticsearch: 权威指南 | Elastic

Elacticsearch介绍

原理

建立索引原理

查询索引原理

更新索引原理

删除索引原理

分片&副本机制，集群发现选举机制，负载机制，容错机制，扩容机制

数据类型

数据结构

先介绍倒排索引的组成部：倒排索引组成三部分

term dictionary

posting list

term index

Translog/FST/FOR/RBM算法

ES面试问题收集（持续更新）

Elacticsearch介绍

Elasticsearch,这里简称ES。ES是一个开源的高可用高扩展的分布式全文搜索与分析引擎，可以提供PB级近实时的数据存储和检索能力，底层基于Lucene作为其核心处理组件并在此之上进行封装提供了多语言API以及Resutful API来隐藏Lucene的复杂性，是目前最流行的企业级搜索引擎；是一个分布式、Restful的搜索及分析引擎，设计用于分布式计算；能够达到实时搜索，稳定，可靠，快速。和Apache Solr一样，它也是基于Lucence的索引服务器，而ElasticSearch对比Solr的优点在于：

轻量级：安装启动方便，下载文件之后一条命令就可以启动。
Schema free：可以向服务器提交任意结构的JSON对象，Solr中使用schema.xml指定了索引结构。
多索引文件支持：使用不同的index参数就能创建另一个索引文件，Solr中需要另行配置。
分布式：Solr Cloud的配置比较复杂。

整体架构：

关键概念：

一、索引(Index)
ES将数据存储于一个或多个索引中，索引是具有类似特性的文档的集合。类比传统的关系型数据库领域来说，索引相当于SQL中的一个数据库，或者一个数据存储方案(schema)。索引由其名称(必须为全小写字符)进行标识，并通过引用此名称完成文档的创建、搜索、更新及删除操作。一个ES集群中可以按需创建任意数目的索引。

二、类型(Type)
类型是索引内部的逻辑分区(category/partition)，然而其意义完全取决于用户需求。因此，一个索引内部可定义一个或多个类型(type)。一般来说，类型就是为那些拥有相同的域的文档做的预定义。例如，在索引中，可以定义一个用于存储用户数据的类型，一个存储日志数据的类型，以及一个存储评论数据的类型。类比传统的关系型数据库领域来说，类型相当于“表”。

三、文档(Document)
文档是Lucene索引和搜索的原子单位，它是包含了一个或多个域的容器，基于JSON格式进行表示。文档由一个或多个域组成，每个域拥有一个名字及一个或多个值，有多个值的域通常称为“多值域”。每个文档可以存储不同的域集，但同一类型下的文档至应该有某种程度上的相似之处。

四、分片(Shard)和副本(Replica)
ES的“分片(shard)”机制可将一个索引内部的数据分布地存储于多个节点，它通过将一个索引切分为多个底层物理的Lucene索引完成索引数据的分割存储功能，这每一个物理的Lucene索引称为一个分片(shard)。每个分片其内部都是一个全功能且独立的索引，因此可由集群中的任何主机存储。创建索引时，用户可指定其分片的数量，默认数量为5个。

Shard有两种类型：primary和replica，即主shard及副本shard。Primary shard用于文档存储，每个新的索引会自动创建5个Primary shard，当然此数量可在索引创建之前通过配置自行定义，不过，一旦创建完成，其Primary shard的数量将不可更改。Replica shard是Primary Shard的副本，用于冗余数据及提高搜索性能。每个Primary shard默认配置了一个Replica shard，但也可以配置多个，且其数量可动态更改。ES会根据需要自动增加或减少这些Replica shard的数量。

ES集群可由多个节点组成，各Shard分布式地存储于这些节点上。

分布式架构
　　多台独立的机器上分别存在es进程，每个es进程中存在多个shard。shard分为primary和replica，replica是primary的从备份，每个primary的replica一般都分布在其他机器上，保证可用性。

【Elacticsearch】原理/数据结构/面试经典问题整理

应用层

Restful API ：提供丰富的操作接口，包括CRUD操作，索引管理，集群状态等。比如：'http:localhost:9200/_cat/indices' 查看创建的索引。
Java API：TransportClient(7.0之后废弃，8.0移除)，RestHighLevelClient（7.0之后常用）。

协议层

Thrift：是一种接口描述语言和二进制通讯协议，它被用来定义和创建跨语言的服务。它被当作一个远程过程调用（RPC）框架来使用。
Tcp：ElasticSearch由Transport负责通信，而Transport是基于TCP通信采用Netty实现。
http：Elasticsearch对外提供的API是以HTTP协议的方式,通过JSON格式以REST约定对外提供。它为我们提供了RestFul API和Java API RestHighLevelClient来提供开发使用。
JMX：JMX（Java Management Extensions，即Java管理扩展）是一个为应用程序、设备、系统等植入管理功能的代理和服务框架。JMX可以跨越一系列异构操作系统平台、系统体系结构和网络传输协议，灵活的开发无缝集成的系统、网络和服务管理应用。(日常ES中使用比较少，作为了解部分即可)

脚本/发现

Discovery：服务发现模块，包括master选举、服务探测、服务发现等，ES默认实现为ZenDiscovery。
Script：ES提供一些脚步开发来实现复杂业务场景功能开发。
Plugins：ES提供抽象插件机制，用户可以实现自己的插件开发来满足不同的业务需求。

数据处理

Index Module：索引模块是按索引创建的模块，控制index相关的所有方面。
Search Module：搜索模块，负责调用底层lucene的搜索服务。
River：Elastisearch中提供了River模块来从其他数据源中获取数据，该项功能以插件的形式存在，目前已有的River插件包括：RabbitMQ、ActiveMQ、CSV、FileSystem、JDBC、、Kafka等，已经覆盖了大部分的数据源，特别是针对关系型数据库提供了统一的jdbc-river来进行数据操作。

核心架构

Lucene是一个功能最强大的搜索库， ES底层的Engine模块通过封装lucene来实现索引写入和查询操作。

数据存储

Gateway 是 Elasticsearch 索引的持久化存储方式，ES 默认是先把索引存放到内存中，提高搜索的时效性，再持久化到硬盘里，保障数据的持久可靠。

如果创建一个索引product_idx，那么该索引的数据就会保存在多个shard中。es 集群多个节点，会自动选举一个节点为 master 节点，这个 master 节点其实就是干一些管理的工作的，比如维护索引元数据、负责切换 primary shard 和 replica shard 身份等。要是 master 节点宕机了，那么会重新选举一个节点为 master 节点。如果某个非 master 节点宕机了。那么此节点上的 primary shard 不就没了。那好，master 会让 primary shard 对应的 replica shard（在其他机器上）切换为 primary shard。如果宕机的机器修复了，修复后的节点也不再是 primary shard，而是 replica shard。

【Elacticsearch】原理/数据结构/面试经典问题整理

1、index包含多个shard。

2、每个shard都是一个最小工作单元，承载部分数据，lucene实例，完整的建立索引和处理请求的能力。增减节点时，shard会自动在nodes中负载均衡。

3 、primary shard和replica shard，每个document肯定只存在于某一个primary shard以及其对应的。replica shard中，不可能存在于多个primary shard。

4、replica shard是primary shard的副本，负责容错，以及承担读请求负载。副本中的数据保证强一致或最终一致。

5、primary shard的数量在创建索引的时候就固定了，因为索引时，需要按照primary shard的数量为文档做路由（默认使用文档的_id属性取哈希值做路由，也可以通过routing指定使用其他文档字段取哈希值做路由）。replica shard的数量可以随时修改。

6、primary shard的默认数量是5，replica默认是1，默认有10个shard，5个primary shard，5个replica shard。

7、primary shard不能和自己的replica shard放在同一个节点上（否则节点宕机，primary shard和副本都丢失，起不到容错的作用），但是可以和其他primary shard的replica shard放在同一个节点上;

原理
建立索引原理
查询索引原理
更新索引原理
删除索引原理
分片&副本机制，集群发现选举机制，负载机制，容错机制，扩容机制
压缩算法

数据类型

字符串类型：是ES最常用的类型之一。其内部使用了倒排索引算法。目前有两类字符串类型：text、keyword；

Keyword 类型：用于索引结构化内容（例如ID、电子邮件地址），默认不分词，应用场景：精准匹配、排序、聚合分析。
Text 类型：用于全文检索领域（例如电子邮件内容、日志内容等），默认进行分词，应用场景：全文检索领域。

数值类型：熟悉关系型数据库的应该都不难理解。其中，独特的是half_float和scaled_float两个类型；

long 带符号的64位整数，最小值为-263，最大值为263-1。
integer 一个带32位整数，最小值为-231，最大值为231-1。
short
byte
double
float
half_float 半精度16位IEEE 754浮点数。
scaled_float 支持固定的缩放因子的浮点数。

布尔型: boolean
日期: date
当你索引一个包含新域的文档—之前未曾出现-- Elasticsearch 会使用动态映射，通过JSON中基本数据类型，尝试猜测域类型；

数据结构

【Elacticsearch】原理/数据结构/面试经典问题整理

倒排索引：

倒排索引建立的是分词（Term）和文档（Document）之间的映射关系，在倒排索引中，数据是面向词（Term）而不是面向文档的。

一个倒排索引由文档中所有不重复词的列表构成，对于其中每个词，都会有一个包含它的文档列表。

普通keyword 数据采用倒排索引，其中根据不同使用场景用到了bitmap 。skipList 等数据结构；

地理位置等信息采用：BKD树；

先介绍倒排索引的组成部：倒排索引组成三部分

term dictionary

会根据分词器对文字进行分词（也就是图上所看到的Ada/Allen/Sara..)，这些分词汇总起来叫做Term Dictionary；

优化手段

该部分的词会非常非常多，所以es内部对其进行了排序，使用二分查找法来查，故而就不需要遍历整个词集

posting list

通过分词找到对应的记录，这些文档ID保存在PostingList；

优化手段

为节约磁盘空间和快速得出交并集结果。使用FOR以及RBM编码技术对内容压缩；

term index

由于Term Dictionary的词实在太多了，不可能把Term Dictionary所有的词都放在内存中，于是elastic还抽了一层叫做Term Index，这层只存储部分 词的前缀，Term Index会存在内存中（检索会特别快）具体如下：

字典里的索引页一样，A开头的有哪些term，分别在哪页，可以理解term index是一颗树。通过term index可以快速地定位到term dictionary的某个offset，然后从这个位置再往后顺序查找。大大减少了磁盘随机读的次数

这里遗留一个问题，如果Term Index树还是很大怎么办？

优化手段

为节省内存，该部分在内存中是以FST -有限状态机（https://cs.nyu.edu/~mohri/pub/fla.pdf）的形式保存的；

1）空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；
2）查询速度快。O(len(str))的查询时间复杂度。

【Elacticsearch】原理/数据结构/面试经典问题整理

其他优化思路：

当对多个字段进行检索时，利用了bitmap按位与进行归并优化（本身也是用bitmap的方式进行了存储

注：在特定场景非bitmap存储时，使用跳表来进行联合查询；

倒排索引特点

在索引时创建
序列化到磁盘
全文搜索非常快
不适合做排序
默认开启

倒排索引适用场景

查询
全文检索

Doc Values 为正排索引；

在 Elasticsearch 中，Doc Values 就是一种列式存储结构，默认情况下每个字段的 Doc Values 都是激活的（除了 text 类型），Doc Values 是在索引时创建的，当字段索引时，Elasticsearch 为了能够快速检索，会把字段的值加入倒排索引中，同时它也会存储该字段的 Doc Values。

Doc values 通过转置两者间的关系来解决适用倒排索引聚合效率低、难以扩展的问题。

倒排索引将词项映射到包含它们的文档，doc values 将文档映射到它们包含的词项。

Doc Values 特点

在索引时创建
序列化到磁盘
适合排序操作
将单个字段的所有值一起存储在单个数据列中
默认情况下，除text之外的所有字段类型均启用 Doc Values。

Doc Values 适用场景

Elasticsearch 中的 Doc Values 常被应用到以下场景：

对一个字段进行排序
对一个字段进行聚合
某些过滤，比如地理位置过滤
某些与字段相关的脚本计算

注意：

因为文档值被序列化到磁盘，我们可以依靠操作系统的帮助来快速访问。
当工作集（working set）远小于节点的可用内存，系统会自动将所有的文档值保存在内存中，使得其读写十分高速；
当其远大于可用内存，操作系统会自动把 Doc Values 加载到系统的页缓存中，从而避免了 jvm 堆内存溢出异常。

fielddata：

如前所述：

搜索需要回答“哪个文档包含此词？”的问题。借助：倒排索引实现。
排序和汇总则需要回答一个不同的问题：“此字段对本文档的价值是什么？” 。借助：正排索引实现。

text 类型字段是不支持 Doc Values正排索引的，text字段使用的是：查询时创建的基于的内存数据结构（query-time in-memory data structure） fielddata。fielddata 将 text 字段用于聚合、排序或在脚本中使用时，将按需构建此数据结构。

实现机理：
它是通过从磁盘读取每个段的整个倒排索引，反转词项↔︎文档关系并将结果存储在JVM堆中的内存中来构建的。

fielddata 特点

适用于文档之类的操作
但仅适用于 text 文本字段类型
在查询时创建
内存中数据结构
没有序列化到磁盘
默认情况下被禁用（构建它们很昂贵，并且在堆中预置）

fielddata 适用场景

全文统计词频
全文生成词云
text类型：聚合、排序、脚本计算

fielddata 使用注意事项

在启用fielddata 之前，请考虑为什么将文本字段用于聚合、排序或在脚本中使用。
启用 fielddata 通常没有任何意义，因为它非常耗费内存资源。
仅仅是做全文搜索的应用，就不需要启用fielddata。

联合索引

上面说的都是单field索引，如果多个field索引的联合查询，倒排索引如何满足快速查询的要求呢？

利用跳表(Skip list)的数据结构快速做“与”运算，或者
利用上面提到的bitset按位“与”

跳表的数据结构：

【Elacticsearch】原理/数据结构/面试经典问题整理

将一个有序链表level0，挑出其中几个元素到level1及level2，每个level越往上，选出来的指针元素越少，查找时依次从高level往低查找，比如55，先找到level2的31，再找到level1的47，最后找到55，一共3次查找，查找效率和2叉树的效率相当，但也是用了一定的空间冗余来换取的。

默认：倒排索引默认所有字段都启用，正排索引 Doc Values 非 text 类型默认启用， source （存储原始文档的所有字段的 json 结构数据）和 store （存储指定字段的 json 数据）的启用与否需要结合业务实际。假设：正排索引、倒排索引、_source 、store 都启用了，存储肯定会增加，但不是线性的 4倍。