スパナー: Googleのグローバル分散データベース

分布式システム翻訳シリーズの最後の記事、原文 https://research.google.com/archive/spanner-osdi2012.pdf

現在、Google Cloud は Cloud Spanner をサポートしており、製品のドキュメントでその機能の詳細を確認できます。

翻訳が非常に悪く、多くの文が英語の語順を保持しているため、中国語で読むのが非常に難しいです。今後は全文翻訳を行わない方が良いかもしれません。

やはり言語能力がひどい、英語でも中国語でも。😢

はじめに#

Spanner は、Google が設計、構築、展開したスケーラブルで、グローバルに分散したデータベースです。最も高い抽象レベルでは、これはデータを世界中のデータセンターに分散した多くの Paxos 状態機械にシャーディングするデータベースです。レプリカは、グローバルな可用性と地理的な局所性を実現するために使用され、クライアントはレプリカ間で自動的にフェイルオーバーを行います。データ量やサーバー数が変化するにつれて、Spanner は自動的にマシン間で再シャーディングを行います。また、Spanner はデータセンターを跨いでマシン間でデータを自動的に移動させ、負荷をバランスさせ、障害を処理します。Spanner は、数百のデータセンター、数百万台のマシン、兆行のデータを跨いでスケールするように設計されています。アプリケーションは、同じ大陸内、あるいは大陸を跨いでレプリケーションを行うことで、高可用性を実現できます。

私たちの最初の顧客は F1: Google 広告のバックエンドの書き換えです。F1 は、全米に分散した 5 つのレプリカを使用しています。他のほとんどのアプリケーションは、同じ地理的地域内の 3〜5 のデータセンター間でデータをレプリケートし、比較的独立した障害モードを持つ可能性があります。つまり、ほとんどのアプリケーションは、障害が発生した場合に 1〜2 のデータセンターが生き残っていれば、低遅延を選択する可能性があります。Spanner が主に注力しているのは、データセンター間のレプリカデータの管理ですが、分散システムインフラストラクチャの上に重要なデータベース機能を設計し、実装するために多くの時間を費やしました。

多くのプロジェクトが Bigtable を使用することを喜んでいる一方で、私たちは Bigtable が特定のタイプのアプリケーションで使用するのが難しいというユーザーからの苦情を受け続けてきました。たとえば、複雑で変更が容易なスキーマを持つアプリケーションや、複数の地域でレプリケーションを行う場合に強い一貫性を実現したいアプリケーションです。

Google の多くのアプリケーションは、意味的な関係モデルと同期レプリケーション操作のサポートのために Megastore を使用することを選択しましたが、書き込み帯域幅は比較的低いです。コンセンサスとして、Spanner は Bigtable に似たバージョン付きのキー・バリュー・ストレージから一時的なマルチバージョンデータベースに進化しました。データはスキーマ付きの半関係型テーブルに保存され、データにはバージョンがあり、各バージョンは自動的にコミット時のタイムスタンプが付与されます。古いデータは構成可能なガベージコレクションポリシーに従い、アプリケーションは古いタイムスタンプのデータを読み取ることができます。Spanner は一般的なトランザクションをサポートし、SQL ベースのクエリ言語を提供します。グローバルに分散したデータベースとして、Spanner は多くの興味深い機能をサポートしています。まず、アプリケーションは非常に細かい粒度でデータレプリカを動的に制御および構成でき、アプリケーションは次の制限を指定して制御できます：どのデータセンターにどのデータが含まれるか、データがユーザーからどれだけ離れているか（読み取り遅延を制御するため）、各レプリカ間の距離がどれだけあるか（書き込み遅延を制御するため）、いくつのレプリカを維持するか（データの永続性、可用性、読み取り性能を制御するため）。データは動的かつ透明にデータセンター間で移動でき、システムはデータセンター間のリソース使用をバランスさせます。次に、Spanner には分散データベースで実現が難しい 2 つの機能があります：外部一貫性のある読み取りと書き込みを提供し、同じタイムスタンプでのグローバルな読み取り一貫性をサポートします。これらの機能により、Spanner はグローバルスケールで一貫性のあるバックアップ、一貫性のある MapReduce 実行、および原子的なスキーマ更新をサポートし、実行中のトランザクションがある場合でも保証されます。

これらの機能が実現できる理由は、Spanner がトランザクションにグローバルに意味のあるコミットタイムスタンプを付与できるという事実に基づいています。たとえトランザクションが分散していても、このタイムスタンプはトランザクションの直列化順序を反映できます。さらに、直列化順序は外部一貫性に適応します（または線形一貫性に等しいと言えます）。もしトランザクション $T_{1}$ が別のトランザクション $T_{2}$ が始まる前にコミットされた場合、 $T_{1}$ のコミットタイムスタンプは $T_{2}$ よりも小さくなります。Spanner は、グローバルスケールでこの保証を提供する最初のシステムです。

このような機能を提供するための重要なサポートは、新しい TrueTime API とその実装です。この API は、時計の不確実性を直接反映しています。Spanner のタイムスタンプが直列化順序を保証することは、TrueTime の実装が提供する範囲の限界に依存しています（注：時計は不確実であるため、TrueTime の実装は固定の瞬間ではなく範囲を提供します）。不確実性が大きい場合、Spanner は不確実性を排除するために速度を落とします。Google のクラスター管理ソフトウェアは TrueTime API の実装を提供します。この実装は、さまざまな現代の時計ソース（GPS と原子時計）を通じて不確実性を十分に小さく（通常は 10ms 未満）保証します。

実装#

このセクションでは、まず Spanner の構造と実装の基本原理を説明し、次にレプリカと局所性を管理するためのディレクトリアブストラクションを説明します。これはデータ移動の基本単位でもあります。最後に、私たちのデータモデル、なぜ Spanner がキー・バリュー・ストレージではなく関係型データベースに似ているのか、そしてアプリケーションがデータの局所性をどのように制御できるかを説明します。

