Lucene倒排索引设计

内存倒排索引构建1、 数据结构ByteBlockPool二维字节数组的内存池IntBlockPool用来存储每个term在ByteBlockPool中下一个要写入的位置每个term对IntBlockPool都是一个数据源slice 切片ByteBlockPool 的切片从ByteBlockPool 中获取一段连续内存多个 slice 通过最后 3 个字节进行串联BytesRefHash类似于一个MapBytesRef, IntergeKey 为 term 字节数组Value 为 term 的自增 id 编号包括三个数据结构ids[]通过对 term 做 hash得到一个在 ids 数组中的 pos 并对 term 进行自增编号在 ids[pos] 存储 term 的编号 idpool用于实际 term 存储bytesStart[]下标为 term 的编号 id值为 term 在 pool 中的偏移值。ParallelPostingsArray记录与 term 相关的文档数据信息包括文档 id、词频、位置、文档中的偏移等。按处理过程划分为两类通过 stream 进行记录。stream中包含的信息如下stream 0docfreqstream 1positionpayloadstartOffsetendOffsetstream 的概念是由 IntBlockPool 来承载的。由IntBlockPool 记录 slice 的写入位置。// 下标是termID值是termID所对应的term在ByteBlockPool中起始offset final int[] textStarts; // 下标是termID值是termID对应streamstream 0stream 1记录在IntBlockPool中当前写入位置的offset final int[] addressOffset; // 下标是termID值是该term的stream在ByteBlockPool中的下一个可以写入的位置 final int[] byteStarts;ParallelPostingsArray有两个子类分别是用来处理倒排和词向量的。对于倒排子类FreqProxPostingsArray有如下字段// 下标是termID,值是termID对应的在当前处理文档中的频率 int[] termFreqs; // 下标是termID,值是上一个出现这个term的文档id int[] lastDocIDs; // 下标是termID,值是上一个出现这个term的文档id的编码docId 1 int[] lastDocCodes; // 下标是termID,值是term在当前文档中上一次出现的position int[] lastPositions; // 下标是termID,值是term在当前文档中上一次出现的startOffset注意这里源码注释不对 int[] lastOffsets;┌─────────────────────────────────────────────────────────────────┐ │ BytesRefHash │ │ ┌─────────────┐ ┌──────────────────────────────────────┐ │ │ │ ids[] │───▶│ 哈希表槽位存储 termId|hashcode高位 │ │ │ └─────────────┘ └──────────────────────────────────────┘ │ │ ┌─────────────┐ ┌──────────────────────────────────────┐ │ │ │ bytesStart[]│───▶│ 词项文本在 ByteBlockPool 中的偏移 │ │ │ └─────────────┘ └──────────────────────────────────────┘ │ └─────────────────────────────────────────────────────────────────┘ │ ▼ ┌─────────────────────────────────────────────────────────────────┐ │ ParallelPostingsArray │ │ ┌─────────────┐ ┌──────────────────────────────────────┐ │ │ │ textStarts[]│───▶│ 词项文本在 bytesHash 中的偏移 │ │ │ ├─────────────┤ ├──────────────────────────────────────┤ │ │ │addressOffset│───▶│ IntBlockPool 中 stream 地址数组偏移 │ │ │ ├─────────────┤ ├──────────────────────────────────────┤ │ │ │ byteStarts[]│───▶│ 第一个 stream 在 ByteBlockPool 偏移 │ │ │ └─────────────┘ └──────────────────────────────────────┘ │ └─────────────────────────────────────────────────────────────────┘ │ ▼ ┌─────────────────────────────────────────────────────────────────┐ │ IntBlockPool (int[][]) │ │ ┌───────────────────────────────────────────────────────────┐ │ │ │ 每个 term 占用 streamCount 个 int存储各 stream 当前 │ │ │ │ 在 ByteBlockPool 中的写入位置会随写入更新 │ │ │ └───────────────────────────────────────────────────────────┘ │ └─────────────────────────────────────────────────────────────────┘ │ ▼ ┌─────────────────────────────────────────────────────────────────┐ │ ByteBlockPool (byte[][]) │ │ ┌───────────────────────────────────────────────────────────┐ │ │ │ 通过 ByteSlicePool 分配 slice存储实际的倒排数据 │ │ │ │ - slice 之间通过头尾指针串联 │ │ │ │ - 支持多 stream 同时写入 │ │ │ └───────────────────────────────────────────────────────────┘ │ └─────────────────────────────────────────────────────────────────┘2、 倒排数据构建流程1、 将 termId 在IntBlockPool 中的当前偏移值写入到ParallelPostingsArray 的 addressOffset[termId] 中2、 同时将 term 字节数组在ByteBlockPool 中的偏移值写到ParallelPostingsArray 的 byteStarts[termId] 中3、IntBlockPool 中两个初始 stream 链是紧邻排列的。通过 stream 编号即可获取每个 stream 在IntBlockPool 的起始偏移4、在初始时会为每个 stream 分配一个 slice 分片 并将 slice 分片的偏移值记录在 IntBlockPool 的 stream 起始偏移位置5、后续数据写入时通过 termId 从 ParallelPostingsArray 的 addressOffset 得到在IntBlockPool 中的偏移值这个偏移值加上 stream 编号即为 stream 在IntBlockPool 中的位置读取这个 stream 位置索引的数组值获取到 slice 在 ByteBlockPool 的位置偏移6、得到 slice 所管理的 ByteBlockPool 内存切片后即可写入数据。3、 总结Lucene 会对文档字段值进行分词得到分词后的词项。Lucene 会给每个词项分配一个全局唯一的自增 IDtermId新词项加入时按顺序分配。词项的去重和 ID 分配由 BytesRefHash 负责它使用 ids[] 数组作为哈希表通过词项的 hash 值确定槽位存储的是 termId 与 hashcode 高位组合后的编码值。Lucene 把词项的原始文本数据存储在 ByteBlockPoolbyte[][] 二维数组中。为了管理每个词项在 ByteBlockPool 中的位置Lucene 使用 BytesRefHash 中的 bytesStart[] 数组以 termId 为索引记录词项文本在 ByteBlockPool 中的起始偏移。由于 Lucene 在倒排构建过程中需要存储文档 ID、词频、位置、偏移等信息这些信息被分成多个 stream。通常 stream 0 存储文档 ID 和词频信息stream 1 存储位置和偏移信息。为了能支持多个 stream 同时写入到 ByteBlockPoolLucene 使用 ByteSlicePool 对 ByteBlockPool 进行切片管理。写操作前先申请一小块 slice 内存当 slice 写满后再申请新的 slice 并使用头尾指针串联。为了管理每个词项的各个 stream 在 ByteBlockPool 中的写入位置Lucene 使用 IntBlockPoolint[][] 二维数组。IntBlockPool 中为每个词项分配 streamCount 个整数用于记录各 stream 当前的写入偏移。这些整数在 IntBlockPool 中的起始位置由 ParallelPostingsArray 中的 addressOffset[] 数组记录以 termId 为索引。同时byteStarts[] 数组记录该词项第一个 stream 在 ByteBlockPool 中的起始偏移用于后续读取时定位。内存倒排索引读取1、数据结构ByteSliceReader内存中倒排数据的读取是在flush的时候触发的。倒排数据的两个stream中分别是由多个slice组成的两个链表ByteSliceReader是用来读取slice的。2、 读取流程 FreqProxFieldsFreqProxFields 在读取数据的时候为每个field生成一个FreqProxTerms对象FreqProxTerms 对象可以迭代 field 所有的 term对每一个 term 用 FreqProxTermsEnum 封装FreqProxTermsEnum 根据是否只需要 stream0 的数据还是都需要分别创建 FreqProxDocsEnum 和 FreqProxPostingsEnum最终完成倒排数据的读取。class FreqProxFields extends Fields { final MapString,FreqProxTermsWriterPerField fields new LinkedHashMap(); Override public Terms terms(String field) throws IOException { FreqProxTermsWriterPerField perField fields.get(field); return perField null ? null : new FreqProxTerms(perField); } private static class FreqProxTerms extends Terms { Override public TermsEnum iterator() { FreqProxTermsEnum termsEnum new FreqProxTermsEnum(terms); termsEnum.reset(); return termsEnum; } } private static class FreqProxTermsEnum extends BaseTermsEnum { Override public BytesRef term() { return scratch; } Override public PostingsEnum postings(PostingsEnum reuse, int flags) {} } private static class FreqProxDocsEnum extends PostingsEnum {} private static class FreqProxPostingsEnum extends PostingsEnum {} }FreqProxTerms- FreqProxTermsEnum迭代获取所有的term使用posting方法获取term的倒排数据迭代器FreqProxPostingsEnumFreqProxDocsEnum倒排索引文件生成为了快速定位 term 在某个文档中的倒排信息或者快速判断 term 是否在某个文档中出现过不能简单使用遍历的方式访问整个倒排Lucene 为了应对上面的需求使用了跳表结构来加速 docID 的查询。跳表中的每个节点是一个block每128个文档生成一个 blockblock的id是block中最大的docID可以通过跳表快速定位到doc所在的block然后再根据block中的其他信息读取doc相关的倒排信息。docIDfreqpositionoffset都是按block存储的为什么要区分block呢因为Lucene中针对小正数使用批量的压缩算法处理如果不区分block则如果有一个值特别大就会导致压缩效果骤降而分block处理就把异常值的影响只落在它所在的block中。对于同一个term而言docID是递增的并且在同一篇文档中position和startOffset也是递增的。词项字典的构建根据倒排索引我们可以非常快速地获取与 term 相关的文档但是如何根据term来获取term的倒排索引数据呢这就需要term字典。在Lucene中一个Field所有的term组成一个字典根据term可以从字典中获取term对应的倒排数据的位置比如term在哪些文档中出现在各个文档中的频率等等这样就可以通过一些相关性算法计算每个doc的相关性得分从而排序得到相关性文档的排序列表。所以term字典设计的首要目标就是速度要快否则就成为了整个检索性能的瓶颈。term字典是用 FST 数据结构来存储的FST要保证查找性能的话需要全部加载到内存中否则会有很多的随机IO消耗导致性能下降。对于数据量比较大的Field的term集合当一个FST放不下就构建多个 FST。然后把所有 FST 的第一个term拿出来构建一个上层的FST作为索引如果两层不够那就再往上1层以此类推。这样只有底层的LeafFST的输出是term的倒排数据地址其他层次中的FST的输出都是term在下层的FST的地址。