Zenn
Open17

Apache Lucene の中身を紐解いてみる/ インデックス・マージとは何か？

Java
Elasticsearch
lucene
hassaku63hassaku63

SearchFiles.java

Apache Lucene - Basic Demo Sources Walk-through より

(source: lucene/lucene/demo/src/java/overview.html)

キーになってるぽいクラスがいくつか

  • IndexSearcher
  • StandardAnalyzer
  • QueryParser

QueryParser は analyzer を伴って構成される。 analyzer は（同じインタフェース）でクエリを解釈するためもの。単語の終わりを検出して、"a" や "an", "the" などの無駄なワードを取り除く働きもする

Query オブジェクトは、Searcher から渡される QueryParser のパース結果を含んでいる（ただし、QueryParser を介さなくともプログラム的に Query を構成することはできる）

クエリパーサーは "Lucene query syntax" を Query に変換する。

検索処理は、以下の2つの方法によって実行できる。

  • Streaming: Collector サブクラスは Document ID とそれぞれのマッチングのスコアを出力する
  • Paging: TopScoreDocCollector を使うことで、ページ(?) に対して結果は出力され、関連度などのスコアによってソートされる

※ Paging の仕組みは大量のデータを扱ったり、Kibana などの UI 上で大量の結果をよしなに描画するためのものと思われる。インデックスの仕組みという観点からはあまり関係ないと思われるし、ひとまず Streaming だけ見ておけばよさそう

hassaku63hassaku63

開発環境を構築するにあたって、よく見聞きする maven, ant, gradle などの立ち位置があまりわかっていなかったので以下の記事でだいたいの雰囲気を知る

https://qiita.com/MahoTakara/items/ff73338e218b656bedfa

maven であれば、紹介されている以下のようなコマンドでプロジェクトディレクトリをいい感じに作成することができる模様。

mvn archetype:generate \
  -DgroupId=org.tkr.app \
  -DartifactId=hello-world \
  -DarchetypeArtifactId=maven-archetype-quickstart \
  -DarchetypeVersion=1.4 \
  -DinteractiveMode=false
hassaku63hassaku63

こちらの記事を参考に、とにかくソースを動かしてみる。

https://rindai87.hatenablog.jp/entry/20120102/1325474405

まずは以下のドキュメントに従い Lucene ディストリビューションをダウンロード

https://lucene.apache.org/core/2_9_4/demo.html

今回は 8.11.1 で進める。アーカイブを展開し、展開したディレクトリにカレントを移動。

クラスパスを設定。コロン区切りなので間違えないように。

export CLASSPATH="$(pwd)/core/lucene-core-8.11.1.jar:$(pwd)/demo/lucene-demo-8.11.1.jar"

インデックスを作成する対象として、Lucene のソースレポジトリを clone

git clone https://github.com/apache/lucene.git

デモのソースを動かしてみる。

java org.apache.lucene.demo.IndexFiles
# Usage: java org.apache.lucene.demo.IndexFiles [-index INDEX_PATH] [-docs DOCS_PATH] [-update]
# 
# This indexes the documents in DOCS_PATH, creating a Lucene indexin INDEX_PATH that can be searched with SearchFiles

java org.apache.lucene.demo.IndexFiles -docs lucene/lucene/
# >>> Indexing to directory 'index'...
# >>> adding lucene/lucene/CHANGES.txt
# >>> adding lucene/lucene/JRE_VERSION_MIGRATION.md
# >>> adding lucene/lucene/MIGRATE.md
# >>> adding lucene/lucene/SYSTEM_REQUIREMENTS.md
# >>> adding lucene/lucene/analysis/common/build.gradle
# >>> adding lucene/lucene/analysis/common/src/generated/checksums/generateClassicTokenizer.json
# >>> adding lucene/lucene/analysis/common/src/generated/checksums/generateHTMLCharacterEntities.json
# >>> adding lucene/lucene/analysis/common/src/generated/checksums/generateHTMLStripCharFilter.json
# >>> adding lucene/lucene/analysis/common/src/generated/checksums/generateTlds.json
# >>> adding lucene/lucene/analysis/common/src/generated/checksums/generateUAX29URLEmailTokenizer.json
# >>> adding lucene/lucene/analysis/common/src/generated/checksums/generateUnicodeProps.json
# >>> adding lucene/lucene/analysis/common/src/generated/checksums/generateWikipediaTokenizer.json
# >>> adding lucene/lucene/analysis/common/src/generated/checksums/snowball.json
# >>> ...
# >>> 16839 total milliseconds

