从分布式系统设计看Elasticsearch集群及数据结构

一： 概述

es本质上就是由分布式思想+lucene组合而成，因为lucene的存在，它比一般的分布式系统会稍微复杂一点，es采取的分布式思想是分片+副本+去中心化。

es持久化的方式是：副本索引文件+translog文件，es默认配置下，为了比较好的速度，选择了性能，是可能丢数据的（5s）。redis aof是1s。和redis一样，在性能和可靠性中选择，如果选择直接写入磁盘，es写性能会损失8倍（压测）

lucene核心倒排索引，和B-TREE索引、k-v索引 数据结构不一样，倒排索引我认为是一个复合索引，它分为两部分，词表+倒排表，词表采用的索引数据结构是FST。搜索的本质就是and和or查询，转换到倒排里面，就是链表求交集和并集的一个过程

二： Elasticsearch写原理

写数据原理：和其它分布式一样，先hash取余，先定位数据分片，请求再写入translog（5s  fsync  translog）和内存缓冲区，内存缓冲区每秒同步到文件缓存，当文件缓冲区30分钟或者translog比较大时（500m），同步到磁盘。

refresh 用于控制搜索的实时性.刚刚写入的数据多长时间可以被搜到（es默认1s）

如果没有协调节点，那么轮询访问数据节点，当您向协调节点发送请求以索引新文档时，将执行以下操作：

1. 所有在Elasticsearch集群中的节点都包含：有关哪个分片存在于哪个节点上的元数据。协调节点(coordinating node)使用文档ID（默认）将文档路由到对应的分片。Elasticsearch将文档ID以murmur3作为散列函数进行散列，并通过索引中的主分片数量进行取模运算，以确定文档应被索引到哪个分片。和mysql分库分表一样，hash取模 
shard = hash(document_id) % (num_of_primary_shards)

2. 当节点接收到来自协调节点的请求时，请求被写入到translog（我们将在后续的post中间讲解translog），并将该文档添加到内存缓冲区。如果请求在主分片上成功，则请求将并行发送到副本分片。只有在所有主分片和副本分片上的translog被fsync’ed后，客户端才会收到该请求成功的确认。

3. 内存缓冲区以固定的间隔刷新（默认为1秒），并将内容写入文件系统缓存中的新段。此分段的内容更尚未被fsync’ed(未被写入文件系统)，分段是打开的，内容可用于搜索。
4. translog被清空，并且文件系统缓存每隔30分钟进行一次fsync，或者当translog变得太大时进行一次fsync。这个过程在Elasticsearch中称为flush。在刷新过程中，内存缓冲区被清除，内容被写入新的文件分段(segment)。当文件分段被fsync’ed并刷新到磁盘，会创建一个新的提交点（其实就是会更新文件偏移量，文件系统会自动做这个操作）。旧的translog被删除，一个新的开始。

translog：事务日志，和redis的aof类似，translog在发生故障的情况下确保数据的完整性，其基本原则是，在数据的实际更改提交到磁盘之前必须先记录并提交预期的更改, 当Elasticsearch尝试恢复或重新打开一个索引，它需要重放 translog 中所有的操作，所以如果日志越短，恢复越快。

下图显示了写入请求和数据流程： 

节点写操作

创建、索引、删除文档都是写操作，这些操作必须在primary shard完全成功后才能拷贝至其对应的replicas上。见Figure9。

下面是Figure9的步骤：

1. 客户端向Node1发送写操作的请求。
2. 
Node1使用文档的_id来决定这个文档属于shard0，然后将请求路由至NODE3，P0所在的位置。

3. Node3在P0上执行了请求。如果请求成功，则将请求并行的路由至NODE1 NODE2的R0上。当所有的replicas报告成功后，NODE3向请求的node(NODE1)发送成功报告，NODE1再报告至Client。（solrcloud是master节点副本。。es不确认）
4. 当客户端收到执行成功后，操作已经在Primary shard和所有的replica shards上执行成功了。

三：  Elasticsearch 查询原理

3.1  queryparse 通过关键字查询

查询阶段

1. 协调节点将搜索请求路由到索引(index)中的所有分片(shards)（包括：主要或副本）
2. 每个分片执行独立查询，根据相关度得到一个排序结果集
3. 所有分片返回默认10条返回给协调节点
4. 协调节点最后排序在合并排序返回最终的10条结果集

获取阶段

在协调节点对所有结果进行排序，已生成全局排序的文档列表后，它将从所有分片请求原始文档，所有的分片都会丰富文档并将其返回到协调节点。

3.2  通过id查询

如果没有路由节点的话，轮询所有节点。

一个文档可以在primary shard和所有的replica shard上读取。见Figure10（通过id查询）

读操作步骤：

1. 客户端发送Get请求到NODE1。

2. NODE1使用文档的_id决定文档属于shard 0.shard 0的所有拷贝存在于所有3个节点上。这次，它将请求路由至NODE2。
3. 
NODE2将文档返回给NODE1，NODE1将文档返回给客户端。

对于读请求，请求节点(NODE1)将在每次请求到来时都选择一个不同的replica。
shard来达到负载均衡。使用轮询策略轮询所有的replica shards。

四： 集群性能优化

由于Elasticsearch核心是分布式思想+lucene，所有优化方式主要也在这两个点上。

4.1  分布式优化

