ElasticSearch

一、引言

1.什么是搜索？

概念：搜索是指使用计算机程序在互联网或本地计算机存储的数据中查找特定信息的过程

即输入关键字，获取想要结果的过程

搜索涉及的种类十分繁杂，包括新闻网页搜索、站内搜索（垂直搜索）等

2.如何实现搜索

2.1 传统数据库

传统MySql数据库能否实现搜索功能呢？答案是肯定的

但是传统MySql数据库实现搜索只能适用数据量小，简单搜索的场景，具有以下弊端

存储问题：电商网站商品上亿条时，涉及到单表数据过大必须拆分表，数据库磁盘占用过大必须分库 (mycat)
性能问题：解决上面问题后，查询“笔记本电脑”等关键词时，上亿条数据的商品名字段逐行扫描，性能跟不上
不能分词：如搜索“笔记本电脑”，只能搜索完全和关键词一样的数据，那么数据量小时，搜索“笔记本电脑”，“电脑”数据要不要给用户

2.2 全文检索与倒排索引

在MySql中，其实也支持全文检索，主要依赖于MySql的全文索引来实现，是一种用于快速搜索文本数据的索引技术，MySQL 5.6及以上版本支持全文索引

全文索引会将指定的列中的文本数据进行分词，去除停用词等处理，生成一个词汇表，将每个词汇与出现该词汇的行进行关联，从而加速文本数据的搜索，需要注意的是，MySQL的全文索引实现是基于倒排索引（Inverted Index）的

何谓倒排索引呢？简单点说就是，以词作为key，出现位置的集合作为value的结构

举个例子，见下表

ID	Name
1	课程周边帽子
2	课程周边衣服
3	课程书籍XXX
4	杰伦签名

那么在对Name列分词，按照倒排索引就可以得到下面的表格

分词term	IDs
课程	[1,2,3]
周边	[1,2]
书籍	[3]
杰伦	[4]
…	…

由此可见，如果用户输入一个关键词后，能够快速的匹配到分词，从而找到分词出现的位置

倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted fifile)

2.3 Lucene

Lucene是一个非常强大和灵活的全文搜索引擎库，能够广泛应用于各种文本搜索场景，包括网站搜索、企业搜索、电子商务、新闻检索等

简单点说，就是一个jar包，里面封装了全文检索的引擎、搜索的算法代码。开发时，引入lucen的jar包，通过api 开发搜索相关业务。底层会在磁盘建立索引库

二、概念介绍

1.简介

Elasticsearch（ES）是基于Lucene构建的分布式搜索引擎，它扩展了Lucene的功能并提供了大规模数据处理、实时搜索、多租户等特性。因此，可以说ES是Lucene的一个扩展和增强版

ES在Lucene的基础上提供了以下特性：

分布式架构：ES具有分布式的数据存储和处理能力，可以实现数据分片、节点扩展和高可用等功能
RESTful API：ES使用基于HTTP协议的RESTful API，可以方便地与其他应用程序和工具进行交互
实时搜索：ES能够在数据发生变化时实时更新索引，提供实时搜索的能力
多租户支持：ES支持多租户模式，可以在同一个ES集群中隔离多个应用的数据和搜索请求
多种查询方式：ES支持多种查询方式，包括全文搜索、精确查询、过滤查询等

上面介绍的是ES的特性，主要是说ES更加适合大型分布式系统，那么它到底具有哪些功能呢？下面介绍

分布式的搜索引擎和数据分析引擎
- 搜索:互联网搜索、电商网站站内搜索、OA系统查询
- 数据分析:电商网站查询近一周哪些品类的图书销售前十;新闻网站，最近3天阅读量最高的十个
- 关键词，舆情分析。
全文检索，结构化检索，数据分析
- 全文检索:搜索商品名称包含java的图书
  - select * from books where book_name like “%java%”。
- 结构化检索:搜索商品分类为spring的图书都有哪些
  - select * from books where category_id=’spring’
- 数据分析:分析每一个分类下有多少种图书
  - select category_id,count(*) from books group by category_id
