地理分散DBについて

地理分散DBについて 2017年4月28日 Database Lounge Tokyo ハッシュタグ #dbltokyo 発表者 熊崎宏樹 @kumagi

トランザクションの基本 • トランザクションとは：CommitかAbortで終わる 複数の手続きの塊 – 例 [Read(x) Read(y) Write(y) Commit] • トランザクションマネージャとは：トランザクショ ンを複数並行して流し込んでも、何らかの順序 で一つずつ直列に流し込んだかのような結果を 生み出すシステム – トランザクションマネージャの中では主に並行制御 アルゴリズムが使われる

並行制御アルゴリズム • 2 Phase Lock・タイムスタン プ・グラフ・楽観的制御と 様々な亜種が考案されて きた – その系統を樹形図で表し たのが右図 – 2PLは有名だがその位置づ けは数ある手法の一角に 過ぎない Transactional Information Systems 176ページから抜粋

2 Phase Lock おさらい A「ロックを取って行った操作は論理的にはいつ実行され た事にして良いか？」 Q「ロックが保持されていた期間の中ならどこでも良い」 処理が実行されたと見なせる論理的な時間軸上の瞬間 を「Linearization Point」と呼ぶ 処理A 処理B Linearization Point

2 Phase Lock おさらい Q「2つ以上のオブジェクトのロックを握って行った 操作は論理的にはいつ実行された事にして良い か？」 A「全部のロックが確保された中の一瞬に全ての 操作が行えた事にしてよい」 処理A 3つのLinearization Pointが重なっている

2 Phase Lock おさらい • 複数のロックを握りっぱなしで行った操作は、複数の オブジェクトを一瞬で操作した事にしてよい • ACI(D)特性を実現する基盤となる考え方 • 他の並行制御アルゴリズムも2PLをベースに拡張した ものが多い • とはいえRead Onlyなクエリでもロックを取ってしまうの で実用上は性能が出にくく、現在の製品ではまず使わ れていない – 製品ではMVCCが使われる事が多い

Multi-Version Concurrency Control • 商用DBで広く使われている並 行制御手法 • 内部は細かく分かれている – MV2PLの事だけをMVCCだと思い 込んでる人が多い An Empirical Evaluation of In-Memory Multi-Version Concurrency Control から引用 Concurrency control protocols Multi-version Concurrency control protocols Pessimistic Nonlocking MVTO Optimistic Locking Locking MV2PL MVOCC Single-version Concurrency control protocols

Multi Version 2 Phase Lock おさらい • 基本は2 Phase Lockだが、書き込みは常にその値の新し いバージョンをタイムスタンプと共に生成する – Read Onlyトランザクションは古いバージョンを読み出す事が できる – 古いバージョンは消えないのでRead Onlyトランザクションが 絶対成功する 処理A 新しいバージョンが生成される

ここまでのまとめ • DBのトランザクションマネージャの中で使われ る並行制御にはいろんな方法がある • MVCCの実現方法一つとってもいろんな方法が ある

地理分散DB モチベーション：データセンターが一つ吹き飛んで も気にせず使えるデータベースが欲しい 1台のマシンに入りきらないぐらい巨大なテーブル を扱えるようになると更にうれしい 複数のマシンの処理性能を生かしたクエリ性能 が出るともっとうれしい

分散トランザクション • 目的から逆算するとトランザクションの経過・結 果について複数台のマシンが同一の値を持つ 事が必須条件 – 分散合意：2 Phase Commit

2 Phase Commit • 分散合意プロトコルの金字塔 – 誰が最初の発明者かも明白でないほど古い – 故障時の挙動に大量の亜種がある coordinator prepare commit worker ok ok worker Phase 1 Phase 2

2 Phase Commit • prepare完了前にworkerが故障したらabort – これはいい coordinator prepare abort worker ok worker ok

2 Phase Commit • Commit前にcoordinatorが故障したら coordinator prepare worker ok worker Phase 1

2 Phase Commit • Commit前にcoordinatorが故障したら、それを検知した リカバリノードがabortを依頼してロールバック – 1つもcommitが成功していない事を調べる coordinator prepare recovery check worker ok worker Phase 1 Phase 2 abort

