blog.tomoyat.dev

去年くらいにSpannerの論文を読んでみていて、全部理解できたわけではなかったけど、わかったことをまとめておく。

Spannerはデータセンター間で分散したデータベース。どっかのData Centerが自然災害とかで動かなくなったとしても大丈夫な設計。semi-relationalなデータモデルで複数のデータセンターにデータを保存できてトランザクションをサポートしている。

Bigtableとかが元々複数のデータセンターにまたがってデータを保存できてそれを利用するアプリケーションもあったが、複雑なスキーマや強い一貫性を持つ場合に大変だった。

書いてある内容で重要そうなことは

データをどうやって保存して複数のDC間でレプリケーションするのか
どのようなデータモデルなのか
どうやって複数のDC間でトランザクションを実現するのか

データをどうやって保存し、複数DCでレプリケーションしているか

データはSpan Serverの中に保存されている。Span ServerはSpannerの基本的なサーバーでデータベースのtablet（データの分割された部分）を管理し、データの読み書き、トランザクションの処理、レプリケーションなどの機能を提供する。

実際のデータベースのデータはkey(key + timestamp) Valueの構造でtabletに分割されて保存されていて、一つのSpan serverの中に100 ~ 1000のtabletが存在している。Spannerはこのtablet単位でデータをレプリケーションされている。

このtabletを複数のサーバーでレプリケーションしたくて、そのためにPaxos state machieを使っている。( おそらくこれ）このPaxosのstate machineそれぞれのtableごとにあって、タブレットのレプリケーションを行っている。

Data Modelについて

SpannerはSQLがつかえてRelationalデータベースみたいだけどちょっと違くて、primary keyが必要。なんでKey valueに見えると言えば見える。

Tabelには階層構造が定義できて、小階層と親階層を同じ位置に配置するように指定することができる。

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;

上記のようなテーブル構造の場合は、Albumの親がUserになっている。なのでUser1に紐づいている、アルバム1,2が同じディレクトリに入る。ディレクトリとはデータを保存するまとまりで、同じディレクトリは同じレプリケーションの設定をもつ。

TrueTimeAPI

今の時刻を範囲で返してくれる。その範囲内には絶対収まっていることが保証されている。それとは別に特定の時刻より確実に後かどうか？前かどうか？を教えてくれるAPIもある。

トランザクション

Spannerのトランザクション前にそもそもトランザクションとは何かって話

トランザクションとは、複数の読み書きをまとめて一つの操作としたもの。そしてこの操作は全体として成功するか、失敗するかしかない。（理想的には）

トランザクションの特性を表す用語としてACIDがある

Atomicity (原子性)
- 複数操作がまとまったトランザクションがあったときに、その操作の一部だけが反映された状態が観測されることはない
Consistency (一貫性)
- 一番曖昧。ACIDではデータが常に正しい状態ではないといけない、ということをさす。ただこれはアプリケーションの仕様などに依存していて、データベースだけで担保できない。
- ただCAP定理のConsistencyは違う意味だし、レプリケーションにもConsistencyが違う意味である
Isolation (分離性)
- 複数のトランザクションを同時に実行した時に分離されていること。同時に実行されてもいいけど、後から見た時にそれぞれのトランザクションが特定の順番に実行されているように見えることを保証する。
Durability (永続性)
- データが永続的に保存されること
- 100%は無理。地球が滅んだら終わり的な意味で

Spannerのトランザクション

SpannerでもACIDを達成しているがそれをどうやって達成しているのか

Cは無視して、AIDを考える。

Durability

これはデータが複数マシンにレプリケーションされてることで担保してる。 Paxosのステートマシンがデータを書くときにWALを使っているみたいなのでクラッシュしてもそれで復旧できるし、たとえそのレプリカがマシンごとダメになったとしても、他のDCにレプリケーションされてるものがあるのでそちらで読み書きができる。

Isolation

transactionがお互いに影響し合わないようにしたい。

まずはreadとwriteが混じったtransactionの場合。spannerではそのために(stong strict)two-phase lockを使っている。必要な要素をロックをとっていって、コミットするので、競合してもロックが取れた方が処理されるのでtransactionの順序が決まる。コミットする際にTrueTimeAPIを使ってcommitが行われた時刻の範囲の上限をこのコミット時にtimestampに割り振る。

ただreadだけのトランザクションでもロックをとっていると遅いので、read-onlyなtransactionが別である。

readだけの場合は指定された（されない場合は最新の）timestampをkeyとしてデータを読む。MVCCっぽくなる。ただマシンが複数あるのでそれぞれのマシンの時刻がズレてるかもしれない。

time=10のデータを欲しいとなった時に、他のサーバーではtime=9だったりする。なのでSpannerではTrueTimeAPIを使ってその問題を解決している。この論文の時点では複数のpaxosグループからデータを読まないといけない場合は、タイムスタンプとして、このタイムスタンプが確実に過ぎるまで待ってから、readを実行する

Atomicity

分散環境下でAtomicityが問題になるのは、複数のノードにデータをcommitする時に、制約の違反や衝突などで一部のノードだけトランザクションが失敗して、他のノードでは失敗するということが起きるから。

そしてこの問題に対してはtwo phase commitで対応している。two phase commitはノードが死ぬと問題が起きるがこのノードひとつひとつがtabletになっていて、裏側ではPaxosグループで書き込みを複数にレプリケーションしてるため基本的には落ちないことが前提になっている。

Spannerの論文を読んだ