ElasticSearch 原理解析

用户头像
Chank
关注
发布于: 2020 年 06 月 16 日
ElasticSearch原理解析

ElasticSearch底层基于Lucene,因此,要深入理解ElasticSearch,首先需要了解Lucene。

Lucene

倒排索引结构

Lucene的核心就是倒排索引(Inverted Index),倒排索引是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。

Lucene会将文档分成一个一个的Term(单词),然后建立倒排索引。首先让我们先来看看倒排索引的结构:



Term Index:Lucene使用FST实现Term Index,Term Index是Term Dictionary的索引,可以快速查找一个Term是否在Dictionary中;并且能够快速定位Block的位置。

Term Dictionary:Segment的字典

Postings:记录了出现过的某个Term的文档列表及该Term在文档中出现的位置信息(Payload)

Payload的作用:

  1. 存储每个文档都有的信息

  2. 影响词的评分

从上图可以看出,Lucene使用FST(Finite State Transducer)实现,FST类似字典树,但与字典树又有很大的不同,FST有如下特点:

  1. 共享前缀

  2. 共享后缀

  3. 确定

  4. 无环

  5. Transducer:接收特定的序列,终止于Final状态,同时会输出一个值

因此可以看出,FST相比于字典树又大大地减少了内存使用率。

Lucene 文件结构



Lucene索引到词(Term)的关系:索引(Index)→ 段(Segment)→ 文档(Document)→ 域(Field)→ 词(Term)。

Lucene一个Index会包含多个Segment,一个Segment又由多个文件共同组成:

xx.tip:存储Term Index

xx.tim:存储Term Dictionary

xx.doc:存储Postings的DocId信息和Term的词频

xx.fnm:存储文档Field的元信息

xx.fdx:存储文档的索引,使用SkipList来实现

xx.fdt:存储具体的文档

xx.dvm:存储DocValues元信息

xx.dvd:存储具体DocValues数据

可以看出,Lucene不仅支持行式存储,还支持列式存储。其中列式存储可以大大提高排序、聚合、统计等查询操作的性能。

Lucene没有更新跟删除逻辑,所有对Lucene的更新都是Append一个新Doc到Segment。

Lucene 索引流程



Lucene索引文档(Document)的流程:

  1. Tokenizer:分词阶段,会将文档分成一个一个的词元(Token)

  2. Linguistic Processor:语言处理阶段,转为小写或者将单词缩减为词根形式等,处理的结果成为词(Term)

  3. Indexer:索引阶段,此阶段会创建字典、创建倒排表等等

让我们再从另一个角度来看一下Lucene的索引流程:



从上图可以看出,在Lucene中,新加的文档首先会被放到内存里,当满足FlushPolicy的时候内存中的数据才会被写入到磁盘。此时新加的文档才能被搜索到,这也是为什么ElasticSearch被称为准实时搜索的原因之一。每次刷新事件发生时,ElasticSearch都会创建一个新的Lucene段,并在稍后进行合并。

Lucene 搜索流程



Lucene搜索文档(Document)的流程:

  1. Lexical Analysis:词法分析,识别单词和关键字

  2. Syntactic Analysis:语法分析,根据语法规则来生成一棵语法树

  3. Linguistic Processor:语言处理,转为小写或者将单词缩减为词根形式等

  4. Search Index:搜索索引,找出包含关键字的文档链表,根据语法树对文档链表进行合并操作,得到最终要搜索的文档

  5. Order Result:结果排序,会计算权重,判断Term之间的关系,从而得到排序后的文档列表

一个Lucene Index是由多个Segment组成的,因此一次搜索请求可能需要同时搜索所有的Segment,如下图所示:

Lucene Segment 合并过程



Segment的合并流程

  1. 根据Segment的名字对其进行排序

  2. 根据Segment的大小对Segment进行分组

  3. 在每一组里面选择要合并的Segment进行合并

Lucene 相关性打分

在ElasticSearch 5.0之前ElasticSearch的相关性打分默认使用的是TF-IDF算法,ElasticSearch 6.0之后采用了BM25算法(TF-IDF的改进版)。BM25(Best Matching)算法在TF无限增加时会使之趋于一个稳定的值。我们首先来看一下BM25算法所使用的公式:



BM25的核心是f(qi, D)跟IDF(qi),n代表的是查询Term的个数,k1跟b是常量。在Lucene中,K1是1.2,b是0.75。

f(qi, D)是TF - Term Frequency,TF = (Number of times term t appears in a document) / (Total number of terms in the document)

IDF(qi)是IDF - Inverse Document Frequency,IDF = log((Total number of documents) / (Number of documents with term t in it))

