Lucene倒排索引的持久化一一（倒排表的持久化）

古城微笑少年丶 2022-10-02 04:56 45阅读 0赞

倒排索引在结构上分为词典和倒排表，本篇博客最主要讲倒排表的持久化过程及其文件数据机构。

当新的doc在内存中积累到一定的数量或数据量大小时（可查看 `org.apache.lucene.index.FlushByRamOrCountsPolicy`），触发Flush过程，将新的doc的所有相关的数据持久化到磁盘，生成新的Segment及其相关数据，这里面比较关键的就是倒排索引的持久化过程，毕竟使用搜索引擎大部分都是通过倒排索引这个入口来检索数据的，了解其结构及持久化结构有助于更好的使用`Lucene`。

在上一篇博客中我稍微介绍了下倒排索引在内存中的结构，每个`Document`在添加添加时，按配置是否分词生成一个`Term`(词元)的集合，然后按照Term的维度添加倒排索引信息，每个term都有自己的倒排表元素，可根据Term从倒排表上找到所有含有此Term的`docID`，出现频率(`freq`)，位置信息(`pos`)，负载因子(`payload`)，位置偏移量(`offset`)。当然上述数据不是都有，要看Field的mappings配置。本篇博客就是讲上述这些数据的持久化过程，以及在磁盘上的数据文件名称，数据格式等。

我们先看这些数据对应的持久化目录中的文件形式，当`IndexWriterConfig` 设置不使用复合文件结构(`setUseCompoundFile(false)`)时，会对上述数据生成相应的文件：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NTI5OTE3_size_16_color_FFFFFF_t_70]

*  `.doc` 存储docID和frequency，含有此term的每个Document的ID和出现此Term的次数
 *  `.pos` 存储position（当前term于上一个term的序号增量，为1的情况偏多）
 *  `.pay` 存储payload和offset，payload就是负载因子，可以用来额外存储一些信息，会影响打分；offset就是当前Term在Document中的字节形式的位置信息。

持久化倒排索引的过程可以简略的提取如下代码：

public final class BlockTreeTermsWriter extends FieldsConsumer { 
    		
    	@Override
        public void write(Fields fields) throws IOException { 
            String lastField = null;
            // 遍历每个域
            for (String field : fields) { 
                assert lastField == null || lastField.compareTo(field) < 0;
                lastField = field;
    			// 获取指定域内的所有term
                Terms terms = fields.terms(field);
                if (terms == null) { 
                    continue;
                }
                TermsEnum termsEnum = terms.iterator();
                TermsWriter termsWriter = new TermsWriter(fieldInfos.fieldInfo(field));
             	// 遍历此域下的所有term
                while (true) { 
                    BytesRef term = termsEnum.next();
                    if (term == null) { 
                        break;
                    }
                    // 写入term相关的数据
                    termsWriter.write(term, termsEnum);
                }
                termsWriter.finish();
            }
        }
    }
    
    public abstract class PushPostingsWriterBase extends PostingsWriterBase { 
    
    	public final BlockTermState writeTerm(BytesRef term, TermsEnum termsEnum, FixedBitSet docsSeen) throws IOException { 
    		......
    		// 从内存中的倒排索引获取此term的所有数据，按doc的维度遍历处理每个doc相关数据
    		while (true) { 
                // 读取这个term的第一个docID
                int docID = postingsEnum.nextDoc();
                // 写入docID和freq 至 .doc文件
                // 如果当前doc中出现了多次此term,遍历每次出现的数据
             	{ 
             	 	// 写入position 至 .pos文件
                	// 写入payload和offset 至 .pay文件
             	}
            }
    }

过程总结如下：

1.  先按`Field`维度遍历，指定当前的Field
2.  从当前Field获取所有的`Term`，然后按Term维度遍历，指定当前正在处理的term
3.  从当前的Term获取倒排表信息，获取此Term在每个`Doc`中的索引信息，然后按Doc的维度处理，指定当前正在处理的Doc
4.  处理当前的Doc，根据`Mappings`里的`IndexOptions`里的配置处理 docID，freq，position，payload和offset。

所以在这些数据文件中，数据是有结构层次的，且结构类似，如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NTI5OTE3_size_16_color_FFFFFF_t_70 1]

