Spanner の仕組み: 厳格な直列化可能性と外部整合性について理解する
Google Cloud Japan Team
※この投稿は米国時間 2023 年 4 月 8 日に、Google Cloud blog に投稿されたものの抄訳です。
データベース システムに関して重要な考慮事項となるのは、そのシステムで確保される分離と整合性のレベルです。分離レベルとは、データベースでどこまで他の同時実行トランザクションがないかのようにトランザクションを実行できるかを意味します。整合性レベルとは、データベースの状態に表れる変化がどの程度不変条件を維持していて、因果関係を反映するのかを意味します。このブログ投稿では、分離レベルと整合性レベルについて記述する 2 つの関連用語として、「厳格な直列化可能性」と「外部整合性」 の意味を解説します。これらの特性を保証するシステムは、完全な分離と整合性が備わっていると言われます。そのようなシステムの一つが、Spanner です。パフォーマンスを犠牲にすることなく、厳格な直列化可能性と外部整合性を確保するために Spanner で採用されている独特のアプローチについて説明します。
トランザクションと整合性
一連の読み取り / 書き込み操作によってデータベースを操作するトランザクションは、「commit」または「ロールバック(中止)」で終了します。トランザクションが commit で終了した場合は、その結果が維持(永続化)される一方、ロールバックで終了した場合はデータベースのコンテンツに対する影響はまったくありません。
トランザクションで重要となる一つの要件は「整合性」です。つまり、トランザクションは、データベースの不変条件(インデックスの更新、制約、カスケードなど)とアプリケーション レベルの不変条件(たとえば、ある口座から別の口座に送金するときに、お金が失われないようにするなど)を維持するようにデータに変更を加えるものでなければなりません。さらに、因果関係も維持する必要があります。つまり、トランザクション B にトランザクション A に依存した因果関係がある場合、トランザクション B による影響が見られたら、トランザクション A による影響もあるはずだということを意味します。アプリケーション レベルの不変条件を維持する責任はトランザクションの作成者にありますが、その他すべての責任はデータベース システムにあります。
正しい形式のトランザクションは、データベースをある状態から別の状態に変換します。整合状態で開始したデータベースに対して正しい形式のトランザクションをシリアル実行すると、そのデータベースは別の整合状態になります。トランザクションのシリアル実行によって整合性は維持されるとはいえ、最適なパフォーマンスを得られない場合があります。たとえば、互いに素なデータセットを操作する 2 つのトランザクションを安全に並行実行できる状況であれば、トランザクションのスループットが向上します。けれども、同時実行トランザクションによる操作が正しい順序でスケジュールされていないと、問題が発生する可能性があります。一例として、それぞれ account1 から account2 に 100 ドルを送金するトランザクション a と b の 2 つが交互に実行される場合を考えてみましょう。
上記の順序で実行すると、account1 から 200 ドルが引き落とされますが、account2 には 100 ドルしか振り込まれません。
直列化可能性
直列化可能性理論という数学的ツールを使用すると、トランザクションの同時実行において分離の原則を守れるかどうかを証明できます。同時に実行される 2 つのトランザクションによる読み取り / 書き込み操作を任意の順序で実行しても、トランザクションの結果には影響がない場合もあります。そのような状況であれば、トランザクション スケジューラで、ある程度柔軟に同時実行トランザクションをスケジュールできます。一連のトランザクションの同時実行が、それらのトランザクションをシリアル実行する場合と同等であれば「直列化可能」であると見なされます。トランザクションにバグがないという前提で、直列化可能なトランザクションは、データベースがある整合状態から別の整合状態に変換されることを保証します(前のセクションのスケジュールの例は直列化可能ではありません)。直列化可能性理論では、同時実行トランザクションのスケジュールに必要な次の特性を導入しています。これらの特性により、トランザクションの操作をスケジュールする順序に対する制限事項が追加されます。
復元可能(RC)。トランザクションの同時実行を復元可能にするために、トランザクション A で書き込まれた x をトランザクション B が読み取るときは、常に B による読み取りの前に A が commit される必要があります。たとえば、A によって書き込まれたなんらかの値を B が読み取り、B がその値を使って計算し、その結果として新しい値を書き込むとします。B が commit された後、A が commit される前にシステムがクラッシュしたとすると、B によって書き込まれた値は復元されますが、A の影響はなくなってしまいます(A は commit されていないため)。したがって、B によって書き込まれて復元された値は無効になります。
ロールバックのカスケードの回避(ACR)。トランザクションの同時実行でロールバックのカスケードが回避されるよう、トランザクション A で書き込まれた x をトランザクション B が読み取るときは、常に B による読み取りの前に A が commit される必要があります。その理由は、A で書き込まれた x を B が読み取った後、A がロールバックされたとしたら、B が読み取った x の値が無効となり、B もロールバックしなければならなくなるためです。
厳格(ST)。トランザクションの同時実行を厳格に直列化可能にするために、トランザクション A で書き込まれた x をトランザクション B が読み取る場合、または書き込む場合は、常に B による読み取り / 書き込みの前にトランザクション A が commit またはロールバックされる必要があります。この特性により、2 つのトランザクションが同じデータ項目 x に書き込む場合、x に書き込まれる値は、最後に commit されたトランザクションによって書き込まれた値であるという保証がさらに強化されます。
一連のトランザクションがある場合、上記の各スケジューラの特性により、交互に実行可能なすべてのトランザクション操作のサブセットが定義され、直列化可能性の厳格さが増していきます(つまり、ST ⊂ ACR ⊂ RC)。Spanner のトランザクション スケジュールは、最高レベルの分離である ST(厳格な直列化可能性)に準拠しています。
Spanner は、マルチバージョン同時実行制御(MVCC)という手法を使用してデータの更新を処理します。この手法では、列の値が更新されても元の値は上書きされません。代わりにタイムスタンプが付けられた新しいバージョンの値がデータベースに追加されます。したがって、過去の特定のタイムスタンプが付けられた値を読み取るようにトランザクションに指示することで、データベースの過去のスナップショットにアクセスできます。古いバージョンが累積されてストレージが過剰に消費されないようにするために、Spanner ではバージョンの保持期間が定義されています(最大 7 日まで構成可能)。保持期間より古くなったバージョンは、自動的にデータベースから削除されます。
外部整合性
外部整合性という用語は、厳格な直列化可能性と若干似ています。外部整合性は分散型ストレージ システムのより困難なケースに関係することから、厳格な直列化可能性と同様の特性を記述するために導入されました。この用語によって導入される、複数のトランザクション全体での実行順序は、トランザクションが完了する実際の時間順(実時間の順)によって定義されます。外部整合性を確保するには、各トランザクションが、そのトランザクションの前に commit されたすべてのトランザクションの影響を考慮し、以降に commit されるトランザクションの影響を受けないようにする必要があります。Spanner は外部整合性を確保するために、トランザクションの commit タイムスタンプを使用します。実質的に、トランザクションでのすべての読み取り / 書き込み操作は、そのトランザクション実行中の特定の実時間を表す commit タイムスタンプの時点で行われます。各トランザクションは、そのトランザクションより前の commit タイムスタンプが付けられたすべてのトランザクションの影響を考慮し、以降の commit タイムスタンプが付けられたどのトランザクションの影響も受けません。より具体的に説明すると、Spanner では外部整合性を次のようにして保証します。
たとえば、T1 と T2 という(どちらも書き込み操作を含む)2 つのトランザクションがあるとします。トランザクション T1 による Commit() 呼び出しの結果が返された後に、トランザクション T2 で Commit() を呼び出す場合、T2 の commit タイムスタンプの値は T1 の commit タイムスタンプの値より大きくなります。
この整合性の保証は、時間的に重複するトランザクションの順序についてはまったく言及していませんが、実際的な目的には「完璧」と見なされています。直列化可能性理論の視点から見ると、外部整合性を備えたトランザクションは直列化可能であり、復元も可能です。ただし、必ずしもその逆が当てはまるとは限りません。一例として、次の操作順序を考えてみましょう。
A write(x) → B write(x) → B commit → A commit
この順序は、直列化可能であり(「A の後に続いて B」に相当するため)、復元も可能ですが(読み取りは関与しないため)、A は B よりも前に x の値を書き込みますが、commit されるのは B の後であるため、この順序では外部整合性を確保できません。外部整合性を備えたトランザクションには、「ロールバックのカスケードの回避」と「厳格」の特性は不要です。一例として、次の操作順序を考えてみましょう。
A write(x) → B write(x) → A commit → B commit
この順序では外部整合性が確保されますが(「A の後に続いて B」に相当し、commit の順序と一致するため)、厳格な直列化可能ではありません。A が x の値を書き込んだ後、commit される前に B が x の値を書き込むためです。以上の追加の特性は定義には含まれていませんが、データベース システムが commit されていないデータの読み取りや上書きを許可せず、外部整合性を確保している場合は、自動的に厳格な直列化可能性が保証されることになります。
Spanner のような分散型データベース システムで厳格な直列化可能性と外部整合性を実現するのは簡単なことではありません。Spanner インスタンスは数千台のマシンで実行される可能性があるからです。トランザクションの高スループットを実現するために、Spanner はデータを互いに素なグループに分割し、それぞれ固有のトランザクション スケジューラを使用して、各グループに固有のローカル クロックに基づくタイムスタンプを生成します。
たとえば、t1 と t2 という 2 つのトランザクションの間に因果関係(t1 → t2)があるとします。これらのトランザクションが操作するデータのセットに重複する部分がある場合、これらのトランザクションは少なくとも 1 つの共通のトランザクション スケジューラを共有します。スケジューラがこれらのトランザクションを到着順にスケジュールして、厳格な直列化可能性を確保する手法(2 フェーズロックなど)を使用する限り、両方のトランザクションに、因果関係を反映する commit タイムスタンプが割り当てられ(t1 commit_ts < t2 commit_ts)、整合性が保証されます。Spanner のトランザクション スケジューラは、このように機能します。
次は、トランザクション t1 と t2 が互いに素なデータセットを操作する場合を考えてみましょう。t2 が間接的に t1 の結果を「学習」し、その知識に基づいて値を計算して書き込むとしたら、t2 には t1 に依存した因果関係があることになります。ただし、これらのトランザクションが直接操作するデータは重複していないため、共通のトランザクション スケジューラを共有しない場合があります。問題が難しくなってくるのは、ここからです。たとえば、マシン A がトランザクション t1 を実行した直後にマシン B がトランザクション t2 を実行する場合を考えてみてください。マシン B 上のクロックがマシン A のクロックよりも遅れている場合、図 1 に示す整合性の問題が発生しかねません。


