ゼロからのElasticsearch、パート1

はじめに

本シリーズを書こうと思った動機には、ElasticsearchやLucene（ある程度は検索エンジン全般）の内部的な仕組みについて理解を深めていただきたいという思いがあります。ハンドルを握ってペダルを踏めば誰でも車を運転できますが、通常、優れたドライバーならばいくらかは車両の構造を理解しているものです。検索エンジンにも同じことが言えます。Elasticsearchには非常に使いやすいAPIが用意されているため、それほど苦労せずに始められ、かなり高度なことまでできるようになります。ただし、Elasticsearchを最大限に活用するためには、基盤となっているアルゴリズムやデータ構造に関する知識を持つことが有効です。そのような知識があれば、充実した機能を最大限に活用し、ユーザーの検索エクスペリエンスを向上させると同時に、システムのパフォーマンスと信頼性を維持し、（ほぼ）リアルタイムでシステムを更新できるようになります。

まずは、基本的なインデックス構造である転置インデックスから始めましょう。これは非常に汎用性の高いデータ構造です。同時に、使いやすくてわかりやすいのも特徴です。とは言え、Luceneの実装は高度に最適化された、見事な技術的偉業です。ここではLuceneの実装の詳細には立ち入らず、転置インデックスがどのように構築され、使用されるかに焦点を当てます。この点が、検索やインデックス作成の方法に影響するからです。

さて、抽象レベルの"基礎"としての転置インデックスを紹介したところで、ここからは以下の各項目を検討していきます。

• 検索をシンプルに実行する方法。
• どのようなタイプの検索なら効果的に実行できるのか（できないのか）、また、転置インデックスを使用する場合に各種の問題を文字列の接頭辞の問題に転換するのはなぜか。
• テキスト処理が重要となる理由。
• インデックスが"セグメント"で構築される仕組みと、それが検索や更新に与える影響。
• Luceneインデックスの構成要素。
• Elasticsearchのシャードとインデックス。

ここまできたら、検索時やインデックス作成時に1つのElasticsearchノード内部で起こっていることがよくわかるようになります。本シリーズ2回目の記事では、Elasticsearchの分散の側面を取り上げます。

転置インデックスとインデックス語

ここに今、3つのドキュメントがあるとします。"Winter is coming."、"Ours is the fury."、"The choice is yours."の3つです。簡単なテキスト処理（小文字化、句読点の削除、単語への分割）を行うと、図に示したような"転置インデックス"を作成できます。

この転置インデックスでは、各インデックス語が、自身が含まれているドキュメントに（場合によっては、ドキュメント内の位置にも）マッピングされています。辞書内の語はソートされているため、特定の語をすばやく見つけることができます。そして、ポスティング構造内では、その語がどのドキュメントで出現しているかを確認できます。これは、特定のドキュメントに関連する語をリストする"前方インデックス"とは逆になります。

複数の語を使った単純な検索では、すべての語とその出現の有無を調べ、出現した語の集合の積集合（AND検索の場合）または和集合（OR検索の場合）を取得して、結果のドキュメントリストを得ます。より複雑なタイプのクエリは当然それだけ複雑になりますが、アプローチは同じです。まず、辞書を操作して候補となる語を見つけ、次にその出現の有無や位置などを見つけます。

このように、インデックス語は検索の単位となっています。生成した語によって、どのようなタイプの検索を効率的に行うことができるか（あるいはできないか）が決まります。たとえば、上の図のような辞書を使えば、"c"で始まるすべての語を効率よく見つけることができます。これに対して、"ours"を含むものすべてを効率よく検索することはできません。そのためには、すべての語を調べる必要があります。すると、"yours"に部分文字列としてoursが含まれていることがわかります。これでは、インデックスがかなり小さいものでない限り、負荷が法外に大きくなってしまいます。接頭辞で語を見つける場合の複雑さが\(\mathcal{O}\left(\mathrm{log}\left(n\right)\right)\)なのに対し、任意の部分文字列で語を見つける場合の複雑さは\(\mathcal{O}\left(n\right)\)になるからです。

裏を返せば、語の接頭辞が与えられていれば、効率の良い検索が可能であるということになります。今回のように転置インデックスだけがある場合には、すべてを文字列の接頭辞の問題に転換するのが効果的です。以下では、その例をいくつか紹介します。シンプルなものもありますが、最後の例はほとんど魔法です。