直观理解下公式的含义:

  • TF(词频):如果一个Term在一个文档中出现的次数越多,那么这个文档就会越符合,这个文档的得分就会越高

  • IDF(逆文档频率):如果一个Term在不同文档中出现的次数越多,那么它就越不重要

  • 字段越短,字段的权重越高。例如出现在类似标题Title这样的字段中,要比它出现在内容Body这样的字段中的相关度更高

ElasticSearch

ElasticSearch是一个基于Lucene的分布式搜索引擎。我们首先来看看ElasticSearch跟Lucene的关系,如下图所示:



ElasticSearch Index由多个ElasticSearch Shard组成,其中每一个ElasticSearch Shard都是一个Lucene Index,一个Lucene Index又是由多个Lucene Segment组成。因此,ElasticSearch在Lucene的基础上实现了分布式的搜索。接下来就让我们看看ElasticSearch的架构。

ElasticSearch Architecture



ElasticSearch集群节点主要有三种角色(ElasticSearch还有其它角色,这里的拓扑结构只是一种推荐做法):

  1. Client Node:无状态,主要做为索引跟搜索的路由器。索引请求会计算文档的Sharding Key,并将请求发给对应的ElasticSearch Shard进行处理(ElasticSearch Shard所在的Data Node会从Master Node进行获取);搜索请求会并行搜索所有的ElasticSearch Shard,并且整合结果后返回给应用程序。

  2. Data Node:数据结点

  3. Master-eligible Node:集群状态结点。主要管理了有如下信息:路由表:所有索引所在的Data Node信息集群结点信息元数据:索引元数据,模板元数据等

ElasticSearch中数据一致性的保证使用的是PacificA算法,因此采用的是主备模式来存储数据,数据的更改只能通过主节点来进行,然后复制到其它节点。PacificA算法中写数据需要等待所有的副本数据都写成功才能提交,因此写数据的延迟取决于最慢的那个节点。但这样做的好处是如果有n+1个节点,那么能容忍n个节点挂掉。数据主节点的选举由Master Node来负责。

ElasticSearch Master-eligible Node采用的是主从架构,ElasticSearch自己实现了一个选举算法(类似Raft)。之所以不采用Zookeeper或者ETCD等第三方框架做Master选举是因为不想引入过多的复杂性,加大运维负担。

ElasticSearch 索引流程



ElasticSearch索引流程:

  1. 索引请求首先会发送到Client Node,Client Node会根据路由规则将请求转发到Data Node(Primary Shard)进行处理(Parimary Shard所在的Data Node从Master Node获取)

  2. Primary Shard会往Lucene写,写成功后会再写到Translog(Translog是ElasticSearch为了提高可靠性引入的,因为Lucene首先会先写内存,如果宕机了数据就丢了),然后会将广播到Replica Shard进行处理

  3. 在所有的Replica Shard都写成功后则返回给用户成功索引数据

ElasticSearch默认的路由规则是:

shard_num = hash(routing) % num_primary_shards

_routing的默认值是文档的 _id

我们也可以自定义路由规则,具体可看:_routing field

ElasticSearch 搜索流程



ElasticSearch搜索流程:

  1. 搜索请求首先会发送到Client Node,Client Node收到搜索请求后会并行请求所有的Shard

  2. Shard收到请求后会并行搜索所有Segment,搜索完后会将结果合并返回给Client Node

  3. Client Node会合并所有Shard的结果,并进行相关性排序,最后将排序的结果返回给用户

ElasticSearch 扩容

上面已经介绍过,ElasticSearch默认的路由策略是: hash(routing) % num_primary_shards

可以看出,路由策略是和Shard数量是强相关的。因此如果我们强制增加Shard的话会破坏路由规则。

那么如果我们需要扩容怎么办呢?

答案是我们可以重新创建一个索引,然后将老索引的数据迁移到新的索引上。ElasticSearch为了简化这个流程,提供了Reindex API

ElasticSearch 搜索常见技巧

Index Mapping

Index Mapping是对索引的字段名称跟数据类型等的定义,类似于MySQL中的表结构信息。可以通过Mapping定义使用的分词器、是否分词、是否存储等等。

Index Setting

Index Setting是索引的设置,可以指定索引的Shard数跟Replicas数等。

在创建索引的时候一般需要仔细设置Index Mapping跟Index Setting。

索引别名

索引别名就像一个快捷方式或软连接,可以指向一个或多个索引。

利用索引别名机制,我们可以按月或按年建索引,使用别名关联多个索引,然后就可以灵活地选择索引的过期时间

Rollover

