エムスリーテックブログ

エムスリー(m3)のエンジニア・開発メンバーによる技術ブログです

Elasticsearchコードリーディング 〜Luceneの検索のコードを読み解く〜

Elasticsearch

エムスリー Advent Calendar 2020 まで残り 7 日です！ Advent Calendar本編に先んじて新卒1〜2年目メンバーが執筆します！

エムスリーのエンジニアリンググループ AI・機械学習チームの新卒1年目の丸尾です。エムスリーには一昨年の夏に、インターンをしていて、その際の体験も記事にしているので、こちらもご覧ください！

www.m3tech.blog

はじめに

私は主に Elasticsearch を用いた検索プロジェクトを担当しています。Elasticsearchへの理解がまだまだ不十分だと感じ、今期からはプロジェクトのメンバーを巻き込んで、Elasticsearch/Lucene のソースコードリーディングの勉強会を開いています。目標は各自がElasticsearchかLuceneにPull Requestを投げつけることです。

今回の記事では、これまでの勉強会で発表した内容をまとめて、次の2点について整理しました。

  • LuceneインデックスのAPIをデモコードを通して触ってみる
  • クエリのための Query クラスの内部を見て、LuceneインデックスのAPIの使われ方を見てみる

インデックスの作成と読み取りをする

まずは、Luceneライブラリを用いて、インデックスの作成を行います。そのあとに、作成されたインデックスへ検索を行ってみます。 さらに踏み込んで、特定の単語が存在するかの判定、単語の出現箇所をリストアップを行い、一段低レイヤーのAPIを扱ってみます。

インデックスの作成をする

兎にも角にもまずはLuceneのインデックスがないといろんなことを試せません。 IndexWriter クラスを用いて適当な文章を読み込んで、次のコードのようにインデックスを作成してみましょう。

Directory directory = FSDirectory.open(Paths.get("./data/index"));
StandardAnalyzer analyzer = new StandardAnalyzer();
IndexWriterConfig config = new IndexWriterConfig(analyzer);
var writer = new IndexWriter(directory, config);

File[] files = new File("./data/doc").listFiles();
for (File file : files) {
    if(!file.isDirectory() && file.exists() && file.canRead()){
        Document document = new Document();
        TextField contentField = new TextField("body", new FileReader(file));
        document.add(contentField);
        writer.addDocument(document);
    }
}
writer.numRamDocs();

writer.close();

指定したディレクトリ（上の例は ./data/index）に新しいファイルが作られます。そのファイルがLuceneにおけるインデックスの実態となっています。

インデックスに対して検索する

次に、簡単なクエリを用いて、作成したインデックスに対して検索を行ってみます。ディレクトリに配置されているインデックスを読み込むためのクラス DirectoryReader を用いて、読み込みを行い、 IndexSearcher クラスにクエリを渡すことで検索を実行できます。

Term term = new Term("body", "You");
TermQuery q = new TermQuery(term);

Directory indexDirectory = FSDirectory.open(Paths.get("./data/index"));
DirectoryReader reader = DirectoryReader.open(indexDirectory);
IndexSearcher searcher = new IndexSearcher(reader);

TopDocs docs = searcher.search(q, 10);
for (ScoreDoc scoreDoc: docs.scoreDocs) {
    System.out.println(scoreDoc);
}

上の例では、 body というフィールドに You というトークンがインデックスに含まれるかを検索しています。Luceneをライブラリとして使うにはこれでほぼ十分なのですが、さらにその内部へ深掘りをしてみます。

単語の存在を判定する

まずは、インデックスの特定のフィールドに特定のトークンの存在を判定してみましょう。 以下がデモコードになります。

public class Demo {
    public static void main(String[] args) throws IOException {
        var d = new Demo();
        d.scanTerm("people");
        d.scanTerm("unknown");
    }

    public void scanTerm(String text) throws IOException {
        System.out.println("-------");
        System.out.println(text);

        Term term = new Term("body", text);

        Directory indexDirectory = FSDirectory.open(Paths.get("./data/index"));
        DirectoryReader reader = DirectoryReader.open(indexDirectory);

        for (LeafReaderContext leaf: reader.leaves()) {
            LeafReader leafReader = leaf.reader(); // SegmentReader
            TermsEnum termsEnum = leafReader.terms(term.field()).iterator();

            if(termsEnum.seekExact(term.bytes())) {
                System.out.println("found");
                System.out.println(termsEnum.termState());  // BlockTermState
            } else {
                System.out.println("not found");
            }
        }
    }
}

標準出力結果

-------
people
found
docFreq=1 totalTermFreq=5 termBlockOrd=8 blockFP=0 docStartFP=62 posStartFP=1474 payStartFP=0 lastPosBlockOffset=-1 singletonDocID=0
-------
unknown
not found

インデックスはセグメントと呼ばれる単位に分割されていて、 reader.leaves() でセグメントの一覧を取り出すことができます。セグメント一個に対して、terms(<フィールド名>).iterator() で特定のフィールドのトークン列のイテレーターを取得できます。

