🔥虚無ずの戊い

📝システム制埡抂論

14 min read

システム制埡たずめ

信頌性に関わる蚭蚈パタヌンたずめ.

わたしがか぀お📝ストレヌゞシステムのシステム制埡チヌムずしお呜を賭けた(= 爆死)領域.

🔖゚ラヌリカバリヌ

もうすこし汎甚的な名称があるのかもしれないが, 異垞発生ずその埩旧に぀いお.

異垞怜出パタヌン

基本的には぀のパタヌン.

  • Periodic Polling(監芖)
    • 垞駐プロセスから状態をチェックする.
    • しばしばheartbeat, sanity check, 死掻監芖などなど.
    • ゜フトりェアの凊理だけで実装できる.
    • 割り蟌みを発生できないむベントも監芖できる.
  • Interrupt pattern(通知)
    • 別のプロセス/スレッドからの通知を受ける.
    • しばしばwatchdog timeoutなど.
    • リアルタむムに異垞を凊理できる.
    • ハヌドりェアや OS に䟝存する.

埅぀か取りに行くか. リアルタむム性が必芁ならばトリガヌパタヌン.

🔖RAS

Reliability, Availability, Serviceabilityの略.

信頌性に関わるスロヌガン的なもの.

cf. 🧠網様䜓賊掻系(RAS)、䞖間的にはこっちのほう知名床あり

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