Spanner 論文（Google's Globally-Distributed Database）を読む

Spanner は何を解決する DB か

Google社内では、主にBigtableとMegastoreがデータストアとして存在した。

	Bigtable	Megastore
データモデル	単純なキーバリュー（行キー → 列）	半リレーショナル（スキーマあり）
トランザクション	1行内のみ。複数行にまたがるものは不可	あり（エンティティグループ内）
データセンター間の複製	結果整合（eventual consistency）	同期複製（Paxos）
弱点	複雑なスキーマや強い整合性が必要だと苦しい	書き込みスループットが低い

多くのアプリがMegastoreを選んでいた。

理由
- Bigtableのほうがスケーラブルで性能は高いが、スキーマの担保と、複数のデータセンターにまたがった同期複製の観点
課題
- 書き込みスループットが遅い

これに対して、Spannerの開発者らは、それぞれの長所を取り入れたデータストアを開発することを考えた。

Bigtable 並のスケール（数百のデータセンター、数兆行）
Megastore のような半リレーショナルなスキーマと同期複製
更に、世界中に分散したデータをまたいでも整合性が保たれるトランザクション

開発するにあたっての設計思想

We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions.

（§2.3 Data Model）

訳: トランザクションの使いすぎによる性能問題は、ボトルネックが生じたときにアプリ開発者に対処してもらう方がよい。トランザクションが無いことを前提に、常にコードで回避させるよりもその方がましだ。

私的にも確かにそのほうがありがたいと思う。トランザクションは正しさ、つまり機能要件に関わる問題だが、性能は非機能要件である。性能問題はボトルネックになった箇所だけを後から直せばよい。対して、トランザクションが無いと、全ての箇所で常に回避策を考え続けなければならない。書き込みが遅くてもMegastoreが多くのアプリに選ばれていたことも、それを裏付けている。

両方の長所を取り入れたデータストアを作ろうとできるのがさすがGoogle。

アーキテクチャ

全体構成

Spannerは大きい単位から順に、次のように構成されている（§2）。

単位	役割
universe	Spannerのデプロイ全体。テスト用、開発・本番用、本番専用の数個だけが動いている
zone	管理と物理的な隔離の単位。データを複製する場所の単位でもある。1つのデータセンターに複数あってもよい
spanserver	zone内に数百〜数千台あり、クライアントにデータを返すサーバー
tablet	spanserver 1台が100〜1000個持つデータの塊

zoneには他に、データをspanserverに割り当てるzonemasterや、クライアントがデータの在りかを調べるためのlocation proxyがいる。universe全体には、zone間のデータ移動を自動で行うplacement driverと、状態を表示するuniverse masterが1つずつある。

flowchart TB
    U["universe"] --> UM["universe master<br/>状態の表示"]
    U --> PD["placement driver<br/>zone間のデータ移動"]
    U --> Z1["zone 1"]
    U --> Z2["zone 2"]
    U --> ZN["zone …"]
    Z1 --> ZM["zonemaster<br/>データをspanserverに割り当て"]
    Z1 --> LP["location proxy<br/>データの在りかを案内"]
    Z1 --> S["spanserver × 数百〜数千"]
    S --> T["tablet × 100〜1000"]

tablet

tabletは次の対応の集まりである（§2.1）。

(key:string, timestamp:int64) → string

キーにtimestampが含まれており、値を上書きせず、時刻付きで複数のバージョンを持つ。この点はBigtableと共通である。違いは、Spannerではタイムスタンプをシステム自身がコミット時に割り当てることである。このタイムスタンプが、後述するTrueTimeやスナップショットリードの土台になる。

tabletの状態は、B-treeに似たファイル群と先行書き込みログ（WAL）として、分散ファイルシステムColossusに保存される。

Paxosグループ

同じtabletのレプリカは、別々のzoneのspanserverに置かれる。このレプリカの集合をPaxosグループと呼ぶ。

