2016年1月20日

分散システムについて語るときに我々の語ること ― 分散システムにまつわる重要な概念について

WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS

(2015-12-04)by Alvaro Videla

本記事は、原著者の許諾のもとに翻訳・掲載しております。

分散システムについては、もう随分と前から学びたいと思っていました。ただ、それは一度首を突っ込んだら最後、ゴールのない迷路に迷い込むようなものなのです。どこまでも続いているウサギの穴のようなものです。分散システムに関する文献は星の数ほど存在します。様々な大学からたくさんの論文が発表されているばかりでなく、膨大な数の書籍もあるのです。私のような全くの初心者には、どの論文を読んだらいいのか、どの書籍を買ったらいいのか、見当もつきません。

そんなとき、一部のブロガーが、 分散システムエンジニア （それがどういう意味であれ）になるなら知っておくべき論文というものを推奨しているのを見つけました。その一部を紹介しましょう。 FLP , Zab , Time, Clocks and the Ordering of Events in a Distributed Systems , Viewstamped Replication , Paxos , Chubby などです。ただ私には、こうした論文を読むべきだという正当な理由が分からないということが問題でした。単に知識を得るためだけに、または好奇心を満たすためだけに学ぶという考え方には大賛成です。とはいえ1日は24時間しかありませんから、何から読むべきか優先順位をつける必要があると思います。

先に述べた通り、膨大な数の論文や研究資料の他に、書籍も数多くあります。そうした書籍もたくさん購入し、あらゆる章を読みました。しかし、タイトルに期待を膨らませて読み始めるものの、結局は知りたかった内容とは全く無関係だったり、知りたい問題の解決につながるようなものではなかったりします。そこで私は、分散システムについて私が考える主なコンセプトを論文や書籍の他、同システムについて学ぶことができる資料を引用しながら掘り下げていきたいと考えたのです。

なお、本記事を書いていく間も、私は学習を継続しています。ミスが起こることもあるだろうと、どうか温かい目で見守ってください。また、最終的にここに書くことを広めようとしているということをご承知おきください。

はじめにお伝えしておきたいのは、私はこのブログに投稿した記事について、様々な学会で発表してきたということです。そのため、もし興味があれば、以下のスライドをご覧いただければと思います。

また、ストックホルムで開催されたErlangユーザー学会でこの内容を講演したときの映像もあります。

それでは記事の内容を見ていきましょう。

主なコンセプト

分散システムのアルゴリズムは、異なる種類の属性により分類することができます。例えば、タイミングモデル、使用されるプロセス間通信の種類、アルゴリズムに適した故障モデル、他にも以下に示す通りたくさんあります。

主なコンセプトは以下の通りです。

タイミングモデル
プロセス間通信
故障モード
故障検出機能
リーダー選出
合意
Quorums
分散システムの時間
FLPの概要
まとめ
参考文献

タイミングモデル

同期モデル、非同期モデル、部分的同期モデル の3種類があります。

同期モデル が最も単純で使いやすいものです。ステップごとに同期を取りながら処理を進めます。この時のステップを同期ラウンドといいます。メッセージが届けられる時間は通常、事前に分かるので、プロセスの処理速度も推定できます。言い換えると、アルゴリズムの１つのステップを実行するのにどれくらい時間がかかるのかが分かるのです。このモデルの問題点は、現実をうまく反映しないということです。分散システムにおいてはなおさらで、メッセージを別のプロセスに送ることはできても、あとはそのメッセージがそのプロセスに到着することを星に願うしかありません。一方、このモデルを使う利点は、のちに他のモデルに移すことのできるような理論上の結果を導き出せるということです。例えば、このモデルはタイミングについて保証しているので、その保証された時間枠の中で解決できない問題が発生した場合は、例え時間枠を広げたとしても問題は恐らく解決しないでしょう（後述の完璧な故障検知機能を思い浮かべてください）。

