Lucene检索全流程学习笔记
阅读原文时间:2023年08月11日阅读:4

一 简介

1 为什么学习Lucene

lucene是基于倒排索引的检索工具库,倒排索引是典型的文本匹配,它能够精确匹配用户搜索的query,它的缺点是不擅长语义理解,而深度学习检索模型擅长的正是理解用户query背后的语义。深度学习的一个优点是可以把用户的各种特征很容易地输入模型以丰富用户搜索的上下文信息。深度学习的一个流派是表示学习,把用户的query、及其他特征通过学习得到向量表示,在向量空间里面比较用户和文档的相似度,返回相似度最高的\(TopK\)文档。

在语义召回的优点之外,embedding召回的结果相关性存在一些问题。例如淘宝 在它的MGDSPR论文中给出了一个例子:用户搜索阿迪达斯运动鞋 ,在向量空间里它和耐克运动鞋 比较相似,因而会返回给用户,然而这违背了用户的本意,因为对用户来说品牌是一个强需求。淘宝通过一些算法上的、工程上的手段解决了这个问题,并认为倒排 是基础,深度学习召回作为补充进一步提升搜索质量。

因此\(倒排索引\) 技术虽然有它的缺点,但是也有精确匹配用户query的优点,作为召回的基础,仍然是值得学习的。

2 学习过程中遇到的问题

初高中语文课上老师教过一种总-分-总的写作范式,先从总体上描述一件事情的脉络,然后针对脉络中的关键点,细细展开来描述,最后做一个总结性的描述来收尾。

笔者在工作上学习模块源码以及阅读开源代码时,喜欢先从总体上梳理出模块的脉络:从主流程最开始的点,顺着它的调用关系,在模块的脉络上跳转。这一块OK后,再针对模块关键点深入梳理了解。否则如果没有第一个阶段,而直接进入到第二阶段,会有一种不踏实的感觉,总感觉没有真正掌握。

同样学习Lucene源码时,最开始免不了去网上搜索一些博客,然而很多优秀的Lucene模块都是针对某一块展开,例如Lucene中的跳跃链表、索引Merge、写term词典的FST算法等专题的形式出现。这些博客写的固然很好,但是总体上没法把Lucene的逻辑串联起来,例如:

  • Lucene中最终要拉出对应query的倒排表,而这个关键点隐藏在query分析中,它会返回一个\(TermQuery\) 类型的query,而这个query中隐含了拉取倒排的接口.

    • 初学者很容易忽略那一行简单的代码:Query query = parser.parse(line); 然后迷失在Lucene代码的汪洋大海中,最终并不知道由于在哪个地方做了什么事,才导致我们能成功拉取倒排,尽管他可能知道拉读倒排的逻辑主要在\(BlockTreeTermsReader\) ,但是整个流程却无法串联到一块
  • 假如初学者找到了调用 拉取倒排的函数,很有可能继续迷失在,倒排是怎么被拉去出来的。我们根据关键字posting很有可能来到下面这个调用链:

    public EverythingEnum reset(IntBlockTermState termState, int flags) throws IOException {
          docTermStartFP = termState.docStartFP;
          posTermStartFP = termState.posStartFP;
          payTermStartFP = termState.payStartFP;
    }

    然而这个调用链只是把倒排文件(.doc .pay .pos)的句柄简单赋值过来,这些句柄其实是隐藏在一个比较深的不太起眼的地方:

    public void decodeTerm(DataInput in, FieldInfo fieldInfo, BlockTermState _termState, boolean absolute) {
    if (fieldHasPositions) {
          termState.posStartFP += in.readVLong();
          if (fieldHasOffsets || fieldHasPayloads) {
            termState.payStartFP += in.readVLong();
          }
        }
    }

    在网上也有一些技术博客,讲解调用链路方面的,但是都不太完整,或者缺一些东西。因此本文的目的就是系统性的分析一下Lucene检索全流程的调用链路,使得我们顺着demo中的searcher.search(query, 100); 这行代码,一点点深入检索流程的调用链,看看最终是如何从索引库里将文档检索出来的。另外看过的一些东西,过段时间再看很容易就忘记部分,因此有必要通过一篇博客记录下来。

本文的目的在于从主流程最开始的地方,通过调用关系逐步深入,来呈现出Lucene检索的完整调用链。因此会在写作时会进行一些舍弃

  • 某个局部区域,挑选一条简单的路径,舍弃其他路径,以求简洁,突出本文的目的。例如在paraser.parse(line) 中,调用路径非常多且复杂,笔者会挑选其中一个返回TermQuery 的调用链来描述,其他的调用路径功能类似,不会再一一描述。另外还会描述一些关键数据,例如query分析中,在哪个地方体现了针对输入的query进行分析(注:代码中将域、query设置在一个比较容易忽视的变量中)

  • 会舍弃一些关键组件的介绍,例如在介绍从词典找到对应的term 拉取倒排的时候,必然涉及FST,但是笔者不会介绍FST, 会介绍FST的哪个地方的哪个调用,去真正拉取了倒排。因为一方面:FST作为Lucene存词典的重要算法,它值得单独一个篇幅专门介绍,另一方面这么处理,也可以突出本文梳理脉络的目的,突出总-分-总 中的第一个总字

  • 本文的目标是梳理总体脉络,重点着墨的部分,这个是针对Lucene这个庞大的代码库而言。具体到本文内部,会采用总-分的方式,在某一块局部的功能中,会先给出的描述,以期快速了解整个面貌,然后针对其中的关键点,细细展开。

  • Lucene中的索引文件种类较多,每一种格式也比较复杂,这些东西也值得单独的篇幅来介绍,因此本文遇到的索引文件,会简要说明它的目的,不会做过深入的分析。

