关于java:深度解析-Lucene-轻量级全文索引实现原理

28次阅读

共计 12770 个字符，预计需要花费 32 分钟才能阅读完成。

一、Lucene 简介

1.1 Lucene 是什么？

  • Lucene 是 Apache 基金会 jakarta 项目组的一个子项目；
  • Lucene 是一个开放源码的全文检索引擎工具包，提供了残缺的查问引擎和索引引擎，局部语种文本剖析引擎；
  • Lucene 并不是一个残缺的全文检索引擎，仅提供了全文检索引擎架构，但仍能够作为一个工具包联合各类插件为我的项目 提供局部高性能的全文检索性能；
  • 当初罕用的 ElasticSearch、Solr 等全文搜索引擎均是基于 Lucene 实现的。

1.2 Lucene 的应用场景

实用于须要数据索引量不大的场景，当索引量过大时须要应用 ES、Solr 等全文搜寻服务器实现搜寻性能。

1.3 通过本文你能理解到哪些内容？

  • Lucene 如此繁冗的索引如何生成并写入，索引中的各个文件又在起着什么样的作用？
  • Lucene 全文索引如何进行高效搜寻？
  • Lucene 如何优化搜寻后果，使用户依据关键词搜寻到想要的内容？

本文旨在分享 Lucene 搜索引擎的源码浏览和性能开发中的教训，Lucene 采纳 7.3.1 版本。

二、Lucene 根底工作流程

索引的生成分为两个局部：

1. 创立阶段：

  • 增加文档阶段，通过 IndexWriter 调用 addDocument 办法生成正向索引文件；
  • 文档增加后，通过 flush 或 merge 操作生成倒排索引文件。

2. 搜寻阶段：

  • 用户通过查问语句向 Lucene 发送查问申请；
  • 通过 IndexSearch 下的 IndexReader 读取索引库内容，获取文档索引；
  • 失去搜寻后果后，基于搜索算法对后果进行排序后返回。

索引创立及搜寻流程如下图所示：

三、Lucene 索引形成

3.1 正向索引

Lucene 的根底层次结构由 索引、段、文档、域、词 五个局部组成。正向索引的生成即为基于 Lucene 的根底层次结构一级一级解决文档并合成域存储词的过程。

索引文件层级关系如图 1 所示：

  • 索引：Lucene 索引库蕴含了搜寻文本的所有内容，能够通过文件或文件流的形式存储在不同的数据库或文件目录下。
  • 段：一个索引中蕴含多个段，段与段之间互相独立。因为 Lucene 进行关键词检索时须要加载索引段进行下一步搜寻，如果索引段较多会减少较大的 I / O 开销，减慢检索速度，因而写入时会通过段合并策略对不同的段进行合并。
  • 文档：Lucene 会将文档写入段中，一个段中蕴含多个文档。
  • 域：一篇文档会蕴含多种不同的字段，不同的字段保留在不同的域中。
  • 词：Lucene 会通过分词器将域中的字符串通过词法剖析和语言解决后拆分成词，Lucene 通过这些关键词进行全文检索。

3.2 倒排索引

Lucene 全文索引的外围是基于倒排索引实现的疾速索引机制。

倒排索引原理如图 2 所示，倒排索引简略来说就是基于分析器将文本内容进行分词后，记录每个词呈现在哪篇文章中，从而通过用户输出的搜索词查问出蕴含该词的文章。

问题：上述倒排索引应用时每次都须要将索引词加载到内存中，当文章数量较多，篇幅较长时，索引词可能会占用大量的存储空间，加载到内存后内存损耗较大。

解决方案：从 Lucene4 开始，Lucene 采纳了 FST 来缩小索引词带来的空间耗费。

FST(Finite StateTransducers)，中文名无限状态机转换器。其次要特点在于以下四点：

  • 查找词的工夫复杂度为 O(len(str))；
  • 通过将前缀和后缀离开存储的形式，缩小了寄存词所需的空间；
  • 加载时仅将前缀放入内存索引，后缀词在磁盘中进行寄存，缩小了内存索引应用空间的损耗；
  • FST 构造在对 PrefixQuery、FuzzyQuery、RegexpQuery 等查问条件查问时，查问效率高。