トランザクションが commit される時間順が、実際の時間順の逆になってしまいます。t1 の commit タイムスタンプ t:1000 が付けられているデータベースのスナップショットを取得しようとすると、実際には t1 の後に行われたトランザクション t2 が含まれるスナップショットが渡されることになります。一方、t:995 の時点でのデータベースのスナップショットを取得しようとすると、スナップショットにはトランザクション t2 が含まれ、t1 は含まれないことになります。
Spanner には、パフォーマンスを犠牲にすることなく厳格な直列化可能性と外部整合性を確保するために連動する 2 つのコンポーネントがあります。Paxos と TrueTime です。
Paxos
Spanner は、Paxos コンセンサス アルゴリズムを使用した同期レプリケーションによって高可用性を実現しています。言い換えると、Spanner データベースに書き込まれるすべてのデータは複数の(地理的に分散された)場所で複製されます。そのため、レプリカのうちのいくつかで障害が発生したとしても、Spanner 内のデータを使用できます。Paxos は書き込みを処理するために、すべてのレプリカに書き込み操作の提案を送信するリーダーを選出します。レプリカの大多数が書き込み操作の提案を受け入れると、その書き込み操作は承認されたと見なされて、処理を続行できるようになります。これにより、書き込みスループットを最大化できるとともに、レプリカで障害が発生しても書き込み操作を続行できます。前述のとおり、Spanner インスタンスは複数の互いに素なグループに分割されます。これらのグループはそれぞれに独立した Paxos プロトコル エンジンでグループ内のデータを複製することから、「Paxos グループ」と呼ばれます。
TrueTime
TrueTime は、Google が開発したクロック同期システムです。このシステムが提供する時刻 API に、クロックの不確実性の概念が表れています。メソッド TT.now() はタイムスタンプのペア [earliest, latest] を返し、TT.now() が呼び出された絶対時間(Google の高精度の時刻基準に従った時間、以下で詳述)が 2 つのタイムスタンプの間に収まっていることを保証します。バックエンドの Spanner サーバーはこのライブラリを使用して、commit タイムスタンプと、そのタイムスタンプに関する理由(タイムスタンプが確実に過去のものであるかどうかを判断するためなど)を生成します。
TrueTime の主なコンポーネントは、「時刻サーバー」という、高精度の時刻基準を提供する特殊なマシンです。この実現には、専用のアンテナとともに搭載された GPS クロックか、原子時計が使用されます(クロックタイプによって異なる障害モードが使用されます)。Spanner サービスを運用している各データセンターでは、複数の時刻サーバーが実行されています。各 Spanner サーバーマシンで実行されている「時刻デーモン」が、時刻サーバーと定期的に通信してマシンのローカル クロックを同期します。この記事を書いている時点で、TrueTime によって実現される Spanner サーバーのクロック不確実性は、99 パーセンタイルで 1 ミリ秒未満です。
連携の仕組み
次は、因果関係を持つトランザクションが同じデータセットを直接参照していない場合(また、異なるトランザクション スケジューラによってスケジュールされる場合)、Spanner が Paxos と TrueTime を使用して外部整合性を確保する仕組みを説明します。Paxos グループがトランザクションに関連付けられた書き込み操作を処理する際に、Paxos リーダーは次のステップを行います。
commit タイムスタンプを選択(commit_ts := TT.now().latest)
Paxos 書き込み提案を送信し、クォーラムを待機
commit wait を実行(TT.now().earliest > commit_ts を待機)
Paxos commit メッセージをレプリカに送信(書き込みがログに記録され、適用される)
ロックを解放
クライアントに通知
ここで注目すべき重要なステップは 3(commit wait)です。このステップにより、commit タイムスタンプが過去のものになるまで、クライアントがトランザクションの影響を認識しないことが保証されます。これが示唆するのは、書き込みトランザクション t2 が書き込みトランザクション t1 の結果に依存する場合(因果関係)、t2 の commit タイムスタンプの値が t1 の commit タイムスタンプの値より大きくなることが保証されるということです。また、ステップ 1 で commit タイムスタンプを選択し、ステップ 3 で待機することにも注目してください。つまり事実上、Paxos 提案を送信してクォーラムを待機するのと並行して、タイムスタンプを待機します。TrueTime とその最小限のクロック不確実性のおかげで、ほとんどの場合、Spanner の commit wait ステップに待機時間が伴うことはありません。複数の Paxos グループにまたがるトランザクションとなると事態は少し複雑になりますが、最終的な効果は同じです。
以上が、Spanner が外部整合性を保証する仕組みです。トランザクションでどのタイムスタンプを使用してデータベースを読み取るかにかかわらず、トランザクションではその時点で完全に整合した状態のデータベースを操作できます。複数の独立したアクターがデータベースを操作するとしても、完全な整合性を実現するために因果関係のあるイベントが適切に順序付けられるようにアクター間で調整を取る必要はありません。Spanner は 2 フェーズロックと commit wait を使用して、完全な分離も保証します。しかも、TrueTime の力によって、クロックの不確実性から発生する待機が理由で Spanner のパフォーマンスが大きく影響されるシナリオは実質的に一つもありません。
まとめ
以上の説明で、厳格な直列化可能性と外部整合性という、Spanner の分離と整合性の保証について記述する 2 つの用語について理解を深めていただけたことを願います。Spanner は、Gmail と YouTube をはじめとする世界最大規模のアプリケーションの数々で活用されています。また、Spanner ではアプリケーションの需要に応じてリソースのプロビジョニングをスケールできるため、初めは小規模でも急速な成長が見込まれるアプリケーションで使用するデータベース サービスとして適しています。Spanner に興味を持ち、試してみたいと思った方は、ぜひ 90 日間無料トライアルをご利用ください。


