ES - 基础
ES简介篇
ES介绍
ElasticSearch是一种分布式全文搜索引擎，基于Lucene(全文搜索框架)开发而来。
Lucene是公认的迄今为止的最好用的搜索引擎库，但是他所提供的API对于我们使用者来说，是非常苦恼的，常要花费大量时间去熟悉学习。ES的出现就很好的解决了这个问题，良好的封装，易用的API，链式书写方式，开瓶即饮。
Lucene与es的关系
处理分词，构建倒排索引，等等，都是这个叫lucene的做的。那么能不能说这个lucene就是搜索引擎呢？ 还不能。lucene只是一个提供全文搜索功能类库的核心工具包，而真正使用它还需要一个完善的服务框架搭建起来的应用。 好比lucene是类似于发动机，而搜索引擎软件（ES,Solr）就是汽车。 目前市面上流行的搜索引擎软件，主流的就两款，elasticsearch和solr,这两款都是基于lucene的搭建的，可以独立部署启动的搜索引擎服务软件。由于内核相同，所以两者除了服务器安装、部署、管理、集群以外，对于数据的操作，修改、添加、保存、查询等等都十分类似。就好像都是支持sql语言的两种数据库软件。只要学会其中一个另一个很容易上手。 从实际企业使用情况来看，elasticSearch的市场份额逐步在取代solr，国内百度、京东、新浪都是基于elasticSearch实现的搜索功能。国外就更多了 像维基百科、GitHub、Stack Overflow等等也都是基于ES的。
ES使用场景
Elasticsearch 在速度和可扩展性方面都表现出色，而且还能够索引多种类型的内容
为用户提供按关键字查询的全文搜索功能。例如：一个在线网上商店，您可以在其中允许客户搜索您出售的产品。在这种情况下，您可以使用Elasticsearch 存储整个产品目录和库存，并为它们提供搜索和自动完成建议
实现企业海量数据的处理分析的解决方案。大数据领域的重要一份子，如著名的ELK框架(ElasticSearch,Logstash,Kibana)，收集日志或交易数据，并且要分析和挖掘此数据以查找趋势，统计信息，摘要或异常。
ES的特点
-
天然分片，天然集群
es 把数据分成多个shard，多个shard可以组成一份完整的数据，这些shard可以分布在集群中的各个机器节点中。随着数据的不断增加，集群可以增加多个分片，把多个分片放到多个机子上，已达到负载均衡，横向扩展。
在实际运算过程中，每个查询任务提交到某一个节点，该节点必须负责将数据进行整理汇聚，再返回给客户端，也就是一个简单的节点上进行Map计算，在一个固定的节点上进行Reduces得到最终结果向客户端返回。
-
天然索引
ES 所有数据都是默认进行索引的，这点和mysql正好相反，mysql是默认不加索引，要加索引必须特别说明，ES只有不加索引才需要说明。 而ES使用的是倒排索引和Mysql的B+Tree索引不同。
传统关系性数据库
弊端：
对于传统的关系性数据库对于关键词的查询，只能逐字逐行的匹配，性能非常差。
匹配方式不合理，比如搜索“小密手机” ，如果用like进行匹配， 根本匹配不到。但是考虑使用者的用户体验的话，除了完全匹配的记录，还应该显示一部分近似匹配的记录，至少应该匹配到“手机”。
ES的工作原理
[图片上传失败...(image-ebc3db-1658974200412)]
ES写入
客户端选择一个node发送请求过去，这个node就是coordinating node（协调节点）
coordinating node，对document进行路由（根据documentID路由），将请求转发给对应的node（有primary shard）
实际的node上的primary shard处理请求，然后将数据同步到replica node
coordinating node，如果发现primary node和所有replica node都搞定之后，就返回响应结果给客户端
ES读出
查询，GET某一条数据，写入了某个document，这个document会自动给你分配一个全局唯一的id，doc id，同时也是根据doc id进行hash路由到对应的primary shard上面去。也可以手动指定doc id，比如用订单id，用户id。
你可以通过doc id来查询，会根据doc id进行hash，判断出来当时把doc id分配到了哪个shard上面去，从那个shard去查询
客户端发送请求到任意一个node，成为coordinate node
coordinate node对document进行路由，将请求转发到对应的node，此时会使用round-robin随机轮询算法，在primary shard以及其所有replica中随机选择一个，让读请求负载均衡
接收请求的node返回document给coordinate node
coordinate node返回document给客户端
ES搜索
es最强大的是做全文检索，就是比如你有三条数据
1.java真好玩儿啊
2.java好难学啊
- j2ee特别牛
你根据java关键词来搜索，将包含java的document给搜索出来。
客户端发送请求到一个coordinate node(随意选择的)
协调节点将搜索请求转发到所有的shard对应的primary shard或replica shard也可以
query phase：每个shard将自己的搜索结果（其实就是一些doc id），返回给协调节点，由协调节点进行数据的合并、排序、分页等操作，产出最终结果
fetch phase：接着由协调节点，根据doc id去各个节点上拉取实际的document数据，最终返回给客户端。
写入原理
-
elasticsearch写入数据时涉及到的核心概念讲解：
segment file: 存储倒排索引的文件，每个segment本质上就是一个倒排索引，每秒都会生成一个segment文件，当文件过多时es会自动进行segment merge（合并文件），合并时会同时将已经标注删除的文档物理删除
commit point（重点理解）: 记录当前所有可用的segment，每个commit point都会维护一个.del文件，即每个.del文件都有一个commit point文件（es删除数据本质是不属于物理删除），当es做删改操作时首先会在.del文件中声明某个document已经被删除，文件内记录了在某个segment内某个文档已经被删除，当查询请求过来时在segment中被删除的文件是能够查出来的，但是当返回结果时会根据commit point维护的那个.del文件把已经删除的文档过滤掉
translog日志文件: 为了防止elasticsearch宕机造成数据丢失保证可靠存储，es会将每次写入数据同时写到translog日志中(图中会有详解)。
os cache的理解：操作系统里面，磁盘文件其实都有一个东西，叫做os cache，操作系统缓存，就是说数据写入磁盘文件之前，会先进入os cache，先进入操作系统级别的一个内存缓存中去
-
写数据的过程
先写入buffer，在buffer里的时候数据是搜索不到的；同时将数据写入translog日志文件
-
如果buffer快满了，或者到一定时间，就会将buffer数据refresh到一个新的segment file中，但是此时数据不是直接进入segment file的磁盘文件的，而是先进入os cache的。这个过程就是refresh
每隔1秒钟，es将buffer中的数据写入一个新的segment file，每秒钟会产生一个新的磁盘文件，segment file，这个segment file中就存储最近1秒内buffer中写入的数据
但是如果buffer里面此时没有数据，那当然不会执行refresh操作咯，每秒创建一个空的segment file，如果buffer里面有数据，默认1秒钟执行一次refresh操作，刷入一个新的segment file中。
只要buffer中的数据被refresh操作，刷入os cache中，就代表这个数据就可以被搜索到了。
为什么叫es是准实时的？NRT，near real-time，准实时。默认是每隔1秒refresh一次的，所以es是准实时的，因为写入的数据1秒之后才能被看到。
可以通过es的restful api或者java api，手动执行一次refresh操作，就是手动将buffer中的数据刷入os cache中，让数据立马就可以被搜索到。
只要数据被输入os cache中，buffer就会被清空了，因为不需要保留buffer了，数据在translog里面已经持久化到磁盘去一份了
只要数据进入os cache，此时就可以让这个segment file的数据对外提供搜索了。
-
重复1~3步骤，新的数据不断进入buffer和translog，不断将buffer数据写入一个又一个新的segment file中去，每次refresh完buffer清空，translog保留。随着这个过程推进，translog会变得越来越大。当translog达到一定长度的时候，就会触发commit操作。
buffer中的数据，倒是好，每隔1秒就被刷到os cache中去，然后这个buffer就被清空了。所以说这个buffer的数据始终是可以保持住不会填满es进程的内存的
每次一条数据写入buffer，同时会写入一条日志到translog日志文件中去，所以这个translog日志文件是不断变大的，当translog日志文件大到一定程度的时候，就会执行commit操作。
commit操作发生第一步，就是将buffer中现有数据refresh到os cache中去，清空buffer
将一个commit point写入磁盘文件，里面标识着这个commit point对应的所有segment file
强行将os cache中目前所有的数据都fsync到磁盘文件中去
-
translog日志文件的作用是什么？就是在你执行commit操作之前，数据要么是停留在buffer中，要么是停留在os cache中，无论是buffer还是os cache都是内存，一旦这台机器死了，内存中的数据就全丢了。
所以需要将数据对应的操作写入一个专门的日志文件，translog日志文件中，一旦此时机器宕机，再次重启的时候，es会自动读取translog日志文件中的数据，恢复到内存buffer和os cache中去。
commit操作：1、写commit point；2、将os cache数据fsync强刷到磁盘上去；3、清空translog日志文件
translog其实也是先写入os cache的，默认每隔5秒刷一次到磁盘中去，所以默认情况下，可能有5秒的数据会仅仅停留在buffer或者translog文件的os cache中，如果此时机器挂了，会丢失5秒钟的数据。但是这样性能比较好，最多丢5秒的数据。也可以将translog设置成每次写操作必须是直接fsync到磁盘，但是性能会差很多。
删除
如果是删除操作，commit的时候会生成一个.del文件，里面将某个doc标识为deleted状态，那么搜索的时候根据.del文件就知道这个doc被删除了
如果是更新操作，就是将原来的doc标识为deleted状态，然后新写入一条数据
buffer每次refresh一次，就会产生一个segment file，所以默认情况下是1秒钟一个segment file，segment file会越来越多，此时会定期执行merge。
每次merge的时候，会将多个segment file合并成一个，同时这里会将标识为deleted的doc给物理删除掉，然后将新的segment file写入磁盘，这里会写一个commit point，标识所有新的segment file，然后打开segment file供搜索使用，同时删除旧的segment file
ES倒排索引
Elasticsearch 索引指相互关联的文档集合。Elasticsearch 会以 JSON 文档的形式存储数据。每个文档都会在一组键 ( 字段或属性的名称 ) 和它们对应的值 ( 字符串、数字、布尔值、日期、数值组、地理位置或其他类型的数据 ) 之间建立联系。
Elasticsearch 使用的是一种名为倒排索引的数据结构，这一结构的设计可以允许十分快速地进行全文本搜索。倒排索引会列出在所有文档中出现的每个特有词汇，并且可以找到包含每个词汇的全部文档。
在索引过程中，Elasticsearch 会存储文档并构建倒排索引，这样用户便可以近实时地对文档数据进行搜索。索引过程是在索引 API 中启动的，通过此 API 您既可向特定索引中添加 JSON 文档，也可更改特定索引中的 JSON 文档。
倒排索引（Inverted Index）也叫反向索引，有反向索引必有正向索引。通俗地来讲，正向索引是通过key找value，反向索引则是通过value找key。
[图片上传失败...(image-ff6b17-1658972353472)]
倒排索引的生成过程
下面通过一个例子来说明下倒排索引的生成过程
假设目前有以下两个文档内容：
<pre class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" lang="xml" cid="n137" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; background: rgb(51, 51, 51); position: relative !important; padding: 10px 10px 10px 30px; width: inherit; color: rgb(184, 191, 198); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">苏州街维亚大厦
桔子酒店苏州街店</pre>
其处理步骤如下：
1、正排索引给每个文档进行编号，作为其唯一的标识。
| 文档 id | content |
|---|---|
| 1 | 苏州街维亚大厦 |
| 2 | 桔子酒店苏州街店 |
2、生成倒排索引：
首先要对字段的内容进行分词，分词就是将一段连续的文本按照语义拆分为多个单词，这里两个文档包含的关键词有：苏州街、维亚大厦… 然后按照单词来作为索引，对应的文档 id 建立一个链表，就能构成上述的倒排索引结构。 Word 文档 id 苏州街 1,2 维亚大厦 1 维亚 1 桔子 2 酒店 2 大赛 1 有了倒排索引，能快速、灵活地实现各类搜索需求。整个搜索过程中我们不需要做任何文本的模糊匹配。
例如，如果需要在上述两个文档中查询 苏州街桔子 ，可以通过分词后 苏州街 查到 1、2，通过 桔子 查到 2，然后再进行取交取并等操作得到最终结果。
[图片上传失败...(image-ab50e1-1658972353472)]
倒排索引的结构
根据倒排索引的概念，我们可以用一个 Map来简单描述这个结构。这个 Map 的 Key 的即是分词后的单词，这里的单词称为 Term，这一系列的 Term 组成了倒排索引的第一个部分 —— Term Dictionary (索引表，可简称为 Dictionary)。
倒排索引的另一部分为 Postings List（记录表），也对应上述 Map 结构的 Value 部分集合。
记录表由所有的 Term 对应的数据（Postings） 组成，它不仅仅为文档 id 信息，可能包含以下信息：
文档 id（DocId, Document Id），包含单词的所有文档唯一 id，用于去正排索引中查询原始数据。 词频（TF，Term Frequency），记录 Term 在每篇文档中出现的次数，用于后续相关性算分。 位置（Position），记录 Term 在每篇文档中的分词位置（多个），用于做词语搜索（Phrase Query）。 偏移（Offset），记录 Term 在每篇文档的开始和结束位置，用于高亮显示等。
[图片上传失败...(image-edd623-1658972353472)]
Lucene 倒排索引实现
全文搜索引擎在海量数据的情况下是需要存储大量的文本，所以面临以下问题：
Dictionary 是比较大的（比如我们搜索中的一个字段可能有上千万个 Term）
Postings 可能会占据大量的存储空间（一个Term多的有几百万个doc）
因此上面说的基于 Map 的实现方式几乎是不可行的。
在海量数据背景下，倒排索引的实现直接关系到存储成本以及搜索性能。
为此，Lucene 引入了多种巧妙的数据结构和算法。其倒排索引实现拥有以下特性：
以较低的存储成本存储在磁盘 （索引大小大约为被索引文本的20-30％）
快速读写
下面将根据倒排索引的结构，按 Posting List 和 Terms Dictionary 两部分来分析 Lucene 中的实现。
Posting List 实现
PostingList 包含文档 id、词频、位置等多个信息，这些数据之间本身是相对独立的，因此 Lucene 将 Postings List 被拆成三个文件存储：
doc后缀文件：记录 Postings 的 docId 信息和 Term 的词频
pay后缀文件：记录 Payload 信息和偏移量信息
pos后缀文件：记录位置信息
基本所有的查询都会用 .doc 文件获取文档 id，且一般的查询仅需要用到 .doc 文件就足够了，只有对于近似查询等位置相关的查询则需要用位置相关数据。
三个文件整体实现差不太多，这里以.doc 文件为例分析其实现。
.doc 文件存储的是每个 Term 对应的文档 Id 和词频。每个 Term 都包含一对 TermFreqs 和 SkipData 结构。
其中 TermFreqs 存放 docId 和词频信息，SkipData 为跳表信息，用于实现 TermFreqs 内部的快速跳转。
[图片上传失败...(image-9f65f3-1658972353472)]
TermFreqs
TermFreqs 存储文档号和对应的词频，它们两是一一对应的两个 int 值。Lucene 为了尽可能的压缩数据，采用的是混合存储 ，由 PackedBlock 和 VIntBlocks 两种结构组成。
PackedBlock
其采用 PackedInts 结构将一个 int[] 压缩打包成一个紧凑的 Block。它的压缩方式是取数组中最大值所占用的 bit 长度作为一个预算的长度，然后将数组每个元素按这个长度进行截取，以达到压缩的目的。
例如：一个包含128个元素的 int 数组中最大值的是 2，那么预算长度为2个 bit, PackedInts 的长度仅是 2 * 128 / 8 = 32个字节，然后就可以通过4个 long 值存储。
[图片上传失败...(image-c75215-1658972353472)]
VIntBlock
VIntBlock 是采用 VInt 来压缩 int 值，对于绝大多数语言，int 型都占4个字节，不论这个数据是1、100、1000、还是1000,000。VInt 采用可变长的字节来表示一个整数。数值较大的数，使用较多的字节来表示，数值较少的数，使用较少的字节来表示。每个字节仅使用第1至第7位(共7 bits)存储数据，第8位作为标识，表示是否需要继续读取下一个字节。
举个例子：
整数130为 int 类型时需要4个字节，转换成 VInt 后仅用2个字节，其中第一个字节的第8位为1，标识需要继续读取第二个字节。
[图片上传失败...(image-13171a-1658972353472)]
根据上述两种 Block 的特点，Lucene 会每处理包含 Term 的128篇文档，将其对应的 DocId 数组和 TermFreq 数组分别处理为 PackedDocDeltaBlock 和 PackedFreqBlock 的 PackedInt 结构，两者组成一个 PackedBlock，最后不足128的文档则采用 VIntBlock 的方式来存储。
[图片上传失败...(image-b6b69c-1658972353472)]
SkipData
在搜索中存在将每个 Term 对应的 DocId 集合进行取交集的操作，即判断某个 Term 的 DocId 在另一个 Term 的 TermFreqs 中是否存在。TermFreqs 中每个 Block 中的 DocId 是有序的，可以采用顺序扫描的方式来查询，但是如果 Term 对应的 doc 特别多时搜索效率就会很低，同时由于 Block 的大小是不固定的，我们无法使用二分的方式来进行查询。因此 Lucene 为了减少扫描和比较的次数，采用了 SkipData 这个跳表结构来实现快速跳转。 调表
跳表是在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。
实质就是一种可以进行二分查找的有序链表。
[图片上传失败...(image-5f8885-1658972353472)]
SkipData结构
在 TermFreqs 中每生成一个 Block 就会在 SkipData 的第0层生成一个节点，然后第0层以上每隔 N 个节点生成一个上层节点。
每个节点通过 Child 属性关联下层节点，节点内 DocSkip 属性保存 Block 的最大的 DocId 值，DocBlockFP、PosBlockFP、PayBlockFP 则表示 Block 数据对应在 .pay、.pos、.doc 文件的位置。
[图片上传失败...(image-64aefb-1658972353472)]
Posting 最终数据
Posting List 采用多个文件进行存储，最终我们可以得到每个 Term 的如下信息：
SkipOffset：用来描述当前 term 信息在 .doc 文件中跳表信息的起始位置。
DocStartFP：是当前 term 信息在 .doc 文件中的文档 ID 与词频信息的起始位置。
PosStartFP：是当前 term 信息在 .pos 文件中的起始位置。
PayStartFP：是当前 term 信息在 .pay 文件中的起始位置。
Term Dictionary 实现
Terms Dictionary（索引表）存储所有的 Term 数据，同时它也是 Term 与 Postings 的关系纽带，存储了每个 Term 和其对应的 Postings 文件位置指针。
[图片上传失败...(image-696922-1658972353472)]
数据存储
Terms Dictionary 通过 .tim 后缀文件存储，其内部采用 NodeBlock 对 Term 进行压缩前缀存储，处理过程会将相同前缀的的 Term 压缩为一个 NodeBlock，NodeBlock 会存储公共前缀，然后将每个 Term 的后缀以及对应 Term 的 Posting 关联信息处理为一个 Entry 保存到 Block。
[图片上传失败...(image-f4187d-1658972353472)]
在上图中可以看到 Block 中还包含了 Block，这里是为了处理包含相同前缀的 Term 集合内部部分 Term 又包含了相同前缀。
举个例子，在下图中为公共前缀为 a 的 Term 集合，内部部分 Term 的又包含了相同前缀 ab，这时这部分 Term 就会处理为一个嵌套的 Block。 [图片上传失败...(image-44da49-1658972353472)]
数据查找
Terms Dictionary 是按 NodeBlock 存储在.tim 文件上。当文档数量越来越多的时，Dictionary 中的 Term 也会越来越多，那查询效率必然也会逐渐变低。
因此需要一个很好的数据结构为 Dictionary 建构一个索引，这就是 Terms Index(.tip文件存储)，Lucene 采用了 FST 这个数据结构来实现这个索引。 FST
FST, 全称 Finite State Transducer（有限状态转换器）。
它具备以下特点：
给定一个 Input 可以得到一个 output，相当于 HashMap
共享前缀、后缀节省空间，FST 的内存消耗要比 HashMap 少很多
词查找复杂度为 O(len(str))
构建后不可变更
如下图为 mon/1，thrus/4，tues/2 生成的 FST，可以看到 thrus 和 tues 共享了前缀 t 以及后缀 s。
[图片上传失败...(image-448a13-1658972353472)]
根据 FST 就可以将需要搜索 Term 作为 Input，对其途径的边上的值进行累加就可以得到 output，下述为以 input 为 thrus 的读取逻辑：
初始状态0
输入t， FST 从0 -> 3， output=2
输入h，FST 从3 -> 4， output=2+2=4
输入r， FST 从4 -> 5， output=4+0
输入u，FST 从5 -> 7， output=4+0
输入s， FST 到达终止节点，output=4+0=4
那么 Term Dictionary 生成的 FST 对应 input 和 output 是什么呢？可能会误认为 FST 的 input 是 Dictionary 中所有的 Term，这样通过 FST 就可以找到具体一个 Term 对应的 Posting 数据。
实际上 FST 是通过 Dictionary 的每个 NodeBlock 的前缀构成，所以通过 FST 只可以直接找到这个 NodeBlock 在 .tim 文件上具体的 File Pointer, 然后还需要在 NodeBlock 中遍历 Entry 匹配后缀进行查找。
因此它在 Lucene 中充当以下功能：
快速试错，即是在 FST 上找不到可以直接跳出不需要遍历整个 Dictionary，类似于 BloomFilter。
快速定位 Block 的位置，通过 FST 是可以直接计算出 Block 的在文件中位置。
FST 也是一个 Automation(自动状态机)。这是正则表达式的一种实现方式，所以 FST 能提供正则表达式的能力。通过 FST 能够极大的提高近似查询的性能，包括通配符查询、SpanQuery、PrefixQuery 等。
倒排查询逻辑
在介绍了索引表和记录表的结构后，就可以得到 Lucene 倒排索引的查询步骤：
通过 Term Index 数据（.tip文件）中的 StartFP 获取指定字段的 FST
通过 FST 找到指定 Term 在 Term Dictionary（.tim 文件）可能存在的 Block
将对应 Block 加载内存，遍历 Block 中的 Entry，通过后缀（Suffix）判断是否存在指定 Term
存在则通过 Entry 的 TermStat 数据中各个文件的 FP 获取 Posting 数据
如果需要获取 Term 对应的所有 DocId 则直接遍历 TermFreqs，如果获取指定 DocId 数据则通过 SkipData 快速跳转
[图片上传失败...(image-8a42e7-1658972353472)]
Lucene 数值类型处理
上述 Terms Dictionary 与 Posting List 的实现都是处理字符串类型的 Term，而对于数值类型，如果采用上述方式实现会存在以下问题：
数值潜在的 Term 可能会非常多，比如是浮点数，导致查询效率低 无法处理多维数据，比如经纬度 所以 Lucene 为了支持高效的数值类或者多维度查询，引入了 BKDTree。 KDTree
BKDTree 是基于 KDTree，KDTree 实现起来很像是一个二叉查找树。主要的区别是，KDTree 在不同的层使用的是不同的维度值。
下面是一个2维树的样例 ，其第一层以 x 为切分维度，将 x>30的节点传递给右子树，x<30的传递给左子树，第二层再按 y 维度切分，不断迭代到所有数据都被建立到 KD Tree 的节点上为止。
[图片上传失败...(image-786a23-1658972353472)]
BKDTree
BKD 树是 KD 树和 B+ 树的组合，拥有以下特性
内部 node 必须是一个完全二叉树
叶子节点存储点数据，降低层高度，减少磁盘 IO
[图片上传失败...(image-c90928-1658972353472)]