设计模式

了解设计模式的人,一定听说过里氏代换 依赖倒转 原则,前者的含义是:所有基类出现的地方,子类一定可以出现;后者的含义是:应该针对抽象编程而不是针对实现编程。这样的好处是可以很容易扩展系统功能,而不会破坏现有的系统,符合开闭原则。

读了Lucene源码,你就会了解这正是Lucene中的编程范式, 由于Lucene源码非常复杂,在调用链很深的地方,往往看到代码在操作一个个基类,而找到它实际的类型才能了解深入它的细节,了解它的正在功能原理。遗憾的是在Lucene这样一个复杂的逻辑里,找到这一点并不容易。当然使用这个编程范式的优点远远大于其的缺点。

二 从demo开始

文件位置:org/apache/lucene/demo/SearchFiles.java

public static void main(String[] args){
    IndexReader reader = DirectoryReader.open(FSDirectory.open(Paths.get(index)));
    IndexSearcher searcher = new IndexSearcher(reader);
    Analyzer analyzer = new StandardAnalyzer();
    QueryParser parser = new QueryParser(field, analyzer);
    Query query = parser.parse(line);
    searcher.search(query, 100);
}

上面这个demo代码是Lucene官方提供的一个搜索例子,为了描述的简洁高效,代码经过删减,只留下了最关键的部分。后文在介绍其他逻辑的时候,也会采用这种方式,不再赘述。

demo中主要包括了6行代码,此处先一一简介其功能,后续章节会详细深入

reader = DirectoryReader.open(FSDirectory.open(Paths.get(index)));

Lucene中有一个名为    segments_n 的索引文件,它里面记录了历次的commit,通过它可以找到所有名为_n.si的文件,每一个.si文件里面记录了诸如.doc .pos .pay .fnm 等索引文件的信息。 这个函数会读取索引元信息,例如域相关的信息,然后层层封装到reader里面,供检索的时候调用。

IndexSearcher searcher = new IndexSearcher(reader);

searcher的功能是检索的总控模块,调用1中的reader进行检索,对检索的结果进行打分等。后文搜索的过程会详细深入。

Query query = parser.parse(line);

对用户的query进行分析,包装成Lucene中定义好的query对象,例如TermQuery BooleanQuery 等。其中TermQuery 是最基本的query对象,它提供了拉取倒排的接口,供Search流程调用。

searcher.search(query, 100)

搜索的入口函数,这个调用的含义是在field 域中搜索query命中的文档,并返回打分最高的前100个文档。

构造reader解析query搜索query 是三个主要流程,其中解析query相对简单,后面先介绍之,构造reader 逻辑比较复杂,关系到搜索流程依赖的很多索引读取逻辑,次之介绍,搜索query是最重要,最复杂的流程,放到最后介绍。

三 解析query

Query query = parser.parse(line); 从这行代码开始,line是用户输入的query

上面的调用进入下面这个函数

位置:org/apache/lucene/queryparser/classic/QueryParserBase.java

public Query parse(String query) throws ParseException {
    ReInit(new FastCharStream(new StringReader(query)));
    Query res = TopLevelQuery(field);
}

1 ReInit 这个函数会将query包装后存入:token_source.ReInit(stream);

2 Query res = TopLevelQuery(field); 进入

位置:org/apache/lucene/queryparser/classic/QueryParser.java

final public Query TopLevelQuery(String field) throws ParseException {
    q = Query(field);
}

note 这个函数的参数是域名,并不是用户搜索的query,第一次看代码的话,顺着这个地方往下看,不容易发现用户query作用的点,所以 1 中特意点出了query存储的地方,后面还会再遇到

3 q = Query(field); 进入到

位置:org/apache/lucene/queryparser/classic/QueryParser.java

final public Query Query(String field) throws ParseException {
    firstQuery = MultiTerm(field, clauses);
}

MultiTerm() 中的text = jj_consume_token(TERM); 体现了消费用户搜索query的地方。接着调用getFieldQuery(field, discardEscapeChar(text.image), false);继续调用

newFieldQuery(Analyzer analyzer, String field, String queryText, boolean quoted) ,进而调用createFieldQuery(analyzer, occur, field, queryText...); 接着进入下一轮调用,见下文4

4 接着调研另外一个同名不同参的函数

位置:org/apache/lucene/util/QueryBuilder.java

