分散システムについて語らせてくれ

分散システムについて 語らせてくれ 日本電信電話株式会社 ソフトウェアイノベーションセンタ 熊崎 宏樹 (@kumagi) Copyright©2016 NTT Corp. All Rights Reserved.

目次 分散システムを作る際に気をつけて欲しい事 1.分散自体を目的にしない事 2.論文を読んでそのまま実装しない事 3.Two Phase Commitを使わない事 4.手を動かす事 Copyright©2016 NTT Corp. All Rights Reserved. 2

分散自体を目的にしない事 • よくわかってない人でもCloudera Managerをダウンロードして1時間後 には巨大なHadoopクラスタを立ち上げてYARN, HDFS, Spark, HBase などで遊ぶ事ができる。 • 世の中では分散システムが必要以上に喧伝されている • 「コンピュータ1台よりも2台の方が高速」という直感に対して反論するの は意外と難しい • あなたのそのシステム、本当に分散システムじゃないとダメ？ Copyright©2016 NTT Corp. All Rights Reserved. 3

システムの肌感覚を掴め みんなが知っているべき数値 by Jeff Dean L1 キャッシュ参照 分岐予測ミス L2 キャッシュ参照 Mutexのlock/unlock メモリ参照 1KBをZIP圧縮 1Gbpsで2KB送る メモリから1MB連続で読む 同一のデータセンタ内のマシンと通信1往復 HDDシーク HDDから1MB読み出し カリフォルニアとオランダ間で通信1往復 0.5 ns 5 ns 7 ns 25 ns 100 ns 3,000 ns 20,000 ns 250,000 ns 500,000 ns 10,000,000 ns 20,000,000 ns 150,000,000 ns Copyright©2016 NTT Corp. All Rights Reserved. 4

システムの肌感覚を掴め みんなが知っているべき数値 by Jeff Dean L1 キャッシュ参照 分岐予測ミス L2 キャッシュ参照 Mutexのlock/unlock メモリ参照 1KBをZIP圧縮 1Gbpsで2KB送る メモリから1MB連続で読む 同一のデータセンタ内のマシンと通信1往復 HDDシーク HDDから1MB読み出し カリフォルニアとオランダ間で通信1往復 0.5 ns 5 ns 7 ns 25 ns 100 ns 3,000 ns 20,000 ns 250,000 ns 500,000 ns 10,000,000 ns 20,000,000 ns 150,000,000 ns Copyright©2016 NTT Corp. All Rights Reserved. 5

システムの肌感覚を掴め 分散システム化すると基本的に遅くなる。 大抵はネットワークが遅延の支配項になる。 速くなる場合のほうがむしろ例外的と思ったほうが良い。 ワークロードと照らし合わせてマイクロベンチを取った 後で分散システム化を検討して欲しい（頼むから実装上 の重要な意思決定で分散ミドルウェアを使用する事を目 的にしないで欲しい） とにかく測れ 測らずに分散システム化するのは Early Optimizationの一種 Copyright©2016 NTT Corp. All Rights Reserved. 6

論文を読んでそのまま実装しない事 • 分散システムの論文は多く出ているがその大半は「やってみたレポート」 「作ってみた」→「動いたっぽい」→「測った」→「Yappy!」 • 分散システム界隈の研究は過去の研究の蓄積が蓄積扱いされにくい分野の 一つであり、論文を真に受けてはならない • 他にそう感じる研究分野はHCI分野 • 故障モデルなどが実は結構厳しく規定されており、そこを読み飛ばすと痛 い目に遭う Copyright©2016 NTT Corp. All Rights Reserved. 7

ケーススタディ：Primary-Backup • レプリケーションプロトコルとして典型的に見かけるパターン • 一番IDが小さいServerをPrimaryとして、MasterがBackupへのレプリケーション を担当する • ReadもWriteもPrimaryが受け取ることによって一貫性の問題を回避 • Primaryが壊れたらBackupのうち一番IDが小さい奴がPrimaryへ昇格する • HDFSでメタデータの複製に使われているのはこれ Client Read Write Server1 Server2 Server3 Server4 Copyright©2016 NTT Corp. All Rights Reserved. 8

