分散システムにおける強い障害モデルの考察

「マルチメディア通信と分散処理ワークショップ

J

平 成5年11

月

分散システムにおける

強い障害モデルの考察

藤 藤 正 史

三菱電機株式会社

情報システム研究所

marcy@ecs

i

.

sl.melco.co.jp 制御システムや情報処理の基幹系システムを代表として、コンビュータシステムの 停止が社会に重大な影響を及ぼすようになってきている。本稿では、強い障害モデ ルとして、 Anticipated障害モデルを提案し、停電、リアルタイムプロセス、冗長構 成のプロセッサでのモデルの適用例について説明する。 A-障害モデルが適用可能な 場合には、簡単な障害回復処置を行なえば良く、リアルタイム性、連続運転性が重 要となる制御システムなどでは、有効なモデルである。

1

はじめに

コ ン ピ ュ ー タ シ ス テ ム の 発 展 と 利 用 形態の多様化により、システム自体が停 止することが社会に大きな影響を及ぼす ようになってきている。例えば、発電所 の制御システムの停止や暴走はその企業 に多大なる損害をもたらすだけでなく、 近隣地域の住居環境に重大な障害をもた らしたり、人命を損なう可能性をも含む ことになる。制御システムでは、このよ うなコンピュータの停止による破滅的な 事態を避けるためにさまざまな手段がと られている。 たとえば、 watchdogタイ・マのあふれ を検出することで、そのコンビュータの 停止を検知し、その処理をパックアップ するというシステムが構築されてきてい る。また、特別なハードウェアなしでも 複数のコンピュータータ問でKeep-AIive メッセージを交換することにより、自分 の状態を他のコンピュータに通知し、他 のコンピュータでの障害の発見を可能と するような構成をとり、障害発見とそれ に対する処置を行なってきた。 一 方 、 耐 障 害 性 の 研 究 も 進 み 、 障 害 モ デ ル の 強 さ に よ る 階 層 化 や [1]、その うちのいくつかの障害モデルに耐えるア ルゴリズム

[

2

]

，

[

3

]

，

[

4

]

、これらのアルゴ リズムを用いたシステム [5]が発表され てきている。 障 害 モ デ Jレの研究においては、 Fail -Stop障 害 モ デ ル 、 ク ラ ッ シ ュ 障 害 モ デ A Study of a Strong Failure Model for Distributed Systems Masashi SAITO Mitsubishi Electric Corporation， Computer and Infonnation SystemsLaboratory

Jレ、 Omission障害モデル、ピザンチン 障害モデルなどが提案されており、それ ぞれの障害モデルにおいて使用可能な合 意アルゴリズム [6]，[7]，[8]も提案されて きている。 と こ ろ が 、 実 際 の 制 御 シ ス テ ム で は、障害に対する仮定をすることができ ない。つまり、どのような障害も起こる 可能性があるため、それらの障害に対処 しなければならない。一方、障害に対す る仮定が弱ければ弱いほど、それに対処 するためのアルゴリズムは複雑となって しまう。その結呆、弱い仮定の隙害に対 するアルゴリズムの実装の正当性の検証 が大変となるだけでなく、実時間性が必 要となる制御システムではアルゴリズム の複雑さゆえに適用できない場合が多 かった。そのため、現状の制御システム では、何らかの形で人間が介在し、障害 に対処することが多かった。 Fail-Stop障害モデルやクラッシュ障 害モデルだけを仮定した場合には、比較 的簡単なアルゴリズムを用いることで対 処 可 能 で あ る こ と が 知ら れ て い る [3]， [4]0例えば、 Fail-Stop障害を仮定した システムにおける排他制御のアルゴリズ ムでは、危険領域に入る前の検査ループ において、現在危険領域に入っているプ ロセスの状態を調べることにより、危険 領域に入っているプロセスの障害による 他のプロセスの飢餓を防ぐことができ る。 このように、強い仮定の障害であれ ばあるほど、それに対する対処方法は簡 便となる。つまり、ある装置などの付加 により、強い障害モデルを提供すること が可能であるならば、障害時の対処が簡 単になり、さまざまなシステムで使用で きる可能性がでてくる。 本稿では、この強い障害モデルとし て、 Anticipated障害モデル(以下、 A-陣 筈モデJレと略す)を提案する。また、 A・ 障害モデルが実際に適用可能な実際の障 害として、停電、リアルタイムプロセス におけるデツドラインの未保証、冗長構 成プロセッサの障害をとりあげて説明す る。 A-障害モデルが適用可能な場合に は、非常に簡単な障害回復処置を行なえ ば良く、リアルタイム性、連続運転性が 重要となる制御システムにおいて、扱い やすい障害モデJレを提供しているo

