【ES】存储原理

搜索引擎

分片和副本

ES 中的索引由多个主分片组成，不同的主分片分布在不同的节点上。每个主分片都有一个或多个副本分片，即主分片的复制，当主分片异常时，副本分片可以提供数据的查询等操作。主分片和对应的副本分片不会落在同一个节点上，避免数据丢失，副本分片数的最大值为节点数 - 1。

文档的新增、修改等写请求必须在主分片完成，并且被复制到副本，当所有副本分片都写成功才会向协调节点报告成功，协调节点向客户端返回成功。ES 为了解决并发写操作过程中的数据冲突问题，通过乐观锁的方式控制，每个文档都有一个 _version 号，当文档被修改时版本号递增。

Lucene 索引

ES 底层基于 Lucene，实际上每个索引分片都对应着一个 Lucene 索引。一个 Lucene 索引 可能由多个子索引/segment 组成，每个 segment 都是一个完全独立的索引，可以单独搜索。segment 文件本身不可变，只能通过以下两种方式变更：

  1. 新增文档时创建新 segment
  2. 合并 segment

索引结构

每个 segment 维护以下内容：

  • Segment Info：段元数据，例如文档数量、使用的文件
  • Field names：索引中使用的字段名称集合
  • Stored Field values：每个文档，每个属性值对列表
  • Term dictionary：所有文档所有属性值字典
  • Term Frequency data：包含词的文档编号，以及词出现频率
  • Term Proximity data：词在文档中出现的位置
  • Per-document values：文档每个属性值，列式存储
  • …

索引文件

Lucene 索引文件大致可以分为以下四个部分：

  1. 词典
    • .tip：词典索引（前缀和后缀指针，需内存加载）
    • .tim：后缀词块、倒排表指针
  2. 倒排表
    • .doc：倒排表、词频
  3. 正向文件（行式存储）
    • .fnm：文件field元信息
    • .fdx：文档位置索引（需内存加载）
    • .fdt：文档值
  4. DocValues（列式存储）
    • .dvm：DocValues元信息
    • .dvd：DocValues值

词典

全文检索技术绝大多数都是基于倒排索引，Lucene 也是如此。倒排索引由词典和倒排表两部分组成，其中词典结构尤为重要，其效率好坏直接影响查询效率。一个合格的词典结构需要具备以下特点：

  1. 查询速度快
  2. 内存占用小
  3. 内存和磁盘相结合

常见词典优缺点：

数据结构 优缺点
排序列表 实现简单，但性能差
哈希表 性能好，但内存占用大
跳跃表 占用内存小且可调，但对模糊查询支持不好
B树 磁盘索引，更新方便，但检索速度慢，多用于数据库应用
字典树 查询效率只与字符串长度有关，但只适合英文词典
双数组字典树 可做中文词典，内存占用小，多用于分词
Finite State Transducers(FST，有限状态转移机) 共享前缀，内存占用小，但要求输入有序，更新不易

在 Lucene3.0 之前，Lucene 词典结构使用的是跳跃表结构，3.0 之后使用 FST 结构，但跳跃表在其他地方还有应用，如倒排表合并和文档号索引。

回到 Lucene 词典，tip 文件部分，文档每列对应一个 FST 索引，每个 FST 存放前缀和后缀指针。tim 文件中存放的是后缀块和词的其他信息如倒排表指针、TF（词频）、IDF（逆文档频率） 等。所以词典部分的检索过程如下：

  1. 内存加载 tip 文件，通过 FST 匹配前缀找到后缀词块位置。
  2. 读取磁盘 tim 文件中的后缀块，并找到后缀和倒排表位置信息。
  3. 到 doc 文件中加载倒排表。

倒排表

倒排表就是文档号集合，Lucene 中使用的倒排表结构为 Frame of reference，其特点有二：

  1. 数据压缩，通过增量编码方式压缩有序的文档号集合。
  2. 跳跃表加速合并，在布尔查询时，and/or 操作都需要合并倒排表，利用跳跃表可以快速定位到相同文档号。

正向文件

正向文件就是原始文档，其存储特点是分块 + 压缩。

  • fdt 文件存放原始文档，占索引库 90% 的磁盘空间，文档以 chunk 块存放，chunk 中包含起始文档、文档数、压缩后的文档内容信息，chunk 中起始文档值使用了平均值压缩算法。
  • fdx 为文档号索引，使用跳跃表结构。每 1024 个 chunk 位置归为一个 block，block 中记录起始文档值，相当于一级调表。

查找原始文档过程如下：

  1. 二分查找 block，定位到文档所在 block
  2. 继续查找定位到 chunk 位置
  3. 加载 fdt 文件指定 chunk，找到文档

DocValues

在需要对检索结果进行分类、排序、数学计算等聚合操作时，需要文档编号到值的快速映射，这时无论是倒排所以还是行式存储都无法满足需要。Lucene 使用列式存储 DocValues 来解决这一问题。

Lucene 有五种类型的 DocValues：NUMERIC、BINARY、SORTED、SORTED_SET、SORTED_NUMERIC，针对每种类型都有特定的压缩方法。