Spanner のデプロイメントは universe と呼ばれ、Spanner がグローバルなデータを直接管理できるため、実行される universe の数は非常に少ないです。現在、私たちは test/playground universe、development/production universe、production universe を運用しています。Spanner は一連の zones で構成されており、各 zone はおおよそ Bigtable サーバーのデプロイメントのグループに似ています。zones はデプロイメントを管理する基本単位です。zones の集合は、データがレプリケートされる場所の集合でもあります。

新しいデータセンターが稼働し、古いデータセンターが閉鎖されるにつれて、システムに zones を動的に追加および削除できます。また、zones は物理的に隔離された単位でもあります：1 つのデータセンター内に複数の zones が存在する場合があります。たとえば、特定の状況では、同じデータセンター内の異なるアプリケーションのデータは異なるサーバーのセットに分割する必要があります。

組織構造

上の図は、Spanner universe の異なるサーバーを示しています。1 つの zone には 1 つの zonemaster と数百から数千の spanserver があり、前者はデータを spanservers に割り当て、後者はクライアントにデータサービスを提供します。各 zone の location proxies は、クライアントがデータを spanservers に割り当てるために使用されます。universe master と placement driver は現在、どちらも単一インスタンスです。universe master は主にすべての zones の状態情報を表示するためのインタラクティブなデバッグ用のコンソールです。placement driver は、分単位での zone 間のデータの自動移動を処理し、placement driver は定期的に spanservers と通信して、更新されたレプリケーション制約や負荷バランスを満たすために移動する必要があるデータを見つけます。スペースの制約上、ここでは spanserver についてのみ詳細に説明します。

Spanserver ソフトウェアスタック#

このセクションでは、spanserver の実装に焦点を当て、Bigtable ベースの実装上にレプリカと分散トランザクションを構築する方法を説明します。ソフトウェアスタックは以下の図のようになります。

ソフトウェアスタック

最下層では、各 spanserver は 100 から 1000 の tablet と呼ばれるデータ構造のインスタンスを担当しています。ここでの tablet は Bigtable の tablet の抽象概念に似ており、以下のマッピング関係の多重集合を実現しています。

(key:string, timestamp:int64) -> string

Bigtable とは異なり、Spanner はデータに直接タイムスタンプを付与します。これは Spanner がキー・バリュー・ストレージではなくデータベースにより似ている重要な点です。各 tablet の状態は、B-tree に似たファイルと write-ahead ログ（WAL）のセットに保存され、これらのファイルはすべて Colossus と呼ばれる分散ファイルシステム（GFS の後継）に保存されます。レプリケーションをサポートするために、各 spanserver は各 tablet の上に個別の Paxos 状態機械を実装しています（初期の Spanner バージョンでは、各 tablet に複数の Paxos 状態機械をサポートし、より柔軟なレプリケーション構成を可能にしましたが、この設計の複雑さから私たちはこれを放棄しました）。各状態機械は、そのメタデータと担当する tablet のログを保存します。私たちの Paxos 実装は、時間リースメカニズムに基づく long-lived Leader をサポートし、デフォルトのリース時間は 10 秒です。現在の Spanner 実装では、各 Paxos 書き込みに対して 2 回ログを記録します：1 回は tablet のログに、もう 1 回は Paxos のログに。この選択は便利さから来ており、最終的には改善される可能性があります。私たちが実装した Paxos はパイプライン化されており、Spanner の WAN 遅延下でのスループットを改善しますが、書き込み操作は Paxos の順次実行です。

Paxos 状態機械は、一貫性のあるレプリケーションのマッピング関係の多重集合を実現します。一組のレプリカのキー・バリュー・マッピング状態は、対応する tablet に保存されます。書き込み操作は、Leader が Paxos プロトコルを開始する必要があります。読み取り操作は、十分に新しいレプリカのいずれかの底層 tablet の状態に直接アクセスします。

一組のレプリカの集合は、1 つの Paxos グループを構成し、各リーダーのレプリカ上で各 spanserver は並行制御を実現するためにロックテーブルを実装しています。このロックテーブルには、2 段階ロックの状態が含まれています：マッピングキーの範囲をロック状態 $K_{0..n} \Rightarrow lock$ にマッピングします（long-lived Paxos リーダーがロックテーブルを効率的に管理することが鍵です）。Bigtable と Spanner の両方で、私たちは long-lived トランザクション（たとえば、レポート生成、数分かかる可能性があります）を設計しましたが、競合が発生するシナリオでは、楽観的並行制御のアクセス性能が非常に悪くなります。同期が必要な操作、たとえばトランザクションの読み取り操作は、まずロックテーブルのロックを取得する必要がありますが、他の操作はロックテーブルのロックをスキップできます。

各レプリカリーダー上で、各 spanserver は分散トランザクションをサポートするためにトランザクションマネージャも実装しています。このトランザクションマネージャは、リーダーに参加するために使用されます。同じグループの他のレプリカは、従属ノードとして参加します。トランザクションが 1 つの Paxos グループにのみ関与する場合（ほとんどのトランザクション）、トランザクションマネージャを介さずに処理できます。なぜなら、ロックテーブルと Paxos が一緒にトランザクションサポートを提供するのに十分だからです。トランザクションが複数の Paxos グループに関与する場合、これらのグループのリーダーが 2 段階コミットを調整します。トランザクションを実行する際には、関与するすべてのグループから 1 つのグループを選択してコーディネーターとして選びます。この選定されたグループ内のリーダーはコーディネーターリーダーと呼ばれ、そのグループの従属ノードはコーディネーター従属ノードと呼ばれます。各トランザクションマネージャの状態は、底層の Paxos グループに保存されます（したがって、複製されます）。

ディレクトリと配置#

