Cloud Spanner: TrueTime と外部整合性

Cloud Spanner にとっての TrueTime のメリット

TrueTime は、すべての Google サーバーのアプリケーションに提供される可用性の高い分散クロックです1。TrueTime により、アプリケーションは単調に増加するタイムスタンプを生成できます。タイムスタンプ T が生成される前にタイムスタンプ T' が生成された場合、アプリケーションは T' より大きいことが保証された T を使って計算できます。この保証は、すべてのサーバーとすべてのタイムスタンプにわたって保持されます。

TrueTime のこの機能は、Cloud Spanner でトランザクションにタイムスタンプを割り当てるために使用されます。具体的には、トランザクションが発生したと Cloud Spanner がみなす瞬間を反映するタイムスタンプが、すべてのトランザクションに割り当てられます。Cloud Spanner は複数バージョンの同時実行制御を使用するので、タイムスタンプの順序保証により、Cloud Spanner のクライアントは書き込みをブロックすることなく、データベース全体で(複数の Cloud リージョンにわたる場合でも)整合性のある読み取りを実行できます。

外部整合性

Cloud Spanner は、トランザクションに対する最も厳格な同時実行制御をクライアントに保証します。これは外部整合性と呼ばれます2。外部整合性のある環境では、Cloud Spanner が実際にはパフォーマンスや可用性の向上のために複数のサーバー(場合によっては複数のデータセンター)でトランザクションを実行している場合でも、すべてのトランザクションが順次実行されるかのようにシステムが動作します。さらに、1 つのトランザクションが完了してから別のトランザクションの commit が開始する場合、クライアントは、最初のトランザクションの効果が反映されないまま 2 番目のトランザクションの効果が反映されるという状態に遭遇することはありません。直感的には、Cloud Spanner はセマンティック的に単一マシンのデータベースと区別されません。Cloud Spanner ではこのような強力な保証が提供されながらも、アプリケーションは(高パフォーマンスと引き換えに保証の弱い)データベースに匹敵するパフォーマンスを実現できます。たとえば Cloud Spanner では、スナップショット分離をサポートするデータベースと同様に、読み取り専用トランザクションによってブロックされることなく書き込みを実行できますが、スナップショット分離で許容される異常が発生しません。

アプリケーション開発は、外部整合性により大幅に簡素化されます。たとえば、Cloud Spanner で銀行アプリケーションを作成し、ある顧客の当座預金口座と貯蓄口座にそれぞれ $50 が最初に存在するとします。その後、アプリケーションが開始するワークフローで、最初に貯蓄口座に $200 を預け入れるトランザクション T1 が commit され、次に当座預金口座から $150 を引き落とす 2 番目のトランザクション T2 が発行されます。さらに、1 日の終わりに一方の口座の残高がマイナスである場合は、もう一方の口座からそのマイナスが自動的に充当され、その日のいずれかの時点で全口座の合計残高がマイナスとなった場合は、お客様にペナルティが発生するとします。T2 の commit は T1 が完了した後に開始されるため、外部整合性によって、データベースのすべての読み取りで必ず、預け入れ T1 が引き落とし T2 より前に発生したことが認識されます。言い換えると、外部整合性により、T2 が T1 より前に発生したと認識する読み取りは存在しないことが保証されます。つまり、引き落としにより、資金不足が原因でペナルティが発生することはありません。

厳密な 2 フェーズロックを使用する従来のデータベースは、外部整合性を提供します。残念ながら、このようなシステムでは、アプリケーションが最新のデータを読み取ろうとするたびに(「強力な読み取り」と呼ばれる)、システムがデータに読み取りロックを適用するため、読み取り中のデータへの書き込みがブロックされます。

タイムスタンプとマルチバージョン同時実行制御(MVCC)

Cloud Spanner やその他多くのデータベース システムでは、書き込みをブロックせずに読み取りを行う目的で、不変なデータ バージョンを複数保持しています(多くの場合、これはマルチバージョン同時実行制御と呼ばれます)。書き込みにより、書き込みトランザクションのタイムスタンプを持つ新しい不変バージョンが作成されます。あるタイムスタンプ時点での「スナップショット読み取り」では、そのタイムスタンプより前の最新バージョンの値が返されるので、書き込みをブロックする必要がありません。したがって、バージョンに割り当てられるタイムスタンプは、トランザクションの commit が認識される順序と整合することが重要です。このプロパティを「正しいタイムスタンプ」と呼びます。正しいタイムスタンプが存在することは、外部整合性と同等であることに注目してください。

正しいタイムスタンプが重要である理由を確かめるため、前のセクションの銀行取引の例を考えてみましょう。正しいタイムスタンプが生成されない場合、T1 に割り当てられるタイムスタンプより前のタイムスタンプが T2 に割り当てられる可能性があります(たとえば、架空のシステムで TrueTime ではなくローカル クロックが使用され、T2 を処理するサーバーのクロックがわずかに遅れている場合に、これが発生する可能性があります)。引き落としが開始される前にお客様が預け入れの完了を確認した場合でも、スナップショット読み取りには、預け入れ T1 ではなく引き落とし T2 が反映されることがあります。

正しいタイムスタンプは、単一マシンのデータベースでは簡単に実現できます(たとえば、単調に増加するグローバルな 1 つのカウンタからタイムスタンプを割り当てるだけです)。これを、世界各地のサーバーでタイムスタンプを割り当てる必要がある Cloud Spanner などの広範な分散システムで実現しようとすると、効率的に行うことははるかに困難になります。