对海量数据进行近实时的处理
- 分布式:ES自动可以将海量数据分散到多台服务器上去存储和检索，进行并行查询，提高搜索效率。相对的，Lucene是单机应用。
- 近实时:数据库上亿条数据查询，搜索一次耗时几个小时，是批处理(batch-processing)。而es 只需秒级即可查询海量数据，所以叫近实时。秒级

简单来说，就是搜索、分析、分布式和近实时

2.适用场景

Elasticsearch（ES）是一个强大的搜索引擎，具有广泛的应用场景，包括但不限于以下几个方面：

企业搜索：ES能够处理海量的企业数据，包括文本、图片、视频等类型的数据，能够提供高效、准确的搜索结果。企业搜索场景包括了员工信息搜索、文档搜索、知识库搜索等。
日志分析：ES能够对大量的日志数据进行处理和分析，提取关键信息，帮助企业监测业务运营和系统性能。日志分析场景包括了网络日志、系统日志、应用程序日志等。
电商搜索：ES能够处理商品信息和用户搜索请求，提供高效、准确的搜索结果。电商搜索场景包括了商品搜索、推荐引擎等。
网站搜索：ES能够处理网站上的信息和用户搜索请求，提供高效、准确的搜索结果。网站搜索场景包括了新闻搜索、博客搜索、社交网络搜索等。
实时监控：ES能够实时处理数据，包括日志、事件、传感器数据等，可以在实时监控场景中应用。实时监控场景包括了网络监控、物联网监控等。

主要场景还是搜索

3.特点

高可用性：ES是一个分布式系统，支持多个节点的部署和自动容错，因此具有高可用性。即使其中某些节点发生故障，系统依然能够正常运行。
多种数据源支持：ES支持多种类型的数据源，包括关系型数据库、文档、日志、传感器数据等，因此适用于各种数据分析场景。
实时搜索和分析：ES能够在数据发生变化时实时更新索引，提供实时搜索和分析的能力。
多种查询方式：ES支持多种查询方式，包括全文搜索、精确查询、过滤查询等，满足不同的搜索需求。
可扩展性：ES具有高度可扩展性，可以根据业务需求动态扩展节点和数据存储容量。
灵活的部署方式：ES可以在云端或本地环境中部署，支持多种操作系统和编程语言，因此非常灵活

可拓展、高可用、功能强大、部署简单

4.核心概念

4.1 NRT(Near Realtime):近实时

两方面:

写入数据时，过1秒才会被搜索到，因为内部在分词、录入索引
es搜索时:搜索和分析数据需要秒级出结果

4.2 Cluster:集群

包含一个或多个启动着es实例的机器群，通常一台机器起一个es实例，同一网络下，集名一样的多个es实例自动组成集群，自动均衡分片等行为，默认集群名为“elasticsearch”

4.3 Node:节点

Node是一个单独的ES实例，可以是单独的服务器或虚拟机

每个Node可以参与一个或多个Cluster，并负责处理Cluster中的数据和请求

Node可以承载多个Index，每个Index可以包含多个Shard

节点名自动分配，也可以手动配置

4.4 Index:索引

Index是ES中最高层级的数据容器，类似于关系型数据库中的Database

每个Index都有自己的Mapping和Settings，可以存储多个Document，并且可以被分成多个Shard，每个Shard可以分配到不同的Node上

索引创建规则如下

索引名称：索引名称必须是小写字母，不能包含大写字母或下划线，只能包含字母、数字、连字符和点号
分片和副本：创建索引时需要指定分片和副本的数量。分片数量应该根据数据量、查询频率和硬件资源进行调整，以保证索引的性能。副本数量可以提高索引的可用性和容错能力
Mapping：Mapping用于定义索引中的文档结构，包括字段类型、分析器、数据格式等。合理地定义Mapping可以提高搜索和分析的性能
设置：设置包括索引级别和节点级别的设置。索引级别的设置包括分片和副本、Mapping、刷新间隔、缓存等。节点级别的设置包括JVM堆内存、文件描述符、线程池等
索引别名：索引别名是索引的可读名称，可以用于在查询时指定具体的索引。索引别名可以随时更改，可以将多个索引合并成一个别名

