過去・現在・未来

 【 マルレク「分散合意アルゴリズム -- Paxos」講演資料公開しました 】 1/29 マルレク「分散合意アルゴリズム -- Paxos」講演資料公開しました。 https://www.marulabo.net/docs/paxos/ から、ご利用ください。 セミナーに向けたショートムービーは、次からアクセスできます。https://youtu.be/24Reuk66l04?list=PLQIrJ0f9gMcOTqmza5742zyEYjkApl_fF 1/29 マルレクへのお申し込みは、つぎのページからお願いします。 https://paxos.peatix.com/　 1/29の夕方  6時くらいまで申し込み受け付けています。 多くの方のお申し込み、おまちしています。

 【「Paxos アルゴリズム (2)」を公開しました 】 1/29  マルレク「分散合意アルゴリズム (1) — Paxos」にむけ、ショートムービー「Paxos アルゴリズム (2)」を公開しました。ご利用ください。 https://youtu.be/d0ZHdFym79c?list=PLQIrJ0f9gMOTqmza5742zyEYjkApl_fF Paxosアルゴリズムの基本論文は二つあります。 一つは、先の「たとえ話で理解するPaxos」で紹介した、Lamportの "Part-Time Parliament" の論文です。もう一つは、Jim GreyとLamportの”Consensus on Transaction Commit”という論文です。　　 https://arxiv.org/pdf/cs/0408036.pdf 今回は、こちらの論文に依拠して、Paxosのアルゴリズムの説明をしたいと思います。 と思ったのですが、この論文の逐条の解釈をやり始めてみると、これがなかなか難しいのです。そこで、今回は、この論文のポイントを説明するというスタイルに、途中で方針を変えました。 スライドでブルーの見出のページが現論文の翻訳で、見出しがグリーンの部分が対応する丸山の解説です。 といっても、原論文を読む必要がなくなる訳ではありません。特に、今回は、ほとんどふれることもできませんでしたが、この論文のAppendixにある TLA+を用いたPaxosアルゴリズムの「形式的記述」は、この論文の真骨頂です。時間があったら、現論文に、ぜひチャレンジください。 （今度のセミナー参加者には、この論文の丸山による翻訳をプレゼントしたいと思います） スライドの pdf はこちらです。 https://drive.google.com/file/d/1MYQ3t9wB61vfk4_kR1FEcNbmB4o3SnoL/view?usp=sharing このPaxosシリーズのショートムービー・参考資料はこちらからアクセスできます。https://www.marulabo.net/docs/paxos/

 【「Paxos アルゴリズム (1)」を公開しました 】 1/29  マルレク「分散合意アルゴリズム (1) — Paxos」にむけ、ショートムービー「Paxos アルゴリズム (1)」を公開しました。ご利用ください。 https://youtu.be/83RRijzzesI?list=PLQIrJ0f9gMcOTqmza5742zyEYjkApl_fF 今回からは、古代Paxosのたとえ話ではなく、現代の分散ネットワークのもとでのPaxosアルゴリズムの紹介です。 Paxosでは、登場人物は、異なる三つの役割をもちます。 　・Proposers（提案者）-- 合意すべき値の提案者 　・Acceptors（受容者）-- 合意の形成に関わる人たち 　・Learners  （学習者）--  形成された合意を学ぶ人たち 物理ノードは、一つ以上の役割を持つことができます。実際、実装的には、一つの物理ノードが、上記3つの論理的役割を同時に果たすのは、よくみられることです。 Paxosのアルゴリズムは、つぎの三つの phaseを持ちます。 　・phase 1 (prepare)　:  提案者による提案に対する投票の準備。 　・phase 2 (accept)   ： accepter による投票と合意の受容。 　・phase 3 (commit)  ： acceptorが受け入れた合意の学習。 phase 1とphase 2 では、一つの提案とその提案の一つの投票に紐づけられた「投票番号」が、大きな役割を果たします。 スライドの pdf はこちらです。 https://drive.google.com/file/d/1LuQzbq3a7B0jM5-12pXdbgXQjs_JuCQQ/view?usp=sharing このPaxosシリーズのショートムービー・参考資料はこちらからアクセスできます。https://www.marulabo.net/docs/paxos/

 【「たとえ話で理解するPaxos (2)」を公開しました 】 1/29  マルレク「分散合意アルゴリズム (1) — Paxos」にむけ、ショートムービー「たとえ話で理解するPaxos (2)」を公開しました。ご利用ください。 https://youtu.be/8NEJRUJKVaA?list=PLQIrJ0f9gMcOTqmza5742zyEYjkApl_fF たとえ話で理解するPaxosの二回目です。引き続き、Lamportの例え話を追いかけます。 「Paxosの数学者は、投票の集合Bに3つの条件を定義して、行われた投票の集合がこれらの条件を満たしていれば、投票の一貫性が保証され、議事の進行が可能であることを示した。」 彼は、Paxosの数学者は、データの整合性を保証する条件を見つけていたといいます。それが、つぎの条件です。 　B1： 　Bの中の投票は、全てユニークな投票番号を持つ。 　B2：　 Bの中の任意の二つの投票のquorumには、少なくとも一人が、共通に含まれる。 　B3： 　Bの中の投票Bは、Bの以前の投票で、quorum内のだれかが賛成票を投じていれば、Bの投票の対象である法令は以前の投票の中で最新の法令に等しい。 B1, B2の条件は、比較的わかりやすいのですが、B3の条件は、わかりにくいものです。ただし、B3の条件は、Paxosの振る舞いを理解する上で重要な意味を持っています。 今回は、特に、条件B3にフォーカスして、それがどのような働きをしているのかを、具体的な例で紹介しようと思います。 スライドのpdfは、次からアクセスできます。https://drive.google.com/file/d/1LjoSWzXtnK2FmXpPh8vNWXgsYp1Sql7D/view?usp=sharing このシリーズののショートムービー・pdf資料は、次からアクセスください。https://www.marulabo.net/docs/paxos/

 【「たとえ話で理解するPaxos (1)」を公開しました 】 1/29  マルレク「分散合意アルゴリズム (1) — Paxos」にむけ、ショートムービー「たとえ話で理解するPaxos (1)」を公開しました。ご利用ください。 https://youtu.be/DRd1lVhtemo?list=PLQIrJ0f9gMcOTqmza5742zyEYjkApl_fF 今回から、Paxosアルゴリズムの説明に入ります。ただし、まわりみちは続きます。 今回は、Paxosアルゴリズムの「たとえ話」での説明の第一回です。 Paxosという名前の由来から始めましょう。 Paxosは、エーゲ海のギリシャの島の名前です。 ある考古学者が古代ギリシャのPaxos島で奇妙な議会制度が発達していたことを発見し、その意思決定のスタイルが現代の分散システムの設計にも役に立つのではという論文を発表します。それが、 “The Part-Time Parliament”という論文です。 この論文が、世に出るには、少し曲折がありました。論文を原著者に代わって投稿した編集者は、こう言っています。 「この投稿は、最近になって、編集部のキャビネットの中から発見されたものだ。古いものだが、編集長は掲載する価値があると考えた。著者は現在、ギリシャの島々でフィールドワークをしていて連絡が取れないため、私が掲載の準備の依頼を受けた。 著者は考古学者で、コンピュータサイエンスにはほとんど興味がないようだ。また、残念なことに、彼が紹介した謎に包まれた古代Paxos文明は、ほとんどのコンピュータ科学者にとって興味のないものだろう。 にもかかわらず、その立法システムは、非同期環境での分散型コンピュータシステムの実装方法の優れたモデルとなっている。実際、Paxos人がプロトコルに加えた改良点のいくつかは、コンピュータ・システムの文献では知られていない。」 ところが、これは、この論文の本当の著者である Lamportの冗談なんです。 ここでは、この架空の物語を書いたLamportが、Paxos島の議会制度に想定したものをまずみておこうと思います。 それは、アルゴリズムとしてのPaxosの、とてもすぐれた「たとえ話」による解説になっています。 スライドのpdfは、次からアクセスできます。https://drive.google