protected Query createFieldQuery(TokenStream source, BooleanClause.Occur operator, String field, boolean quoted, int phraseSlop) {
     return analyzeTerm(field, stream);
}

5 进入analyzeTerm函数,它的某个代码分支会返回如下代码

return newTermQuery(new Term(field, termAtt.getBytesRef()), boostAtt.getBoost());

注意 newTermQuery 很关键,它有一个成员函数getTermsEnum(LeafReaderContext context 用于从索引中拉倒排数据

四 构造reader

lucene用codec来描述所有倒排文件的格式,codec的版本会再索引阶段写入段文件里面,读取的时候根据这个值找到对应的版本,以Lucene87为例

位置:org/apache/lucene/codecs/lucene87/Lucene87Codec.java

截取主要倒排文件定义如下

public class Lucene87Codec extends Codec {
    private final FieldInfosFormat fieldInfosFormat = new Lucene60FieldInfosFormat();
    private final SegmentInfoFormat segmentInfosFormat = new Lucene86SegmentInfoFormat();

    public Lucene87Codec(Mode mode) {
        super("Lucene87");
        this.storedFieldsFormat = new Lucene87StoredFieldsFormat(Objects.requireNonNull(mode).storedMode);
        //posting的格式
        this.defaultFormat = new Lucene84PostingsFormat();
        this.defaultDVFormat = new Lucene80DocValuesFormat(mode.dvMode);
    }
}

后文会有很多地方从codec里面取出对应的倒排工具类,然后执行业务逻辑

1) 从DirectoryReader.open()说起

IndexReader reader = DirectoryReader.open(FSDirectory.open(Paths.get(index)));

再到达核心流程前会经过层层嵌套调用:

1)org/apache/lucene/index/DirectoryReader.java

StandardDirectoryReader.open(directory, null, null);

2)org/apache/lucene/index/SegmentInfos.java

public T run(IndexCommit commit)

3)org/apache/lucene/index/SegmentInfos.java

protected DirectoryReader doBody(String segmentFileName)

主要的流程在doBody() 这个函数中

2) doBody() 流程

protected DirectoryReader doBody(String segmentFileName) throws IOException {
        SegmentInfos sis = SegmentInfos.readCommit(directory, segmentFileName);
        final SegmentReader[] readers = new SegmentReader[sis.size()];
        for (int i = sis.size()-1; i >= 0; i--) {
            readers[i] = new SegmentReader(sis.info(i), sis.getIndexCreatedVersionMajor(), IOContext.READ);
        }
        DirectoryReader reader = new StandardDirectoryReader(directory, readers, null, sis, leafSorter, false, false);
        return reader;
}

2.1 主流程

位置:org/apache/lucene/index/SegmentInfos.java

readCommit(Directory directory, String segmentFileName) segmentFileName是形如segments_N的文件,读取的时候会选取目录中N最大的那个值对应的段文件。

  1. 从磁盘读取segments_N文件

  2. 调用同名不同参的readCommit函数

  3. 实例化infos = new SegmentInfos ,infos里面有一个List容器,前文说过segments_N文件管理了多个commit,每一个commit被读取后,存入这个List 容器中。这个List的定义是private List<SegmentCommitInfo> segments = new ArrayList<>();

  4. 关键字段读取:int numSegments = input.readInt(); 这个字段描述了段文件segments_N 管理了多少个commit,根据Lucene的删除保留策略,可能有多个,也可能只有一个,我们假定是多个

  5. 遍历numSegments 个commit,每一个commit的逻辑,进入6)开始的流程描述

  6. 读取关键字段Codec codec = readCodec(input); (其余还有很多字段,本文只描述能串联调用链的字段,后文也是如此,不再赘述) 本文的Codec以Lucene87为例

  7. SegmentInfo info = codec.segmentInfoFormat().read(directory, segName, segmentID, IOContext.READ);

    1)去lucene87codec.java中能够看到定义

    segmentInfosFormat = new Lucene86SegmentInfoFormat();

    2)然后进入到org/apache/lucene/codecs/lucene86/Lucene86SegmentInfoFormat.java

    public SegmentInfo read(Directory dir, String segment, byte[] segmentID, IOContext context)

读单个segmentinfo的逻辑比较复杂,下文专门一个小节来介绍

  1. 7返回的info描述了一个commit的信息,例如该commit里面的文档数量、软删除的数量等等

  2. 以8中的info为参数,再包装一层

SegmentCommitInfo siPerCommit = new SegmentCommitInfo

  1. 将9中的siPerCommit 塞进 3)中提到的List容器中

  2. 将3中的infos返回给前文提到的dobody()函数

2.2单个Segment的读取

在2.1 readCommit 主流程里面还遗留了单个segment的读取逻辑在此介绍。它对应读取的总控文件是_N.si文件,N是一个数字,跟索引的迭代有关。下面介绍它的主要调用流程

位置:org/apache/lucene/codecs/lucene86/Lucene86SegmentInfoFormat.java

