はじめに

coursera でとっている Cloud Computing Concepts で Gossip-Style HeartBeat というものが出てきたので詳しく調べてみた.

以前の仕事について

以前の仕事は異常監視。

信頼性を確保するために, 部品は冗長化されている. 最大で, 8 ノードの部品が互いを監視しあうような構成.

あるの部品が故障した場合に, 別の部品で異常を検出して, その部品を部分的に停止するような機能.

監視のロジックは単純で, 定期的に相手と通信して, 通信タイムアウトが多発したら異常と判断する.

異常検出はそれがすべてと思っていた. しかし, 実際はずっと奥が深かったのだった.

ということ. 以下, 詳しく.

Failure Detector

分散システムのノードの中で, 異常検出を担うものを 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 の特徴

Property Description

Completeness each failure is detected. Accuracy there is no mistaken detection. Speed Time to first detction of a failure. Scale Equal Load on each member/ Network Message Load. (No bottlenecks, single failure point)

HeartBeating

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

Keep-Alive ともいう.

HeartBeating の種類

実施方法は, いろいろある.

Centralized Heartbeating

ひとつのノードが他のすべてにハートビートを送る.

scale において x (single point of failure)

Ring Heartbeating

円上にならんだ, ノードがとなりのノードにハートビートを送る.

Accuracy において x.(いつも検出できない)

All-to-all Heartbeating

それぞれのノードがそれぞれのノードに対してハートビートを送る.

通信の負荷が高い.

Gossip-style Heartbeating

Better All-to-all Heartbeating.Probabilistic Failure Detector.

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

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

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

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

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

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

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

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

Membership protocols

Gossip-style を実現するための方法.

メンバシップリストというデータを互いのノードが送信しあって, 同期をする方式.

  • ノードを追加するときは, メンバシップリストにノードを登録する.
  • ノードを削除するときは, メンバシップリストからノードを削除する.

メンバシップリストは, Gossip-Style Multicast によって, あっという間に各ノードで共有される.

Snippet

たとえば, 30%の確率で まわりのノードに HeartBeat をおくっていても, ちゃんと異常を検出できる.

すべてのノードに送らなくてもいいことに驚いた.

void MP1Node::sendHeartBeat () {
  Address address;
  double prob = 0.3;

  for (MemberListEntry entry: memberNode->memberList) {

    // 自分自身はスキップ
    if (isSameAddress (getAddress (entry), memberNode->addr)) {
      continue;
    }

    // ランダムに送信する (Gossip)
    if ((((double) (rand () % 100))/100) < prob) {
      address = getAddress (entry);
      sendMessage (HEARTBEAT, &address);
    }
  }
}

Fault-tolerant Patterns

Fault-tolerant Patterns の分野は Pattern 化されている.この分野の話をもっと知りたい.

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

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

上の本の書評

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

おわりに

異常検出は奥が深かった!

今回, 調べてみて驚いたのは, こういう異常検出というのは,

  • Fault-Tolerant という用語で検索するとたくさん情報がでてくる
  • 異常検出方法は, 体系的にまとまっている
  • スケーラブルなハートビートが存在する

ということ. 自分の視野の狭さと, 分散システムのおもしろさを感じた.

特許を考えるにはあまりに無知だった

今まで, 自分の頭でいろいろな分散ノードの異常検出方法について, 特許になりそうなものを考えてきた.

しかし, この分散システムにおける異常検出というのは, すでにいろいろなアイデアが出されていることを知った.

分散シテステムの鉄板本にいろいろなアイデアが載っている.

分散システム 第二版
posted with amazlink at 15.02.23
アンドリュー・ S ・タネンバウム
楽天

それらを知らずに自分でアイデアをひねり出すことは,遠回りのような気がした. また, そういうアイデアがすでにたくさんあることにも驚きだった.

まずは先人のアイデアを身につけることを優先したほうがよい気がした. そして, それらのアイデアを知った上で, プラスアルファで新しいアイデアが生まれるかもしれないと思った.

分散システムにおける論文について調べるとおもしろいかもしれない.