分散合意アルゴリズム (1) ? Paxos

全体概要

このセミナーは、「分散合意アルゴリズム Paxos」を中心テーマとして掲げ、現代のIT技術者が避けて通れない問いに真正面から向き合います。その問いとは、「ネットワーク上に分散した複数のノードが、障害やメッセージ遅延の存在する環境下で、どのようにして一つの値に合意できるのか」というものです。

セミナーの背景には、日本で大規模システム障害が連続して発生しているという現実的な危機感があります [p.5]。21世紀初頭のクラウドとスマートフォンの登場により、今日のプログラマの大部分は本人の意識如何にかかわらず「ネットワーク・プログラマ」となりました [p.8], [p.9]。しかしその技術的意味が、クラウド以前の世代にも以降の世代にも、十分には伝わっていないという問題意識が本セミナーの出発点となっています [p.11]。

Paxosは1998年にLeslie Lamportが発表した分散合意アルゴリズムです [p.81]。GoogleのGFS・BigTableの両システムで共通に利用された分散ロックサービス「Chubby」はPaxosの実装にほかならず、また「Googleの秘密兵器」と呼ばれたクラスタ管理システム「Borg」もその永続ストアにPaxosを採用しています [p.13], [p.65]。さらにApache Mesos、ZooKeeperなど現代のコンテナ・オーケストレーション技術の根底にも同じ思想が流れています [p.66], [p.67]。

セミナーは三部構成で、第一部でネットワーク・プログラミングの本質的な難しさを哲学的・工学的に整理し、第二部でPaxosが実際にどのような役割を担っているかをシステム事例から俯瞰し、第三部でアルゴリズムそのものを「たとえ話」と「形式的定義」の両面から解説します。「分散合意」は枯れた過去の技術ではなく、その重要性は現代のIT技術においても新しい装いのもとに引き継がれているというのが、本セミナー全体を貫く結論です [p.13]。

講義のロードマップ

■ Part 0: はじめに ― なぜ、今、Paxosなのか？

• この部の核心:

大規模システム障害の多発という現実を出発点として、クラウド技術の歴史的意義とその技術的エッセンスが十分に継承されていないという危機感を示します。GFS・BigTableに共通して使われた「Chubby」がPaxosの実装であることを指摘し、知らないままに通り過ぎることのできない技術として本セミナーの意義を宣言します [p.5], [p.13]。

• 論理展開:
• 日本における大規模システム障害（みずほ銀行、JIP事例）を冒頭の問題提起として提示 [p.6], [p.7]
• 21世紀のIT変化の本質はクラウドとクラウドデバイス（スマートフォン）の成立にある [p.8]
• 変化のスピードが早すぎたため、世代を超えて技術的意味の断絶が生じている [p.11]
• GFS/BigTable/Borgを支えるChubbyがPaxosの実装であるという事実が核心 [p.13]

■ Part 1: ネットワーク・プログラミングの難しさ

• この部の核心:

Jim Waldoの1994年の論文「A Note on Distributed Computing」を主軸に据え、「ローカルなプログラミングとリモートなプログラミングは本質的に異なる」という命題を丁寧に論証します。レイテンシ・部分的障害・状態の喪失という三つの難関が、システムの複雑さの段階的な進化（SEQ→MT→MP→MM→MMU）とともに現れることを示します [p.16], [p.40]。

• 論理展開:
• ローカルオブジェクトとリモートオブジェクトを同一視しようとする「Unified Objectsのビジョン」は根本的に誤りである [p.22], [p.24], [p.27]
• ネットワーク越しのパケット送受信は「1ナノ秒＝1秒」換算で「5年間のブロック」に相当するという衝撃的なレイテンシの可視化 [p.33], [p.34], [p.35], [p.36]
• 複雑さの段階的飛躍：MT移行で「順序」を失い、MP移行で「単一コンテキスト」を失い、MM移行で「グローバルな状態」を失う [p.41], [p.42]
• 各段階での喪失と引き換えに得るもの：並列処理・プロセス分離・独立した障害・スケール [p.43]