public SegmentInfo read(Directory dir, String segment, byte[] segmentID, IOContext context)
  1. 首先读取si文件

    input = dir.openChecksumInput(fileName, context)

    会读取一些字段,进行版本check之类。

  2. 读取排序的域个数

    numSortFields = input.readVInt(),每一个域在索引阶段可以指定排序的方式,在读取的时候要求每一个commit的相同域的排序规则一致,否则返回失败

  3. 最后将读取到的字段为参数,构造si = new SegmentInfo 返回给调用者

3.1 总控流程

前文有一段代码如下, 遍历读到的每一个segmentInfo(对应_N.si文件),构造每一个对应的SegmentReader, 本小节就来介绍下这块逻辑

for (int i = sis.size()-1; i >= 0; i--) {
&nbsp;&nbsp;&nbsp;&nbsp;readers[i] = new SegmentReader(sis.info(i), sis.getIndexCreatedVersionMajor(), IOContext.READ);
}

位置:org/apache/lucene/index/SegmentReader.java

  1. 构造CoreReader, CoreReader是这块的核心,会在第4小节专门介绍

     core = new SegmentCoreReaders(si.info.dir, si, context);
  2. 读取Livedocs:操作的是.liv文件,从这个文件能看到哪些docid还“活着”

    liveDocs = codec.liveDocsFormat().readLiveDocs(directory(), si, IOContext.READONCE);
  3. 初始化域相关信息

    fieldInfos = initFieldInfos();
    
    private FieldInfos initFieldInfos() throws IOException {
        if (!si.hasFieldUpdates()) {
          return core.coreFieldInfos;
        } else {
          // updates always outside of CFS
          FieldInfosFormat fisFormat = si.info.getCodec().fieldInfosFormat();
          final String segmentSuffix = Long.toString(si.getFieldInfosGen(), Character.MAX_RADIX);
          return fisFormat.read(si.info.dir, si.info, segmentSuffix, IOContext.READONCE);
        }
      }

    可以看出,如果读取期间域没有更新,则直接返回core.coreFieldInfos,它是在SegmentCoreReader中读取的。否则的话需要读取.fnm文件

  4. 其他倒排文件相关初始化

    docValuesProducer = initDocValuesProducer();

4.1 总控流程

  1. 获取前文提到的codec(lucene87)

  2. 读域文件.fnm

    coreFieldInfos = codec.fieldInfosFormat().read(cfsDir, si.info, "", context);

    查看Lucene87codec,可以看到fieldInfosFormat()返回的是如下工具类

     private final FieldInfosFormat fieldInfosFormat = new Lucene60FieldInfosFormat();

    \(read()\)的逻辑比较复杂,在4.2 小节会转门介绍

  3. 倒排数据(此处指.doc .pay .pos .tim .tip等)读取工具类的初始化

    final PostingsFormat format = codec.postingsFormat();
    fields = format.fieldsProducer(segmentReadState);

    此部分逻辑链条也比较长、复杂,在4.3 小节专门介绍

  4. 域文件.fdt .fdx .fdm的读取。可以简单理解为.fdt .fdx .fdm从属于.fnm

    fieldsReaderOrig = si.info.getCodec().storedFieldsFormat().fieldsReader(cfsDir, si.info, coreFieldInfos, context);
  5. 其他索引文件的读取,此处略去

4.2 域的读取

本文介绍前文 4.1) 中第2步提到的域.fnm

coreFieldInfos = codec.fieldInfosFormat().read(cfsDir, si.info, "", context);

read函数的位置:org/apache/lucene/codecs/lucene60/Lucene60FieldInfosFormat.java

public FieldInfos read(Directory directory, SegmentInfo segmentInfo, String segmentSuffix, IOContext context) throws IOException {
}
  1. 从磁盘索引中读取.fnm文件

    input = directory.openChecksumInput(fileName, context)
  2. 读取域的个数

    final int size = input.readVInt(); //read in the size
    infos = new FieldInfo[size];
  3. 遍历size个域,读取每个域的信息,进入到4中描述之

  4. 读取域的编号:fieldNumber = input.readVInt();

  5. 读取标志位字节:bits = input.readByte(); 这个字节的不同bit位描述了这个域是否存储了term vector数据、norms数据、payload数据及软删除数据;

  6. 其他的还读取了诸如点数据等属性字段

  7. 对于每一个域读取完上述属性字段后,作为参数构造FieldInfo

    infos[i] = new FieldInfo(name, fieldNumber, storeTermVector, omitNorms, storePayloads,
                                         indexOptions, docValuesType, dvGen, attributes,
                                         pointDataDimensionCount, pointIndexDimensionCount, pointNumBytes, isSoftDeletesField);
  8. 包装infos并返回:return new FieldInfos(infos); 这个构造函数里面,将infos生成2个map 1)byName : key是域名,值是FieldInfo类型数据,也即7中的infos[i]; 2) byNumber 同byName 区别是key是域的编号

  9. 返回到SegmentCoreReaders主流程,FieldInfos赋值给coreFieldInfos

4.3 倒排数据相关初始化

4.1第3步提到倒排数据的读取

final PostingsFormat format = codec.postingsFormat();
fields = format.fieldsProducer(segmentReadState);