【「LeaseとPaxos」を公開しました 】 1/29  マルレク「分散合意アルゴリズム (1) — Paxos」にむけ、ショートムービー「LeaseとPaxos」を公開しました。ご利用ください。 https://youtu.be/hzVT0fRx22k?list=PLQIrJ0f9gMcOTqmza5742zyEYjkApl_fF 前回、前々回とPaxosアルゴリズムは、Azureのようなクラウド技術でも、Borgのようなコンテナー技術でも、大事な役割を果たしているという話をしてきました。 今回は、少し違った角度からPaxos を見てみようと思います。 それは、このシリーズの前半に紹介した Jim Waldoたちの分散システムの特徴の分析と、Paxosとの接点についてです。具体的には、Waldoたちが技術的に定着させた「リース」の概念とPaxosの関係について述べたいと思います。 分散システムでは、システム全体の統合・調整を担う、マスター・ノードと呼ばれるノードが特別な役割を果たします。 どの時点でも、システムの中心となるマスター・ノードは、必ず存在しなければなりません。しかも、マスターは、一つだけです。障害を引き金としたノードの再構成が行われたとしても、二つのノードが、同時にマスターになってはいけません。 その点では、マスター・ノードの復旧は、単なるレプリカ・ノードの復旧とは異なる問題があります。こうした問題を解決するには、マスターがリース期間を持つという考えが役に立ちます。同時に、そのことで、リースという考えとPaxosの考え方の類似を見ることができます。 今回は、実は、Paxosアルゴリズムの最小実装と言っていい googleのChubbyのアルゴリズムの紹介です。 スライドは、次のURLからアクセスできます。 https://drive.google.com/file/d/1J9PRLW4mKDWDMNJW5V6iCYGHQgegP-hF/view?usp=sharing 以前の講演ビデオ・講演資料は、次からアクセスください。 https://www.marulabo.net/docs/paxos/

