分散システムとは — 歴史・時間・障害・複製

分散システムは、離れた場所にある複数のプロセスがメッセージを交換しながら、利用者には一つのサービスや計算として見える仕組みです。Leslie Lamportは1978年の論文で、空間的に離れたプロセスと、無視できない通信の遅延を定義の中心に置きました。肝心なのは台数ではありません。プロセスがお互いの状態を瞬時には知りようがない、という点です。

一台の高性能なコンピューターで多数の処理を同時に走らせる「並列計算」と、ネットワーク越しに複数の機械が協調する「分散計算」は重なりますが、同じものではありません。分散システムでは、通信が遅れる、片側だけが止まる、同じ出来事を別々の順番で受け取るといったネットワーク固有の問題が、設計の中心に来ます。

「分散」「非中央集権」「P2P」「グリッド」「クラウド」「ブロックチェーン」は互いに関連しますが、言い換えのきく言葉ではありません。分散とは、計算や状態が複数の場所にあるという技術的な性質です。非中央集権は、制御する権限がどこに集まっているかという統治の話です。地理的に分散していても、一社が全ノードを管理するシステムは珍しくありません。

P2Pは、参加者がクライアントとサーバーに固定的に分かれず、対等な役割も担えるネットワークの構成を指します。グリッド計算は組織や場所をまたいで計算資源を束ね、クラウドはその資源を必要なときに必要なだけ提供します。ブロックチェーンは、共有台帳を改ざんの検知できる形に複製する設計の一群であり、分散システムという広い集合の一部にあたります。

1969年のARPANETは、地理的に離れた計算機をパケット通信で結んだ歴史的な基盤です。ただし、これを単純に「最初の分散システム」と呼ぶのは正確ではありません。ネットワークが担ったのは通信路の提供までで、その上で状態・複製・障害・計算の協調を扱う研究は、ここから発展していきました。

1970年代後半から1990年代にかけて、論理時計、Byzantine障害、合意不能の条件、Paxos、複製状態機械が理論の骨格を作りました。2000年代にはMapReduceが大量データの処理を多数の汎用サーバーへ配り、Dynamoが常時稼働を優先する分散データストアの設計を公開しました。いずれもビットコインより前に、別の目的と信頼モデルのもとで分散性を実用化した系譜です。

2008年のビットコイン白書は、電子現金の二重使用問題に対して、P2Pネットワーク、ハッシュ連鎖、Proof of Work、経済的な報酬を組み合わせました。新しかったのは分散計算そのものの発明ではなく、公開の参加者どうしで取引履歴を維持するために、既存の要素を一つにまとめた点です。

分散システムでは、二つの出来事のどちらが先かを常に決められるわけではありません。プロセスAの出来事をきっかけにメッセージが送られ、それが届いた後にプロセスBで出来事が起きたのなら、そこには因果の順序があります。一方、互いに通信していない二つの出来事は並行しており、壁時計のわずかな差だけで意味のある順序を決めることはできません。

Lamportの「happened-before」関係と論理時計は、因果の順序と矛盾しない番号をイベントに与えます。とはいえ、時計の値が小さいからといって、そこに因果関係があるとは限りません。`a → b` なら論理時計は `C(a) < C(b)` になりますが、その逆は一般に成り立ちません。ベクタークロックは、持ち運ぶメタデータが増える代わりに、並行性についてより多くの情報を残せます。

この区別は、二重予約、口座残高、ファイルの更新、ブロックの到着順といった場面で効いてきます。ビットコインでも、別々のマイナーがほぼ同時に有効なブロックを見つければ、ノードごとに最初に見た先端が一時的に食い違います。最終的な順序をそろえるのは物理的な時計ではなく、プロトコルの規則です。

分散システムの難しさは「すべて停止」ではなく「一部だけ停止」にあります。応答のないノードについて、クラッシュしたのか、回線が分断されたのか、処理が遅いだけなのか、返答が途中で失われたのかを、外側から完全に見分けることはできません。タイムアウトは有用な推測の手段ですが、故障の証明にはなりません。

Byzantine障害は「悪意ある人」だけを指す言葉ではありません。ソフトウェアの不具合、壊れたメモリ、破損した通信、乗っ取られたノードのように、仕様から外れた任意の振る舞いをまとめて扱う、強い故障モデルです。どこまでの障害を想定するかによって、必要な複製の数も通信量も大きく変わります。

分散プロトコルの保証は、しばしば安全性と生存性に分けて考えます。安全性は「決して悪いことが起きない」という性質で、二つのレプリカが同じ位置に異なる値を確定しない、無効な取引を受理しない、といった保証です。生存性は「いつか良いことが起きる」という性質で、要求がいずれ処理される、合意がいつかは決まる、といった進行の保証です。

ネットワークが不安定なとき、安全性を守るために処理を止める設計はあり得ます。逆に、常に応答を返すために一時的な不整合を許す設計もあります。「止まらない」ことと「正しい」ことは同じ物差しではありません。その設計が何を優先したのかを、分けて読む必要があります。

ビットコインも同じです。ノードが無効なブロックを拒否するのは安全性の側の規則です。一方、新しい有効なブロックが途切れずに生成されることは、ネットワークでの伝播とハッシュパワーについての仮定に依存する、生存性の側の性質です。