ケーススタディ：Chain-Replication • 次に見かけるレプリケーションプロトコル • バケツリレーのように受け取ったものを即座に次のサーバに渡していく • データを全部受け取る前から次のサーバにリレーできるので大容量のデータ転送に強 くメッセージの飛び交う回数はサーバ台数+1で最小だがサーバ台数に比例するメッ セージ遅延がかかる • 故障したサーバはスキップする • HDFSでデータの複製に使われているのはこれ Client Read Write Server1 Server2 Server3 Server4 Copyright©2016 NTT Corp. All Rights Reserved. 9

ケーススタディ: Primary-Backup と Chain-Replication • 通信の特性を見極めて最適なプロトコルを使おう • Primary-Backupは「細かくて素早い」特性 • Chain-Replicationは「時間が掛かっても通信効率が良い」特性 • どちらもサーバが故障する場合は縮退運転していき、最小1台でも稼動は する プロトコル名 Primary-Backup Chain-Replication 通信遅延数 メッセージ数 4回 2N個 N+1回 N+1個 Copyright©2016 NTT Corp. All Rights Reserved. 10

ちょっと待った Copyright©2016 NTT Corp. All Rights Reserved. 11

ケーススタディ：Primary-Backupの故障 • これは容易にバグる • Readを常に全体に伝える必要があるかは実装次第だが典型例として • みんながカジュアルに生死判断を行うと食い違ったときに容易に世界が壊れる ➢いわゆるSplit-Brain Client Write(x=2) Server1の 応答が遅かったので 死んでると想定して Server2へリトライ Read(x) -> 0 Server1 Server2 Server3 Server2の 応答が遅かったので 死んでると想定して 無視 Server4 Copyright©2016 NTT Corp. All Rights Reserved. 12

間違った実装が世界を揺るがす • 「Redis Sentinelという自動レプリケーションの仕組みを作りました。 最強です（ｷﾘｯ」 • しかし特定の実行パターンによって内容物の半分以上が失われる • Jepsen Testが築く屍の山 • 様々な分散ミドルウェアで 意図的にSplit-Brain状態を引き起こして挙動を確認する一連のブログポス ト群：Call me maybe • 面白いぐらい多くのシステムが次々と壊れていく ➢（生き残ったのはZK, Riak, etcd, consulぐらい？ • 興味のある人はぜひURL参照 ➢https://aphyr.com/tags/jepsen Copyright©2016 NTT Corp. All Rights Reserved. 13

• https://aphyr.com/tags/jepsen

そのプロトコル、凶暴につき • サーバが壊れた場合の挙動をどうするかは論文に書いてあるけれど、何が 起きたらサーバが壊れたと認識するかは書いてない • • • • これらのプロトコルはサーバの故障情報を天から与えられる物として設計している プログラマ「そっか、じゃあ通信がタイムアウトしたら故障ね」←バグの温床 プログラマ「タイムアウトの閾値を大きくすれば誤検知が減って安心だね」←低速化 プログラマ「タイムアウトの閾値をどうすればいいのさ？？」←決定解はない • 分散システムの論文ではシステムに対して前提を置いていることが多いが、 なぜその前提を置いているのかは知識がないとわからない • Primary-BackupとChain-ReplicationはFail-Stop故障モデルを前提 としている • それより厳しい故障モデルの上では容易に壊れる • その故障モデルの解説はこれからする Copyright©2016 NTT Corp. All Rights Reserved. 14

故障モデル • サーバが壊れる状況のしんどさを段階的に切り分けたモデルのこと • より楽な故障モデルで動かないプロトコルは、しんどい故障モデルでは 「絶対に」動かない • Fail-Stop: 壊れたサーバはいずれ全部のサーバから故障として観測される。壊れてい ないサーバを壊れたと誤認する事や、壊れたサーバを壊れていないと誤認する事は発 生しない。壊れたサーバは二度と復活しない。 • Crash-Recover: サーバは壊れるかも知れないが復活する事もある。つまりいつまで も故障したと断言できない。 故障なし し ん ど い Fail-Stop(同期通信) Fail-Stop(非同期通信) Crash-Recovery Byzantine Copyright©2016 NTT Corp. All Rights Reserved. 15