非同期モデル は少し複雑になります。コンポーネントは処理を進めますが、処理を実行する順序は予測できません。従って、処理が完了するまでの時間も保証できません。このモデルの問題点の１つは、単純なモデルでありながら現実に比較的近いことは間違いないものの、現実を適切に反映しているとは限らないことです。例えば、あるプロセスは要求に応答するために非常に時間がかかるかも知れませんが、実際のプロジェクトでは、その要求にタイムアウトが課され、そのタイムアウトが期限切れになると、その要求は中断されるでしょう。このモデルが難しいのは、プロセスが無事に動いているかどうかをどう確認するかです。有名な 不可能結果 の１つの “Impossibility of Consensus with one Faulty Process（故障中のプロセスとの合意の不可能性）” もこのモデルを対象にした研究でした。プロセスがクラッシュしているのか、単にメッセージに対する応答が遅いだけなのかを検出することはできません。

部分的同期モデル ではコンポーネントがタイミングに関する情報を保持していて、ほぼ同期しているクロックにアクセスできます。または、メッセージが届けられるまでにどれくらいの時間を要するか、処理を実行するプロセスにどれだけ時間がかかるのかの概算の情報を持っています。

Nancy Lynchの書いた『Distributed Algorithms（分散アルゴリズム）』という本の中で、これらのタイミングモデルをベースに書かれたセクションがあります。

プロセス間通信

ここではシステムのプロセス どのようにして 情報をやり取りしているのかを考えましょう。お互いにメッセージを送りあうことによる メッセージパッシング モデルや、共通の変数にアクセスすることでデータの共有をする 共有メモリ モデルを使用して、情報のやり取りは実現できます。

１つ覚えておいてもらいたいのは、メッセージパッシングアルゴリズムは分散共有メモリのオブジェクトを作成するのに使うことができるということです。各書籍でよく取り上げられている例が、読み取り/書き込みレジスタの実装です。また、キューやスタックも使えます。キューやスタックは不可分操作のような一貫性のあるプロパティを記述するのに何人かの著者が使っていました。ここで、「共通変数にアクセスすることによってプロセス間でデータを共有する方法としての 共有メモリ 」を、前述したような、メッセージパッシングで構築する 共有メモリの抽象化 と混同しないように気を付けてください。

メッセージパッシングモデルに話を戻しますと、アルゴリズムを理解する上でもう１つ別の抽象化を考えなくてはいけません。それはプロセス間で使われる一種のリンクです（プロセス間でメッセージをやり取りするために使われるチャネルを思い浮かべてください）。これらのリンクでは、それらを使用するアルゴリズムに一定の保証が与えられます。例えば、信頼性のある配信をし、複製を送らない 完璧なリンク の抽象化があります。この抽象化は、確実に1回だけの配信を保証します。この抽象化も現実がうまく反映されないことは簡単に分かります。それゆえ、アルゴリズムの設計者が、実際のシステムに近いモデルを設計する時に使うリンクの抽象化は他にもあります。完璧なリンクの抽象化がリアルに感じられなくても、とても役に立つ方法だということは覚えておいてください。例えば、ある問題が 完璧なリンク を仮定しても解決不可能であることを証明できるなら、膨大な量の、同様に解決不可能かも知れない関連する問題について知ることができるのです。リンク先のトピックでは、著者たちは通常、メッセージの処理順序をFIFOと想定していて、 Zab もこれに従っています。

故障モード

私は failure modes in distributed systems（分散システムの故障モード）についての記事をすでに書いていますが、とても重要なことなので今回も同じ説明をします。分散システムモデルのプロパティの一つは、「どんなプロセス故障が推測されるか」です。 クラッシュストップ（クラッシュによって停止する ）故障モードでは、プロセスがクラッシュするまでプロセスは正常であると想定されます。一度クラッシュすると、二度と元に戻りません。また、 クラッシュ･リカバリーモデル というのもあります。このモデルは、故障のあとに復旧することが可能です。そして、中には、クラッシュする前に記述したものを復旧するためのプロセスも含まれているアルゴリズムもいくつかあります。これを可能にする方法としては、永続的な記憶装置から読み込む、グループの中の別のプロセスと通信するといった方法が考えられます。グループメンバーシップのアルゴリズムでは意味がありません。クラッシュしてから復旧するプロセスは、正常だったときの同一のプロセスであるとはみなされませ。ん。これは通常、グループが動的であるか、固定であるかによります