2

停電事象

2

.

1

.

停電の確率

停 電 と い う 障 害 は 、 コ ン ピ ュ ー タ を 動作させるための電源の供給が停止し、 コンピュータの継続的な処理を阻害する ものである。停電の要因は、気象条件や 発電所や変電所の障害などによるのであ るが、コンピュータから見た場合にはこ の原因は本質的ではない。 日本における停電の度合は、頻度が 多い地域で一年で 30 回以下(全国平均 では

1

5

回以下)、その

90%

が

0

.4秒以下 の電源断である

[

9

]

0

こ れ ら の 短 い 電 源 断 は 瞬 停 と 呼 ば れ、送電線への落雷による電力系統の異 常を保護リレーによって切り離し、別系 統 へ 接 続 す る 場 合 に 発 生 す る こ と が 多 い。しかし、このような短い期間の停電 であってもコンピュータが停止すること となるo したがって、停電に対処するた めの第一の方策は、瞬停をマスクするこ とである。以下では、ある短い時間、例 えば 1秒 1以下の停電を瞬停として扱 う。この遷移は図1.のようにモデル化 することができる。ここで、矢印上の記 1.1秒という固定値は、特別の意味を持 たない。ここでは、 0.4秒以上のある 時間を仮定している。

号は、確率をあらわしているo 図1.瞬停時の状態遷移 停電の多頻度地域においても停電回 数が30回程度ということは、図1.の瞬 停状態への遷移の確率σ は非常に小さ いといえる。また、先に述べたように、 瞬停が起きた後にすぐに回復する確率は 90% と 見 積 も る こ と が 可 能 で あ る の で、図1.のpは 0.9であると考えて良

2

.

2

.

UPS

による停電の対処

UPS(Uninterruptible Power Supply)は、 内部にバッテリを保持し、停電が発生し たさいに、障害内容の通知、障害のマス クなどの動作を行なうものである。した がって、 UPS を用いると、停電の 90% に及ぶ、瞬停をマスクすることが可能と なる。

[

9

]

の統計によれば、停電には瞬停だ けでなく、より長時間の電源断が起こる 可能性も示しているo つまり、 1秒以上 の停電の場合に対しでも、何らかの対処 を

4

子なう必要治Tあるo しかし、 UPSが 保持しているバッテリの容量も無限では なく、上限が存在する。したがって、 UPSを用いたとしても、長時間停電の 場合にはいつかは停電が起こることを意 味しているo この状況は、図 2. のようにモデル化 することができる。 図2.中のpは図1.のものと同じであ る。ここで、比較的長い一定時間(例え ば 5分)の停電継続を検知した場合に、 図

2

.

停電の状態遷移 その後の一定時間(例えば15分)以内に 停電から回復する確率(1 -l)は、 pに 比して非常に小さい。これは、 sの分散 は、統計的な傾向がなく、停電のケース に大きく依存していることによるo した がって、比較的大きな確率 tで長時間停 電となる。 長時間停電の場合には、 UPSで提供 できるバッテリを使い果たし、システム 停 止 に 追 い や ら れ る こ と に な る 。 し た がって、一定時間停電検知した場合に は、長時間停電になると考えて良い。

3 A

ー障害モデル

3

.

1

.

停電と

A-

障害モデル

