Spanner：原子時計で世界規模の一貫性を実現する

この論文が解いた問題

横にスクロール

分散データベースには長らく、一つのジレンマが付きまとってきた。データを世界中のデータセンターに複製すれば、災害にも強く、どの地域のユーザーからも近い距離でアクセスできる。しかしその代償として、強い一貫性を諦めるのが常識だった。ネットワークで隔てられた拠点どうしが「今この瞬間の正しい順序」で合意するのは難しく、多くのシステムは結果整合性（eventual consistency）に流れ、アプリケーション側で不整合を吸収させてきた。この緊張関係はCAP定理としても語られ、分断耐性を持つ分散システムでは一貫性か可用性のどちらかを選ばざるを得ない、という形で受け止められてきた。

Spanner（Corbettら、2012年、Google）が挑んだのは、まさにこの通念だった。目標は野心的だ。世界中の複数リージョンにまたがってデータを複製しながら、なお外部一貫性（external consistency）を満たすトランザクションを提供する。外部一貫性とは、線形化可能性（linearizability）を分散トランザクションへ拡張した最も強い保証で、平たく言えば「あるトランザクションが別のトランザクションより前にコミットしたなら、その順序が全世界のどのクライアントから見ても保たれる」ことを意味する。しかも単なるキー・バリューではなく、スキーマ・SQL・二次索引を備えた本格的なデータベースとして、である。

なぜこれが難しいのか。核心は「時刻」にある。全世界に散らばったサーバーが、トランザクションの前後関係を一つの時間軸の上で決めようとしても、各マシンの物理時計は互いにずれている。数ミリ秒のずれでも、地球規模で同時に走る大量のトランザクションの順序を誤らせるには十分だ。従来はこのずれを恐れて、厳密な順序付けを諦めるか、単一のマスターへ書き込みを集約して事実上グローバルな並行性を捨てるかのどちらかだった。Spannerはこの時計のずれを消そうとするのではなく、ずれの大きさを正直に測り、設計に組み込むという逆転の発想で解いた。

核心アイデア

Spannerを支える第一の柱がTrueTime APIである。通常のプログラムが時刻を問うと、返ってくるのは一つの値だ。だがその値がどれだけ正確かは分からない。TrueTimeはここを根本から変える。時刻を一点ではなく、不確かさを含む区間として返すのだ。具体的には現在時刻を「[earliest, latest]」という区間で表し、真の絶対時刻は必ずこの範囲の中にある、と保証する。区間の幅はεと呼ばれ、これが時計の不確かさそのものである。

この保証を成り立たせるため、Googleは各データセンターにGPS受信機と原子時計という二種類の時刻源を配備した。GPSと原子時計は故障の仕方が独立しているため、片方が異常な値を出しても互いに検出でき、信頼できる基準時刻を安定して供給できる。各サーバーはこの基準に定期的に同期し、同期からの経過時間に応じて自分のεを見積もる。実運用ではεはおおむね数ミリ秒に収まり、しかも時間とともに変動する上限として厳密に管理される。時刻を点で扱う世界では「たぶん正しい」としか言えないが、区間で扱えば「確実にこの範囲内」と言い切れる。この違いがすべての土台になる。

第二の柱が、この区間を使ったcommit wait（コミット待機）である。あるトランザクションをコミットするとき、Spannerはまずコミットタイムスタンプを、そのときのTrueTimeが返す区間のlatest、すなわち最も遅い可能性のある時刻に選ぶ。そして即座に確定させるのではなく、TrueTimeの区間のearliestがそのタイムスタンプを追い越すまで、つまりεぶんだけ意図的に待ってからコミットを完了させる。この待機が終わった時点では、真の絶対時刻は必ずそのタイムスタンプを過ぎている。ゆえに、このトランザクションより後に開始される、いかなる場所のトランザクションも、より大きいタイムスタンプを持つことになる。

