概要

App Engine の データストア クエリ はすべて インデックス によって処理されます。組み込みのインデックスは、単一プロパティに対する簡単なクエリ（指定された種類のすべてのエンティティを含む）、フィルタ、並び替え順序、また任意の数のプロパティに対する等価フィルタを処理できます。一方、より複雑なクエリについては、カスタムのインデックスの定義と設定が必要です。

開発者はこれらのインデックスのことを「複合インデックス」と呼び、組み込み種類のインデックスや単一プロパティのインデックスと区別します。複合と呼ばれるのは、1 つのインデックス行に対して複数の値がインデックス データを含む構成を持つからです。

新しい複合インデックスをアプリケーションに追加した場合、クエリを処理するには、そのインデックスにデータストアの既存のデータを追加する必要があります。同様に、アプリケーションからインデックスを削除したときは、アプリケーションのインデックス行も削除しなければなりません。App Engine は、インデックス作成ワークフローをバックグラウンドで実行することで、インデックスにデータを追加したり、そのインデックスを削除したりします。

この記事では、インデックスをレイアウトする方法、インデックス作成ワークフローの仕組みについて説明するほか、インデックス作成に関するよくある質問を紹介します。

インデックスのレイアウト

App Engine では、インデックス データが、アプリケーション全体で共有される 4 つの Bigtable に格納されます。最初の 3 つのテーブルには、組み込み種類のインデックス、昇順の単体プロパティのインデックス、降順の単体プロパティのインデックスが格納されます。そして最後のテーブルには、すべての複合インデックスが格納されます。

インデックス行内のインデックス データは Bigtable の行の名前で格納されています。データにはアプリケーションの ID、種類、キーのほか、インデックスによって異なる追加データなどが含まれます。組み込みの単一プロパティのインデックスの追加データにはプロパティの名前や値などがあります。組み込み種類のインデックスには追加データはありません。

複合インデックスの場合は、インデックス定義の各プロパティの値に加え、その親が追加データとなります（指定されている場合）。インデックス定義自体にプロパティ名が含まれているので、スペース節約のためプロパティ名は省略されています。ただし、複合インデックス行にはインデックス ID が含まれています。この ID によって、インデックス行を、同じプロパティ値が同じ順序で含まれる別の複合インデックスと区別します。

インデックスのレイアウトの詳細については、Under the Covers of the Google App Engine Datastore の Google I/O トークをご覧ください。

インデックスの作成と削除

新しいインデックスを定義し、インデックスを作成するようユーザーが指示すると、次の手順が実行されます:

1. インデックス定義のメタデータをアプリケーションに追加します。
2. インデックス メタデータに Building のマークを付けます。これにより、データストアは、すべての書き込みでインデックスを更新するように、ただし、クエリではまだそのインデックスを使用しないように指示されます。
3. 既存のエンティティをマッピングし、インデックスに追加します。
4. インデックスに Serving のマークを付けます。これにより、クエリでインデックスを使用できることがデータストアに通知されます。

インデックスの削除についても、ほとんど同じ手順で行われます:

1. インデックス メタデータに Deleting のマークを付けます。これにより、データストアは、書き込みとクエリの両方でインデックスを無視するよう指示されます。
2. インデックスの行を削除します。
3. インデックスのメタデータを削除します。

エンティティが作成または削除されたら、そのエンティティのすべてのインデックス行を更新する必要があります。ただし、既存のエンティティが更新されたときは、データストアは、その差分、つまり変更されたプロパティを確認し、そのプロパティが含まれるインデックス行のみを更新します。

さらに、データストアは、複合インデックスを自動的に処理します。エンティティが追加または削除されると、データストアは、上記で説明したように、更新が必要な複合インデックス行を確認して更新します。

データストアによるインデックス更新は効率的かつ自動的に処理されるため、インデックス作成ワークフローでは、データストアのコードを単純に再利用しています。インデックスを作成または削除するために、ワークフローはアプリケーションのすべてのエンティティを 1 つずつマッピングします。そして、エンティティごとに、トランザクションでデータストアを使用して読み取り、変更せずに書き戻します。データストアは、Building または Deleting のマークが付いたインデックスを検出し、関連するインデックス行を更新します。

並行処理

インデックス作成ワークフローでは、インデックスの作成や削除を段階的に、かつ同時並行で実行できる「ワーカー」を使用します。このため、異なるアプリケーションのインデックスを同時に作成または削除できます。また、1 つのアプリケーションのインデックスの作成または削除を並列処理することも可能です。そして作業にチェックポイントを設定しているため、ワーカーの 1 つが何らかの理由で機能しなくなっても、作業を再開できます。

ワークフローでは、作成または削除するインデックスを持つ、すべてのアプリケーションが登録されたリストが中央で管理されています。各アプリケーションのデータは区画（以下、シャード）に分割されています。アイドル状態のワーカーはこのリストを調べ、データのシャードを期限付きの「リース」契約のように預かります。そのシャードのエンティティをマッピングして、上記で説明したようにインデックス行に追加します。ワーカーが完了する前にシャードの返却期限が切れた場合、そのリースは停止し、部分的に完了した作業を破棄します。そして、シャードは、他のワーカーが再試行できるよう利用可能になります。