具体存储形式如图 3 所示：

倒排索引相干文件蕴含.tip、.tim 和.doc 这三个文件，其中：

  • tip：用于保留倒排索引 Term 的前缀，来疾速定位.tim 文件中属于这个 Field 的 Term 的地位，即上图中的 aab、abd、bdc。
  • tim：保留了不同前缀对应的相应的 Term 及相应的倒排表信息，倒排表通过跳表实现疾速查找，通过跳表可能跳过一些元素的形式对多条件查问交加、并集、差集之类的汇合运算也进步了性能。
  • doc：蕴含了文档号及词频信息，依据倒排表中的内容返回该文件中保留的文本信息。

3.3 索引查问及文档搜寻过程

Lucene 利用倒排索引定位须要查问的文档号，通过文档号搜寻出文件后，再利用词权重等信息对文档排序后返回。

  • 内存加载 tip 文件，依据 FST 匹配到后缀词块在 tim 文件中的地位；
  • 依据查问到的后缀词块地位查问到后缀及倒排表的相干信息；
  • 依据 tim 中查问到的倒排表信息从 doc 文件中定位出文档号及词频信息，实现搜寻；
  • 文件定位实现后 Lucene 将去.fdx 文件目录索引及.fdt 中依据正向索引查找出指标文件。

文件格式如图 4 所示：

上文次要解说 Lucene 的工作原理，下文将论述 Java 中 Lucene 执行索引、查问等操作的相干代码。

四、Lucene 的增删改操作

Lucene 我的项目中文本的解析，存储等操作均由 IndexWriter 类实现，IndexWriter 文件次要由 Directory 和 IndexWriterConfig 两个类形成，其中：

Directory：用于指定寄存索引文件的目录类型。既然要对文本内容进行搜寻，天然须要先将这些文本内容及索引信息写入到目录里。Directory 是一个抽象类，针对索引的存储容许有多种不同的实现。常见的存储形式个别包含存储有本地（FSDirectory），内存（RAMDirectory）等。

IndexWriterConfig：用于指定 IndexWriter 在文件内容写入时的相干配置，包含 OpenMode 索引构建模式、Similarity 相关性算法等。

IndexWriter 具体是如何操作索引的呢？让咱们来简略剖析一下 IndexWriter 索引操作的相干源码。

4.1. 文档的新增

a. Lucene 会为每个文档创立 ThreadState 对象，对象持有 DocumentWriterPerThread 来执行文件的增删改操作；

ThreadState getAndLock(Thread requestingThread, DocumentsWriter documentsWriter) {
  ThreadState threadState = null;
  synchronized (this) {if (freeList.isEmpty()) {
      // 如果不存在已创立的闲暇 ThreadState，则新创建一个
      return newThreadState();} else {
      // freeList 后进先出，仅应用无限的 ThreadState 操作索引
      threadState = freeList.remove(freeList.size()-1);

      // 优先应用曾经初始化过 DocumentWriterPerThread 的 ThreadState，并将其与以后
      // ThreadState 换位，将其移到队尾优先应用
      if (threadState.dwpt == null) {for(int i=0;i<freeList.size();i++) {ThreadState ts = freeList.get(i);
          if (ts.dwpt != null) {freeList.set(i, threadState);
            threadState = ts;
            break;
          }
        }
      }
    }
  }
  threadState.lock();
  
  return threadState;
}

b. 索引文件的插入：DocumentWriterPerThread 调用 DefaultIndexChain 下的 processField 来解决文档中的每个域，processField 办法是索引链的外围执行逻辑。通过用户对每个域设置的不同的 FieldType 进行相应的索引、分词、存储等操作。FieldType 中比拟重要的是 indexOptions：

  • NONE：域信息不会写入倒排表，索引阶段无奈通过该域名进行搜寻；
  • DOCS：文档写入倒排表，但因为不记录词频信息，因而呈现屡次也仅当一次解决；
  • DOCS\_AND\_FREQS：文档和词频写入倒排表；
  • DOCS\_AND\_FREQS\_AND\_POSITIONS：文档、词频及地位写入倒排表；
  • DOCS\_AND\_FREQS\_AND\_POSITIONS\_AND\_OFFSETS：文档、词频、地位及偏移写入倒排表。