2 Phase Commit • 死んだと思っていたcoordinatorが生きていたら？ – 食い違って死ぬ – 2 Phase Commitは基本的に死ぬ coordinator prepare commit check worker abort committed ok aborted worker Phase 1 Phase 2

2 Phase Commit • commit途中でcoordinatorが落ちたら coordinator prepare commit worker ok ok worker Phase 1 Phase 2

2 Phase Commit • commit途中でcoordinatorが落ちたら回復ノードが表 れて一つでもcommitしていたら全部をcommitさせる coordinator prepare commit check commit ok worker ok worker Phase 1 Phase 2

2 Phase Commit • commit途中でcoordinatorが落ちたら一つでもcommit しているときリカバリノードが全部をcommitさせる – その途中で一部のworkerが落ちて後で復活したら？→死 coordinator prepare commit check abort ok aborted worker ok committed worker Phase 1 Phase 2

2 Phase Commit • 2 Phase Commitは故障したり復活したりするとすぐ 壊れる • 回復中に壊れるパターンや回復ノードが壊れるパ ターンまで挙げだすと壊せるシナリオは山ほど出 てくる • 弱点を補強したという触れ込みの3 Phase Commit なんてものもあるけどやはり壊れている • GoogleのChubbyの開発者Mike Burrows「合意プロ トコルは一つしかない。Paxosだ」（≒他の合意プロト コルは全て合意不能） 覚えていただきたい事実：2 Phase Commitはその ままでは使えない

Paxos • Lamport先生が「参加者の故障や復活がある場 合絶対に合意には至れない」ということを証明 しようとして逆に生み出してしまった合意プロト コル – 実は故障に耐える合意プロトコルは他にも viewstamped replicationとかstake replicationとかい ろいろあるが、きっちり証明されたのはPaxosが初だ から有名らしい 出典:http://lamport.azurewebsites.net/pubs/pubs.html#lamport-paxos

Paxos • 複雑さに定評がある(とよく言われる) – 正常時の挙動やメッセージ数は2PCと同じ – prepare, proposeがバージョン番号を持つ coordinator prepare(n) propose(n, v) worker ok(n, v) worker accept(n)

