スパナー: 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 の実装が提供する範囲制限（bound という訳注：時計は不確実であるため、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 に保存されます。書き込み操作は、リーダーが 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 グループのメタデータを更新します。

ディレクトリは、アプリケーションが地理的レプリケーション属性（または配置ポリシー）を指定できる最小単位でもあります。私たちの配置仕様言語は、レプリカ構成の管理の責任を分離します。管理者は、レプリカの数とタイプ、およびこれらのレプリカが配置されるアドレス位置の 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 に欠けている行をまたぐトランザクションも頻繁に苦情を引き起こしました（led to frequent complaints）。Percolator を構築した理由の一部は、この問題を解決することです。一部の著者は、一般的な二段階コミットをサポートすることは高価すぎると考えています。なぜなら、それはパフォーマンスや可用性の問題を引き起こすからです。私たちは、アプリケーションプログラマーがトランザクションの乱用によってパフォーマンスのボトルネックが発生する場合にパフォーマンスの問題を処理する方が良いと考えています。Paxos を介して二段階コミットを実行することで、可用性の問題を軽減します。

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

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

spanner-figure4

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

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

ON DELETE CASCADEは、ディレクトリテーブルの 1 行を削除すると、すべての関連する子行が削除されることを示します。上の図は、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 は、各データセンターの一連のタイムマスター機械と各機械上のタイムスレーブプロセスによって実装されています。ほとんどのマスターには、専用のアンテナを備えた GPS 受信機が装備されています。これらのマスターは、物理的に隔離されており、アンテナ故障、無線干渉、欺瞞の影響を軽減します。残りのマスター（私たちはこれを Armageddon マスターと呼びます）は、原子時計を装備しています。原子時計はそれほど高価ではなく、Armageddon マスターのコストは GPS マスターのコストと同等です。

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

各デーモンは、複数のマスターをポーリングして、任意の 1 つのマスターノードに依存する脆弱性を減らします。一部は、データセンターの近くから選ばれた 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 クライアントの書き込みを区別することが重要です。たとえば、二段階コミットの 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}$ がいつ $s_{max}$ よりも早くなるかを説明します。放棄する前に、リーダーは $TT.after(s_{max})$ が true であることを保証する必要があります。

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

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

開始：コーディネーターリーダーは、書き込みトランザクション $T_{i}$ にタイムスタンプ $s_{i}$ を割り当てます。ここで、 $s_{i}$ は $e_{i}^{server}$ の計算後の $TT.now().latest$ 以上でなければなりません。参加者リーダーはここでは重要ではありません。次のルールの実装にどのように参加するかを説明します。
コミット待機：コーディネーターリーダーは、 $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 つのステップの間にあるトランザクションの場合、レプリカの $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$ となります。

読み取り専用トランザクションへのタイムスタンプの割り当て#

読み取り専用トランザクションの実行は 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 メッセージを送信して、参加者リーダーがそのトランザクションをタイムアウトさせないようにします。クライアントがすべての読み取り操作を完了し、すべての書き込み操作をキャッシュした後、二段階コミットを開始します。クライアントはコーディネーターグループを選択し、各参加者リーダーに commit メッセージを送信します：コーディネーター識別子とすべての書き込み操作を含みます。クライアント駆動の二段階コミットを使用することで、データを 2 回転送することを回避できます。

コーディネーターでない参加者（non-coordinator-participant）リーダーは、最初に書き込みロックを要求し、その後、すべてのタイムスタンプよりも大きい prepare タイムスタンプを選択します（単調性を保証します）。その後、Paxos を介して prepare 記録を追加します。各参加者は、その prepare タイムスタンプをコーディネーターに通知します。

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

任意のコーディネーター副本がコミット記録を適用する前に、コーディネーターリーダーは $TT.after(s)$ が true になるまで待機し、4.1.2 で説明したcommit-waitルールを遵守します。コーディネーターは $TT.now().latest$ に基づいてコミットタイムスタンプ 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 グループによって提供される場合、さまざまな選択肢があります。最も複雑な選択肢は、すべてのグループリーダーと 1 回の通信を行い、 $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 ベースのクエリ言語を取得し、システムコミュニティからは、スケ

且听风吟