Spanner の実装は、キー・バリュー・マッピングの多重集合の上に、ディレクトリと呼ばれるバケット抽象をサポートします。これは、同じプレフィックスを持つ連続したキーの集合です（ディレクトリという用語を選択したのは歴史的な理由であり、より良い呼び方はバケットかもしれません）。ディレクトリをサポートすることで、アプリケーションはキーを慎重に選択することでデータの局所性を制御できます。ディレクトリはデータ配置の単位であり、同じディレクトリ内のすべてのデータは同じレプリカ構成を持ちます。彼らはディレクトリ単位で Paxos グループ間で移動します。以下の図のように：

directory 移動

Spanner は、負荷を軽減するために Paxos グループからディレクトリを移動したり、頻繁に一緒にアクセスされるディレクトリを同じグループに配置したり、ディレクトリをアクセス者に近いグループに移動したりすることがあります。ディレクトリは、クライアントが操作を実行している間に移動できます。50MB のディレクトリは、約数秒で移動できます。

1 つの Paxos グループには複数のディレクトリが含まれる可能性があります。これは Spanner の tablet と Bigtable の tablet の違いです：前者は必ずしも単一の行空間に辞書順で連続したパーティションではありません。逆に、Spanner の tablet は、行空間の複数のパーティションをカプセル化できるコンテナです。この決定を下したのは、頻繁に一緒にアクセスされる複数のパーティションが共存できるようにするためです。

Movedirは、Paxos グループ間でディレクトリを移動するためのバックグラウンドタスクです。Movedir は、Paxos グループ内でレプリカを追加および削除するためにも使用されます。現在、Spanner は Paxos に基づく構成変更をサポートしていません。Movedir は単一のトランザクションとして実装されておらず、大量のデータ移動中に進行中の読み書き操作をブロックしないようにしています。代わりに、movedir はバックグラウンドでデータの移動を開始したことを記録し、ほぼすべてのデータを移動した後、トランザクションを使用して残りのわずかなデータを自動的に移動し、2 つの Paxos グループのメタデータを更新します。

ディレクトリは、アプリケーションが地理的レプリケーション属性（または配置ポリシー）を指定できる最小単位でもあります。私たちの placement-specification 言語は、レプリカ構成の管理責任を分離します。管理者は、レプリカの数とタイプ、およびこれらのレプリカの配置先のアドレス位置の 2 つの次元を制御します。この 2 つの次元に基づいて、命名オプションのメニューが作成されます（たとえば、北米、5 つのレプリカと 1 つのウィットネスレプリカを使用）（注：ウィットネスレプリカは通常、リーダー選挙投票、競合の仲裁、ブレインスプリットの防止などに使用されます。参考：Cloud ドキュメント）。アプリケーションは、これらのオプションの組み合わせを使用して、各データベースおよび（または）各ディレクトリにラベルを付け、データがどのようにレプリケートされるかを制御します。たとえば、アプリケーションは、各エンドユーザーのデータをそれぞれのディレクトリに保存し、ユーザー A のデータがヨーロッパに 3 つのレプリカ、ユーザー B のデータが北米に 5 つのレプリカを持つようにすることができます。

説明を簡素化するために、過度の簡略化を行いました。実際には、ディレクトリが大きすぎる場合、Spanner はそれを複数のフラグメントにシャーディングし、フラグメントは異なる Paxos グループ（したがって異なるサーバー）でサービスを提供する可能性があります。Movedir は実際にはグループ間でフラグメントを移動しているのです。

データモデル#

Spanner はアプリケーションに以下のデータ特性を公開します：スキーマに基づく半関係型テーブルのデータモデル、クエリ言語、および一般的なトランザクション。これらの機能をサポートする方向への移行は、さまざまな要因によって推進されました。

スキーマに基づく半関係型テーブルと同期レプリケーションのニーズは、Megastore の人気によって推進されました。Google には少なくとも 300 のアプリケーションが Megastore を使用しています（その性能は比較的低いですが）、なぜならそのデータモデルは Bigtable よりも管理が簡単で、データセンター間の同期レプリケーションをサポートしているからです（Bigtable はデータセンター間の最終的な一貫性のレプリケーションのみをサポートしています）。Megastore を使用している比較的有名なアプリケーションには、Gmail、Picasa、Calendar、Android Market、AppEngine などがあります。Dremel がインタラクティブなデータ分析ツールとしての人気を考慮すると、Spanner で SQL ライクなクエリ言語をサポートする必要性も非常に明白です。

最後に、Bigtable で欠けている行を跨ぐトランザクションも頻繁に苦情を引き起こしました；Percolator を構築する部分的な理由はこの問題を解決することでした。一部の著者は、一般的な 2 段階コミットをサポートすることは非常に高価であると考えています。なぜなら、それは性能や可用性の問題を引き起こすからです。私たちは、アプリケーションプログラマーがトランザクションの乱用によって性能ボトルネックが発生した場合に性能問題を処理する方が良いと考えています。Paxos を介して 2 段階コミットを実行することで、可用性の問題を軽減します。

アプリケーションのデータモデルは、ディレクトリをバケットとするキー・バリュー・マッピングの上に構築されています。アプリケーションは 1 つの universe 上に 1 つ以上のデータベースを作成できます。各データベースは無制限の数の構造化テーブルを含むことができます。テーブルは関係型データテーブルに似ており、行、列、およびバージョン化された値を含みます。私たちは Spanner のクエリ言語の詳細には深入りしません。それは SQL のように見え、プロトコルバッファ値フィールドをサポートするためにいくつかの拡張が行われています。

Spanner のデータモデルは純粋な関係型ではありません。なぜなら、各行は名前を持たなければならないからです。より正確には、各テーブルは 1 つ以上の順序付けられた主キー列の集合を持つ必要があります。この要件により、Spanner は依然としてキー・バリュー・ストレージのように見えます：主キーは行の名前を構成し、各テーブルは主キー列から非主キー列へのマッピングを定義します。行は主キーに値が定義されている場合（NULL であっても）にのみ存在します。この構造を強制することは有用です。なぜなら、これによりアプリケーションはキーを選択することでデータの局所性を制御できるからです。

