【ITニュース解説】Where Distributed Systems Complexity Comes From

システムエンジニアを目指す皆さんにとって、現代のITシステムは単一のコンピュータだけで動くことは稀である。複数のコンピュータが協力し合って一つの大きな仕事をする「分散システム」が主流となっている。しかし、この分散システムには、単一のコンピュータでは考えられないような根源的な複雑さが潜んでおり、それが開発や運用を難しくしている。この複雑さは主に「空間」「時間」「合意形成」という三つの問題から生じる。

まず、「空間」の問題から見てみよう。単一のコンピュータでは、全てのデータが同じメモリ空間にあり、書き込まれたデータはすぐに誰からでも参照できる。しかし、複数のコンピュータ、すなわち分散システムになると、データは複数の場所に散らばって存在する。どのコンピュータも全体のデータの一部しか持っていないため、「真実の全体」を把握するコンピュータは一つもないという状況が発生する。この問題を解決するために、「データの複製（レプリケーション）」と「データの分割（パーティショニング）」という技術が使われる。レプリケーションでは、データを複数のコンピュータに複製することで、一部のコンピュータが故障してもシステム全体が停止しないようにする。しかし、どのコンピュータがデータを書き込む権限を持つかという問題が生じる。全てのコンピュータが自由に書き込めると、同時に異なるデータが書き込まれてしまい、どのデータが正しいのか分からなくなる「競合」が発生する可能性がある。これを避けるために、一つの「リーダー」となるコンピュータだけが書き込みを許可され、他のコンピュータは「フォロワー」としてリーダーからの複製を受け取る「シングルリーダーレプリケーション」という方法がある。しかし、リーダーが故障した場合、新しいリーダーを選出するまでに時間がかかり、その間システムが停止する可能性がある。また、フォロワーのデータがリーダーよりも遅れている場合、古いデータを読み取ってしまう可能性もある。リーダーを複数設ける「マルチリーダーレプリケーション」や、リーダーを置かない「リーダーレスレプリケーション」といった方法もあるが、それぞれ異なる種類の障害や複雑さを持つ。次にパーティショニングは、データ量が単一のディスクに収まらなくなった場合に、データを複数のコンピュータに分割して保存する技術である。データを特定のキーの範囲で分割する方法や、ハッシュ値を使って均等に分割する方法があるが、どちらも特定の種類のデータアクセス（例：範囲検索）が遅くなったり、一つのクエリが複数のコンピュータに問い合わせる必要が生じたりするなどの課題がある。これらのレプリケーションとパーティショニングの組み合わせ方によって、分散システムの設計はさらに複雑になるのだ。

次に、「時間」の問題である。単一のコンピュータでは、プログラムの命令は厳密な順序で実行される。例えば、「A = 1」という行が実行された後でなければ、「B = A + 1」という行がAの正しい値を使って計算されることはない。これはコンピュータのハードウェアが順序を保証しているためだ。しかし、分散システムでは、異なるコンピュータがそれぞれ独自の時計を持っているため、厳密なグローバルな時計は存在しない。たとえNTP（ネットワークタイムプロトコル）で時計のずれを調整したとしても、ミリ秒単位のずれは避けられず、毎秒何千もの操作を処理するシステムではこのずれが問題となる場合がある。さらに、ネットワークはメッセージの送信順序を保証しない。あるコンピュータが「メッセージA」を送った直後に「メッセージB」を送ったとしても、受け取ったコンピュータでは「メッセージB」が先に届くこともあり得るのだ。このため、イベントが発生した正確な時刻を示す「壁時計時間」だけでは、どのイベントが先に起こったかを確実に判断することはできない。そこで、「論理時計」という考え方が登場する。これは、イベントの正確な時刻ではなく、イベント間の「因果関係」に注目する。もしイベントAがイベントBの原因であれば、AはBより先に起こったと判断できる。どちらも互いの原因でなければ、それらは並行して起こったとみなすのだ。最も基本的な論理時計は単純なカウンターだが、これでは並行したイベントと因果関係のあるイベントを区別できない。そこで、「ベクトル時計」が使われる。これは各コンピュータが他のコンピュータのカウンターも記録するもので、二つのイベントのベクトル時計を比較することで、因果関係があるのか、それとも並行に起こったのかを判断できる。しかし、システム内のコンピュータが増えるにつれて、各メッセージに付加するカウンターの数も増え、その管理が複雑になるという問題がある。このような時間の不確実性があるため、分散システムでは「整合性（コンシステンシー）」のモデルを選ぶ必要がある。「線形化可能性」は、あたかも全ての操作が単一のコンピュータで瞬時に実行されたかのように見える最も厳密なモデルである。「結果整合性（Eventual Consistency）」は最も緩やかなモデルで、書き込みが止まれば最終的には全ての複製が同じ状態になることを約束するが、いつそうなるとは言わない。厳密な整合性を追求すればするほど、システムの速度が落ちたり、一部が故障した際にシステム全体が利用できなくなったりする可能性が高まるため、どの整合性モデルを選ぶかは、システムがどこまで許容できるかのトレードオフとなる。