成果物として index/ というディレクトリが作成されているので、見に行く

# ls -la index
ls -la
合計 30340
drwxrwxr-x 2 ec2-user ec2-user     288 12月 18 19:40 .
drwxrwxr-x 6 ec2-user ec2-user      74 12月 18 19:39 ..
-rw-rw-r-- 1 ec2-user ec2-user     415 12月 18 19:39 _0.cfe
-rw-rw-r-- 1 ec2-user ec2-user 4923153 12月 18 19:39 _0.cfs
-rw-rw-r-- 1 ec2-user ec2-user     392 12月 18 19:39 _0.si
-rw-rw-r-- 1 ec2-user ec2-user     415 12月 18 19:39 _1.cfe
-rw-rw-r-- 1 ec2-user ec2-user 6610806 12月 18 19:39 _1.cfs
-rw-rw-r-- 1 ec2-user ec2-user     392 12月 18 19:39 _1.si
-rw-rw-r-- 1 ec2-user ec2-user     415 12月 18 19:40 _2.cfe
-rw-rw-r-- 1 ec2-user ec2-user 5162282 12月 18 19:40 _2.cfs
-rw-rw-r-- 1 ec2-user ec2-user     392 12月 18 19:40 _2.si
-rw-rw-r-- 1 ec2-user ec2-user     415 12月 18 19:40 _3.cfe
-rw-rw-r-- 1 ec2-user ec2-user 6804981 12月 18 19:40 _3.cfs
-rw-rw-r-- 1 ec2-user ec2-user     392 12月 18 19:40 _3.si
-rw-rw-r-- 1 ec2-user ec2-user     415 12月 18 19:40 _4.cfe
-rw-rw-r-- 1 ec2-user ec2-user 7440657 12月 18 19:40 _4.cfs
-rw-rw-r-- 1 ec2-user ec2-user     392 12月 18 19:40 _4.si
-rw-rw-r-- 1 ec2-user ec2-user     415 12月 18 19:40 _5.cfe
-rw-rw-r-- 1 ec2-user ec2-user   65000 12月 18 19:40 _5.cfs
-rw-rw-r-- 1 ec2-user ec2-user     392 12月 18 19:40 _5.si
-rw-rw-r-- 1 ec2-user ec2-user     564 12月 18 19:40 segments_1
-rw-rw-r-- 1 ec2-user ec2-user       0 12月 18 19:39 write.lock
hassaku63hassaku63

https://zenn.dev/link/comments/9fc43b95e0c01a

このサンプルソースから生成した .si ファイルを表示してみた。

${ascii_character_type}: ${value_hex_or_string} で表記。