由前文可知,这个format是 Lucene84PostingsFormat ,因此进入对应的fieldsProducer函数

位置:org/apache/lucene/codecs/lucene84/Lucene84PostingsFormat.java

public FieldsProducer fieldsProducer(SegmentReadState state) throws IOException {
    PostingsReaderBase postingsReader = new Lucene84PostingsReader(state);
    boolean success = false;
    try {
      FieldsProducer ret = new BlockTreeTermsReader(postingsReader, state);
      success = true;
      return ret;
    } finally {
      if (!success) {
        IOUtils.closeWhileHandlingException(postingsReader);
      }
    }
  }

这其中有两个非常重要的倒排工具类:postingsReaderBlockTreeTermsReader 。它们是读取倒排文件的核心类,是lucenen检索流程的基石,下面会分2个单独的章节来介绍

docIn = state.directory.openInput(docName, state.context);
posIn = state.directory.openInput(proxName, state.context);
payIn = state.directory.openInput(payName, state.context);

主要逻辑是从磁盘索引文件读取.doc .pos .pay文件,是后续检索流程查找倒排数据的基础。doc文件里面存储的是文档id和term的词频;pos文件存储的是term的位置信息;pay文件里面存储的是term的offset和term的payload信息。

6.1 BlockTreeTermsReaderpostingsReader 的关系

所谓的倒排索引值的是根据term找到对应的文档list,正排索引指的是根据文档号找到文档的属性信息。此处BlockTreeTermsReader 是读取term词典用的,postingsReader 是读取文档相关的倒排文件的用的。因此两者是包含的关系:

FieldsProducer ret = new BlockTreeTermsReader(postingsReader, state);

6.2 new BlockTreeTermsReader

  1. 从磁盘索引中读取.tim .tip数据,它们存储的就是前文提及的term词典数据,以FST算法产出的格式存储。

  2. 读取.tmd文件(PS:这个可能是新版本增加的一种格式,后面再研究,此处略去)

  3. 从.tmd文件中读取域的个数 numFields = termsMetaIn.readVInt();

  4. 遍历numFields中的每一个,进入到5中来描述

  5. 读取域的编号、rootcode(FST相关数据)

  6. 根据5中域的编号获取域对象

    final FieldInfo fieldInfo = state.fieldInfos.fieldInfo(field);

    state.fieldInfos实际上是前文提到的coreFieldInfos,因此上面代码实际上是从其内部的byNumber容器中取出已经构造好的域对象

  7. 读取minTerm、maxTerm(按字典序最小、最大). 这个用于快速排除一些肯定不在term词典的情况

    BytesRef minTerm = readBytesRef(termsMetaIn);
    BytesRef maxTerm = readBytesRef(termsMetaIn);
  8. 构造FieldReader

    final long indexStartFP = indexMetaIn.readVLong();
    FieldReader previous = fieldMap.put(fieldInfo.name,
                    new FieldReader(this, fieldInfo, numTerms, rootCode, sumTotalTermFreq, sumDocFreq, docCount,
                        indexStartFP, indexMetaIn, indexIn, minTerm, maxTerm));

    6.3 new FieldReader

    FieldReader 类成员函数iterator是拉取倒排的第一步:构造TermsEnum,后面调用iterator的SeekExact()、postings接口后就会拉取到倒排表。前文提到TermQuery中有一个接口getTermsEnum() 它的内部实际上底层调用的就是此处FieldReader的iterator接口。

      public TermsEnum iterator() throws IOException {
        return new SegmentTermsEnum(this);
      }

五 搜索

searcher.search(query, 100); 出发走完整个搜索流程。

经过了前文query分析、Reader构造等大量的初始化工作,现在已经可以进入搜索的流程了。Lucene中同名search函数很多,它们层层调用,最终才会进入主题,此处沿着这个调用链,直达最接近检索的那个search函数,然后在其他小节具体深入分析。

  1. public TopDocs search(Query query, int n)

  2. 然后进入public TopDocs searchAfter(ScoreDoc after, Query query, int numHits) 函数

  3. 从2中进入public T search(Query query, CollectorManager collectorManager)函数

  4. 从3进入public void search(Query query, Collector results)函数,其中检索到的文档存入results中

  5. 进入protected void search(List leaves, Weight weight, Collector collector)中,至此已经比较接近搜索真正的入口了,从第2节开始详细介绍