最後に、「合意形成（コンセンサス）」の問題である。これは、空間と時間の問題が積み重なって発生する、分散システムが直面する最も困難な課題と言える。例えば、分散システムにおいてどのコンピュータをリーダーに選出するか、二つのデータベースにまたがるトランザクション（一連の操作）を全て成功させるか、全て失敗させるかの判断、複数のクライアントが同じデータを同時にロックしようとする場合など、様々な場面でコンピュータ群が「一つの値」や「一つの決定」に合意する必要がある。問題は、互いに信頼できないかもしれないコンピュータ群が、メッセージの紛失や遅延が頻繁に発生するネットワークを介して、一つの決定に到達しなければならないという点である。理論上、非同期システム（メッセージがいつ届くか分からないシステム）において、もし一つのコンピュータが故障する可能性がある場合、決して間違った答えを出さない決定的なプロトコルでは合意形成を保証できないという「FLP原理」が知られている。しかし、現実世界では、このFLP原理の制約外にある、確率的に高い成功率で合意形成を実現するプロトコルが利用されている。代表的なものに「Paxos」や「Raft」がある。これらは「クォーラム（定足数）」と呼ばれる多数のコンピュータの合意を必要とし、ランダムなタイムアウトなどの仕組みを組み合わせることで、実際には合意形成を可能にしている。特にRaftはPaxosと同じ問題をより理解しやすいように、リーダー選出、ログ複製、安全性という三つの部分に分割して設計されており、分散システムの教科書にもよく登場する。これらのプロトコルは、システム全体の過半数のコンピュータが正常に動作していることを前提とするため、例えば5台のコンピュータで構成されるシステムでは、2台までの故障には耐えられるが、3台が故障するとシステムが書き込み操作を受け付けられなくなる。また、分散システムで複雑な操作を行う際には「分散トランザクション」という技術も使われる。二相コミットはその一例で、まず全ての参加者に準備を求め、その後で全員にコミットを指示する。この「準備」と「コミット」の間の期間に、もし調整役のコンピュータが故障すると、参加者がロックを保持したまま待機し続ける「デッドロック」のような状態に陥る可能性がある。これを改善するために三相コミットやSagaのような手法もあるが、それぞれ別の複雑さやトレードオフを伴う。

これらの「空間」「時間」「合意形成」の問題は、それぞれが独立して存在するのではなく、互いに深く関連し合って、分散システムの複雑さの根源となっている。最初に気づきやすいのは空間の問題である。例えば、古いデータが返されるといった現象は、データが複数の場所に複製されていることが原因であることが多い。時間の問題はもう少し気づきにくい。時計のずれやメッセージの順序入れ替わりが引き起こすバグは、一見すると空間の問題のように見えることもあるが、詳しく調べて初めて時間の問題だと判明することがある。そして合意形成の問題は、データが複数箇所に存在し、メッセージが予測不能な順序で届くという空間と時間の問題が重なって初めて、その本当の難しさが露呈する。分散システムで使われるベクトル時計、クォーラム、一貫性ハッシュ、リーダー選出、補償プロトコルといった様々な技術は、全て「複数のコンピュータが協力して一つの仕事を成し遂げるが、それぞれのコンピュータは自身のローカルな状態しか知らない」という根本的な課題に対する異なるアプローチなのである。分散システムの設計において、「レプリケーションで誰が書き込むかを決め」「パーティショニングでデータがどこに存在するかを決め」「時間で順序がどの程度重要かを決め」「合意形成でグループとして何を許容するかを決める」ことが、システム全体の振る舞いを決定する重要な意思決定となる。