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

01分散システムの本質

• 分散システムは、離れた複数のプロセスがメッセージを交換しながら、利用者には一つのサービスや計算として見える仕組みです。Leslie Lamportは1978年の論文で、空間的に離れたプロセスと無視できない通信遅延を定義の中心に置きました。重要なのは台数ではなく、プロセス同士が相手の状態を瞬時には知れないことです。
• 一台の高性能コンピューターで多数の処理を同時に走らせる「並列計算」と、ネットワーク越しの複数機が協調する「分散計算」は重なりますが同じではありません。分散システムでは、通信が遅れる、片側だけが停止する、同じ出来事を異なる順番で受け取る、というネットワーク固有の問題が設計の中心になります。

02似ている言葉を分ける

• 「分散」「非中央集権」「P2P」「グリッド」「クラウド」「ブロックチェーン」は互いに関連しますが、交換可能な言葉ではありません。分散は計算や状態が複数の場所にあるという技術的性質、非中央集権は制御権がどこに集中するかという統治上の性質です。分散配置されていても一社が全ノードを管理するシステムは普通に存在します。
• P2Pは参加者が固定されたクライアントとサーバーに完全分離されず、対等な役割を担い得るネットワーク構成です。グリッド計算は組織や場所をまたぐ計算資源を束ね、クラウドは資源をオンデマンドで提供します。ブロックチェーンは共有台帳を改ざん検知可能な形で複製する設計の一群で、分散システムという広い集合の一部です。

03ARPANETから公開参加型台帳まで

• 1969年のARPANETは、地理的に離れた計算機をパケット通信で結ぶ歴史的な基盤でした。ただし、これを単純に「最初の分散システム」と呼ぶのは正確ではありません。ネットワークが通信路を提供し、その上で状態、複製、障害、計算の協調を扱う研究が発展していきます。
• 1970年代後半から1990年代にかけて、論理時計、Byzantine障害、合意不能条件、Paxos、複製状態機械が理論を形作りました。2000年代にはMapReduceが大量データ処理を多数の汎用機へ分配し、Dynamoが常時稼働を優先する分散データストアの設計を公開しました。これらはBitcoinより前から、別の目的と信頼モデルで分散性を実用化した系譜です。
• 2008年のBitcoin白書は、電子現金の二重使用問題に対し、P2Pネットワーク、ハッシュ連鎖、Proof of Work、経済的報酬を組み合わせました。新しさは分散計算そのものの発明ではなく、公開参加者の間で取引履歴を維持するために既存要素を統合した点にあります。

04世界共通の「いま」はない

• 分散システムでは、二つの出来事のどちらが先かを常に決められるわけではありません。プロセスAの出来事からメッセージが送られ、その受信後にプロセスBで出来事が起きたなら因果的な順序があります。一方、互いに通信していない二つの出来事は並行であり、壁時計のわずかな差だけで意味のある順序を断定できません。
• Lamportの「happened-before」関係と論理時計は、因果順序と矛盾しない番号をイベントへ与えます。ただし、時計値が小さいからといって必ず因果関係があるわけではありません。`a → b` なら論理時計は `C(a) < C(b)` になりますが、その逆は一般に成立しません。vector clockはmetadataを増やす代わりに、並行性についてより多くの情報を保持できます。
• この区別は、二重予約、口座残高、ファイル更新、ブロック到着順などで重要です。Bitcoinでも、異なるマイナーがほぼ同時に有効ブロックを見つければ、ノードごとに最初に見た先端が一時的に異なります。物理時計ではなく、プロトコルの規則で最終的な順序を収束させます。

05部分障害 — 壊れたか、遅いだけか

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

• Byzantine障害は「悪意ある人」だけを意味しません。バグ、故障したメモリ、破損した通信、侵害されたノードのように、仕様から外れた任意の振る舞いをまとめた強い故障モデルです。どの障害まで扱うかによって、必要な複製数と通信量は大きく変わります。

06SafetyとLivenessを分ける

• 分散プロトコルの保証は、しばしばSafetyとLivenessに分けて考えます。Safetyは「決して悪いことが起きない」性質で、二つのレプリカが同じ位置に異なる値を確定しない、無効な取引を受理しない、といった保証です。Livenessは「いつか良いことが起きる」性質で、要求が最終的に処理される、合意がいつか決まる、といった進行の保証です。
• ネットワークが不安定なとき、安全性を守るために処理を止める設計はあり得ます。逆に、常に返答するために一時的な不整合を許す設計もあります。「止まらない」と「正しい」は同じ指標ではなく、何を優先したのかを分けて読む必要があります。
• Bitcoinも同様です。ノードが無効なブロックを拒否することはSafety側の規則であり、新しい有効ブロックが継続的に生成されることはネットワーク伝播とハッシュパワーの仮定に依存するLiveness側の性質です。

07複製状態機械 — 同じ順序から同じ状態へ