• "tastic"で終わるものをすべて見つけるには、文字の順序を逆にしたインデックス（例："fantastic"→"citsatnaf"）を作成し、"citsat"で始まるものをすべて検索します。
• 部分文字列を見つけるには、多くの場合、語を"nグラム"と呼ばれる短い文字列に分割する必要があります。たとえば、"yours"は"^yo"、"you"、"our"、"urs"、"rs$"に分割できます。つまり、"our"と"urs"を検索することで"ours"を取得できることになります。
• ノルウェー語やドイツ語などの複合語を使う言語では、たとえば"Donaudampfschiff"のような単語を見つけるために"schiff"を検索する場合は、これを{"donau", "dampf", "schiff"}といった形に"分解"する必要があります。
• (60.6384, 6.5017)のような地理的座標点は"ジオハッシュ"に変換でき、この場合は"u4u8gyykk"となります。文字列が長いほど精度が高くなります。
• 人名などに非常に便利な音声照合を有効化するには、"Smith"を{"SM0", "XMT"}に、"Schmidt"を{"XMT", "SMT"}に変換するMetaphoneのようなアルゴリズムがあります。
• Luceneは、数値データ（およびタイムスタンプ）を処理する場合に、精度の異なる複数の語をトライ木のような形で自動的に生成するため、範囲検索を効率的に行うことができます¹。単純化すると、123という数値は、"1"個の100、"12"個の10、および"123"として格納できます。したがって、範囲[100, 199]のすべてを検索することは、100が"1"個の語すべてに一致することになります。これはもちろん、"1"で始まるものをすべて検索することとは違います。それだと、"1234"なども含まれてしまうからです。
• "これのことですか？"型の検索を実行して、入力に近いスペルを見つける場合には、"レーベンシュタイン"オートマトンを構築すると、効率的に辞書を走査できます。これは極めて複雑なもので、Luceneでの活用に至るまでの興味深い経緯についてはこちらを参照してください。

テキスト処理に関する詳細な説明は今後の記事に譲るとして、ここで強調したかったのは、インデックス語の生成に細心の注意を払わなければならない理由です。それは、検索を効率的に実行できるようにするためにほかなりません。

インデックスの構築

転置インデックスを構築する際は、検索速度、インデックスのコンパクトさ、インデックスの作成速度、新しい変更が可視化されるまでの時間など、優先順位を付ける必要がある項目がいくつかあります。

検索速度とインデックスのコンパクトさは関連しています。検索に使用するインデックスが小さいほど、処理が必要なデータ量が減り、メモリーに収まるデータ量が増えます。この2つ、特にコンパクトさを重視すると、後述するように、インデックスの作成速度が犠牲になります。

インデックスのサイズを最小化するための圧縮技術には、さまざまなものがあります。たとえば、Luceneでは、ポスティング（かなり大きくなる可能性があります）を格納する際に、差分エンコーディング（例：[42, 100, 666]を[42, 58, 566]として保存）や可変バイト数（小さな数字を1バイトで保存）といった手法を使っています。

しかし、データ構造を小さくコンパクトに維持すると、データを効率的に更新できなくなる可能性があります。実際、Luceneではデータをまったく更新しません。Luceneが書き込むインデックスファイルは変更不可能で、更新されることは絶対にありません。この点は、たとえば、更新可能で、想定される更新の頻度を示す曲線因子を指定できたりするBツリーなどとはまったく異なります。

ただし、削除は例外です。インデックスからドキュメントを削除すると、そのドキュメントは特別な削除ファイルで削除済みとマークされますが、削除ファイルは実際は、更新負荷の小さいビットマップファイルに過ぎません。インデックス構造そのものは更新されません。

そのため、以前にインデックス作成したドキュメントを更新することは、いったんドキュメントを削除してから再挿入することを意味します。そもそもドキュメントの更新は追加よりもはるかに負荷がかかるのです。したがって、次々と変化するカウンターのようなものをLuceneインデックスに格納することは、通常、推奨されません。値のインプレース更新機能がないからです。