Cloud Spanner は、単調に増加するタイムスタンプを生成する TrueTime に依存します。Cloud Spanner は、これらのタイムスタンプを 2 つの方法で使用します。まず、グローバル通信の不要な書き込みトランザクション用の正しいタイムスタンプとして使用します。2 番目に、強力な読み取り用のタイムスタンプとして使用します。これにより、強力な読み取りが複数のサーバーにまたがる場合でも、1 回の通信で強力な読み取りを実行できます。

よくある質問

Cloud Spanner はどのような整合性保証を提供しますか?

Cloud Spanner は、トランザクション処理システム用の最も厳密な整合性プロパティである外部整合性を提供します。Cloud Spanner のすべてのトランザクションは、パーティション内のプロパティだけでなく、この外部整合性プロパティを満たします。外部整合性により、Cloud Spanner でのトランザクション実行方法は、トランザクションが順次実行されるシステムと区別されません。また、トランザクションの commit が認識される順序は、順次実行順序と整合します。トランザクション用に生成されるタイムスタンプは、順次実行の順序と対応するため、別のトランザクション T1 の完了後にトランザクション T2 の commit が開始したことがクライアントで認識された場合、システムは T1 のタイムスタンプより大きいタイムスタンプを T2 に割り当てます。

Cloud Spanner は線形化可能性を提供しますか?

はい。実際には、線形化可能性はトランザクションの動作に影響しないため、Cloud Spanner は線形化可能性より強力なプロパティである外部整合性を提供します。線形化可能性は、アトミック読み取りまたは書き込みオペレーションをサポートする同時実行オブジェクトのプロパティです。データベースにおいて「オブジェクト」とは通常単一の行であり、場合によっては単一のセルのこともあります。外部整合性は、任意のオブジェクトに対する複数の読み取りまたは書き込みオペレーションを含むトランザクションをクライアントが動的に合成する、トランザクション処理システムのプロパティです。線形化可能性は、単一オブジェクトに対する単一の読み取りまたは書き込みオペレーションのみがトランザクションに含まれる、外部整合性の特殊なケースとみなすことができます。

Cloud Spanner は直列化可能性を提供しますか?

はい。Cloud Spanner は実際には、直列化可能性より厳密なプロパティである外部整合性を提供します。トランザクション処理システムは、トランザクションを順次実行するシステムと区別されない方法でトランザクションを実行する場合、直列化可能となります。さらに Cloud Spanner では、順次実行の順序と、トランザクションの commit が認識される順序とが必ず整合します。

前述の銀行の例をもう一度見てみましょう。直列化可能性はあっても外部整合性がないシステムでは、お客様が T1 を実行した後で T2 を実行した場合でも、システムがそれらの順序を変更できるため、引き落としによる資金不足が原因のペナルティが発生する可能性があります。

Cloud Spanner は強整合性を提供しますか?

はい。Cloud Spanner は実際には、強整合性よりさらに強いプロパティである外部整合性を提供します。Cloud Spanner のデフォルトの読み取りモードは「強力」です。これにより、どのレプリカが読み取りを受け取るかに関係なく、オペレーションの開始前に commit されたすべてのトランザクションが必ず反映されます。

強整合性と外部整合性の違いは何ですか?

レプリケートされたオブジェクトが線形化可能である場合、レプリケーション プロトコルは「強整合性」を示します。線形化可能性と同様に、「強整合性」はトランザクションの動作に何の影響も与えないため、「外部整合性」より弱いプロパティです。

Cloud Spanner は結果整合性(または遅延整合性)を提供しますか?

Cloud Spanner は、結果整合性よりはるかに強力なプロパティである外部整合性を提供します。結果整合性では、高パフォーマンスと引き換えに保証が弱くなります。結果整合性の問題点として、読み取りの結果データベースが実際の状態とは異なる状態だと認識される可能性があります(たとえば、トランザクション A がトランザクション B より前に発生した場合でも、読み取りによって B は commit 済み、A は未 commit と認識される可能性があります)。Cloud Spanner が提供するステイル読み取りでは、結果整合性と同等の高いパフォーマンスを実現でき、しかもはるかに強い整合性保証が得られます。ステイル読み取りは、「古い」タイムスタンプからデータを返します。古いバージョンのデータは不変であるため、これによって書き込みがブロックされることはありません。

その他の資料

  • 1J. C. Corbett、J. Dean、M. Epstein、A. Fikes、C. Frost、J. Furman、S. Ghemawat、A. Gubarev、C. Heiser、P. Hochschild、W. Hsieh、S. Kanthak、E. Kogan、H. Li、A. Lloyd、S. Melnik、D. Mwaura、D. Nagle、S. Quinlan、R. Rao、L. Rolig、Y. Saito、M. Szymaniak、C. Taylor、R. Wang、D. Woodford「Spanner: Google's Globally-Distributed Database」。2012 年 10 月にカリフォルニア州ハリウッドで開催された第 10 回オペレーティング システム設計と実装に関する USENIX シンポジウム(OSDI 12)、pp. 261-264。
  • 2Gifford、D. K.「Information Storage in a Decentralized Computer System」1981 年発行、スタンフォード大学博士論文。
  • このページは役立ちましたか?評価をお願いいたします。

    フィードバックを送信...

    Cloud Spanner のドキュメント