> [!abstract] 概要(abstract 日本語訳) > F1 は Google の AdWords ビジネスを支えるために Google が構築した分散リレーショナルデータベースシステムである。F1 は高可用性・Bigtable のような NoSQL システムのスケーラビリティ・従来の SQL データベースの一貫性と使いやすさを兼ね備えたハイブリッドデータベースである。F1 は Spanner 上に構築されており、Spanner がデータセンター間の同期複製と強一貫性を提供する。同期複製によりコミットレイテンシは高くなるが、我々は階層スキーマモデルと構造化データ型、そしてスマートなアプリケーション設計によってそのレイテンシを緩和する。F1 はまた、完全に機能する分散 SQL クエリエンジンと自動変更追跡・配信機能も備える。 ## 論文情報 - **タイトル**: F1: A Distributed SQL Database That Scales - **著者**: Jeff Shute, Radek Vingralek, Bart Samwel, Ben Handy, Chad Whipkey, Eric Rollins, Mircea Oancea, Kyle Littlefield, David Menestrina, Stephan Ellner, John Cieslewicz, Ian Rae(University of Wisconsin-Madison)*, Traian Stancescu, Himani Apte（*のみ外部所属、他は Google） - **媒体**: Proceedings of the VLDB Endowment (PVLDB), Vol. 6, No. 11, pp. 1068–1079 - **発表年**: 2013（VLDB 2013: Riva del Garda, Italy, 2013-08-26〜30） - **URL**: http://www.vldb.org/pvldb/vol6/p1068-shute.pdf ## 概要 F1 は Google の AdWords 広告システムを支えるためにゼロから設計されたグローバル分散 OLTP/OLAP データベースである。スケールアウトが困難だったシャード MySQL の後継として 2012 年初頭に本番稼働を開始し、100 TB 超・毎日数十兆行スキャン・可用性 5 ナイン(99.999%)を達成する。[[分散トランザクション]] の基盤として [[Spanner]] を採用し、その上に階層スキーマ・分散 SQL エンジン・非ブロッキングスキーマ変更・変更履歴という独自レイヤーを追加した。 ## 問題設定 - **入力**: OLTP/OLAP 混在ワークロード、100 TB 超のデータ、数百のアプリ・数千のユーザーが共有 - **課題**: シャード MySQL はスケールが困難で、ユーザーは複雑なジョインのためにシャードを慎重に設計しなければならず、再シャーディングがアプリを壊す。スキーマ変更時のダウンタイムも許容不可 - **設計目標**: ①スケーラビリティ(リソース追加だけで自明にスケール)、②可用性(計画・非計画の停止ゼロ)、③強一貫性(ACID)、④使いやすさ(フル SQL + セカンダリインデックス) ## 提案手法 ### アーキテクチャ **Figure 1: F1 の基本アーキテクチャ(2 データセンター構成)** ![[_attachments/p1068-shute/fig01-architecture.png]] (Figure 1. F1 Client → Load Balancer → F1 Master / F1 Server + Slave Pool → Spanner → CFS の 2 層構造。F1 Server はステートレスで、データは持たず Spanner からリモート読み書きする。Source: Shute et al. 2013, p.1069.) F1 はクライアントライブラリ・ロードバランサ・F1 Server(ステートレス)・F1 Master(スレーブプール管理)・Slave Pool(分散クエリ実行)・Spanner・Colossus File System(CFS)で構成される。**F1 Server はデータを保持しない**ため、追加・削除でデータ再配置が不要。Spanner Server はデータセンター内の CFS とのみ通信し、CFS はグローバル複製しない。 ### 階層スキーマとクラスタ化ストレージ **Figure 2: 伝統的リレーショナルスキーマ vs 階層クラスタ化スキーマ** ![[_attachments/p1068-shute/fig02-hierarchical-schema.png]] (Figure 2. 左: 伝統的スキーマでは結合に複数マシンにまたがる読み取りが必要。右: 階層スキーマでは Customer→Campaign→AdGroup を同一 Spanner ディレクトリに物理クラスタ化し、単一リクエストで読み取れる。Source: Shute et al. 2013, p.1070.) F1 のデータモデルはテーブルを論理階層で組織化し、子テーブルの行を親テーブルの行に**インタリーブ(混在)** して物理的に格納する。子テーブルの主キーは親テーブルの主キーを前置キーとして含む(例: `AdGroup(CustomerId, CampaignId, AdGroupId)`)。 この階層スキーマにより: - **並列読み取り**: 主キー前置プロパティにより Customer/Campaign/AdGroup を並列に開始できる - **単一範囲読み取り**: AdGroup を主キー順の範囲読み取りで一括取得可能(インデックス不要) - **単一 Spanner リクエスト**: 同一ディレクトリのデータを 1 リクエストで取得可能 - **2PC 回避**: 単一ルートに限定されたトランザクションは 2PC を回避し、コミットレイテンシを半減 ### Protocol Buffer 列型 F1 はテーブル列に Protocol Buffer(protobuf)型をネイティブ対応する。繰り返しフィールド(repeated fields)を子テーブルの代替として使用でき、アプリとDB間のインピーダンスミスマッチを解消。SQL は `PROTO JOIN` 構文で repeated field をバーチャル子テーブルとして JOIN できる。 ### インデックス 全インデックスはトランザクション一貫性を持ち、Spanner に別テーブルとして保存される(インデックスキー + 主キーの連結)。 | 種別 | キー前置 | 配置 | 2PC | |---|---|---|---| | ローカルインデックス | ルート行主キーを含む | ルート行と同一ディレクトリ | 不要 | | グローバルインデックス | ルート行主キーを含まない | 複数ディレクトリに分散 | 必要(参加者追加) | グローバルインデックスへの大量挿入(1,000 行 → 100 以上の 2PC 参加者)は性能劣化するため、スキーマ上でグローバルインデックスを最小限に抑えることを推奨。 ### 非ブロッキングオンラインスキーマ変更 F1 全体にわたる同期スキーマ変更は応答時間に壊滅的な影響を与えるため、**スキーマ変更は非同期に各サーバーへ適用**される。これが許容される理由は: 1. **最大 2 バージョン同時有効**: lease 付きスキーマで、全サーバーが current か next のどちらか一方のみ使用 2. **互換フェーズ分割**: スキーマ変更を「delete-only → write-only → バックフィル → read-write」の互換フェーズ列に分割し、各フェーズ遷移を安全に実行。これにより「インデックスエントリの孤立」などの破損を防ぐ ### トランザクションモデル F1 は 3 種類のトランザクションを提供し、ACID 保証の下で混在利用できる: | 種別 | ロック | レイテンシ | 用途 | |---|---|---|---| | スナップショット | なし(snapshot read) | 最低(ローカルレプリカ) | SQL クエリ・MapReduce(デフォルト) | | 悲観的 | Spanner 二相ロック | 中(ステートフル・サーバー固定) | 高競合シナリオ | | 楽観的 | なし(読み取りフェーズ)→短い書き込みフェーズ | 可変(競合時は失敗) | デフォルト(ORM) | 楽観的トランザクションの仕組み: 各行に「最終更新タイムスタンプ」を hidden lock column として保持。書き込み時に再読み取りして競合を検出し、差異があれば abort。 楽観的トランザクションの利点: - 不正クライアントへの耐性(ロックを保持しない) - 任意の長さの読み取りフェーズ(エンドユーザー操作待ちを含む) - サーバー側でのリトライ透過化(自己完結した commit) - サーバー障害後の別サーバーへの接続切り替え - Speculative writes(MapReduce で読んだ値に基づく書き込み) 欠点: 挿入ファントム(insertion phantom)を防げない、高競合カウンタ系は悲観的ロックが有効。 ### 分散 SQL クエリエンジン **Figure 3: 分散クエリプラン(AdWords サンプルクエリ)** ![[_attachments/p1068-shute/fig03-distributed-query-plan.png]] (Figure 3. Scan → Lookup Join → Repartition(HASH) → Hash Join → Repartition(HASH) → Aggregation → Coordinator の DAG 構造。丸角ボックスが別マシンのプロセス。Source: Shute et al. 2013, p.1075.) F1 SQL は中央実行(OLTP 向け・単一 F1 Server)と**分散実行**(OLAP 向け・Slave Pool 使用)を自動選択する。分散クエリの特徴: - **データが常にリモート**: Spanner はリモートストレージ。ネットワークレイテンシをバッチング+パイプラインで緩和 - **ランダム分散**: Spanner の partitioning は任意でレンジ統計が使えない → **ハッシュ分散のみ** を採用(レンジ分散は使わない) - **Lookup Join**: 外表から 50 MB または 10 万キー分バッチしてから内表を一括検索。非同期並列読み取りでパイプライン停止を最小化 - **クラスタ結合(Cluster Join)**: 階層テーブルを単一 Spanner リクエストで読み取り、プレオーダー深さ優先順で受け取る interleaved ストリームをマージジョインで処理 - **分散ハッシュ結合・分散集約**: ハッシュキーで再分散 → 各ワーカーがインメモリハッシュテーブルで処理。メモリ不足時はディスクスピル - **パーティション化コンシューマ**: MapReduce 向けに複数クライアントが同一クエリ結果を並列シャード受信 クエリオペレーターはインメモリ実行でチェックポイントなし。障害時はクエリ全体を透過リトライ(1 時間以下のクエリは十分信頼性あり)。 ### 変更履歴(Change History) 全テーブルの変更をデータベースレベルで自動追跡。各トランザクションがルートテーブルのキーと変更前後の値を含む `ChangeBatch` Protocol Buffer を生成し、各ルートテーブルの子テーブルとして保存する。 - **Pub/Sub 連携**: 変更後に少なくとも 1 回の通知を保証(Spanner 内で commit と同時に publish)。チェックポイント(high-water mark)で exactly-once 処理を実現 - **分散キャッシュ**: コミットタイムスタンプを使って分散キャッシュの一貫性を保証。古いキャッシュは ChangeBatch を読み込んで差分更新 ## 新規性 従来の「スケーラビリティと一貫性はトレードオフ」という通説(Brewer の CAP 定理、Stonebraker の "SQL vs NoSQL" 論文)に対して、**実際に両立できることを本番系で示した**点が最大の新規性。技術的には Spanner の強一貫性・グローバル分散を基盤として、以下で MySQL 相当の使い勝手を実現: 1. 階層スキーマによるデータクラスタ化 → RPCラウンドトリップ削減 2. ORM のシリアル読み取り排除・並列/非同期化 → レイテンシ尾部分布の改善 3. スキーマ変更の非ブロッキング化 → 計画メンテナンスダウンタイム排除 4. Change History の DB 内実装 → アプリ側の破損した変更追跡ロジックを置換 Megastore([3]) の階層スキーマ・楽観的トランザクションとは類似するが、F1 は Spanner の外部一貫性を継承しており Megastore より強い一貫性保証を持つ。 ## 実験設定 本番系の実測値(AdWords プロダクション環境): - **構成**: 5 データセンター(米国大陸、東西海岸 各 2、中央 1)、5 way Paxos 複製 - **データサイズ**: 100 TB 超 - **ワークロード**: 数十万リクエスト/秒、毎日数十兆行スキャン ## 実験結果 | メトリクス | 値 | |---|---| | 読み取りレイテンシ | 5-10 ms | | コミットレイテンシ | 50-150 ms(データセンター間ネットワーク律速) | | 可用性 | 99.999%(5 ナイン、非計画停止含む) | | 対話型 Web アプリ P50 レイテンシ | 〜200 ms(MySQL と同等) | | 最小クエリ(OLTP) | <10 ms | - MySQL は平均 200-300 ms だが大量データでは数秒超の尾部。F1 は最小レイテンシが高いが尾部は中央値の数倍以内 - 大規模 OLAP クエリは MySQL より高速(より多くの並列度を活用できるため) - CPU コストは MySQL の約 10 倍(データ圧縮・解凍・ネットワーク転送のオーバーヘッド) ## 考察 - コミットレイテンシ 50-150 ms は「隠蔽」できるが、物理限界として残る。データセンターを近づければ低減可能だが可用性とのトレードオフ - グローバルインデックスは大規模トランザクション(1,000 行挿入 → 2PC 参加者 100 以上)でボトルネックになる。Megastore 的な非同期グローバルインデックスは一貫性を犠牲にするため採用せず、今後の課題 - Protocol Buffer 列はクエリ時に全フィールドを転送・パースするコストがある。将来的に Spanner 側でパース・フィールド選択を行い帯域削減を目指す - クエリ実行はチェックポイントなしのインメモリ実行のため、1 時間超のクエリは信頼性が低下する ## 強み / 弱点・課題 **強み**: - スケール・可用性・強一貫性・SQL の 4 要件を実際に満たした - F1 Server のステートレス設計によりデータ再配置なしにサーバーを追加・削除可能 - 変更履歴を DB ファーストクラス機能として実装し、アプリ側の破損したアドホック実装を置換 **弱点・課題**: - グローバルインデックスのスケーラビリティ(大量挿入時の 2PC 参加者爆発)は未解決 - CPU コストが MySQL の約 10 倍(圧縮・解凍・ネットワーク処理起因) - パーティション化コンシューマは分散リーダー間の水平依存(ディスクバッファリングが未実装)でスロー読み取りが全体に波及 - 長時間クエリ(>1 時間)はチェックポイントなしでの信頼性不足