spanner-figure4

上の図は、各ユーザー、各アルバムに基づいて写真のメタデータをソートした Spanner の例の構造を含んでいます。このスキーマ定義言語は Megastore に似ていますが、追加の要件が増えています：各 Spanner データベースは、クライアントによって 1 つ以上の階層構造に対してテーブルを分割する必要があります。

クライアントアプリケーションは、データベーススキーマ内でINTERLEAVE INを宣言して階層構造を示します。階層構造の最上位のテーブルはディレクトリテーブルです。ディレクトリテーブルでは、キー K を起点とし、辞書順に並べられた K で始まるすべての行がディレクトリを構成します。

ON DELETE CASCADEは、ディレクトリテーブルの行を削除する際に、すべての関連する子行を削除することを示します。上の図は、example データベースの交錯レイアウトも示しています。たとえば、Albums (2,1) は、Albums テーブルの user_id == 2 && album_id == 1 から始まる行を示します。このようなテーブルの交錯はディレクトリを構成する上で非常に重要です。なぜなら、これによりクライアントは複数のテーブル間の局所性関係を記述でき、シャーディングされた分散データベースで良好な性能を得るために必要だからです。この機能がなければ、Spanner は最も重要な局所性関係を知ることができません。

TrueTime#

このセクションでは、TrueTime API と実装の概要を説明します。詳細は別の論文に残しています。このセクションの目的は、私たちにこのような API がもたらす力を証明することです。

メソッド	戻り値
TT.now()	TTinterval: [earlist, latest]
TT.after(t)	t が確実に経過した場合は true
TT.before(t)	t が確実に到着していない場合は true

上の表は、API のメソッドを示しています。TrueTime は時間を $TTinterval$ として明示的に表現し、これは有界な時間不確実性を持つ時間間隔です（標準ライブラリの時間インターフェースはクライアントに不確実性の概念を伝えるだけです）。 $TTinterval$ のノードのタイプは $TTstamp$ であり、 $TT.now()$ メソッドは、 $TT.now()$ を呼び出したときの絶対時間を保証する $TTinterval$ の範囲を返します。time epoch は、うるう秒のあいまいさを処理した UNIX 時間に似ています。瞬時誤差界限を $\varepsilon$ 、すなわち時間区間の幅の半分、平均誤差を $\bar{\varepsilon}$ と定義し、 $TT.after()$ および $TT.before()$ メソッドは $TT.now()$ の簡易ラッパーです。

関数 $t_{abs}(e)$ は、イベント $e$ が発生した絶対時間を示します。より正式には、TrueTime は次のことを保証します：任意の呼び出し（invocation） $tt = TT.now(), tt.earliest \le t_{abs}(e_{now}) \le tt.latest$ 、ここで $e_{now}$ は呼び出し（invocation）イベントです。

TrueTime の基盤となる時間は GPS と原子時計を参照しています。TrueTime が 2 つの形式の時間参照を使用するのは、異なる障害モードがあるからです。GPS 参照源の脆弱性には、アンテナや受信機の故障、ローカル無線干渉、関連する故障（欠陥を含む、たとえば誤ったうるう秒処理や欺瞞）、および GPS システムの中断が含まれます。原子時計は、GPS や他の原子時計とは無関係に故障する可能性があり、時間の経過とともに周波数誤差により明らかな漂移が発生します。

TrueTime は、各データセンターの一群の time master マシンと各マシン上の timeslave プロセスによって実装されています。ほとんどの master は専用アンテナを備えた GPS 受信機を装備しています；これらの master は物理的に隔離されており、アンテナ故障、無線干渉、欺瞞の影響を軽減します。残りの master（私たちはこれを Armageddon マスターと呼びます）は原子時計を装備しています。原子時計はそれほど高価ではありません：Armageddon マスターのコストは GPS マスターのコストと同等です。

すべての master の時間参照は定期的に相互比較され、各 master は参照時間の進行速度を自分のローカル時計とクロスチェックし、顕著な偏差がある場合は自分自身を除外します。2 回の同期の間、Armageddon マスターは徐々に増加する時間誤差（time uncertainty）を宣言します。この誤差は、時計の漂移に基づいて最悪のケースで保守的に推定されます。GPS マスターが宣言する誤差は通常ゼロに近いです。

各デーモンは、複数の master をポーリングして、任意の 1 つの master ノードに依存する脆弱性を減らします。一部はデータセンターの近くから選ばれた GPS マスターです；残りの GPS マスターは遠くのデータセンターから来ています；もちろん、Armageddon マスターもあります。デーモンは、Marzulloアルゴリズムの変種を使用して虚偽情報を検出し、拒否し、ローカルマシンの時計と非虚偽情報（nonliars）を同期させます。ローカル時計の故障を防ぐために、周波数オフセットが対応するコンポーネントの標準および操作環境下の最悪のケースの誤差界限を超えるマシンは除外されます。

2 回の同期の間、デーモンは徐々に増加する時間誤差を宣言します。e は、最悪のケースでのローカル時計の漂移を保守的に推定したもので、e は time-master の誤差と time-master との通信遅延に依存します。私たちの生産環境では、e は通常、時間の鋸歯状関数です。各ポーリング間隔内で 1ms から 7ms の変化があるため、e はほとんどの時間 4ms です。デーモンのポーリング間隔は現在 30s で、現在使用されている漂移率は 200 マイクロ秒 / 秒に設定されており、合計で 0 から 6ms の鋸歯状変化範囲をもたらし、残りの 1ms は time master への通信遅延から来ています。障害が発生した場合、この鋸歯状変化は偏移することがあります。たとえば、時折 time-master が利用できない場合、e はデータセンターの範囲で増加します。同様に、マシンやネットワーク接続の過負荷も、時折局所的なスパイクを引き起こす可能性があります。

