一、参考资料
Elasticsearch-基本介绍
Spring Boot整合Elasticsearch
Elasticsearch 如何做到快速检索 - 倒排索引的秘密
lucene字典实现原理——FST
关于Lucene的词典FST深入剖析
二、基本概念
- 索引index：存储document文档数据的结构，类似于关系型数据库中的数据库
- 类型type：用于存储document的逻辑结构，相对于index来说，type是index的下级，类似于关系型数据库中的表
- 文档document：json格式，类似于关系型数据库中的行数据
三、倒排索引
- term：关键字
- Term index：字典树，一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。这棵树不会包含所有的term，它包含的是term的一些前缀。
- term dictionary：ES为了能快速查找到term，将所有的term排了一个序，二分法查找。
- postings list：所有包含特定term文档的id的集合。
3.1 FST（Finite State Transducers）
term index在内存中是以FST的数据结构保存的。
- 一种有限状态转移机。
- 空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间。
- 查询速度快。O(len(str))的查询时间复杂度。
对“cat”、“deep”、“do”、“dog”、“dogs”这5个单词进行插入构建FST（注：必须已排序）
3.2 postings list-Frame of Reference（FOR）
PostingList会使用Frame Of Reference（FOR）编码技术对里边的数据进行压缩，节约磁盘空间。
73+227+2+30+... ...
3.3 Roaring Bitmaps (for filter cache)
PostingList使用Roaring Bitmaps来对文档ID进行交并集操作。节省空间，快速得出交并集的结果。
将doc id拆成高16位，低16位（2^16整除、取余数）。对高位进行聚合 (以高位做 key，value 为有相同高位的所有低位数组)，根据低位的数据量 (不同高位聚合出的低位数组长度不相同)，使用不同的container(数据结构) 存储。
- len<4096ArrayContainer直接存值
- len>=4096BitmapContainer使用bitmap存储
分界线的来源：value的最大总数是为2^16=65536。假设以bitmap方式存储需要65536bit=8kb，而直接存值的方式，一个值2byte，4K个总共需要2byte✖️4K=8kb。所以当value总量<4k时，使用直接存值的方式更节省空间。
空间压缩主要体现在:
- 高位聚合 (假设数据中有100w个高位相同的值，原先需要100w✖️2byte，现在只要1✖️2byte)
- 低位压缩
3.4 skip list
如果查询的filter没有缓存，那么就用skip list的方式去遍历磁盘上的postings list。
首先选择最短的posting list，逐个在另外两个posting list中查找看是否存在，最后得到交集的结果。遍历的过程可以跳过一些元素，比如我们遍历到绿色的13的时候，就可以跳过蓝色的3了，因为3比13要小。
四、数据操作
一个Elasticsearch集群会有多个Elasticsearch节点，所谓节点实际上就是运行着Elasticsearch进程的机器。在众多的节点中，其中会有一个Master Node，它主要负责维护索引元数据、负责切换主分片和副本分片身份等工作，如果主节点挂了，会选举出一个新的主节点。
Elasticsearch最外层的是Index（相当于数据库表的概念）；一个Index的数据我们可以分发到不同的Node上进行存储，这个操作就叫做分片。
数据写入的时候是写到主分片，副本分片会复制主分片的数据，读取的时候主分片和副本分片都可以读。
4.1 数据写入
集群上的每个节点都是coordinating node（协调节点），协调节点表明这个节点可以做路由。比如节点1接收到了请求，但发现这个请求的数据应该是由节点2处理（因为主分片在节点2上），所以会把请求转发到节点2上。
- Elasticsearch会把数据先写入内存缓冲区，然后每隔1s刷新到文件系统缓存区（当数据被刷新到文件系统缓冲区以后，数据才可以被检索到）。所以Elasticsearch写入的数据需要1s才能查询到。
- 为了防止节点宕机，内存中的数据丢失，Elasticsearch会另写一份数据到日志文件上，但最开始的还是写到内存缓冲区，每隔5s才会将缓冲区的刷到磁盘中。所以：Elasticsearch某个节点如果挂了，可能会造成有5s的数据丢失。
- 等到磁盘上的translog文件大到一定程度或者超过了30分钟，会触发commit操作，将内存中的segement文件异步刷到磁盘中，完成持久化操作。
写内存缓冲区（定时去生成segement，生成translog），能够让数据能被索引、被持久化。最后通过commit完成一次的持久化。
每个Segment事实上是一些倒排索引的集合，只有经历了refresh操作之后，数据才能变成可检索的。
4.2 数据更新和删除
给对应的doc记录打上.del标识，如果是删除操作就打上delete状态，如果是更新操作就把原来的doc标志为delete，然后重新新写入一条数据。
每隔1s会生成一个segement文件，那segement文件会越来越多越来越多。Elasticsearch会有一个merge任务，会将多个segement文件合并成一个segement文件。在合并的过程中，会把带有delete状态的doc给物理删除掉。
4.3 数据查询
根据ID去查询具体的doc的流程：
- 检索内存的Translog文件
- 检索硬盘的Translog文件
- 检索硬盘的Segement文件
根据query去匹配doc的流程：
- 同时去查询内存和硬盘的Segement文件
Elasticsearch查询又分可以为三个阶段：
- QUERY_AND_FETCH（查询完就返回整个Doc内容）
- QUERY_THEN_FETCH（先查询出对应的Doc id，然后再根据Doc id匹配去对应的文档）
- DFS_QUERY_THEN_FETCH（先算分，再查询）
QUERY_THEN_FETCH总体的流程流程大概是：
- 客户端请求发送到集群的某个节点上。集群上的每个节点都是coordinate node（协调节点）
- 然后协调节点将搜索的请求转发到所有分片上（主分片和副本分片都行）
- 每个分片将自己搜索出的结果(doc id)返回给协调节点，由协调节点进行数据的合并、排序、分页等操作，产出最终结果。
- 接着由协调节点根据doc id去各个节点上拉取实际的document数据，最终返回给客户端。