（たいていは）更新によって新しいドキュメントが追加されると、インデックスの変更はまずメモリーのバッファに格納されます。最終的に、インデックスファイル全体がディスクにフラッシュされます。これはLuceneでの"フラッシュ"の意味であることに注意してください。Elasticsearchのフラッシュ操作はLuceneのコミットなどを伴います。これについてはトランザクションログのセクションで説明します。

フラッシュのタイミングは、変更を確認できるまでの時間、バッファリングに利用できるメモリー容量、I/Oの飽和状態など、さまざまな要因で変わります。一般に、インデックスの作成速度を上げるには、バッファは大きければ大きいほどよいのですが、ただし、I/O処理が追いつける大きさまでという制限が付きます²。次のセクションでもう少し詳しく説明します。

書き込まれたファイルによってインデックスセグメントが構成されます。

インデックスセグメント

Luceneのインデックスは1つ以上の変更不能なインデックスセグメント（基本的には"ミニインデックス"）で構成されています。検索を実行する際、Luceneはすべてのセグメントに対して検索を行い、削除をフィルターアウトし、すべてのセグメントからの結果をマージします。セグメントの数が増えれば増えるほど、この操作が高負荷になることは言うまでもありません。セグメントの数を管理しやすいレベルに維持するために、新しいセグメントが追加されると、Luceneは何らかのマージポリシーに従ってセグメントをマージすることがあります。LuceneハッカーのMichael McCandless氏は、セグメントのマージについて解説し、これを視覚化した優れたブログを投稿しています。³ セグメントをマージすると、削除済みとマークされているドキュメントは最終的に破棄されます。ドキュメントを追加するとインデックスサイズが小さくなる理由はこれです。つまり、ドキュメントの追加により、マージがトリガーされるからです。

ElasticsearchとLuceneは、セグメントをマージするタイミングを全般的に適切に処理します。Elasticsearchのポリシーは、マージ設定を構成することで微調整できます。また、APIを使用して、マージを強制することも可能です。

セグメントがディスクにフラッシュされる前に、変更はメモリーのバッファに格納されます。以前（Lucene 2.3より前）は、追加されたドキュメントは、実際にはそれ自身の小さなセグメントとして存在し⁴、すべてがフラッシュ時にマージされていました。現在ではDocumentsWriterがあります。これを使用すると、ドキュメントのバッチからより大きなメモリー内セグメントを作ることができます。Lucene 4では、スレッドごとにセグメントを1つずつ配置できるため同時フラッシュが可能になり、インデックス作成のパフォーマンスが向上しています（以前は、インデックス作成では1つのフラッシュが完了するまで待機しておく必要がありました）。

フラッシュまたはマージによって新しいセグメントが作成されると、特定のキャッシュが無効にもなるため、検索のパフォーマンスが悪影響を受ける可能性があります。フィールドキャッシュやフィルターキャッシュのようなキャッシュはセグメントごとにあります。ElasticsearchにはウォーマーAPI⁵が用意されており、新しいセグメントを検索可能にする前に、必要なキャッシュを"ウォームアップ"しておくことができます。

Elasticsearchでフラッシュが発生する最も一般的な原因は、連続的なインデックス更新です。これはデフォルトでは毎秒1回行われます。新しいセグメントがフラッシュされると、セグメントの検索が可能になりますが、これは（ほぼ）リアルタイム検索と言えます。フラッシュは（確定した書き込みを待機する必要がないため）コミットほど高負荷ではありませんが、新しいセグメントが作成されるので、一部のキャッシュが無効になり、場合によってはマージが誘発されることがあります。

バッチ（再）インデックス作成など、インデックス作成のスループットが重要な場合、小さなセグメントのフラッシュとマージに多くの時間を費やすことはあまり生産的ではありません。したがって、このような場合は通常、一時的にrefresh_interval設定の値を増やすか、いっそのこと自動更新を完全に無効にするのが得策です。任意のタイミングで手動で更新することも、インデックス作成時に更新することも、どとらも可能です。

Elasticsearchインデックス

「コンピュータサイエンスにおけるすべての問題は、もう一段階の遠回りによって解決できる」 - David J. Wheeler