• elasticsearch集群角色划分和隔离，把master(集群和索引管理 3台就够了)和client（路由节点）独立出来
• 分片副本策略
• 数据冷热隔离： 一般用户日志型应用，一般每天建立一个新索引，当天的热索引会有比较多的查询，如果上面还存在比较早的数据，那么当用户做大跨度的历史数据查询的时候，过多的磁盘IO和CPU消耗很容易拖慢写入，造成数据的延迟。 所以我们用了一部分机器来做冷数据的存储，利用ES可以给结点配置自定义属性的功能，为冷结点加上"boxtype":"weak"的标识，每晚通过维护脚本更新冷数据的索引路由设置index.routing.allocation.{require|include|exclude}，让数据自动向冷结点迁移。 冷数据的特性是不再写入，用户查的频率较低，但量级可能很大。
• query优化，主要就是query缓存

4.2  lucene优化

1. 定期做段合并（segment）https://www.jianshu.com/p/9b872a41d5bb 
2. docValues相关：Elasticsearch默认所有字段都开启了docValue（除了分词）（solr默认全部关闭的），按照业务酌情关闭部分字段，Elasticsearch Jvm内存要给系统内存留足够大的空间。
3. cpu相关：屏蔽打分/排序机制tf-idf，同样的条件，精确查询速度还没有模糊查询速度快 
4. io相关：

1. 优化io，一次查询，至少3次随机io，预算充足的话，全部固态硬盘，次之，tim、doc文件放到ssd。
2. 减少io，使用布隆过滤器，预先判断单词是不是在该索引库里

五   lucene 原理

5.1 lucene索引结构

lucene查询过程：

整个流程至少发生三次随机IO： 

　　1. 读后缀词块 

　　2. 读倒排表 

　　3. 取文档（如果文档号跳跃性很大或者因为打分完全乱序，那么会发生更多次随机IO，极端情况就是取多少文档就发生多少次随机IO） 

5.2  倒排索引

目的是建立词到文档id的映射关系。

倒排索引文件（词表索引需要内存加载）：tip=词典索引，内存加载；tim=后缀词典、倒排表指针；doc=倒排表

倒排索引原理

1. 词表：FST。类似于字典树（适合英文），共享前缀，内存消耗小； 词表结构
2. 倒排表：文档号集合。数据压缩+有序链表+跳表    倒排表原理

FST词表：

lucene为了使信息的存储空间更小，访问速度更快，采用了一些技巧：

1. 前缀后缀原则：当某一个词和前面一个词有共同的前缀的时候，后面的词仅仅保留    前缀在词中的偏移，以及出前缀外的字符串
2. 差值原则：先后保存两个整数的时候，后面的整数仅仅保存和前面整数的差值即可。
3. 或然跟随原则: lucene索引结构用一个标志位来表示某个值A后面可能存放某个值       B 这样会浪费一个byte的空间，实际上一个bit就够了
4. 跳跃表规则：元素按顺序排列，按跳跃间隔和跳跃层次提交查找速度

1. 优势：内存占用率低，压缩率一般在3倍~20倍之间、模糊查询支持好、查询快
2. 缺点：结构复杂、输入要求有序、更新不易，和hashMap比较查询稍慢

5.3  列式存储（docValues）（d*）

文档到词列表的映射（一列上存储所有value）

换句话说，我们需要一个在倒排索引的基础上建立的“正排索引”，这里的“正排索引”结构通常在其他系统中（如关系型数据库）被称为“列式存储”。

        索引时，ES会把“词”加入到倒排索引中，同时把这些词也加入到面向“列式存储”的doc values中（存储在硬盘上）。依赖操作系统的file system cache 替代JVM的堆内存，当我们的“工作集”小于OS可用内存时，操作系统会自然的加载这些doc values到内存。这时doc values的性能和在JVM堆内存中表现是一样的。

        我们配置JVM的堆内存基本和操作系统内存各占一半（50%），由于引进了doc values所以我们可以考虑把JVM的堆内存留一部操作系统。

列式存储压缩：

doc values使用几种手段来压缩数字。

1. 如果所有的数字值都相等（或者缺失），会设置一个标记来表示该值

2. 如果所有数字值的个数小于256个，将会使用一个简单的编码表来压缩

3. 如果大于了256个，看看是否存在最大公约数，存在则使用最小公倍数压缩

4. 如果不存在最大公约数，则存储偏移量来压缩数字。

        其实字符串压缩也是和数字压缩一样采用同样的方法通过一个序数表来压缩，字符串被去重、排序后被赋予了一个ID，这些ID就是数字，这样就可以采用上面的方案进行压缩了

5.4 正向文件（f*）

正向文件指的就是原始文档，Lucene对原始文档也提供了存储功能，它存储特点就是分块+压缩，fdt文件就是存放原始文档的文件，它存储特点就是分块+压缩，fdt文件就是存放原始文档的文件，它占了索引库90%的磁盘空间。

取文档过程非常依赖随机IO，以及lucene虽然提供了取特定列，但从存储结构可以看出，并不会减少取文档时间。

5.5  segment

一个Index会由一个或多个sub-index构成，sub-index被称为Segment

Lucene中的数据写入会先写内存的一个Buffer（类似LSM的MemTable，但是不可读），当Buffer内数据到一定量后会被flush成一个Segment，每个Segment有自己独立的索引，可独立被查询，但数据永远不能被更改。这种模式避免了随机写，数据写入都是Batch和Append，能达到很高的吞吐量。

Segment中写入的文档不可被修改，但可被删除，删除的方式也不是在文件内部原地更改，而是会由另外一个文件保存需要被删除的文档的DocID，保证数据文件不可被修改。

Index的查询需要对多个Segment进行查询并对结果进行合并，还需要处理被删除的文档，为了对查询进行优化，Lucene会有策略对多个Segment进行合并，这点与LSM对SSTable的Merge类似。

5.6  Flush、Commit

1. flush是把数据写入到操作系统的缓冲区，只要缓冲区不满，就不会有硬盘操作。
2. commit是把所有内存缓冲区的数据写入到硬盘，是完全的硬盘操作。