故障モデルと複製アルゴリズム PBFT Byzantine Paxos Raft Viewstamped-Replication Broker-Replication Crash-Recovery Stake-Replication 3-Phase Commit Primary-Backup Fail-stop Chain-Replication 2-Phase Commit 故障なし Copyright©2016 NTT Corp. All Rights Reserved. 16

FLP不可能性 • Fischer,Lynch,Pattersonの3人が提唱したのでその頭文字から取って FLP不可能性と呼ぶ • 端的に言うと、下の図の赤線より下の世界では「全ての壊れていないサー バが有限の時間で確実に合意に至るアルゴリズムは存在しえない」という 事を理論的に証明した • 比較的緩い故障モデルでもダメということはそれより下では絶対に無理という事 故障なし Fail-Stop(同期通信) Fail-Stop(非同期通信) Crash-Recovery Byzantine Copyright©2016 NTT Corp. All Rights Reserved. 17

FLP不可能性を簡単に • 個々のサーバ内の時間の流れを操って絶対に合意を終わらせようとしない 悪魔が存在したと仮定する • 昼ごはんの行き先について合意を取る例 牛丼いいな カレー 牛丼 カレーいいな カレーいいな 牛丼 カレー 牛丼いいな 状態を変更しうる通信と、状態の変更のタイミングとの間が悪ければ 非決定的な状態（bivalent）な状態が無限に続きうる Copyright©2016 NTT Corp. All Rights Reserved. 18

FLP不可能性の意味する大事な所 • 分散システムの問題が複数ある中、それぞれはお互いに「帰着」しあう事 ができる 合意問題が解ければリーダー選出ができる（リーダーを誰にするかに合意する） リーダー選出ができれば合意問題が解ける（リーダーが決めた値に全員従う） 合意問題が解ければアトミックブロードキャストができる（順序について合意する） アトミックブロードキャストができれば合意問題が解ける（最初の値で合意する） 合意問題が解ければState Machine Replicationが解ける（Multi Paxos的な） Replicated State Machine が解ければ合意問題が解ける（合意するステートマシン を作ればよい） などなど • • • • • • • その中で｢合意問題が解けない｣は他の全ての問題も有限の時間では解けな い事を意味する • みんな無限の時間が掛かりうるから適当に迂回するなり諦めるなりしている Copyright©2016 NTT Corp. All Rights Reserved. 19

補足：アトミックブロードキャスト • 全員の参加者から「同じ順序」が観測できるブロード キャスト • 単一のリーダーから全員に送る、というのも立派な一つの解 • 参加者がそれぞれバラバラの順序で受信したブロードキャスト メッセージを、同一の順序で観測し直すように合意する、という 方法もある ➢個々のアルゴリズムは詳しくないのでまた今度 ZooKeeperはZookeeper Atomic Bloadcast(ZAB)プロトコルを 使っている。 Copyright©2016 NTT Corp. All Rights Reserved. 20

補足: State Machine Replication • 「同じ命令列を受け取ったら同じ状態になる」という仮想的なマシンを想 定する。 • 意識としては、オブジェクト指向でいうところのクラスが仮想的なマシン、メンバメ ソッド呼び出しとその引数のセットが命令、命令の羅列が命令列、と考えて良い • 仮想的なマシンを複製し、同じ命令列を与える事で同じ状態を複数台作り 上げる事ができる 整列アルゴリズム Walk(5) Walk(5) Walk(5) Beam Beam Beam Jump Jump Jump Walk(3) Walk(3) Walk(3) Dash(1) Dash(1) Dash(1) Copyright©2016 NTT Corp. All Rights Reserved. 21

分散システムのモジュラーアプローチ • 合意→リーダー選出→アトミックブロードキャスト→State Machine Replicationの順で問題は難しくなるが、組み合わせて解く事ができる • 問題を分解して代替可能な部品(モジュール)にするのでモジュラーアプローチ • 解どのレイヤーまでをどう解くと効率が良いか未だに決定解はない Chubby State Machine Replication ZK アトミックブロードキャスト Raft リーダー選出 Multi Paxos ZAB 合意 Paxos Copyright©2016 NTT Corp. All Rights Reserved. 22