また、プロセスがメッセージの送受信に失敗する故障モードもあります。このモードのことを オミッション（切り捨て）故障モード といいます。さまざまな切り捨てがあります。プロセスがメッセージの受信か送信に失敗する可能性もあります。なぜこれが問題なのでしょうか？　仮にプロセスのグループが分散キャッシュを実装したとします。たとえグループ上の他のプロセスからの要求の応答に失敗したり、プロセスからの要求を受信することができたとしても、そのプロセスはまだ最新の状態を保持しています。つまり、クライアントからの読み取り要求に応答することができます。

さらに複雑な故障モードはビザンチン、もしくは 任意故障モード と呼ばれるものです。ここではプロセスが他のピアに間違った情報を送ってしまう可能性があります。プロセスに成りすます可能性もあります。他のプロセスに正しいデータを送り返しても、ローカル･データベースの内容を間違って伝えてしまうこともあります。さらに別のパターンもあります。

システムの設計を考える時は、まずどんな種類の故障を扱おうとしているのかを把握する必要があります。Birman（『Guide to Reliable Distributed Systems（信頼できる分散システムのガイド）』を見てください）は、通常はビザンチン故障と戦う必要はない、と言っています。彼はYahoo!で行った作業を引用しています。Yahoo!では、クラッシュ故障はビザンチン故障よりはるかに一般的であると結論付けています。

故障検出機能

プロセス故障モードとタイミングの仮定に従って、プロセスがクラッシュした場合(あるいはクラッシュが疑われる場合)のシステムへの通知を考慮した抽象化を構築することができます。決して誤報が発生しない、 完璧な故障検出 機能を考えてみます。クラッシュストップ故障モードと同期システムを組み合わせる場合、タイムアウトを利用するだけで、このアルゴリズムを実装することができます。この故障検出機能に対して定期的にpingを返すようにプロセスに要求すると、pingが故障検出機能に到着するはずのタイミングが正確に分かります（同期モデルによって保証されているため）。設定可能な一定のタイムアウト時間を超えてもpingが到達しない場合、どこかのノードがクラッシュしたと推察することができます。

実際のシステムでは、メッセージが目的地に到達するまで、またはプロセスがステップを実行するまでの時間を見積もることが不可能な場合もあります。このような場合のために、 N ミリ秒のタイムアウト時間を過ぎてもプロセス q が応答を返さない時は q に障害発生の疑いがあると通知する、故障検出機能 p を設けることができます。 q がその後応答を返すと、 p は、障害の疑いがあるプロセスのリストから q を除外すると同時に設定値 N を増大させます。これは、システムと q との間で実際に発生したネットワーク遅延の実態が解明しきれない条件下でも、「 q は実際は稼働中のプロセスであるにもかかわらず、pingを返すまでの時間が N を超えたために、 q がクラッシュしているのではないかと疑わなければならない」という場合を除外するためです。仮にどこかの時点で q がクラッシュした場合、 p はまず q がクラッシュしたことを疑い、その判断を覆すことはありません（ q がpingを返すことはないので）。このアルゴリズムをより詳しく説明している文献があります。『Introduction to Reliable and Secure Distributed Programming（信頼性が高く安全な分散プログラミングへの入門）』の”Eventually Perfect Failure Detector”（ついに登場した完璧な故障検出機能）セクションを参照してください。

故障検出プロセスには通常、完全性と精度の2種類のプロパティが実装されています。従って 完璧な故障検出機能 には、次の2つの種類があります。

強力な完全性 ：最終的には、全ての正しいプロセスが、クラッシュした全てのプロセスを常に疑うようになる。
最高に強固な精度 ：正しいプロセスは最後まで、他の正しいプロセスから疑われることはない。

非同期モデルで発生した合意の問題を解決する際に、故障検出機能は重要な役割を果たします。上記で言及した FLP に関する論文の中で、合意ができないという結果が提示されており、このFLP不可能性は今や広く知られています。この論文では、非同期の分散システムで、その中の1つのプロセスに障害が発生していると、合意ができなくなることを取り上げています。この不可能性の回避策の1つとして、問題を避けることができる故障検出機能の導入が挙げられます。

リーダー選出