出力結果
PRINTABLE: ?
EXTENDED : 0xd7
PRINTABLE: l
CTRL     : ETB
CTRL     : DC3
PRINTABLE: Lucene90SegmentInfo
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : HT
EXTENDED : 0x9d
PRINTABLE: a
EXTENDED : 0xc9
PRINTABLE: n
EXTENDED : 0xa1
PRINTABLE: i
EXTENDED : 0x8b
EXTENDED : 0x87
EXTENDED : 0xaa
PRINTABLE: 2
EXTENDED : 0xae
EXTENDED : 0xcb
EXTENDED : 0xd3
EXTENDED : 0xfc
PRINTABLE: i
CTRL     : NUL
CTRL     : HT
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : HT
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : SOH
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : SOH
CTRL     : HT
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : HT
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : SOH
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : SOH
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : SOH
EXTENDED : 0xff
CTRL     : BS
CTRL     : HT
PRINTABLE: timestamp
CTRL     : CR
PRINTABLE: 1704663470013
CTRL     : DC4
PRINTABLE: java.runtime.version
CTRL     : SYN
PRINTABLE: 17.0.9+9-Ubuntu-120.04
CTRL     : VT
PRINTABLE: java.vendor
CTRL     : CR
PRINTABLE: Private Build
CTRL     : STX
PRINTABLE: os
CTRL     : ENQ
PRINTABLE: Linux
CTRL     : BEL
PRINTABLE: os.arch
CTRL     : ENQ
PRINTABLE: amd64
CTRL     : LF
PRINTABLE: os.version
CTRL     : SO
PRINTABLE: 5.4.0-1024-aws
CTRL     : SO
PRINTABLE: lucene.version
CTRL     : ENQ
PRINTABLE: 9.9.1
CTRL     : ACK
PRINTABLE: source
CTRL     : ENQ
PRINTABLE: flush
CTRL     : ETX
CTRL     : ACK
PRINTABLE: _1.cfs
CTRL     : ACK
PRINTABLE: _1.cfe
CTRL     : ENQ
PRINTABLE: _1.si
CTRL     : SOH
CTRL     : US
PRINTABLE: Lucene90StoredFieldsFormat.mode
CTRL     : LF
PRINTABLE: BEST_SPEED
CTRL     : NUL
EXTENDED : 0xc0
PRINTABLE: (
EXTENDED : 0x93
EXTENDED : 0xe8
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
CTRL     : NUL
PRINTABLE: ~
EXTENDED : 0x95
EXTENDED : 0xd1
PRINTABLE: 6
hassaku63hassaku63

Lucene99SegmentInfoFormat.java の write メソッドをトレースして、Python で Lucene90SegmentInfo コーデックでエンコードされた .si ファイルをパースして読み込んでみた。

Python のコードは別で commit して公開するとして、si ファイルが持っている構造を print してみた結果がこちら

$ python -m main -t si output/index1/_1.si
byte length = 336

# IndexHeader (offset=0)
## CodecHeader (offset=0)
actual_header (4 bytes): 1071082519, MAGIC = True
codec: Lucene90SegmentInfo
version (4 bytes): 0
## ObjectId (offset=28)
index_header_id (16 bytes): 09 9d 61 c9 6e a1 69 8b 87 aa 32 ae cb d3 fc 69
## ObjectSuffix (offset=44)
suffix_length (1 byte): 0
suffix_length is 0. skip.

# Version (offset=45)
Version: 9.9.1

# [optional] SegMinVersion (offset=57)
SegMinVersion: 9.9.1

# NumDocs (offset=70)
NumDocs: 1
is_compound_file: True
has_blocks: False

# Diagnostics (offset=76)
diagnostics_size (vint): 8
diagnostics: {
  "timestamp": "1704663470013",
  "java.runtime.version": "17.0.9+9-Ubuntu-120.04",
  "java.vendor": "Private Build",
  "os": "Linux",
  "os.arch": "amd64",
  "os.version": "5.4.0-1024-aws",
  "lucene.version": "9.9.1",
  "source": "flush"
}

# Files (offset=254)
files_size (vint): 3
files: [
  "_1.cfs",
  "_1.cfe",
  "_1.si"
]

# Attributes (offset=275)
attributes_size (vint): 1
attributes: {
  "Lucene90StoredFieldsFormat.mode": "BEST_SPEED"
}

# numSortFields (offset=319)
num_sort_fields (vint): 0

# Footer (offset=320)
footer_magic (4 bytes): -1071082520, MAGIC = True
algorithm_id (4 bytes): 0 (is default, zlib-crc32)
checksum (8 bytes): 7e 95 d1 36
actual_checksum   : 7e 95 d1 36
is match checksum?: True

# End of file
seek: 336, total length: 336
EoF: True
hassaku63hassaku63

同じ要領で、フィールド情報を持っている .fnm ファイルをパースしてみた

$ python -m main -t fnm output/index1/_b.fnm
byte length = 774
# IndexHeader (offset=0)
header (4 bytes): 1071082519, MAGIC = True
codec: Lucene94FieldInfos
version (4 bytes): 0
## ObjectId (offset=27)
index_header_id (16 bytes): 62 43 1c ee a7 20 c6 62 cf 3b 3e 8a 1f 2a 5e 2f
## ObjectSuffix (offset=43)
suffix_length (1 byte): 0
suffix_length is 0. skip.
# FieldInfos (offset=44)
field_infos_size (vint): 7
## FieldInfo[0] (offset=63)
field_name: title
field_number: 0
field_bits: FieldBits(store_termvector=False, omit_norms=False, store_payloads=False, soft_deletes_field=False, parent_field_field=False)
index_options: DOCS_AND_FREQS_AND_POSITIONS
doc_vlues: NONE
doc_values_generation: -1
attributes_size (vint): 2
attributes: {
  "PerFieldPostingsFormat.format": "Lucene99",
  "PerFieldPostingsFormat.suffix": "0"
}
point_dimension_count: 0
vector_dimension: 0
vector_encoding: 1
vector_similarity_function: 0
## FieldInfo[1] (offset=166)
field_name: title_no_store
field_number: 1
field_bits: FieldBits(store_termvector=False, omit_norms=False, store_payloads=False, soft_deletes_field=False, parent_field_field=False)
index_options: DOCS_AND_FREQS_AND_POSITIONS
doc_vlues: NONE
doc_values_generation: -1
attributes_size (vint): 2
attributes: {
  "PerFieldPostingsFormat.format": "Lucene99",
  "PerFieldPostingsFormat.suffix": "0"
}
point_dimension_count: 0
vector_dimension: 0
vector_encoding: 1
vector_similarity_function: 0
## FieldInfo[2] (offset=264)
field_name: file_name
field_number: 2
field_bits: FieldBits(store_termvector=False, omit_norms=False, store_payloads=False, soft_deletes_field=False, parent_field_field=False)
index_options: DOCS_AND_FREQS_AND_POSITIONS
doc_vlues: NONE
doc_values_generation: -1
attributes_size (vint): 2
attributes: {
  "PerFieldPostingsFormat.format": "Lucene99",
  "PerFieldPostingsFormat.suffix": "0"
}
point_dimension_count: 0
vector_dimension: 0
vector_encoding: 1
vector_similarity_function: 0
## FieldInfo[3] (offset=360)
field_name: content
field_number: 3
field_bits: FieldBits(store_termvector=False, omit_norms=False, store_payloads=False, soft_deletes_field=False, parent_field_field=False)
index_options: DOCS_AND_FREQS_AND_POSITIONS
doc_vlues: NONE
doc_values_generation: -1
attributes_size (vint): 2
attributes: {
  "PerFieldPostingsFormat.format": "Lucene99",
  "PerFieldPostingsFormat.suffix": "0"
}
point_dimension_count: 0
vector_dimension: 0
vector_encoding: 1
vector_similarity_function: 0
## FieldInfo[4] (offset=467)
field_name: last_modified_time
field_number: 4
field_bits: FieldBits(store_termvector=False, omit_norms=False, store_payloads=False, soft_deletes_field=False, parent_field_field=False)
index_options: DOCS_AND_FREQS_AND_POSITIONS
doc_vlues: NONE
doc_values_generation: -1
attributes_size (vint): 2
attributes: {
  "PerFieldPostingsFormat.format": "Lucene99",
  "PerFieldPostingsFormat.suffix": "0"
}
point_dimension_count: 0
vector_dimension: 0
vector_encoding: 1
vector_similarity_function: 0
## FieldInfo[5] (offset=581)
field_name: last_modified_time_millis
field_number: 5
field_bits: FieldBits(store_termvector=False, omit_norms=False, store_payloads=False, soft_deletes_field=False, parent_field_field=False)
index_options: NONE
doc_vlues: SORTED_NUMERIC
doc_values_generation: -1
attributes_size (vint): 2
attributes: {
  "PerFieldDocValuesFormat.format": "Lucene90",
  "PerFieldDocValuesFormat.suffix": "0"
}
point_dimension_count: 1
point_index_dimension_count: 1
point_num_bytes: 8
vector_dimension: 0
vector_encoding: 1
vector_similarity_function: 0
## FieldInfo[6] (offset=678)
field_name: size
field_number: 6
field_bits: FieldBits(store_termvector=False, omit_norms=False, store_payloads=False, soft_deletes_field=False, parent_field_field=False)
index_options: NONE
doc_vlues: SORTED_NUMERIC
doc_values_generation: -1
attributes_size (vint): 2
attributes: {
  "PerFieldDocValuesFormat.format": "Lucene90",
  "PerFieldDocValuesFormat.suffix": "0"
}
point_dimension_count: 1
point_index_dimension_count: 1
point_num_bytes: 8
vector_dimension: 0
vector_encoding: 1
vector_similarity_function: 0
# Footer (offset=758)
footer_magic (4 bytes): -1071082520, MAGIC = True
algorithm_id (4 bytes): 0 (is default, zlib-crc32)
checksum (8 bytes): ab 31 de f2
actual_checksum   : ab 31 de f2
is match checksum?: True
# End of file
seek: 774, total length: 774
EoF: True
hassaku63hassaku63

https://lucene.apache.org/core/9_9_1/core/org/apache/lucene/codecs/lucene99/package-summary.html#package.description

次は fdx のパースを試みる。

リンク先のクラスは Lucene90StoredFieldsFormat なので次のドキュメントに飛ぶ。

https://lucene.apache.org/core/9_9_1/core/org/apache/lucene/codecs/lucene90/Lucene90StoredFieldsFormat.html

これのソースを見ていくことになる。

// 引用元: lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90StoredFieldsFormat.java

public class Lucene90StoredFieldsFormat extends StoredFieldsFormat {
  // ...

  @Override
  public StoredFieldsWriter fieldsWriter(Directory directory, SegmentInfo si, IOContext context)
      throws IOException {
    String previous = si.putAttribute(MODE_KEY, mode.name());
    if (previous != null && previous.equals(mode.name()) == false) {
      throw new IllegalStateException(
          "found existing value for "
              + MODE_KEY
              + " for segment: "
              + si.name
              + "old="
              + previous
              + ", new="
              + mode.name());
    }
    return impl(mode).fieldsWriter(directory, si, context);
  }

  // ...

  StoredFieldsFormat impl(Mode mode) {
    switch (mode) {
      case BEST_SPEED:
        return new Lucene90CompressingStoredFieldsFormat(
            "Lucene90StoredFieldsFastData", 
            BEST_SPEED_MODE, 
            BEST_SPEED_BLOCK_LENGTH, 
            1024, 10);
      case BEST_COMPRESSION:
        return new Lucene90CompressingStoredFieldsFormat(
            "Lucene90StoredFieldsHighData",
            BEST_COMPRESSION_MODE,
            BEST_COMPRESSION_BLOCK_LENGTH,
            4096,
            10);
      default:
        throw new AssertionError();
    }
  }
hassaku63hassaku63

これまで読んできたソースとは違って直接的な read/write を提供していないので、ひとまず構造や使い方を利用するためにドキュメントを流し読みする。

StoredFieldsFormat は16KB 単位のブロックレベルで LZ4 圧縮を行う。ドキュメントレベルで圧縮するよりも高い圧縮率になるから、らしい。

速度と圧縮率はトレードオフ関係にあり、選択できる。BEST_SPEED をデフォルトとしている。速度を犠牲にして圧縮率を高くするようにもでき、その場合は圧縮単位が 48KB のブロックになる模様。

この圧縮モードは、IndexWriterConfig で設定できるようになっている。

   // the default: for high performance
   indexWriterConfig.setCodec(new Lucene87Codec(Mode.BEST_SPEED));

   // instead for higher performance (but slower):
   indexWriterConfig.setCodec(new Lucene87Codec(Mode.BEST_COMPRESSION));
hassaku63hassaku63

_ Stored fields_ には3種類ある

  1. データファイル .fdt
  2. フィールドインデックスファイル .fdx
  3. フィールドメタデータ .fdm
hassaku63hassaku63

(1) .fdt

16KB もしくはそれ以上のブロックを圧縮した、Document の表現。

Segment を書き込むとき、ドキュメントはインメモリのバッファに追加される。バッファのバイト列が 16KB を超えたとき、いくつかのメタデータがディスクに Flush され、続けて LZ4 圧縮されたバッファが続く。

少なくとも1つのドキュメントが十分に大きく、チャンクが 32KB より大きい場合、チャンクは 16KB の複数個のブロックに圧縮される。こうすると、ドキュメントの最初のフィールドにしか興味がない場合、StoredFieldVisitors は全部のデータを解凍することなく最初の 16KB だけを扱えば良くなる。

圧縮前の長さがチャンクのメタデータに書き込まれるので、解凍する側はこの情報を使って、十分なデータが解凍された時点で解凍処理を止めることができる。

ドキュメントが非圧縮である場合、圧縮フォーマットによるオーバーヘッドは 0.5% 未満である。

読解メモ

ここで言うチャンクって何にかかっているのだろうか？

あと、最後の1文が言ってる意味がよくわからない。incomplessible って「圧縮不可能」という意味に聞こえるのが意味不明なのと、なんのオーバーヘッドなのかが見えない。解凍によって増加する処理時間のこと？

In case documents are incompressible, the overhead of the compression format is less than 0.5%.

hassaku63hassaku63

(2) .fdx

2つの Monotonic arrays を格納している

1つ目は各ブロックの Doc ID、もう1つはディスク上のオフセット。

検索時には、Doc ID が二分探索 (binary search) され、その Doc ID を持つブロックがどれなのかを探し出す。
そして、対応するオフセットを使ってディスクからデータを読み出す

hassaku63hassaku63

(3) fdm

idnex file (fdx) に保存されている _ monotonic arrays_ のメタデータを格納する。