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

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

通常在搜索打分完毕后,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,如需转载请自行联系原作者

相关文章
|
4月前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
70 0
|
3天前
|
存储 算法 安全
.NET 平台 SM2 国密算法 License 证书生成深度解析
授权证书文件的后缀通常取决于其编码格式和具体用途。本文档通过一个示例程序展示了如何在 .NET 平台上使用国密 SM2 算法生成和验证许可证(License)文件。该示例不仅详细演示了 SM2 国密算法的实际应用场景,还提供了关于如何高效处理大规模许可证文件生成任务的技术参考。通过对不同并发策略的性能测试,开发者可以更好地理解如何优化许可证生成流程,以满足高并发和大数据量的需求。 希望这段描述更清晰地传达了程序的功能和技术亮点。
50 13
.NET 平台 SM2 国密算法 License 证书生成深度解析
|
4月前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
87 3
|
13天前
|
监控 算法 安全
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
33 10
|
10天前
|
存储 监控 算法
探秘员工泄密行为防线:基于Go语言的布隆过滤器算法解析
在信息爆炸时代,员工泄密行为对企业构成重大威胁。本文聚焦布隆过滤器(Bloom Filter)这一高效数据结构,结合Go语言实现算法,帮助企业识别和预防泄密风险。通过构建正常操作“指纹库”,实时监测员工操作,快速筛查可疑行为。示例代码展示了如何利用布隆过滤器检测异常操作,并提出优化建议,如调整参数、结合日志分析系统等,全方位筑牢企业信息安全防线,守护核心竞争力。
|
1月前
|
存储 算法 安全
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
54 17
|
1月前
|
算法 搜索推荐 Java
【潜意识Java】深度解析黑马项目《苍穹外卖》与蓝桥杯算法的结合问题
本文探讨了如何将算法学习与实际项目相结合,以提升编程竞赛中的解题能力。通过《苍穹外卖》项目,介绍了订单配送路径规划(基于动态规划解决旅行商问题)和商品推荐系统(基于贪心算法)。这些实例不仅展示了算法在实际业务中的应用,还帮助读者更好地准备蓝桥杯等编程竞赛。结合具体代码实现和解析,文章详细说明了如何运用算法优化项目功能,提高解决问题的能力。
68 6
|
1月前
|
存储 运维 负载均衡
Hologres 查询队列全面解析
Hologres V3.0引入查询队列功能,实现请求有序处理、负载均衡和资源管理,特别适用于高并发场景。该功能通过智能分类和调度,确保复杂查询不会垄断资源,保障系统稳定性和响应效率。在电商等实时业务中,查询队列优化了数据写入和查询处理,支持高效批量任务,并具备自动流控、隔离与熔断机制,确保核心业务不受干扰,提升整体性能。
78 11
|
2月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
2月前
|
机器学习/深度学习 人工智能 算法
深入解析图神经网络:Graph Transformer的算法基础与工程实践
Graph Transformer是一种结合了Transformer自注意力机制与图神经网络(GNNs)特点的神经网络模型,专为处理图结构数据而设计。它通过改进的数据表示方法、自注意力机制、拉普拉斯位置编码、消息传递与聚合机制等核心技术,实现了对图中节点间关系信息的高效处理及长程依赖关系的捕捉,显著提升了图相关任务的性能。本文详细解析了Graph Transformer的技术原理、实现细节及应用场景,并通过图书推荐系统的实例,展示了其在实际问题解决中的强大能力。
302 30

推荐镜像

更多
AI助理

你好,我是AI助理

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