🔥虚無との戦い

📝システム制御概論

14 min read

システム制御まとめ

信頼性に関わる設計パターンまとめ.

わたしがかつて📝ストレージシステムのシステム制御チームとして命を賭けた(= 爆死)領域.

🔖エラーリカバリー

もうすこし汎用的な名称があるのかもしれないが, 異常発生とその復旧について.

異常検出パターン

基本的には２つのパターン.

  • Periodic Polling(監視)
    • 常駐プロセスから状態をチェックする.
    • しばしばheartbeat, sanity check, 死活監視などなど.
    • ソフトウェアの処理だけで実装できる.
    • 割り込みを発生できないイベントも監視できる.
  • Interrupt pattern(通知)
    • 別のプロセス/スレッドからの通知を受ける.
    • しばしばwatchdog timeoutなど.
    • リアルタイムに異常を処理できる.
    • ハードウェアや OS に依存する.

待つか取りに行くか. リアルタイム性が必要ならばトリガーパターン.

Fault tolerant

フォールトトレラント.

構成部品の一部が故障しても正常に処理を続行すること.

Fault tolerant の条件

Wikipedia より.

1 単一障害点がないこと (障害に対して全体の障害とならないよう対策が施されていること)) 2 単一故障点がないこと (ハードウェア故障についても同様) 3 障害部品の隔離ができること (部分縮退) 4 障害の伝播を防ぐこと 5 代替モードがあること

dependable system

高信頼システム. 以下の要求を満たす.

  • 可用性 … システムがすぐに使えるようになるという性質.
  • 信頼性 … システムが障害をおこすことなく実行しつづける性質.
  • 安全性 … システムが一時的に正常にどうさしない状況でも, 重大な問題が生じないこと
  • 保守性 … システムが容易に回復できること.

システムの状態について

  • 故障 (fail): システムが予定した行動をとれなくなった場合
  • エラー (error): 障害を引き起こすかもしれない状態. エラーの要因を障害 (fault) という.

システム制御とは, 以下をさす.

  • 障害を防ぐ
  • 障害を除去する
  • 障害を予測する

障害は以下に分類される

  • 過渡障害 … 一度だけ発生して消滅するもの
  • 間欠障害 … しばしば発生するもの
  • 永久障害 … 欠陥が除去されるまで繰り返し存在し続けるもの

single point of failure

単一障害点. 冗長化がされていない部品.

冗長化

  • レプリケーション

同じシステムの複製を複数用意し, それら全部に同じ処理を並列に実行させ, 定足数を満足した結果を正しい結果として採用する.

  • 冗長性

同じシステムの複製を複数用意し, 障害が発生したら予備のシステムに切り替える.

  • 多様性

同じ仕様の異なる実装のシステムを複数用意し, レプリケーションのようにそれを運用する. この場合, 各システムが同じ障害を発生することがないと考えられる.

Communication Protocol Styles

Multicast

決められた複数のネットワーク端末 (ノード) に対して, 同時にパケット (データ) を送信する事.

マルチキャストは UDP を使用する. 信頼性が求められる情報通信には向かない.

Tree-Based Multicast と組み合わせることも. 最小探索木を作成して, Multicast.

Ordering

順序性を保証するために 3 つの代表的なアルゴリズムがある.

  • FIFO ordering

Multicasts from each sender are received in the order they are sent, at all receivers.

  • casual ordering

Multicasts whose send events are causally related, must be received in the same causality-obeying order at all receivers.

  • Total ordering

高信頼クライアントサーバ間通信

RPC エラーのリカバリ方法のまとめ. (分散システム p340)

  • クライアントからサーバの位置か特定できない場合

  • クライアントからサーバへの要求メッセージが喪失した場合

  • サーバが要求を受けたあとにクラッシュした場合クライアントはタイムアウトにしかみえない. 対処は 3 つある.

    • at-least-once semantics 最低一回リトライする
    • at-most-once semantics リトライせずに異常を通知
    • なにもしない. 異常を無視.

  • サーバからクライアントへの要求メッセージが喪失した場合

  • クライアントで要求メッセージを送信後に障害が起きた場合

高信頼グループ間通信

Reliable Multicalsing (分散システム p346).

Make sure that all of them receive the same updates in the same order as each other.

  • 仮想同期 (Virtual Synchrony)

Gossip (Epidemic)-Style Multicast (Protocol)

Gossip はうわさのこと. 人のうわさがあっという間に広まるのには理論的根拠があった.

Multicast には以下の課題がある

  • Nodes may crash
  • Packets may be dropped
  • 1000’s of nodes

Multicast 通信で, 特定のグループに情報を伝達するためのよい手段.

  • epidemics とも呼ばれている.
  • 速く, 信頼性があり, スケーラブル.
  • Amazon EC2, S3
  • Cassendra
  • NNTP

あるノードが通信を受信すると, ランダムに選んだ n つのノードにメッセージを送信する.

ウワサや伝染病が広まるように, 情報が伝達していく.

Unicast

ユニキャスト.単一の送信相手を指定して, データを送信する. TCP を利用することが多い.

Broadcast

不特定多数のノードに, 同時にパケットを送信すること.

高コスト.

