索引流程
更新和删除文档的流程
- 删除和更新也都是写操作，但是Elasticsearch中的文档是不可变的，因此不能被删除或者改动以展示其变更；
- 磁盘上的每个段都有一个相应的.del文件。当删除请求发送后，文档并没有真的被删除，而是在.del文件中被标记为删除。该文档依然能匹配查询，但是会在结果中被过滤掉。当段合并时，在.del文件中被标记为删除的文档将不会被写入新段。
- 在新的文档被创建时，Elasticsearch会为该文档指定一个版本号，当执行更新时，旧版本的文档在.del文件中被标记为删除，新版本的文档被索引到一个新段。旧版本的文档依然能匹配查询，但是会在结果中被过滤掉。
ElasticSearch不让索引改变有以下优点： 1）不需要加锁，提升了并发性能。 2）查询出的数据就能一直保存在缓存中，比如过滤查询filter就使用了缓存。 3）可以节省cpu和io的开销
Elasticsearch搜索的流程
- 搜索被执行成一个两阶段过程，我们称之为Query Then Fetch；
- 在初始查询阶段时，查询会广播到索引中每一个分片拷贝（主分片或者副本分片）。每个分片在本地执行搜索并构建一个匹配文档的大小为from + size 的优先队列。PS：在搜索的时候是会查询Filesystem Cache的，但是有部分数据还在Memory Buffer，所以搜索是近实时的。
- 每个分片返回各自优先队列中所有文档的ID 和排序值 给协调节点，它合并这些值到自己的优先队列中来产生一个全局排序后的结果列表。
- 接下来就是取回阶段，协调节点辨别出哪些文档需要被取回并向相关的分片提交多个GET 请求。每个分片加载并丰富文档，如果有需要的话，接着返回文档给协调节点。一旦所有的文档都被取回了，协调节点返回结果给客户端。
- Query Then Fetch的搜索类型在文档相关性打分的时候参考的是本分片的数据，这样在文档数量较少的时候可能不够准确，DFS Query Then Fetch增加了一个预查询的处理，询问Term和Document frequency，这个评分更准确，但是性能会变差。
搜索拆解为“ query then fetch” 两个阶段。 query 阶段的目的：定位到位置，但不取。 步骤拆解如下：
1、假设一个索引数据有5 主+1 副本共10 分片，一次请求会命中（主或者副本分片中） 的一个。 2、每个分片在本地进行查询，结果返回到本地有序的优先队列中。 3、第2步骤的结果发送到协调节点， 协调节点产生一个全局的排序列表。 fetch 阶段的目的：取数据。 由节点获取所有文档，返回给客户端。
Elasticsearch集群脑裂问题
脑裂问题可能的成因
网络问题：集群间的网络延迟导致一些节点访问不到master，认为master挂掉了从而选举出新的master，并对master上的分片和副本标红，分配新的主分片
节点负载：主节点的角色既为master又为data，访问量较大时可能会导致ES停止响应造成大面积延迟，此时其他节点得不到主节点的响应认为主节点挂掉了，会重新选取主节点。
内存回收：data节点上的ES进程占用的内存较大，引发JVM的大规模内存回收，造成ES进程失去响应。
脑裂问题解决方案
减少误判：discovery.zen.ping_timeout节点状态的响应时间，默认为3s，可以适当调大，如果master在该响应时间的范围内没有做出响应应答，判断该节点已经挂掉了。调大参数（如6s，discovery.zen.ping_timeout:6），可适当减少误判。
选举触发: discovery.zen.minimum_master_nodes:1
该参数是用于控制选举行为发生的最小集群主节点数量。当备选主节点的个数大于等于该参数的值， 且备选主节点中有该参数个节点认为主节点挂了，进行选举。官方建议为（n/2）+1，n为主节点个数 （即有资格成为主节点的节点个数）
角色分离：即master节点与data节点分离，限制角色
主节点配置为：node.master: true node.data: false
从节点配置为：node.master: false node.data: true
在并发情况下，Elasticsearch如何保证读写一致
- 可以通过版本号使用乐观并发控制，以确保新版本不会被旧版本覆盖，由应用层来处理具体的冲突；
- 另外对于写操作，一致性级别支持quorum/one/all，默认为quorum，即只有当大多数分片可用时才允许写操作。但即使大多数可用，也可能存在因为网络等原因导致写入副本失败，这样该副本被认为故障，分片将会在一个不同的节点上重建。
- 对于读操作，可以设置replication为sync(默认)，这使得操作在主分片和副本分片都完成后才会返回；如果设置replication为async时，也可以通过设置搜索请求参数_preference为primary来查询主分片，确保文档是最新版本。
部分参考 知乎
倒排索引如何存储数据
知道了倒排索引的搜索过程，那么倒排索引的数据又是如何存储的呢？
回答这个问题之前我们先来看另一个问题，那就是建立索引的目的是什么？最直接的目的肯定是为了加快检索速度，而为了达到这个目的，那么在不考虑其他因素的情况下，必然是需要占用的空间越少越好，而为了减少占用空间，可能就需要压缩之后再进行存储，而压缩之后又涉及到解压缩，所以采用的压缩算法也需要能达到快速压缩和解压的目的。
FOR 压缩
FOR 压缩算法即 Frame Of Reference。这种算法比较简单，也有一定的局限性，因为其对存储的文档 id 有一定要求。
假设现在有一亿个文档，对应的文档 id 就是从 1 开始自增。假设现在关键字 elasticsearch 存在于 1000W 个文档中，而这 1000W 个文档恰好就是从 1 到 1000W，那么假如不采用任何压缩算法，直接进行存储需要占用多少空间？
int 类型占用了 4 个字节，而 1000W 这个数量级需要 2 的 24 次方，也就是说如果用二进制来存储，在不考虑符号位的情况下也需要 24 个 bit 才能存储，而因为 Posting list TF 是一个数组，所以为了能解析出数据，文档 id=1 的数据也需要用 24 个 bit 来进行存储，这样就会极大的浪费了空间。
为了解决这个问题，我们就需要使用 FOR 算法，FOR 算法并不直接存储文档 id，而是存储差值，像这种这么规律的文档 id，差值都是 1，而 1 转成二进制就可以只使用 1 个 bit 进行存储，这样就只需要 1000W 个 bit 的空间来进行存储就够了，相比较直接存储原始文档 id 的情况下，这种场景采用 FOR 算法大大减少了空间。
上面举的这个例子是比较理想的情况，然而实际上这种概率是比较小的，那我们再来看下面这一组文档 id：
1,9,15,45,68,323,457
这个数组计算差值后得到下面这个数组：
8,6,30,23,255,134
这个时候如果还是直接用普通差值的算法，虽然也能节省空间，但是却并不是最优的一种解决方案，那么这个时候有没有一种更高效的方法来进行存储呢？
我们观察下这个差值数组，发现这个数组可以进一步拆分成两组：
- [8,6,30,23]：这一组最大值为 30，只需要 5 个比特就能进行存储。
- [255,134]：这一组最大值为 255，需要 8 个比特就能存储。 这么拆分之后，原始数据需要用 32_7=224 个比特（原始数据直接用 int 存储），普通差值需要 8_6=48 个比特，而经过分组差值拆分之后只需要 5_4+8_2=36 个比特，进一步压缩了空间，这种优势随着数据量的增加会更加明显。
但是不管采用哪种方案都有一个问题，那就是进行差值或者拆分之后，怎么还原数据，解压的时候怎么知道差值数组内的元素占用空间大小？
所以对每一个数据，还需要一块一个字节的空间大小来存储当前数组内元素占用的比特数，所以分组并不是越细越好，假如对每一个差值元素都单独存储，那么反而会比不分组更浪费空间，反之，如果每个分组内的元素足够多，那么存储占用空间的这一个字节反带来的影响就会更小或者忽略不计。
RBM 压缩
上面例子中介绍的差值都不会大相径庭，那么假如我们差值计算之后得到的数组，其每个元素差别都很大呢？比如说下面这个文档 id 数组：
1000,62101,131385,132052,191173,196658
这个数组大家可以去计算一下差值，计算之后会发现一个大一个小，两个差值之间差距很大，所以这种方式就不适合于用 FOR 压缩，所以我们就需要有另外的压缩算法来提升效率，这就是 RBM 压缩。 RBM 压缩算法的核心思想是：将 32 位无符号整数按照高 16 位进行划分容器，即最多可能有 65536 个 container。因为 65536 实际上就是 2 的 16 次方，而一个无符号 int 类型正好是需要 32 位进行存储，划分为高低位正好两边都是 16 位，也就是最多 65536 个。
划分之后根据高 16 位去找 container（比如高 16 位计算的结果是 1 就去找 container_1，2 就去找 container_2，依次类推），找到之后如果发现容器不存在，那么就会新建一个容器，并且把低 16 位存入容器内，如果容器存在，就直接将低 16 位存入容器。
这样就会出现一个现象：那就是容器最多有 65536 个，而每个容器内的元素也恰好最多是 65536 个元素。
也就是上面的数组经过计算就会得到以下容器（container_1 没有元素）：
如果说大家觉得上面的高低 16 位不好理解，那么可以这么理解，我们把数组中的元素全部除以 65536，对其取模，每得到一个模就创建一个容器，而其余数就放入对应的模所对应的容器中。因为一个 int 类型就是 2 的 32 次方，正好是 65536 的平方。
经过运算之后得到容器，那么容器中的元素又该如何进行存储呢？可以选择直接存储，也可以选择其他更高效的存储方式。在 RBM 算法中，总共有三种容器类型，分别采用不同的方法来存储容器中的元素：
- ArrayContainer
ArrayContainer 采用 short 数组来进行存储，因为每个容器中的元素最大值就是 65535，采用 2 个字节进行存储。这种存储方式的特点是随着元素个数的增多，所需空间会一直增大。
- BitmapContainer
BitmapContainer 采用位图的方式进行存储，也就是固定创建一个 65536 长度的容器，容器中每个元素只用一个比特进行存储，某一个位置有元素则存储 1，没有元素则存储为 0。这种存储方式的特点是空间固定就是占用 65536 个比特，也就是大小固定为 8kb。
- RunContainer
RunContainer 比较特殊，在特定场景下会使用，比如文档 id 从 1-100 是连续的，那么采用这种容器就可以直接存 1,99，表示 1 后面有 99 个连续的数字，再比如 1,2,3,4,5,6,10,11,12,13 可以被压缩为 1,5,10,3，表示 1 后面有 5 个连续数字，10 后面有 3 个连续数字。
至于每次存储采用什么容器，需要进行一下判定，比如 ArrayContainer，当存储的元素少于 4096 个时，他会比 BitmapContainer 占用更少空间，而当大于 4096 个元素时，采用 ArrayContainer 所需要的空间就会大于 8kb，那么采用 BitmapContainer 就会占用更少空间。
倒排索引如何存储
前面我们讲了 es 中的倒排索引采用的是什么压缩算法进行压缩，那么压缩之后的数据是如何落地到磁盘的呢？采用的是什么数据结构呢？
字典树（Tria Tree）
字典树又称之为前缀树（Prefix Tree），是一种哈希树的变种，可以用于搜索时的自动补全、拼写检查、最长前缀匹配等。
字典树有以下三个特点：
- 根节点不包含字符，除根节点外的其余每个节点都只包含一个字符。
- 从根节点到某一节点，将路径上经过的所有字符连接起来，即为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
下图所示就是在数据结构网站上依次输入以下单词（AFGCC、AFG、ABP、TAGCC）后生成的一颗字典树：
上图中可以发现根节点没有字母，除了根节点之外其余节点有白色和绿色两种颜色之分，这两种颜色的节点有什么区别呢？
绿色的节点表示当前节点是一个 Final 节点，也就是说当前节点是某一个单词的结束节点，搜索的时候当发现末尾节点是一个 Final 节点则表示当前字母存在，否则表示不存在。
比如我现在搜索 ABP，从根节点往下找的时候，最后发现 P 是一个 Final 节点，那就表示当前树中存在字符串 ABP，如果搜索 AFGC，虽然也能找到这些字母，但是 C 并不是一个 Final 节点，所以字符串 AFGC 并不存在。
不过字典树存在一个问题，上图中就可以体现出来，比如第二列中的后缀 FGCC 和 第三列中的 GCC 其实最后三个字符是重复的，但是这些重复的字符串都单独存储了，并没有被复用，也就是说字典树没有解决后缀共用问题，只解决了前缀共用（这也是字典树又被称之为前缀树的原因）。当数据量达到一定级别的时候，只共享前缀不共享后缀也会带来很多空间的浪费，那么如何来解决这个问题呢？
FST
要解决上面字典树的缺陷其实思路也很简单，就是除了利用字符串的前缀，同时也将相同的后缀进行利用，这就是 FST，在了解 FST 之前，我们先了解另一个概念，那就是 FSM，即：Finite State Transducer。
FSM
FSM，即 Finite State Machine，翻译为：有限状态机。如果大家有了解过设计模式中的状态模式的话，那么应该会对状态机有一定了解。有限状态机顾明思议就是状态可以全部被列举出来，然后随着不同的操作在不同的状态之间流程。
如下图所示就是一个简易的有限状态机（假设一个人一天做的事就是下面的所有状态，那么状态之间可以切换流转，下图中的数字表示状态的转换条件）：
有限状态机主要有以下两个特点：
- 状态是有限的，可以被全部列举出来。
- 状态与状态之间可以流转。
而我们今天所需要学习的 FST，其实就是通过 FSM 演化而来。
继续回到我们上面的那颗字典树，那么假如现在我们换成 FST 来存储，会得到如下的数据结构：
上面这幅图是怎么得到的呢？字母后的数字又代表了什么含义呢？有些节点有数字，有些是空白又有什么区别呢？这幅图又是如何区分 Final 节点呢？接下来我们就一步步来来构建一个 FST。
构建 FST 首先我们知道，既然现在讲的是存储索引，所以除了 key 之外自然得有 value，否则是没有意义的，所以上图中其实字母就代表了索引关键字，也就是 key，而后面的数字代表了存储的文档 id（最终会转换成二进制存储），然而这个 每个数字代表的 id 又可能是不完整的，这个我们下面会解释原因。
- 首先我们收到第一个存储索引的的键值对 AFGCC/5，得到如下图：
上图中红色代表开始节点，深灰色代表结束节点，加粗的线条代表其后面的节点是一个 Final 节点。这里有一个问题，那就是 5 为什么要存储在第一条线（没有存储数字的线上实际上是一个 null 值），实际上我存储在后面的任意一条线都可以，因为最终搜索的时候会把整条线路上所有的数字加起来得到最终的 value，这也就是上面我为什么说每一条线上的 value 可能是不完整的，因为一个 value 可能会被拆成好几个数字相加，并且存储在不同的线上。
首先这个 5 为什么要存储在第一段其实是为了提高复用率，因为越往前复用的机会可能就会越大。
2. 继续存储第二个索引键值对 AFG/10，这时候得到下图：
这时候我们发现，G 后面的节点存储了一个 5，其他线段上并没有存储数字，这是为什么呢？因为 10=5+5，而前面第一段已经存储了一个 5，后面一个 5 存储在任何一段线上都会影响到我们的第一个键值对 AFGCC/5，所以这时候就只能把他存储在当前索引 key 所对应的 Final 节点上（源码中有一个属性 output），因为搜索的时候，如果路过不属于自己的 Final 节点上的 value，是不会相加的，所以当我们搜索第一个索引值 AFGCC 的时候，是不会把 G 后面的 Final 节点中的 value 取出来相加的。
3. 接下来继续存储第三个索引键值对 ABP/2，这时候得到下图：
这时候因为 ABP 字符串和前面共用了 A，而 A 对应的 value 是 5，已经比 2 大了，所以只要共用 A，那么是无论如何也无法存储成功的，所以就只能把第一个节点 5 拆成 2+3，原先 A 的位置存储 2，那么后面的 3 遵循前面的原则，越靠前存储复用的概率越大，所以存在第二段线也就是字符 F 对应的位置，这时候就都满足条件了。
4. 最后我们来存储最后一个索引键值对 TAGCC/6，最终得到如下图：
这时候因为 GCC 这个后缀和前面是共用的，而恰好 GCC 之后的线上都没有存储 value，所以直接把这个 6 存储在第一段线即可，注意，如果这里再次发生冲突，那么就需要再次重新分配每一段 value，到这里我们就得到和上图中网站内生成的一样的 FST 了。
为什么全文索引不使用 B+ 树进行存储
关系型数据库，如 MySQL，其选择的是 B+ 树索引，如下图就是一颗简单的的 B+ 树示例：
上图中蓝色的表示索引值，白色的表示指针，最底层叶子节点除了存储索引值还会存储整条数据（InnoDB 引擎），而根节点和枝节点不会存储数据，B+ 树之所以这么设计就是为了使得根节点和枝节点能够存储更多的节点，因为搜索的时候从根节点开始搜索，每查询一个节点就是一次 IO 操作，所以一个节点能存储更多的索引值能减少磁盘 IO 次数。
那么到这里我们就可以思考这个问题了，假如索引值本身就很大，那么 B+ 树是不是性能会急剧下降呢？答案是肯定的，因为当索引值很大的话，一个节点能存储的数据会大大减少（一个节点默认是 16kb 大小），B+ 树就会变得更深，每次查询数据所需要的 IO 次数也会更多。而且全文索引就是需要支持对大文本进行索引的，从空间上来说 B+ 树不适合作为全文索引，同时 B+ 树因为每次搜索都是从根节点开始往下搜索，所以会遵循最左匹配原则，而我们使用全文搜索时，往往不会遵循最左匹配原则，所以可能会导致索引失效。
总结起来 B+ 树不适合作为全文搜索索引主要有以下两个原因：
- 全文索引的文本字段通常会比较长，索引值本身会占用较大空间，从而会加大 B+ 树的深度，影响查询效率。
- 全文索引往往需要全文搜索，不遵循最左匹配原则，使用 B+ 树可能导致索引失效。
若有收获，就点个赞吧
0 人点赞
