アルゴリズム
Direct Edit
\(\def\vector#1{\boldsymbol{#1}}\)

分散システム

Takami Torao
  • このエントリーをはてなブックマークに追加

概要

分散システム (distributed system) は、クライアント (エンドユーザ) から単一のシステムとして見えるように動作する、協調して動作する複数のコンピュータで構成されるシステム。複数のコンポーネントが異なるノードに配置されており、個別のノードが故障してもシステム全体がそれを見せないように動作し続けることができる。またノード数を増やすことでスケールすることができる。ノード間は非同期メッセージパッシングで通信する。

Table of Contents

  1. 概要
  2. 分散合意
  3. Safety と Liveness
  4. 同期/非同期/部分同期モデル
  5. 障害耐性
    1. 障害モデル
  6. FTP 不可能性
  7. 参考文献

分散合意

システムに参加している非故障プロセスがどのように合意形成するかは分散システムにおける重要な課題の一つである。例えば分散データベースは各ノードがトランザクションをコミットするか中止するかについて合意する必要がある。障害耐性を持つ分散システム向けプロトコルが故障プロセスの存在を許容しながら分散合意 (distributed agreement) の機能や特性を維持するには以下の要件を満たす必要がある。

Agreement

すべての非故障プロセスは同一の値に合意する (ある同じ値 \(x\) を出力する、同じ状態になる等々、表現のバリエーションは多い)。

Integrity

すべての非故障プロセスは一度しか値を決定しない。これは一度決定した値を覆さないという意味であり、Agreement と同一視されることも多い。

Termination

すべての非故障プロセスは最終的に値を決定する。

Validity

全ての非故障プロセスが合意する値はソースプロセスの提案によってもたらされる。これは、例えば提案を無視して常に true で応答するようなプロセスの可能性を排除し、合意した値がソースの提案に基づいていることを保証している。

ソースプロセスが故障している場合、非故障プロセスはどのような値にも合意しても良い。また故障している合意プロセスが何の値を決定するかは考慮しない。

より形式的には、合意を形成しようとしている \(n\) 個のプロセスの集合 \(P=\{p_1,p_2,\ldots,p_n\}\) が存在する。そのうちの \(F \subset P\) は故障している。各プロセス \(p_i\) は値 (状態) \(v_i\) を保持している。

Safety と Liveness

古い論文では Liveness の意味で Termination と表現しているものもある。

同期/非同期/部分同期モデル

標準的な分散コンピューティング環境におけるすべてのプロセスは遅延を伴うメッセージングによって相互に通信することができる。また過負荷などによってあるプロセスの処理が遅れている可能性もある。プロトコルの特性を証明または説明するために、メッセージの遅延に関連する障害や攻撃を制限するための 3 つの通信モデルを定義する。

同期モデル

同期モデル (synchronous model) ではすべての参加者が知っている遅延上限 \(\delta\) (有限時間範囲) が定義されている。例えばプロセスが同期モデルの場合、あるプロセスの動作が停滞したとしてもその処理遅延は \(\delta\) を超えないと仮定とする。またネットワークが同期モデルの場合は、送信者が送信したメッセージは確実に \(\delta\) 時間以内に相手に受信されると仮定する。

言い換えると、同期モデルでは高負荷状況や危機の不調などによる一時的な大きな遅延を想定せず、またネットワークの一部または全体を制御できるような攻撃者も想定しないという理想系のモデルである。したがって同期モデルのプロトコルを実務向けシステムに適用することは困難である (せいぜい実時間処理が保証されている RTOS やハードウェア回路などの環境であろう)。

非同期モデル

非同期モデル (asynchronous model) では、送信されたメッセージは任意の有限時間後に相手に受信されることのみが保証されている。つまりネットワークの中継機器や攻撃者は最終的にメッセージが配信されるならいくらでも遅らせることができる。

非同期モデルは同期モデルより現実的なネットワーク (特に公衆回線経由のインターネット) の挙動に沿ったモデルである。しかし、完全な非同期モデルでは有限時間内に合意形成が終了することを保証するには 1 つのプロセス障害も許容できないことが知られている [FLP85]。このため非同期モデルを採用したプロトコルの正しさを保証するためには多くの制約を導入する必要があり証明が複雑になる傾向を持つ。

部分同期モデル [DLS88]

部分同期モデル (partial synchronous model) [DLS88] は時刻 \(t \le {\rm GST}\) に送信したメッセージが時刻 \(t'\) \(=\) \(\max(t,{\rm GST})\) \(+\) \(\delta\) までに相手に受信されることを保証する (同期モデルに GST と呼ばれるイベント時刻を追加したものである)。これにより、部分同期モデルのシステムは GST までは非同期モデルで動作し、GST 以降は同期モデルで動作することができる。

GST (global stabilization time) の直感的な例は、能動的には各プロセスが持つ処理タイムアウトであったり、受動的には高負荷状態が緩和して通常通り進行できるようになる時刻や、手作業による機器の復旧時刻といったようなイベントである。つまり一時的な問題が解消して機能や進行が回復する時刻を意味している。これは、現実的なシステムの挙動でありながら非同期モデルほど証明や説明が困難ではないという利点があり、多くの現実的なプロトコルが部分同期モデルを採用している (翻って言えば非同期モデルによく導入される制約を定式化したものが部分同期モデルである)。

現状、同期モデルは実用性よりも新しい提案や論議のためのモデルとして提示されるものと考えて良い。典型的には、まず同期モデルでそのプロトコルの全体像や直感的な利点を説明し、その後に (しばしば若干の修正を追加して) 非同期モデルや部分同期モデルを適用して実用面での正しさを証明するといった段階的な論議で進行するのが定石である。

障害耐性

障害耐性 (fault-tolerance) は、プロセスや通信の故障を検出して (設計上想定されている) エラーを生成するか、またはユーザから故障を隠ぺいして動作し続けることのできるシステムの性質。一般に障害耐性を達成するためにはシステムの構成要素を冗長化し、一部のコンポーネントが故障しても残ったコンポーネントで全体が機能するように設計する。

障害モデル

障害耐性を論議するときは、どの障害モデルを対象にしているかを考慮する。

欠落障害

欠落障害 (omission failure) は送信完了したメッセージが相手に届かないまま喪失する障害である。無限大時間の遅延で配信されるという見方をすると、非同期モデルにおけるネットワーク遅延と同じと考えることもできる。

Crash 障害

プロセスは任意のタイミングでクラッシュすることができる。クラッシュしているプロセスはそれ以上プログラムを進行せず、他のプロセスからのメッセージに応答しない (あるいは故障中という応答をする)。他のプロセスがクラッシュを検出できる場合、クラッシュはフェイルとも呼ばれる。

Crash Stop 障害

クラッシュしたプロセスはそのままシステムから喪失し復帰しない (process omission 障害とも呼ばれる)。

Crash Recovery 障害

クラッシュしたプロセスは任意の時間 (一瞬～かなり長期間) の後にシステムに復帰できる。言い換えると、すべてのプロセスは設計上あり得る状態遷移の範囲で過去の任意の時点の状態から処理を再開することができる。これはプロセスの単純な停止/再開だけではなく、初期状態のプロセスがシステムに途中参加したり、クラッシュ後にバックアップから復元したプロセスが復帰するケースも含んでいる。

Crash Recovery 障害は任意のメッセージをロストする喪失障害 (omission failure)、性能低下で応答が著しく遅れる性能障害 (performance)、許容時間内に応答できないタイミング障害 (timing) 障害なども包括する。

Arbitrary 障害

プロセスは任意のタイミングで設計や状態遷移を逸脱した行動をする。

Byzantine 障害

プロセスは (悪意をもって) システムの safety および liveness を破壊しようと積極的に行動する。

Authenticated Byzantine 障害

各プロセスがすべてのプロセスと公開鍵を共有している環境での Byzantine 障害 [DLS88]。メッセージに送信者の署名を付けることができるためメッセージの偽造ができないという仮定を置くことができる。

FTP 不可能性

一つでもプロセス故障が発生しうる (許容する) 非同期 (メッセージパッシング) システムは、有限時間内に合意に達する保証ができない。

FLP 不可能性 (FLP impossibility) は障害耐性と安全性を持つ分散システムは合意が不可能であることを示す基本的な定理。この結果の正当性の証明は大域的状態の価数の重要な概念に導かれている。

\(v(S_g)\) を任意の大域的状態 \(S_g\) から到達可能なある大域的状態で合意可能な値の集合を表すとする。\(|v(S_g)|\) を大域的状態 \(S_g\) の valency (価数; 取り得る値の個数) と定義する。大域的状態は 0 または 1 のブール代数の決定値に対して 2 の価数を持てば bivalent (二価) であるし、また 1 の価数を持てば monovalent (一価) である。言い換えれば bivalent なら合意に達することができず monovalent であれば合意に達することができる。

monovalent 状態の \(S_g\) は \(v(S_g) = \{1\}\) であれば 1-valent、\(v(S_g) = \{0\}\) なら 0-valent である。二価性をとる大域的状態からは 0-valent または 1-valent の状態のどちらにも到達可能であるため、決定における不確実性を導く。

コンセンサス値は入力のよって決定することから初期状態では一価である。しかし、故障が発生したケースではコンセンサスプロトコルは必然的に二価の初期状態を持つことを示すことができる (各プロセスが \(\{0,1\}\) から任意の初期値を持つことができると仮定し trivial な解を除外する)。これは背理法から導くことができる。

入力が全て 0 である初期状態は 0-valent であり、入力が全て 1 である初期状態は 1-valent であることは明かである。入力割り当てを all-0 から all-1 に移行すると、それぞれ 0-valent と 1-valent の入力割り当て \(\vector{I}_0\) と \(\vector{I}_1\) が存在し、一つのプロセス \(p_f\) の入力のみが異なる入力値をとるとする。もし 1 つのプロセスの故障に耐えられるコンセンサスプロトコルが存在する場合、以下のようになる。

  1. \(\vector{I}_0\) から始まりすぐに \(p_f\) が発生した場合、他のプロセスは termination 条件のために 0 に合意しなければならない。
  2. \(\vector{I}_1\) から始まりすぐに \(p_f\) が発生した場合、他のプロセスは termination 条件のために 1 に合意しなければならない。

実行 2. は実行 1. と同じに見えるが、しかし実行 2. はコンセンサス値 0 (矛盾) で終了する必要がある。従って、少なくとも 1 つの二価の初期状態が存在しなければならない。

コンセンサスに達するためには初期値を交換する必要があることに注意。(モデルによるがメッセージパッシングか共有メモリによって)。従って、実行中のプロセスでコンセンサスを一方的に決定することはできない。不可能性結果の鍵となる考えは、潜在的なプロセス故障に遭遇した場合、プロセスが故障したこととプロセスまたは通信経路が非常に遅いことを区別できないことである。従って 2 価状態から 1 価状態に遷移することはできない。具体的には次のようになる。プロトコルが 2 価の大域的状態から 1 価の大域的状態に遷移し、証明における推論のために大域的時間インターリーブモデルを使用するためには、コンセンサス値を決定することで価数を変更する重要なステップ実行が存在しなければならない。これは 2 つの可能性がある:

  • 重要なステップは単一のプロセスで発生するイベントである。しかし、他のプロセスは、このプロセスがクラッシュした 2 つのシナリオと、このプロセスが非常に遅いシナリオを区別できない。どちらのシナリオでも、他のプロセスは永遠に待機し続けることができるため、プロセスはコンセンサス値に到達することができず、2価状態のままになる可能性がある。
  • 重要なステップは、異なるプロセスにおける服す野独立した (すなはち送受信関連ではない) イベントで発生する。しかし、様々なプロセスでの独立したイベントはどのような順序でも起こりうるため、重要なステップは明確に定義されておらず、この可能性は受け入れられない。

故障が発生する可能性のあるいかなる非同期システムにおいても合意の問題が全ては解決できないことを意味するため、この不可能性の問題は重要である。次のような合意を必要とする全ての問題は1つの故障であっても解決できない可能性があることを示すことができる。

  • リーダー選挙
  • broadcast-convergecast フローを用いたネットワーク側のグローバル機能問題
  • 信頼できるブロードキャストの終了
  • アトミックブロードキャスト

FLP 不可能性に対する一般的な分散システムの戦略は (1) ランダム性と (2) クロックやタイムアウトの 2 つを導入することである。例えば Raft では乱数調整された選挙タイムアウトを用いることでリーダー選出時の Split Vote 問題を回避しているし、もし起きてもタイムアウトによって選挙が再開される。

参考文献

  1. Dwork, Cynthia, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM) 35.2 (1988): 288-323.
  2. Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM) 32.2 (1985): 374-382.
↑ページの先頭