図 2. の一定時間停電検知状態におい て、確率 tで未来の状態を予言している といえる。このように、 『近い将来、あ る確率でプロセスが障害を起こすj状態 を障害として扱い、 A-障害と呼ぶ。 A-障害が起こった場合には、自分の 障害を、自発的な通知により伝達するこ とができる。したがって、停電の場合に は、一定時間停電検知の状態において、 自ら終了処理を開始し、自分の状態を他 のプロセス(コンピュータ)に通知す る。この通知を受けとったプロセスは、 障害を起こしたプロセスの近未来の状態 に応じて、処置を行なうことができる。

A-障害モデルを障害の階層に当ては めてみると、 A-障害モデルは、非常に 強い仮定を伴うモデルである。 Fail-Stop障害モデルは、あるプロセ ス P において障害が起きた場合に、他 のプロセスの項 Failed(P) がその瞬間に 真となっているものである。この実現は 非常に難しく、いくつかのシステムで は、ある上限時間内に、 Failed(P)が真 となるとして、実現している [5]0これ と同様のことが、 A-障害モデルでも実 現できる。 Fail-Stop障害モデルでは、障害が起 こったことは他のプロセスに通知される が、そのプロセスのどこで隊害が起こっ たかについては知らされない。したがっ て、 Fail-Stop を起こしたプロセスが一 貫性のある状態であるかどうかについて は、何もわからない。 A-障害モデルでは、障害が起こった 時点でも、一定時間継続的な処理が可能 であるので、自分が障害を起こすであろ う場所やその時のプロセスの状態を通知 することも可能である。したがって、以 下に示すような処置を行なうことによ り、システム全体としては、継続的な処 理が可能となる。 (1) A・障害を起こしたプロセスは、 処理中のイベントを完了させ、自 プロセスの状態を一貫した状態と し、処理を中止、又は停止する。 (2) A-障害の通知を受けたプロセス は、障害後に処理を請け負うプロ セスを起動し、その後のイベント 処理を継続的に行なう。 本稿では、プロセスが A・障害を起こ したとしても、そのプロセスは、ある一 定時間動作可能であると仮定している。 したがって、 A・障害は、以下の二つの 性質を満たしたものであるo (i)近い将来、ある確率でプロセスが陣 筈を起こす。 (ii)障害検知後、一定時間正常動作する ことカfできる。 つまり、 UPSを用いた停電事象の緩 和は、 A-陣害モデルに当てはまる。

3

.

2

.

実時間性と

A

・障害モデル

A-障害モデルは、停電だけでなく他 の場面でも適用可能である。 まず、リアルタイムシステムにおけ る例を説明する。ここでのリアルタイム システムは、時間制約を持つプロセスの 集合により構成される。ここで、あるプ ロセス Pに注目し、 Pのデッドラインが データが生成されてから

s

であったと し、平常の処理においては、プロセス P は

0

.

5

d以内で処理が完了していたとす る。 ある時にプロセス P の 処 理 時 間 が データ生成の時聞から

0

.

9

9

dかかるよ うになってきたとしよう。これは、プロ セス P が他の高い優先度を持つプロセ スにより処理が遅らされたことを意味し ており、この状態が長く続いた場合に は、プロセス P がデッドラインを満た せなくなってしまう確率は高いと考えら れる。 この時に、プロセス P は自分自身が A・障害を起こしたと他のプロセス(コ ンピュータ)に通知することで、.プロセ ス P の処理を他の場所に移送 (migrate) することで対処することが可能となる。 ここで、プロセス P は先に示した A-障害の第2の性質により、一貫した状態 で処理を停止するとが可能となる。

3

.

3

.

冗長プロセッサと

A-

障害モデル

