エムスリーエンジニアリンググループ AI・機械学習チームでソフトウェアエンジニアをしている中村(@po3rin) です。
弊社では毎週水曜日にElasticsearchとLuceneのコードリーディング会が開催されています。最近ではLuceneのFSTやKD-Tree、もうすぐ公開されるNSWの実装周りを読んでいました。
先日、私の発表回でLuceneのメモリ上での転置インデックスのデータ構造について発表したので、その内容を紹介します。Luceneのことが少しでも身近に感じていただければ幸いです。
Luceneとは
Elasticsearchの内部で利用されているオープンソースの検索エンジンライブラリです。あらかじめ蓄積した大量のデータから指定したキーワードを探し出す機能などがJavaのクラスライブラリとして提供されています。
Luceneに触れるのが初めての人は私の過去ブログがおすすめです。
今回はApache Lucene 8.8.1のコードを見ていきます。
転置インデックスに関する事前知識
転置インデックスは、クエリのタームに対応するドキュメントID、出現位置、出現頻度などのデータを高速に取得するための索引データ構造です タームはドキュメントやクエリに含まれる構成単位であり、日本語においては形態素解析をした結果のトークンであることが多いです。
転置インデックスを構成するコンポーネントは主にポスティングリストと辞書の2つがあります。 ポスティングリストは実際にそのタームがどのドキュメントでどの位置に出現したかなどを保存します。 辞書は、タームから、そのタームの出現位置などを記録したポスティングリストを引くためのデータ構造です。
例えば辞書をハッシュテーブル、ポスティングリストを展開リンクリスト(unrolled linked list) で実装した場合は下記のような形になります。
これらの詳しい解説やGoによる簡易的な実装を試したブログを公開しているのでもしよろしければご覧ください。
Luceneの事前知識
LuceneのIndex処理の全体像は下図になります。
まずはメモリ上で転置インデックスを構築し、定期的、もしくはRAM使用量が閾値を超えるとセグメント化と呼ばれる永続化処理が走ります。今回はMemory Bufferでの転置インデックス構造を追っていきます。
LuceneではIndexWriterクラスがインデックス書き込みの責務を持っており、addDocumentを呼ぶことでドキュメントをインデックスできます。
IndexWriterの最終到達地点がメモリ上での転置インデックスであり、永続化するタイミングは別途IndexWriterConfigで設定できます。よってメモリ上での転置インデックスの構造を覗きたければIndexWriterのコードを読んでいくことになります。
IndexWriterを読んでいくとPerField.invertというフィールドごとにドキュメントを格納していくクラスが見つかります。
private final class PerField implements Comparable<PerField> { // ... FieldInvertState invertState; TermsHashPerField termsHashPerField; // ... public void invert(int docID, IndexableField field, boolean first) throws IOException { // ... try (TokenStream stream = tokenStream = field.tokenStream(analyzer, tokenStream)) { stream.reset(); invertState.setAttributeSource(stream); termsHashPerField.start(field, first); while (stream.incrementToken()) { try { // termsHashPerFieldにトークンを情報を格納する termsHashPerField.add(invertState.termAttribute.getBytesRef(), docID); } catch (MaxBytesLengthExceededException e) { // ... } // ...
Analyzerでドキュメントをタームに分割して作成したTokenStreamを１つずつTermsHashPerFieldに格納しています。よって今回はTermsHashPerFieldで転置インデックスがメモリ上でどのように構築されているかが論点となります。
Luceneのメモリ上での転置インデックス実装内部
先にTermsHashPerFieldの概要を図にしたものをお見せします。
BytesRefHashが転置インデックスのコンポーネントで言う所の辞書であり、実装はハッシュテーブルとなっています。TokenStreamで渡ってくるタームをハッシュテーブルに格納しています。bytesStartがポスティングリストの位置を保持します。ポスティングリストはByteBlockPoolで表現されていて、そのタームのドキュメントIDや出現位置を格納します。
まずは辞書の部分についてみていきましょう。辞書に関しての実装を覗くとbytesHash.addで辞書にタームを格納しているのがわかります。
abstract class TermsHashPerField implements Comparable<TermsHashPerField> { // ... void add(BytesRef termBytes, final int docID) throws IOException { assert assertDocId(docID); int termID = bytesHash.add(termBytes); if (termID >= 0) { // New posting initStreamSlices(termID, docID); } else { termID = positionStreamSlice(termID, docID); } if (doNextCall) { nextPerField.add(postingsArray.textStarts[termID], docID); } } // ...
BytesRefHashのaddをみていきます。
public int add(BytesRef bytes) { assert bytesStart != null : "Bytesstart is null - not initialized"; final int length = bytes.length; // final position final int hashPos = findHash(bytes); int e = ids[hashPos]; if (e == -1) { // new entry // ... e = count++; // ... return e; } return -(e + 1); }
findHash という関数名からも分かる通り、termをハッシュ化してハッシュテーブルに格納しています。
関数の返り値として0からインクリメントされるタームのIDを返しています。もしすでに存在していた場合はそのIDに1足してマイナスをつけた-(e + 1)を返しています。これですでにタームが存在していた場合を判定しています。
ここでデバッグプリントを挟んで、field field filedというstreamを空のFiledにindexする場合にどうなるか見てみます。
void add(BytesRef termBytes, final int docID) throws IOException { // ... int termID = bytesHash.add(termBytes); // ... System.out.println("add term=" + termBytes.utf8ToString() + " doc=" + docID + "termID=" + termID); } // ...
これでテスト用のドキュメントを書き換えてテスト実行すると下記のようになります。
add term=field doc=0 termID=0 add term=field doc=0 termID=-1 add term=field doc=0 termID=-1
最初の"field"はまだ辞書に存在しないのでtermID=0を返しますが、続く"field"はすでに存在しているのでtermID=-1を返しています。
ここまでのコードでタームのbytesとドキュメントIDと重複情報を含むタームIDが用意できていることが確認できます。
これらをポスティングリストに格納しています。新しいタームだった場合に呼ばれるTermsHashPerField.add内でtermID>=0の時に呼ばれるinitStreamSlicesをみていきたいのですが、少し処理やコードがわかりづらいのでデバッグプリントを仕込んでどんな転置インデックスができるかを直接みていきます。実装の詳細に興味のある方はTermsHashPerField.javaのinitStreamSlicesメソッドをご覧ください。
initStreamSlicesに下記のようなプリントを挟みます。
private void initStreamSlices(int termID, int docID) throws IOException { // （省略） System.out.println("INFO: " + Arrays.toString(Arrays.copyOfRange(bytePool.buffers[0], 0, 50))); }
DocHelper.javaで用意されている"one filed text"というドキュメントを格納する場合は下記のような出力が得られます。
INFO: add term=one doc=0termID=0 INFO: [3, 111, 110, 101, 0, 0, 0, 0, 16, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] INFO: add term=field doc=0termID=1 INFO: [3, 111, 110, 101, 0, 0, 0, 0, 16, 0, 0, 0, 0, 16, 5, 102, 105, 101, 108, 100, 0, 0, 0, 0, 16, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] INFO: add term=text doc=0termID=2 INFO: [3, 111, 110, 101, 0, 0, 0, 0, 16, 0, 0, 0, 0, 16, 5, 102, 105, 101, 108, 100, 0, 0, 0, 0, 16, 2, 0, 0, 0, 16, 4, 116, 101, 120, 116, 0, 0, 0, 0, 16, 4, 0, 0, 0, 16, 0, 0, 0, 0, 0]
1タームずつbyte列に情報を格納しています。わかりやすいように転置インデックスの概要図を再掲します。
黄から次の黄の範囲までが１つのタームを表します。黄はターム文字列のbyte長を表し、赤はターム文字列のbyte表現を格納します。水色はdoc_idとタームの出現頻度を格納し、ピンクはタームの出現位置を差分リストとして格納します(メモリの節約のため)。
単語でポスティングリストにアクセスするときはタームをハッシュ化したのちにBytesRefHashのids、byteStartと辿っていけば該当するポスティングリストの位置を取得できます。
確保したメモリがあふれた場合
実装の説明は省略しますが、ついでに"one two one one one one one one"の場合にどうなるかを説明します。
下図のように、"one"のposition用に確保したメモリが埋まった場合は、次のメモリバッファの空きにpositionを埋め込んで行きます。元のpositionが入っていた位置には次のpositionを格納している位置を格納します。この形からLuceneのメモリ転置インデックスがデータ構造が展開リンクリストになっていることがわかります。
使用するbyteBlockのサイズがどのように大きくなっていくかはByteBlockPool.javaに定義があります。
// in ByteBlockPool.java public static final int[] LEVEL_SIZE_ARRAY = {5, 14, 20, 30, 40, 40, 80, 80, 120, 200};
詳しい実装はTermsHashPerField.javaのpositionStreamSliceメソッド配下をご覧ください。
ここまででLuceneのメモリ上での転置インデックス構造を大雑把に見ることができました。もしByteBlockPoolのbufferがいっぱいになった場合は次のbufferを用意してそこにデータを詰めていきます。
まとめ
今回は弊社でやっているElasticsearch/Luceneコードリーディング会の内容を少しだけお見せしました。転置インデックスの構造から復習し、Luceneのメモリ上での転置インデックスの実装を覗くことで少し検索エンジンが身近に感じられるようになったと思います。転置インデックスの仕組みについてもっと探求したい方は下記の書籍がオススメです。
次回はメモリからディスクへの永続化の部分を追っていこうと思います。
Elasticsearch/Luceneコードリーディング会は毎週水曜にやっているので、これからもどんどんElasticsearchやLuceneの内部について発信していければと思います。
We're hiring !!!
エムスリーでは検索&推薦基盤の開発&改善を通して医療を前進させるエンジニアを募集しています！ 社内では日々検索や推薦についての議論が活発に行われています。
「ちょっと話を聞いてみたいかも」という人はこちらから！ jobs.m3.com
