分散コンピューティング / 障害

分散コンピューティング

障害の分類

　障害耐性のあるシステムの目標
　　「構成部品の障害があっても，システム全体として正常に機能すること」

頻度による分類

• 一時的障害
  　一回発生すると，もう同じ障害は起こらない．
  

• 間欠障害
  　いつでも発生しておさまる障害．何度も発生する．
  

• 永久障害
  　一回発生すると，修理するまで回復しない障害．
  

影響による分類

• fail-silent障害
  　障害が発生すると，黙り込むタイプ．
  

• ビザンチン障害
  　障害が発生すると，違った情報を発生するタイプ．（タチが悪い）
  

同期によるシステムの分類

• 同期システム
  　メッセージを送ると，必ず一定時間後に返ってくることが保証されてるので，障害検出がしやすい．
  

• 非同期システム
  　応答が一定時間以内に返ってくることは保証されないので，障害検出がしにくい．
  

RPCで発生する障害

クライアントがサーバを見つけられない

• 原因
  

  ・サーバがダウンしている
  ・クライアントのスタブが古く，新しいサーバを見つけられない

• 対策
  

  ・サーバを起動してあげる
  ・新しいスタブで，クライアントをコンパイルする

処理要求メッセージが失われる

• 原因
  
  • IPパケットは性質上，無くなる事がある．
    

• 対策
  
  • メッセージを送る際，カーネルでタイマーを設定する．
    　　→ 応答メッセージが設定時間たっても帰ってこなかったら再送する．
    

• 問題点
  
  • 応答メッセージが遅れてるだけかもしれない．
    　　→ 再送してしまったら２回要求を送ることになる．（２回処理してしまう）

• 解決策
  
  • 何回処理しても大丈夫な処理の要求を作る（Idempotentトランザクション）
  • 処理要求メッセージにシーケンス番号を振り分けて，区別する．
    　　（重複メッセージの場合は破棄してくれる）

処理応答メッセージが失われる

• 原因
  
  • IPパケットは無くなる事がある．
    

• 対策
  
  • 応答メッセージを送る側のカーネルでタイマーを設定．
    　　→ 設定時間たっても伝達確認が来なかったら再送する．
    

• 問題点
  
  • クライアントからの伝達確認が遅いだけかもしれない
    　　→ シーケンス番号をつければ，重複した場合は破棄してくれる．

サーバがクラッシュする

• サーバでの処理
  • 受信
  • 実行
  • 応答
    

• 問題点
  　この３つの処理のうち，どの時点でクラッシュしたかが区別できない．
  　　→ 受信してからか，実行してからかの区別が難しい
  • 受信してからクラッシュした場合
    　もう一度，クライアントが処理要求を再送すればよい．
    

• 受信・実行してからクラッシュした場合
  　うっかり，もう一度実行させると結果が変わってしまうかもしれない．
  　　→ サーバの状態を確認して対処しなくてはいけない．

• 保証すべきこと
  

• 最低一回の実行：要求を送り続ける
  

• 最高一回の実行：失敗があったら諦める
  

• 無し：何も保証しない
  

• 正確に１回の実行：理想的だけど，実現は不可能
  

• システムの一貫性を回復
  　保証されていることによって，障害のあとの回復処理が異なってくる．

クライアントがクラッシュする

• 処理要求を送った後にクラッシュした場合
  　　余計な処理がシステム内に残ることになるので，これの始末をつける必要がある．

冗長性の利用

　システムの障害耐性を実現する一般的な方法．

情報の冗長構成

　間違った情報の回復のために，冗長な情報を付加する
　（ex.エラー回復のためのハミング符号）

時間的な冗長構成

　実行して，もし必要であればまた繰り返す → 一時的障害や間欠障害に有効
　（ex.アトミックトランザクションを使った繰り返して，中止したトランザクションを再度実行する）

物理的な冗長構成

　冗長な装置を付加する

例として，冗長なプロセッサを付加した場合の２つの方法．

• Active Replication（複製）
  　同一の構成要素を複数並列に動作させる．
  　全てのサーバに順番通り要求を送り，全てのサーバが同じ処理を行う．
  

• k fault tolerant
  　k個の構成部品の障害が起こってもシステムとして障害とならないようなシステム

  ・fail-silentの場合　 ：k+1個の冗長構成
  ・ビザンチン障害の場合：2k+1個の冗長構成
  　　k=1のときは，３つの構成部品を並列に動作させ，その結果の多数決をとる
  　　（TMR：Triple Modular Redundancy）

• Primary Backup
  　プライマリサーバを用意しておき，そのサーバがすべての仕事をしておく．
  　そのサーバに障害が起こると，バックアップサーバが仕事を引き取る．
  　　→ サーバの変更はアプリケーションからは見えない

• 利点

  ・通常の処理は，１つのサーバに送ればいいので簡単．
  ・マシンはプライマリサーバとバックアップサーバの２つだけでいい．

• 欠点

  ・ビザンチン障害時には，プライマリサーバが正常に動作してるように見えてしまう．
  ・障害のタイミングによって，２つのサーバによって処理が複数回行われてしまうかもしれない．

• 解決策
  

  ・バックアップがプライマリに対して正常かどうかの確認メッセージを周期的に送る．
  　→ プライマリの応答が遅いのと，クラッシュを区別するのが難しい
  ・バックアップに切り替えたら，ハードウェアによってプライマリを強制的にストップさせる．

  　

障害に対する合意

　分散処理における合意では，プロセスがすべて正常に合意しなければならない．
　→ 目標：すべての正常なプロセスの間で合意に達すること

• システムの条件
  • メッセージが正しく配達されるか
  • 障害は，fail-silentかビザンチンか
  • システムは同期か非同期か

２つの軍隊の問題

　プロセスは正常だが，ときどきメッセージが無くなる（通信の信頼性が無い）
　

• 状況
  

  ・谷に赤軍（5000人）がいて，その両側の丘の上に２つの青軍（3000人ずつ）がいる
  ・青軍が赤軍を攻めるときに，１つの軍だと負けてしまう
  ・２つの軍がいっぺんに仕掛ければ赤軍に勝てる
  ・反対側にいる青軍に連絡をとって，合意の下で一斉攻撃を仕掛けたい
  ・伝令は谷を通っていくため，赤軍に捕まってしまう心配があり，通信の信頼性が無い

• 問題の解決
  　この問題は解決できないことを証明する条件

  ・最後のメッセージが配達できないと実行できない
  ・最後のメッセージが正しく配達することが保証できない

ビザンチン帝国の将軍の問題

　通信は信頼できるが，プロセスに異常があるかもしれない．

• 状況
  

  ・谷に赤軍がいて，まわりの丘にn個の青軍（それぞれに将軍）がいる
  ・青軍の間の通信は１対１で電話が使えて信頼性がある
  ・青軍のn人の将軍の内，m人は反逆者で，合意を阻止しようとする
  ・忠実な将軍は真実を伝え，反逆者はすべての将軍にウソをつく

• 問題の解決
  

  ・各将軍は，自分の兵力を他の全ての将軍に伝える
  ・その後，それぞれの各将軍は集まった情報から全ての将軍の兵力リストを作る
  ・そして，各将軍はそのリストをまた他の全ての将軍に伝える
  ・各将軍は受け取ったすべてのメッセージから多数決によって真実を決める

• Lamportの証明
  　m個の障害プロセスがあるとき，2m+1の正常なプロセスがあれば合意に達する