【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:NUMERICBINARYSORTEDSORTED_SETSORTED_NUMERIC,针对每种类型都有特定的压缩方法。