位置:org/apache/lucene/search/IndexSearcher.java

  protected void search(List<LeafReaderContext> leaves, Weight weight, Collector collector)
      throws IOException {
    for (LeafReaderContext ctx : leaves) { // search each subreader
      final LeafCollector leafCollector;
      try {
        leafCollector = collector.getLeafCollector(ctx);
      } catch (CollectionTerminatedException e) {
        // there is no doc of interest in this reader context
        // continue with the following leaf
        continue;
      }
      BulkScorer scorer = weight.bulkScorer(ctx);
      if (scorer != null) {
        try {
          scorer.score(leafCollector, ctx.reader().getLiveDocs());
        } catch (CollectionTerminatedException e) {
          // collection was terminated prematurely
          // continue with the following leaf
        }
      }
    }
  }
  • 在for循环语句里,遍历leaves,然后对每一个leave执行对应的检索流程。这里面的context和leaves是什么关系,它们和前文提到的SegmentReader又是如何联系到一块的,下面会在第3 小节理清这里面的调用关系

  • 接下来的调用BulkScorer scorer = weight.bulkScorer(ctx); 比较关键,拉取倒排的迭代器,隐藏在打分对象的成员变量里。这一部分会在第4小节拉取倒排数据部分介绍,由于本文的目的是串联检索调用路径,因此对打分部分简单提下,不会深入梳理,尽管拉倒排的逻辑嵌入在打分对象里面。

  • scorer.score(leafCollector, ctx.reader().getLiveDocs());上一个步骤拉取了倒排数据,那么接下来就轮到了从倒排里面检索数据,取出文档了。这一部分会在下文第5 小节介绍。

3.1 回顾读取索引目录的逻辑

protected DirectoryReader doBody(String segmentFileName) throws IOException {
        SegmentInfos sis = SegmentInfos.readCommit(directory, segmentFileName);
        final SegmentReader[] readers = new SegmentReader[sis.size()];
        for (int i = sis.size()-1; i >= 0; i--) {
            readers[i] = new SegmentReader(sis.info(i), sis.getIndexCreatedVersionMajor(), IOContext.READ);
        }
        DirectoryReader reader = new StandardDirectoryReader(directory, readers, null, sis, leafSorter, false, false);
        return reader;
}

为了避免上下文距离过长影响阅读,此处再把对应的代码贴出来。这段代码先从目录中读取每一个commit对应的索引文件,构造出SegmentReader, 然后再把所有的SegmentReader List作为参数构造出StandardDirectoryReader 类型的Reader, 赋值给基类对象,返回调用方

返回的reader会用来构造IndexSearcher(), 进而生成leaves。每一个leave代表了一个不可分割的原子结点,它里面实际上是一个SegmentReader。先来看看StandardDirectoryReader 的继承体系,在后文会用到,以下按照顺序依次给出继承体系中每一个类

  1. StandardDirectoryReader

  2. DirectoryReader

  3. BaseCompositeReader

  4. CompositeReader

  5. IndexReader

3.2 生成Leaves

再回到前问提到的IndexSearcher searcher = new IndexSearcher(reader);

  1. 这段代码 实际上调用的是下面这个函数

    public IndexSearcher(IndexReader r, Executor executor) {
    this(r.getContext(), executor);
    }

  2. r.getContext()的r即是前文提到的StandardDirectoryReader;根据继承链的关系,它调用的是类CompositeReader中的getContext函数

  3. 接2,它里面有一行关键代码

    readerContext = CompositeReaderContext.create(this); 这个create函数里面执行了Builder(reader).build(); 参数里面的reader即是调用语句的参数this,即为StandardDirectoryReader。

  4. 接3,调用的build函数的逻辑

     public CompositeReaderContext build() {
          return (CompositeReaderContext) build(null, reader, 0, 0);
     }
  5. 接4,此时进入到最底层真正发挥作用的build函数,经过删减只留下关键逻辑的代码如下

     private IndexReaderContext build(CompositeReaderContext parent, IndexReader reader, int ord, int docBase) {
          if (reader instanceof LeafReader) {
            final LeafReader ar = (LeafReader) reader;
            final LeafReaderContext atomic = new LeafReaderContext(parent, ar, ord, docBase, leaves.size(), leafDocBase);
            leaves.add(atomic);
            return atomic;
          } else {
            final CompositeReader cr = (CompositeReader) reader;
            final List<? extends IndexReader> sequentialSubReaders = cr.getSequentialSubReaders();
            final List<IndexReaderContext> children = Arrays.asList(new IndexReaderContext[sequentialSubReaders.size()]);
            for (int i = 0, c = sequentialSubReaders.size(); i < c; i++) {
              final IndexReader r = sequentialSubReaders.get(i);
              children.set(i, build(newParent, r, i, newDocBase));
              newDocBase += r.maxDoc();
            }
            assert newDocBase == cr.maxDoc();
            return newParent;
          }
        }
      }

    1) 根据StandardDirectoryReader的继承体系,得知参数里面的reader是CompositeReader 类型,于是进入到else分支;

    2)else 分支里面children.set(i, build(newParent, r, i, newDocBase)); 中的r是一个SegmentReader() note : StandardDirectoryReader的构造函数调用链里面会调用基类的构造函数,将SegmentReader塞入到一个List中,而此getSequentialSubReaders(); 返回到便是这个List.

    3)build(newParent, r, i, newDocBase) 递归 调用自身。r是单个SegmentReader, 而LeafReader在它的继承链里面,于是进入到if 分支

    4)leaves.add(atomic); if 分支里面,对单个SegmentReader简单包装后,存入到leaves中

    5)随着循环+递归的执行,所有的SegmentReader都会加入到leaves中。注:实际上leaves存入的是LeafReaderContext类型的数据。在SegmentReader的基类LeafReader中有这么一行代码:

     private final LeafReaderContext readerContext = new LeafReaderContext(this);

    参数this实际就是SegmentReader对象自身

    小结 再回到第五章,第2小节提到的search流程里面

    for (LeafReaderContext ctx : leaves) {
    }

    此时调用链的关系已经非常清楚,解答了第五章第2小节提出的问题:这里面的context和leaves是什么关系,它们和前文提到的SegmentReader又是如何联系到一块的

    每一个ctx里面包含了一个SegmentReader,后面会在每一个SegmentReader里面取检索数据。

