コラム

CTC教育サービス・ホーム　＞　コラム　＞　グーグルのクラウドを支えるテクノロジー　＞　第7回　スケーラビリティと一貫性を両立した分散データストアMegastore（パート１）

グーグルのクラウドを支えるテクノロジー

CTC 教育サービス

[IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes

第7回　スケーラビリティと一貫性を両立した分散データストアMegastore（パート１） (中井悦司) 2016年12月

はじめに

　今回からは、2011年に公開された論文「Megastore: Providing Scalable, Highly Available Storage for Interactive Services」をもとにして、分散データストア「Megastore」を紹介していきます。Google Cloud Platform（GCP）では、Cloud Datastoreというデータストアを利用することができますが、Cloud Datastoreは、内部的にMegastoreを用いて実装されています。Megastoreに機能を追加して、より簡単に使えるようにしたものがCloud Datastoreだと考えて構わないでしょう。
　Megastore、あるいは、Cloud Datastoreは、スケールアウト型の構造を持っており、1台のサーバーでは対応できないような大量のデータを取り扱うことができます。また、Megastoreの内部構造を知ることにより、Cloud Datastoreの特徴であるエンティティグループやAncestorクエリー、あるいは、インデックスの使い方をスッキリと理解することが可能になります。今回は、Megastoreの仕組みを理解する準備として、まずは、Cloud Datastoreの概要とこれらの特徴を整理しておきます。

Cloud Datastoreの概要

　Cloud Datastoreは、一般に、分散キーバリューストア、あるいは、NoSQLなどに分類されるデータストアです。「Kind」とよばれる複数のテーブルに「エンティティ」とよばれるデータを保存していきます。Kindは、スプレッドシートにおける1枚のシートに相当するもので、各行が個別のエンティティに対応すると考えるとよいでしょう。そして、シートの列に相当するのが「プロパティ」です。各エンティティには、自身を特定する識別子（「ID」＋「Parent」）があり、それぞれのKindに固有のプロパティに対して実際のデータを保存していきます。
　図1は、ユーザーが所有する書籍の情報を登録する「本棚アプリ」のデータを想定した例です。ユーザーのプロファイル情報を保存するKind「User」と、それぞれの書籍の情報を保存するKind「Book」があります。

図1 「本棚アプリ」で使用するKindの例

　この時、それぞれの書籍に対して、それを保有するユーザーをひも付ける必要がありますが、これは、エンティティグループの機能によって行います。エンティティグループは、複数のKindにまたがるエンティティをツリー状のグループにまとめる機能です。ツリーの頂点にあたる「ルートエンティティ」があり、その下に「子ども」のエンティティがぶら下がっていきます。先ほどの例では、ユーザーが所属する組織を表わすエンティティ（Kind「Organization」、ID「Flywheel」）がルートエンティティになっており、その下にユーザーを表わすエンティティ、さらにその下にそのユーザーが保有する書籍を表わすエンティティがひも付いています（図2）。

図2 エンティティグループのツリー構造

　あるエンティティについて、ルートエンティティからそれ自身までの経路は、次のように、経路上のエンティティについて、KindとIDの組を並べて示すことができます。これをこのエンティティの「Ancestorパス」と呼びます。

('Organization', 'Flywheel') → ('User', 'Alice') → ('Book', 'GCP入門')

　先ほど、「各エンティティには、自身を特定する識別子（「ID」＋「Parent」）がある」と説明しましたが、「Parent」の部分には、直近の親のAncestorパスが格納されます。これにより、あるエンティティがどのエンティティグループに所属するかが識別されるようになります。「ID」＋「Parent」でユニークな識別子になりますので、Parentの値が異なっていれば（つまり、異なるエンティティグループに属するエンティティであれば）、あるKindの中に同じ「ID」のエンティティがあっても構いません。IDには、任意の文字列、もしくは、自動で割り当てられるランダムな整数値が使用できます。
　なお、実際にAncestorパスを表記する際は、矢印は省略して、KindとIDの組を順番にならべたタプルを使用します。先ほどの例であれば、実際には、次のように表記されることになります。

('Organization', 'Flywheel', 'User', 'Alice', 'Book', 'GCP入門')

　図1の「Parent」の部分には、この表記方法で親となるエンティティのAncestorパスが記載されています。

グローバルクエリーとAncestorクエリー

　Cloud Datastoreでデータの検索を行う時は、グローバルクエリーとAncestorクエリーの2種類の検索が利用できます。まず、グローバルクエリーは、あるKindに含まれるすべてのデータを検索対象とするものです。次は、Kind「Book」から、プロパティ「pages」（ページ数）が999より大きいものをすべて検索する例になります。

SELECT * FROM Book WHERE pages > 999

　このようなグローバルクエリーでは、一般に、イベンチュアル・コンシステンシーとよばれる動作が行われます。これは、直前に書き込まれたデータが必ずしも検索結果に含まれるとは限らないことを意味します。Cloud Datastoreの検索処理は、すべて、専用のインデックステーブルを参照して行われますが、その時点でインデックステーブルへの反映が完了していないデータは、検索対象から漏れてしまうためです。グローバルクエリーの場合、検索対象のエンティティの数が膨大になる可能性があるため、インデックスの反映が完了するのをまたずに検索処理を開始するようになっていると考えてください。
　もう一方のAncestorクエリーは、検索対象のエンティティグループを指定して行います。より正確に言うと、あるエンティティを「Ancestor」として指定すると、そのエンティティの配下にあるエンティティのみが検索対象になります。次の例では、「('Organization', 'Flywheel', 'User', 'Alice')」がAncestorに指定されているので、ユーザー「Alice」が所有する書籍のみが検索対象になります。

SELECT * FROM Book WHERE pages > 999 AND __key__ HAS \
  ANCESTOR Key('Organization', 'Flywheel', 'User', 'Alice')

　そして、このようなAncestorクエリーの場合は、ストロングコンシステンシーとよばれる動作が行われます。この場合、イベンチュアル・コンシステンシーと異なり、それまでに書き込まれたすべてのエンティティが必ず検索対象になることが保証されます。検索範囲が特定のエンティティグループに限られているため、該当のエンティティグループに含まれるすべてのエンティティについて、インデックスの反映が完了するのを待ってから検索処理が開始するものと考えるとよいでしょう。
　一般に、スケールアウト型の分散データストアは、ストロングコンシステンシーを持った処理を苦手としており、イベンチュアル・コンシステンシーのみを提供するソフトウェアも見られます。Cloud Datastoreは、大量のデータ保存に対応したスケールアウト型のデータストアでありながら、エンティティグループの仕組みを利用することにより、ストロングコンシステンシーを持った処理にも対応している点が大きな特徴となります。

Cloud Datastoreを使いこなす上での課題

　Cloud Datastoreを使用する際に、とくに忘れてはならないのが、インデックスの作成処理です。前述のように、Cloud Datastoreの検索は、すべてインデックステーブルを参照して行われます。このため、検索に必要なインデックスを事前に作成しておかないと、検索に失敗してエラーが発生します。この際に問題になるのが、どのような検索に対して、どのようなインデックスが必要なのかがわかりにくいということです。
　あるいは、Cloud Datastoreでは、利用可能な検索の種類にも不思議な制限があります。たとえば、次のように、複数の不等号条件を持った検索処理は実施することができません。

SELECT * FROM Book WHERE pages > 999 AND price < 3000

　このように、検索に必要なインデックスを理解する、あるいは、利用可能な検索の種類を正しく知っておくということが、Cloud Datastoreを使いこなす上でのポイントであり、課題でもあるということになります。

次回予告

　今回は、Megastoreの内部構造を理解する準備として、Megastoreをベースとした分散データストアであるCloud Datastoreの概要を説明しました。とくにCloud Datastoreを使いこなす上での課題についても触れました。実は、Cloud Datastoreの背後にあるMegastoreは、エンティティやインデックスの情報をバックエンドのBigtableに格納しています。この際、どのような構造でデータが格納されているのかを知ると、どのようなインデックスが必要になるのか、あるいは、なぜ複数の不等号条件での検索ができないのか、という点を明確に理解することが可能になります。
　次回は、MegastoreのアーキテクチャーとBigtableに対するデータの格納方法の詳細について、解説を進めていきます。

Disclaimer：この記事は個人的なものです｡ここで述べられていることは私の個人的な意見に基づくものであり、私の雇用者には関係はありません｡