• 信頼性を上げる基本手段は複製です。ただしデータを複数台へコピーするだけでは、同時更新の順序が異なれば状態も分岐します。複製状態機械は、同じ初期状態を持つ決定的な処理系へ、すべての命令を同じ順序で適用することで、複数レプリカを一つのサービスとして動かします。
• 合意アルゴリズムが決める中心課題は「どの命令を、ログのどの位置へ置くか」です。PaxosやRaftは既知のサーバー集合でクラッシュ障害に耐える複製ログを構成します。PBFTは任意動作するレプリカを含むモデルへ拡張します。アルゴリズムの詳細より前に、参加者が既知か、何台壊れ得るか、どのネットワーク仮定を置くかを確認する必要があります。
• Bitcoinの全ノードも同じ検証規則からUTXO状態を再計算しますが、命令の提案者は公開参加のマイナーであり、履歴選択には累積Proof of Workを使います。古典的な企業内レプリカ群とは参加モデルが異なります。

08FLPが示した「不可能」の範囲

• Fischer、Lynch、Patersonの1985年論文、通称FLPは、完全に非同期なメッセージシステムで、決定的な合意プロトコルが、たった一つのクラッシュ障害を許したとき、すべての許容実行で終了を保証することはできないと示しました。これは「分散合意は現実に不可能」という意味ではありません。
• 定理が対象にするのは、メッセージ遅延と処理速度に上限がなく、故障と遅延を区別できず、決定的で、どんな実行でも終了するという強い条件の組み合わせです。実システムは、最終的には通信が安定するという部分同期、乱数、failure detector、運用上のタイムアウトなどを追加して進行します。
• Dwork、Lynch、Stockmeyerは部分同期モデルを定式化しました。ここから得るべき教訓は、アルゴリズム名だけでなく「時間について何を仮定したか」を仕様として読むことです。

09CAP定理を「三つから二つ」で終わらせない

• CAP定理は、ネットワーク分断が起きている最中に、atomic consistency（単一コピーのように見える強い整合性）とavailability（すべての非故障ノードへの要求が応答を得ること）を同時には保証できない、という結果です。Pは自由に捨てられる機能ではなく、分断が起き得る環境条件です。
• よくある「Consistency、Availability、Partition toleranceから好きな二つを選ぶ」という三角形は、入口としては覚えやすい一方、通常運転時まで永久に二択するような誤解を生みます。実際の設計では、分断を検知した範囲、操作の種類、遅延許容、整合性モデルごとに判断が細かく分かれます。
• また、CAPのCを「データがだいたい一致すること」、Aを単なる稼働率と読み替えると定理の範囲が崩れます。原論文の定義と、自分が設計するサービスレベル目標を分けて扱う必要があります。

10クラスタ、グリッド、クラウドが変えた規模

• 2004年のMapReduce論文は、入力の分割、タスク配置、失敗した処理の再実行、機械間通信をランタイムへ隠し、大量データ処理を汎用サーバーのクラスタへ広げました。重要なのは、障害を例外ではなく通常発生するものとして、再実行で吸収した点です。
• 2007年のDynamoは、ショッピングカートなど常時応答が重要な用途で、高可用なkey-value storeを構成する方法を公開しました。consistent hashing、vector clock、sloppy quorum、read repairなどを組み合わせ、単一の「正しい分散設計」ではなく、用途に応じた整合性と可用性の取引があることを示しました。
• 一方、グリッド計算とボランティアコンピューティングは、組織や家庭に散らばる未使用資源を科学計算へ束ねました。これらは共有台帳を作るのではなく、分割可能な仕事を配り、返ってきた結果を検証して集約します。詳しくは「ボランティアコンピューティング」の記事でたどります。

11Bitcoinは何を継承し、何を変えたか

• Bitcoinが継承したのは、P2P通信、複製された状態、暗号学的ハッシュ、デジタル署名、障害下での順序付けという分散システムの問題です。一方で、既知のサーバーを事前登録せず、誰でも参加でき、同一人物が多数の仮想IDを作れる環境を扱う必要がありました。
• Proof of Workは「ノード一台につき一票」ではなく、検証可能な計算資源を履歴提案の重みに変えます。各ノードは最も累積作業量の大きい有効チェーンを選び、攻撃者のhash powerがhonest側を下回るなどモデルの仮定が成り立つ範囲で、承認が深くなるほど履歴が覆る確率は低下します。ただし、数学的に即時不可逆な確定ではありません。
• マイナーが順序の候補を作っても、無効なブロックを計算量だけで正当化することはできません。各full nodeが署名、二重使用、発行量、スクリプトなどの規則を独立に検証します。計算資源によるSybil耐性と、規則による妥当性検証は別の役割です。

12設計を読むための六つの質問

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

• この枠組みで見ると、BOINC、Raft、Bitcoinはすべて分散していますが、解いている問題は異なります。BOINCは信頼できない家庭用PCへ独立仕事を配り、project固有のvalidatorで検証して必要なら複製結果を照合します。Raftは既知サーバーのログ順序を一致させ、Bitcoinは公開参加者の間で価値移転履歴を維持します。違いを消さずにつなぐことが、分散コンピューティングを理解する最短経路です。