> [!abstract] 概要(ACM TOCS abstract の日本語訳) > Spanner は Google のスケーラブルなマルチバージョン・グローバル分散・同期レプリケーションデータベースである。世界規模でデータを分散させ、外部一貫性のある分散トランザクションをサポートする最初のシステムである。本論文では、Spanner の構造・機能セット・各設計決定の根拠、および時刻の不確実性を公開する新しい時刻 API について説明する。この API とその実装は、外部一貫性および多様な強力な機能、すなわち過去へのノンブロッキング読み取り・ロックフリースナップショットトランザクション・Spanner 全体にわたるアトミックなスキーマ変更を支えるうえで不可欠である。 ## 論文情報 - **タイトル**: Spanner: Google's Globally Distributed Database - **著者**: James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh(責任著者), Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, Dale Woodford(全員 Google, Inc.) - **媒体**: ACM Transactions on Computer Systems(TOCS), Vol. 31, No. 3, Article 8(August 2013)。元は OSDI 2012 論文。 - **DOI**: http://dx.doi.org/10.1145/2491245 ## 概要 Spanner はグローバル分散・同期レプリケーション・マルチバージョンのデータベースであり、Bigtable 的なバージョン付きキーバリューストアからスキーマ付き半リレーショナルデータベースへ進化した。最大の設計上の革新は **TrueTime API** を用いた[[外部一貫性]]保証であり、グローバルスケールで意味のあるコミットタイムスタンプを割り当てることで、「T1 がコミットしてから T2 が開始した」ならば必ず T1 のタイムスタンプ < T2 のタイムスタンプが成立する。これにより、一貫したバックアップ・一貫した MapReduce 実行・アトミックスキーマ変更がグローバルスケールで可能となる。 ## 問題設定 - **入力**: 世界中のデータセンターに分散された何百万台ものサーバーにまたがる関係データ - **出力**: 外部一貫性のある読み書きトランザクション・ロックフリースナップショット読み取り・SQL クエリ - **前提**: Google 社内の分散クラスタ管理ソフトウェア(GPS と原子時計を使った TrueTime 実装)が利用可能 Bigtable はクロスデータセンターでは結果整合性レプリケーションしか提供せず、クロスロウトランザクションも欠如していた。Megastore は同期レプリケーションを持つが書き込みスループットが低く、長寿命リーダーを持たないため Paxos グループのスループットが毎秒数件程度に制限される。F1(Google の広告バックエンド)は MySQL のシャーディングを人手で管理しており、再シャーディングに 2 年以上を要していた。 ## 提案手法 ### アーキテクチャ Spanner の展開単位を **universe** と呼ぶ。universe は複数の **zone** から構成され、各 zone は Bigtable のデプロイに相当する行政的配置単位である。 **Figure 1: Spanner サーバー構成** ![[_attachments/1974/fig01-server-organization.png]] (Figure 1. Spanner サーバーの構成。universemaster と placement driver がシングルトンとして存在し、各 zone に zonemaster・location proxy・spanserver が配置される。) 各 zone は 1 つの zonemaster と 100〜数千の spanserver を持つ。universemaster はステータス表示用コンソール、placement driver はデータを zone 間で移動させる自動化デーモンである。 ### spanserver ソフトウェアスタック **Figure 2: spanserver ソフトウェアスタック** ![[_attachments/1974/fig02-spanserver-stack.png]] (Figure 2. spanserver のソフトウェアスタック。各 spanserver は 100〜1000 個の tablet を管理し、それぞれに Paxos ステートマシンと lock table・transaction manager が重なる。) 各 spanserver は 100〜1000 個の **tablet** を管理する。tablet は `(key:string, timestamp:int64) → string` のマッピングを実装し、Bigtable と異なりタイムスタンプが付与される。tablet の状態は分散ファイルシステム **Colossus**(GFS の後継)に保存される。 各 tablet の上に **Paxos ステートマシン**が 1 つ実装される。Paxos はパイプライン化されており WAN レイテンシ下でもスループットを確保する。リーダーになった replica は **lock table**(二相ロック用)と **transaction manager**(分散トランザクション用)を持つ。 ### ディレクトリと配置 **ディレクトリ(directory)** は共通プレフィックスを持つ連続したキーの集合であり、データ配置とデータ移動の最小単位である。 **Figure 3: Paxos グループ間のディレクトリ移動** ![[_attachments/1974/fig03-directory-movement.png]] (Figure 3. dir2 が Group 1 から Group 2 へ Paxos グループをまたいで移動する様子。ディレクトリは 50MB 程度なら数秒で移動できる。) **Movedir** がバックグラウンドでディレクトリを移動する。クライアント操作中でも移動可能で、大部分を移動してから残りを 1 つのトランザクションでアトミックに完了させる。ディレクトリの地理的配置制御はアプリケーションが指定でき、ユーザー A のデータは欧州 3 レプリカ、ユーザー B のデータは北米 5 レプリカといった設定が可能である。 ディレクトリが巨大になると **fragments** に分割され、異なる Paxos グループから提供される。Movedir は実際にはフラグメント単位で移動する。 ### データモデル Spanner は半リレーショナルテーブル・クエリ言語・汎用トランザクションを提供する。 **Figure 5: インターリーブされたテーブルレイアウト** ![[_attachments/1974/fig05-interleaved-table.png]] (Figure 5. Users テーブルと Albums テーブルがディレクトリ 3665 と 453 として格納されている様子。INTERLEAVE IN PARENT 宣言により、関連する子行が親行の近くに物理配置される。) `INTERLEAVE IN PARENT ... ON DELETE CASCADE` 宣言で階層テーブルを定義すると、親の行と子の行が物理的に同一ディレクトリに配置され、シャード分散データベースでのローカリティを確保できる。各テーブルは必ず主キーを持ち、主キーがその行の名前となる。 ## TrueTime **Table I: TrueTime API** | メソッド | 戻り値 | |---|---| | `TT.now()` | `TTinterval: [earliest, latest]` | | `TT.after(t)` | t が確実に過去なら true | | `TT.before(t)` | t が確実に未来なら true | TrueTime は時刻を単一値でなく**不確実性区間**として表現する。ε = 区間幅の半分(平均 4ms、最大 7ms 程度)。GPS マスターと原子時計(「Armageddon マスター」)を各データセンターに置き、タイムスレーブデーモンが Marzullo のアルゴリズムで嘘つきを排除しながら同期する。ドリフトレートは 200μs/sec を上限に設定。 ## 並行制御 ### 新規性:外部一貫性のタイムスタンプ保証 Spanner は 3 種類の操作をサポートする(Table II): 1. **読み書きトランザクション(RW)**:悲観的並行制御(二相ロック)。リーダーでのみ実行。 2. **スナップショットトランザクション(RO)**:ロックフリー。タイムスタンプは先読み宣言が必要。リーダー以外でも実行可能。 3. **スナップショット読み取り**:ロックフリー。クライアント指定タイムスタンプまたは古さ上限で実行。 **外部一貫性の証明**(commit wait による): ``` s1 < tabs(e1^commit) … commit wait tabs(e1^commit) < tabs(e2^start) … 仮定 tabs(e2^start) ≤ tabs(e2^server) … 因果関係 tabs(e2^server) ≤ s2 … Start ルール ∴ s1 < s2 … 推移律 ``` **Commit Wait ルール**: コーディネーターリーダーは `TT.after(si)` が真になるまでコミットを公開しない。期待待機時間は少なくとも 2ε。 **Paxos リーダーリース**: デフォルト 10 秒。リース区間の不整合性(disjointness)不変条件を TrueTime を使って証明しており、余分なログ書き込み不要で実現される。 ### スキーマ変更トランザクション TrueTime を使って未来のタイムスタンプでスキーマ変更を登録する。グループ数が百万になっても大半の操作をブロックせずに実行できる。 ## 実験設定 - 計測マシン: 4GB RAM / 4 コア(AMD Barcelona 2200MHz)の spanserver - クライアントは別マシン。各 zone に 1 spanserver。ネットワーク距離 < 1ms。 - 50 Paxos グループ / 2500 ディレクトリ / 4KB 読み書き。 ## 実験結果 **Table III: マイクロベンチマーク(レイテンシ ms / スループット Kops/sec)** | レプリカ数 | 書き込みレイテンシ | スナップショットトランザクション | スナップショット読み取り | 書き込みスループット | |---|---|---|---|---| | 1D(commit wait 無効) | 10.1±0.3 | — | — | 4.2±0.03 | | 1 | 14.1±1.0 | 1.3±0.04 | 1.3±0.02 | 4.2±0.07 | | 3 | 14.3±0.5 | 1.4±0.08 | 1.4±0.08 | 1.8±0.03 | | 5 | 15.4±2.3 | 1.4±0.07 | 1.6±0.04 | 1.2±0.2 | - Commit wait ≈ 4ms、Paxos レイテンシ ≈ 10ms(1D と 1 レプリカの差から推定) - レプリカ増加でスナップショット読み取りスループットは線形に増加(どのレプリカでも実行可能なため) - 書き込みスループットはレプリカ増加で線形に減少(Paxos の作業量が増えるため) **Table IV: 2 フェーズコミットのスケーラビリティ** - 参加者数 50 まではレイテンシが許容範囲(mean 33.8ms / p99 62.4ms)。100 参加者から顕著に増加(mean 55.9ms / p99 88.9ms)。 **可用性実験(Figure 5: キル時のスループットへの影響)** - 非リーダーゾーン(Z2)のキル: 影響なし - リーダーゾーン(Z1)のソフトキル(引継ぎ通知あり): 約 3〜4% のスループット低下 - リーダーゾーン(Z1)のハードキル: スループットがほぼ 0 に落ち、約 10 秒後(リースの最大有効期間)に回復 **F1(本番ワークロード、Table VI)** - 全読み取り: mean 8.7ms / std 376.4ms(21.5B 件/24 時間) - シングルサイトコミット: mean 72.3ms / std 112.8ms(31.2M 件) - マルチサイトコミット: mean 103.0ms / std 52.2ms(32.1M 件) ## 考察 **結果の解釈**: 1-replica と 1D の差がコミット待機 ≈ 4ms を示す。レプリカ増加でのスナップショット読み取りスループット向上は、どのレプリカでも実行可能という設計の直接的成果。F1 のデータは、マルチサイトコミット(103ms)がシングルサイト(72ms)の約 1.4 倍というコストを示す。 **TrueTime の信頼性**: 機械統計上、故障 CPU は故障クロックの 6 倍多い。クロック問題は Spanner が依存する他のソフトウェアと同程度に信頼性があると著者は主張する。 ## 強み / 弱点・課題 **強み**: - 外部一貫性を世界規模で保証する最初のシステム。数学的証明付き。 - アトミックスキーマ変更を百万グループ規模で非ブロッキングに実行。 - ディレクトリ単位の地理的配置制御で、ユーザー単位のレプリカポリシーが可能。 - スナップショットトランザクションによる過去の一貫した読み取り(バックアップ・MapReduce に有用)。 **弱点・課題**: - ノードローカルのデータ構造は複雑な SQL クエリに対するパフォーマンスが低い(単純なキーバリューアクセス向けに設計)。 - 2PC の参加者が 100 を超えるとレイテンシが顕著に増加。 - ε が大きくなるとコミット待機が延長されパフォーマンスが劣化。 - セカンダリインデックスの自動管理が当時未実装(F1 は独自実装)。 - Paxos のインコンフィグレーション変更が未サポート(Movedir での全データ再移動で対処)。 ## 関連 - エンティティ: [[James C. Corbett]] / [[Jeffrey Dean]] / [[Sanjay Ghemawat]] / [[Google]] - 概念: [[外部一貫性]] / [[TrueTime]] / [[分散トランザクション]] - 先行技術: [[Bigtable]]・Megastore(Google 内前身) - 関連 MOC: [[structures/Systems for ML - MOC]] ## 出典 - `.raw/papers/1974.pdf` — ACM TOCS 2013 掲載版(OSDI 2012 論文の軽微な改訂) - DOI: http://dx.doi.org/10.1145/2491245