总的来说，ES索引创建的规则包括索引名称、分片和副本、Mapping、设置和索引别名等

4.5 Document:文档

es中的最小数据单元。一个document就像数据库中的一条记录。通常以json格式显示。多个 document存储于一个索引(Index)中

例如:

book document
{
"book_id": "1",
"book_name": "carl的笔记",
"book_desc": "carl呕心沥血写的菜谱，一定要好好研习", 
"category_id": "2",
"category_name": "java"
}

4.6 Field:字段

Field是Document中的属性，类似于关系型数据库中的列

Field可以是不同的数据类型，如字符串、数字、日期、布尔等

4.7 Type:类型

在早期的ES版本中，Type是指在一个Index中对数据进行分组的方式，类似于关系型数据库中的表

分析: 为什么要7.X版本去除Type?
因为关系型数据库比非关系型数据库的概念提出的早，而且很成熟，应用广泛。所以，后来很多 NoSQL(包括:MongoDB，Elasticsearch等)都参考并延用了传统关系型数据库的基本概念。由于需要有一个对应关系型数据库表的概念，所以type应运而生。那么为什么我们又需要把type去除呢?并且需要在7.X版本去除呢?
首先，我们可以看一下ES的版本演变。
在 5.X 版本中，一个 index 下可以创建多个 type;
在 6.X 版本中，一个 index下只能存在一个 type;
在7.X 版本中，直接去除了 type 的概念，就是说index 不再会有 type。
原因分析:
为何要去除 type 的概念?
答: 因为 Elasticsearch 设计初期，是直接查考了关系型数据库的设计模式，存在了 type(数据表)的概念
但是，其搜索引擎是基于 Lucene 的，这种 “基因”决定了 type 是多余的。 Lucene 的全文检索功能之所以快，是因为倒序索引的存在。而这种倒序索引的生成是基于 index 的，而并非 type。多个type 反而会减慢搜索的速度。

为了保持 Elasticsearch “一切为了搜索” 的宗旨，适当的做些改变(去除 type)也是无可厚非的，也是值得的。

为何不是在 6.X 版本开始就直接去除 type，而是要逐步去除type?

答:因为历史原因，前期 Elasticsearch 支持一个 index 下存在多个 type的，而且，有很多项目在使用 Elasticsearch 作为数据库。如果直接去除 type 的概念，不仅是很多应用 Elasticsearch 的项目将面临业务、功能和代码的大改，而且对于 Elasticsearch 官方来说，也是一个巨大的挑战(这个是伤筋动骨的大手术，很多涉及到 type源码是要修改的)。

所以，权衡利弊，采取逐步过渡的方式，最终，推迟到 7.X 版本才完成 “去除 type” 这个革命性的变革

4.8 shard:分片

index数据过大时，将index里面的数据，分为多个shard，分布式的存储在各个服务器上面。可以支持海量数据和高并发，提升性能和吞吐量，充分利用多台机器的cpu

4.9 replica:副本

在分布式环境下，任何一台机器都会随时宕机，如果宕机，index的一个分片没有，导致此index不能搜索。所以，为了保证数据的安全，我们会将每个index的分片进行备份，存储在另外的机器上。保证少数机器宕机es集群仍可以搜索。能正常提供查询和插入的分片我们叫做主分片(primary shard)，其余的我们就管他们叫做备份的分片(replica shard)

4.10 Mapping:映射

Mapping用于定义Index中的Document结构，包括Field名称、Field类型、分析器、数据格式等。Mapping的定义可以影响搜索和分析的性能。

4.11 对比

关系型数据库(比如Mysql)	非关系型数据库(Elasticsearch)
数据库Database	索引Index
表Table	索引Index(原为Type)
数据行Row	文档Document
数据列Column	字段Field
约束 Schema	映射Mapping

三、核心原理

1.文件存储

对应上面介绍的Document概念

ES是一个文档型数据库，在其中，一条数据就是一个文档，Json格式作为保存形式