Paxos • Coordinator – prepare(n)に対して過半数からok(n,v)が貰えたらそ の中で最大のnに対するvを全workerに投げる • このvがnullなら自分自身のvを使う • nullでないならvは生死不明な他のCoordinatorのvである • Worker – 過去に見たprepare(n)のうち最大のnであればそれ にok(n,v)を返す。そうでなければng(n') • vは過去に一度も合意してない場合nullかも知れない 25行で説明するPaxos: http://nil.csail.mit.edu/6.824/2015/notes/paxos-code.html

Paxos • 2PCだと死んだシナリオ – 蘇るcoordinator • 間に入った別のcoordinatorがバージョン番号を変えるので 間違った合意に至らなくなる coordinator prepare(n) propose(n) prepare(n') propose(n',v) ng(n',v) worker ok(n,v) worker ng(n',v)

Paxos • 過半数にproposeが届いた時点でクラスタは合意した事になる – workerが復活してもok – 不完全な複製は後続のcoordinatorが複製し直してくれる prepare(x) propose(x, v1) coordinator2 coordinator1 prepare(n) propose(n, v1) ok(x, v1) worker ok(n, v) worker

Paxos • あらゆる故障パターンを網羅して描いても良い けれどスライドに書くには手狭&退屈 • エッセンスだけ掻い摘むと – バージョン番号のお陰で古いcoordinatorやworker が場を乱そうとしても適切に無視される – 複数のcoordinatorがある意味リカバリノードを兼ね ている（合意した値が既に一部のworkerにあれば それを再度全体へ周知する） – 過半数が合意すればプロトコルが進行するように設 計されているためシンプル

ここまでのまとめ • 2 Phase Commitは基本的に壊れている • 任意の通信遅延(つまりノードの復活)を含む分 散環境で合意するにはPaxosのような強固なプ ロトコルが必要

Spanner • Googleが開発してOSDI 2012で発表した地理分 散データベース – 登場時は原子時計やGPSを使っている事ばかりが 話題にされたが実はそこは枝葉末節 • その実態はMV2PLと2Phase LockとPaxosを組み 合わせたオモシロ地理分散データベース

Spanner • 巨大なDBでACIDかつ地理分散したい – テーブルをタブレットへ水平分割 数 万 行 ID 名前 住所ID スコア ID ID 名前 名前 住所ID スコア スコア 住所ID 1 佐藤 3 123 11 佐藤 佐藤 33 123 123 2 田中 2 3243 22 田中 田中 22 3243 3243 3 鈴木 3 54 ID 名前 住所ID スコア 4 山田 5 2 3 鈴木 3 54 5 磐田 6 332 4 山田 5 2 6 吉井 3 232 5 磐田 6 332 7 山下 5 332 ID 名前 住所ID スコア 8 熊谷 3 12 7 山下 5 332 8 熊谷 3 12 約 千 行

Spanner • 障害に備えたい – 1タブレットを1 Paxos単位として地理分散 フランスDC ID 名前 住所ID スコア 1 佐藤 3 123 2 田中 2 3243 日本DC ID 名前 住所ID スコア 1 佐藤 3 123 2 田中 2 3243 Paxos 西海岸DC ID 名前 住所ID スコア 1 佐藤 3 123 2 田中 2 3243

Spanner • データセンタ1つあたり100から数1000のサーバ • サーバ1台で100～1000個のタブレットを持つ 日本DC 100～数1000台 100～ 1000 タブレット シンガポールDC tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet フランスDC Paxos tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet tablet ・・・

タブレット with Paxos • 1つのタブレットの操作はPaxosで調停する – Paxosは1つの値についてしか合意できないので、それを並 べて命令列を作り、合意できた命令から順に適用していく – 同じ命令列を同じ順序で実行したのだから同じ状態になる • Replicated State Machineという複製アプローチ 1 2 3 4 5 6 未実行命令 x=10 y=3 z=2 a=8 b=5 c=9 実行済命令 x=10 y=3 z=2 a=8 x=10 y=3 z=2 a=8 Paxosの合意 1回分

Spannerでの更新 • トランザクションの操作が1つのtabletの中で収 まるなら、TabletのPaxosを行うリーダーに命令 の実行を依頼する – tablet内は2 phase lockで並行制御 • 複数のtabletに跨るトランザクションは、複数の tabletの間で2 Phase Commitを行う – 2 Phase Commitは故障に弱いのでは？→Paxosが 参加者なので故障しないと仮定してよい – tabletを跨っても2 phase lockで並行制御

Spannerでの更新 • paxosグループが参加者となって2phase commitを行う – paxos – 2PC prepare commit paxos prepare paxos ok ok

Spannerでの参照 • 2 Phase Lockを使って更新しているのでトランザ クションとしてはこの上なく正しい • だがRead Onlyな操作であっても毎回2 Phase Lockを使うのはコストが高すぎる • よし、全部の値にタイムスタンプを振って追記す る形を取れば、過去の任意の時間の値に遡っ て一貫性のあるRead-Onlyトランザクションがで きるぞ！ – いわゆるMV2PL – (そのままでは)分散環境ではまともに動かない

SpannerでのRead-Onlyトランザクション • まともに動かない理由：各サーバの時刻がズレて いるから 期待する挙動 read(x), read(y) write(x,10) write(y,10) x=10, y=10

SpannerでのRead-Onlyトランザクション • まともに動かない理由：各サーバの時刻がズレて いるから 発生する挙動 read(x), read(y) write(x,10) write(y,10) x=0, y=10

Spannerが満たしたい一貫性 • External Consistency – あるトランザクションT1が終わった後に始まったトラ ンザクションT2のタイムスタンプは絶対にT1より後 – これを分散MV2PL環境下で実現したのがSpannerの Contribution • どうやって？ – やっと原子時計・GPSの出番

True Time API • 正しい時刻がどの範囲にあるかわかるAPI – GPSでも原子時計でも一応ズレるので、その誤差範 囲を制限できる機能がある • システムに参加している全マシンの時刻の誤差 範囲を予測可能にする事が目的 – この範囲を超えて時間が狂うマシンはシステムから 除外される（地味に重要）

Spannerのcontribution: Commit Wait • True Time APIを用いて – トランザクションで書く値にタイムスタンプを振る – タイムスタンプで振った時刻が「確実に過ぎた」と断言で きるまで、ロックを意図的に握ったままにする read(x), read(y) write(x,10) write(y,10) Commit Wait Commit Wait x=10, y=10

Commit Waitの証明 • External Consistencyを満たす証明は論文に書 いてあって複雑に見えるが実は簡単 – T1が振ったタイムスタンプが過ぎてからアンロック • s1 < T1(完了) – アンロックが済んだ後のデータをT2が読む • T1(完了) < T2(開始) – T2に振られる時刻はT2の開始より後(当然) • T2(開始) < s2 – よって s1 < s2 → External Consistencyは守られた

細かい議論 • Read Onlyトランザクションもタイムスタンプを振られ る – そのタイムスタンプより前の値しか読みだすことができ ない – そのタイムスタンプの値を読み出せたと断言するために はそのタイムスタンプの時刻が過ぎた後でないといけな い – なお、Tabletを跨らないRead Onlyは普通にMV2PLの範 疇で値を読んでかまわないから少し速い • googleのシステムでは時刻ズレは1桁ミリ秒の範囲 で収まっている様子。これによって比較的高速なト ランザクションができる – 単純に遅延が小さいことより、ジッタが少ない事が脅威

ベンチマーク • Quizletというサービスが使い込んだベンチを公 開している • ノード数を増やすごとにスループットの限界が伸びている • 台数当たりの性能ではやはりMySQLに軍配 • アルゴリズムの割にレイテンシが引く程低い

Spannerのまとめ • 基本的にMV2PLを分散環境に拡張しただけ • Commit Waitがcontributionだが愚直にやると 性能が残念になる • そこでTrue Time APIでCommit Waitを短縮した

その他の地理分散DB • Spannerは主にその効率性の観点から批判が いくつかある – 一言で言うと「Paxos遅い」

Spannerでの遅延 • paxosの通信は常に地理的に跨っている – 地理間通信に片道10ms掛かると仮定すると…？ prepare commit paxos 40ms prepare ok paxos • tabletを跨る2PCは最低でも160msかかる – 実際はもっと細かい高速化ができるが割愛 ok

Replicated Commitアプローチ • 2PCのログ結果を共有するのではなくコミット可能か否かを共 有する • Paxos on 2PCにすれば地理間通信が減るね prepare(n) prepare propose(n,v) commit 2PC ok(n,v) ok(n,v) 2PC • この方式なら2往復で済む – 2PCの進行に掛かるログをPaxosで複製する(Log Replication)のではなく、コミット可能 か否かという情報をPaxosで複製する(Commit Replication) Hatem Mahmoud et al. Low-Latency Multi-Datacenter Databases using Replicated Commit(VLDB2013)

Calvin • トランザクションリクエストそのものを複製すれば良いよね – 同じリクエストを同じ順序で実行したら同じDB状態になるし – 各DBはクエリを実行する順序だけ合意して、あとはFIFOに処理していくだけ – いわゆる並行処理制御でいうDeterministicアプローチ prepare(n) propose(n,v) 2PC ok(n,v) 2PC

Spanner vs Calvin • 要旨：ほとんどのケースでCalvinはSpannerより優れている – DC間通信をしている間に値をロックし続ける必要が無いという点で速度 的に優位 • 試したい人はFaunaDBを使ってみてね https://fauna.com/blog/spanner-vs-calvin-distributed-consistency-at-scale

• https://fauna.com/blog/spanner-vs-calvin-distributed-consistency-at-scale

まとめと所感 • 分散DBと違って地理分散DBはDC間の遅延が支配項に なりがちなので新しいプロトコルが考案される素地があ る • トランザクションの実行順序だけ合意するというアプロー チは良さそうに見えるがDBを大規模に水平分割する前 提で考えるとShared-Everything的になってスケーラビリ ティに限界が出るのでは？ – どのクエリがどの値に触るかを断定すればShared-Nothing になるがその断定に掛かるコストが今度は高くつきそう