同時実行制御#

このセクションでは、TrueTime を使用して同時実行制御の正確性を保証する方法、およびこれらの特性を使用して外部一貫性トランザクション、読み取り専用のロックフリー・トランザクション、履歴非ブロッキング読み取りなどの特性を実現する方法を説明します。これらの特性により、たとえば、タイムスタンプ $t$ の時点でデータベース全体の監査読み取りが、 $t$ より前にコミットされたすべてのトランザクションの効果を読み取ることができます。

Paxos が見た書き込み（以降 Paxos 書き込みと呼ぶ）と Spanner クライアントの書き込みを区別することが重要です。たとえば、2 段階コミットの prepare 段階で Paxos 書き込みが発生しますが、対応する Spanner クライアントの書き込みはありません。

タイムスタンプ管理#

操作	同時実行制御	必要なレプリカ
読み書きトランザクション	悲観的	リーダー
読み取り専用トランザクション	ロックフリー	タイムスタンプのリーダー；読み取りは任意
スナップショット読み取り、クライアント提供のタイムスタンプ	ロックフリー	任意
スナップショット読み取り、クライアント提供の境界	ロックフリー	任意

上の表は、Spanner がサポートする操作タイプを示しています。Spanner の実装は、読み書きトランザクション、読み取り専用トランザクション（事前宣言されたスナップショット隔離トランザクション）、およびスナップショット読み取りをサポートしています。独立した書き込みは読み書きトランザクションとして実装され、非スナップショットの独立した読み取りは読み取り専用トランザクションとして実装され、両者とも内部的にリトライを行います（クライアントが明示的にループリトライする必要はありません）。

読み取り専用トランザクションは、スナップショット隔離の性能上の利点を持つトランザクションです。読み取り専用トランザクションは、書き込みを含まないことを事前に宣言する必要があります。これは、単に書き込み操作がない読み書きトランザクションではありません。読み取り専用トランザクションでは、読み取り操作はシステムが選択したタイムスタンプでロックフリーで実行されるため、後続の書き込み操作をブロックしません。読み取り専用トランザクション内の読み取り操作は、十分に新しいレプリカのいずれかで実行できます。

スナップショット読み取りは過去の読み取りであり、実行時にもロックをかけません。クライアントはスナップショット読み取りのタイムスタンプを指定するか、期待されるタイムスタンプの古さの上限を提供し、Spanner にタイムスタンプを選択させることができます。いずれの場合でも、スナップショット読み取りは十分に新しいレプリカで実行されます。

読み取り専用トランザクションとスナップショット読み取りの場合、タイムスタンプが選択されると、コミット時には避けられません。これは、そのタイムスタンプのデータがすでにガベージコレクションされていない限りです。最終的に、クライアントはリトライループで結果をバッファリングすることを避けることができます。サービスが障害を起こした場合、クライアントは内部的に別のサーバーにタイムスタンプと現在の読み取り位置を提供してクエリを続行します。

Paxos リーダーリース#

Spanner の Paxos 実装は、時間ベースのリースを使用して long-live-leader（デフォルトは 10 秒）を保証します。潜在的なリーダーは、時間ベースのリース投票リクエストを送信します。十分な過半数の票を受け取った後、彼は自分がリースを取得したと見なすことができます。レプリカは、成功した書き込みの後に明示的にリース投票を延長し、リーダーはリースが期限切れに近づくとリースの更新投票を要求します。

リーダーのリース間隔を定義します：彼が十分な過半数のリース投票を受け取ったことを発見してから、彼がもはや十分な過半数のリース投票を持たなくなるまでの間隔（いくつかの投票が期限切れになったため）。

Spanner は、次の不交差性不変量（disjointness invariant）に依存します：各 Paxos グループに対して、各 Paxos のリーダーと他のすべてのリーダーのリース間隔は重複しません（付録 A では、この不変量を維持する方法について説明します）。

Spanner の実装では、Paxos リーダーがリース投票を放棄することでリーダーの地位を放棄できます。不交差性不変量を維持するために、Spanner は放棄を許可するタイミングを制限します。 $s_{max}$ をリーダーが使用する最大タイムスタンプと定義し、次の段落では、 $s_{max}$ がいつ早まるかを説明します。放棄する前に、リーダーは $TT.after(s_{max})$ が true であることを保証する必要があります。

RW トランザクションへのタイムスタンプの割り当て#

トランザクションの読み取りと書き込みは 2 段階ロックを使用し、最終的に、彼らは [すべてのロックを取得した後、任意のロックを解放する前] の任意のタイミングでタイムスタンプを割り当てることができます。特定のトランザクションに対して、Spanner はそのタイムスタンプを、トランザクションのコミットを表す Paxos 書き込みに割り当てられたタイムスタンプに設定します。

Spanner は次の単調不変性に依存します：各 Paxos グループ内で、Spanner は Paxos 書き込みに単調増加の順序でタイムスタンプを割り当てます。リーダーが変わっても（注：リーダーが他のノードに変わることがあります）。単独のリーダーレプリカは、単調増加の順序でタイムスタンプを簡単に割り当てることができます。不交差不変性を利用することで、リーダー間でこの不変性を維持できます：リーダーはそのリーダーリース間隔内でのみタイムスタンプを割り当てることができます。

適切にタイムスタンプ $s$ が割り当てられた場合、 $s_{max}$ は必ず $s$ より大きくなければなりません。不交差を維持するためです。Spanner は次の外部一貫性不変量も強制します：もしトランザクション $T2$ の開始がトランザクション $T1$ のコミットの後に発生した場合、 $T2$ のコミットタイムスタンプは必ず $T1$ のコミットタイムスタンプより大きくなければなりません。