Leader Election

選任アルゴリズム.

通常, 分散システムでは, Coordinator が存在する. Coordinator で異常が発生したさい, 次の Coordinator を決定する必要がある.

また, 異常な Coordinator が復旧したときに Coordinator を戻す必要がある.

古典的な Coordinator を決定するためのアルゴリズムは以下.

  • Bully algorithm
  • Ring algorithm

実際の実装例.

  • Google Chubby
  • Apatch ZooKeeper

Bully Algorithm

Bully (ガキ大将) アルゴリズム. つよいものが勝つというもの.

3 種類のメッセージがある.

  • Election Message: Sent to announce faster election
  • Answer Message: Respond to the election message
  • Coordinator message: Sent to announce the identity of the elected process

手順は以下

  1. あるノードが Master の異常を検出したとき, Election を開催する. Master が異常状態から復旧したときも, Election を開催する.
  2. あるノードは自身よりも高い ID をもつノードにたいして, Election Message をおくる. (生存宣言)
  3. Election Message をうけとったノードは, Answer Message をかえす. そして, 自身よりも高い ID をもつノードにたいして, Election Message をおくる.
  4. 2, 3 が続いた結果, どのノードからも応答がない, 送信するノードがない場合に, そのノードが Master となる. Master は Coordinator messag をおくる.

Ring Algorithm

リング上にノードの ID が割り振られる. あるノードは自身のとなりにならぶノードにメッセージを送る.

となりとなりにメッセージをおくることで, リングを一周したら, リングを構成するノードの生存確認がとれるので, もっとも高い ID をもつノードが Master になる.

Bookmarks

Failure detector

分散システムのノードの中で, 異常検出を担うもの.

In distributed computing, a failure detector is an application or a subsystem that is responsible for detection of node failures or crashes in a distributed system.

以下の論文で提出された概念.

Failure Detector の解説を噛み砕いて書いてある.

Failure Detector の異常検出方法

2 種類のパターンしかない.

Alive - Suspected - Failed という 3 つの状態遷移がある.

故障したかを確認するのに, タイムアウトの仕組みを使うことが多い

Ack-Ping Protocol

能動的にプロセスがお互いに”生きてますか”という旨のメッセージを送信しあう.

  • A は B に T 秒ごとに ping を投げる.
  • B は A に ack を応答する.
  • A は B からの応答が 2T 秒 以内が帰ってこなければ B を異常と判断. タイムアウトは 2T 以内.

Heartbeating Protocol

受動的に相手からの通信をまつ.

  • B -> A へ T 秒ごとに heartbeat を投げる.
  • A は T 秒ごとに heartbeat を受信する.
  • A は B からの heartbeat が 3T 秒間なければ, A は B を異常と判断.

Faulure Detector の特徴

PropertyDescription
Completenesseach failure is detected.
Accuracythere is no mistaken detection.
SpeedTime to first detction of a failure.
ScaleEqual Load on each member/ Network Message Load.
(No bottlenecks, single failure point)

📝ハートビート

HeartBeating

ネットワーク上で, コンピュータやネットワーク機器が自身が正常に稼動していることを外部に知らせるために送る信号.

Keep-Alive ともいう.

実施方法は, いろいろ.

  • Centralized Heartbeating
  • Ring Heartbeating
  • All-to-all Heartbeating
    • Gossip-Style Heartbeating
      • All-to-all よりも効率的.

Membership protocols

メンバリストを互いに送信しあって, 同期をする方式.

  • Gossip-style
  • SWIM

📝Gossip Protocol

Gosship-Style heartbeating. Better All-to-all Heartbeating. Probabilistic Failure Detector.

Multicast 通信で, 特定のグループに情報を伝達するためのよい手段.

  • epidemics とも呼ばれている.
  • 速く, 信頼性があり, スケーラブル.

すべてのノードに heartbeat をするのではなく, ランダムに選出したノードに対して heartbeat を実施する.

Load (負荷) は N に比例しないという特徴がある. つまり, いくらでもノードを動的に拡張できるということ.

Gossip はうわさのこと. 人のうわさがあっという間に広まるのには理論的根拠があった.

あるノードが通信を受信すると, ランダムに選んだ n つのノードにメッセージを送信する.

ウワサや伝染病が広まるように, 情報が伝達していく.

Amazon EC2/S3 で利用されている.

SWIM Membership Protocols

SWIM (スケーラブル, 弱一貫性のあるプロセス·グループ·メンバーシップ·プロトコル)

direct-ping と indirect-ping の両方を利用する.

ping-ack ベースのプロトコル.

  • first detection time が 一定.
  • process load が一定 (Scalable)

だれかさんの和訳.

Bookmarks

なんか, MOOC と同じ絵が載っているスライド見つけた.

Outage (停電)

以下の要因で停電にある. 70%は人間のミスで発生する.

  • Power outage
  • Over-heating
  • Human error
  • Fire
  • DOS Attack

References

Fault-tolerant Patterns

Fault-tolerant で利用される概念がコンパクトにまとまっている.

Fault-tolerant のパターン. POSA と同じ出版社.

上の本の書評

Pattern についてまとまった PDF.

グラフビュー

バックリンク

Recents