論文を読んでそのまま実装しない事 • まともな論文であれば分散システムの歴史に立脚してい るはず • その歴史の中でそのアプローチはどの立ち位置なのか、 問題をどう分解しているのかを理解してから実装する （尺が足りないから話せないFailure Detectorとか Syncronizationとかの問題の話はまた今度） Copyright©2016 NTT Corp. All Rights Reserved. 23

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

Two Phase Commit • prepare完了前にworkerが故障したらabort • これはいい prepare abort coordinator worker ok ok worker Copyright©2016 NTT Corp. All Rights Reserved. 25

Two Phase Commit •Commit前にcoordinatorが故障したら prepare coordinator worker ok worker Phase 1 Copyright©2016 NTT Corp. All Rights Reserved. 26

Two Phase Commit •Commit前にcoordinatorが故障したら、それを検 知したリカバリノードがabortを依頼してロールバッ ク • 1つもcommitが成功していない事を調べる prepare recover y check coordinator abort worker ok worker Phase 1 Phase 2 Copyright©2016 NTT Corp. All Rights Reserved. 27

Two Phase Commit •死んだと思っていたcoordinatorが生きていたら？ • 食い違って死ぬ • Two Phase Commitは基本的に死ぬ prepare commit coordinator check abort worker committed ok aborted worker Phase 1 Phase 2 Copyright©2016 NTT Corp. All Rights Reserved. 28

Two Phase Commit •commit途中でcoordinatorが落ちたら prepare commit coordinator worker ok ok worker Phase 1 Phase 2 Copyright©2016 NTT Corp. All Rights Reserved. 29

Two Phase Commit •commit途中でcoordinatorが落ちたら回復ノー ドが表れて一つでもcommitしていたら全部を commitさせる prepare commit coordinator check commit ok worker ok worker Phase 1 Phase 2 Copyright©2016 NTT Corp. All Rights Reserved. 30

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

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

分散システムあるある • 「Paxosっていうアルゴリズムがあるんですが…説明す るには難しいのでまた今度にします」←分散システムに ついて語る人あるある • Paxos怖くないよ！合意しかできないだけだよ！ Copyright©2016 NTT Corp. All Rights Reserved. 33

Paxos • Lamport先生が「参加者の故障や復活がある場合絶対 に合意には至れない」ということを証明しようとして逆 に生み出してしまった合意プロトコル • 実は故障に耐える合意プロトコルは他にもviewstamped replicationと かstake replicationとかいろいろあるが、きっちり証明されたのは Paxosが最初 Lamport先生 最近はTLA+の布教にお熱 出典:http://lamport.azurewebsites.net/pubs/pubs.html#lamport-paxos Copyright©2016 NTT Corp. All Rights Reserved. 34

Paxos • 複雑さに定評がある(とよく言われる) • prepare, proposeがバージョン番号を持つ prepare(n) propose(n, v) proposer acceptor ok(n, v) accept(n) acceptor Copyright©2016 NTT Corp. All Rights Reserved. 35