トランザクション $T_{i}$ の開始とコミットの時間をそれぞれ $e_{i}^{start}$ と $e_{i}^{commit}$ 、コミットタイムスタンプを $s_{i}$ と定義すると、不変性は次のようになります：

$t_{abs}(e_{1}^{commit}) < t_{abs}(e_{2}^{start}) \Rightarrow s_{1} < s_{2}$

トランザクションを実行し、タイムスタンプを割り当てるプロトコルは、不可変性を保証するために 2 つのルールに従います。書き込みトランザクション $T_{i}$ のコミットリクエストがコーディネーターリーダーに到達するイベントを $e_{i}^{server}$ と定義します。

Start: コーディネーターリーダーは書き込みトランザクション $T_{i}$ にタイムスタンプ $s_{i}$ を割り当てます。ここで $s_{i}$ は、 $e_{i}^{server}$ の計算後の $TT.now().latest$ 以上でなければなりません。参加者リーダーはここでは重要ではありません。後で彼らがどのように 2 番目のルールの実装に参加するかを説明します。
Commit Wait: コーディネーターリーダーは、 $TT.after(s_{i})$ が true である前に、クライアントが $T_{i}$ のコミットデータを見られないことを保証します。コミット待機は、 $s_{i}$ が $T_{i}$ のコミットの絶対時間より小さいことを保証します。すなわち、 $s_{i} < t_{abs}(e_{i}^{commit})$ 。コミット待機の実装は後で紹介します。証明：

タイムスタンプでの読み取りの提供#

前述の単調不変性により、Spanner はレプリカの状態が読み取りリクエストを満たすのに十分新しいかどうかを正しく判断できます。各レプリカは、最大タイムスタンプに更新された安全時間 $t_{safe}$ という値を追跡します。もしリクエストタイムスタンプ $t \le t_{safe}$ であれば、レプリカは読み取りリクエストを満たすことができます。

$t_{safe} = min(t_{Paxos}^{safe}, t_{TM}^{safe})$ と定義します。ここで、各 Paxos 状態機械には安全時間 $t_{Paxos}^{safe}$ があり、各トランザクションマネージャには安全時間 $t_{TM}^{safe}$ があります。 $t_{Paxos}^{safe}$ は非常に単純です：それはすでに適用された Paxos 書き込み操作の最大タイムスタンプです。タイムスタンプは単調増加し、書き込み操作は順次適用されるため、 $t_{Paxos}^{safe}$ またはそれ以降の時間には書き込み操作は存在しません。 $t_{TM}^{safe}$ は、そのレプリカのリーダーのトランザクションマネージャの状態を使用します。この状態は、Paxos 書き込みプロセス中のメタデータを介して取得されます。

レプリカ上に「準備完了だがまだコミットされていない」トランザクションがない場合：すなわち、2 段階コミットの 2 つのステップの間にあるトランザクションの場合、レプリカの $t_{TM}^{safe}$ は $\infty$ です（参加者スレーブサーバーの場合、 $t_{TM}^{safe}$ は実際にはそのレプリカのリーダーのトランザクションマネージャの状態を使用します。この状態は、Paxos 書き込み操作によって伝達されるメタデータを介して推測できます）。このようなトランザクションが存在する場合、これらのトランザクションが状態に与える影響は不確実です：参加者レプリカはこのトランザクションがコミットされるかどうかをまだ知りません。前述のように、コミットプロトコルは、各参加者が準備されたトランザクションのタイムスタンプの下限を知ることを保証します。グループ g に対して、各参加者リーダーはトランザクションの prepare 記録に prepare タイムスタンプ $s_{i,g}^{prepare}$ を割り当て、コーディネーターリーダーはグループ g 内のすべての参加者に対して、トランザクションのコミットタイムスタンプ $s_{i} \ge s_{i,g}^{prepare}$ を保証します。したがって、g 内の任意のレプリカは、g 上で準備されたすべてのトランザクション $T_{i}$ に対して $t_{TM}^{safe} = min_{i}(s_{i,g}^{prepare}) - 1$ となります。

RO トランザクションへのタイムスタンプの割り当て#

読み取り専用トランザクションの実行は 2 つの段階に分かれます：タイムスタンプ $s_{read}$ を割り当て、その後 $s_{read}$ でトランザクションの読み取りをスナップショット読み取りとして実行します。スナップショット読み取りは、十分に新しいレプリカで実行できます。 $s_{read}$ は、トランザクション開始後の任意のタイミングで $s_{read} = TT.now().latest$ として割り当てることができます。これは、前述の書き込みの状況と同様に外部一貫性を提供します。ただし、 $t_{safe}$ がまだ十分に新しくない場合（ $s_{read}$ より小さい場合）、データ読み取り操作は $s_{read}$ でブロックされる必要があります（さらに、カスタムの $s_{read}$ 値を選択することで、 $s_{max}$ を増加させて不交差性を維持することができます）。ブロックの機会を減らすために、Spanner は外部一貫性を保護するために最も古いタイムスタンプを割り当てるべきです。4.2.2 では、このようなタイムスタンプを選択する方法を説明します。

詳細#

このセクションでは、以前に無視された読み書きトランザクションと読み取り専用トランザクションのいくつかの実践的な詳細、および原子的なスキーマ変更を実現するための特別なトランザクションの実装を説明します。次に、以前に説明した基本的なスキームの改善を説明します。

読み書きトランザクション#

Bigtable と同様に、トランザクション内の書き込み操作は、コミットされるまでクライアント内でキャッシュされます。最終的に、トランザクション内の読み取り操作は、トランザクション内の書き込み操作の効果を見ません。この設計は、Spanner でうまく機能します。なぜなら、読み取り操作は読み取ったデータのタイムスタンプを返し、未コミットの書き込みにはまだタイムスタンプが割り当てられていないからです。

