3年ほど前に(後述するライブラリを目的に)読んだ"Introduction Of Reliable Distributed Programming"を、復習も兼ねてレビュー。
注意：すでに2nd Edition "Introduction to Reliable and Secure Distributed Programming" が出ているが、このレビューは1st Editionを対象とする。
癖のある本なので、これから1stか2nd Editionを読む人の参考になれば。
イントロ
本書は分散プログラミングのための基礎知識を解説した書籍である。
解説している内容は次のとおり:
＊分散プログラミングの基礎。障害の概念など含む
＊Reliable Broadcast(高信頼ブロードキャスト)
＊Shared Memory
＊Consensusアルゴリズム (Paxosには触れず)
ごくありきたりの項目であるが、本書の最も大きな特徴は「実際のJavaプログラムをベースに解説」「ライブラリ＋サンプルコードをダウンロードして自分で動かすことができる」ことに尽きる。
このライブラリについては後述する。
ただし、2nd Editionの目次をみると、「自分で動かす(Hands-On)」のセクションが消えている。Exercisesに吸収されたのか、排除されたのか、筆者は2nd Editionを持っていないので分らない。
筆者がこのライブラリを利用して作ったシステムは「Postgres-XC gtmの多重化」を参照。先に結論を述べると、これは教育用であって実用には耐えないのでJGroupに乗り換えた。
章立てと概要
詳しい目次はこちらを参照して頂くとして、章立てと概要を簡単に示す。
1章 Introduction
この章は、プログラミングライブラリの概説であって、分散プログラミングの概要ではない。本書独特の記法と記述形式の解説。
階層的なモジュールで構成され、各モジュールの定義と実装(アルゴリズム)が以下の形式で示される。
レイヤ毎に機能の異なるモジュールがあり、それらを組み合わせてReliable BroadcastやConsensusアルゴリズムを構築して解説するのが、本書の基本的なスタイル。
2章 Basic Abstractions
分散プログラミングの基本要素の解説とライブラリの説明を同時に行っている。
どちらかといえば後者に注力しており、基本要素の解説は網羅的でない。基本要素(用語)の把握には別の参考書が必要と思う。
例えば、故障の分類はCrash fault、 Omission fault、Crash and Recovery fault。Byzantine faultは触れていない。
障害検出の概念の説明は通常と異なり、P(Perfect)と<>P(EventuallyPerfect)が天下りで定義され、その定義内で完全性(Completeness)と正確性(accuracy)が解説されている。
以下に、本書でのPと<>Pの解説図を示す。これに文章による簡単な解説がつく。
まず、Pのモジュール定義とアルゴリズム。
念のため書くと、これはP障害検出器の作り方ではなく、このライブラリにおいて「このロジックでP障害検出器をエミュレートしている」という解説。
具体的には「P２P通信は同期で、障害検出しない限り完全と仮定。タイムアウトで障害検出するよ、これが障害と判断したらそれはStrong completeness, Strong accurancyを満たしてると思って、上位レイヤやアプリケーションを作ってね」という話。
次は、<>Pのモジュール定義と、アルゴリズム。
本書で使う障害検出クラスはこの２つ(Pと<>P) + (EventualLeaderDetector:Ω *1 )だから、以降の解説の理解には十分だが、他のクラス(S,<>S,Q,W,<>Q,<>W)には触れていない。
このような調子で、他にも同期非同期、リンクのモデリングなどが解説されている。
3章 Reliable Broadcast
ここからが本題。以下に列挙する高信頼ブロードキャストの解説。
1. Best-Effort Broadcast
2. Regular Reliable Broadcast
3. Uniform Reliable Broadcast
4. Stubborn Broadcast
5. Logged Best-Effort Broadcast
6. Logged Basic Broadcast
7. Randomized Broadcast
8. Causal Broadcast
それぞれについて、いくつかのパターンの実装と解説がなされている。
例えばBest-Effort Broadcastのモジュール定義とアルゴリズムは次の通りである。
下位レイヤのPerfectP2Pリンクを使って実装する。
次、Regular Reliable BroadcastはLazyとEagerの2種類の実装が示される。
はじめにLazy。下位レイヤとして先のBest-Effort BroadcastとPerfectFailureDetectorを使う。
次にEager。下位レイヤはBest-Effort Broadcastのみ。障害検出器を使わない。
などなど、各Broadcastについて、障害検出器の有無や実装上の違い(例えばメッセージを確保し続けるか、適度にガベージコレクションするのか)で、複数のアルゴリズムが解説されている。
ただし、紙面の都合か、全パターンを網羅しているわけではないので、期待し過ぎないほうがよい。
なお、本書では実装の分類にFail-stop、Fail-noisy、Fail-silentなど独特の用語を使っている。
* Fail-stop：P障害検出を使う (各プロセスは他プロセスの障害を正しく認識できる)
* Fail-noisy: <>P障害検出を使う
* Fail-silent: 障害検出を使わない (各プロセスは他プロセスの障害を検出できない)
他にもFail-recovery、Randomizedなどあるが、ここでは省略。
目次で内容を確認する際は注意。
4章 Shared Memory
未読。
5章 Consensus
解説するConsensusアルゴリズムは以下のとおり。Paxosはありません。
1. Regular Consensus
2. Uniform Consensus
3. Abortable Consensus
4. Logged Abortable Consensus
5. Randomized Consensus
ここでも、各Consensus方式について、実装の違いや故障検出器の有無などで、２〜３のアルゴリズムが解説されている。
例として、Regular Flooding Consensusアルゴリズム(Best-Effort通信路＋PerfectFailureDetectorを使う)のモジュール仕様、アルゴリズム、ダイアグラムを示す。
6章 Consensus Variants
疲れたので、後ほど。
7章 Concluding Remarks
未読。
ライブラリ
現在はバージョンが多少上がり、担当者も変わったようなので、以降の文章は３年前のバージョンの評価としてご理解頂きたい。
本書の主役であるライブラリはAPPIA Communication Frameworkと名付けられている。
ライブラリ＝フレームワークはソースコードでもjarファイルでも入手可能。
本書の例題はHandsOnを参照。
で、
筆者はPostgres-XC gtmの多重化(改訂2版:2011.01.01)のために本書を購入し、期待してappiaフレームワークを使ってみたが、とても実用に耐えず、JGroupに乗り換えた。
このライブラリ＝フレームワークは教育用であって、実用的ではない。
実用上、まずい点を2つだけ書く。
- 遅い。とにかく遅い。
- レイヤ間のデータ渡しで、一々コピー
- ただのP2Pすらモジュールを使うわけで、やたら無駄な処理が多い。
- メッセージを保管し続けるので、長時間稼働するとメモリを喰い尽くす。
- 過去メッセージを保存するのはよいが、ガベージコレクション機構がないので、しばらく稼働するとメモリが尽きる。
- アルゴリズム名にガベージコレクションを謳ったものもあるが、それは上位レイヤの話で、下位レイヤではメッセージを全保存してたりする。
本書を購入する前は「まともなフレームワーク」と聞いていたが、あくまで教育用としてまともという感じ。
「解説されたアルゴリズムを手元で動かすことができる。ソースレベルで動作を確認できる」という点のみ、このライブラリ＝フレームワークの価値があると思う。
*1:一般的なのかどうか分からない
