My Projects Jp

0章：イントロダクション — お金を動かす“合意” こんにちは。久しぶりの投稿になります。 アドベントカレンダーの時期は、ふだん記事化できていないテーマに取り組む良いきっかけになりますね。 今年のテーマは 「Raft と Paxos」 です。 分散システムにおける合意（Consensus）アルゴリズムといえばまず Paxos が挙がります。しかしその説明は、歴史的背景も構造も含めて、とにかく難解です。一方の Raft は、あえて「理解しやすさ」を設計思想に据えて作られたアルゴリズムです。 本記事では、この2つのアルゴリズムを “歴史の Paxos” と “実装の Raft” という対比の軸で読み解いていきます。 ただし、いきなりアルゴリズムそのものに飛び込んでしまうと唐突なので、まずは「そもそも分散システムに“合意”はなぜ必要なのか？」という直感的なところから話を始めていきます。 0.1 分散システムで銀行口座を扱うという仮想世界（改訂案） まずは、直感的に理解しやすい“仮想の銀行システム”で考えてみましょう。 これは実際の銀行の仕組みとは異なりますが、**「なぜ合意が必要か」**を説明するには最適な例えです。 一般的に銀行システムは RDB などを中心とした堅牢なアーキテクチャを持ちますが、ここでは一旦それを横に置き、次のような少し極端な世界を想定します。 RDB を中央集約せず、 各サーバが独立したコピーの残高データを持っている 3〜5 台のサーバに残高を複製し、どのサーバも同じ残高に到達する必要がある サーバは落ちたり復帰したりする ネットワークは遅延するし、順序も入れ替わり、メッセージがロスすることもある （補足） 実際の金融システムや生命に関わるシステムでは、この記事で説明する合意アルゴリズムよりもさらに高い保証が必要です。そのため、ここで紹介するメカニズムが“どこにでも”使われているわけではありません。ただし 「どうやって複数台の状態を揃えるのか」 を理解するうえでは十分役に立ちます。 この前提のもとで扱う世界は、常に 不確実 です。 だからこそ、すべてのサーバが同じ状態に到達するためには 「操作が同じ順序で実行されること」 が絶対条件になります。 “合意”とは、この順序を全サー...

1.  この記事で書くことは何？ 　この投稿では、2021 年のアドベントカレンダー用に書くので、前後の投稿とは関係なく前後のコンテキストがわからなくても読めるように書こうかと思っています。もしかしたら、この投稿がこのBlog の初投稿になっているかもしれません。 　本投稿では、分散システムはそんなに詳しくないけど、ちょっと興味があるって人が、分散システムに入門できればと思って書いています。分散アルゴリズムの基本は案外簡単でもある事を知ってもらい、その応用アルゴリズムの理解に役立てばと思います。入門にあたり、重要となる考えに時間の概念があります。この記事内では、特に分散システムの時間に関して書いていこうかと思います。分散アルゴリズムの基本的な概念はとてもシンプルですので、分散アルゴリズムを難しそうに思わなくなる人が増えればと思います。 2.  背景 　分散システムは、我々の社会で至って普通に利用されているシステムの一つです。 　分散システムという分野は、コンピュータの歴史では比較的歴史の古いものひとつです。コンピュータは、単一の巨大な大型でパワフルな計算機に集中的に計算する時代を経験したり、それらを低価格で実現できるように等の理由により並行処理ができるようにしてみる様な時代を経験してみたりを繰り返しながら進化を続けています。計算機を複数利用することで、システムを機能単位でモジュールを分割することができたり、大きい計算量のある処理を分割・並行処理を行い計算時間の短縮が得られるメリットがあります。 　一方で、複数の機能群や計算機群の中で一つでも故障する事で、全てが利用できない様な状態は困ります。分散システム内の一部が故障しないようにする・故障してもシステム全体としてはサービス可能な構造を作る方法も様々なアプローチがあります。故障を管理するための計算機を用意するのもひとつの方法です。しかし、故障を管理するためのシステムが故障すると故障が管理できないなどのSinglePointOfFailure があります。自律分散システムでは、この様に単一の故障管理機構を利用することなく、システムが自律的に故障とうまく共存ししながら、目的とするサービスを提供し続けることを目的とします。もちろん、システム内の一部が故障した場合には、パフォーマンスの低下や一部の機能が利用で...