// 构建倒排表

if (fieldType.indexOptions() != IndexOptions.NONE) {fp = getOrAddField(fieldName, fieldType, true);
    boolean first = fp.fieldGen != fieldGen;
    // field 具体的索引、分词操作
    fp.invert(field, first);

    if (first) {fields[fieldCount++] = fp;
      fp.fieldGen = fieldGen;
    }
} else {verifyUnIndexedFieldType(fieldName, fieldType);
}

// 存储该 field 的 storeField
if (fieldType.stored()) {if (fp == null) {fp = getOrAddField(fieldName, fieldType, false);
  }
  if (fieldType.stored()) {String value = field.stringValue();
    if (value != null && value.length() > IndexWriter.MAX_STORED_STRING_LENGTH) {throw new IllegalArgumentException("stored field \"" + field.name() + "\" is too large ("+ value.length() +" characters) to store");
    }
    try {storedFieldsConsumer.writeField(fp.fieldInfo, field);
    } catch (Throwable th) {throw AbortingException.wrap(th);
    }
  }
}

// 建设 DocValue（通过文档查问文档下蕴含了哪些词）DocValuesType dvType = fieldType.docValuesType();
if (dvType == null) {throw new NullPointerException("docValuesType must not be null (field: \"" + fieldName + "\")");
}
if (dvType != DocValuesType.NONE) {if (fp == null) {fp = getOrAddField(fieldName, fieldType, false);
  }
  indexDocValue(fp, dvType, field);
}
if (fieldType.pointDimensionCount() != 0) {if (fp == null) {fp = getOrAddField(fieldName, fieldType, false);
  }
  indexPoint(fp, field);
}

c. 解析 Field 首先须要结构 TokenStream 类，用于产生和转换 token 流，TokenStream 有两个重要的派生类 Tokenizer 和 TokenFilter，其中 Tokenizer 用于通过 java.io.Reader 类读取字符，产生 Token 流，而后通过任意数量的 TokenFilter 来解决这些输出的 Token 流，具体源码如下：

// invert：对 Field 进行分词解决首先须要将 Field 转化为 TokenStream
try (TokenStream stream = tokenStream = field.tokenStream(docState.analyzer, tokenStream))
// TokenStream 在不同分词器下实现不同，依据不同分词器返回相应的 TokenStream
if (tokenStream != null) {return tokenStream;} else if (readerValue() != null) {return analyzer.tokenStream(name(), readerValue());
} else if (stringValue() != null) {return analyzer.tokenStream(name(), stringValue());
}

public final TokenStream tokenStream(final String fieldName, final Reader reader) {
  // 通过复用策略，如果 TokenStreamComponents 中曾经存在 Component 则复用。TokenStreamComponents components = reuseStrategy.getReusableComponents(this, fieldName);
  final Reader r = initReader(fieldName, reader);
  // 如果 Component 不存在，则依据分词器创立对应的 Components。if (components == null) {components = createComponents(fieldName);
    reuseStrategy.setReusableComponents(this, fieldName, components);
  }
  // 将 java.io.Reader 输出流传入 Component 中。components.setReader(r);
  return components.getTokenStream();}

d. 依据 IndexWriterConfig 中配置的分词器，通过策略模式返回分词器对应的分词组件，针对不同的语言及不同的分词需要，分词组件存在很多不同的实现。

  • StopAnalyzer：停用词分词器，用于过滤词汇中特定字符串或单词。
  • StandardAnalyzer：规范分词器，可能依据数字、字母等进行分词，反对词表过滤代替 StopAnalyzer 性能，反对中文简略分词。
  • CJKAnalyzer：可能依据中文语言习惯对中文分词提供了比拟好的反对。

 以 StandardAnalyzer（规范分词器）为例：