将ES与MySql相关术语对应描述一条数据如下

一个 Elasticsearch 集群可以包含多个索引(数据库)，也就是说其中包含了很多类型(表)。这些类型中包含了很多的文档(行)，然后每个文档中又包含了很多的字段(列)

Elasticsearch的交互，可以使用 JavaAPI，也可以直接使用HTTP的Restful API方式

2.倒排表与分类索引

在上面的介绍中，可以知道在ES中索引对应数据库中的dataBase

上面4.4介绍过索引的简历规则，这里不再赘述

那么在ES中，索引是以什么结构存在的呢？先别急，先看个例子，引入一下概念

假设有三条结构化数据，存储在MySql中，如下所示

|ID  |Name    |Age    | Sex   | 
| -- |:------:| -----:| -----:| 
|1   |张三     |18     |Female 
|2   |李四     |50     |Male
|3   |王五     |18     |Male

那么这些数据，在ES当中是如何存储的呢？

首先是Name

| Term | Posting List |
| -- |:----:|
|张三 |	1	| 
|李四 |	2	| 
|王五 |	3	|

Age

| Term | Posting List |
| -- |:----:	|
| 50 | 2 			|
| 18 | [1,3]  |

Sex

| Term   | Posting List |
| -- 	   |	  :----:    |
| Female |      1       |
| Male   |    [2,3]     |

可以观察到，上面出现了两个列概念Term和Posting List

Term：分类索引
- 分类索引则是按照文档的主题或类别来建立索引的数据结构
Posting List：倒排表
- 倒排表是根据文档中的单词或词语来建立索引的数据结构

分类索引就是上面的分别根据Name，Age和Sex建立索引

倒排表就是每个分类索引里面实现的分词-ids的结构

从上面的结构，可以论证之前说的，在ES中，倒排索引使用分词作为key，将key出现在的文档id集合作为values，这就是简化的索引结构

但是像MySql会出现的数据量过大问题一样，当上面的倒排表中，数据量过大怎么办？此时遍历扫描查询效率必然会受到极大的限制

3.Term Dictionary(词典)

在ES中，每个字段Field都有自己的一个词典结构，用于快速查找当中的term值

那么词典到底是什么呢？

就像上面的Name列，词典存储的就是”张三”、”李四”和”王五”这三个词条

除了词条本身，词典还会存储一些元数据信息，比如每个词条出现的文档频率（Document Frequency），即包含该词条的文档数目，以及倒排索引中的位置信息等

词典的具体实现方式由ES来决定，可选择哈希表、红黑树等数据结构