这些文件在写入批量数据时使用到这样一个算法：`统计128个数据中最大的数据(仅限数值类型)，然后计算这个压缩这个数据最多需要多少位，然后给每个数据分配这个位数，将压缩后的数据依次写入分配好的比特位中，填不满的空着，且在数据块的最前方写入一个字节表示分配的位数，分配的位数不能大于32(int上限)`。这样读取的时候按位数读取，就能确认当前数据的序号以及此位置的实际数据。

对于`.doc`文件：

*  如果一个term出现的Document超过128个时，会将128个docID(使用`Delta`形式)压缩成一个块，128个freq压缩成一个块。使用上述算法写入.doc文件
 *  如果term出现的Document不足128个或者在写入多个块后的剩余下不足128个的，使用Vint的形式写入，一个docID后续紧跟着其freq。

对于`.pos`和`.pay`文件，一个doc中可能出现多次相同的term，docID和freq值仅需要记录一次，但是position，payload，offset却需要记录每一次的数据，所以正常情况下.pos，.pay文件的数据会比较大。Lucene对这种情况作了一些优化，只有一个term出现的次数超过128次(同一个doc中出现多次也算)时，才会将数据写入.pos和.pay文件，否则仅写入.doc文件。

`如果term出现的次数超过128次`：

*  写position：每128个position数据合成一个块，使用上述算法写入.pos文件中，且position也使用Delta的形式，缩减数据写入量。
 *  写payload：每128个payload的length合成一个块，用上述算法写入.pay文件中。然后写入payload的数据的字节长度，最后实际写入payload的编码后的数据。结构可能如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NTI5OTE3_size_16_color_FFFFFF_t_70 2]  
    这样在读取的时候才能根据 `payload length buffer` 里的字节长度从 `payload bytes` 拿到对应序号的payload的实际数据。
 *  写offset：每128个offset的start数据(Delta形式，也就是当前出现情形的start offset `减去`上次出现情形的start offset)合并成块写入.pay文件，然后将每次出现的offset的起始位置和终点位置的差值(offset length)合并成块写入.pay文件:
    
      
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NTI5OTE3_size_16_color_FFFFFF_t_70 3]

`写入.pos，.pay文件只有满足term出现的频率超过128次才行，每128次的数据合并成块，分别写入相应的文件。剩下的或者是出现频率不足128次的，都直接写入.doc 文件，且数据结构和内存中的倒排表结构相同，docID + freq + position + payload + offset`。

当然在写入这些数据后，字典上的term肯定要记录这些数据的起始位置，这样使用倒排索引时才能根据term值获取这些索引数据：

public final class Lucene50PostingsWriter extends PushPostingsWriterBase { 
    
    	  /** * 结束处理某个term, 这个term可能出现在多个doc中, 因此其与 {@link #startTerm()} 之间夹杂这多次的 * {@link #startDoc(int, int)} 和 {@link #finishDoc()} * Called when we are done adding docs to this term */
        @Override
        public void finishTerm(BlockTermState _state) throws IOException { 
    		......
    		// 当前nterm在.doc, .pos, .pay 文件中的数据的起始位置
            state.docStartFP = docStartFP;
            state.posStartFP = posStartFP;
            state.payStartFP = payStartFP;
            state.singletonDocID = singletonDocID;
            state.skipOffset = skipOffset;
            state.lastPosBlockOffset = lastPosBlockOffset;
    		......
    	}
    
    }

以上就是倒排表的持久化过程以及其在文件中的数据结构。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NTI5OTE3_size_16_color_FFFFFF_t_70]: /images/20220113/05e515992fde42e4a413bec1837ca2e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NTI5OTE3_size_16_color_FFFFFF_t_70 1]: /images/20220113/c9279175427145f586213d10e4dd9b23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NTI5OTE3_size_16_color_FFFFFF_t_70 2]: /images/20220113/1b61dc432f324a36be5b9ae12f7584d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3NTI5OTE3_size_16_color_FFFFFF_t_70 3]: /images/20220113/bf0dde468af24ae0bc63290f7b6e0d25.png