seekExact メソッドを使うことで、特定のキーワードがそのインデックスのフィールドに存在するかを判定することができます。

単語の出現箇所をリストアップする

次に、ドキュメント内の単語の位置をリストアップしてみます。以下がデモコードになります。

public class Demo {
    public static void main(String[] args) throws IOException {
        var demo = new Demo();
        demo.postings("world");
    }

    IndexReader reader;
    IndexSearcher searcher;

    Demo() throws IOException {
        reader = DirectoryReader.open(FSDirectory.open(Paths.get("./data/index")));
        searcher = new IndexSearcher(reader);
    }

    void postings(String text) throws IOException {
        var t = new Term("body", text);
        for (LeafReaderContext leaf: reader.leaves()) {
            var it = leaf.reader().terms("body").iterator();

            System.out.println(t.text());
            System.out.println(it.seekExact(t.bytes()));
            var p = it.postings(null, PostingsEnum.ALL);
            p.nextDoc();
            for (int i = 0; i < p.freq(); i++) {
                System.out.println("pos: " + p.nextPosition());
            }
        }
    }
}

標準出力結果

world
true
pos: 16
pos: 214
pos: 240
pos: 326
pos: 846
pos: 904
pos: 964
pos: 1386

先ほどと同様に、terms(<フィールド名>).iterator() で特定のフィールドのトークン列のイテレーターを取得し、postings メソッドで位置情報のイテレーターを取得できるようになります。

Queryクラスを読み解く

次にQueryクラスの実装を読み込んでみますが、上述のインデックスに対するAPIが内部で使われています。

f:id:snowhork:20201124080832p:plain
QueryからScore計算の流れ

Query はまず IndexSearcher を渡すことで Weight を生成します。この時点でインデックス全体の情報を渡します。さらにセグメントの情報を渡すことで、各セグメントにおける Scorer を生成することができます。検索におけるヒットの判定とのスコアリングは Scorer が用いられます。

Query 自体は抽象クラスであり、具体的なクラスについて見てみます。

TermQuery

TermQuery は特定のフィールドに特定のキーワードが含まれるかを判定する、最も基本的なクエリになります。

1 . createWeight 内で TermStates.build を呼ぶ。 https://github.com/apache/lucene-solr/blob/releases/lucene-solr/8.6.3/lucene/core/src/java/org/apache/lucene/search/TermQuery.java#L194-L206

2 . TermStates.build 内で loadTermsEnum を呼ぶ。 https://github.com/apache/lucene-solr/blob/releases/lucene-solr/8.6.3/lucene/core/src/java/org/apache/lucene/index/TermStates.java#L102-L118

3 . loadTermsEnum 内で termsEnum.seekExact でキーワードの存在を判定 https://github.com/apache/lucene-solr/blob/releases/lucene-solr/8.6.3/lucene/core/src/java/org/apache/lucene/index/TermStates.java#L120-L129

  private static TermsEnum loadTermsEnum(LeafReaderContext ctx, Term term) throws IOException {
    final Terms terms = ctx.reader().terms(term.field());
    if (terms != null) {
      final TermsEnum termsEnum = terms.iterator();
      if (termsEnum.seekExact(term.bytes())) {
        return termsEnum;
      }
    }
    return null;
  }

上述したように、seekExact メソッドを用いてキーワードの存在の判定をしています。

PhraseQuery

PhraseQuery は「the world war」のように複数のキーワードを指定した時に、「the」「world」「war」のそれぞれのキーワードがその順番で現れた場合にヒットするクエリです。

マッチ判定は、PhraseMatcher クラスの nextMatch メソッドで行われていることが、ソースコードを追うとわかります。 https://github.com/apache/lucene-solr/blob/releases/lucene-solr/8.6.3/lucene/core/src/java/org/apache/lucene/search/ExactPhraseMatcher.java#L117

f:id:snowhork:20201124081746p:plain
PhraseQueryのマッチ判定

上の図に、 postings メソッドによって各キーワードの出現位置をリストアップし、それぞれのキーワードが順番に現れるかを調べることで、フレーズ検索を実施しています。

まとめ

今回の記事では、チームで毎週行っているElasticsearch勉強会の資料を改めてまとめました。実はキーワードの存在判定や、出現箇所のリストを返す関数は Codec と呼ばれるクラスに実装されていて、そのクラスで効率的な検索が実現されています。次はその内部実装を深掘りするのも面白いかもしれません。

We are hiring!

エムスリーではElasticsearch、AWS、GCP、Goなど幅広い技術スタックを扱っており、各分野に精通しているエンジニアがたくさんいます。 私も入社当初は Elasticsearch についてはほとんど何も知りませんでしたが、この半年で一気にキャッチアップすることができました。新しい技術にどんどん吸収したい方、特に新卒のエンジニア志望の方、ぜひご応募ください！

jobs.m3.com