FOLIOアドベントカレンダー2018 17日目です。
昨日はyasuharu519さんのDocker stop 時に別のコマンドを実行して Graceful shutdown を実現する でした。
NewSQLを調べつつ最近はストレージ周りにも手を出してみたいバックエンドエンジニアの @matsu_chara です。
今回はFAST '18のBest PaperであるProtocol-Aware Recovery for Consensus-Based Storage を読んだので紹介や感想を書きたいと思います。
自分が面白いと思ったところを中心にしたり、個人的に調べた内容が入っていたりするので正確かつ完全な情報は上記論文や関連文献等を直接読んでいただければと思います。
ざっくり
プロトコル 特有の知識を利用した分散システムにおけるストレージ障害からの回復方法(PAR=protocol-aware recovery)である、CTRL (Corruption-Tolerant RepLication)
の提案です。
多くのモデルでは、 クラッシュ
, ネットワーク断
を想定することが多いですが、今回はこれらの障害に加え、ストレージ故障
も含めます。
ここでのストレージ故障は、何らかのストレージレイヤーでの故障によりデータ破損(数byteが読み取れないetc)・アクセス不可能(read error)などが発生するケースを指しています。
この ストレージ故障
が発生したときに、合意アルゴリズム 特有の知識を利用することで データが一つ以上コピーされている場合は安全に復旧する
, すべてのデータが破損している場合は(間違ったデータを返すのではなく)利用不可
といった保証を実現するのがCTRLです。
ただし、特定のconsensus algorithm(今回の場合はRSM=Replicated state machines)での知識に依存しているので全てのシステムに適用できるわけではありません。
適用範囲こそ限定されてはいますが、RSMはpaxos, raftやzab(zookeeper)など幅広く使われているので、これについてより安全性が高まるのは重要な成果と言えそうです。
モチベーション
前述しましたが、クラッシュとネットワーク断以外にもストレージ故障によってデータ破損やアクセス不可能などの障害が発生する可能性があります。
ext2 ,3,4などではデータ破損時に破損したデータが読み取られることがありますし、btrfsではデータ破損時にアクセス不可能になります。(どちらのfilesystemでもアクセス不可能になるような障害はありうる)
またデータだけでなくinodeなどのメタデータ ももちろん破損することがあります。
このような状況下で、分散システムの1ノードについてデータ破損が発生した場合、あるあるなパターンではデータを完全削除して再起動(=まっさらなノードとして立てる)という方法があります。*1
さて、これで安全に復旧可能かと言われるとそうではありません。むしろこのリカバリ ー中にコミット済みのデータが失われることすらあります。
5台のクラスタ について下記のシナリオを考えます。
https://www.usenix.org/system/files/conference/fast18/fast18-alagappan.pdf より
データ破損が発生したノードS1のデータを削除して再起動
何らかの理由で最新commitedなデータを持ったノードS2,S3がcrash。(このときS1,S4,S5は最新データを持ってないとする)
残ったS4,S5+S1でmajorityを構成できるのでS1,S4,S5のクラスタ が誕生
このときS1,S4,S5は前述の通り最新commitedなデータを持ってないので、同時にcrashしたのは2/5台なのにcommit済みデータが失われました。(= globally data loss)*2
このような問題は当然困るので、これらを防ぐための方法が必要です。
ここで、protocolに依存しない( protocol-oblivious
な)方法ではなくprotocolに依存した( protocol-aware
な)方法を採用しているようです。*3
今回の論文ではRSMに対応したprotocol-awareなrecovery手法(PAR)を考えます。
冒頭でRSMはpaxos, raftやzab(zookeeper)で使われていると述べましたが、これらの合意KafkaやHDFS 、GFSやBigTable など様々な分散システムを構成する際に用いられる基礎的なパーツの一つになっており、これの信頼性を上げるというのは一つの大きなチャレンジと言えそうです。
CTRL (Corruption-Tolerant RepLication)
ストレージ故障はメディアエラ ー以外にもファームウェア ・デバイスドライバ ー・ファイルシステム のバグなどいろいろな事象から発生します。
今回の故障モデルでは通常のエラーに加えストレージ故障として2つのエラー(block errors, corruption)を追加します。
すでに知られている対処方法
No Detection
checksumを見ない方法。間違ったデータをクライアントに返すことがある。(多くのシステムでは基本的にはchecksum見ている。がLogCabinはsnapshotを読み取るときにchecksumを見ていないらしい)
Crash
checksum等を見ておかしかったら、そのノードをクラッシュさせる。(LogCabin, Zookeeper, etcd, ...etc。例えばzookeeperはsnapshotが壊れていた場合はcrashする。LogCabinはsnapshotではチェックしていないがlog entryではチェックしているらしい)
間違ったデータを返すことはないがどこか一箇所でも壊れていることを検知したらcrashするのでクラスタ ー全体がunavailableになるリスクが増している。
ディスク故障の場合、crashしたあとそのまま再起動しても治らないケースもあるのでマニュアルで治すまで障害が続くのも特徴。
Truncate
壊れていたデータの後続を捨てる。(RSMなので後続ログを捨てるイメージ)
自動で復旧してくれそうに見えて、comittedなデータを失うことがある。
truncateしたノードとlagがある複数台のノードでmajorityを構成できるようなケースではtruncate後のログが正になりうる。その場合一度commitしたはずのデータが(特にエラーなどを出さずに)上書きされる。*4
また、ログの先頭の方でストレージ故障が発生した場合、多くのデータをリーダーから貰う必要がありネットワーク帯域を消費したり、リカバリ ー時間の増加につながるといった問題がある。
safetyとfast recoveryに問題があるTruncateですが、一方でavailabilityは高いですしマニュアル作業などは不要。
DeleteRebuild
Truncateだが、異常を発見したら完全にまっさらにしてnodeを立て直す方法。*5
メリット・デメリットは基本的にTruncateと同じ。
MarkNonVoting
Google のPaxosベースのシステムで使われているらしい。*6
レプリケーション が追いつくまでvotingの権限を奪うことでTruncateで起きたようなsafety violationを回避することができます。
が、それでも安全でない場合がある様子。*7
またストレージ故障時にvoteできなくなるので可用性にも問題が出る可能性がある。
Reconfigure
壊れたノードを取り除いて新しいノードをjoinさせる方法。
新しいnodeをjoinさせるためにはマジョリティのコミットが必要なので、可用性に問題が出るケースがある。
BFT
究極的にはByzantine障害耐性のあるアルゴリズム を使えばストレージ故障があっても一貫性のある値をクライアントに返すことができる。
が、コストが高い(スループット が半分になる可能性もある)。また故障数fに対して3f+1ノードが必要なのもネック。
CTRL
CTRLが利用するRSM特有の知識
leader base: すべての更新はまずリーダーが受け取る
epoch: 1epochにつきリーダーは一人。ログは<epoch, index>の組でユニークに特定できる。(indexはログエントリーに振られる番号)
leader completeness: leaderはすべてのcommitedなログを持っている。
CTRLではlocal storage layer
とdistributed recovery protocol
の2つがセットになって復旧を行う。
具体的にはstorage layerがストレージ故障を検出し、distributed recovery protocolが冗長化 されたデータから復元する役割分担になっている。
CTRLが保証すること
コミット済みの正しいデータが最低一つあれば、それを使って修復を行う
コミット済みのデータは消失しない。
すべてのコピーが故障した場合、unavailable状態になる(暗黙に上書きなどを行わない)
さらなる保証:uncommittedなデータの故障についても可能な限り早期に決定を行う(可用性向上)
ストレージはログ・スナップショット・メタデータ の3つを永続化する。
ログはRSMのエントリー単位で故障を検知する(protocol aware)
snapshotは大きくなるのでチャンク単位で故障を検知する
メタデータ はノード固有の情報を持つので他ノードからのリカバリ ーは不可能である。そのためローカルに2つのコピーを持って復旧を行う。
storage faultの検知はreadのreturn codeとchecksumで行う。メタデータ のエラーもopen時のエラーハンドリングで検知可能。*8
大抵のケースで、メタデータ fault時はcrashさせる。
これはsafetyには影響しないがunavaiableになる時間が増える。
ただデータブロックのほうがメタデータ ブロックに比べて圧倒的に多いので、相対的には許容可能な停止時間になるだろうとの見込み。
CTRLで行われる故障の分離
単にchecksumミスマッチを起こした場合でも下の2つの場合を分離可能
更新途中でノードがクラッシュした場合(crashed)
古いログが壊れた場合(corrupted)
前者の場合はackを返してないはずなので安全にログをdiscardできる。
コミットされているかどうかはpersist record p_i
をevent entry e_i
の後のタイミングで書きこむことで確認できるようになる。
通常は write(ei), fsync(),write(pi), fsync()
のようにするが、厳密な判断をしたいわけでなくcrashのケースを拾いたいだけなので、パフォーマンスのネックになるfsyncを除いてwrite(ei),write(pi),fsync()
としている。
e_i
, p_i
の順序が入れ替わるかもしれないことに注意。(今回のケースでは大丈夫ですが、fsyncを入れないと、どうなるか?といった議論はちょうど去年のアドベントカレンダー に書いた内容で議論されているのでぜひ https://matsu-chara.hatenablog.com/entry/2017/12/09/110000 という脱線)
つまり、persist recordが存在しなければcrashであることがわかる。存在する場合にeが最後のイベントだと判定が行えなくなるがその場合はcorruptと判定して他ノードからリカバリ ーする。*9
*10
なおsnapshot等はtemporary fileに書いたあとatomicにrenameを行うことで破損を避けています。
CTRLで行われる故障箇所のidentify
故障したデータが何だったのか?という特定(identify)を行う必要があるため、identifierを別途保存してどのログやデータが壊れたか分かるようにしている(ついでにpersist recordも兼ねる)。内容としては <epoch, index>
のペアがあればログエントリーを一意に特定できる。
identifierは物理的にデータとは別の場所に保存されるため、基本的に同時に壊れる可能性は低い。もし同時に壊れていた場合はnodeをcrashさせる。(unavailableにはなるが、頻度が低いため許容可能)
CTRLでの具体的なリカバリ ー方法
ナイーブな方法としてLeader Restriction. リーダーになる際にfaultyでないことを保証する方法がある。
リーダーがすべてのイベントを持っているので、フォロワーのストレージ故障時は基本的にはリーダーからコピーすればOK。
ログを問い合わせ(<epoch, index>でユニーク)て、リーダーが知らない場合は正式にcommitされたものではないのでdiscardする。
ただし、この方法だとリーダーになる前にすべてを保証しないといけなくてunavailableになる可能性が高くなる。
一つでも無事なコピーが存在していればクラスタ 全体は継続して利用可能にしたい。
そのため以下のようにクラスタ ーから情報を収集して判断を行う。
リーダーが正常で、フォロワーが故障している場合
修正は容易。
リーダーからコピーする
リーダーが知らない場合は、uncomittedなものなのでdiscardする
リーダーが故障している場合
リーダーはフォロワーに<epoch, index>を問い合わせる。レスポンスは以下の3種が考えられる
(have) フォロワーが壊れていないログを持っている
(dontHave) フォロワーがログを持っていない
(haveFaulty)フォロワーはログを持っているが、壊れている。
リーダーはこれらのレスポンスを集めて以下の判断をする
一つ以上のフォロワーから壊れていないログが帰ってきた(have)場合はログを修復する。
フォロワーの過半数 がログを持っていない場合(dontHave)、未コミットなので該当イベントとその後続を捨てる
haveFaultyが帰ってきた場合は1, 2のどちらかになるのを待つ*11
Snapshotリカバリ ー
ログ同様snapshotも壊れる可能性がある。ZooKeeperとLogCabinはどちらもsnapshotが壊れていた場合に正しくハンドルできないケースがある(らしい)。
スナップショットは本質的にコミット済みの物のみを含むのでdiscardできない点がログと異なる。
また各ノードが独立してsnapshotを取るので、uniqueなidentifierで取得といったことができない(そのidで必ずsnapshotを取るわけではないので)し、その場合chunk単位で持ってくるのも難しいのがハードル。まるっとsnapshotを送ると帯域を消費するため避けたい。
これを解決するためにリーダーがsnapshotを取るindexについて合意を取ることで同一のsnapshotを生成する。
過半数 がsnasphotを取り終えたらGC markerを挿入して再び合意を取りつつログをGC する。
リカバリ ー時は以下のように判断する。
ローカルログがGC されずに残っている場合はそこから復旧
GC されている場合は、他ノードでsnapshotがあることが保証されているので、そこからコピー
フォロワーがリーダーの知らないindexを問い合わせた場合(フォロワーが古いindexを送る場合など)は、リーダーが最新のsnapshot全体を送ります。*12
まとめ
今回の論文では以下のようなテクニックが使われていました。
a crash/corruption disentanglement
a global-commitment determination
leader-initiated snapshotting
この後、実装についてとパフォーマンス評価が続いていますが今回は割愛したいと思います。興味が出たらぜひ読んでみてください!
Python ベースのモデル検査やTLA+ specification of RaftにCTRLのログリカバリ ーを追加して検査もしているようです。*13
related worksにはいくつかのstorage fault対策をほどこした研究が挙げられています。基本的には故障台数の上限を決めて動かしているようです。(わりと自然な仮定なような気もします)CTRLは一つでもコピーが残っていればなんとか復旧してくれるのでそういう実用面では優位性がありそうです。
一方でPASCはメモリエラーにも対応できるようです。(CTRLでstorage faultに耐え、PASCでメモリー エラーに耐えるなどの併用による強化も可能らしいです。)
感想
FASTは普段はあまり読まないんですが、たまに読むと課題設定からし て勉強になることが多いのでFileSystemマイスター以外の方にもおすすめです。
zookeeperがお手軽にinconsistentにされることが多い気がするんですが・・不憫。(それだけ使われているということでもあります)
分散システムのみならずアプリケーションの整合性を考えるという意味ではファイルシステム の整合性は切っても切り離せません。
うまく動くでしょ、と思っていたらファイルが破損して・・みたいなことは実運用にでかいシステムを乗せると 稀によくある
ことだと思うので、
本番で論文に出てくるようなものを直近で使う予定がなくても、ここでおかしなことになるといった知見や、それに対する解決方法などから得た新しい概念はどこかで活かせるのではないかと思います₍₍ (ง´・_・`)ว ⁾⁾