故障検出機能の問題に絡めていうと、このプロセスとは全く逆のことを実行するもの、すなわちクラッシュせずに正常に稼働しているプロセスを特定するプロセスも存在します。このプロセスはネットワーク上の他のピアとの信頼関係を確立していて、分散して実行される複数のアクションを協調させることができる、リーダーとみなされます。例えば Raft や Zab などのプロトコルは、アクションを協調させるリーダーを必要とします。

プロトコル内にリーダーがある場合、ノード間の非対称性が発生します。リーダー以外のノードはフォロワとなるからです。このことは、複数の処理で、リーダーノードがボトルネックとなる結果につながります。従って、解決しようとしている問題の性質によっては、リーダー選出が必要なプロトコルを採用するのが適切ではない場合もあります。ただしプロトコルはほとんど、リーダープロセスと一連のフォロワとの間で何らかの合意を形成することで整合性を実現していることに注意してください。具体例については、 Paxos 、 Zab 、 Raft のいずれかを参照してください。

合意

合意、または同意の問題が初めて提示されたのは、Pease、Shostak、Lamportの3名が共著でまとめた “Reaching Agreement in the Presence of Faults”（障害に対処するための合意の形成）という論文の中でのことでした。論文では、この問題を次のように取り上げていました。

耐故障性システムでは、個々のプロセッサやプロセス同士が、互いにある種の完全な合意に達するための手段が必要になることがあります。例えば、冗長性のあるシステムのプロセッサ同士で内部クロックを定期的に同期させる場合には、合意が必要です。あるいは、各プロセッサに少しずつ異なる測定値を送信する、時変入力センサに従うことで合意する場合もあります。

合意とは、複数のプロセス間で同意に達するまでの問題を指します。問題が発生すると、各プロセスは、センサが現時点で読み取っている値など、何らかの値をそれぞれに提示します。そして、提示された値に基づいて実行する共通のアクションについて同意します。例えば自動車は、ブレーキの温度レベルなど様々な情報を提供するセンサを搭載しています。各センサの精度などによって、センサが読み取る値には、ある程度の幅がありますが、ここでABSコンピュータは、ブレーキにどのくらいの圧力をかけるべきかについて合意しなければなりません。これこそ日常生活の中で発生する、合意に関する問題の解決例です。『Fault-Tolerant Real-Time Systems（耐故障性がありリアルタイム処理を実行するシステム）』」という書籍では、自動車業界の実例に基づいて、分散システムの合意やその他の問題が説明されています。

ある形式の合意を実現するプロセスは、提案関数と決定関数を含むAPIを開示することにより機能します。合意を開始した際、プロセスはある値を提示しますが、そのプロセスは、システム内で提示された複数の値の中から、１つの値を決定しなければなりません。このアルゴリズムには、Termination、Validity、Integrity、Agreementの4つのプロパティを含まなければなりません。例えば 通常の合意 では、プロパティにはそれぞれ次のような性質があります。

Termination（終結） ：正常なプロセスは全て、最終的には何らかの値を決定する。
Validity（正当性） ：1つのプロセスが値vを決定すると、別のプロセスがvを提示する。
Integrity（統一性） ：プロセスが値を決定するのは1度だけである。
Agreement（同意） ：正常なプロセスが決定する値は1つだけである。

合意についての詳細は、先述の論文を参照してください。また、以下の文献も大いに参考になります。

Quorums

quorumは、耐故障性の分散システムの設計に使用されるツールです。quorumとは、なんらかのプロセスが故障した可能性のあるときにシステムの特性を知るために使用することができる、共通する部分を有する複数のプロセスのセットを指します。

例えば、あるアルゴリズムを使用する場合に、N個のプロセスがクラッシュ故障モードを有するとすれば、プロセスの過半数がある操作(例えばデータベースへの書き込みなど)をシステムに対して行っているとき、プロセスのquorumが必ず存在します。プロセスのうち半数未満、すなわち N/2 - 1 個のプロセスが故障したとしても、プロセスの過半数はシステムに加えられた最近の操作を覚えています。例えば、Raftはシステムにログをコミットするときに、多数決を使用します。リーダーは、クラスタ内のサーバの半数がログ複製の要求に応答し終わるとすぐに、ステートマシンにエントリを行います。サーバの半数にリーダーを加えたものが過半数を構成します。このことには、クラスタ全体がログ複製RPC要求に応答するまでRaftが待つ必要がないという利点があります。

