ElasticsearchのMore like this内部実装とパフォーマンス問題の解決

エムスリーエンジニアリンググループ AI・機械学習チームでソフトウェアエンジニアをしている中村(po3rin) です。検索とGoが好きです。

今回はLuceneのMore like this(MLT)機能のコードリーディングでMLTの実装を理解して、エムスリーで問題になっていたMLTパフォーマンス問題を解決したお話をします。

What's MLT

MLTを簡単に説明すると、入力ドキュメントを形態素解析し、て入力ドキュメントを形態素解析して、TF-IDFスコアが高いタームを使って、文書検索をかけるElasticsearch、Luceneの機能です。

MLTの説明

LuceneにはMore like this(MLT)という機能があり、似た文書を探すなどに利用できます。

MoreLikeThis (Lucene 9.1.0 queries API)

ElasticsearchからもLuceneのMLT機能にアクセスでき、More like this APIとして利用できます。

More like this query | Elasticsearch Guide [8.1] | Elastic

エムスリーでは検索基盤にElasticsearchを利用しており、類似文書検索のファーストステップとして開発コストが小さいという観点からよくMLTを採用します。

簡単にLuceneのMLT機能の使い方を紹介します。Luceneのドキュメントに簡単な使い方が書いてあるので抜粋します。

IndexReader ir = ...
IndexSearcher is = ...

MoreLikeThis mlt = new MoreLikeThis(ir);
Reader target = ... // orig source of doc you want to find similarities to
Query query = mlt.like(target);

Hits hits = is.search(query);
// now the usual iteration thru 'hits' - the only thing to watch for is to make sure
//you ignore the doc if it matches your 'target' document, as it should be similar to itself

MoreLikeThisクラスは主に検索クエリを生成するためだけの責務を持ちます。実際の検索はMLTから分離された検索インターフェースであるIndexSearcherを利用します。IndexReaderã‚’MoreLikeThisクラスに渡していますが、これはタームのTFã‚„IDFã‚’indexから取得するために利用しています。

IndexSearcherã‚„IndexReaderは簡単に説明するとそれぞれ検索用、Indexing用のクラスです。詳しくは僕が過去に書いた記事をご覧ください。

po3rin.com

MLTの利用ケースとパーフォーマンス問題

弊社のとあるプロダクトではコンテンツベース推薦のメルマガをMLTで生成しています。効果としては簡単な協調フィルタリング系のアルゴリズムよりも効果が高かったです。

メルマガ生成アーキテクチャ

しかし、MLTの実行速度の問題で、メルマガの配信時間までに、メルマガ対象ユーザ数分のMLT処理が終わらないという問題が発生していました。そこでMLTのコードリーディングを通して、速度改善のポイントを把握して、実際に速度改善を行いました。

今回はコードリーディングで学んだMLTのパフォーマンス改善のポイントとして以下の3点を紹介します。

• ドキュメント指定かID指定か
• Fieldの数とテキスト長
• max_query_terms

高速化のポイント1: ドキュメント指定かID指定か

ElasticsearchのMLTは2パターンの使用法があります。すでにIndexingされているドキュメントのIDを指定するか、ドキュメントを文字列として直接渡すかです。実際にLuceneでも2つのlikeメソッドが存在します。

public Query like(String fieldName, Reader... readers) throws IOException {
  // ...
}

public Query like(int docNum) throws IOException {
  // ...
}

ID指定の方は下記のようなコードになります。addTermFrequencies内部では指定されたAnalyzerでドキュメントを形態素解析を行い、タームとTF-IDFスコアを取得します。そしてcreateQueueでTF-IDFスコアの大きいものから順に検索に使うターム最大数まで格納していきます。最後にキューに入ったタームをcreateQueryでShouldクエリで繋いで、検索用クエリを生成します。

public Query like(String fieldName, Reader... readers) throws IOException {
    Map<String, Map<String, Int>> perFieldTermFrequencies = new HashMap<>();
    for (Reader r : readers) {
      addTermFrequencies(r, perFieldTermFrequencies, fieldName);
    }
    return createQuery(createQueue(perFieldTermFrequencies));
  }

一方で下記のドキュメント指定の方のlikeメソッドで注目すべきはirというメンバ変数で、これはIndexReaderクラスです。つまり、すでにIndexingしているターム情報をIndexReaderから取得してMLTを行います。なのでID指定の方法は形態素解析をスキップできます。更にTF-IDFのスコアもすでにIndexingするので、スコア計算も不要です。