Paxos • Coordinator • prepare(n)に対して過半数からok(n,v)が貰えたらその中で最大のnに対するvを全 workerに投げる ➢このvがnullなら自分自身のvを使う ➢nullでないならvは生死不明な他のCoordinatorのvである • Acceptor • 過去に見たprepare(n)のうち最大のnであればそれにok(n,v)を返す。そうでなけれ ばng(n') ➢vは過去に一度も合意してない場合nullかも知れない • Learner • 確定した値を読みに来る。Acceptorに最新の値vを訊きに来る。 • 過半数のAcceptorが同じ値を返さない限り、値が読めた(確定した)事にならない • Learnerが観測するフェーズまで含めるとPaxosはThree Phaseある事になる 25行で説明するPaxos: http://nil.csail.mit.edu/6.824/2015/notes/paxos-code.html Copyright©2016 NTT Corp. All Rights Reserved. 36

Paxos •2PCだと死んだシナリオ • 蘇るcoordinator •間に入った別のcoordinatorがバージョン番号を変 えるので間違った合意に至らなくなる prepare(n) propose(n) proposer prepare(n') propose(n',v) ng(n',v) acceptor ok(n,v) ng(n',v) acceptor Copyright©2016 NTT Corp. All Rights Reserved. 37

Paxos • 過半数にproposeが届いた時点でクラスタは合意した事になる • workerが復活してもok • 不完全な複製は後続のcoordinatorが複製し直してくれる prepare(x) propose(x, v1) coordinator2 prepare(n) propose(n, v1) proposer1 ok(x, v1) acceptor ok(n, v) acceptor Copyright©2016 NTT Corp. All Rights Reserved. 38

Paxos • 最後にLeanerが値を読みに来る read() learner prepare(n) propose(n, v) proposer ok(n, v) acceptor ok(n, v) accept(n) ok(n, v) acceptor Copyright©2016 NTT Corp. All Rights Reserved. 39

Multi-Paxos • Paxosは一度合意した値は二度と覆らないので、まっさらな合意を 次々と新しく作り出していく事で命令列を複製し、State Machine Replicationを成す • Learnerが読んで合意の確認が取れた命令を実行していく • 命令列に隙間ができたらスキップとかいろんな工夫があるので気になる人はRaftの論文を。 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回分 Copyright©2016 NTT Corp. All Rights Reserved. 40

RaftとPaxosの類似性 • In Search of an Understandable Consensus Algorithmという衝撃的なタイトルで登場したRaft • Understandableの価値を学会に認めさせるために苦労したのだとか • Paxosが合意(Consensus)しか解いてないのに対し、Raftは 合意はもちろんState Machine Replicationも解ける（=多く の分散アルゴリズム問題に帰着できる） • Googlerは合意アルゴリズムに過ぎないPaxosをロックマネージャ等へ 帰着させるのに大変な苦労をしたが、SMRから帰着させるのはずっと楽 であるという目論見 • PaxosのProposerとLearnerの両方をRaftのLeaderが兼ね ている点がすごい（Multi-Paxos的な高速化をしやすい） Copyright©2016 NTT Corp. All Rights Reserved. 41

Raftを手短に • Candidate(候補者)のみの状態からスタート • お互いがお互いを知っている • 全員にRequestVoteに半数以上がOKを返してくれたらLeaderへ昇格 • RequestVoteを送るまでの時間を乱数で散らす事で収束を高速化 • LeaderがAppendEntriesを送る事でSMRを実現 RequestVote(t) AppendEntries(t,h) ok ok(n) candidate candidate candidate Copyright©2016 NTT Corp. All Rights Reserved. 42

Raftを手短に • AppendEntriesの中にMulti-Paxosの重要な要素が詰まっている • Entryが空ならheartbeat変わり • candidateから返ってきたnの中の最小値を全員に送る事で「過去に合意に至ったロ グのIDを共有」できる ➢Multi-Paxosでの合意済みIDの共有もこの中に入ってる AppendEntries(t,h) AppendEntries(t,h+1) leader candidate ok(n) ok(n+1) candidate Copyright©2016 NTT Corp. All Rights Reserved. 43

Raftを手短に •AppendEntries • Leader「みんなー、Team 13番のリーダーだよ。前回のログの IDは同じTerm13の38だったね。39のログの内容はXXXだよ。 過去にみんなに合意してもらえたIDの最小値は36までだからス テートマシンは36まで進めて良いよ。」 • RequestVote • Candidate「Leader死んでる気がするから僕が立候補します。 前回のログはTerm13の46だったよ。」 • これら2つのRPCだけでMulti-Paxosに相当する事が実 現できるように練りこまれたのがRaft • 過去の合意の観測(PaxosでいうLearnerの仕事)を、Leaderが同 時に行ってRPCの中に折りたたんでいるのがかっこいい。 Copyright©2016 NTT Corp. All Rights Reserved. 44

手を動かせ •分散システムエアプ勢多すぎる • ポンチ絵とにらめっこし続ける会議をヤメロ •既成品を使うだけではなく、一緒に血反吐吐き ながらコード書きましょう • コードを書かないと見えてこないものはいっぱいある • システムの肌感覚を掴んでこそエンジニア Copyright©2016 NTT Corp. All Rights Reserved. 45