Lucene4.2源码解析之fdt和fdx文件的读写——fdx文件存储一个个的Block,每个Block管理着一批Chunk,通过docID读取到document需要完成Segment、Block、Chunk、document四级查询,引入了LZ4算法对fdt的chunk docs进行了实时压缩/解

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介:
前言

通常在搜索打分完毕后,IndexSearcher会返回一个docID序列,但是仅仅有docID我们是无法看到存储在索引中的document,这时候就需要通过docID来得到完整Document信息,这个过程就需要对fdx/fdt文件进行读操作。为了更清楚地了解fdx/fdt文件的作用,本文把fdx/fdt文件的读和写整合到了一起,尽管这在Lucene中是两个分开的过程。

1. 索引生成阶段

索引生成阶段包含着一个复杂的过程,所以了解本文前最好对Lucene的索引架构有一定的了解,可以参考博客:Lucene的索引链结构_IndexChain 

由于在数据处理的过程中大量用到Packed,所以对数据的压缩最好也要有一点的了解,可以参考博客:Lucene源代码学习之PackedInts;由于在存储的过程也用到了LZ4算法,关于LZ4算法的原理,可以参考博客:lucene源代码学习之LZ4压缩算法在lucene中应用

1.1      fdx/fdt文件的创建。

fdx/fdt文件的创建完整线条如下:

 

 

在dwpt完成一个document的分析时,如果CompressionStoreFieldsWriter没有实例化,则创建:

 

1.2     fdx/fdt文件的格式。

  具体参考Lucene41StoredFieldsFormat.html (见Lucene4.2.0的docs)

fdt文件结构:

 

 

上图理解起来也不难,<Header>和PackedIntsVersion略过,我们重点关注<Chunk>,Chunk的中文意思是”大块”,我们可以理解为数据的存储区域。在内存中表现为缓存。一个Chunk由5个部分组成:DocBase表示当前的Chunk块的起始DocId;ChunkDocs表示当前Chunk中的doc个数;DocFieldCounts是一个数组,表示每个doc中Field的个数;DocLengths也是一个数组,表示每个doc占用byte的个数,即doc的长度;<CompressedDocs>即doc的内容,用LZ4算法压缩存储。FieldNumAndType是把FieldNumber和FieldType合并到一个VLong字段里面,整个<CompressedDocs>就是FieldNumAndType和Value的交替序列。

 

   fdx文件结构:

 

 

fdx文件重点关注的是<Block>,一个Block由三个部分组成:BlockChunks表示当前Block中Chunk的个数;<DocBases>表示当前Block中每个Chunk的doc个数,可以看作一个数组;<StartPointers>表示当前Block中每个Chunk在fdt文件中的起始位置,其结构与<DocBases>相同。

 

尽管fdx/fdt文件只是Lucene的正向文件,并不是Lucene的核心。但是还是有干货的。在Lucene4中引入了LZ4算法对fdt的doc进行了实时压缩/解压。而且用SPI(Service Provider Interface)技术对架构进行了重构。

 

1.3    fdx/fdt文件的写入。

fdx/fdt文件的写入操作非常清晰。逻辑上都在CompressingStoredFieldsWriter类中完成,而CompressingStoredFieldsIndexWriter则作为其成员变量。其写入的顺序与上面的格式一致,只是有些名字不一样。在写入docs的过程中,用GrowableByteArrayDataOutput作为缓存,直到缓存满了,才flush到硬盘上去。用LZ4算法压缩就是在flush时处理的。(关于LZ4算法会在另外的博文中描述)

 

fdt文件的写入:

       fdt文件的基本单位是Chunk,这一点需要牢记。一个Chunk写入到文件中的代码如下:<对照着前面的图看代码>

 

那么什么时候会调用上面的flush函数呢?

情况一:索引提交.

情况二:doc的大小或者doc的数量超过设定阈值.一般是1<<14=16384 (参见函数triggerFlush)

       通过观察flush函数,我们会发现fdt文件的写入非常简单,就两句代码:

前面一句代码记录整个chunk中的docBase(最小docID),numBufferedDocs(doc数量),numStoredFields(每个doc的Field个数),lengths(每个doc的长度),一共四种信息.在记录numStoredFields和lengths时,用PackedInts及其它的方式对内容进行了压缩。后面一句代码记录整个chunk中的doc的完整内容(用LZ4算法进行压缩).

关于writeHeader(docBase,numBufferedDocs, numStoredFields, lengths); 这一句代码,存储numBufferedDocs和存储numStoredFields方式是一样的,存储方式如下:

 

(上图截自于Lucene41StoredFieldsFormat.html)

 

    解释一下上图:在存储DocFieldCounts,即numBufferedDocs时,如果ChunkDocs=1(即当前Chunk只有一个doc),那么一个VInt存储就足够了;否则首先存储一个VInt的标志位,暂时称为bitsRequired。如果bitsRequired = 0 ,代表当前Chunk中所有doc中FieldCount相同;否则用Packed Array来存储DocFieldCounts,Packed Array中每个值占用的bit数即bitsRequired。

DocLengths的存储方式与DocFieldCounts相同,实现的代码如下:

fdx文件的写入

       fdx是fdt文件的辅助文件.如果说fdt是一本书的正文,那么fdx就是目录.fdx的基本单位是Block,一个Block中包含多个Chunk。

       一个Block写入到fdx文件中代码参看CompressingStoredFieldsIndexWriter.wirteBlock方法。由于代码太长,这里就不贴出来了。

       一个Block包含三方面的内容:

       1 ChunkCount;

       2 <DocBases>;

       3 <StartPointers> ;

       如果细细读这两段代码,会发现两段代码逻辑相似性达90%。确实,这两段代码的内容的处理方式上是一样的。在LUCENE-4512这个Improvement里面,有这样一段文字能帮助我们理解上面代码:

存的是文件位置startpointer!

       这段文字讲了一个技巧:“存储真实值和平均值的差值来代替存储真实值”;比如有下面几个数据需要存储到文件中:[10000,9888,10002,99997,10003];各个数与平均值之间的差值如下:[0,-2,2,-3,3] ,用差值存储就可以节约很多bits了。但是这样做又带来一个新的问题:负数的符号位都在最高位,而且PackedInts无法存储负数。因此需要对数据进行转码,转码方式就是zigzag转码。Zigzag编码的方法非常简单:

Int32: (n << 1) ^ (n >> 31)

Int64: (n << 1) ^ (n >> 63)

Zigzag编码主要在于对负数的压缩,比如-1(1111 1111 1111 1111 1111 1111 1111 1111),经过转码后,变成了1(0000 0000 0000 0000 0000 0000 0000 0001),节约了很多符号位。

经过Zigzag编码的数怎么还原呢?

(n>>> 1) ^ -(n & 1)

       了解了原理,我们再来分析<DocBases>内容的写入过程:

第一步:计算平均值(avgChunkDocs)

一般最后一个chunk都没有存满,所以docNum会低于其它的Chunk,所以在计算平均值的时候不用它。

第二步:存储docBase和平均值(avgChunkDocs)

第三步:计算最大的差值(delta),这个delta是用来计算bitsRequired

第四步:用PackedInts来压缩并存储docBaseDeltas。

存储<startPointerDeltas>的逻辑与<DocBases>类似,就不再赘述了。

 

本文出自 “每天进步一点点” 博客,请务必保留此出处http://sbp810050504.blog.51cto.com/2799422/1533162















本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6395210.html,如需转载请自行联系原作者

目录
打赏
0
0
0
0
64
分享
相关文章
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
基于FPGA的图像双线性插值算法verilog实现,包括tb测试文件和MATLAB辅助验证
本项目展示了256×256图像通过双线性插值放大至512×512的效果,无水印展示。使用Matlab 2022a和Vivado 2019.2开发,提供完整代码及详细中文注释、操作视频。核心程序实现图像缩放,并在Matlab中验证效果。双线性插值算法通过FPGA高效实现图像缩放,确保质量。
解锁“分享文件”高效密码:探秘 Java 二叉搜索树算法
在信息爆炸的时代,文件分享至关重要。二叉搜索树(BST)以其高效的查找性能,为文件分享优化提供了新路径。本文聚焦Java环境下BST的应用,介绍其基础结构、实现示例及进阶优化。BST通过有序节点快速定位文件,结合自平衡树、多线程和权限管理,大幅提升文件分享效率与安全性。代码示例展示了文件插入与查找的基本操作,适用于大规模并发场景,确保分享过程流畅高效。掌握BST算法,助力文件分享创新发展。
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
创建型模式的主要关注点是“怎样创建对象?”,它的主要特点是"将对象的创建与使用分离”。这样可以降低系统的耦合度,使用者不需要关注对象的创建细节。创建型模式分为5种:单例模式、工厂方法模式抽象工厂式、原型模式、建造者模式。
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
剖析文件共享工具背后的Python哈希表算法奥秘
在数字化时代,文件共享工具不可或缺。哈希表算法通过将文件名或哈希值映射到存储位置,实现快速检索与高效管理。Python中的哈希表可用于创建简易文件索引,支持快速插入和查找文件路径。哈希表不仅提升了文件定位速度,还优化了存储管理和多节点数据一致性,确保文件共享工具高效运行,满足多用户并发需求,推动文件共享领域向更高效、便捷的方向发展。
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
行为型模式用于描述程序在运行时复杂的流程控制,即描述多个类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务,它涉及算法与对象间职责的分配。行为型模式分为类行为模式和对象行为模式,前者采用继承机制来在类间分派行为,后者采用组合或聚合在对象间分配行为。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象行为模式比类行为模式具有更大的灵活性。 行为型模式分为: • 模板方法模式 • 策略模式 • 命令模式 • 职责链模式 • 状态模式 • 观察者模式 • 中介者模式 • 迭代器模式 • 访问者模式 • 备忘录模式 • 解释器模式
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
结构型模式描述如何将类或对象按某种布局组成更大的结构。它分为类结构型模式和对象结构型模式,前者采用继承机制来组织接口和类,后者釆用组合或聚合来组合对象。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象结构型模式比类结构型模式具有更大的灵活性。 结构型模式分为以下 7 种: • 代理模式 • 适配器模式 • 装饰者模式 • 桥接模式 • 外观模式 • 组合模式 • 享元模式
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
Hologres 查询队列全面解析
Hologres V3.0引入查询队列功能,实现请求有序处理、负载均衡和资源管理,特别适用于高并发场景。该功能通过智能分类和调度,确保复杂查询不会垄断资源,保障系统稳定性和响应效率。在电商等实时业务中,查询队列优化了数据写入和查询处理,支持高效批量任务,并具备自动流控、隔离与熔断机制,确保核心业务不受干扰,提升整体性能。
78 11
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
新版本发布:查询更快,兼容更强,TDengine 3.3.4.3 功能解析
经过 TDengine 研发团队的精心打磨,TDengine 3.3.4.3 版本正式发布。作为时序数据库领域的领先产品,TDengine 一直致力于为用户提供高效、稳定、易用的解决方案。本次版本更新延续了一贯的高标准,为用户带来了多项实用的新特性,并对系统性能进行了深度优化。
60 3

推荐镜像

更多
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等