グループ内の1台がリーダーになり、書き込みはリーダーから始まる
リーダーは書き込みをレプリカに送り、過半数が受け取ったらコミットとする
読み取りは、十分に新しいデータを持つレプリカならどれからでもできる

flowchart LR
    subgraph G["Paxosグループ（tablet Xの5レプリカ）"]
        direction LR
        L["zone Aのspanserver<br/>tablet X（リーダー）<br/>ロックテーブル"]
        RB["zone Bのspanserver<br/>tablet X"]
        RC["zone Cのspanserver<br/>tablet X"]
        RD["zone Dのspanserver<br/>tablet X"]
        RE["zone Eのspanserver<br/>tablet X"]
    end
    L -- "複製" --> RB
    L -- "複製" --> RC
    L -- "複製" --> RD
    L -- "複製" --> RE

5レプリカのうち1つが落ち、1つが遅れている場合の書き込みは次のようになる。

%%{init: {"sequence": {"width": 100, "actorMargin": 20}}}%%
sequenceDiagram
    participant C as クライアント
    participant A as リーダーA
    participant B as B
    participant Cz as C
    participant D as D（障害）
    participant E as E（遅延）
    C->>A: 書き込み
    A->>B: 複製
    A->>Cz: 複製
    A-xD: 複製（届かない）
    A->>E: 複製
    B-->>A: OK
    Cz-->>A: OK
    Note over A,Cz: A・B・Cの3/5で過半数 → コミット
    A-->>C: コミット完了
    E-->>A: OK（遅れて到着）

全員ではなく過半数の応答でコミットする理由は2つある。

遅いレプリカや落ちたレプリカを待たなくてよい: 5レプリカなら過半数は3なので、2 zoneまでの障害なら書き込みを続けられる
過半数どうしは必ず重なる: 5台から3台を選ぶと、どの選び方でも1台以上が共通する。そのため、リーダーが落ちて次のリーダーを過半数で選ぶとき、コミット済みのデータを持つレプリカが必ず含まれ、コミット済みのデータは失われない

仮に5台中2台の応答でコミットすると、{A, B}だけが知っている書き込みを、{C, D, E}で選ばれた新リーダーは知らない。コミット済みのデータが消えてしまう。

なお、応答しなかったレプリカが落ちたとは限らない。遅れているだけかもしれないし、ネットワークが分断されているだけかもしれない。Paxosはその区別をせず、待たずに先へ進む。遅れたレプリカは、後からログの抜けを埋めて追いつく。

TrueTime と外部整合性

外部整合性

Spannerが保証したいのは、次の外部整合性（external consistency）である（§1）。

トランザクションT1がコミットした後にT2が始まったなら、T1のコミットタイムスタンプはT2のものより小さい

たとえば東京でT1「Aさんを友達から外す」がコミットされ、その後ニューヨークでT2「写真を投稿」が始まったとする。この保証があれば、T2の時刻のスナップショットにはT1も必ず反映されているので、外されたAさんに写真が見えることはない。

Spannerはタイムスタンプで順序を決め、そのタイムスタンプで過去のスナップショットを読む。そのため、タイムスタンプの順序が現実の時間順序と一致することが重要になる。

問題は、各サーバーの時計が完全には一致しないことである。東京のサーバーの時計が5ms進んでいると、T1には実際より大きいタイムスタンプが付く。直後にニューヨークで始まったT2のタイムスタンプがT1より小さくなり、T2の時刻で読むとT1が反映されていない、ということが起こりうる。

sequenceDiagram
    participant T as 東京のサーバー<br/>（時計が5ms進んでいる）
    participant N as ニューヨークのサーバー<br/>（時計は正確）
    Note over T: 本当の時刻100msにT1をコミット<br/>タイムスタンプs1 = 105
    T->>N: T1の完了を知った利用者が写真を投稿
    Note over N: 本当の時刻102msにT2を開始<br/>タイムスタンプs2 = 102
    Note over T,N: 実際はT1→T2の順なのに s2 < s1 で逆転する

TrueTime API