Google では、データをシャードに分割するメカニズムをいくつ用意しています: 1 つは Bigtable タブレットを使用した分割です。また、タブレット内で分割を行うメカニズムもあります。ここでは、この両方の方法について説明します。

タブレットによる分割

アプリケーションのエンティティをシャードに分割する処理は、意外にも簡単ではありません。理想的には、ワークフローが Bigtable に対して間隔を指定し、アプリケーションの最初のエンティティから最後までの行がこの間隔に従って渡されます。これが、各シャードを区切る「分割」ポイントになります。

ただし、Bigtable では、こうしたオフセット操作は意図的に行われていません。そこで、Google ではこれに近い処理を行うようにしました。Bigtable は、データを、タブレットと呼ばれる連続する行範囲に分割します。このタブレットは、実行時に分割、結合できます。また、タブレット サーバー間での移動も可能です。Bigtable では各タブレットの開始行と終了行を認識しているため、開発チームはタブレットごとにシャードを挿入することから開始しました。

残念ながら、タブレットは合計データ サイズによってのみ制限されます。したがって、行（つまりエンティティ）数はタブレット間でかなりばらつきがある可能性があります。インデックスにデータを追加するのに必要な時間は、エンティティのサイズよりもエンティティのプロパティ数の影響を受けます。このため、タブレット シャードが異なると、ワーカーで費やされる時間が大幅に違ってくることがあります。多数の行が含まれるタブレットでは、ワーカーが定められたリースを超過することはよくあり、これによりインデックスの作成や削除に時間がかかることは珍しくありません。

タブレット内での分割

これに対応するために、大きなシャードを分割できるようになりました。ワーカーは、シャード上のリースに対する有効期限が間近であることに気が付くと、作業を中断し、そのシャードを n 個の小さなシャードに分割します。この小さなシャードそれぞれに、元のシャードの行範囲と 2 つのシャード パラメータ、n（すべての部分で共通）と k（0～n-1 の範囲）が含まれています。

ワーカーは、シャード パラメータで分割されたシャードを処理するときに、シャードの行範囲にあるすべてのエンティティを、通常どおり、マッピングします。そして、エンティティが見つかるたびに、そのエンティティのキーをハッシュし、ハッシュと k modulo n が等しければ、そのエンティティのインデックスにデータを追加します。

また、k 番目のエンティティごとにデータを追加するという方法もあります。この方法は簡単ですが、エンティティを見落とす可能性があります。この処理中もアプリケーションが動作し、エンティティを挿入または削除しているからです。

シャードが分割されても、その行範囲は変わらないという点も強調しておきます。ワーカーは、引き続き行範囲全体をスキャンします。しかし、このスキャンは、インデックスの更新に必要な読み取りや書き込みに比べると比較的コストがかかりません。ディスクの帯域幅はディスク シークよりもかなり軽量なため、Bigtable スキャンは、個別の行に対するランダム アクセスによる読み取りや書き込みよりもコストをかけずに行うことができます。

よくある質問

インデックスを内部で作成または削除する方法についてよくある質問をいくつか次に示します。（使用しているアプリケーションのインデックスを指定する方法については、こちらのドキュメントをご覧ください。）

質問: 長い間インデックスの状態が Building または Deleting のままなのはなぜですか？
回答: 昔はこの現象がよく発生していました。ワーカー シャード が大きすぎて、リース期間内に完了できなかったからです。この問題に対処するには、まず、リース期間を増やします。次に、個々のタブレットをシャードに分割します。引き続きインデックス作成に時間がかかることもありますが、以前に比べるとかなり速くなっています。

質問: インデックスに Error とマークされるのはなぜですか？
回答: インデックスのデータが増えすぎた可能性があります。たまにですが、Google では、インデックスを手動で Error にする必要があります。通常、このような場合は直接ご連絡いたします。

質問: アプリケーションのデータストア全体がマッピングされるのはなぜですか？組み込み種類のインデックスを使用してインデックスの種類のエンティティのみをマッピングし、他の種類は省略できませんか？
回答: 個々のエンティティの読み取りと書き込みのトランザクション分離レベルは READ COMMITTED ですが、インデックスでは同じことが保証されていません。このため、種類インデックスでは、エンティティが見落とされてしまうことがあります。詳細については、App Engine におけるトランザクション分離 をご覧ください。

質問 : インデックスを削除するときに、そのインデックス行だけを直接削除できませんか？アプリケーション ID とインデックス ID で Bigtable プレフィックス スキャンを実行できるのに、エンティティ自体がマッピングされるのはなぜですか？
回答: 残念ながら、複雑な事情があります。エンティティには、そのエンティティに適用する複合インデックスに関するメタデータが含まれています。このため、インデックス行を削除する場合は、そのメタデータも更新する必要があります。