> [!abstract] 概要(abstract 日本語訳) > 私たちは国や大陸をまたいで活動する組織が増えるなかで、ますます相互につながった世界に暮らしている。グローバルなユーザーベースに対応するため、組織は OLTP ワークロードを数百万人のユーザーにスケールできるクラウドベースのシステムへと従来型 DBMS を置き換えている。 > > CockroachDB は、こうしたグローバル OLTP ワークロードをサポートしながら高可用性と強一貫性を維持するために、ゼロから構築されたスケーラブルな SQL DBMS である。その名前の由来と同様に、CockroachDB はレプリケーションと自動復旧メカニズムによってあらゆる障害に耐える。 > > 本論文は CockroachDB の設計と、汎用ハードウェア上で一貫性のある地理分散トランザクションをサポートする独自のトランザクションモデルを提示する。データをレプリケートして分散させ、障害耐性と高性能を実現する方法、ならびに分散 SQL 層がデータベースクラスタのサイズに合わせて自動的にスケールしながらユーザーが期待する標準 SQL インターフェイスを提供する方法を説明する。最後に、包括的な性能評価と、CockroachDB ユーザーの事例研究をいくつか紹介し、過去 5 年間の CockroachDB 構築で学んだ教訓を述べる。 ## 論文情報 - **タイトル**: CockroachDB: The Resilient Geo-Distributed SQL Database - **著者**: Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Darnell, Bram Gruneir, Justin Jaffray, Lucy Zhang, Peter Mattis (Cockroach Labs, Inc.) - **媒体**: SIGMOD'20 — ACM SIGMOD International Conference on Management of Data - **発表**: 2020-06-14〜19、Portland, OR, USA (オンライン開催) - **DOI**: https://doi.org/10.1145/3318464.3386134 - **コード**: https://github.com/cockroachdb/cockroach (Business Source License → Apache 2.0 after 3 years) - **TLA+ 検証**: https://github.com/cockroachdb/cockroach/tree/master/docs/tla-plus/ParallelCommits ## 概要 CockroachDB(以下 CRDB)は [[Cockroach Labs]] が開発した商用のスケーラブル SQL DBMS で、地理分散 OLTP ワークロードを対象とする。設計目標は「フォールトトレランス」「地理分散パーティショニングとレプリカ配置」「高性能トランザクション」の 3 点である。PostgreSQL ワイヤープロトコルと SQL 方言を採用し、クラウド中立(cloud-neutral)でプライベートクラウドとパブリッククラウドを単一クラスタで混在させられる。 **Figure 1: グローバル CockroachDB クラスターの構成例** ![[_attachments/2026_Unknown_CockroachDB_Resilient_Geo_Distributed_SQL/fig01-global-cluster.png]] (Figure 1. US-east / EU-west / EU-south(オンプレ) / EU-east / AU-south / AU-north の 6 リージョンにわたるクラスター。R=レプリカ、R*=リースホルダーレプリカ。ゲーム会社の実事例デプロイメントビジョン。Source: Adapted from Figure 1.) ## 問題設定 グローバル企業が必要とする要件: 1. GDPR 準拠のためデータ主権(data domiciling)——欧州ユーザーのデータはEU域内に 2. ユーザーに近い場所へのデータ配置によるレイテンシ最小化 3. リージョン全体の障害にも対応するフォールトトレランス 4. データ異常を防ぐ SQL + 直列化可能トランザクション これらを専用ハードウェア(Spanner の TrueTime 相当)なしに汎用クラウドサーバーで実現することが課題である。 ## システムアーキテクチャ CRDB は Shared-Nothing アーキテクチャを採用し、全ノードがストレージと計算を両方担う。クライアントはクラスタの任意のノードへ接続可能。単一ノード内部は 5 層構造である。 ### 層構造 | 層 | 役割 | |---|---| | SQL | パーサ・オプティマイザ・実行エンジン。KV ストアの抽象化のうえで動作 | | Transactional KV | MVCC による原子性と直列化可能分離の保証 | | Distribution | 論理キー空間を提示。Range パーティショニング(~64 MiB)でデータを分割 | | Replication | Raft 合意によるデータのレプリカ管理 | | Storage | RocksDB ベースのローカルディスク KV ストア | ### Range CRDB のデータ分散の最小単位を **Range** と呼ぶ。~64 MiB の連続したキー範囲を 1 Range とし、大きくなれば分割・小さくなればマージ・負荷に応じてノード間を移動する。Range のインデックスは 2 レベルのシステム Range に保持され、高速なキールックアップを提供する。 ## レプリケーションとフォールトトレランス ### Raft による合意(§2.2.1) 各 Range は Raft グループを形成する。書き込みの最小単位は **コマンド**(storage engine への低レベル変更列)であり、Raft がコマンドを一貫した順序でログに記録する。各レプリカはローカルに独立して storage engine へ適用する。 **Range リース**: Raft グループ内の 1 レプリカが **リースホルダー**(通常 Raft リーダー)として機能し、権威ある最新読み取りと書き込み提案を独占する。ノードの生存確認のため 4.5 秒ごとにハートビートを送信する。 ### 自動リカバリと負荷再分散(§2.2.2) - **短期障害**: Raft が多数派レプリカを維持する限りシームレスに動作継続。障害レプリカはゴシッププロトコルで検出し、復旧後はスナップショット送信または Raft ログ差分で追いつかせる。 - **長期障害**: 過少レプリケーション Range を自動検出し新規レプリカを生成。GCP/AWS インスタンス障害ドメインをまたいで配置。 ### データ配置ポリシー(§2.3) | ポリシー | 特性 | |---|---| | Geo-Partitioned Replicas | テーブルをアクセスリージョンでパーティション化しそのリージョンに固定。高速なイントラリージョン読み書き。リージョン全体障害時は非可用 | | Geo-Partitioned Leaseholders | リースホルダーをアクセスリージョンに固定、残余レプリカは他リージョン。高速ローカル読み取り + リージョン障害耐性。クロスリージョン書き込みが遅くなる | | Duplicated Indexes | 全リージョンにセカンダリインデックスを複製しリースホルダーをリージョン固定。最低レイテンシ読み取り + リージョン障害耐性。書き込み増幅あり | ## トランザクションモデル CRDB は MVCC ベースの独自プロトコルで直列化可能分離を実現する。Spanner とは設計が根本的に異なる。 ### 概要(§3.1) - SQL トランザクションはゲートウェイノードで開始し、**トランザクションコーディネーター**として機能する。 - MVCC でコミットタイムスタンプを全読み書きに割り当て、システム全体のトランザクションを全順序化する。 - **Write Pipelining**: 依存しないキーへの操作を直列化を保ちながら並列発行。依存関係があると "パイプラインストール" が生じる。 - **Parallel Commits**: コミット時に staging ステータスを書き込み、コミットステータスの複製とライト残留の確認を並列化。追加の合意ラウンドを回避。 **Figure 2: Parallel Commits の性能効果** ![[_attachments/2026_Unknown_CockroachDB_Resilient_Geo_Distributed_SQL/fig02-parallel-commits-performance.png]] (Figure 2. セカンダリインデックス数(0〜5)に対するスループット(上)とレイテンシ(下)の比較。Parallel Commits は 2PC と比べてスループット最大 72% 向上、p50 レイテンシ最大 47% 削減。3 サーバー・3 リージョン構成。Source: Adapted from Figure 2.) ### 原子性保証 — Write Intents(§3.2) 全書き込みは **write intent**(暫定値)として保存され、コミット前は通常の MVCC ペアと区別できる。intent には **transaction record**へのポインタが付き、pending/staging/committed/aborted の状態を一括公開する。Parallel Commits の staging 状態では、全 intent のレプリケーション確認でコミット成立とみなし、障害時でも contending トランザクションが解決できる。 ### 並行制御(§3.3) | 衝突種別 | 動作 | |---|---| | 書き込み→読み取り(write-read) | 低タイムスタンプ intent に遭遇した読み取りはファイナライズを待機 | | 読み取り→書き込み(read-write) | 書き込みが読み取りより低タイムスタンプなら commit_ts を進める | | 書き込み→書き込み(write-write) | 低タイムスタンプ intent はファイナライズを待機。デッドロック検知で循環を解消 | ### Read Refresh(§3.4) commit_ts を進める必要が生じたとき、過去の読み取り集合を再スキャンし、タイムスタンプ区間 `(ta, tb]` に MVCC 値が落ちていないことを確認する(PostgreSQL SSI の rw-antidependency 追跡に相当)。成功すれば新タイムスタンプで続行、失敗すればリトライ。これが CRDB の楽観的並行制御の核であり、Spanner の commit wait の代替となる。 ### Follower Reads(§3.5) リースホルダーが **クローズドタイムスタンプ**(現在時刻の ~2 秒前)を定期的に発行し、非リースホルダーレプリカがそれ以前のタイムスタンプの読み取りを処理できるようにする。`AS OF SYSTEM TIME` クエリで明示的に指定。 ## クロック同期 ### Hybrid Logical Clock(§4.1) 各ノードは **HLC**(Hybrid Logical Clock)を保持する。物理時刻(NTP / Amazon Time Sync Service で同期した粗いシステムクロック)と Lamport 論理時刻を組み合わせる。最大許容オフセットはデフォルト 500 ms。 HLC の 3 特性: 1. **因果関係追跡**: ノード間メッセージに HLC タイムスタンプを添付し、受信で更新。リース不整合(disjointness)は HLC を通じた因果移転で強制される 2. **厳密単調増加**: プロセス再起動後も最大クロックオフセット待機で保証 3. **自己安定**: 一時的クロックスキューがあっても通信があれば HLC は収束 ### 不確実性区間と単一キー線形化可能性(§4.2) 各トランザクションは commit_ts から `[commit_ts, commit_ts + max_offset]` の **不確実性区間** を持つ。区間内のキー値は "過去の書き込み" とみなし、uncertainty restart でタイムスタンプを進める。これにより **単一キー線形化可能性**を保証する。 > [!contradiction] [[外部一貫性]]との比較 > Spanner([[@2013__TOCS__Spanner - Google's Globally Distributed Database]])は TrueTime commit wait で **厳密直列化可能性(strict serializability)** を達成するが、CRDB は**単一キー線形化可能性のみ**を保証する。異なるゲートウェイノードを経由した因果依存トランザクションで、スキューが max_offset を超えると陳腐化読み取りが起こりえる。CRDB は各ノードがクロックオフセットを監視し、80% 超過で自己終了して問題を緩和する。 クロックスキューが max_offset 外になっても **直列化可能分離**は両方のリース保護機構(リース区間チェック + Raft ログシーケンス番号チェック)で維持される。 ## SQL 層 ### データモデル(§5.1) 全テーブル・インデックスは 1 つ以上の Range に格納される。すべてのユーザーデータは順序付きインデックスとして格納され、プライマリインデックス(主キーでキー付け)と任意数のセカンダリインデックスを持つ。ハッシュインデックスで特定キーへの負荷集中(ホットスポット)を回避できる。 ### クエリオプティマイザ — Optgen(§5.2) Cascades スタイルオプティマイザが 200 超の変換ルールで実行計画空間を探索する。ルールは **Optgen**という DSL で記述し Go にコンパイルする。地理分散を意識した最適化として: - テーブルパーティション情報からフィルタを推論してより選択的なインデックススキャンを有効化 - コスト計算にデータ分散を考慮し、ゲートウェイノードに近いインデックスレプリカを優先 ### 分散クエリ実行(§5.3) 読み取りクエリはゲートウェイ単独モードまたは**分散モード**で実行。物理プランニング段階で論文の DAG(有向非循環グラフ)に変換され、TableReader をデータ保持ノードに分散配置することで、フィルタ・結合・集計を可能な限りデータに近いノードで処理する。 **Figure 3: 分散ハッシュ結合の物理プラン** ![[_attachments/2026_Unknown_CockroachDB_Resilient_Geo_Distributed_SQL/fig03-distributed-hash-join.png]] (Figure 3. 3 ノードクラスター上での 2 テーブル(a, b)の分散ハッシュ結合。テーブル a の Range が Node 1 と Node 3 に分散し、ハッシュでシャッフル後に各ノードでローカル HashJoiner が結合。結果をゲートウェイで Union。Source: Adapted from Figure 3.) 実行エンジンは 2 種類: - **行単位エンジン**: Volcano モデル。全 SQL 機能をサポート - **ベクトル化エンジン**: MonetDB/X100 インスパイア。個々のオペレータで 2 桁の高速化、TPC-H で最大 4 倍 ### スキーマ変更(§5.4) オンラインスキーマ変更を F1 方式で実装。スキーマ変更を増分変化の列に分解し、クラスター全体で最大 2 バージョンの同時共存を許容することで、ローリング中もデータ一貫性を維持する。 ## 実験結果 ### スケーラビリティ(§6.1) **Figure 4: vCPU あたりスループット(垂直・水平スケーリング)** ![[_attachments/2026_Unknown_CockroachDB_Resilient_Geo_Distributed_SQL/fig04-throughput-per-vcpu.png]] (Figure 4. Sysbench OLTP 挿入とポイントセレクトの vCPU あたりスループット。6〜1728 vCPU にわたってほぼ一定——垂直スケーリング(3 ノード, AWS c5d 各サイズ)と水平スケーリング(c5d.9xlarge, 3〜48 ノード)の双方で線形スケール。Source: Adapted from Figure 4.) TPC-C 性能 (v19.2.0): | ウェアハウス | Max tpmC | 効率 | NewOrder p90 | |---|---|---|---| | 1,000 | 12,474 | 97.0% | 39.8 ms | | 10,000 | 124,036 | 96.5% | 436.2 ms | | 100,000 | 1,245,462 | **98.8%** | 486.5 ms | Amazon Aurora は 10,000 ウェアハウスで効率 7.3% まで低下。CRDB は 100,000 ウェアハウスでも 98.8% 効率を維持。(Source: Table 1) **Figure 5: クロスノード調整ありの TPC-C スケーリング** ![[_attachments/2026_Unknown_CockroachDB_Resilient_Geo_Distributed_SQL/fig05-tpcc-scaling.png]] (Figure 5. リモートトランザクション割合(0%/10%/100%)・レプリカ数(1/3/5)・ノード数(1〜48)の組み合わせでの最大 tpmC。レプリケーションで最大 57%、分散トランザクションでさらに最大 46% のオーバーヘッドが生じるが、すべて線形スケール。Source: Adapted from Figure 5.) ### マルチリージョン可用性(§6.2) **Figure 6: AZ/リージョン障害時の各配置ポリシー性能** ![[_attachments/2026_Unknown_CockroachDB_Resilient_Geo_Distributed_SQL/fig06-multiregion-availability.png]] (Figure 6. TPC-C 1,000 ウェアハウス。点線間は AZ 障害と回復・リージョン障害と回復の各フェーズ。Geo-Partitioned Leaseholders のみリージョン障害に耐える(tpmC の維持)が、p90 レイテンシが高い。Duplicated Indexes は平常時に最低レイテンシ。Source: Adapted from Figure 6.) ### Spanner との比較(§6.3) **Figure 7: YCSB スループット(CRDB vs Cloud Spanner)** ![[_attachments/2026_Unknown_CockroachDB_Resilient_Geo_Distributed_SQL/fig07-ycsb-vs-spanner.png]] (Figure 7. YCSB A〜F のスループット(3 サーバーと 15 サーバー)と軽負荷時のレイテンシ比較。CRDB は Workload A(更新ヘビー・ジップ分布)を除くほぼ全ワークロードで Spanner を大幅に上回る。Spanner の commit wait に起因する高レイテンシが顕著。Source: Adapted from Figure 7.) ## 教訓(§7) | # | 教訓 | 内容 | |---|---|---| | 7.1 | Raft のハートビート削減 | 数十万の Raft グループで heartbeat をノード単位にコアレス + 非アクティブグループを一時停止 | | 7.2 | Joint Consensus | 単一メンバー変更では 3 リージョン可用性が一時的に失われる。Joint Consensus で解決 | | 7.3 | スナップショット分離の削除 | write skew を防ぐため SNAPSHOT を SERIALIZABLE のエイリアスに。SNAPSHOT は安全な悲観的ロックを必要とし複雑 | | 7.4 | PostgreSQL 互換の摩擦 | ドライバ再利用でクライアントが CRDB 固有のトランザクションリトライを処理する必要があり摩擦が生じる。CRDB 専用クライアントドライバを開発中 | | 7.5 | バージョンアップの落とし穴 | レプリカ間のコード差異を防ぐため、評価フェーズを Raft 提案前に移動(効果の複製・適用へ変更) | | 7.6 | Follow the Workload の不採用 | 自動リースホルダー移動は実際にはほとんど使われない。手動配置制御で十分なケースが多い。適応的技術は予測不可能な動作になりがち | ## 強み・弱点 **強み** - 専用ハードウェアなしに直列化可能分離・高可用性・地理分散を両立 - TPC-C 100,000 ウェアハウスで Aurora を大幅に凌ぐ効率 - Parallel Commits で commit の追加コンセンサスラウンドを回避 - PostgreSQL 方言採用でエコシステムを活用 - クラウド中立(マルチクラウド・ハイブリッド対応) - TLA+ による Parallel Commits の形式検証 **弱点・課題** - 厳密直列化可能性(strict serializability)は保証しない——外部低レイテンシ通信チャネルがある場合に問題になりうる - 高コンテンション・ジップ分布ワークロード(YCSB Workload A)でスケールしにくい(論文時点) - Transaction retry を要するため PostgreSQL クライアントと完全互換でない - Follower reads は ~2 秒のラグを受け入れる必要がある ## 関連 - ソース: [[@2013__TOCS__Spanner - Google's Globally Distributed Database]] / [[@2017__SIGMOD__Amazon Aurora - Design Considerations for High Throughput Cloud-Native Relational Databases]] / [[@2024__SIGMOD__Amazon MemoryDB - A Fast and Durable Memory-First Cloud Database]] - エンティティ: [[CockroachDB]] / [[Cockroach Labs]] / [[Rebecca Taft]] - 概念: [[分散トランザクション]] / [[外部一貫性]] / [[ハイブリッド論理クロック]] / [[地理分散SQLデータベース]] / [[OLTPシステムアーキテクチャ]] ## 出典 - Rebecca Taft ほか. "CockroachDB: The Resilient Geo-Distributed SQL Database." SIGMOD'20, June 2020. DOI: 10.1145/3318464.3386134