Spannerは時計を完璧に合わせることを諦め、ずれの範囲を明示するAPIを作った（§3）。

TT.now()は1つの時刻ではなく区間[earliest, latest]を返す。本当の時刻はこの区間のどこかに必ずある
TT.after(t)はtが確実に過去なら真、TT.before(t)はtが確実に未来なら真を返す
区間の半分の幅が不確実性εで、本番環境では概ね1〜7ms、平均4ms程度である

TT.after(t)はTT.now().earliest > tと同じ意味である。earliestは本当の時刻の下限なので、下限ですらtより大きければtは確実に過去と言える。

GPSと原子時計

TrueTimeは、各データセンターに置いたtime masterと、各マシンのデーモンで実装されている。

time masterの多くはGPS受信機を持ち、残りは原子時計を持つ。2種類を使うのは、故障の仕方が異なるからである
各マシンのデーモンは30秒ごとに複数のtime masterに問い合わせ、嘘をついているmasterを除外して時刻を合わせる
問い合わせの間は、ローカル時計のずれを最悪の場合（200μs/秒）で見積もってεを増やしていく。そのためεは1〜7msの間をのこぎり波のように変動する

commit wait

外部整合性は、次の2つのルールで保証される（§4.1.2）。

Start: コミット要求が届いた後にTT.now()を呼び、コミットタイムスタンプsをTT.now().latest以上にする
Commit Wait: TT.after(s)が真になるまで、コミット結果をクライアントに見せない

commit wait の時間軸。区間の幅は 2ε。s を latest で取り、earliest が s を超えるまで待つので、待ち時間は区間の幅ぶんになる

T1のコミット後にT2が始まった場合を考えると、次のようにs1 < s2が成り立つ。

ステップ	理由
① s1 < T1が見えるようになった本当の時刻	Commit Waitで、s1が確実に過去になるまで待ったから
② 〃 < T2が始まった本当の時刻	T1のコミット後にT2が始まったという前提
③ 〃 ≤ s2	Startルールで、s2は本当の時刻の上限`latest`以上だから

時計がずれていても、ずれの範囲だけ待てば順序が保証される。これがTrueTimeの核心である。

sをlatestで取り、earliestがそれを超えるまで待つので、待ち時間の期待値は少なくとも2εになる（§4.2.1）。ただし、この待ちはPaxosの通信と並行して行われる。

εが大きくなっても整合性は壊れず、待ち時間が延びてSpannerが遅くなるだけである（§1）。逆に言えば、この保証はεが本当にずれの上限になっていることに依存している。論文によれば、時計の故障はCPUの故障の1/6程度の頻度で、TrueTimeは他のソフトウェアと同程度に信頼できるとしている（§5.3）。

read-onlyトランザクション

読み取り専用のトランザクションは、次の2段階で実行される（§4.1.4）。

読み取り時刻s_readを決める
s_read時点のスナップショットを読む。つまり、s_read以前にコミットされた最新の値を返す

ロックを取らないので、書き込みを止めない。また、十分に新しいデータを持つレプリカなら、リーダー以外からでも読める。

最も単純なs_readの決め方はTT.now().latestである。書き込みのStartルールと同じ理屈で、外部整合性が保たれる。仮にearliestにすると、s_readが本当の時刻より小さくなりうる。その結果、読み取りより前にコミットされた「友達を外す」が見えず、外されたはずのAさんに写真が見えてしまう。

safe time

レプリカが「十分に新しい」かどうかは、safe timeで判断する（§4.1.3）。safe timeは「この時刻以下のデータは確定している」という値で、レプリカはs_read ≤ safe timeのときだけ読み取りに応える。safe timeは次の2つのうち小さい方である。

Paxosのsafe time: 適用済みの最新のPaxos書き込みのタイムスタンプ。リーダーはタイムスタンプを単調増加で割り当て、書き込みは順番に適用されるので、これ以下の時刻に新しい書き込みが入ることはない
トランザクションマネージャのsafe time: 2PCのprepare済みで、まだコミットが決まっていないトランザクションがあれば、それらのprepareタイムスタンプの最小値 − 1。コミットされるか分からない書き込みより前の時刻までしか確定していない、という意味である

