Caprice: Golang版的高性能实时全文检索引擎(segment 设计篇)

承接前文Caprice: Golang版的高性能实时全文检索引擎(实现篇)，本文是系列文章的第四篇。系列文章地址如下:

一. 如何构建实时全文检索引擎

二. Caprice: Golang版的高性能实时全文检索引擎

三. Caprice: Golang版的高性能实时全文检索引擎(实现篇)

本篇主要介绍segment的设计。我们知道FST被认为是构建高效的倒排索引的核心，但它的缺点是修改不易，因此为了克服这个问题，包括lucene在内的检索引擎，在使用FST的时候几乎都选择了segment这个概念去处理这个问题。将一段时间内的document集中起来处理，生成FST，同时利用LSM的设计思想，避免直接update和delete，但是代价就是索引并不能实时可见，不过好在很多使用全文检索的场景对实时性要求都不高，因此这也基本上成为一个默认约定。caprice是一个高性能的实时全文检索引擎，这里不再讲述实时性，而是讨论caprice的segment设计。

caprice的segment共由五个文件组成：.fdt, .fdx, .td, .fi, .dv，它们分别负责stored field的value，stored field的索引， term dict，field meta，doc value。而delete file则存储在boltDB中，boltDB也同时用来存储segment的元数据，我们正在替换boltDB以减少项目对其他组件的依赖，这个是历史问题，bleve 使用boltDB存储segment元数据，之所以如此，我猜测是为了支持提供一个可以存储KV的接口，我个人认为这个需求意义不大，因此在caprice中废弃了这个接口。

.FDT 文件格式

FDT是按照一个chunk一个chunk紧密排列组合而成，之所以使用chunk是为了压缩stored field，单个document的压缩压缩效果不理想，尤其是little size document的压缩，为了解决这个问题，我们采用chunk的方式对累计满足64KB或者document的数量达到512个时使用lz4压缩。

docBase：记录chunk的起始docID（内部doc ID，递增数字）；docBitmap：记录这个chunk中存储了哪些docID，之所以如此，是因为考虑到并不是所有的document都会stored field，因此可能存在空洞，必须紧密存储以节约空间。docFieldCounts：一个数组，记录每一个document的stored field的数量；docLengths：一个数组，记录每一个document的stored field的size。后面就是压缩的数据，解压之后是field meta和field value的组合依次排列存放，field meta是一个uint64的数字，最高16bit存放fieldID，后面的16bit存放field type，剩余的32bit存放field value length。

FDX文件格式

FDX文件是DFT文件的索引文件，记录了chunk的位置等信息，FDX按照block组织，每一个block包含1024个chunk（最后一个block包含的chunk数目可能会不足1024），这样设计的好处是加速检索的速度。

block包含三部分：BlockChunks；DocBases；ChunkSizes。

BlockChunks记录了block中包含的chunk数量，最大1024；DocBases记录了block中各个chunk中起始docID，即docBase，docBaseDeltas是一个数组，采用差值压缩的方式存储了各个chunk的DocBase。ChunkSizes记录了chunk在FDT中偏移，chunkSizeBase记录了起始偏移，AvgChunkSize记录了block中平均chunk size，chunkSizeBaseDeltas是一个数组，采用平均值压缩方式存储。

DV文件格式

（感谢项目核心成员MervinKid供图）

doc value使用列式存储，主要的目的就是方便聚合和sort。doc value也是按照chunk的方式组织和压缩数据，不过必须说明的是，doc value因为是列式存储，优化的空间很大。doc value目前处于减少fd句柄资源的考虑已经合并成一个文件了，核心是索引文件很小，后面随着压缩优化的进行会重新考虑索引的设计。这张图说的很明确了，大家自行看图理解其中的逻辑。

FI文件

（感谢项目核心成员MervinKid供图）

FI文件中存储了field name和field ID的映射关系以及各个field dict在TD文件中的起始偏移。

TD文件格式

segment拆分成多个文件的好处是在build的时候可以独立操作，分时段操作，从而大大提升写的性能。多个文件的弊端是导致打开的文件句柄会太多造成不稳定，后期我们会考虑在merge的时候合并成一个文件以减少这种不稳定因素带来的影响，幸运的是我们开始重构的时候就对这些文件的访问进行了抽象，因此一切会比较平滑。