// 规范分词器创立 Component 过程，涵盖了规范分词处理器、Term 转化小写、常用词过滤三个性能
protected TokenStreamComponents createComponents(final String fieldName) {final StandardTokenizer src = new StandardTokenizer();
  src.setMaxTokenLength(maxTokenLength);
  TokenStream tok = new StandardFilter(src);
  tok = new LowerCaseFilter(tok);
  tok = new StopFilter(tok, stopwords);
  return new TokenStreamComponents(src, tok) {
    @Override
    protected void setReader(final Reader reader) {src.setMaxTokenLength(StandardAnalyzer.this.maxTokenLength);
      super.setReader(reader);
    }
  };
}

e. 在获取 TokenStream 之后通过 TokenStream 中的 incrementToken 办法剖析并获取属性，再通过 TermsHashPerField 下的 add 办法构建倒排表，最终将 Field 的相干数据存储到类型为 FreqProxPostingsArray 的 freqProxPostingsArray 中，以及 TermVectorsPostingsArray 的 termVectorsPostingsArray 中，形成倒排表;

// 以 LowerCaseFilter 为例，通过其下的 increamentToken 将 Token 中的字符转化为小写
public final boolean incrementToken() throws IOException {if (input.incrementToken()) {CharacterUtils.toLowerCase(termAtt.buffer(), 0, termAtt.length());
    return true;
  } else
    return false;
}
  try (TokenStream stream = tokenStream = field.tokenStream(docState.analyzer, tokenStream)) {
    // reset TokenStream
    stream.reset();
    invertState.setAttributeSource(stream);
    termsHashPerField.start(field, first);
    // 剖析并获取 Token 属性
    while (stream.incrementToken()) {
      ……
      try {
        // 构建倒排表
        termsHashPerField.add();} catch (MaxBytesLengthExceededException e) {……} catch (Throwable th) {throw AbortingException.wrap(th);
      }
    }
    ……
}

4.2 文档的删除

a. Lucene 下文档的删除，首先将要删除的 Term 或 Query 增加到删除队列中；

synchronized long deleteTerms(final Term... terms) throws IOException {
  // TODO why is this synchronized?
  final DocumentsWriterDeleteQueue deleteQueue = this.deleteQueue;
  // 文档删除操作是将删除的词信息增加到删除队列中，依据 flush 策略进行删除
  long seqNo = deleteQueue.addDelete(terms);
  flushControl.doOnDelete();
  lastSeqNo = Math.max(lastSeqNo, seqNo);
  if (applyAllDeletes(deleteQueue)) {seqNo = -seqNo;}
  return seqNo;
}

b. 依据 Flush 策略触发删除操作;

private boolean applyAllDeletes(DocumentsWriterDeleteQueue deleteQueue) throws IOException {
  // 判断是否满足删除条件 --> onDelete
  if (flushControl.getAndResetApplyAllDeletes()) {if (deleteQueue != null) {ticketQueue.addDeletes(deleteQueue);
    }
    // 指定执行删除操作的 event
    putEvent(ApplyDeletesEvent.INSTANCE); // apply deletes event forces a purge
    return true;
  }
  return false;
}
public void onDelete(DocumentsWriterFlushControl control, ThreadState state) {
  // 判断并设置是否满足删除条件
  if ((flushOnRAM() && control.getDeleteBytesUsed() > 1024*1024*indexWriterConfig.getRAMBufferSizeMB())) {control.setApplyAllDeletes();
    if (infoStream.isEnabled("FP")) {infoStream.message("FP", "force apply deletes bytesUsed=" + control.getDeleteBytesUsed() + "vs ramBufferMB=" + indexWriterConfig.getRAMBufferSizeMB());
    }
  }
}

4.3 文档的更新

文档的更新就是一个先删除后插入的过程，本文就不再做更多赘述。

4.4 索引 Flush

文档写入到肯定数量后，会由某一线程触发 IndexWriter 的 Flush 操作，生成段并将内存中的 Document 信息写到硬盘上。Flush 操作目前仅有一种策略：FlushByRamOrCountsPolicy。FlushByRamOrCountsPolicy 次要基于两种策略主动执行 Flush 操作：

  • maxBufferedDocs：文档收集到肯定数量时触发 Flush 操作。
  • ramBufferSizeMB：文档内容达到限定值时触发 Flush 操作。

