以下は、Jason Baker 他による、Megastore: Providing Scalable, Highly Available Storage for Interactive Services 、CIDR 2011 5 th Biennial Conference on Innovative Data Systems Research (CIDR ’11) で発表、 の kanda.motohiro@gmail.com による訳です。この翻訳は、Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0/) の元で配布されます。
This is a Japanese translation by kanda.motohiro@gmail.com of the portions of the paper "Megastore: Providing Scalable, Highly Available Storage for Interactive Services" by Jason Baker et al., presented at CIDR 2011 5 th Biennial Conference on Innovative Data Systems Research (CIDR ’11). This translation is distributed under Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0/)
Megastore: Providing Scalable, Highly Available Storage for Interactive Services
Jason Baker, Chris Bond, James C. Corbett, JJ Furman, Andrey Khorlin, James Larson,
Jean-Michel Léon, Yawei Li, Alexander Lloyd, Vadim Yushprakh
Google, Inc.
{jasonbaker,chrisbond,jcorbett,jfurman,akhorlin,jimlarson,jm,yaweili,alloyd,vadimy}@google.com
概要
Megastore は、現在の対話的オンラインサービスの要求を満たすために開発されたストレージシステムです。Megastore は、NoSQL データストアのスケーラビリティと、伝統的 RDBMS の使いやすさを、新しい方法でブレンドします。そして、強一貫性の保証と、高可用性の両方を提供します。私達は、細粒度のデータのパーティションの中で、完全にシリアライズ可能な ACID セマンティクスを提供します。このパーティショニングのために、それぞれのライトをワイド・エリア・ネットワークにわたって、合理的な遅延で同期的に複製することができます。そして、データセンタの間のシームレスなフェールオーバーもサポートされます。この論文は、Megastore のセマンティクスと複製アルゴリズムを述べます。また、Megastore を使って構築された、広い範囲の Google 本番サービスをサポートする上で私達が経験したことも述べます。
Categories and Subject Descriptors
C.2.4 [Distributed Systems]: Distributed databases; H.2.4
[Database Management]: Systems—concurrency, distrib-
uted databases
General Terms
Algorithms, Design, Performance, Reliability
Keywords
Large databases, Distributed transactions, Bigtable, Paxos
This article is published under a Creative Commons Attribution License
(http://creativecommons.org/licenses/by/3.0/), which permits distribution
and reproduction in any medium as well allowing derivative works, pro-
vided that you attribute the original work to the author(s) and CIDR 2011.
5 th Biennial Conference on Innovative Data Systems Research (CIDR ’11)
January 9-12, 2011, Asilomar, California, USA.
１． はじめに
デスクトップアプリケーションがクラウドに移行するにつれて、対話的オンラインサービスはストレージコミュニティに新しい要求を満たすように強いてきました。電子メール、コラボレーティブドキュメント、そしてソーシャルネットワーキングのようなサービスは指数的に増加しており、既存のインフラストラクチャの限界を試しています。これらサービスのストレージ要求を満たすことは、いくつかの矛盾する要件のために挑戦的です。
まず、インターネットは潜在的利用者のぼうだいな参加者を連れてきます。このため、アプリケーションは高度にスケーラブルでなくてはいけません。サービスは、MySQL [10] をそのデータストアとして使えば、迅速に構築できるかもしれません。しかし、そのサービスを数百万の利用者にスケールすることは、そのストレージインフラストラクチャの完全な再設計を必要とします。２つめに、サービスは競争して利用者を得なくてはいけません。これは、機能のラピッドな開発と市場への素早い投入が必要です。３つめに、サービスは応答性が良くなくてはいけません。このため、ストレージシステムは低遅延でなくてはいけません。４つめに、サービスは利用者に、データの一貫したビューを提供するべきです。更新の結果は、直ちに見えるべきで、永続的であるべきです。クラウドにホストされたスプレッドシートの編集が消えるのは、どんなに短時間でも、貧しいユーザ経験です。最後に、利用者は、インターネットサービスが、24/7 アップであることを期待するようになりました。なので、サービスは高可用でなくてはいけません。サービスは、個々のディスク、マシン、ルーターの障害から、データセンタ全体に影響する大規模な停電に至るまでの多くの種類の障害に対して、頑強でなくてはいけません。
これらの要件は、競合します。リレーショナルデータベースは簡単にアプリケーションを構築するためのリッチな機能セットを提供します。しかし、それは数億の利用者にスケールするのは困難です。Google の Bigtable [15], Apache Hadoop の HBase [1], あるいは Facebook の Cassandra [6] のような NoSQL データストアは、高度にスケーラブルです。しかし、それらの制限のある API と、ゆるい一貫性モデルは、アプリケーション開発を複雑にします。データを、離れたデータセンタにまたがって複製し、同時に、低遅延を提供するのは挑戦的です。また、複製されたデータの一貫したビューを保証するのは、特に障害の間、同様に挑戦的です。
Megastore は、今日の対話的オンラインサービスのストレージ要件を満たすために開発されたストレージシステムです。それは、NoSQL データストアのスケーラビリティと、伝統的 RDBMS の使いやすさを、ブレンドした点で、新しいです。それは、高可用性とデータの一貫したビューを達成するために、同期の複製を使います。短く言えば、それは完全にシリアライズ可能な ACID セマンティクスを、離れた複製にわたって提供し、対話的アプリケーションをサポートするために十分な低遅延を提供します。
私達はこれを、RDBMS vs. NoSQL 設計空間の中間に位置することで達成します。私達はデータストアを分割し、それぞれのパーティションを別々に複製します。パーティションの中では、完全な ACID セマンティクスを提供します。しかし、それらをまたがっては、限られた一貫性保証しか提供しません。私達はセカンダリインデックスのような、伝統的なデータベース機能を提供します。しかしそれは、利用者が許容できる遅延限界内でスケールすることのできる機能、そして私達のパーティションスキームがサポートできるセマンティクスの元、に限られます。私達は、ほとんどのインターネットサービスのデータは、このアプローチが実現可能なように、適切に分割できる（例えば、利用者ごとに）ことと、少しの、しかし、厳格でない機能のセットは、クラウドアプリケーションの開発の負荷を大いに減らすことができると主張します。
慣用的知恵 [24, 28] とは逆に、私達は Paxos [27] を使って、対話的アプリケーションにとって合理的な遅延を提供し、かつ、ライトを地理的に分散したデータセンタにわたって同期で複製する高可用なシステムを作ることができました。多くのシステムは Paxos を、ロック、マスター選出、あるいはメタデータと構成の複製のためにだけ使いますが、私達は、Megastore が、主となるユーザデータを、ライトのたびに、複数のデータセンタにわたって複製するために Paxos を使う、実際に配備された最大のシステムだと信じます。
Megastore は、Google 内部で何年にもわたって広く配備されてきました[20]。それは一日に、３０億以上のライトと、２００億以上のリードトランザクションを処理し、ほぼ１ペタバイトのプライマリデータを多くの地球規模のデータセンタをまたがって格納します。
この論文の主な寄与は以下です。
１． 対話的アプリケーションのラピッドな開発を可能とするとともに、高可用性とスケーラビリティが最初からビルトインされているデータモデルとストレージシステムの設計。
２． システムに高可用性を提供するために地理的に分散されたデータセンタをまたがった、低遅延操作に最適化された Paxos 複製とコンセンサスアルゴリズムの実装。
３． Google での大規模な Megastore の配備をした私達の経験の報告。
この論文は以下のように構成されます。２節は、 Megastore がパーティショニングを使って、どのように高可用性とスケーラビリティを提供するかを述べます。また、多くの対話的インターネットアプリケーションにとって、私達の設計が十分であることを正当化します。３節は、Megastore のデータモデルと機能の概要を提供します。４節は、複製アルゴリズムを詳しく説明し、現実でのその性能測定結果をいくらか示します。５節はシステムを開発する上での私達の経験をまとめます。関連する研究を６節に、結論を７節に述べます。
２ 可用性とスケールに向けて
地球規模、高信頼、そしてスケールが任意に大きいという私達のストレージプラットフォームへの要求と比較して、私達のハードウェア構成要素は、地理的に閉じ込められ、障害がありがちで、容量も限られます。私達はこれらのコンポーネントを、より優れたスループットと信頼性を提供する、一つの統一された統合体にまとめなければいけません。
そのために私達は両方を攻めるアプローチを取りました。
・可用性のために、私達は、長距離リンクに最適化された、同期で、フォールトトレラントなログリプリケータを実装しました。
・スケールのために、私達は、データを小さいデータベースからなる広い空間に分割しました。それぞれは、複製ごとの NoSQL データストアに自分自身の複製されたログを持ちます。
２．１ 複製
データを、単一のデータセンタ内のホストにまたがって複製することは、ホスト固有の障害を克服することによって、可用性を改善します。しかし、限界もあります。それらを外の世界につなぐネットワークや、それらを給電、冷却、そして設置するインフラストラクチャに対峙しなくてはいけません。経済的に建設されたサイトはあるレベルの施設ごとの停電の危険[25]があり、地域的災害の危険もあります。クラウドストレージが可用性の要求に応えるためには、サービス提供者は、データを広い地理的領域に複製しなくてはいけません。
２．１．１ 戦略
広域複製のための一般的な戦略を、私達は以下のように評価しました。
非同期マスター／スレーブ
マスターノードは、ライトアヘッドログエントリを、少なくても一つのスレーブに複製します。ログ追加は、マスターにおいて、スレーブへの転送と並行して、アクノリッジされます。マスターは、速い ACID トランザクションをサポートできますが、スレーブへのフェールオーバーの間、ダウン時間あるいはデータ喪失の危険があります。マスターシップを調停するためにコンセンサスプロトコルが必要です。
同期マスター／スレーブ
マスターは、変更をアクノリッジする前に、変更がスレーブにミラーされるのを待ちます。それは、データ喪失の無いフェールオーバーを可能とします。マスターとスレーブの障害は、外部システムによる迅速な検出が必要です。
楽観的複製
均質な複製グループのどのメンバでも変更を受け付けます[23]。変更は、非同期に、グループ内を伝搬します。可用性と遅延は素晴らしいです。しかし、コミット時には、グローバルな変更の順序はわかりません。このため、トランザクションは不可能です。
私達は、障害の時にデータを失うことのある戦略は避けました。障害は巨大システムではよくあることです。また私達は、ACID トランザクションを許さない戦略は捨てました。結果整合のシステムは運用上で有利ですが、ラピッドなアプリケーション開発におけるリード・モディファイ・ライト慣用句をあきらめるのは、現在では困難すぎます。
私達はまた、重量級のマスターがある選択を捨てました。フェールオーバーは高い遅延のステージの連続を必要とし、それはしばしば、利用者に見える中断となります。さらに、かなりの量の複雑さがあります。特別のマスターを完全に避けることができるのに、なぜ、マスターシップを調停するフォールトトレラントシステムと、フェールオーバーワークフローを構築するのでしょうか？
２．１．２ Paxos 登場
私達は、Paxos を使うことに決めました。それは、証明され、最適で、フォールトトレラントなコンセンサスアルゴリズムであり、特別のマスターが不要です[14, 27]。私達は、ライトアヘッドログを、対象のピアで構成されるグループ内で複製します。どのノードも、リードとライトを開始できます。それぞれのログ追加は、複製の過半数からのアクノリッジを待ってブロックします。そして、マイノリティにある複製は、可能ならばキャッチアップします。このアルゴリズムの本質的なフォールトトレランスは、特別の、「障害」状態を必要としません。４．４．１節で詳しく述べる新しい Paxos の拡張は、アップツーデートのどの複製からも、ローカルリードを許します。もうひとつの拡張は、単一のラウンドトリップのライトを許します。
Paxos によるフォールトトレランスがあっても、単一のログを使うための限界があります。複製が、ワイド・エリア・ネットワークをまたがって分散されていることから、通信遅延は全体のスループットを制限します。さらに、複製がどれも最新でない場合や、過半数がライトをアクノリッジできない場合に、進行は止められます。数千あるいは数百万の利用者をホストする伝統的 SQL データベースでは、同期で複製されるログを使うことは、広い範囲の衝撃を持つサービス中断の危険があります[11]。このため、可用性とスループットを改善するために、私達は複数の複製されたログを使います。それぞれのログは、データセットの自分自身のパーティションを管理します。
２．２ パーティショニングと局所性
私達の複製スキームをスケールし、元となるデータストアの性能を最大化するために、私達はアプリケーションに、自分のデータのパーティショニングと局所性を細粒度で制御させます。
２．２．１ エンティティグループ
スループットをスケールし、サービス中断を局所化するために、私達はデータを、エンティティグループ[24]の集まりに分割します。それぞれのエンティティグループは、独立して、同期で、ワイド・エリアを通して複製されます。元となるデータは、それぞれのデータセンタのスケーラブルな NoSQL データストアに格納されます（図１を参照）。
一つのエンティティグループ内の複数のエンティティは、単一フェーズの ACID トランザクション（そのためのコミットログは、Paxos を使って複製されます）によって更新されます。エンティティグループをまたがる操作は、高価な２相コミットに頼ることもできます。しかし、典型的には、Megastore の効率的な非同期メッセージを活用します。送信側のエンティティグループにあるトランザクションは、一つあるいはそれ以上のメッセージをキューに置きます。受信側のエンティティグループにあるトランザクションはアトミックにこれらのメッセージを消費して、その結果となる更新を適用します。
私達は、論理的に離れたエンティティグループの間で非同期メッセージを使うのであり、物理的に離れた複製の間ではないことに注意下さい。データセンタの間の全てのネットワークトラフィックは複製操作によるものです。それは同期で一貫しています。
エンティティグループにローカルなインデックスは ACID セマンティクスに従います。エンティティグループをまたがるそれは、よりゆるい一貫性を持ちます。エンティティグループについて、そしてエンティティグループの間のいろいろな操作は、図２を参照下さい。
２．２．２ エンティティグループの境界を選ぶ
エンティティグループは高速な操作のためのデータのアプリオリなグルーピングを定義します。細粒度過ぎる境界は、グループをまたがる操作を過度に起こします。しかし、あまりに多くの関係のないデータを一つのグループに置くと、無関係なライトをシリアライズするため、スループットが低下します。
以下の例は、アプリケーションがこれらの制約の中でうまくふるまう方法を示します。
電子メール
それぞれの電子メールアカウントは、自然なエンティティグループを作ります。アカウント内の操作はトランザクショナルで、一貫しています。メッセージを送ったりラベル付けする利用者は、万一、他の複製にフェールオーバーすることがあっても、その変更を観測することが保証されます。外部のメールルータが、アカウントの間の通信を扱います。
ブログ
ブログアプリケーションは、エンティティグループの複数のクラスを使ってモデルされるでしょう。それぞれの利用者はプロファイルを持ちます。それは自然に、それ自身のエンティティグループです。しかし、ブログはコラボレーティブであり、単一の永続的所有者はいません。私たちはエンティティグループの二つ目のクラスを作って、それぞれのブログのポストとメタデータを持たせます。三つ目のクラスは、それぞれのブログで名乗られる、一意の名前をつなぎます。アプリケーションは、一つのユーザ操作がブログとプロファイルの両方に影響するとき、非同期メッセージングに頼ります。新しいブログを作ったり、その一意の名前を名乗るなどの低いトラフィックの操作には、二相コミットがより便利で、適切に動作します。
マップ
地理的データは、一貫したあるいは便利な大きさの自然の粒度は何も持ちません。マップアプリケーションは地球をオーバーラップしないパッチに分割することで、エンティティグループを作ることができます。パッチをまたがる更新に対しては、アプリケーションは二相コミットを使ってそれらをアトミックにします。パッチは、二相トランザクションがあまり無いように、十分大きくなくてはいけません。しかし、それぞれのパッチが、小さいライトスループットしか必要としない程度には小さくなくてはいけません。以前の例とは異なり、エンティティグループの数は使用が増しても増えません。なので、後のスケールにおいて十分な合計スループットが出るように、最初に、十分な数のパッチを作る必要があります。
Megastore の上に作られたほとんど全てのアプリケーションは、エンティティグループの境界を引く自然な方法を見つけてきました。
２．２．３ 物理レイアウト
私たちは、一つのデータセンタ内のスケーラブルでフォールトトレラントなストレージのために、 Google の Bigtable [15] を使います。それは、操作を複数の行に分散することによって、任意のリードとライトのスループットをサポートすることを私たちに許します。
私たちは、アプリケーションにデータの配置を制御させることで、遅延を最小に、スループットを最大にします。アプリケーションは、Bigtable インスタンスを選択し、インスタンス内の局所性を指定します。
遅延を最小化するために、アプリケーションはデータを利用者の近くに、複製を互いに近くに維持しようとします。それぞれのエンティティグループをそれが最もアクセスされる地域あるいは大陸に割り当てます。その地域内で、アプリケーションは、独立した障害ドメインに属するデータセンタへ、三重もしくは五重の複製を割り当てます。
低遅延、キャッシュの効率化、そしてスループットのために、エンティティグループのデータは Bigtable の行の連続した範囲に置かれます。アプリケーションは、私たちのスキーマ言語を使って、一緒にアクセスされるデータを近くの行に格納したり、あるいは同じ行に非正規化したり、階層型データの配置を制御します。
３． Megastore のツアー
Megastore はこのアーキテクチャを、スケーラブルアプリケーションのラピッドな開発を促進するように注意深く選ばれた機能セットにマップします。この節は、トレードオフを動機づけ、その結果となった、開発者のための機能を述べます。
３．１ API 設計哲学
ACID トランザクションは、正しさについての推論を単純にします。しかし、性能について推論できることも同じくらい重要です。Megastore は、コスト透明な API を強調します。それは、実行時のコストが、アプリケーション開発者の直観に合うものです。
正規化されたリレーショナルスキーマは問い合わせ時のジョインに依存して、利用者の操作に応えます。Megastore アプリケーションにとって、これはいくつかの理由で正しいモデルではありません。
・大規模な対話的負荷は、表現力に優れた問い合わせ言語よりも、予測可能な性能からの方がより利益を得ます。
・私たちの対象とするアプリケーションはライトよりリードがほとんどです。なので、仕事を、リード時からライト時に移すことは価値があります。
・Bigtable のようなキーバリューストアにおいて、階層的データを格納、問い合わせするのは直截的です。
これらを心にとどめて、私たちは物理的局所性を細粒度で制御するためのデータモデルとスキーマ言語を設計しました。階層的レイアウトと、宣言的非正規化は、ほとんどのジョインの必要をなくすのに助けになりました。問い合わせは、特定のテーブルとインデックスに対して、走査あるいは検索を指定します。
ジョインが必要な時には、それはアプリケーションコードで実装されます。私たちはマージジョインアルゴリズムのマージフェーズの実装を提供します。そこで利用者は、同じテーブルのプライマリキーを同じ順序で返す複数の問い合わせを提供します。私たちは次に、提供された全ての問い合わせに対するキーの論理積を返します。
並列問い合わせをしてアウタージョインを実装するアプリケーションもあります。これは典型的にはインデックスの検索をして、その検索の結果を使って並列のインデックス検索をすることを含みます。セカンダリインデックスの検索が並列に行われ、最初の検索の結果の数が合理的に小さいならば、これは SQL スタイルのジョインの効率的な代わりになることに私たちは気が付きました。
スキーマの変更は、問い合わせの実装コードに対応する変更を必要としますが、このシステムは、機能が、その性能への影響を明確に理解して作られていることを保証します。例えば、利用者が（データベースの背景は持たないかもしれません）ネストしたループのジョインアルゴリズムのようなものを書いていることに気が付いたならば、その人は直ちに、インデックスを追加して、前記のインデックスをベースとするジョインアプローチに従うほうが良いだろうと分かります。
３．２ データモデル
Megastore は、RDBMS の抽象化されたタプルと、NoSQL の具体的な行カラムストレージの中間に位置するデータモデルを定義します。RDBMS と同様に、データモデルはスキーマで宣言され、強い型付けがされます。それぞれのスキーマはテーブルのセットを持ち、テーブルはエンティティのセットを含み、エンティティは属性のセットを含みます。属性は、名前と型がある値です。型は、文字列、いろいろな種類の数字、あるいは、Google の Protocol Buffers [9] です。それは、必須、オプショナル、あるいは、繰り返し型（一つの属性に値のリストを置くことが可能です）です。あるテーブルの全てのエンティティは同じセットの使用可能属性を持ちます。属性のシーケンスを使って、エンティティのプライマリキーを作ります。プライマリキーはそのテーブル内で一意でなくてはいけません。図３は、単純な写真ストレージアプリケーションのためのスキーマの例を示します。
Megastore テーブルは、エンティティグループルートテーブルであるか、子テーブルであるかのどちらかです。それぞれの子テーブルは、図３の ENTITY GROUP KEY アノテーションで示すように、ルートテーブルを参照する、一つの識別される外部キーを宣言しなくてはいけません。こうして、子エントリはそれぞれ、そのルートテーブルの特定のエントリ（ルートエントリと呼ばれます）を参照します。エンティティグループは、ルートエンティティと、子テーブルにあってそれを参照する全てのエントリからなります。一つの Megastore インスタンスは複数のルートテーブルを持つことができます。その結果、エンティティグループの異なるクラスができます。
図３の例のスキーマで、それぞれの利用者の写真のコレクションは別々のエンティティグループです。ルートエンティティは User で、Photo が子エンティティです。Photo.tag フィールドは繰り返し型であることに注意ください。こうして、サブテーブルの必要なしに、Photo ごとに、複数のタグが可能です。
３．２．１ キーを使った、プレジョイン
伝統的リレーショナルモデリングは、全てのプライマリキーが surrogate value を取ることを勧めます。Megastore のキーは、一緒に読まれるエンティティをクラスタ化するために選ばれます。それぞれのエンティティは一つの Bigtable 行にマップされます。プライマリキー値は、Bigtable の行キーを作るために連結され、残った属性それぞれは、Bigtable カラムを一つ、占めます。
図３において、Photo と User テーブルが共通の user id キープレフィックスを共有する様子を注意してください。IN TABLE User ディレクティブは、Megastore に、これら二つのテーブルを同じ Bigtable に一緒に置くように指示します。そして、キーの順序は、Photo エンティティが対応する User の近くに格納されることを保証します。この機構を再帰的に適用して、任意のジョイン深さに沿った問い合わせを高速化できます。 このようにして利用者は、キー順序を操作することによって階層的レイアウトを強制できます。
スキーマで、キーが昇順もしくは降順にソート、あるいはソートと一切無関係になるように宣言できます。SCATTER 属性は、 Megastore に、それぞれのキーの先頭に２バイトのハッシュをつけるように指示します。単調増加するキーをこのようにエンコードすることで、複数の Bigtable サーバをまたがる大きなデータセットにおいて、ホットスポットを防ぎます。
３．２．２ インデックス
エンティティ属性のリストあるいはプロトコルバッファ内のフィールドのどれにでも、セカンダリインデックスを宣言できます。私たちはインデックスの二つの高レベルクラスを区別します。ローカルとグローバルです（図２を参照）。ローカルインデックスはそれぞれのエンティティグループのための別々のインデックスとして扱われます。それは、エンティティグループ内でデータを探すために使われます。図３で、PhotosByTime はローカルインデックスの例です。インデックスエントリはエンティティグループ内に格納され、主のエンティティデータとともに、アトミックに、一貫して、更新されます。
グローバルインデックスはエンティティグループをまたがります。それは、それを含むエンティティグループをあらかじめ知ることなく、エンティティを探すために使われます。図３の PhotosByTag インデックスはグローバルであり、所有者にかかわらずに、指定したタグでマークされた写真を見つけることができます。グローバルインデックスの走査は多くのエンティティグループが所有するデータを読むことができます。しかし、全ての最近の更新を反映することは保証されません。
Megastore はこれ以外にもインデックス機能を提供します。
３．２．２．１ Storing 節
エンティティデータをインデックスを使ってアクセスするのは、通常は２ステップの処理です。最初にインデックスを読んで、マッチするプライマリキーを探します。次にそのキーを使ってエンティティをフェッチします。私たちは、エンティティデータの一部を、インデックスエントリに直接、非正規化する方法を提供します。インデックスに、STORING 節を加えることで、アプリケーションは主テーブルから追加の属性を格納でき、リード時に高速なアクセスが可能です。例えば、PhotosByTag インデックスは、写真のサムネイル URL を格納して、追加の検索の必要なしに速い取得ができます。
３．２．２．２ 繰り返し型インデックス
Megastore は、繰り返し型属性と、プロトコルバッファのサブフィールドをインデックスする能力を提供します。繰り返し型インデックスは、子テーブルの、効率的な代替です。PhotosByTag は、繰り返し型インデックスです。tag 属性のそれぞれの一意のエントリは、Photo のために、一つのインデックスエントリを作ります。
３．２．２．３ インラインインデックス
インラインインデックスは、ソースエンティティから、関連するターゲットエンティティへとデータを非正規化する方法を提供します。ソースエンティティからのインデックスエントリは、ターゲットエンティティ内の、仮想的な繰り返し型カラムとして現れます。インラインインデックスは、他のテーブルを参照する外部キーを持つテーブルならばどれにでも作ることができます。ターゲットエンティティの最初のプライマリキーを、インデックスの最初のコンポーネントとして使い、ターゲットと同じ Bigtable 内で物理的にデータを位置づけます。
インラインインデックスは、子エンティティから情報のスライスを抽出し、そのデータを親に格納して、速いアクセスを可能とするために便利です。繰り返し型インデックスと組み合わせると、多対多のリンクテーブルを維持するよりもずっと効率的に、多対多の関係を実装するために使えます。
PhotosByTime インデックスは、親の User テーブルのインラインインデックスとしても実装することができました。これは、データを、通常のインデックスとして、あるいは、User に含まれるそれぞれの Photo の時刻で順序付けられたエントリとして、User の仮想的な繰り返し型属性としてアクセス可能とするでしょう。
３．２．３ Bigtable へのマッピング
Bigtable カラム名は、Megastore テーブル名と属性名をつないだものです。これにより、異なる Megastore テーブルからのエンティティが衝突なしに同じ Bigtable 行にマップされます。図４は、例にした写真アプリケーションからのデータが、Bigtable ではどのように見えるかを示します。
ルートエントリのための Bigtable 行の中に、私たちはそのエンティティグループのためのトランザクションと複製のメタデータを格納します。それには、トランザクションログも含みます。全てのメタデータを一つの Bigtable 行に格納することは、それを一つの Bigtable トランザクションでアトミックに更新することを許します。
インデックスエントリのそれぞれは、一つの Bigtable 行で現わされます。セルの行キーは、インデックスされるエントリのプライマリキーに、インデックスされる属性値をつないで作られます。例えば、PhotosByTime インデックスの行キーは、それぞれの写真に対して、タプル (user id; time; primary key) となるでしょう。繰り返し型フィールドをインデックスすると、繰り返される要素ごとに一つのインデックスエントリが作成されます。例えば、三つのタグを持つ写真のプライマリキーは、PhotosByTag に、三回現れます。
３．３ トランザクションと同時実行制御
それぞれの Megastore エンティティグループは、シリアライズ可能 ACID セマンティックを提供する小さなデータベースとして機能します。トランザクションは、その更新を、そのエンティティグループのライトアヘッドログに書き、そして、その更新はデータに適用されます。
Bigtable は、同じ行／カラム対に、複数の値を異なるタイムスタンプを持って格納する能力を提供します。私たちはこの機能を、複数バージョン同時実行制御、multiversion concurrency control (MVCC)を実装するために使います。トランザクション内の更新が適用される時、そのトランザクションのタイムスタンプのところに、その値が書かれます。リーダーは、最後に完全に適用されたトランザクションのタイムスタンプを使って、部分的更新を見ないようにできます。リーダーとライターは互いにブロックしあいません。そして、リードは、トランザクションの間、ライトから孤立化されます。
Megastore は、current, snapshot, そして inconsistent リードを提供します。current と snapshot リードは常に一つのエンティティグループのスコープ内で起きます。current リードを始めるとき、トランザクションシステムは最初に、全ての以前にコミットされたライトが適用されたことを保証します。次にアプリケーションは最近のコミットしたトランザクションのタイムスタンプのところを読みます。snapshot リードの場合、システムは最後に完全に適用されたことがわかっているトランザクションのタイムスタンプをピックアップします。そしてそこから読みます。その時、コミットしたトランザクションがまだ適用されていないことがあっても構いません。Megastore は、inconsistent リードも提供します。それは、ログの状態を無視して、直接、最新の値を読みます。これは、よりアグレッシブな遅延要件を持ち、無効あるいは部分的に適用されたデータに耐えることのできる操作にとって便利です。
ライトトランザクションは、次に使用可能なログ位置を決めるために、常に current リードから始まります。コミット操作は変更をログエントリに集めて、それに以前のどれよりも大きいタイムスタンプを割り当て、Paxos を使ってそれをログに追加します。そのプロトコルは楽観的同時実行制御を使います。複数のライターが同じログ位置に書こうと試みるかもしれませんが、一つだけが勝ちます。残りは、勝ったライトを見て、アボートし、自分の操作をリトライします。衝突の影響を減らすために、アドバイザリーロックが使用可能です。特定のフロントエンドサーバへのセッションアフィニティを使って、ライトをバッチすることで、全く衝突を除くこともできます。
完全なトランザクションライフサイクルは以下のようです。
１ リード： 最後にコミットしたトランザクションのタイムスタンプとログ位置を得ます。
２．アプリケーションロジック：Bigtable から読んで、ライトをログエントリに集めます。
３．コミット；Paxos を使ってそのエントリをログに追加するコンセンサスを得ます。
４．適用：Bigtable にあるエンティティとインデックスに変更を書きます。
５．後始末：不要になったデータを消します。
ライト操作は、コミットの後いつでもクライアントに戻ることができます。しかし、最も近い複製に適用がされるまで、ベストエフォートで待ちを試みます。
３．３．１ キュー
キューは、エンティティグループの間でトランザクショナルなメッセージを提供します。それは、グループをまたがる操作や、複数の更新を一つのトランザクションにまとめたり、あるいは仕事を後回しにするために使うことができます。あるエンティティグループにおけるトランザクションは、そのエンティティを更新することに加えて、アトミックに複数のメッセージを送受信できます。それぞれのメッセージは送信と受信エンティティグループが一つづつあります。両者が異なるときは、配布は非同期です。（図２を参照。）
キューは、多くのエンティティグループに影響する操作を実行する方法を提供します。例えば、カレンダーアプリケーションを考えましょう。それぞれのカレンダーは別々のエンティティグループを持ちます。カレンダーのグループに、招待を送りたいとします。一つのトランザクションは、招待のキューメッセージを多くの別々のカレンダーにアトミックに送ることができます。そのメッセージを受けたそれぞれのカレンダーは自分自身のトランザクションで招待を処理して、招待された人の状態を更新し、メッセージを削除します。
完全機能の RDBMS には、メッセージキューの長い歴史があります。私たちのサポートはそのスケールにおいて注目すべきです。キューを宣言するとそれぞれのエンティティグループに自動で inbox が作成され、数百万のエンドポイントができます。
３．３．２ 二相コミット
Megastore は、エンティティグループをまたがるアトミックな更新のために、二相コミットをサポートします。このトランザクションはずっと高い遅延を持ち、衝突の危険を増やしますから、私たちは一般的には、アプリケーションがこの機能を使うのを推奨せず、キューをお勧めします。そうはいっても、これは一意のセカンダリインデックスを強制するためのアプリケーションコードを単純にするには便利です。
３．４ その他の機能
私たちは、Bigtable のフルテキストインデックスと緊密な連携を作りました。そこでは、更新と検索は Megastore のトランザクションと複数バージョン同時実行制御に参加します。Megastore スキーマで宣言されたフルテキストインデックスは、テーブルのテキストや、アプリケーションの生成した他の属性をインデックスできます。
同期の複製は、もっとも一般的な破壊と事故に対しては十分な防衛です。しかし、プログラマあるいはオペレータの誤りに対しては、バックアップが欠かせません。Megastore の統合されたバックアップシステムは定期的なフルスナップショットも、トランザクションログのインクリメンタルなバックアップもサポートします。回復処理は、エンティティグループの状態を任意の時刻に戻すことができます。選択したログエントリを除くこともオプションでできます（事故による削除の場合など）。バックアップシステムは、削除されたデータを捨てる場合、法律的そして常識的な原則に従います。
アプリケーションは格納中のデータを暗号化するオプションがあります。それには、トランザクションログも含まれます。暗号化は、エンティティグループごとに別の鍵を使います。同じオペレータに暗号化の鍵と暗号化されたデータの両方へのアクセスを許可することを避けます。
４． 複製
この節は、私たちの同期複製スキームの核心である、Paxos の低遅延な実装について詳しく述べます。運用上の詳細を議論して、私たちの本番サービスの測定結果をいくつか示します。
４．１ 概要
Megastore の複製システムは、元となる複製に格納されたデータの、単一で一貫したビューを提供します。リードとライトはどの複製から始まってもよく、クライアントがどの複製から始めたかにかかわらず、ACID セマンティックが守られます。複製は、エンティティグループごとに、そのグループのトランザクションログを複製のクオーラムに同期で転送することで行われます。ライトは典型的には、一回の、データセンタ間の通信を必要とし、健全な場合のリードはローカルに走ります。Current リードは以下の保証をします。
・リードは常に、最後にアクノリッジされたライトを観測します。
・あるライトが観測された後は、全ての未来のリードはそのライトを観測します。（ライトは、アクノリッジされる前に観測されることがあります。）
４．２ Paxos の簡単なまとめ
Paxos アルゴリズムは、複製のグループ内で、単一の値に関してコンセンサスに達するための方法です。それは、メッセージの遅延やリオーダーに耐え、停止して失敗する複製にも耐えます。アルゴリズムが進むためには、複製の過半数がアクティブで到達可能でなくてはいけません。つまり、それは 2F + 1 の複製中で、F の障害を許します。過半数が一度値を選択したら、その値を読み書きする未来の全ての試みは同じ結果に達します。
単一の値の結果を決定する能力は、それだけでは、データベースにとってそれほど役に立ちません。データベースは典型的には Paxos を使ってトランザクションログを複製します。その場合、ログ内のそれぞれの位置ごとに、個別の Paxos インスタンスが使われます。新しい値は、最後に選択された位置の次の位置に書かれます。
オリジナルの Paxos アルゴリズム [27] は、複数ラウンドの通信を必要とするために、高遅延のネットワークリンクには不適切です。ライトは、コンセンサスが得られる前に、少なくても二回の複製間ラウンドトリップが必要です。prepare ラウンドは、それに続く accept ラウンドの権利を確保します。リードは、最後に選択された値を決めるために、一ラウンドの prepare が必要です。Paxos を使って作られる実際の世界のシステムは、必要なラウンドトリップの数を減らして、それを現実的なアルゴリズムにします。私たちは最初に、マスターをベースとするシステムがどのように Paxos を使うかを概観し、次に、私たちがどのように Paxos を効率的にしたかを説明します。
４．３ マスターをベースとするアプローチ
遅延を減らすために、多くのシステムは専用のマスターを使い、全てのリードとライトはそこに向けられます。マスターは全てのライトに参加するため、その状態は常に最新です。それはネットワーク通信を起こさずに、現在のコンセンサス状態のリードを処理できます。それぞれの accept で、次のライトのための prepare をピギーバックすることで [14] ライトを単一の通信ラウンドに減らすことができます。マスターは、複数のライトを一緒にバッチして、スループットを改善できます。
マスターへの依存は、リードとライトの柔軟性を制限します。トランザクション処理は、連続するリードの遅延が蓄積しないように、マスターレプリカの近くで行われなくてはいけません。潜在的なマスターレプリカの全ては、システムの完全な負荷にとって適切なリソースを持っていなくてはいけません。スレーブレプリカは、それがマスターになる瞬間まで、リソースを浪費します。マスターのフェールオーバーは複雑な状態マシンを必要とすることがあり、サービスが回復するまでにはいくつものタイマーが満了する必要があります。利用者に見えるサービス中断を避けるのは困難です。
４．４ Megastore のアプローチ
この節で、私たちは、Paxos を私たちのシステムにとって現実的とした最適化と革新を議論します。
４，４，１ 速いリード
私たちは初期から、current リードは通常は任意の複製において、複製間の RPC なしで実行できるべきであるという要件を決めました。ライトは通常は全ての複製において成功するため、ローカルリードをどこでも許すのは現実的です。このローカルリードが、私たちに、よりよい使用率、全ての領域での低遅延、細粒度のリードフェールオーバー、そしてより単純なプログラム経験を与えました。
私たちは、コーディネータと呼ばれるサービスを設計しました。そのサーバが、それぞれの複製のデータセンタにいます。コーディネータサーバは、エンティティグループのセットであって、その複製がすべての Paxos ライトを観測したものを追跡します。そのセットに含まれるエンティティグループに対しては、複製はローカルリードを処理する十分な状態を持ちます。
コーディネータ状態を保守的に保つのは、ライトアルゴリズムの責任です。もし、ある複製の Bigtable へのライトが失敗したら、それは、そのグループのキーがその複製のコーディネータから除去されるまではコミットしたとは認められません。
コーディネータは単純なので、Bigtable よりも高信頼かつ迅速に応答します。まれな障害ケースやネットワーク分割の扱いは、４．７節に述べます。
４．４．２ 速いライト
速い、一度のラウンドトリップのライトを達成するために、Megastore はマスターをベースとするアプローチで使われる、prepare の前の最適化を採用します。マスターをベースとするシステムでは、成功したそれぞれのライトは、次のログ位置のための accept メッセージを発行する権利をマスターに許可するための prepare メッセージを暗黙的に含みます。ライトが成功したら、prepare は許可されたので、次のライトは直接、accept フェーズにスキップします。Megastore は専用のマスターは使いませんが、その代わり、リーダーを使います。
私たちはそれぞれのログ位置に対して、独立した Paxos アルゴリズムのインスタンスを走らせます。それぞれのログ位置のリーダーは、一つ前のログ位置のコンセンサス値とともに選択された一つの複製です。そのリーダーは、どの値が提案番号ゼロを使うことができるかを調停します。リーダーに値を最初に提出したライターが、全ての複製に、その値を提案番号ゼロとして受け入れるように頼む権利を勝ち得ます。他の全てのライターは二相 Paxos にフォールバックしなければいけません。
ライターは、値を他の複製に提出する前にリーダーと通信しなくてはいけないので、私たちは、ライターとリーダーの遅延を最小化します。私たちは、次のライトのリーダーを選ぶためのポリシーを、ほとんどのアプリケーションは、ライトを同じ領域から繰り返し提出するという観測事実に従って設計しました。これは、単純でかつ、効果的なヒューリスティックにつながります。最も近い複製を選べ。
４．４．３ 複製タイプ
これまで、全ての複製は full replica でした。それは、複製が全てのエンティティとインデックスのデータを持ち、current リードを処理できることを意味します。私たちはまた、witness replica というものもサポートします。witness は、Paxos ラウンドで投票し、ライトアヘッドログを格納します。しかし、そのログを適用せず、エンティティデータもインデックスも格納しません。なので、それらはより低いストレージコストを持ちます。それらは実効的にはタイブレーカであり、クォーラムを形成するための full replica が十分いないときに使われます。それらにはコーディネータはいないので、それらがライトをアクノリッジできないときも追加のラウンドトリップを強制することはありません。
Read-only replica は witnesse の逆です。それらは、データの完全なスナップショットを持ち、投票しない複製です。これらの複製へのリードは最近の過去の一時点での一貫したビューを反映します。この古さを許容できるリードにとっては、read-only replica は、ライト遅延に影響を与えることなく、データを広い地理的範囲に拡散させる助けとなります。
４．５ アーキテクチャ
図５は、二つの full replica と一つの witness replica を持つ Megastore インスタンスの鍵となるコンポーネントを示します。
Megastore はクライアントライブラリと補助的なサーバによって配備されます。アプリケーションはクライアントライブラリにリンクします。それは、Paxos や他のアルゴリズムを実装します。リードのための複製を選択し、遅れた複製をキャッチアップするなど。
それぞれのアプリケーションサーバは、特定の local replica を持ちます。クライアントライブラリはトランザクションを直接ローカルな Bigtable に送ることで、その複製への Paxos 操作を永続的にします。ワイドエリアラウンドトリップを最小にするために、ライブラリはリモート Paxos 操作をステートレスな中継 replication server に提出します。それは、自分のローカルな Bigtable と通信します。
クライアント、ネットワーク、あるいは Bigtable 障害は、ライトを、非決定な状態で放棄されたままとすることがあります。複製サーバは定期的に未完了のライトを走査し、Paxos を使って no-op 値を提案し、それを完了に持っていきます。
４．６ データ構造とアルゴリズム
この節は、単一の値のコンセンサスから、機能する複製されたログへのジャンプをするために必要なデータ構造とアルゴリズムを詳細に述べます。
４．６．１ 複製されたログ
それぞれの複製は、そのグループに関係するログエントリの変更とメタデータを格納します。ある複製が、以前の中断から回復した時にでもライトクォーラムに参加できることを保証するために、私たちは、複製がアウトオブオーダーの提案を受け付けるのを許します。私たちは、ログエントリを、Bigtable 内のそれぞれ独立したセルに格納します。
ログ複製が、ログの不完全なプレフィックスを持つ場合、ログ複製は「ホール」を持つと言います。図６は、一つの Megastore エンティティグループのいくつかの代表的なログ複製があるこのシナリオを示します。ログ位置 0-99 は完全にごみ掃除され、位置 100 は部分的に掃除されています。なぜならば、それぞれの複製は、他の複製は決してコピーを要求しないであろうことを知らされているからです。ログ位置 101 は全ての複製によってアクセプトされました。ログ位置 102 は、A と C で、ぎりぎりのクォーラムを見つけました。位置 103 は A と C でアクセプトされ、残り B は 103 にホールがある点で注目すべきです。位置 104 で、複製 A と B に競合するライトが試みられ、コンセンサスが得られていません。
４．６．２ リード
current リードの準備をする（ライトの前も同様に）ために、少なくても一つの複製がアップトゥデイトにされなくてはいけません。以前にログにコミットされた全ての変更はこの複製に複写され、適用されなくてはいけません。このプロセスを、キャッチアップと呼びます。
デッドライン管理をいくらか省略すると、current リードのアルゴリズムは以下の通りです。（図７に示します）
１ ローカルに問い合わせる：ローカルな複製のコーディネータに問い合わせて、このエンティティグループがローカルにアップトゥデイトであるかを決めます。
２ 位置を見つける：最高のコミットされたと思われるログ位置を決め、そのログ位置までを適用した複製を選びます。
(a) （ローカルリード）ステップ１がローカルな複製がアップトゥデイトであることを示すならば、ローカルな複製から最高のアクセプトされたログ位置とタイムスタンプを読みます。
(b) （マジョリティリード）もしローカルな複製がアップトゥデイトでない（あるいはステップ１かステップ2a がタイムアウトした）ならば、複製の過半数から読んで、どれかの複製が見た最大のログ位置を見つけます。そして、読む複製を選びます。私たちは、最も応答の良いあるいはアップトゥデイトな複製を選びます。常にローカルな複製とは限りません。
キャッチアップ：複製が選ばれたらすぐ、以下のように、それを最大の既知のログ位置までキャッチアップします。
(a)選んだ複製がコンセンサス値を知らないそれぞれのログ位置に対して、他の複製から値を読みます。既知のコミットされた値が得られない全てのログ位置に対して、Paxos を起動して、no-op ライトを提案します。Paxos は過半数の複製が単一の値、no-op もしくは以前に提案されたライトのどちらかに収束するようにはたらくはずです。
(b)適用されていない全てのログ位置のコンセンサス値をシーケンシャルに適用して、その複製の状態を分散コンセンサス状態に進めます。
失敗したら、別の複製でリトライします。
検証：ローカルな複製が選ばれ、それが以前はアップトゥデイトでなかった場合、コーディネータに validate メッセージを送り、(entity group; replica) 対が全てのコミットされたライトを反映していることを主張します。応答は待たないでください。もし要求が失敗したら、次のリードがリトライするでしょう。
データを問い合わせる：選ばれたログ位置のタイムスタンプを使って選ばれた複製を読みます。その選ばれた複製が使用不可能となったら、他の複製を選び、キャッチアップを行い、代わりにそこから読みます。一つの大きな問い合わせの結果は、複数の複製から透過的に集められることもできます。
現実的には、1 と 2a は並行して実行されるのに注意下さい。
４．６．３ ライト
リードアルゴリズムを完了した後、Megastore は次の使われていないログ位置、最後のライトのタイムスタンプ、そして次のリーダー複製を観察します。コミット時に状態への全てのペンディングの変更はパッケージされ、タイムスタンプと次のリーダの指名者とともに、次のログ位置のためのコンセンサス値として提案されます。もしこの値が分散コンセンサスに勝ったら、それは全ての full replica において状態に適用されます。そうでないときは、トランザクション全体はアボートされ、リードフェーズの始めからリトライしなくてはいけません。
前に述べたように、コーディネータは自分の担当の複製の中で、アップトゥデイトのエンティティグループを追跡します。もしライトが複製においてアクセプトされないときは、そのエンティティグループのキーを、その複製のコーディネータから除かなくてはいけません。この処理を、無効化と呼びます。あるライトがコミットされ適用する準備ができたと考えられる前に、全ての full replica はアクセプトしたかあるいは自分のコーディネータにそのエンティティグループを無効化させていなければいけません。
ライトのアルゴリズムは以下の通りです。（図８に示します）
１ アクセプトリーダー：リーダーに、その値を提案番号ゼロとしてアクセプトするように頼みます。うまくいったら、ステップ３にスキップします。
２ プリペア：このログ位置で今まで見られた最も高い提案番号より大きなものを使って、Paxos Prepare フェーズを全ての複製で走らせます。より高い番号の提案が見つかったら、書かれるべき値をそれに変えます。
３ アクセプト：残りの複製にその値をアクセプトするように頼みます。これが過半数の複製で失敗したら、ランダム化したバックオフの後、ステップ２に戻ります。
４ 無効化：その値をアクセプトしなかった全ての full replica において、コーディネータを無効化します。このステップでの障害処理は、以下の４．７節で述べます。
５ 適用：可能な限り多くの複製で、その値の変更を適用します。選択された値がもともと提案されたものと違う場合、衝突エラーを返します。
ステップ１は、４．４．２節の「速いライト」を実装します。単一フェーズの Paxos を使うライターは Accept コマンドを提案番号ゼロで送ることによって、Prepare メッセージをスキップします。ログ位置 n において選ばれた次のリーダー複製は、n + 1 での提案ゼロで使われる値を調停します。複数の提案者が提案番号ゼロを使って値を提出するかもしれないので、この複製でのシリアライズは特定のログ位置に対して、その提案番号がただ一つの値に対応することを保証します。
伝統的データベースシステムでは、コミット点（変更が永続的であるとき）は、可視点（リードが変更を見ることができ、ライターが成功を通知される時）と同じです。私たちのライトアルゴリズムでは、コミット点はステップ３の後で、そのライトが Paxos ラウンドに勝ったときです。しかし、可視点はステップ４の後です。全ての full replica がアクセプトしたか、それらのコーディネータを無効化した後になってやっと、ライトはアクノリッジされることができ、変更は適用されます。ステップ４の前にアクノリッジすることは、私たちの一貫性保証を破ることがあります。無効化がスキップされた複製における current リードはアクノリッジされたライトを観測できないことがあります。
４．７ コーディネータ可用性
コーディネータプロセスは、それぞれのデータセンタで走り、自分のローカルな複製の状態だけを維持します。前記のライトアルゴリズムでは、それぞれの full replica はアクセプトするか、自分のコーディネータを無効化するかのどちらかをしなくてはいけませんでした。なので、一つの複製の障害（Bigtable とコーディネータ）は常に、アクセス不能を起こすように見えるかもしれません。
現実的には、これはあまり問題とはなりません。コーディネータは単純なプロセスで外部依存も永続的ストレージも持ちません。なので、それは Bigtable サーバよりはずっと安定していることが多いです。とは言っても、ネットワークとホストの障害は、それでもコーディネータを使用不能にすることがあります。
４．７．１ 障害検知
ネットワーク分割に対処するために、コーディネータは、他のコーディネータがアップ、健康、そして一般的に到達可能であるかを判定するための、アウトオブバンドのプロトコルを使います。
私たちは、Google の Chubby ロックサービス [13] を使います。コーディネータは、開始時に、遠隔のデータセンタにある特定の Chubby ロックを取ります。要求を処理するために、コーディネータは、そのロックの過半数を持っていなければいけません。もしそれがクラッシュあるいはネットワーク分割のためにそのロックの過半数を失ったら、それは自分の状態を、保守的なデフォルトに戻します。自分の担当の全てのエンティティグループを古くて無効と考えます。その複製への以降のリードは複製の過半数にログ位置を問い合わせなくてはいけません。これは、ロックが再確保され、そのコーディネータのエントリが再度、有効になるまで続きます。
ライターは、コーディネータがそのロックを失ったかテストすることで、コーディネータの障害から保護されます。そのシナリオでは、コーディネータが自分のロックを再確保しようとしたときに自分が無効化されていると判定すると、ライターはわかっています。
このアルゴリズムは、生きているコーディネータを含むデータセンタが突然使用不可能になったときに、少しの（数十秒）ライトのサービス中断の危険があります。すべてのライターは、ライトが完了できる前に、コーディネータの Chubby ロックが満了するまで待たなくてはいけません（マスターフェールオーバーが始まるのを待つのとよく似ています）。マスターフェールオーバーの後と違って、コーディネータの状態が再構成されている間、リードとライトはスムーズに進行できます。この短くまれなサービス中断の危険は、それが可能とする速いローカルリードの安定した状態を考えると、十分以上に正当化されます。
コーディネータのライブネスプロトコルは非対称なネットワーク分割に弱いです。もしコーディネータが自分の Chubby ロックへのリースを維持できる一方、プロポーザと接触を失った場合、影響を受けるエンティティグループはライトの失敗を経験します。このシナリオでは、オペレータが、部分的に孤立化したコーディネータを無効にするために手作業のステップを実行します。この状況に直面したのは数回しかありません。
４．７．２ 検証の競合
可用性の問題に加えて、コーディネータを読み書きするためのプロトコルは多くの競合条件と争わなくてはいけません。無効メッセージは常に安全です。しかし、検証メッセージは注意して扱わないといけません。以前のライトに対する検証と、後のライトに対する無効化は、そのアクションに関連するログ位置を常に送ることで、コーディネータ内で競合から保護されます。より大きな数を持つ無効化は、常により小さい数を持つ検証に勝ちます。また、位置 ｎ にあるライターによる無効化と、どこかの位置 m < n にある検証との間のクラッシュに関連する競合もあります。私たちは、コーディネータのそれぞれの起動ごとに与えられる一意のエポック番号を使ってクラッシュを検出します。検証は、最近のコーディネータのリード以来、エポックが変わらないときだけ、コーディネータ状態を変更できます。
まとめると、コーディネータを使うことで、どのデータセンタからも速いローカルリードができることは、可用性への衝撃という点でタダではありません。しかし現実的には、コーディネータを走らせることによるほとんどの問題は、以下の要素によって緩和されます。
・コーディネータは、Bigtable サーバよりずっと単純なプロセスです。依存関係もずっと少ないです。このため、自然と、より高可用です。
・コーディネータの負荷は単純で均質なので、配備は安価で予測可能です。
・コーディネータのネットワークトラフィックは軽いので、安定した接続性のもとで高ネットワーク QoS を使うことができます。
・オペレータは、メンテナンスのため、あるいは不健康な期間、中央集権的にコーディネータを、無効化できます。特定のモニタリングシグナルについてはこれは自動化できます。
・Chubby のロックのクォーラムは、ネットワーク分断とノード障害のほとんどを検出します。
４．８ ライトスループット
私達の Paxos 実装は、システムのふるまいについて面白いトレードオフを持ちます。複数のデータセンタにあるアプリケーションサーバは、同じエンティティグループとログ位置に対して、同時に、ライトを始められます。そのうち一つ以外は失敗して、トランザクションをリトライしなくてはいけません。同期の複製による増加した遅延は、あるエンティティグループあたりのコミット率における衝突の確率を増やします。
その率を、エンティティグループあたり毎秒、数ライトにすると、大きな衝突率になります。エンティティが一度に少数の利用者によって操作されるアプリケーションにとっては、この制限は一般的には問題ではありません。私達のターゲットとするほとんどの顧客は、エンティティグループをより細かくシャードするか、複製たちが同じ地域に置かれることを保証することによってライトスループットをスケールします。それは遅延と衝突率の両方を下げます。
サーバーにある種の「スティックネス」を持つアプリケーションは、利用者の操作をバッチして、より少ない Megastore トランザクションにする有利な位置にあります。Megastore キューメッセージをバッチ処理するのは、一般的なパッチのテクニックであり、衝突率を下げ、合計スループットを増します。
常に毎秒数ライト以上を超さざるを得ないグループに対しては、アプリケーションは、コーディネータサーバが提供する細粒度のアドバイザーロックを使うことができます。トランザクションをバックツゥバックで整列させることで、衝突を検出した時に、リトライと、二相 Paxos に戻ることによる遅延を避けられます。
４．９ 運用上の問題
特定の full replica が不安定になったり、接続を失った時、Megastore の性能は落ちることがあります。この障害に対処するための方法がいくつかあります。それには、利用者を問題の複製以外にルーティングすること、そのコーディネータを無効化すること、あるいは、それ全体を無効にすることがあります。現実的には、これらのテクニックの組み合わせを使います。それらは固有のトレードオフを持ちます。
最初で、最も重要な障害への対応は、アプリケーションサーバへのトラフィックを近くの他の複製にルーティングしなおすことによって、影響を受けた複製にある Megastore クライアントを無効化することです。これらクライアントは典型的には、それらの下にあるストレージスタックと同じサービス中断の衝撃を経験します。そして外の世界からは到達不可能かもしれません。
トラフィックをルーティングし直すだけでは、不健康なコーディネータが自分の Chubby ロックを保持し続けている時には不十分です。次の対策は、その複製のコーディネータを無効にして、その問題がライト遅延に最小限の衝撃を持つことを保証することです。（４．７節はこの処理をより詳細に述べます。）一旦、ライターがその複製のコーディネータを無効にすることができたら、不健康なコーディネータのライト遅延への衝撃は限られたものとなります。ライトアルゴリズム中で、最初の「リーダーをアクセプトする」ステップだけが、複製に依存します。そして私達は厳しいデッドラインを維持し、その後、二相 Paxos にフォールバックするとともに、より健康なリーダーを次のライトのために指名します。
さらに厳しく、まれにしか使われないアクションは、その複製を完全に無効にすることです。クライアントも、複製サーバもそれとは通信しようとしなくなります。複製を引退させるのは魅力的に思えるかもしれませんが、可用性への大きな衝撃があります。一つ少ない複製は、ライターがクォーラムを形成するのを妨げるかもしれません。
訳注。原文は逆なのだが、前後の文脈から、こう訳しました。
この有効なユースケースは、試みられた操作が害をなすかもしれないとき、例えば、元となる Bigtable が極めて過負荷にあるとき、です。
４．１０ 本番での指標
Megastore は、Google 内で何年にもわたって配備されてきました。１００以上の本番アプリケーションがそれを自分のストレージサービスとして使います。この節で私達は、そのスケール、可用性、そして性能の測定結果をいくらか報告します。
図９は、アプリケーション毎、操作毎あたりに測定された可用性の分布を示します。私達のほとんどの顧客は、定常的なマシン障害、ネットワーク障害、データセンタ停電などの故障があっても、極めて高レベルの可用性を経験します。（少なくても５つの９）このサンプルの最低の端は、いくらかの、まだテスト段階にある本番前のアプリケーションとより高い障害耐性を持つバッチ処理アプリケーションを含みます。
平均リード遅延は数十ミリ秒です。これはデータ量に依存します。これはほとんどのリードがローカルであることを示します。ほとんどの利用者は、100–400 ミリ秒の平均ライト遅延を見ます。これは、データセンタ間の距離、書かれるデータの大きさ、そして full replica の数に依存します。図１０は、リードとコミット操作の平均遅延の分布を示します。
５． 経験
このシステムの開発は、テスト可能性への強い強調によって助けられました。コードは多くの（ただし安価な）アサーションとログでインストゥルメントされます。そして完全な単体テストカバレッジを持ちます。しかし、最も効果的なバグ発見ツールは、私達のネットワークシミュレータである、擬似ランダムテストフレームワークでした。それは、シミュレートされるノードあるいはスレッド間の、通信の全ての可能なオーダリングと遅延の空間を探査する能力があります。そして、同じシードを与えられれば、決定論的に同じ振る舞いを再現できます。バグは、アサーションの失敗（あるいは不正な結果）をトリガーした、怪しそうなイベントのシーケンスを見つけることによって明らかとなります。問題を診断するための十分なログとトレース情報をつけることもしばしばです。それはまた、単体テストのスイートに加えられます。スケジューリング状態空間の完全な探査は不可能ですが、この擬似ランダムシミュレーションは、他の方法で現実的である以上のことを探索できます。毎晩、シミュレートされる何千時間分の操作を走らせることによって、このテストは多くの驚くべき問題を見つけてきました。
現実世界での配備において、私達は期待される性能を観測しました。私達の複製プロトコルの最適化は実際に、ほとんどの場合にローカルリードを提供しました。そしれ、ライトはほぼ、一つの WAN ラウンドトリップのオーバーヘッドで行えました。ほとんどのアプリケーションは、遅延を許容できると判断しました。あるアプリケーションはライト遅延を利用者から隠すように設計されました。いくつかは、エンティティグループの境界を注意深く選んで、ライトスループットを最大化する必要がありました。この努力は大きな運用上の利点をもたらしました。Megastore の遅延のテールは、元となる層のそれよりも大いに短く、ほとんどのアプリケーションは計画されたあるいは計画されない中断を、わずかなあるいは全く無い手作業による介入で耐えることができました。
ほとんどのアプリケーションは、Megastore スキーマ言語を使ってそれぞれのデータをモデルします。Megastore スキーマ言語の中に、自分自身のエンティティ属性値モデルを実装したものもありました。そして、自分自身のアプリケーションロジックを使って、そのデータをモデルしました。（最も有名なのは、Google App Engine [8] です）二つのアプローチのハイブリッドを使うものもありました。静的なスキーマの上にダイナミックなスキーマを作ることは、そうでない方法と比べて、ほとんどのアプリケーションが、静的なスキーマの、性能、ユーザビリティ、一貫性の利点を享受することを許す一方、ダイナミックスキーマを必要とするものにはそれを与えるオプションを可能としました。
「高可用」という用語は普通は、システムの集まりを、個々のシステムに比べてより高信頼にして障害をマスクする能力を示します。フォールトトレランスはとても望ましいゴールですが、特有の落とし穴もあります。それはしばしば、永続的な元となる問題を隠します。私達のグループにはことわざがあります。「フォールトトレランスはフォールトマスキングである」あまりにしばしば、元となる障害を追跡することへの警戒が不十分であることと、私達のシステムが頑強であることが結びついた結果、予期しない問題が起きることがありました。永続的な修正不可能な問題の上に見えてくる小さな一時的なエラーが、ずっと大きな問題を起こすことがありました。
もう一つの問題はフロー制御です。問題のある参加者を許容するアルゴリズムは、遅いものに対して不注意です。理想的には、個別のマシンの集合は最も能力の低いものの速度でしか進めません。もし遅いことが障害であるとして解釈され、許容された場合、最高速の過半数のマシンは自分自身のペースで要求を処理しますが、遅い人がキャッチアップしようとして努力する負荷のところで平衡状態に達して遅くなります。この異常を、連鎖ギャングスロットリングと呼びます。これは、逃げる犯罪者のグループが、落伍者をひきずる速度でしか進めないというイメージを引き起こします。
Megastore のライトアヘッドログの利点は、外部システムを統合するのが簡単だということです。べき等の操作ならどれでも、ログエントリを適用する中のステップの一つに入れることができます。
より複雑な問い合わせに対する良い性能を達成するためには、Bigtable 内の物理的データ配置に注意する必要があります。問い合わせが遅い時、開発者は Bigtable のトレースを調べて、なぜその問い合わせが期待よりも遅いのかを理解する必要があります。Megastore はブロック長、圧縮、テーブル分割、局所グループ、そして Bigtable が提供する他のチューニング制御に対して、特別のポリシーを強制することはありません。その代わりに私達はこれらの制御を公開し、アプリケーション開発者に性能を最適化する能力（と負担）を提供します。
６． 関連する研究
最近、大きなウェブアプリケーションの要求を満たすために、NoSQL データストレージに対する興味は増加しています。代表的な研究には、Bigtable [15], Cassandra [6], そして Yahoo PNUTS [16] があります。これらのシステムでは、スケーラビリティは伝統的 RDBMS システムの一つ以上の性質を犠牲にすることで達成されます。例えば、トランザクション、スキーマサポート、問い合わせ能力[12, 33]。これらのシステムは、しばしば、トランザクションのスコープを、単一キーアクセスの粒度に減らします。その結果、アプリケーションを作る負荷を大きく増します[18, 32]。システムによっては、トランザクションのスコープを、一つのテーブル内の複数の行に拡張します。例えば、Amazon SimpleDB [5] は、ドメインという概念をトランザクションの単位として使います。しかし、それらの努力はまだ限られたものです。トランザクションは複数テーブルをまたがることはできず、任意にスケールすることもできないからです。さらに、多くの現在のスケーラブルなデータストレージは RDBMS の豊富なデータモデルを持ちません。それは開発者に負担を増やします。データベースとスケーラブルなデータストアの両方の利点を組み合わせて、Megastore はトランザクショナルな ACID 保証をエンティティグループ内で提供し、利用者定義のスキーマや、データベーススタイルでフルテキストのインデックス、そしてキューを持つ柔軟なデータモデルを提供します。
地理的に分散したデータセンタをまたがったデータ複製は最先端のストレージシステムにとって可用性を改善するための不可欠の方法です。最もよくあるデータストレージシステムは弱い一貫性モデルを使う非同期の複製スキームを使います。例えば、Cassandra [6], HBase [1], CouchDB [7], そして Dynamo [19] は結果整合性モデルを使い、PNUTS は “timeline”一貫性 [16] を使います。それに対して、同期複製は強いトランザクショナルなセマンティクスを、ワイド・エリア・ネットワークをまたがって保証し、current read の性能を改善します。
伝統的な RDBMS に対する同期複製は性能上の挑戦をもたらし、スケールするのは困難です[21]。提案された、いくつかの回避策は、非同期複製を使って強一貫性を可能とします。一つのアプローチは、更新が、その効果が複製される前に完了するのを許します。その更新状態を読む必要のあるトランザクションに、同期に必要な遅延を渡します[26]。他のアプローチは、ライトを一つのマスターにルーティングします。そして、リードオンリーのトランザクションは複製のセットに分散します[29]。更新は非同期に残りの複製に伝搬します。そして、リードは遅延されるかそれとも、すでに同期をした複製に送られます。効率液な同期複製についての最近の提案は、オーダリングのプリプロセッサを導入します。それが、入力トランザクションを決定論的にスケジュールして、複数の複製に対して独立に適用しても同じ結果が得られるようにします[31]。同期の負担はプリプロセッサにシフトされましたが、それ自身もスケーラブルに作られなくてはいけません。
最近まで、Paxos を同期複製を達成するために使う例は少なかったです。SCALARIS は、Paxos コミットプロトコル[22]を使って分散ハッシュテーブルの複製を実装した一つの例です。[30] Keyspace [2] も、 Paxos を使って汎用のキーバリューストアにおける複製を実装します。しかし、これらのシステムのスケーラビリティと性能は公開されていません。Megastore はたぶん、データセンタをまたがる Paxos をベースとする複製を実装した、最初の大規模ストレージシステムです。そしてそれは、クラウドのスケーラブルなウェブアプリケーションのスケーラビリティと性能要件を満足します。
慣用的なデータベースシステムは成熟し、洗練されたデータ管理機能を提供します。しかし、この論文[33]がターゲットとするような大規模対話的サービスを提供することは困難です。MySQL [10] のようなオープンソースデータベースシステムは、私達が要求するレベルまでにはスケールしません。また、Oracle [4] のような高価な商用データベースシステムは、クラウドでの大規模な配備のための所有の総コストを大いに増します。さらに、それらのどれも、フォールトトレラントな同期複製機構[3, 11]を提供しません。それは、クラウドでの対話的サービスを構築するための鍵となる部品です。
７．結論
この論文で私達は、Megastore を紹介しました。それは、スケーラブルで高可用なデータストアであり、対話的インターネットサービスのストレージ要件を満たすために設計されました。私達は Paxos を使って同期のワイド・エリア複製をします。それは、それぞれの操作の、軽量で高速なフェールオーバーを提供します。ワイドに分散された複製をまたがる、同期複製の遅延ペナルティは、単一システムイメージの便利さとキャリアグレードの可用性の運用上の利点によって十分におつりが来ます。私達は Bigtable をスケーラブルなデータストアとして使います。同時に、ACID トランザクション、インデックス、そしてキューのような豊富なプリミティブを加えます。データベースをエンティティグループというサブデータベースに分割することは、ほとんどの操作に対して親しみのあるトランザクション機能を提供し、同時にストレージのスケーラビリティとスループットを可能とします。
Megastore は、内部と外部の利用者に使われる、１００以上の本番アプリケーションを持ちます。そして、より高レベルのインフラストラクチャを提供します。これらアプリケーションの数と広がりは、Megastore の使いやすさ、汎用性、そしてパワーの証拠です。私達は、Megastore が、今日のスケーラブルなストレージシステムにとって、機能セットと複製一貫性において、中間位置の実現可能性をデモンストレートできたことを希望します。
８．謝辞
省略。原文を参照下さい。
９．参考文献
省略。
以上