4.Term Index(词典索引）

很明显，仅有词典还是不够的，因为当数据量上来之后，使用词典还是要全表扫描来找到词term，再去倒排表中找文档id，因此会考虑到去用索引结构加速term的查询

Term Index(词典索引）就是这个作用

那么如何实现词典索引呢？

主要分为基于树形的索引和基于哈希表的索引，此处主要介绍树形词典索引

索引树实现如上，它本质上是一颗前缀树，在树的节点中会存储词典的偏移量，从偏移量位置向后遍历，下面看一下他们的整体结构

用户查询时，先利用词典索引去词典中定位，再根据词典去倒排表中找到文档id

词典和倒排表可以存在内存中，也可以存储在磁盘中，上述样例是词典和倒排表都基于磁盘的存储，因为全部放在内存可能会占用空间过多

查找流程如下：

用户输入c，根据词典索引，找到c，根据c上的偏移量offset找到词典位置
读取词典carl，找到对应的倒排表中的位置，从而查出来对应的文档编码

为了加快访问速度，可以使词典索引存储在内存中，但是词典索引都放在内存中又会占用太多的空间，如何优化这个问题呢？

5.FST

FST，全称为finite state transducer，是一种有限状态自动机（finite state machine）的数据结构

FST 的基本思想是将一个有限状态自动机编码为一个紧凑的数据结构，并将其存储在内存中，以支持快速的查找和匹配操作。在 FST 中，每个状态都对应着一个整数编号，每个状态都可以转移到另一个状态，转移的过程可以使用一个字符或一组字符来触发。在实际的应用中，FST 还可以扩展为支持权重或成本，以支持更复杂的匹配操作

简单点说，FST就是用来压缩词典索引的，下面通过一个案例介绍FST实现思想

假设有以下字段和序号映射关系：

字段	序号
mop	0
moth	1
pop	2
star	3
stop	4
top	5

很明显，用Map结构可以存储这些对应关系，那么能不能对他们进行压缩，从而使用更少的空间来存储呢？

上图中，将单词拆分成单个字母，通过⭕和–>表示出来

在–>上，不显示表示权重为0

如果⭕后面出现分支，就标记权重，最后整条路径上的权重加起来就是这个单词对应的序号

例如stop，id就是3+0+1+0=4

但是这个树并不会包含所有的term，而是很多term的前缀，通过这些前缀快速定位到这个前缀所属的磁盘的block，再从这个block去找文档列表

为了压缩词典的空间，实际上每个block都只会保存block 内不同的部分，比如 mop 和 moth 在同一个以 mo 开头的block，那么在对应的词典里面只会保存 p 和th ，这样空间利用率提高了一倍

早期的ES模糊查询使用编辑距离来计算，使用FST之后将模糊查询效率提升了100倍以上

现在词典索引已经被压缩，可以通过词典索引+词典找到倒排表位置，文档肯定是存储在磁盘上的，但是倒排表就直接原样放到磁盘上吗？这样会不会占用大量磁盘空间？

假如1亿个文档，每个文档有10个字段，那单倒排表就需要数十亿个integer空间，不太现实

6.压缩-Frame Of Reference 索引帧

Frame Of Reference主要压缩的就是倒排表posting list

如果有上千万个同学，而世界上只有男/女这样两个性别，每个posting list都会有至少百万个文档id。 Elasticsearch是如何有效的对这些文档id压缩的呢?

在进行查询的时候经常会进行组合查询，比如查询同时包含man和woman的文档，那么就需要分别查出包含这两个单词的文档的id，然后取这两个id列表的交集;如果是查包含man或者woman的文档，那么就需要分别查出posting list然后取并集。为了能够高效的进行交集和并集的操作。为了方便压缩， Elasticsearch要求posting list是有序的(为了提高搜索的性能，再任性的要求也得满足)。同时为了减小存储空间，所有的id都会进行delta编码

举例

比如现在有id列表 [73, 300, 302, 332, 343, 372] ，转化成每一个id相对于前一个id的增量值(第一个id的前一个id默认是0，增量就是它自己)列表是 [73, 227, 2, 30, 11, 29] 。在这个新的列表里面，所有的id都是小于255的，所以每个id只需要一个字节（8bit）存储

实际上ES会做的更加精细，它会把所有的文档分成很多个block，每个block正好包含256个文档，然后单独对每个文档进行增量编码，计算出存储这个block里面所有文档最多需要多少位来保存每个id，并且把这个位数作为头信息(header)放在每个block 的前面。这个技术叫Frame of Reference（索引帧）

8个二进制位构成一个字节。这种压缩算法的原理就是通过增量，将原来的大数变成小数仅存储增量值，再精打细算按bit排好队，最后通过字节存储，而不是大大咧咧的尽管是2也是用int(4个字节)来存储

在返回结果的时候，其实也并不需要把所有的数据直接解压然后一股脑全部返回，可以直接返回一个迭代器 iterator ，直接通过迭代器的 next 方法逐一取出压缩的id，这样也可以极大的节省计算和内存开销

通过以上的方式可以极大的节省posting list的空间消耗，提高查询性能。不过ES为了提高filter过滤器查询的性能，还做了更多的工作，那就是缓存

7.缓存-Roaring Bitmaps 咆哮位图

ES会缓存频率比较高的filter查询，其中的原理也比较简单，即生成 (fitler, segment数据空间) 和id列表的映射，但是和倒排索引不同，我们只把常用的filter缓存下来而倒排索引是保存所有的，并且 filter缓存应该足够快，不然直接查询不就可以了。ES直接把缓存的filter放到内存里面，映射的posting list放入磁盘中

ES在filter缓存使用的压缩方式和倒排索引的压缩方式并不相同，filter缓存使用了roaring bitmap的数据结构，在查询的时候相对于上面的Frame of Reference方式CPU消耗要小，查询效率更高，代价就是需要的存储空间(磁盘)更多。

Roaring Bitmap是由int数组和bitmap这两个数据结构改良过的成果——int数组速度快但是空间消耗大，bitmap相对来说空间消耗小但是不管包含多少文档都需要12.5MB的空间，即使只有一个文件也要 12.5MB的空间，这样实在不划算，所以权衡之后就有了下面的Roaring Bitmap

Bitmap是一种数据结构，假设有某个posting list: [1,3,4,7,10]
对应的bitmap就是:[1,0,1,1,0,0,1,0,0,1]
非常直观，用0/1表示某个值是否存在，比如10这个值就对应第10位，对应的bit值是1，这样用一个字节就可以代表8个文档id，旧版本(5.0之前)的Lucene就是用这样的方式来压缩的，但这样的压缩方式仍然不够高效，如果有1亿个文档，那么需要12.5MB的存储空间，这仅仅是对应一个索引字段(我们往往会有很多个索引字段)。于是有人想出了Roaring bitmaps这样更高效的数据结构
Bitmap的缺点是存储空间随着文档个数线性增长，Roaring bitmaps需要打破这个魔咒就一定要用到某些指数特性

Roaring Bitmap首先会根据每个id的高16位分配id到对应的block里面，比如第一个block里面id应该都是在0到65535之间，第二个block的id在65536和131071之间
对于每一个block里面的数据，根据id数量分成两类
- 如果数量小于4096，就是用short数组保存
- 数量大于等于4096，就使用bitmap保存

即通过文档id的高16位散射到block上，block的结构则由散射过来的id数量决定

为什么选择4096作为分界线呢？

因为当数量小于4096的时候，如果用bitmap就需要8kB的空间，而使用2个字节的数组空间消耗就要少一点。比如只有2048个值，每个值2字节，一共只需要4kB就能保存，但是 bitmap需要8kB

8.倒排索引实现联合索引

上面讨论的都是单个索引的流程，那么如何使用倒排索引做联合索引呢？

两种实现方式：跳表或者bitset

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

首先是跳表，如下

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

假设有下面三个posting list需要联合索引:

如果使用跳表，对最短的posting list中的每个id，逐个在另外两个posting list中查找看是否存在，最后得到交集的结果

如果使用bitset(基于bitMap)，就很直观了，直接按位与，得到的结果就是最后的交集

注意，这是倒排索引实现联合索引的方式，不是说ES就是这样操作的

四、总结

**Elasticsearch的索引思路:**将磁盘里的东西尽量搬进内存，减少磁盘随机读取次数(同时也利用磁盘顺序读特性)，结合各种奇技淫巧的压缩算法，用及其苛刻的态度使用内存

所以，对于使用Elasticsearch进行索引时需要注意:

不需要索引的字段，一定要明确定义出来，因为默认是自动建索引的
同样的道理，对于String类型的字段，不需要analysis(分词)的也需要明确定义出来，因为默认也是会analysis的
选择有规律的ID很重要，随机性太大的ID(比如java的UUID)不利于查询

关于最后一点，个人认为有多个因素:

其中一个(也许不是最重要的)因素: 上面看到的压缩算法，都是对Posting list里的大量ID进行压缩的，那如果ID是顺序的，或者是有公共前缀等具有一定规律性的ID，压缩比会比较高;
另外一个因素: 可能是最影响查询性能的，应该是最后通过Posting list里的ID到磁盘中查找Document 信息的那步，因为Elasticsearch是分Segment存储的，根据ID这个大范围的Term定位到Segment的效率直接影响了最后查询的性能，如果ID是有规律的，可以快速跳过不包含该ID的Segment，从而减少不必要的磁盘读次数