其中 activeBytes() 为 dwpt 收集的索引所占的内存量，deleteByteUsed 为删除的索引量。

@Override
public void onInsert(DocumentsWriterFlushControl control, ThreadState state) {
  // 依据文档数进行 Flush
  if (flushOnDocCount()
      && state.dwpt.getNumDocsInRAM() >= indexWriterConfig
          .getMaxBufferedDocs()) {
    // Flush this state by num docs
    control.setFlushPending(state);
  // 依据内存使用量进行 Flush
  } else if (flushOnRAM()) {// flush by RAM
    final long limit = (long) (indexWriterConfig.getRAMBufferSizeMB() * 1024.d * 1024.d);
    final long totalRam = control.activeBytes() + control.getDeleteBytesUsed();
    if (totalRam >= limit) {if (infoStream.isEnabled("FP")) {infoStream.message("FP", "trigger flush: activeBytes=" + control.activeBytes() + "deleteBytes=" + control.getDeleteBytesUsed() + "vs limit=" + limit);
      }
      markLargestWriterPending(control, state, totalRam);
    }
  }
}

将内存信息写入索引库。

索引的 Flush 分为被动 Flush 和主动 Flush，依据策略触发的 Flush 操作为主动 Flush，被动 Flush 的执行与主动 Flush 有较大区别，对于被动 Flush 本文暂不多做赘述。须要理解的话能够跳转链接。

4.5 索引段 Merge

索引 Flush 时每个 dwpt 会独自生成一个 segment，当 segment 过多时进行全文检索可能会跨多个 segment，产生屡次加载的状况，因而须要对过多的 segment 进行合并。

段合并的执行通过 MergeScheduler 进行治理。mergeScheduler 也蕴含了多种管理策略，包含 NoMergeScheduler、SerialMergeScheduler 和 ConcurrentMergeScheduler。

1) merge 操作首先须要通过 updatePendingMerges 办法依据段的合并策略查问须要合并的段。段合并策略分为很多种，本文仅介绍两种 Lucene 默认应用的段合并策略：TieredMergePolicy 和 LogMergePolicy。

  • TieredMergePolicy：先通过 OneMerge 打分机制对 IndexWriter 提供的段集进行排序，而后在排序后的段集中选取局部（可能不间断）段来生成一个待合并段集，即非相邻的段文件（Non-adjacent Segment）。
  • LogMergePolicy：定长的合并形式，通过 maxLevel、LEVEL\_LOG\_SPAN、levelBottom 参数将间断的段分为不同的层级，再通过 mergeFactor 从每个层级中选取段进行合并。
private synchronized boolean updatePendingMerges(MergePolicy mergePolicy, MergeTrigger trigger, int maxNumSegments)
  throws IOException {

  final MergePolicy.MergeSpecification spec;
  // 查问须要合并的段
  if (maxNumSegments != UNBOUNDED_MAX_MERGE_SEGMENTS) {
    assert trigger == MergeTrigger.EXPLICIT || trigger == MergeTrigger.MERGE_FINISHED :
    "Expected EXPLICT or MERGE_FINISHED as trigger even with maxNumSegments set but was:" + trigger.name();

    spec = mergePolicy.findForcedMerges(segmentInfos, maxNumSegments, Collections.unmodifiableMap(segmentsToMerge), this);
    newMergesFound = spec != null;
    if (newMergesFound) {final int numMerges = spec.merges.size();
      for(int i=0;i<numMerges;i++) {final MergePolicy.OneMerge merge = spec.merges.get(i);
        merge.maxNumSegments = maxNumSegments;
      }
    }
  } else {spec = mergePolicy.findMerges(trigger, segmentInfos, this);
  }
  // 注册所有须要合并的段
  newMergesFound = spec != null;
  if (newMergesFound) {final int numMerges = spec.merges.size();
    for(int i=0;i<numMerges;i++) {registerMerge(spec.merges.get(i));
    }
  }
  return newMergesFound;
}