public Query like(int docNum) throws IOException {
  if (fieldNames == null) {
    Collection<String> fields = FieldInfos.getIndexedFields(ir);
    fieldNames = fields.toArray(new String[fields.size()]);
  }

  return createQuery(retrieveTerms(docNum));
}

まとめると、ドキュメント指定だと形態素解析が走るので、ID指定の方が断然早いということになります。

弊社では以前はドキュメント指定方式をとっていました。なぜならElasticsearchとマスターのDBの同期処理はBatchで行っていたので、ID指定だとまだIndexingされていない最新のドキュメントの閲覧ログが使えないためです。しかし、ユーザー分のメルマガが生成できないというデメリットが大きいため、最新のドキュメントの閲覧ログが使えないという点に目を瞑り、ID指定のMLTに切り替えました。

もっとコードを追ってみたい方はリポジトリのlucene/queries/src/java/org/apache/lucene/queries/mlt/MoreLikeThis.javaを読んでみてください。

高速化のポイント2: Fieldの数とテキスト長

タイトルやボディなどのFieldごとに検索をかけるので、当然、MLTに使うフィールドが少ない方が速度が速くなります。実際にID指定のlikeで呼ばれているretrieveTermsの中身を見ると、フィールドごとのターム情報を格納しているのがわかります。

private PriorityQueue<ScoreTerm> retrieveTerms(int docNum) throws IOException {
  Map<String, Map<String, Int>> field2termFreqMap = new HashMap<>();
  for (String fieldName : fieldNames) {
    // field2termFreqapにフィールドごとのターム情報を格納していく
  }

  return createQueue(field2termFreqMap);
}

最終的にこの中からTF-IDFが高い順に選んでShouldで繋げるのですが、フィールドのテキスト長が長ければ長いほど、ループに時間がかかることがわかると思います。

弊社では以前、長すぎるテキストフィールドをMLTのフィールドに指定していたので、このフィールドをMLTの対象から外すことで高速化をしました。

高速化のポイント3: max_query_termsの設定

Luceneにはmax_query_termsというMLTの設定があります。これはShouldで繋げるタームの最大値です。検索パフォーマンスのために少し数を抑える必要があります。

実際にこの設定が効くのはキュー生成ステージです。キューの長さをmax_query_termsの値で生成しているのが分かります。

private PriorityQueue<ScoreTerm> createQueue(
  Map<String, Map<String, Int>> perFieldTermFrequencies) throws IOException {
    // have collected all words in doc and their freqs
    final int limit = Math.min(maxQueryTerms, this.getTermsCount(perFieldTermFrequencies));
    FreqQ queue = new FreqQ(limit); // will order words by score
    for (Map.Entry<String, Map<String, Int>> entry : perFieldTermFrequencies.entrySet()) {
      
    }
    return queue;
  }

キューに入ったタームをShouldで繋いでクエリを生成するので、この数が少ないほどクエリが軽くなります。 弊社ではmax_query_termsはデフォルトの25を使っていましたが、max_query_terms=15でも問題ない精度が出ることを確認できた為、ここの数値を変更したところ速度が大幅に改善しました。

結果

コードリーディングを通して分かった速度改善のためのポイントをまとめると下記になります。

• ドキュメント指定だと形態素解析が走るので、ID指定の方が断然早い。
• Fieldごとに形態素解析、検索を行うので、フィールドの数は少ない方が当然良い。
• max_query_termsの数だけタームががshouldでつながるので、検索パフォーマンスのために少し数を抑える必要がある。

この結果、MLTによるメルマガ生成の所要時間が1/2になり、更にCPU使用率の削減にも成功しました。

まとめ

今回はMore like thisの内部実装を覗きました。やはりコードを読むと機能の理解が進みやすいです。 初期の実装ではMLTは簡単に試せるのでおすすめですが、これから先、MLTでは精度、速度ともに限界が見えているので、別の推薦アルゴリズムに乗り換えることも検討しています。というか乗り換えたいので、推薦やりたい人来て欲しいです。笑

We're hiring !!!

エムスリーでは検索&推薦基盤の開発&改善を通して医療を前進させるエンジニアを募集しています！社内では日々検索や推薦についての議論が活発に行われています。各週で情報/推薦論文読み会も開催されています。

「ちょっと話を聞いてみたいかも」という人はこちらから！ jobs.m3.com