深度解析 Lucene 輕量級全文索引實現原理

作者：vivo 互聯網服務器團隊 - Qian Yulun

一、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 基礎工作流程

索引的生成分爲兩個部分：

創建階段：

添加文檔階段，通過 IndexWriter 調用 addDocument 方法生成正向索引文件；
文檔添加後，通過 flush 或 merge 操作生成倒排索引文件。

搜索階段：

用戶通過查詢語句向 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。

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 等分佈式搜索服務器作爲搜索功能的實現方案。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/_oT38Ra9QXiDKNjG3r7mAQ

猜你喜歡