2）通过 ConcurrentMergeScheduler 类中的 merge 办法创立用户合并的线程 MergeThread 并启动。

@Override
public synchronized void merge(IndexWriter writer, MergeTrigger trigger, boolean newMergesFound) throws IOException {
  ……
  while (true) {
    ……
    // 取出注册的后选段
    OneMerge merge = writer.getNextMerge();
    boolean success = false;
    try {
      // 构建用于合并的线程 MergeThread 
      final MergeThread newMergeThread = getMergeThread(writer, merge);
      mergeThreads.add(newMergeThread);

      updateIOThrottle(newMergeThread.merge, newMergeThread.rateLimiter);

      if (verbose()) {message("launch new thread [" + newMergeThread.getName() + "]");
      }
      // 启用线程
      newMergeThread.start();
      updateMergeThreads();

      success = true;
    } finally {if (!success) {writer.mergeFinish(merge);
      }
    }
  }
}

3）通过 doMerge 办法执行 merge 操作；

public void merge(MergePolicy.OneMerge merge) throws IOException {
  ……
      try {
        // 用于解决 merge 前缓存工作及新段相干信息生成
        mergeInit(merge);
        // 执行段之间的 merge 操作
        mergeMiddle(merge, mergePolicy);
        mergeSuccess(merge);
        success = true;
      } catch (Throwable t) {handleMergeException(t, merge);
      } finally {
        // merge 实现后的收尾工作
        mergeFinish(merge)
      }
……
}

五、Lucene 搜寻性能实现

5.1 加载索引库

Lucene 想要执行搜寻首先须要将索引段加载到内存中，因为加载索引库的操作十分耗时，因而仅有当索引库产生变动时须要从新加载索引库。

加载索引库分为加载段信息和加载文档信息两个局部：

1）加载段信息：

  • 通过 segments.gen 文件获取段中最大的 generation，获取段整体信息；
  • 读取.si 文件，结构 SegmentInfo 对象，最初汇总失去 SegmentInfos 对象。

2）加载文档信息：

  • 读取段信息，并从.fnm 文件中获取相应的 FieldInfo，结构 FieldInfos；
  • 关上倒排表的相干文件和词典文件；
  • 读取索引的统计信息和相干 norms 信息；
  • 读取文档文件。

5.2 封装

索引库加载实现后须要 IndexReader 封装进 IndexSearch，IndexSearch 通过用户结构的 Query 语句和指定的 Similarity 文本类似度算法（默认 BM25）返回用户须要的后果。通过 IndexSearch.search 办法实现搜寻性能。

搜寻：Query 蕴含多种实现，包含 BooleanQuery、PhraseQuery、TermQuery、PrefixQuery 等多种查询方法，使用者可依据我的项目需要结构查问语句

排序：IndexSearch 除了通过 Similarity 计算文档相关性分值排序外，也提供了 BoostQuery 的形式让用户指定关键词分值，定制排序。Similarity 相关性算法也蕴含很多种不同的相关性分值计算实现，此处暂不做赘述，读者有须要可自行网上查阅。

六、总结

Lucene 作为全文索引工具包，为中小型我的项目提供了弱小的全文检索性能反对，但 Lucene 在应用的过程中存在诸多问题：

  • 因为 Lucene 须要将检索的索引库通过 IndexReader 读取索引信息并加载到内存中以实现其检索能力，当索引量过大时，会耗费服务部署机器的过多内存。
  • 搜寻实现比较复杂，须要对每个 Field 的索引、分词、存储等信息一一设置，应用简单。
  • Lucene 不反对集群。

Lucene 应用时存在诸多限度，应用起来也不那么不便，当数据量增大时还是尽量抉择 ElasticSearch 等分布式搜寻服务器作为搜寻性能的实现计划。

作者：vivo 互联网服务器团队 -Qian Yulun

正文完
java
发表至： java
2021-07-20
 0
关于java:Ubuntu环境DockerK8sDashboard的安装配置无坑亲测
关于java:面试官在-Java-中-new-一个对象的流程是怎样的彻底被问懵了
H3BPM关于钉钉免登失败的处理
关于java:深入理解Java的继承特性