通过ElasticSearch的Rollover机制,可以在索引满足一个的条件后新建索引,并将索引别名转向新索引。可以设置的Rollover条件有:

  1. max_age:索引最大存活时间

  2. max_docs:索引最大文档数

  3. max_size:索引最大大小

索引模板

索引模板 + Rollover机制 + 索引别名机制 可以实现自动创建索引,在我们需要对数据进行过期处理时这几个特性联合使用非常强大。

索引模板在索引创建时会自动应用到索引上。

搜索提示

ElasticSearch的搜索提示使用基于内存的FST实现,因此速度极快。

具体可参考:You Complete Me

ILM(Index Lifecycle Management)

ElasticSearch索引生命周期管理可用来实现热-温-冷架构。

ElasticSearch索引生命周期有四个阶段:

  • 热:索引更新跟查询比较频繁

  • 温:索引不再被更新,但还会有搜索

  • 冷:索引不再被更新,而且搜索请求很少

  • 删除:索引不再需要,可以被删除

可以看出,热-温-冷架构非常适合用于日志或指标类的时序数据。

分页

由于ElasticSearch是分布式的,查找第一页数据需要所有Shard都返回第一页的数据,然后由Client Node进行聚合跟排序,最后只将一页的结果返回给用户。因此ElasticSearch深度分页会随着分页的深度成指数上升。一般不建议分页数太大。

如果有查询大批量数据的需求的话可以使用ElasticSearch的Scroll功能。

多集群架构

可以参考:

滴滴Elasticsearch多集群架构实践(基于Tribe Node,已经弃用)

Search Across Clusters

Cross-cluster Replication

冷热数据读写分离

假如查询需要搜索的数据量很大,那么大量的磁盘IO会阻塞新数据的写入。因此为了优化写入的性能,我们需要做读写分离。

具体方案:

  1. 在热数据节点中配置: node.tag: hot,在冷数据节点上配置: node.tag: stale (在elasticsearch.yml中配置)

  2. 对新建索引添加hot标签

  3. 每天定时任务更新索引的配置,将tag更改为stale,ElasticSearch就会自动将索引迁移到冷数据节点了

也可以使用ILM来控制。

调优解决方案

这里只是总结下Pronto团队总结的ElasticSearch调优的策略方法,具体可以看这里

  1. 预估集群大小索引吞吐量搜索吞吐量文档大小保留策略响应时间需求SLA级别

  2. 优化索引设计如果查询有一个过滤字段并且它的值是可枚举的,那么把数据分成多个索引如果查询有一个过滤字段并且它的值是不可枚举的,建议使用Routing如果查询具有日期范围过滤子句,则按日期建立索引明确设置Mapping确保分片均匀分布在节点上Frozen Indices

  3. 索引性能调优使用批量请求使用多线程发送请求增加刷新时间间隔减少副本数量

  4. 搜索性能调优尽可能使用过滤上下文(Filter)替代查询上下文(Query)增加刷新时间间隔增加副本数尝试不同的分片数节点查询缓存分片查询缓存:适用于大多数查询是聚合查询仅检索必要的字段避免搜索停用词避免使用通配符查询

  5. 运行性能测试每一次变更都需要运行性能测试来验证变更是否适用

参考

ElasticSearch Reference

Wikipedia: 倒排索引

关于Lucene的词典FST深入剖析

Build your own FST(Try FST)

Lucene底层原理

Lucene索引文件

lucene中倒排索引的逻辑结构

What is term vector in Lucene

Lucene倒排索引原理探秘

A few things you need to know about Lucene

生产环境elasticsearch的配置建议

Guide to Refresh and Flush Operations in Elasticsearch

Lucene IndexWriter: An In-Depth Introduction

Visualizing Lucene's segment merges

Merge Policy Internals

深入理解Lucene默认打分算法

Elasticsearch 搜索的高级功能学习

Elasticsearch Distributed Consistency Principles Analysis (1) - Node

Elasticsearch Distributed Consistency Principles Analysis (2) - Meta

Elasticsearch Distributed Consistency Principles Analysis (3) - Data

索引分片: 从策略层面,控制分片分配的选择

Elasticsearch如何做到数十亿数据查询毫秒级响应?

腾讯万亿级 Elasticsearch 技术解密

You Complete Me

使用索引生命周期管理实现热温冷架构

滴滴Elasticsearch多集群架构实践

eBay 的 Elasticsearch 性能调优实践

Okapi BM25 with Game of Thrones

有赞搜索引擎实践(算法篇)



用户头像

Chank

关注

还未添加个人签名 2019.02.06 加入

邮箱:fangliquan@qq.com

评论

发布
暂无评论
ElasticSearch原理解析