4.1 createWeight

//函数调用
search(leafContexts, createWeight(query, results.scoreMode(), 1), results);
  1. 前文那一大坨同名不同参的Search各种大乱调,最终调用的是上面的这个函数,它的参数里面有一个createWeight函数。Weight和打分有关,但是本文只关注拉取倒排、检索相关逻辑,因此下面的叙述会省略掉打分相关的描述。

  2. 进入到下一层调用链:Weight weight = query.createWeight(this, scoreMode, boost); 在前文第章提到query分析后得到TermQuery对象,因此此处调用的实际上是TermQuery类的成员函数createWeight

  3. 接2,进入createWeight看看,函数最终返回的是return new TermWeight(searcher, scoreMode, boost, termState); 记住是TermWeight 类型的对象,下文会用到

4.2 拉取倒排

 BulkScorer scorer = weight.bulkScorer(ctx);

同前文,此处只关注检索部分,忽略打分相关。由4.1可以知道调用的应该是TermWeight对象的成员函数bulkScorer. 不过子类没有实现这个方法,调用的是基类Weight中的方法

  1. bulkScorer逻辑

      public BulkScorer bulkScorer(LeafReaderContext context) throws IOException {
        Scorer scorer = scorer(context);
        if (scorer == null) {
          return null;
        }
        return new DefaultBulkScorer(scorer);
      }

    关键的一行调用:Scorer scorer = scorer(context);

  2. 接1,继续介绍scorer函数,由于子类实现了scorer函数,此处调用的是TermWeight中的方法.

        public Scorer scorer(LeafReaderContext context) throws IOException {
          assert termStates == null || termStates.wasBuiltFor(ReaderUtil.getTopLevelContext(context)) : "The top-reader used to create Weight is not the same as the current reader's top-reader (" + ReaderUtil.getTopLevelContext(context);;
          final TermsEnum termsEnum = getTermsEnum(context);
          if (termsEnum == null) {
            return null;
          }
          LeafSimScorer scorer = new LeafSimScorer(simScorer, context.reader(), term.field(), scoreMode.needsScores());
          if (scoreMode == ScoreMode.TOP_SCORES) {
            return new TermScorer(this, termsEnum.impacts(PostingsEnum.FREQS), scorer);
          } else {
            return new TermScorer(this, termsEnum.postings(null, scoreMode.needsScores() ? PostingsEnum.FREQS : PostingsEnum.NONE), scorer);
          }
        }
  3. 接2继续介绍scorer函数,其中的final TermsEnum termsEnum = getTermsEnum(context); 会为获取搜索query对应的倒排数据做准备,逻辑比较复杂,放到下文的4.3小节讲。termsEnum.postings()是把对应用户搜索query(分词后的term)对应的文档List 倒排数据拉取出来。这部分逻辑同样放到下文4.4小节讲述。

4.3 获取倒排数据前的准备工作

private TermsEnum getTermsEnum(LeafReaderContext context) throws IOException {
      final TermState state = termStates.get(context);
      if (state == null) { // term is not present in that reader
        assert termNotInReader(context.reader(), term) : "no termstate found but term exists in reader term=" + term;
        return null;
      }
      final TermsEnum termsEnum = context.reader().terms(term.field()).iterator();
      termsEnum.seekExact(term.bytes(), state);
      return termsEnum;
    }
  1. 获取termsEnum

    final TermsEnum termsEnum = context.reader().terms(term.field()).iterator();

    从前文可知,这个context里面存储的是SegmentReader,它的基类codecReader实现了terms函数

  2. 接1,继续介绍terms函数。CodecReader的成员函数terms里面调用了return getPostingsReader().terms(field); getPostingsReader调用的是SegmentReader的成员函数,从第章节的第4.3小节知道,它返回的是BlockTreeTermsReader

  3. 接2,进而调用BlockTreeTermsReader的成员函数terms(field)

      public Terms terms(String field) throws IOException {
        assert field != null;
        return fieldMap.get(field);
      }

    从第章第6.2小节可以知道返回的是FieldReader对象

  4. 继续往下走,要调用FieldReader的迭代器iterator()接口,从第章第6.3小节可以看到返回的实际是SegmentTermsEnum

      public TermsEnum iterator() throws IOException {
        return new SegmentTermsEnum(this);
      }
  5. 接4,SegmentTermsEnum 的构造函数里面,定义、初始化FST相关数据,还记得前文提到的Lucene中Term词典是用FST算法格式存储的么?

  6. 再回到getTermsEnum函数的termsEnum.seekExact(term.bytes(), state); 语句调用。这个函数里面将term设置到成员变量中,同时也做了其他成员变量的初始化等操作。接下来进入到4.4 小节继续描述