この仕組みがあるので、ロックを取らずに読んでも、読んでいる途中でs_read以下の時刻に書き込みが割り込むことはない。

並行制御

read-writeトランザクション

読み書きするトランザクションは、2相ロック（2PL）と2相コミット（2PC）で実行される（§4.2.1）。

読み取り: クライアントは各Paxosグループのリーダーに読みに行く。リーダーは読み取りロックを取ってから最新データを返す
書き込みのバッファ: 書き込みはコミットまでクライアント側に溜めておく
2PC: クライアントがcoordinatorとなるグループを1つ選び、各参加グループのリーダーにコミット要求を送る
- 参加者のリーダー: 書き込みロックを取り、prepareタイムスタンプを決めてPaxosでログに残し、coordinatorに通知する
- coordinatorのリーダー: 全参加者のprepareタイムスタンプを受け取った後、コミットタイムスタンプsを決める。sは全prepareタイムスタンプ以上、かつTT.now().latestより大きい値にする。commit waitをしてからコミットし、結果を各参加者に伝える
各参加者がコミットを適用してロックを解放する

sequenceDiagram
    participant C as クライアント
    participant P as 参加者リーダー<br/>（グループ1）
    participant Co as coordinatorリーダー<br/>（グループ2）
    C->>P: 読み取り
    Note over P: 読み取りロック
    C->>Co: 読み取り
    Note over Co: 読み取りロック
    Note over C: 書き込みはクライアントにバッファ
    C->>P: コミット要求 + 書き込み
    C->>Co: コミット要求 + 書き込み
    Note over P: 書き込みロック<br/>prepareタイムスタンプを決める<br/>prepareをPaxosで複製
    Note over Co: 書き込みロック
    P->>Co: prepare完了（prepareタイムスタンプ）
    Note over Co: sを決める<br/>s ≥ 全prepareタイムスタンプ<br/>s > TT.now().latest<br/>commitをPaxosで複製
    Note over Co: commit wait（TT.after(s)まで）
    Co-->>C: コミット完了（s）
    Co->>P: コミット結果（s）
    Note over P,Co: commitを適用してロックを解放

coordinatorはprepareを省略し、全参加者のprepareを待ってからsを決める。commit waitはPaxosの複製と並行して行われる。

デッドロックはwound-wait（古いトランザクションが新しいものを中断させる方式）で回避する。

書き込みをバッファするので、トランザクション内で自分が書いた値を読んでも見えない。それでも問題にならないのは、読み取りが返す値はどれもコミット済みでタイムスタンプが付いており、自分の書き込みにはコミット時にようやくsが付くからである。トランザクション内で読んだものは全て「sより前の状態」で揃う。

Paxosリーダーのリース

リーダーは期限付きの許可証であるリースを持つ（§4.1.1）。

リーダー候補はレプリカの過半数からリースの投票をもらってリーダーになる。期限はデフォルト10秒で、書き込みが成功するたびに延長される
投票したレプリカは、期限が切れるまで他の候補に投票しない
過半数どうしは必ず重なるので、期限内に別のリーダーが過半数を集めることはできない。リーダーは同時に1人だけになる

リーダーが同時に2人いると、2つの問題が起きる。

ロックが効かない: ロックテーブルは各リーダーのメモリにあるので、片方のリーダーでロック中のデータを、もう片方のリーダー経由で書き換えられてしまう
タイムスタンプが逆転する: リーダーは自分のリース期間内の時刻だけをタイムスタンプとして割り当てる。リース期間が重ならないことで、リーダーが交代してもタイムスタンプが単調増加する。この前提が崩れる

データモデル

Spannerのテーブルは行・列・バージョン付きの値を持ち、クエリ言語もSQLに似ている（§2.3）。ただし純粋なリレーショナルではなく、全テーブルに主キーが必須で、主キーが行の「名前」になる。この点はキーバリューストアに近い。