信頼性を上げる基本の手段は複製です。ただし、データを複数台へコピーするだけでは足りません。同時に届いた更新を別々の順序で適用すれば、そこで状態が分岐します。複製状態機械は、同じ初期状態から始まる決定的な処理系に、すべての命令を同じ順序で適用することで、複数のレプリカを一つのサービスとして動かします。

合意アルゴリズムが決める中心の課題は「どの命令を、ログのどの位置へ置くか」です。PaxosやRaftは、既知のサーバー集合を前提に、クラッシュ障害に耐える複製ログを組み立てます。PBFTは、任意の振る舞いをするレプリカを含むモデルへこれを広げます。アルゴリズムの細部より先に、参加者が既知かどうか、何台まで壊れてよいのか、ネットワークにどんな仮定を置くのかを確かめる必要があります。

ビットコインの全ノードも、同じ検証規則からUTXOの状態を計算し直します。ただし、命令を提案するのは公開で参加するマイナーであり、履歴の選択には累積のProof of Workを使います。企業内に登録されたレプリカ群とは、参加のモデルが異なります。

Fischer、Lynch、Patersonが1985年に発表した論文、通称FLPは、合意の限界を形式的に示しました。完全に非同期なメッセージシステムで、たった一つのクラッシュ障害を許したとき、決定的な合意プロトコルはすべての許容実行で終了を保証できない、という内容です。これは「分散合意は現実に不可能」という意味ではありません。

定理が前提に置くのは、強い条件の組み合わせです。メッセージの遅延にも処理速度にも上限がなく、故障と遅延を区別できず、動作は決定的で、しかもどんな実行でも終了することを求めます。現実のシステムは、いずれ通信が安定するという部分同期の仮定、乱数、障害検出器、運用上のタイムアウトなどを足すことで前に進みます。

Dwork、Lynch、Stockmeyerは、この部分同期のモデルを定式化しました。ここから受け取るべき教訓は、アルゴリズムの名前だけでなく「時間について何を仮定したか」を仕様として読む姿勢です。

CAP定理が述べているのは、ネットワーク分断が起きている最中の制約です。原子的整合性（単一のコピーのように見える強い整合性）と可用性（すべての非故障ノードへの要求が応答を得ること）を、同時には保証できません。Pは自由に捨てられる機能ではなく、分断が起こり得るという環境の条件です。

よくある「Consistency、Availability、Partition toleranceから好きな二つを選ぶ」という三角形は、入口としては覚えやすい説明ですが、正常に動いているときまで永久に二択を迫られるかのような誤解も生みます。実際の設計では、分断が及んだ範囲、操作の種類、許容できる遅延、整合性のモデルごとに、判断はもっと細かく分かれます。

また、CAPのCを「データがだいたい一致すること」、Aを単なる稼働率と読み替えてしまうと、定理の射程は崩れます。原論文の定義と、自分が設計するサービスレベル目標は、分けて扱う必要があります。

2004年のMapReduce論文は、入力の分割、タスクの配置、失敗した処理の再実行、機械どうしの通信を実行基盤の側へ隠し、大量データの処理を汎用サーバーのクラスタへ広げました。重要なのは、障害を例外ではなく日常的に起きるものとして扱い、再実行で吸収した点です。

2007年のDynamoは、ショッピングカートのように常に応答することが重要な用途で、可用性の高いキーバリューストアを構成する方法を公開しました。コンシステントハッシュ、ベクタークロック、スロッピークォーラム、リードリペアなどを組み合わせ、唯一の「正しい分散設計」があるのではなく、用途に応じて整合性と可用性を取引するのだと示しました。

一方、グリッド計算とボランティアコンピューティングは、組織や家庭に眠る未使用の資源を科学計算へ束ねました。作るのは共有台帳ではありません。分割できる仕事を配り、返ってきた結果を検証してから集約します。詳しくは「ボランティアコンピューティング」の記事でたどります。

ビットコインが継承したのは、P2P通信、複製された状態、暗号学的ハッシュ、デジタル署名、そして障害のもとでの順序付けという、分散システムの問題群です。一方で、既知のサーバーを事前に登録する方式を採らず、誰でも参加でき、同一人物がいくつもの仮想的な識別情報を作れる環境を扱う必要がありました。

Proof of Workは「ノード一台につき一票」の仕組みではなく、検証できる計算資源を、履歴を提案する重みに変えます。各ノードは、累積の作業量が最も大きい有効なチェーンを選びます。攻撃者のハッシュパワーが正直な参加者の側を下回るなど、モデルの仮定が成り立つ範囲では、承認が深くなるほど履歴が覆る確率は下がります。ただし、数学的に即時不可逆な確定ではありません。

マイナーが順序の候補を作っても、無効なブロックを計算量だけで正当化することはできません。署名、二重使用、発行量、スクリプトなどの規則は、各フルノードが独立に検証します。計算資源によるSybil耐性と、規則にもとづく妥当性の検証は、別々の役割です。

分散システムを比べるときは、製品名や「分散型」という宣伝文句より先に、次の六つを確認すると構造が見えてきます。

この枠組みで見ると、BOINC、Raft、ビットコインはどれも分散していますが、解いている問題は違います。BOINCは、信頼できない家庭用PCへ独立した仕事を配り、プロジェクト固有の検証プログラムで判定し、必要なら複製した結果を照合します。Raftは既知のサーバー群でログの順序をそろえ、ビットコインは公開の参加者の間で価値の移転履歴を維持します。違いを消さずにつなぐことが、分散コンピューティングを理解する近道です。