別の例を示します。共有リソースへの同時アクセスを1つのプロセスに制限したいとします。このリソースはプロセスのセット S によって保護されています。プロセス p がそのリソースにアクセスしたいときは、最初に、そのリソースを保護しているプロセスセット S の過半数に対して許可を求める必要があります。次にプロセスセット S の過半数が、そのリソースへのアクセスを p に許可します。ここで、プロセス q がシステムに加わり、共有リソースへのアクセスを試みます。 q が S 内のどのプロセスに連絡したとしても、その共有リソースを p が開放するまでは、その共有リソースへのアクセスを q に許可することになる過半数のプロセスには到達できません。詳細については、『The Load, Capacity, and Availability of Quorum Systems(システムの負荷、容量、および可用性)』を参照してください。

quorumは、必ずしもプロセスの過半数を指すわけではありません。例えば、ビザンチン故障を被る可能性のある N 個のプロセスのグループの場合などです。この場合、操作が成功するためには、quorumを形成するには過半数よりも多くのプロセスが必要なことがあります。この場合は、許容されるプロセス故障の数が f であればquorumは (N + f) / 2 個以上のプロセスのセットになります。詳細については、『Introduction to Reliable and Secure Distributed Programming（信頼性が高く安全な分散プログラミングへの入門）』を参照してください。

この話題に興味のある方には、1冊まるごと分散システムのquorumについて書かれている次の書籍もあります。

『Quorum Systems: With Applications to Storage and Consensus（Quorumシステム：ストレージと合意への適用）』

分散システムの時間

時間とその影響を理解することは、分散システムでの最も重大な問題の１つです。私たちが日常生活で慣れているイベントの概念では、次々と発生するイベントの順序は完全に happend before の順によって定められますが、メッセージを交換したり、同時にリソースにアクセスしたりする一連の分散プロセスについて、どのプロセスが先に発生したかを知る方法はあるでしょうか？　この種の問題に答えるには、プロセスは同期したクロックを共有して、電子がネットワーク内を移動するのにかかる時間やCPUがタスクをスケジューリングするためにかかる時間などを、正確に知る必要があるでしょう。このようなことは、現実世界のシステムでは明らかに不可能です。

この問題について論じた有力な論文『Time, Clocks, and the Ordering of Events in a Distributed System（分散システムにおける時間、クロック、およびイベントの順序づけ）』では、論理クロックの概念が紹介されています。論理クロックは、システム内のイベントに番号を割り当てる方法で、その番号は実際の時間の経過には関係なく、分散システム内のノードによるイベントの処理に関係します。

論理クロックのアルゴリズムには、 Vector Clocks や Interval Tree Clocks などの多くのものがあります。

分散システムでの時間についての興味深い論説として、Justin Sheehyの “There Is No Now（”現在”は存在しない）” を推奨します。

分散システムでの時間とそれに関する問題は、理解すべき重要な概念の1つだということを強調したいと思います。 同時性という考えは捨てなければなりません。 これは、”絶対知”という古い信念に関係し、私たちは、絶対知というものが達成可能だと考えていました。物理法則によれば、光でさえ、ある場所から別の場所に行くためにはいくらかの時間がかかるので、光が私たちの目に届き、脳によって処理されるときには必ず、その光が伝達するものが何であっても、それは過去の世界の眺めなのです。この考えについて、Umberto Ecoが書籍『Inventing the Enemy（敵を発明する）』の”Absolute and Relative（絶対と相対）”の章で論じています。

FLPの概要

