分散システム
Distributed System ・ ぶんさんしすてむ
複数のコンピュータが協調して一つの系として振る舞う仕組み。部分故障と遅延を抱える。
✦ 30秒で試す — 航海1台なら起きない「半分だけ壊れる」が、日常になるこの時点で、AがCについて確実に言えることは？予想してみる概要
分散システムは、ネットワークでつながった複数のコンピュータ（ノード）が協調して、利用者からは一つの系（システム）として見えるように振る舞う仕組みです。1台のマシンの中で完結する処理と違い、状態やデータが複数のノードにまたがって存在し、ノード同士はメッセージをやり取りしながら足並みを揃えます。「巨大な1台」ではなく「多数の小さな1台の集まり」で問題を解く、という設計思想です。
私たちが日常で触れる大規模サービスの裏側は、ほぼすべて分散システムです。数千万人が使う SNS、世界中に配信するストリーミング、止められない決済基盤は、1台のサーバでは処理量にも耐障害性にも到底足りません。そこで多数のサーバに負荷を分け、一部が壊れても全体は動き続けるように組みます。マイクロサービス、レプリケーション、シャーディングといった語彙は、いずれもこの分散という土俵の上で語られます。
分散システムが与えてくれるのは「規模（スケール）」と「可用性（落ちにくさ）」です。ただしそれは無料ではありません。1台では起きなかった「一部だけ壊れる（部分故障）」「メッセージが遅れる・消える・順序が入れ替わる（非同期）」「相手が死んだのか、遅いだけなのかが分からない」といった、分散ならではの難しさを丸ごと引き受けることになります。
なぜ生まれたか
かつては、性能が足りなければより高価で強力な1台のマシンに買い替える「スケールアップ（垂直スケーリング）」が基本でした。しかしこのやり方には二つの壁があります。第一に、1台のマシンの性能には物理的な上限があり、青天井には強くできません。第二に、どれだけ高価なマシンでも壊れるときは壊れ、その1台がサービス全体の単一障害点（そこが落ちると全部止まる急所）になってしまいます。
そこで、普通のマシンを大量に並べて横に足していく「スケールアウト（水平スケーリング）」が主流になりました。台数を増やせば処理能力は積み上がり、1台が壊れても残りで処理を続けられるので可用性も上がります。象徴的なのが、Google が2003年に発表した分散ファイルシステム GFS と、2004年の MapReduce の論文です。安価な市販のサーバは「いつもどれかが壊れている」ことを前提に、壊れてもソフトウェアの側で吸収する設計を示し、その後の Hadoop などの手本になりました。
ただし、台数を増やすことは「壊れ方の数」を増やすことでもあります。分散システムの研究で知られるレスリー・ランポートは1987年に「分散システムとは、存在すら知らなかったコンピュータの故障で、自分のコンピュータが使えなくなるシステムのことだ」と皮肉りました。分散システムは「もっと大きく、もっと落ちないように」という欲求への、ハードウェアではなくアーキテクチャによる回答であり、同時に新しい種類の難しさの始まりでもあったのです。
詳細
何が本質的に難しいのか
分散システムの難しさは、突き詰めると「離れた複数の場所の状態を、遅延と故障がある通信だけで揃えなければならない」ことに尽きます。1台の中なら共有メモリを見れば全体の状態が一目で分かりますが、分散では各ノードが自分の手元しか直接は見えず、ほかのノードの状況はメッセージ越しの間接的な情報でしかありません。しかもそのメッセージは、遅れることも、失われることも、順序が入れ替わることもあります。
とりわけ厄介なのが「ネットワーク分断（partition）」です。ノード自体は生きているのに、ノード間の通信だけが途切れる状況を指します。部分故障と非同期の通信が重なると、分散システムの設計はいつも同じ問いに行き着きます。「返事が来ない相手を、どう扱うか」です。
死んだのか、遅いだけなのか
ノード A がノード C に要求を送り、返事を待っているとします。返事が来ないとき、原因はいくつも考えられます。C が止まっている、要求がネットワークのどこかで消えた、C は受け取ったが処理が遅れている（ガベージコレクションの停止や過負荷）、C は処理を終えたが返事が途中で消えた、あるいは単に回線が混んでいる。A の手元にある情報は、どの場合も「送った」と「返事がまだない」の二つだけです。
A にできるのは、どこかで待つのをやめて「死んだとみなす」ことだけです。この見切りの線がタイムアウトで、ヘルスチェックや故障検知もすべて「一定時間返事がなければ死んだとみなす」という同じ原理で動いています。線を短く引けば、止まった相手にはすぐ気づけますが、遅いだけの相手まで死んだと誤判定します。誤判定された相手の処理は実は済んでいるかもしれないので、慌てて再送すると同じ処理が二重に走ります。線を長く引けば誤判定は減りますが、本当に止まったときに気づくのが遅れ、その間ずっと待たされます。正解の線はなく、平常時の応答時間の分布を見て「ここを超えたら異常」と決める設計判断になります。
下の部品で、C を止めたり線を引っぱって遅くしたりしてから要求を送り、A から見える帯を見比べてください。タイムアウトの線を左右に動かすと、過去の判定も塗り直されます。
まず「要求を送る」を押して、ふつうに返事が戻るのを見てください。そのあと C を押して止めるか、線の真ん中を下へ引っぱって遅くしてから、もう一度送ります。
ネットワークについての8つの誤謬
1台のプログラムの感覚で分散システムを作ると、ネットワークについて無意識の思い込みをしてしまいます。1994年ごろ Sun Microsystems のピーター・ドイッチュがまとめ、のちにジェームズ・ゴスリングが1項目を加えた「分散コンピューティングの8つの誤謬」は、その思い込みの一覧です。ネットワークは信頼できる、遅延はゼロ、帯域は無限、ネットワークは安全、構成（トポロジ）は変わらない、管理者は1人、転送のコストはゼロ、ネットワークは均質である――どれも1台の中では気にせずに済んだことばかりで、分散システムの障害の多くはこのどれかを前提にしたコードから生まれます。上の「死んだのか遅いのか」は、最初の二つ（信頼できる・遅延ゼロ）を捨てた瞬間に現れる問題です。
時計は信用できない
もう一つの落とし穴が時刻です。各ノードの時計は水晶発振器で進むので少しずつずれ、NTP で合わせても数ミリ秒から、条件が悪ければ数百ミリ秒の誤差が残ります。合わせた瞬間に時計が逆戻りすることさえあります。そのため「ノード X の時刻 10:00:00.120 の書き込みは、ノード Y の 10:00:00.100 の書き込みより後だ」と物理時刻で順序を決めると、実際の順序と食い違うことがあります。時刻の新しいほうを勝たせる（Last Write Wins）設計が、黙って更新を失う原因になるのはこのためです。
ランポートは1978年の論文で、物理時刻の代わりに「どのイベントがどのイベントの原因になりうるか」という因果の順序だけを数える論理時計を提案しました。順序が大事な場面では、時刻ではなくこうした論理的な番号（バージョン番号、単調に増えるカウンタ）を使うのが定石です。Google の Spanner（2012年）のように、原子時計と GPS で誤差の幅そのものを測り、その幅だけ待つことで物理時刻を安全に使う、という逆方向の解決もあります。
一貫性と可用性のトレードオフ
同じデータを複数ノードに複製していると、あるノードで更新した内容がほかのノードに伝わる前に読まれれば、古い値が返ります。全ノードが常に同じ最新値を返すこと（一貫性）と、どのノードもリクエストに応答すること（可用性）は、ネットワーク分断が起きた瞬間には両立できません。分断された向こう側と同期できない以上、「古いかもしれないが応答する」か「正しさを守るためにエラーを返す」かを選ぶしかないからです。この制約を定式化したのが CAP定理です。
分断が去った後も、レプリケーションされた複製の食い違いをどう収束させるかという問題が残ります。多くの分散データストアは、いったんズレを許し、時間が経てば全ノードが同じ値に落ち着くことを保証する結果整合性を採ります。厳密な同期をあきらめる代わりに、可用性と性能を取る割り切りです。
協調のための道具立て
ノード同士が一つの決定を共有するための仕組みが合意アルゴリズムです。Raft や Paxos は、一部のノードが故障しても過半数が生きていれば一つの値に合意できることを保証し、リーダー選出や設定情報の共有の土台になります。複数のノードが同じ資源を奪い合う場面では、分散ロックで「同時に一人」を作ります。
処理の直接呼び出しを避けてメッセージキューを挟めば、送り手と受け手を時間的に切り離し、相手が一時的に落ちていても後で処理を続けられます。ただし、上で見たように「返事が来ない」は「処理されていない」を意味しないので、失敗したら送り直すリトライと指数バックオフと組み合わせると、同じ処理が二重に届くことが避けられません。何度実行しても結果が変わらない冪等性を受け手に持たせるのは、このためです。
部分故障と観測可能性
分散システムでは「全部動いている」か「全部止まっている」の二択ではなく、「一部だけ壊れている」状態が常態です。ある1台の遅延が呼び出し元に連鎖し、返事を待つスレッドが積み上がってシステム全体を巻き込む「カスケード障害」は典型的な落とし穴です。返事が返らない相手への呼び出しを早めに諦めるタイムアウトや、壊れた依存先を一時的に切り離すサーキットブレーカーが欠かせないのは、止まった相手より遅い相手のほうが呼び出し元を長く縛るからです。
さらに、処理が多数のノードをまたいで流れるので、障害が起きても「どこで何が詰まったか」を1台のログを見るだけでは追えません。各ノードのログを集約し、システム全体の状態を可視化する監視、一つのリクエストが辿ったノード間の経路を串刺しで追う分散トレーシングは、分散システムの運用に必須の観測手段です。「壊れないシステム」ではなく「壊れても気づけて、壊れた部分だけで済むシステム」を目指すのが、分散システムとの現実的な付き合い方です。
試問
サーバ A がネットワーク越しにサーバ C へ要求を送り、返事を待つ画面です。C は押すと止まり（もう一度押すと戻る）、A と C を結ぶ線の真ん中を下へ引っぱると通信が遅くなります。下の帯には A から見えるもの（送った時刻と、返事が届いた時刻）だけが並び、A はタイムアウトの線（左右にドラッグできる）までに返事が来なければ「C は死んだ」と判断します。帯の各行は、待ちきると右端に真相が出ます。
まず「要求を送る」を押して、ふつうに返事が戻るのを見てください。そのあと C を押して止めるか、線の真ん中を下へ引っぱって遅くしてから、もう一度送ります。