現役エンジニアが解説する分散システム理論

分散システムのエンジニアで、“RabbitMQ in Action”の共著者でもあるAlvaro Videla氏が、QCon London 2017で、分散システム理論についての講演を行なった。タイミングモデルや障害モードなど、分散システムをさまざまなクラスに分類した上で、それぞれのトレードオフを議論する、という内容だ。

最初に取り上げたのはタイミングモデル(timing model)だ。氏はさまざまなタイミングモデルを紹介し、分散システムがステップに要する時間を認識しているかどうかを論じた。氏は３つのカテゴリを列挙した上で、並行プログラミングにおけるそれぞれの別の意味と混同しないように注意を促した。

• 同期(Synchronous): 各ステップのタイミングが既知である分散システム。障害検出などの課題には役立つが、現実のシステムを反映してはいない。
• 非同期(Asynchronous): 各ステップのタイミングに保証はなく、任意の順序でステップを実行する分散システム。実際のシステムに近いが、現実にはタイムアウトが設定される場合がある点などが異なる。
• 準同期(Semi-synchronous): 何らかのタイミング情報を持ち、各ステップの見積が可能な分散システム。

さらにVidela氏は、プロセス間通信のタイプについても詳しく説明した。これは単純で、メッセージパッシングを通じた通信か、共有メモリ経由の二者択一となる。

Videla氏が挙げた最後の分類は障害モード(failure mode)で、想定されるプロセス障害を決定するものだ。これには次のようなものがある。

• クラッシュ停止(Crash-stop): プロセスのクラッシュ時にリカバリを行なわない。これは現実を反映したものではない - マシンに障害が発生した場合、廃棄されるのではなく、再利用されるのが普通だからだ。
• クラッシュリカバリ(Crash-recovery): プロセス障害時、一般的にはリカバリアルゴリズムの類を用いて回復する。データベースからの読み込みや、他プロセスとの通信などがこれに含まれる。
• オミッション故障(Omission Faults): プロセスがメッセージの送受信に失敗する場合。例としてVidela氏が挙げたのは、グループからのメッセージを受信できるが、返信することのできないキャッシュだ。最新データの獲得は可能であるため、クライアントからは依然として利用することができる。
• 任意障害モード(Arbitrary Failure Modes): プロセスが誤った情報の送信あるいは受信を始めると、その結果として、システムの状態が無効になる可能性がある。

このようにさまざまなモデルとカテゴリを決定する上で銀色の弾丸は存在しない、とVidela氏は強調する。開発中のシステム要件に基づいて行なう必要のあるトレードオフなのだ。

これらオプションのいくつかは現実のシステムを反映していないが、分散システム理論においては有効である点にも注目すべきだ。これは、新たなアルゴリズムを証明する場合において、これらと組み合わせることによって作業が簡単になるためである。また、シンプルなモデルで機能しないものは複雑なモデルでも機能しない、という暗黙の了解もある。

Videla氏は障害検出器(failure detector)についても言及した。これは、他プロセスの停止の検出に利用されるアルゴリズムである。この場合のおもな問題は、障害の発生したプロセスと、処理に時間を要しているプロセスを識別することだ。ここでは“最終的に完璧な障害検出器(Eventually Perfect Failure Detector)”として、一定時間の経過後にのみプロセス障害を推測する回避策が提示された。この方法であれば、後にそのプロセスが生きていると判明した時、それを障害の推測対象リストから外すとともに、タイムアウトを延長することが可能になる。

講演全体のビデオがオンラインで公開されている。またVidela氏が、講演の内容を記事としても書いている。どちらもクォーラムやコンセンサスといたコンセプトについても触れると共に、さらに詳細を学ぶ上でのアドバイスも与えている。