この記事の最後に、論文 Impossibility of Distributed Consensus with One Faulty Process(1つのプロセスが故障している場合の分散合意の不可能性） “に簡単に触れ、分散システムについて学んできたいくつかの概念を関連付けましょう。

この論文の要約は次の文で始まります。

合意の問題には非同期な複数のプロセスからなるシステムが関係し、それらのプロセスのいくつかには信頼性がないことがある。

つまり、私たちが扱うものは 非同期のシステム なので、処理速度にも、メッセージが他のプロセスに到達するために必要な時間にも、タイミングが仮定されません。それに、これらのプロセスの幾つかがクラッシュすることもあることが分かっています。

ここでの問題は、通常の技術用語では非同期とは、例えばRPCなどの要求を処理する方法を指すということです。その方法では、プロセス p がプロセス q に非同期要求を送信し、 q が要求を処理している間、 p が他のことをしています。つまり p は応答を待機しながら止まっているわけではありません。この定義は、分散システムの文献で使われているものとは全く異なっていることが分かります。そのことを知らなければ、このFLP論文の冒頭の文の意味さえも完全に理解することは非常に困難です。

この論文には、後に次のように書かれています。

本論文で示す驚くべき結果は、完全に非同期な合意プロトコルには、ただ１つのプロセスの死が通知されないことすら許容するものがないということだ。ここではビザンチン故障については考慮せず、メッセージシステムには信頼性があり、すべてのメッセージを正しくかつ正確に1回だけ配信すると仮定する。

つまり、この論文では前述した crash-stop モード（ fail-stop とも呼ばれる）のみが考慮されています。また、メッセージシステムに信頼性があるので、オミッション故障もありません。

最後に次の条件が加えられています。

最後に、ここではプロセスの死を検出する能力を前提条件とはしない。したがって、あるプロセスが別のプロセスが死んでいる（全く停止している）のか動作が非常に遅いだけなのかを知ることは不可能である。

つまり、故障検出機能さえ使用することができません。

要約すると、FLPの不可能性は、fail-stopプロセッサをもち、信頼性のあるメッセージシステムにアクセスでき、プロセスの死を検出することができない非同期システムに当てはまります。分散システムの様々なモデルに関する理論を知らなければ、このような詳細の多くを見落としたり、著者の意図とは全くかけ離れた解釈をしたりするかも知れません。

FLPの概要について、より詳しくは、ブログ記事 A Brief Tour of FLP Impossibility をご一読ください。

Marcos Aguileraの論文 “Stumbling over Consensus Research: Misunderstandings and Issues（合意の研究のつまずき：誤解と問題点）” の、分散システムに対する 不可能性結果 であることはFLPにとって何を意味するかについての論説を読むのも興味深いと思います（ネタバレ注意：停止性問題と同じレベルの 不可能性 ではありません）。

まとめ

お分かりのように、分散システムについて学ぶには時間がかかります。膨大なトピックがあり、細かい分野のそれぞれに大量の研究がなされています。しかも、分散システムの実装と確認は非常に複雑です。そこでミスを犯すと実装したものが予期せぬ環境で完全に崩壊してしまうような、隠れた数多くの箇所があります。

間違ったquorumを選択して、新しい巧みな複製アルゴリズムが重要なデータを失ったら？　とても保守的なquorumを選択してアプリケーションを不必要に低速化し、顧客とのSLAに違反してしまったら？　解決しようとしている問題が全く合意を必要とせず、結果整合性を甘受できるなら？　システムのタイミング仮定が間違っているのでは？　システムが使っている故障検出機能が基本システム属性に適合していないかも？　あれこれの小さなステップを避けてRaftのようなアルゴリズムを最適化することに決めて、結局は安全保証に違反してしまったら？　分散システムの基本理論を理解しなければ、このようなことや、もっと多くのことが起こる可能性があります。

もちろん、分散システムの仕組みを再発明したいわけではありませんが、このような膨大な文献と一連の問題のセットを前にして、どこから手を付ければよいのでしょう？　この記事の最初に書いたように、やみくもに論文を読んでも何にもなりません。FLP論文に関して前述したように、冒頭の文を理解するには様々なタイミングモデルについて知っていなければなりません。ですから、まずは次の2冊を読むことをお薦めします。

『Distributed Algorithms（分散アルゴリズム）』（著者：Nancy Lynch）。分散システムのバイブルのようなものです。前述した様々なモデルを扱い、それぞれにアルゴリズムのセクションがあります。

『Introduction to Reliable and Secure Distributed Programming（信頼性が高く安全な分散プログラミングへの入門）』（著者：Christian Cachinら）。優れた入門書であるとともに、多種の合意アルゴリズムについて触れられています。アルゴリズムを説明する擬似コードが豊富にあり、持っていると便利です。

他にも多数の良書がありますが、手始めとして、この2冊が良いと思います。より深く学びたくなったときのために、この記事で使用した参考文献のリストを揚げておきます。