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

贺大伟 · · 1091 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

承接前文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的时候合并成一个文件以减少这种不稳定因素带来的影响,幸运的是我们开始重构的时候就对这些文件的访问进行了抽象,因此一切会比较平滑。


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:贺大伟

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

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

1091 次点击  
加入收藏 微博
被以下专栏收入,发现更多相似内容
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传