​ElasticSearch

基本概念

倒排索引

FST

简介

ES是一个基于lucene构建的，分布式的，RESTful的开源全文搜索引擎。支持对各种类型的数据的索引；搜索速度快，可以提供实时的搜索服务；便于水平扩展，每秒可以处理 PB 级海量数据

• E：EalsticSearch 搜索和分析的功能
• L：Logstach 搜集数据的功能，类似于flume（使用方法几乎跟flume一模一样），是日志收集系统
• K：Kibana 数据可视化（分析），可以用图表的方式来去展示，文不如表，表不如图，是数据可视化平台

基本概念

ES 和传统数据库相比对应关系如下：

• 索引：一个 索引 就是一个拥有几分相似特征的文档的集合。ES 将数据存储于一个或多个索引中，索引 就相当于 SQL 中的一个数据库。
• 类型：类型是索引内部的逻辑分区（category/partition）,然而其意义完全取决于用户需求。因此，一个索引内部可定义一个或多个类型（type）。一般来说，类型就是为那些拥有相同的域的文档做的预定义。类比传统的关系型数据库领域来说，类型 相当于 表，7.x 版本默认使用 _doc 作为 type 。
• 文档：文档是 Lucene 索引和搜索的 原子单位，它是包含了一个或多个域的容器，基于 Json 格式进行表示。文档有一个或多个域组成，每个域拥有一个名字及一个或多个值，有多个值的域通常被称为 多值域，每个文档可以存储不同的域集，但同一类型下的文档至应该有某种程度上的相似之处。相当于 mysql 表中的 row 。
• 字段：Field 是相当于数据库中的 Column
• 映射：Mapping 是定义文档及其包含的字段如何存储和索引的过程。Mapping 是 ES 中的一个很重要的内容，它类似于传统关系型数据中 table 的 schema，用于定义一个索引（index）的某个类型（type）的数据结构。

• 集群（cluster）& 节点（Node）：Elasticsearch 本质上是一个分布式数据库，允许多台服务器协同工作，每台服务器可以运行多个 Elasticsearch 实例。单个 Elasticsearch 实例称为一个节点（Node），一组节点构成一个集群（Cluster）。
• 分片（shard）：一个 索引 可以存储超出单个结点硬件限制的大量数据。比如，一个具有 10亿文档的索引占据 1TB 的磁盘空间，而任一节点都没有这样大的磁盘空间；或者单个节点处理搜索请求，响应太慢。为了解决这个问题，Elasticsearch 提供了将索引划分成多份的能力，这些份就叫做分片。当你创建一个索引的时候，你可以指定你想要的分片的数量。每个分片本身也是一个功能完善并且独立的 索引，这个 索引 可以被放置到集群中的任何节点上。
• 副本（Replica）：副本是一个分片的精确复制，每个分片可以有零个或多个副本。提高系统的容错性，当某个节点某个分片损坏或丢失时，可以从副本中恢复；提高 ES 查询效率，ES 会自动对搜索请求进行负载均衡。

倒排索引

es之所以那么快，查询起来效率这么高，主要还是es插入数据的索引机制。

我们知道 mysql 查询这么快，是由于建立了 B+树 ，内部建立了树状的索引，这种称为正排索引。

用B+树作为索引行不行呢？全文索引就是需要支持对大文本进行索引的，从空间上来说 B+ 树不适合作为全文索引，同时 B+ 树因为每次搜索都是从根节点开始往下搜索，所以会遵循最左匹配原则，而我们使用全文搜索时，往往不会遵循最左匹配原则，所以可能会导致索引失效。这时候倒排索引就派上用场了。

es 建立的索引称为倒排索引，在数据插入的时候，就对数据进行统计，将每一个 document 经过分词，分词之后统计出现的频数，这样查询的时候就可以根据查询的词快速定位到某一个数目，同时由于创建的时候统计的频数，可以对具体内容进行排序，可以类比于百度的搜索排名

倒排索引的结构主要包括了两大部分一个是Term Dictionary（单词词典），另一个是Posting List（倒排列表）。Term Dictionary（单词词典）记录了所用文档的单词以及单词和倒排列表的关系。Posting List（倒排列表）则是记录了term在文档中的位置以及其他信息，主要包括文档ID,词频（term在文档中出现的次数，用来计算相关性评分），位置以及偏移（实现搜索高亮）。

FST

如上文所述，在进行全文检索的时候，通过倒排索引中term与docId的关联关系获取到原始数据。但是这里有一个问题，ES底层依赖Lucene实现倒排索引的，因此在进行数据写入的时候，Lucene会为原始数据中的每个term生成对应的倒排索引，因此造成的结果就是倒排索引的数据量就会很大。而倒排索引对应的倒排表文件是存储在硬盘上的。如果每次查询都直接去磁盘中读取倒排索引数据，在通过获取的docId再去查询原始数据的话，肯定会造成多次的磁盘IO，严重影响全文检索的效率。因此我们需要一种方式可以快速定位到倒排索引中的term。

大家想想使用什么方式比较好呢？可以考虑HashMap， TRIE， Binary Search Tree或者Tenary Search Tree等数据结构，实际上Lucene实际是使用了FST（Finite State Transducer）有限状态传感器来实现二级索引的设计，它其实就是一种有限状态机。

我们先来看下 trie树的结构，在Lucene中是这样做的，将倒排索引中具有公共前缀的term组成一个block，如下图所示的cool以及copy，它们拥有co的公共前缀，按照类似前缀树的逻辑来构成trie树，对应节点中携带block的首地址。我们来分析下trie树相比hashmap有什么优点？hashmap实现的是精准查找，但是trie树不仅可以实现精准查找，另外由于其公共前缀的特性还可以实现模糊查找。那我们再看trie树有什么地方可以再进行优化的地方？

 如上如所示，term中的school以及cool的后面字符是一致的，因此我们可以通过将原先的trie树中的后缀字符进行合并来进一步的压缩空间。优化后的trie树就是FST。

因此通过建立FST这个二级索引，可以实现倒排索引的快速定位，不需要经过多次的磁盘IO，搜索效率大大提高了。不过需要注意的是FST是存储在堆内存中的，而且是常驻内存，大概占用50%-70%的堆内存，因此这里也是我们在生产中可以进行堆内存优化的地方。