commit waitがもたらす結果は強力だ。タイムスタンプの大小関係が、そのまま現実のコミット順序と一致する。あるトランザクションが別のトランザクションより実時間で後にコミットしたなら、その事実がタイムスタンプの順序として全世界に反映される。時刻の順序がコミットの順序と一致する、という等式が地球規模で成立し、これが外部一貫性の正体である。数ミリ秒待つという一見素朴な代償で、グローバルな強一貫性を買っているのだ。εが小さいほど待ち時間は短くなるため、TrueTimeの精度を上げる工学的努力が、そのまま性能に直結する。

トランザクションとデータ複製の仕組みも押さえておきたい。Spannerはデータを行の範囲で分割し、各断片をPaxosグループとして複数リージョンに複製する。合意アルゴリズムのPaxos（Paxos論文を参照）が、複製間で書き込みの順序を一つに合意させ、一部のレプリカが落ちても処理を継続させる。単一のPaxosグループ内で完結する書き込みはそのグループの合意で済むが、複数のグループにまたがる書き込み、たとえば別々の断片にある二つの行を同時に更新する場合は、それらのグループをまたいで二相コミット（2PC）で束ねる。各グループのリーダーが参加者となり、全員の合意が取れて初めてトランザクション全体をコミットする。

これらを組み合わせることで、Spannerはスキーマ・SQL・分散トランザクションという、それまで大規模分散環境では両立しないとされた三つを、初めて同時に成立させた。開発者は世界規模のデータベースを、あたかも単一マシン上のリレーショナルデータベースであるかのように扱える。一貫性の面倒をアプリケーション側で抱え込む必要がない、という点にこそ最大の価値がある。

その後の影響

Spannerの登場は、分散データベースの常識を書き換えた。それまで一貫性とスケールは両立できない、というのは議論の前提として半ば当然視されていた。Spannerはその前提を、分散合意の理論ではなく、GPSと原子時計という物理的なインフラ、すなわち時刻の工学によって覆した。一貫性はソフトウェアだけの問題ではなく、正確な時刻という物理量を調達できれば買える資源になった、という発見が本質的だった。

この成果は製品とオープンソースの両面へ広がった。Google自身はSpannerを外部向けにCloud Spannerとして提供し、グローバルに分散しながら強い一貫性とSQLを保つマネージドデータベースとして商用化した。さらに大きかったのは、Spannerの設計思想が「NewSQL」と呼ばれる潮流を生んだことだ。CockroachDBやYugabyteDBといったシステムは、Spannerの論文を出発点に、リレーショナルなインターフェースと水平スケールする分散トランザクションの両立を目指した。

ただし多くの後発システムは、GPSと原子時計を自前で配備できるわけではない。そこで彼らは、専用ハードウェアに頼らずソフトウェア的に時刻の不確かさを扱う方向へ進んだ。ハイブリッド論理クロック（HLC）のような手法で、物理時計と論理的な順序情報を組み合わせ、Spannerがハードウェアで得た保証に近いものをコモディティ環境で近似する。TrueTimeという具体的な実装は再現されなくとも、時刻を不確かさ込みで扱い、その幅を設計に組み込むという発想は広く受け継がれた。

Spannerが示したのは、単なる一つのデータベースの作り方にとどまらない。理論上のトレードオフに見えたものが、前提となる道具を変えれば動かせる、という視点そのものだった。分散システムの限界は固定ではなく、どんなインフラを前提に置くかで変わる。この教訓は、Spanner以後の分散データ基盤の設計に、今も影響を与え続けている。

まとめ

Spanner（2012年）は、世界規模の分散データベースで外部一貫性のトランザクションとSQLを両立させた画期的なシステムだ。鍵はTrueTime APIにある。時刻を一点ではなく不確かさ区間「[earliest, latest]」として扱い、コミット時にその幅εぶんだけ待つcommit waitによって、時刻の順序とコミットの順序を全世界で一致させた。データはPaxosで複製し、複数グループにまたがる書き込みは二相コミットで束ねる。一貫性とスケールは両立できないという通念を時刻の工学で覆したこの論文は、Cloud SpannerやNewSQLへと直接つながった。関連する論文解説は論文で辿る分散システムから辿れる。