冗長構成したプロセッサにおいても A・障害モデルとして扱うことが可能で ある。ここでは、 3つのプロセッサで各 命令を同期させながら実行し、それらの 実行結果を多数決回路により決定するプ ロセッサを取り上げる。これらの冗長プ ロセッサが正常に動作していれば、すべ ての実行結果が同一であるが、あるプロ セッサが障害をおこした場合には、二対 ーの多数決により結果を選択することに なる。 も と も と 冗 長 構 成 を し て い る プ ロ セッサであるため、障害を起こしたプロ セッサを切り離すことにより処理を継続 することができるが、残ったこつのプロ セッサが異なる結果を出した、つまりも う一つのプロセッサも障害を起こす可能 性が残されているため、早い時期にこの プロセッサを交換しなければ、今後の処 理が正当であるということが保証できな い。この場合にも、実際に問題となる障 害は、未来に起こることを示しているo また、障害を起こしていないプロセッサ は正常動作できるD したがって、プロ セッサとしての状態が一貫した時、例え ばすべてのプロセスを他のコンピュータ に移送し、オペレーティングシステムが 停止した後に修理を待つことができる。 この場合には、実際に、いつ二番目 の障害が起こるかの確率は、最初に障害 を起こしたプロセッサと同ーであるの で、停電の時のように障害が起こる確率 が増加するわけではない。しかし、制御 システムなどの応用では、速続運転性が 非常に重要な要素となるため、一つのプ ロセッサの障害を全体の障害の前兆とと らえるのは適切な処置と言える。

4 A

・障害モデルと障害の対処

4

.

1

.

障害の通知と発見

A-障害モデルでの障害の通知と発見 についてクラッシュ障害モデルと比較す る。 ク ラ ッ シ ュ 障 害 モ デ ル は 、 あ る 時 点 であるプロセスカまクラッシュし、その後; の入力に対する処理が行なえないだけで なく、出力も行なえない状態を示す。 クラッシュ障害はある瞬間に起こる ために、クラッシュ障害を起こしたプロ セスは、自分のクラッシュ状態を他のプ ロセスに通知することができない。 クラッシュ障害を発見する手法とし ては、以下に示す実装が行なわれること が多い。 (1) Watchdogタイマ: あるプロセスが定期的にWatchdog タイマをクリアする。 Watchdogタ イマがあふれた場合には、特別な 割り込みが上がるとともに、外部 にその割り込みが伝達される。 (2) Keep-Aliveメッセージ: プロセスは協調処理を行なってい るイ也のプロセスと Keep-Aliveメッ セージを送り合い、その存在を確 認する。あるプロセスからのメッ セージが一定時間以内に受けとれ ない場合には、そのプロセスはク ラッシュ障害を起こしたものとし て扱う。 Watchdogタイマによる実装は、実際 に陣害を起こしたプロセス(プロセッサ) からの通知が自発的に行なわれ、そのプ ロセスが障害を起こしたことは確信でき る。しかし、 Watchdogタイマがあふれ るまでの遅延が必要である。 Keep-Alive による実装の場合には、 実際に障害が起きたかどうかの判定は、 外音ISからの観測にもとづいている。した

がって、実際にはそのプロセスは障害を 起こしていない場合にも、障害として取 り扱ってしまう。 ところが、協調処理を行なっている 複数のプロセスをグループとしてまと め、障害を起こしたとみなしたプロセス をそのグループから除外することによ り、以降の処理は正当性を満たすことが できる [10]0 この場合にも、定期的なメッセージ 交換のための間隔の遅延が必要となる。 A-障害の場合には、これらの手法を 用いる必要がない。 A- 障害を検知し、 そのプロセスの状態を一貫したものとし たの後に、他のプロセスに自分の障害を 伝達することができるため、他のプロセ スが障害発見にかかる時間はメッセージ 伝達時間と等しい。 これは、 Unixのシャットダウンメッ セージが、他のコンピュータに通知され ることと似ている。つまり、 A-障害の 場合には正常にコンピュータが停止した ものとして扱うことが可能である。 また、制御システムのようのリアル タイム性が必要なシステムでは、障害発 見の遅延時間が致命的な事態となること がある。センサのデータが1秒毎に生成 されている時に、そのデータを処理して いるプロセスの障害が1秒以内に発見で きない場合には、いくつかのデータを張 失してしまう。したがって、リアルタイ ム性が必要となるシステムにおいては、 障害発見にかかる時間の上限値が規定さ れていなければならない。 A-障害が起きた場合には、障害の通 知のためにかかる時間はメッセージ転送 の遅延だけとなるので、制御システムに おいては非常に現実的な解決方法を提供 している。