読み書きトランザクション内の読み取り操作は、woundwaitを使用してデッドロックを回避します。クライアントは、対応するグループのレプリカリーダーに読み取り操作リクエストを送信し、読み取りロックを要求して最新のデータを読み取ります。クライアントのトランザクションがオープンのままの場合、keepalive メッセージを送信して、参加者リーダーがそのトランザクションをタイムアウトさせないようにします。クライアントがすべての読み取り操作を完了し、すべての書き込み操作をキャッシュした後、2 段階コミットを開始します。クライアントはコーディネーターグループを選択し、各参加者リーダーにコミットメッセージを送信します：コーディネーターの識別子とすべての書き込み操作を含みます。クライアント主導の 2 段階コミットを使用することで、データを 2 回転送することを回避できます。

非コーディネーター参加者（non-coordinator-participant）リーダーは、最初に書き込みロックを要求し、次に、彼がトランザクションに割り当てるすべてのタイムスタンプより大きい必要がある prepare タイムスタンプを選択します（単調性を保証します）。その後、Paxos を介して prepare 記録を追加します。各参加者はその prepare タイムスタンプをコーディネーターに通知します。

コーディネーターリーダーも最初に書き込みロックを要求しますが、prepare 段階をスキップします。他のすべての参加者からメッセージを受け取った後、彼はトランザクション全体にタイムスタンプを選択します。コミットタイムスタンプ $s$ は、すべての prepare タイムスタンプ以上でなければなりません（整合性を満たすため）、コーディネーターがそのコミットメッセージを受け取ったときの $TT.now().latest$ よりも大きく、リーダーが以前のトランザクションに割り当てたすべてのタイムスタンプよりも大きくなければなりません（再度、単調性を保証します）。その後、コーディネーターリーダーは Paxos を介してコミットログを記録します（または、他の参加者を待っている間にタイムアウトした場合は中断します）。

任意のコーディネーター副本がコミット記録を適用する前に、コーディネーターリーダーは $TT.after(s)$ が true になるまで待機します。これは、4.1.2 で説明されているcommit-waitルールを遵守するためです。コーディネーターは $TT.now().latest$ に基づいてコミットタイムスタンプ s を選択し、現在このタイムスタンプが過去になるまで待機するため（注：現在の絶対時間が必ず s より大きくなるまで待機する必要があります）、期待される待機時間は $2 * \bar{\varepsilon}$ です（注：セクション 3 で言及された平均誤差時間）。この待機時間は通常、Paxos との通信時間と重複します。コミット待機の後、コーディネーターはコミットタイムスタンプをクライアントと他のすべての参加者リーダーに送信し、各参加者は Paxos を介してトランザクションの結果を記録します。すべての参加者は同じタイムスタンプを適用し、その後ロックを解放します。

読み取り専用トランザクション#

タイムスタンプを割り当てるには、読み取り操作が関与するすべての Paxos グループ間でコミュニケーションフェーズ（negotiation phase）が必要です。最終的に、Spanner は各読み取り専用トランザクションにスコープ式を持たせる必要があります。この式は、トランザクションが読み取るキーの集合を概括します。Spanner は単一のリクエストのためにこのスコープを自動的に推測します。もしスコープの値が単一の Paxos グループによって提供できる場合、クライアントはそのグループのリーダーに読み取り専用トランザクションリクエストを送信できます（現在の Spanner 実装では、Paxos リーダー上でのみ読み取り専用トランザクションにタイムスタンプを選択します）。このリーダーは $s_{read}$ タイムスタンプを割り当て、その後読み取り操作を実行します。単一の読み取りの場合、Spanner は $TT.now().latest$ を直接呼び出すよりも良いタイムスタンプ割り当て方法を持っています。 $LastTS()$ を Paxos グループ上で最後に書き込まれたコミットのタイムスタンプと定義します。もし prepare トランザクションがなければ、 $s_{read} = LastTS()$ を直接割り当てることで外部一貫性を簡単に満たします：トランザクションは最後の書き込みの結果を見て、それに続くことになります。

もしスコープの値が複数の Paxos グループによって提供される必要がある場合、いくつかの選択肢があります。最も複雑な選択肢は、すべてのグループリーダーと一回の通信を行い、 $LastTS()$ に基づいて $s_{read}$ を協議して選択することです。現在の Spanner 実装は、クライアントが一回の通信を行うのを避けるために、単にその読み取り実行時間を $s_{read} = TT.now().latest$ に設定します（安全時間が追いつくまで待つ必要があるかもしれません。注：この時間は安全時間を超える可能性があります）。トランザクション内のすべての読み取りは、十分に新しいレプリカに送信できます。

スキーマ変更トランザクション#

TrueTime は、Spanner が原子的なスキーマ変更をサポートすることを可能にします。標準のトランザクションを使用することは不可能です。なぜなら、参加者の数（データベース内のグループの数）のデータが数百万に達する可能性があるからです。Bigtable は、1 つのデータセンター内での原子的なスキーマ変更をサポートしていますが、そのスキーマ変更はすべての操作をブロックします。一方、Spanner のスキーマ変更トランザクションは、通常の非ブロッキング標準トランザクションの変種です。

まず、将来のタイムスタンプを明示的に割り当て、prepare 段階で登録します。最終的に、数千台のサーバーにわたるスキーマ変更が、他の並行活動に非常に小さな中断をもたらすことなく完了できます。次に、読み書き操作は、スキーマに明示的に依存します。

次に、スキーマに対する暗黙の依存関係を持つ読み書き操作は、時間 $t$ において、登録されたスキーマ変更と同期します：もし彼らのタイムスタンプが $t$ より前であれば、実行される可能性があります。そうでなければ、彼らはスキーマ変更トランザクションの後までブロックされなければなりません（注：このトランザクションの時間は $t$ より大きいため、スキーマ変更トランザクションが先に実行されるのを待つ必要があります）。TrueTime がなければ（このような安定した、グローバルに一貫した時間 API がなければ）、スキーマ変更が時間 $t$ に発生することを定義することは意味がありません。

改善#