4.4 将匹配对应Term的文档倒排数据拉出来

回到4.2 第2步的score函数里面,它有如下调用

if (scoreMode == ScoreMode.TOP_SCORES) {
        return new TermScorer(this, termsEnum.impacts(PostingsEnum.FREQS), scorer);
} else {
        return new TermScorer(this, termsEnum.postings(null, scoreMode.needsScores() ? PostingsEnum.FREQS : PostingsEnum.NONE), scorer);
}

impacts和postings都是拉取倒排数据,但是impacts里面使用了跳跃链表等高级技术,为了描述的简洁,此处以termsEnum.postings()为例来介绍,虽然demo中的例子,其实走的是impacts()这条路径

  1. 进入到SegmentTermsEnum的成员函数postings

    位置:org/apache/lucene/codecs/blocktree/SegmentTermsEnum.java

      public PostingsEnum postings(PostingsEnum reuse, int flags) throws IOException {
        assert !eof;
        currentFrame.decodeMetaData();
        return fr.parent.postingsReader.postings(fr.fieldInfo, currentFrame.state, reuse, flags);
      }
  2. 接1,进入decodeMetaData 中,下面这行代码的调用比较关键ste.fr.parent.postingsReader.decodeTerm(bytesReader, ste.fr.fieldInfo, state, absolute); 它实际调用的是Lucene84PostingsReader.java 中的decodeTerm函数。

  3. 接2,decodeTerm函数里面,会读取term对应的doc、pos、pay文件的偏移量

    final long l = in.readVLong();
    if ((l & 0x01) == 0) {
    termState.docStartFP += l >>> 1; //.doc文件
    if (fieldHasPositions) {
          termState.posStartFP += in.readVLong();//.pos文件
          if (fieldHasOffsets || fieldHasPayloads) {
            termState.payStartFP += in.readVLong();//.pay文件
          }
    }

    至此拉取倒排文件的调用全流程已经串联起来了

  4. 再回到1中的fr.parent.postingsReader.postings函数,它调用的是Lucene84PostingsReader.java 中的postings函数

  5. 接4 以postings函数中的EverythingEnum 为例,它会构造本地数据结构,用以容纳从磁盘索引读到的倒排数据。还会将3.中的docStartFP、posStartFP、payStartFP赋值给自己的成员变量。后面遍历倒排数据,实际就是从这些文件句柄里面按照已知的格式读取磁盘数据到内存

6. new TermScore

  TermScorer(Weight weight, PostingsEnum postingsEnum, LeafSimScorer docScorer) {
    super(weight);
    iterator = this.postingsEnum = postingsEnum;
    impactsEnum = new SlowImpactsEnum(postingsEnum);
    impactsDisi = new ImpactsDISI(impactsEnum, impactsEnum, docScorer.getSimScorer());
    this.docScorer = docScorer;
  }

可以看到5中的EverythingEnum 最后赋值给了TermScore的iterator成员变量

前文4.4中已经将term对应的倒排数据拉出来了,此处会遍历倒排数据,获取每一个docid,进行一些操作:

  1. 过滤已经被删除的文档,例如lucene的软删除机制,会在.liv文件里面标志被删除的文档

  2. 打分、排序等

回到本章第2节的scorer.score(leafCollector, ctx.reader().getLiveDocs()); 调用,它会将符合条件的文档,收集到leafCollector中。最终调用的是DefaultBulkScorer中的score函数,进而调用ScoreAll函数

static void scoreAll(LeafCollector collector, DocIdSetIterator iterator, TwoPhaseIterator twoPhase, Bits acceptDocs) throws IOException {
      if (twoPhase == null) {
        for (int doc = iterator.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc = iterator.nextDoc()) {
          if (acceptDocs == null || acceptDocs.get(doc)) {
            collector.collect(doc);
          }
        }
      } else {
        // The scorer has an approximation, so run the approximation first, then check acceptDocs, then confirm
        for (int doc = iterator.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc = iterator.nextDoc()) {
          if ((acceptDocs == null || acceptDocs.get(doc)) && twoPhase.matches()) {
            collector.collect(doc);
          }
        }
      }
    }
  }

我们只看if分支,遍历调用EveryhtingEnum的成员变量nextDoc(),取出一个文档

    public int nextDoc() throws IOException {
      if (docBufferUpto == BLOCK_SIZE) {
        refillDocs();
      }

      doc = (int) docBuffer[docBufferUpto];
      freq = (int) freqBuffer[docBufferUpto];
      posPendingCount += freq;
      docBufferUpto++;

      position = 0;
      lastStartOffset = 0;
      return doc;
    }

可见如果还有数据的话,会返回docBufferUpto索引对应的文档,然后移到下一个准备提取的位置。如果已经超过128了,则重新从磁盘索引文件里面读下一块数据到索引中,具体的工作在函数refillDocs中做。