【「Paxosとコンテナー技術」を公開しました 】 1/29  マルレク「分散合意アルゴリズム (1) — Paxos」にむけ、ショートムービー「Paxosとコンテナー技術」を公開しました。ご利用ください。 https://youtu.be/_tRSLUmnETY?list=PLQIrJ0f9gMcOTqmza5742zyEYjkApl_fF 前回は、MSのクラウドAzureのデータ・ノードの多重化と、障害が起きた際のノードの再構成の振る舞いを紹介して、Paxosの働きをイメージとしてつかんでもらおうとしました。 クラウドの高い耐障害性、高い可用性は、こうしたメカニズムで支えられています。そうしたメカニズムは、クラウド以前には存在しなかったものです。 前回のコンテンツは、その意味では、クラウド以前の技術者に留意して学んでほしいことだったのですが、今回のコンテンツは、クラウド以降の技術者が学んでほしいことを意識しています。 今回のシリーズで強調してきたように、ネットワーク・プログラミングには独特の難しさがあります。ネットワークの世界には、さまざまな落とし穴があります。 大規模な分散システムを開発するには -- 現在の大規模システムは、開発者がそれを意識するか否かにかかわらず、大規模分散システムの形をとります --  注意しなければいけないことがあるのです。 2015年、Googleは、彼らの大規模分散システムを支えてきたBorgの技術を公開します。これは、大規模分散システムの開発技術にとって、画期的な出来事だったと思います。Borgのオープンソース版のKubernetesの受容を中心に、大規模分散システムの開発スタイルは大きく変わりました。 スライドは、次のURLからアクセスできます。 https://drive.google.com/file/d/1J9PRLW4mKDWDMNJW5V6iCYGHQgegP-hF/view?usp=sharing 以前の講演ビデオ・講演資料は、次からアクセスください。 https://www.marulabo.net/docs/paxos/