分散合意アルゴリズム (1) -- Paxos
2022/01/29 マルレク「分散合意アルゴリズム (1) -- Paxos」概要
今回のマルレクのテーマは、代表的な「分散合意アルゴリズム」であるPaxosの紹介です。
申し込み：https://paxos.peatix.com/
なんで今頃Paxosなのかと感じる人もいると思います。IT系の話題を取り上げるのは久しぶりなので、最初に、このセミナーの背景を述べておこうと思います。それは、現在の日本で、大規模なシステム障害が連続して起きていることと、すこし関係しています。
21世紀初頭のIT技術とITビジネスの大きな変化は、膨大な計算資源を集中してネットワークを通じてサービスを提供するクラウドと呼ばれる巨大なシステムの成立によって特徴づけられます。こうしたクラウドへのリソースの集中に対応して、クラウドのサービスを利用するクラウド・デバイスとしてのスマートフォンが拡散し、ほとんど全人類に普及します。
技術者のライフサイクルからみれば、このクラウド時代への移行は、驚くほど短期間に急速に進行しました。
大規模システムというのは、単に、システムの規模が大きいことを意味しません。今日では、大規模システムは、設計者がそれを意識するか否かに関わらず、クラウドと同じようにネットワークをまたいだ大規模分散システムの形を取ります。
プログラミングのスタイルも大きく変わりました。サーバーサイドでサービスを作るプログラマも、クライアントサイドでアプリを作るプログラマも、本人がそれを意識すると否とに関わらず、今日のプログラマの大部分は、ネットワーク・プログラマです。
クラウド技術はもちろんネットワーク技術なのですが、クラウド技術成立の前提には、「ネットワーク上で規模を拡大しながら、システム全体としては障害を起こさないシステムを作ることは難しい」という認識があったことです。この認識は「ハードウェアの障害は起きるものだ」という障害観の成立とともに、重要なものだと思います。
クラウドの技術は、まさにこうした困難を乗り越える技術として登場しました。また、それは、冒頭でも見たように、大きな成功を収めました。
ただ、僕は、変化のスピードが早すぎて --- 繰り返しますが、技術者のライフサイクルから見ればということですが --- ネットワーク上でシステムを構築するというクラウド時代の中心的変化の技術的な意味が、クラウド以前の技術者にもクラウド以降の技術者にも、きちんと伝わっていないのではという心配をもっています。
それは、クラウド以前の技術者だけの問題ではありません。若い技術者は、必ずしもクラウド技術の一時代を画したGoogleの"Google File System (GFS)" や"BigTable" に関心を持っているわけではないように思えます。
GFSとBigTableは、直接的には異なる目的のために開発されたものです。ただ、両者で共通に利用されている "Chubby"と呼ばれた「分散ロック・サービス」は、Paxosの実装にほかなりません。見かけは地味ですが、こうした形での「分散合意アルゴリズム」の利用には、クラウド技術のエッセンスが詰まっていると僕は考えています。
10年以上前の技術の昔話をするつもりはありません。「風が吹けばオケ屋が儲かる」式に「Paxosがわかればクラウド技術がわかる」という話をするつもりもありません。ただ、知らないままに通り過ぎる訳にはいかない技術は存在します。
その上、「分散合意」技術、けっして完成した過去の枯れた技術ではありません。その重要性は、現代のIT技術においても、新しい装いのもとに引きつがれています。
セミナーの構成と参考文献
今回のセミナーは、次のような構成を考えています。
第一部 ネットワーク・プログラミングの難しさ
第二部 Paxosは、どう使われているか
第三部 Paxosアルゴリズム
第一部 ネットワーク・プログラミングの難しさ
第一部では、「ローカルなプログラミングとリモートなプログラミングをはっきりと区別すべき」だという立場を明確にしたJim Waldoの洞察に依拠して、ネットワーク・プログラミングの「難しさ」を振り返ってみようと思います。
Jim Waldo
“A Note on Distributed Computing”
https://scholar.harvard.edu/waldo/publications/note-distributed-computing
"Complexity Quanta and Platform Definition"
https://wstrange.wordpress.com/2006/10/05/summary-jim-waldos-keynote-at-the-10th-jini-community-meeting/
第二部 Paxosは、どう使われているか
第二部では、Paxosが、どういうところで利用されているのかを紹介します。
"Large-scale cluster management at Google with Borg"
https://storage.googleapis.com/pub-tools-public-publication-data/pdf/43438.pdf
"The Chubby lock service for loosely-coupled distributed systems"
https://static.googleusercontent.com/media/research.google.com/ja//archive/chubby-osdi06.pdf
第三部 Paxosアルゴリズム
第三部は、Paxos アルゴリズムを紹介します。
Leslie Lamport
"The Part-Time Parliament"
https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf
Jim Gray and Leslie Lamport
"Consensus on Transaction Commit"
https://arxiv.org/pdf/cs/0408036.pdf
この論文自体は、決して読みやすいものではないのですが、ネットワーク環境での Two-Phase Commitの失敗例や、クラウド環境でPaxosのアルゴリズムがどう利用されるのかのシナリオベースで、わかりやすく解説できればいいと考えています。