Elasticsearchインデックスは1つ以上のシャードで構成され、シャードには0個以上のレプリカを含めることができます。これらはすべて個別のLuceneインデックスです。つまり、Elasticsearchインデックスは多数のLuceneインデックスで構成されており、Luceneインデックスはインデックスセグメントで構成されています。Elasticsearchインデックスを検索すると、すべてのシャード、ひいてはすべてのセグメントに対して検索が実行され、マージされます。複数のElasticsearchインデックスを検索する場合も同じです。実は、1つのシャードを含む2つのElasticsearchインデックスをそれぞれ検索することは、2つのシャードを含む1つのインデックスを検索することとほぼ変わりません。どちらの場合も、基盤となっている2つのLuceneインデックスが検索されるのです。

本記事のこれ以降の部分では、単に"インデックス"と言った場合は、Elasticsearchインデックスのことを指します。

"シャード"は、Elasticsearchの基本的なスケーリング単位です。インデックスに追加されたドキュメントは、シャードにルーティングされます。デフォルトでは、これはドキュメントのIDのハッシュに基づいてラウンドロビン方式で行われます。本シリーズのパート2では、シャードがどのように移動するのか、さらに詳しく見ていきますが、シャードの数はインデックス作成時に指定するため、後から変更することはできないことを認識しておく必要があります。ShayはElasticsearchに関する初期のプレゼンテーションで、シャードが実際には完全なLuceneインデックスである理由や、他の方法と比較した場合のさまざまな利点やトレードオフについてわかりやすく説明しています。

検索リクエストの送信先となるElasticsearchインデックスやシャード（およびレプリカ）は、さまざまな方法でカスタマイズできます。インデックスパターン、インデックスエイリアス、ドキュメント/検索ルーティングを組み合わせることで、さまざまなパーティショニングとデータフローの戦略を実装できます。ここでは深入りしませんので、ドキュメントルーティングのカスタマイズに関するZachary Tongの記事や、ビッグデータ、検索、分析に関するShay Banonのプレゼンテーションを参照されることをお勧めします。参考までに、いくつか例を以下に紹介します：

• データの多くが、時間ベースである（例：ログ、ツイート）。日（週、月、...）ごとにインデックスを作成することで、特定の時間範囲に検索を絞り込み、古いデータを消去できます。既存のインデックスからは効率的にデータを削除できませんが、インデックス全体を削除することは容易であることに注意してください。
• 検索を特定のユーザーに絞り込む必要がある場合（例："メッセージの検索"）は、そのユーザーのすべてのドキュメントを同一のシャードにルーティングし、検索が必要なインデックスの数を減らすとうまくいったりします。

トランザクション

Luceneにはトランザクションの概念がありますが、Elasticsearchにはありません。Elasticsearchでのすべての操作は同じタイムラインに追加されますが、フラッシュはタイミングに依存するため、ノード間で完全に一貫しているわけではありません。

分散システムのノード間でインデックスをまたいで異なるセグメントやキャッシュなどの分離と可視性を管理するのは、非常に困難です。Elasticsearchではそういうことを目指さず、速度を優先しています。

Elasticsearchには"トランザクションログ"があり、インデックスを作成したドキュメントが追記されます。ログファイルへの追記はセグメントを構築するよりもはるかに負荷が小さいため、Elasticsearchでは、クラッシュすると失われるメモリー内のバッファに加え、永続的な場所にあるインデックスにドキュメントを書き込むことができます。また、インデックス作成時に、必要な一貫性レベルを指定することもできます。たとえば、インデックス作成操作の結果が返されるタイミングが、すべてのレプリカがドキュメントのインデックスを作成した後になるように要求することができます。

まとめ

要約すると、Luceneが単一ノードでインデックスの構築、更新、検索を行う仕組みについては、以下のような特性を理解しておく必要があります。

• インデックス作成対象のテキストの処理方法によって、検索方法が変わってくる。適切なテキスト分析が重要である。
• インデックスは最初メモリー内に作成され、時折セグメントとしてディスクにフラッシュされる。
• インデックスセグメントは変更不可能である。削除されたドキュメントは削除済みとマークされる。
• インデックスは複数のセグメントから構成される。検索はすべてのセグメントに対して実行され、結果がマージされる。
• セグメントは時折マージされる。
• フィールドおよびフィルターキャッシュはセグメントごとに行われる。
• Elasticsearchにはトランザクションがない。

本シリーズの次の記事では、クラスター全体で検索とインデックス作成がどのように行われるかを確認します。