4

.

2

.

プロセス状態の遷移

障害モデルの満たす性質として、 A-障害を起こしたプロセスは、ある一定時 間正常勤作可能であるとしている。 ここでは、多くのプロセスが実行す るであろう対処方法として、 A-障害が 起きた時に、自分を一貫した状態に遷移 させ、その後に停止するという対処を取 り上げる。 プロセスの状態が一貫した状態、であ るかどうかは、アプリケーションプログ ラムにより異なる。 例えば、トランザクションシステム は、 トランザクションに囲まれた途中状 態は一貫した状態でなく、その初期状 態、もしくは終了状態が一貫した状態で ある。したがって、以下のような処理が 考えられる。 二層で構成されるトランザクション の第一層でA-障害が起きた場合には、そ のトランザクションのアボート処理を行 ない、第二層で起きた場合には、継続す ることとする。これは、 トランザクショ ンの第二層は第一層に比較して、非常に 短い時間で処理されるという仮定にも とづいている [11]0 プロセスがトランザクションの列と して構成されていない場合には、より複 雑な処理が必要となる。例えば、図

3

.

の プログラムの Unixでの実行では、アプ リケーションプログラムそのものが自分 で一貫性のある状態を示す必要がある。 図

3

.

の例では、

u

p

d

a

t

e

_

d

a

t

a

手続きの 中の (3)の命令が終了した時点?をアプリ ケーションが意図したデータが一貫した 状態で 7ァイルとして書き込まれたζと になるo しかし、 (2)の時点では、アプ リケーションプログラムの意味づけから

は、一貫のある状態であるとはいえない のが普通であるo このような意味づけは アプリケーションの意図するデータ構造 とそれへの操作の組合せによりなされる ものであるo upda胞:_data(臼，index，COnlent) 泊tfd; 加1index; char申contenl; write(fd， &index， sizeof(int)); ー・(1) --(2) write(fd， con胞nt，strlen(content)); …(3) 図

3

.

アプリケーションプログラム例 さらに、この書き込みが Unixのディ スク上のファイルシステムに対するもの で あ る な ら ば 、 フ ァ イ ル シ ス テ ム の キャッシュの機構により、書き込まれた データは、同期的にディスク上に書き込 まれることを保証していない。つまり、 その状態がオペレーティングシステム内 部に蓄えられたことになる。 その意味で、図

3

.

のプログラムでは、 (3)が終了した時点で、且つ Unixがディ スクキャッシュを書き込んだ時点で一貫 した状態となる oUnix においては、

f

s

y

n

c

O

システムコールを発行すること でディスクキャッシュをクリアできる が、毎回行なうことは、性能的にも好ま しくない。 システムにおける障害として、 A-障 害モデルを仮定した場合には、プロセス が障害を検知した時に、図 3. の(1)や (2)の状態、もしくはそれ以前だった場 合には、一貫した状態まで選移した後 に、他のプロセスに自分の A・障害を通 知することができるo プロセスの移送が 不可能な場合でも、障害を起こしたプロ セスが処理の引き継ぎに必要な情報を、 障害を起こしたプロセス自身により保存 可能であるために、切れ目のない実行が 可能となるo プ ロ セ ス 制 御 の ア プ リ ケ ー シ ョ ン は、多くの場合、センサからのデータを 受けた時に、その処理を行なうプロセス が起動され、一連の処理を行なった後に そのプロセスは終了するo この処理は、 性能上の観点からプロセスをデータ入力 のたびに起動するのではなく、

d

a

e

m

o

n