主キーを必須にしているのは、キーの選び方でデータの局所性を制御できるようにするためである。そのための仕組みがINTERLEAVE IN PARENTで、親子関係を宣言すると、子テーブルの行が親の行の直後に並ぶ。

CREATE TABLE Users {
  uid INT64 NOT NULL, email STRING
} PRIMARY KEY (uid), DIRECTORY;

CREATE TABLE Albums {
  uid INT64 NOT NULL, aid INT64 NOT NULL,
  name STRING
} PRIMARY KEY (uid, aid),
  INTERLEAVE IN PARENT Users ON DELETE CASCADE;

キーは次の順に並ぶ。

Users(1)
  Albums(1,1)
  Albums(1,2)
Users(2)
  Albums(2,1)

階層の最上位のテーブル（Users）の1行と、そのキーで始まる子孫の行をまとめたものが、前述のdirectoryになる。directoryは配置の単位なので、ユーザー1のメールアドレスとアルバム名を同時に更新するトランザクションは、1つのPaxosグループで完結し、2PCが要らない（directoryが大きくなりすぎると複数のfragmentに分割され、別々のグループに置かれることはある）。

INTERLEAVEが無いと、Spannerはどのテーブルのデータが一緒に使われるかを知ることができない。論文も、この宣言なしには最も重要な局所性の関係が分からない、としている。

評価・運用

Spannerの最初の本番ユーザーは、Googleの広告バックエンドF1である（§5.4）。

移行前のF1は、手動でシャーディングしたMySQLで動いていた。顧客ごとに関連データを固定のシャードに割り当てる方式で、アプリのビジネスロジックがシャーディングの構成を知っている必要があった。最後の再シャーディングには2年以上かかり、数十チームの調整が必要だった。MySQLの成長を抑えるために一部のデータをBigtableに逃がしたが、その分トランザクションと全データ横断のクエリが使えなくなった。

F1チームがSpannerを選んだ理由は次の3つである。

手動の再シャーディングが不要
同期複製と自動フェイルオーバー（MySQLのマスター・スレーブ構成では、フェイルオーバーが難しく、データ損失の恐れもあった）
任意のデータにまたがるトランザクションと、一貫した読み取りが必要だった

再シャーディングが不要になるのは、directory単位のデータ移動がSpanner内部で自動化されているからである。directoryは稼働中でもmovedirでPaxosグループ間を移動でき、アプリはどのデータがどのグループにあるかを知らなくてよい。

レプリカは米国西海岸に2、東海岸に3置かれている。東海岸だけで過半数の3になるので、リーダーを東海岸に置けば、コミットに大陸横断の往復が要らなくなるはずである（この効果は論文に明記されておらず、筆者の推測）。実際、計画外のクラスター障害でも自動フェイルオーバーはほぼ気づかれず、F1チームがしたのは、Paxosリーダーを優先的に置く場所をスキーマで更新することくらいだった。

directoryはおおよそ顧客1人に対応し、大半のdirectoryはfragmentが1つだけである。つまり大半の顧客のデータの読み書きは、1台のサーバーで完結する。

まとめ

世界中に分散したデータベースで課題になるのは時間である。サーバー間で時計がずれていると、コミットの順序とタイムスタンプの順序が逆転し、不整合が起きうる。

Spannerは、時刻を正確に合わせる代わりに、ずれの範囲を明示するTrueTimeを用意した。書き込みではcommit waitでずれの範囲だけ待ち、読み取りではずれを考慮した時刻のスナップショットを読むことで、外部整合性を保証している。

データはPaxosグループで複製し、過半数のレプリカの応答でコミットする。これにより、遅いレプリカや落ちたレプリカがあっても書き込みを続けられ、コミット済みのデータも失われない。さらに、一緒に使われるデータを同じPaxosグループにまとめることで、2PCを減らしてレイテンシを抑えている。

参考

Spanner: Google’s Globally-Distributed Database (OSDI 2012)