上記で定義した $t_{safe}^{TM}$ には弱点があります。すなわち、準備されたトランザクションが $t_{safe}$ の進行を妨げる可能性があります。最終的に、後続のタイムスタンプでは、読み取り操作を実行できなくなります。たとえその読み取り操作がトランザクションと何の衝突もない場合でも。この誤った衝突は、キー範囲から prepare トランザクションのタイムスタンプへのマッピングを細かく追加することで排除できます。この情報はロックテーブルに保存できます。このテーブルはすでにキー範囲をロックメタデータにマッピングしています。読み取り操作が到達すると、それは単にその衝突するキー範囲に対応する細かい安全時間を確認する必要があります。

以前に定義した $LastTS()$ には同様の弱点があります：もしトランザクションがちょうどコミットされた場合、衝突のない読み取り専用トランザクションはこのトランザクションのタイムスタンプを $s_{read}$ に割り当てる必要があります。最終的に、読み取り操作が遅延する可能性があります（注：このトランザクションがちょうどコミットされたため、すべての参加者に同期されていない可能性があり、あるレプリカで読み取る際に待機する必要があるかもしれません）。この弱点も、ロックテーブルに $LastTS()$ を追加し、キー範囲からコミットタイムスタンプへの細かいマッピングを追加することで修正できます（現在、この最適化は実装されていません）。読み取り専用トランザクションが到達すると、そのタイムスタンプは、衝突するキー範囲の $LastTS()$ の最大値として割り当てられます。現在、衝突する prepare トランザクションがない限り（細かい安全時間を介して確認できます）。

以前に定義した $t_{safe}^{Paxos}$ には、Paxos 書き込み操作がない場合に進行できないという弱点があります（注： $t_{safe}^{Paxos}$ は最後の書き込み操作のタイムスタンプを使用しています）。すなわち、 $t$ のスナップショット読み取りは、最後の書き込み操作が $t$ より前の Paxos グループで実行できません。Spanner はリーダーリース間隔の不交差性を利用してこの問題を解決します。各 Paxos リーダーは、しきい値を維持し、将来の書き込み操作のタイムスタンプがこのしきい値を超えるようにします。これは、Paxos シーケンス番号 n から将来の Paxos シーケンス番号 n+1 に割り当てられる可能性のある最小タイムスタンプのマッピング $MinNextTS(n)$ を維持します。レプリカは、すでに n シーケンス番号を適用した後、 $t_{safe}^{Paxos}$ を $MinNextTS(n)−1$ に進めることができます。

単独のリーダーは $MinNextTS()$ の約束を簡単に実行できます。なぜなら、 $MinNextTS()$ の約束されたタイムスタンプはリーダーのリース内にあり、不交差不変性（注：各リーダーのリース時間は重複しない）により、リーダー間で $MinNextTS()$ の約束を実行できます。リーダーが $MinNextTS()$ をリーダーリースを超えて進めたい場合、リースを更新する必要があります。 $s_{max}$ は常に $MinNextTS()$ の最大値を超えていることに注意して、不交差性を保証します。

リーダーはデフォルトで 8 秒ごとに $MinNextTS()$ の値を進めるため、準備されたトランザクションがない場合、空いている Paxos グループ内の健全なスレーブは、最悪の場合、最古のタイムスタンプより 8 秒大きいタイムスタンプを提供できます。リーダーはスレーブの要求に応じて $MinNextTS()$ の値を上げることもできます。

評価#

省略...

今後の作業#

昨年、私たちは F1 グループと共に、Google の広告バックエンドを MySQL から Spanner に移行するために大部分の時間を費やしました。私たちは監視とサポートツールの改善に積極的に取り組んでおり、その性能も最適化しています。また、バックアップと復元システムの機能と性能も改善しています。現在、Spanner スキーマ言語、自動化された補助インデックスの維持、負荷に基づく自動再シャーディングを実装しています。長期的には、多くの新機能を研究する計画です。楽観的な並行読み取りは比較的価値のある戦略かもしれませんが、初期の実験では、正しい実装が簡単ではない可能性があることが示されています。さらに、最終的には Paxos 構成を直接変更することをサポートする計画です。

私たちは、多くのアプリケーションが非常に近いデータセンターにデータをレプリケートすることを期待しているため、TrueTime の $\varepsilon$ が性能に大きな影響を与える可能性があることを考慮しています。私たちは、 $\varepsilon$ を 1ms に減少させることに対して、越えられない障害が何もないことを確認していません。Time-master-query（注：time-master に時間を調整するように要求する）間隔を減少させることができ、より良いクォーツ時計も比較的安価です。Time-master-query の遅延は、ネットワークトポロジーを改善することで改善でき、代替の time-distribution 技術を使用して回避できる可能性もあります。

最終的に、改善できる明らかな点がたくさんあります。Spanner はノード数を拡張できますが、ノードローカルデータ構造は複雑な SQL クエリの性能が相対的に低いです。なぜなら、これらは単純なキー・バリューアクセスのために設計されているからです。データベース文献からのアルゴリズムやデータ構造は、単一ノードの性能を大幅に改善できます。次に、クライアントの負荷に基づいてデータセンター間でデータを自動的に移動することは、私たちの目標の 1 つですが、この目標を効率的に実現するためには、クライアントアプリケーションプロセスをデータセンター間で自動化された調整された方法で移行する能力が必要です。プロセスの移行は、データセンター間でリソースの要求と割り当てを管理するという、より厳しい問題をもたらします。

結論#

要するに、Spanner は 2 つのコミュニティからの研究を結合し、拡張しています：データベースコミュニティからは、親しみやすく使いやすい半関係型インターフェース、トランザクション、SQL ベースのクエリ言語を取得し、システムコミュニティからは、スケーラビリティ、自動シャーディング、障害耐性、一貫性のあるレプリケーション、外部一貫性、広域分散を取得しています。

且听风吟