プロセスのように、入力を待ちと処理の ループで実装される場合が多い。この場 合には、プロセスそのものは継続的に実 行され続けているが、処理の論理的な単 位としては別のものである。 A-陣害が起こった場合には、ループ の入力待ちの前に、障害の確認を行な い、 A- 障害が起こっていた場合には、 そこで他のプロセスに通知し、自分は実 行を停止すれば、一貫した状態を保証で きる o また、データ生成の間隔が短く、他 のプロセス(コンピュータ)が次のデー タ処理を行なうための準備ができない場 合にも、他のプロセスと同期をとること により、切れ目ない連続処理が可能とな る。 l.fsyncなどの動作が必要な場合には、こ の時にあわせて行なう。

5

おわりに

本稿では、障害モデルとして非常に 強い仮定を持つ A-障 害 モ デ ル を 提 案 し、 A-障害モデルが、いくつかの場面 で適用可能であることを示した。 A-障害モデルは、近い将来、ある確 率でプロセスが障害を起こすことを意味 し、かっ、障害を起こしたプロセスが、 一定時間正常動作することが可能な障害 を示しているo A-障害が起こった場合には、障害を 起こしたプロセスが自発的に障害処理を 行なうことが可能であるだけでなく、他 のプロセスにおける障害発見が高速に行 なえるo また、障害を起こしたプロセス が、一貫した状態で停止することが可能 である。 一 般 に 、 シ ス テ ム で 発 生 す る 障 害 は、 A-障害のように強い仮定にもとづ くものではなく、クラッシュ障害や、オ ミッション障害、ピザンチン障害などが 起こるo ところが九これらの障筈のうち のいくつかは、

UPS

の よ う な 特 別 な ハードウェアやプログラムの追加によ り、より強い仮定を持つ障害として扱う ことが可能となるo 今後は、種々の障害を A-障害として 扱うために必要となる装置やプロセスの 状態の検討を行なうだけでなく、継続処 理を可能とするために、 A-障害が起き た場合のプロセスの移送方式、そこでリ アルタイム性を保証するための移送先の 決定アルゴリズムとそこでのスケジュー ル方式について検討を進めていく予定で あるo [参考文献] [1] Hadzi1acos， V.組.dToueg， S.: Faulto・Tolerant BroadcasLS and Related Problems， DisLributed Systems， Mullender， S. (edふsecondedition， Addison-wesley (1993). [2] Budhiraja，N.， Marzullo， K.: Tradeoffs in imple -menting prim訂y-backupprotocols， Dep首 位nent of Computer Science， Comell University， Techni -cal Report TR 92・1307(1992). [3] Schlichting， R.D. and Schneider， F.B.: Fail-Sωp Processors: an Approach 10 Designing Faull-Tol -eranl Computing Systems， ACM Transactions on Computer Systems， 1(3)，222-238(1983). [4] Schneider， F.B.: Implementing fault-LOlerant ser -vices using lhe state machine approach: A tuLO・ rial， ACM Computing Serveys， 22 (1990). 同 Binnan，K.P.:The pr

∞

ess group approach to reli・ able distrlbuted computing， Department of Com-puter Science， Comell Universicy， TR93・1216 (1993).

[6] Pea民，M.，shostak，R. and Lamport，L.:Reaching Agreement in the Presence of Faults， Joumal of 由eACM， 27(2)， 228・234(1980).

ロ

]

Perry，K.J.and Toueg， S.: Distributed agreement in由epresence of processor and communication fauI岱，IEEE Transactions on Soflware Engineer -ing，SE・12(3)，477-482(1986). [8] Toueg， S.， Peπy， K.J.and Srikanth， T.K.: FaSl Distributed Agreement Siam Journal on Comput-ing， 16(3)，445-457 (1987). [9]瞬時電圧低下対策専門委員会:瞬時電圧低下 対策，電気共同研究，Vol.46， No.3 (1990). [10] Ricciardi， A.and Birman， K.: Using Process Groups 10 Implement Failure Detection in Asyn-chrounous Environments， Proceedings of山e Tenth ACM Annual Symposium on Principles of Distributed Computing. Ladner， R.， ed.， ACM Press.341・351(1991)~

[11] Coulouris， G.F. and D01limore J.: DisLributed Systems -Concepts and Design A，- ddison-wes -ley(1988).