Replicated State Machinesでのストレージ故障からのリカバリー

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

さて、これで安全に復旧可能かと言われるとそうではありません。むしろこのリカバリー中にコミット済みのデータが失われることすらあります。

5台のクラスタについて下記のシナリオを考えます。

f:id:matsu_chara:20181130203110p:plain
https://www.usenix.org/system/files/conference/fast18/fast18-alagappan.pdf より

  1. データ破損が発生したノードS1のデータを削除して再起動
  2. 何らかの理由で最新commitedなデータを持ったノードS2,S3がcrash。（このときS1,S4,S5は最新データを持ってないとする）
  3. 残った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)

ストレージ故障はメディアエラー以外にもファームウェア・デバイスドライバー・ファイルシステムのバグなどいろいろな事象から発生します。 今回の故障モデルでは通常のエラーに加えストレージ故障として２つのエラー(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 の２つがセットになって復旧を行う。 具体的にはstorage layerがストレージ故障を検出し、distributed recovery protocolが冗長化されたデータから復元する役割分担になっている。

CTRLが保証すること

  • コミット済みの正しいデータが最低一つあれば、それを使って修復を行う
  • コミット済みのデータは消失しない。
  • すべてのコピーが故障した場合、unavailable状態になる（暗黙に上書きなどを行わない）
  • さらなる保証：uncommittedなデータの故障についても可能な限り早期に決定を行う（可用性向上）

ストレージはログ・スナップショット・メタデータの３つを永続化する。

  • ログはRSMのエントリー単位で故障を検知する（protocol aware)
  • snapshotは大きくなるのでチャンク単位で故障を検知する
  • メタデータはノード固有の情報を持つので他ノードからのリカバリーは不可能である。そのためローカルに２つのコピーを持って復旧を行う。

storage faultの検知はreadのreturn codeとchecksumで行う。メタデータのエラーもopen時のエラーハンドリングで検知可能。*8

大抵のケースで、メタデータfault時はcrashさせる。 これはsafetyには影響しないがunavaiableになる時間が増える。 ただデータブロックのほうがメタデータブロックに比べて圧倒的に多いので、相対的には許容可能な停止時間になるだろうとの見込み。

CTRLで行われる故障の分離

単にchecksumミスマッチを起こした場合でも下の２つの場合を分離可能

  • 更新途中でノードがクラッシュした場合(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>を問い合わせる。レスポンスは以下の３種が考えられる

  1. (have) フォロワーが壊れていないログを持っている
  2. (dontHave) フォロワーがログを持っていない
  3. (haveFaulty)フォロワーはログを持っているが、壊れている。

リーダーはこれらのレスポンスを集めて以下の判断をする

  1. 一つ以上のフォロワーから壊れていないログが帰ってきた(have)場合はログを修復する。
  2. フォロワーの過半数がログを持っていない場合(dontHave)、未コミットなので該当イベントとその後続を捨てる
  3. 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にされることが多い気がするんですが・・不憫。（それだけ使われているということでもあります）

分散システムのみならずアプリケーションの整合性を考えるという意味ではファイルシステムの整合性は切っても切り離せません。 うまく動くでしょ、と思っていたらファイルが破損して・・みたいなことは実運用にでかいシステムを乗せると 稀によくある ことだと思うので、 本番で論文に出てくるようなものを直近で使う予定がなくても、ここでおかしなことになるといった知見や、それに対する解決方法などから得た新しい概念はどこかで活かせるのではないかと思います₍₍ (ง´･_･`)ว ⁾⁾

*1:本番で愚直にやるとレプリケーション負荷で死ぬシステムもあるのでご利用は計画的になやつ

*2:リカバリして最新に追いつくまでhealthyなnodeとしてカウントしなければ、そもそも前提エラーになるような気もしなくもない？と思った人！（僕がそうなんですが・・）この後その方式が出てくるのでご期待ください

*3:protocol-obliviousだと何故だめなのかに関する議論はあまりなかったように読めました。要勉強。

*4:この辺は前述したまっさらにして再起動パターンで起こる現象と同じですね。

*5:検証中とかによくわかんなくなったらとりあえずこれやりますよね

*6:引用されてる文献はリアルワールドPaxosノウハウ集で有名なやつ（？）ですね https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf

*7:リーダー入れ替え後に古いリーダーからのエントリーを受け入れてしまうようです。詳しくは文献70を参照

*8:メタデータ破損時はそもそもファイルが開けなくなるという想定

*9:crashedにするのはあくまでも最適化なので、crashedなものをcorrupt判定してしまっても保証にとっては影響がないということですね。

*10:pもcorruptedになるのでは？と思うが、pもchecksumにより検査されるのと、p自体は小さいのでatomicに書かれるためcrashによってはcorruptedにならないだろうとのこと。なおeとpが同時にcorruptedになった場合は後者と判断し、慎重にリカバリーを行う。

*11:過半数がhaveFaultyで、残りがdontHaveを返してきた場合と、全体がhaveFaultyを返してきた場合について記載がないように思える（見落としかも）ものの、corruptedであるというエラーを返すのが目的だったと思うのでそのようにするのかなと思っています。

*12:すべてのノード上でsnasphotが壊れていた場合のケースがなさそうでしたが、その場合はもはやどうしようもなさそうですね・・。

*13:そこも気になったんですがさらっと書いてあるだけでした。