■ Part 2: Paxosは、どう使われているか

• この部の核心:

Paxosの抽象的なアルゴリズムが、実際の大規模分散システムの中でどのような具体的役割を担っているかをイメージとして把握させます。クラウドにおけるノードの多重化・再構成、Googleのクラスタ管理システムBorg、そして「マスターが二つ存在する問題」をLeaseで解決するパターンという三つの切り口から、Paxosの実用的価値を浮き彫りにします [p.50], [p.60], [p.71]。

• 論理展開:
• Azureのデータノード多重化：Primaryからの読み込みとQuorumに従う書き込みの仕組み [p.50]
• Primary障害・Secondary除去・replicaの修復が重複して起きても安全な再構成の設計 [p.51]
• GoogleのBorgは「Googleの秘密兵器」として10年以上非公開だったが、2015年に初公開。永続ストアにPaxosを採用 [p.58], [p.59], [p.64], [p.65]
• MesosはBorgにインスパイアされたOSSで、ZooKeeper quorumによるマスター選挙を実装 [p.66], [p.67]
• マスターが二つ存在する問題の解決策としてのLeaseの考え方：旧マスターのリースが切れた場合にのみ新マスター提案を受け入れる [p.70], [p.71]
• GFS・BigTableが利用した分散ロックサービスChubbyの構成（5台のサーバ、1台のmaster、RPCによるクライアントアクセス）[p.72]

■ Part 3: Paxosアルゴリズム

• この部の核心:

Lamportの論文「The Part-Time Parliament」が描く架空のPaxos島の議会制度という巧みな「たとえ話」から出発し、形式的な三条件（B1・B2・B3）、さらにPhase 1a/1b/2a/2b/3という具体的プロトコルの流れへと段階的に理解を深めます。最終的に安全性（Safety）と生存性（Liveness）という二つの保証がどのように成立するかを明示します [p.79], [p.89], [p.127]。

• 論理展開:
• たとえ話（1）：Paxos島の議会では全議員が台帳を持ち、使者によってのみ通信し、議員は自由に議場を出入りする。これが分散システムのノード・メッセージ・障害モデルに対応 [p.82], [p.83], [p.85]
• たとえ話（2）：投票の三条件 B1（番号のユニーク性）・B2（任意の二quorumの共通メンバー存在）・B3（以前の投票の最新法令の継承）が一貫性を保証する [p.89]
• 投票セットの具体例（番号2・5・14・27・29の五つの投票）でB3の動作を視覚的に確認 [p.90], [p.91], [p.92], [p.93], [p.94]
• ノードの三役割：Proposer（提案者）・Acceptor（受容者）・Learner（学習者）[p.96]
• Phase 1（prepare）：proposerが番号nのprepareリクエストを送り、acceptorは最大既知番号と最新賛成票をpromiseレスポンスとして返す [p.97]
• Phase 2（accept）：proposerがacceptリクエストを送り、acceptorが多数派となれば値vが選択される [p.98], [p.99]
• Paxosの性質P1・P2・P3：P3が「最も大きい番号の提案の値を継承する」ことを保証し、一貫性の核心となる [p.101], [p.102]
• Phase 1a/1b/2a/2b/3の詳細：FreeとForcedの二状況に応じたproposerの値の決定ロジック [p.109], [p.110], [p.111], [p.112], [p.113], [p.115], [p.116], [p.117], [p.119], [p.120], [p.121], [p.122], [p.125], [p.126]
• 2F+1台のacceprtorがあればF台の障害に耐えられる。Two-Phase CommitはPaxos CommitのF=0の特殊ケースである [p.105], [p.106]
• 安全性（提案された値だけが・一つだけ選ばれる）と生存性（最終的に何らかの値が選ばれ、学習される）の二保証 [p.127]