第 16 章分散システム¶

まえがき — 1 台では足りない世界¶

「サーバを 1 台増やせば 2 倍の性能になる」と思っていませんか? 実際は遥かに難しい。ネットワークは落ちる、時計はずれる、メッセージは順序がバラバラに届く――1 台では起きなかった現象が、複数台で動かし始めた瞬間に襲ってきます。

それでも分散システムは避けられません。スケールするため、可用性を上げるため、地理的に分散したいため。現代のクラウドアプリはほぼすべて分散システムです。

🎯 章の目標

分散システム特有の難しさ（時計、障害、整合性）を理解する

レプリケーション、合意アルゴリズム、CAP 定理を語れる

障害モデル、冪等性、メッセージング保証を実務で使える

サーキットブレーカー、サーガなど障害対策パターンを知る

16.1 なぜ分散システムが難しいか¶

16.1.1 分散の 8 つの誤謬 (Fallacies)¶

L. Peter Deutsch が指摘した、開発者が陥りがちな誤解:

ネットワークは信頼できる
遅延はゼロ
帯域は無限
ネットワークは安全
トポロジーは変化しない
管理者は 1 人
転送コストはゼロ
ネットワークは均質

すべて誤り。これらを否定するところから設計が始まります。

16.1.2 「1 台」 vs 「複数台」¶

	単一マシン	分散システム
通信	関数呼び出し (ns)	ネットワーク (ms)
故障	全部止まる	一部だけ止まる (難しい)
時計	1 つ	バラバラ
順序	自然に保たれる	保証なし
デバッグ	簡単	地獄

「最初から分散にするな」が最大の格言。単純なモノリスで足りる規模では、分散の複雑さは本末転倒な負債になります。必要になってから慎重に分散化しましょう。

16.2 時間と順序¶

物理時計は 同期しない。NTP でも数 ms ずれます。これが分散の根本的難しさ。

16.2.1 Lamport 時計 (論理時計)¶

Leslie Lamport が 1978 年に提案。

各イベントに整数を割当てる:
- ローカルイベント: count++
- メッセージ送信: count を一緒に送る
- メッセージ受信: count = max(local, received) + 1

これで「因果関係」を保つ全順序が作れます。物理時刻ではなく 論理的な順序。

16.2.2 ベクトル時計¶

各ノードが他全ノードの時計を持つベクトル。

Node A: [3, 1, 2]
Node B: [3, 2, 2]

「\(V_a < V_b\) ⇔ \(a\) が \(b\) の原因」を厳密に判定できる。Riak, Voldemort で採用。

16.2.3 Hybrid Logical Clock (HLC)¶

物理時計 + 論理時計のハイブリッド。CockroachDB で採用。

16.2.4 Google TrueTime¶

GPS と原子時計で 時刻の不確実性区間 \((t_{min}, t_{max})\) を返す。Spanner の 外部一貫性 の鍵。

「時間の不確実性まで含めて」扱うことで、グローバル分散 DB を実現。

16.3 障害モデル¶

モデル	内容
Crash-stop	ノードが止まる (再起動しない)
Crash-recovery	止まって戻る
Omission	メッセージを取りこぼす
Byzantine	任意の振る舞い (悪意・故障)

ブロックチェーンでは Byzantine が前提です（誰が悪意ある参加者か分からない）。

16.3.1 FLP 不可能性 (1985)¶

「非同期 + 1 ノード故障で、決定的な合意は不可能」(Fischer, Lynch, Paterson)。

「完璧に正しい合意プロトコル」は理論上存在しません。実用ではタイムアウトや乱択でこれを回避します。

16.4 一貫性モデル¶

「読み手はどんな値を見ることを許されるか」を規定。

モデル	強さ	例
Strict / Linearizability	最強	グローバル時計の即時反映
Sequential	強	順序維持、時刻はずれてよい
Causal	中	因果関係のあるイベントは順序を保つ
Read-Your-Writes	弱	自分の書いたものは読める
Monotonic Reads	弱	一度新しい値を見たら古い値を見ない
Eventual	最弱	最終的に一致

「強い一貫性 = 遅い・可用性低い」のトレードオフ。

16.5 CAP 定理¶

graph TB
    C[Consistency<br/>一貫性]
    A[Availability<br/>可用性]
    P[Partition Tolerance<br/>分断耐性]

    CP[CP: Spanner, etcd<br/>HBase]
    AP[AP: Cassandra<br/>DynamoDB]
    CA[CA: 単一マシン DB<br/>分散では不可]

    C -.-> CP
    P -.-> CP
    A -.-> AP
    P -.-> AP
    C -.-> CA
    A -.-> CA

    style C fill:#bbdefb
    style A fill:#c5e1a5
    style P fill:#ffe0b2
    style CA fill:#ffcdd2

ネットワーク分断 (P) のとき、C と A を同時には満たせない。

実用ではネットワーク分断は前提。よって C と A のトレードオフ:

選択	例
CP	HBase, MongoDB (デフォルト), Spanner, etcd
AP	Cassandra, DynamoDB (eventual モード)

16.5.1 PACELC¶

CAP の拡張: 「分断時 (P) は C か A、それ以外 (E) は遅延 (L) と整合性 (C)」。

つまり「分断中じゃなくても、強い一貫性は遅い」。

16.6 レプリケーション¶

16.6.1 同期 vs 非同期¶

種類	内容	トレードオフ
同期	全レプリカ書込み完了で OK	安全だが遅い
非同期	マスターのみで OK	速いが障害でデータロス
Quorum	\(W + R > N\) で必ず最新	中間的

16.6.2 レプリケーション方式¶

Single Leader¶

書き込みは 1 ノード。 - PostgreSQL Replication - MySQL の半同期

Multi-Leader¶

複数ノードで書き込み。地理分散・オフラインクライアントに。

問題: 衝突解決が必要。

Leaderless¶

任意のノードに書き込み可能。Dynamo, Cassandra。

16.6.3 衝突解決¶

Last-Write-Wins (LWW): 単純だがデータ損失
ベクトル時計 + アプリ層マージ
CRDT (Conflict-free Replicated Data Type): 自動収束する代数構造

CRDT 例: G-Counter (Grow-Only Counter)¶

各ノードが自分の値だけ更新、合計を取る。マージ時に最大を取る。

協調編集 (Google Docs, Figma) や分散カウンタで活躍。

16.7 シャーディング (パーティショニング)¶

データを範囲・ハッシュで分割。

16.7.1 方式¶

方式	利点	欠点
レンジ	範囲クエリに強い	偏りやすい
ハッシュ	均等	範囲クエリ苦手
一貫性ハッシュ	ノード追加で再分配最少	実装複雑

16.7.2 一貫性ハッシュ (Consistent Hashing)¶

円周上にノードとキーをハッシュで配置:

   ┌── Node A
  / 
 ●  Key1 ─→ Node A (時計回り最初)
  \
   ●── Node B
   |
  Key2 ─→ Node B
   \
    ●── Node C

ノード追加・削除で 1/N のキーだけ移動。Cassandra, DynamoDB で採用。

16.7.3 仮想ノード¶

物理ノード 1 つに対し複数の仮想ノードを配置 → 偏りをならす。

16.7.4 ホットスポット問題¶

人気キー（バイラルなコンテンツなど）に偏る → ソルトやキー分割で回避。

16.8 合意アルゴリズム¶

複数ノードが「同じ値に合意する」プロトコル。

16.8.1 Paxos¶

Lamport が提案 (1989)。Proposer / Acceptor / Learner。難解で有名（論文タイトルが "The Part-Time Parliament" でジョークだった）。

Multi-Paxos でリーダー固定し効率化。Google Chubby, ZooKeeper の基盤。

16.8.2 Raft (2014)¶

「Paxos の理解しやすい代替」を目指して Ongaro & Ousterhout が設計。

構成¶

リーダー選出: タイマーランダム化で 1 人選ぶ
ログレプリケーション: リーダーがフォロワに伝播
安全性: リーダー完備性、コミット制限

stateDiagram-v2
    [*] --> Follower
    Follower --> Candidate: タイムアウト
    Candidate --> Leader: 過半数の得票
    Candidate --> Follower: 新リーダー検出
    Leader --> Follower: 上位タームを発見

    note right of Follower: リーダーからの<br/>ハートビートを待つ
    note left of Candidate: 自分に投票し<br/>他に投票要求
    note right of Leader: ログを伝播し<br/>ハートビート送信

採用: etcd, Consul, CockroachDB, TiKV。

16.8.3 Byzantine Fault Tolerance¶

悪意ある参加者を含む合意。

PBFT (Practical Byzantine Fault Tolerance)
Tendermint
HotStuff

\(3f + 1\) ノードで \(f\) ビザンチン故障に耐える。

ブロックチェーンでは PoW (Proof of Work) や PoS (Proof of Stake) と組合せ。

16.8.4 Gossip プロトコル¶

「伝染病的に」情報を拡散。各ノードがランダムに数人に伝える。

Cassandra のメンバーシップ
SWIM (障害検出)

スケールに強く、中心点なしの設計。

16.9 分散トランザクション¶

16.9.1 2 相コミット (2PC)¶

1. 準備フェーズ:
   コーディネータ → 全参加者「準備できる?」
   各参加者 → コーディネータ「yes / no」

2. コミット/中止フェーズ:
   全員 yes ならコミット、1 つでも no なら中止

問題: ブロッキング（コーディネータ障害で参加者が永遠に待つ）。

16.9.2 3 相コミット¶

ブロッキングを軽減するが、ネットワーク分断には弱い。

16.9.3 Paxos Commit¶

各シャードに Paxos を走らせ、コーディネータの単一障害点を解消。Spanner で採用。

16.9.4 Saga パターン¶

「長時間の業務トランザクション」を、補償アクション 付きの小さなステップに分割。

注文 → 決済 → 在庫予約 → 配送

失敗時の補償:
配送 ✗ → 在庫戻し → 決済キャンセル → 注文取消

完全な ACID は保てないが、最終整合性は実現できる。マイクロサービスでよく使う。

16.10 メッセージング保証¶

保証	内容	使いやすさ
At-most-once	重複なし、消失あり	簡単だが信頼性低い
At-least-once	必ず届く、重複あり	一般的
Exactly-once	1 度だけ	条件付きで実現可能

実は exactly-once は 理論的に分散では極めて難しい。実用では「at-least-once + 冪等性」で実現します。

16.10.1 冪等性 (Idempotency)¶

「何度実行しても結果が変わらない」性質。

# 非冪等
balance += 100   # 毎回増える

# 冪等
balance = 1000   # 何度実行しても 1000

リクエスト ID を持って「この ID は処理済み」と記録すれば、リトライしても 1 度しか反映されません。

16.10.2 キュー / Pub-Sub¶

ミドルウェア	特徴
Kafka	ログ指向、順序保証、リテンション
RabbitMQ	AMQP、ルーティング豊富
SQS / SNS	AWS マネージド
NATS, Redis Streams	軽量

16.10.3 Outbox パターン¶

DB トランザクションとメッセージ送信を整合させる:

DB トランザクション:
  - 注文を保存
  - 「メール送信せよ」を outbox テーブルに保存
  ↓ commit

別プロセス:
  outbox から読んでキューへ送信

「DB 書き込みとメッセージ送信を 2 相コミットしない」ための定石。

16.11 ストリーム処理¶

連続するイベントのリアルタイム集計。

フレームワーク	特徴
Kafka Streams	Kafka 統合
Apache Flink	低遅延、状態管理
Spark Streaming	バッチに近い
Apache Beam	抽象化レイヤ

16.11.1 ウィンドウ¶

タンブリング: 重ならない固定窓
スライディング: 重なる窓
セッション: 活動の途切れで区切る

16.11.2 イベント時間 vs 処理時間¶

「実際に起きた時刻」と「システムが受信した時刻」は違う。ウォーターマーク で「これより古いイベントは来ない」と宣言して窓を閉じる。

16.11.3 厳密 1 度処理¶

チェックポイント + トランザクショナル書込みで実現可能（Flink, Kafka）。

16.12 サービスメッシュとマイクロサービス¶

16.12.1 マイクロサービス¶

「1 つの大きなアプリを、小さなサービスに分割」。

メリット: 独立デプロイ、技術選択の自由、チーム分離。デメリット: 分散の難しさが全部降ってくる。

「最初はモノリス、必要に応じて分割」が定石。

16.12.2 横断的関心事¶

ロードバランス
サーキットブレーカー
リトライ
タイムアウト
認証
観測

これらを各サービスに書くのは面倒。サービスメッシュ (Istio, Linkerd) がサイドカープロキシで肩代わり。

16.12.3 通信プロトコル¶

REST: HTTP/JSON、シンプル
gRPC: HTTP/2 + Protobuf、高速
GraphQL: クライアント駆動

16.13 障害対策パターン¶

16.13.1 リトライ + 指数バックオフ + ジッタ¶

def retry_with_backoff(fn, max_retries=5):
    for i in range(max_retries):
        try:
            return fn()
        except TransientError:
            sleep(min(2**i + random(), 30))
    raise PermanentError

ジッタ（ランダム要素）は 同時リトライ集中 を防ぐため。

16.13.2 サーキットブレーカー¶

「連続失敗で短絡」し、回復を待つ。

状態:
  Closed (通常) → 失敗多発 → Open (即失敗)
                            ↓ 一定時間後
                          Half-Open (試す)
                            ↓ 成功
                          Closed

ダウンしたサービスへのリクエストを止めて、自分も道連れにならない。

16.13.3 バルクヘッド¶

部分障害が他を巻き込まないよう隔離。

スレッドプールを分ける
リソース上限を設ける

「1 つの船室が浸水しても、他は無事」の発想。

16.13.4 タイムアウト¶

必須。無限待ちはバグ。

response = requests.get(url, timeout=5)

16.13.5 冗長化と自動フェイルオーバ¶

アクティブ-アクティブ
アクティブ-スタンバイ
ロードバランサのヘルスチェック

16.13.6 カオスエンジニアリング¶

意図的にサーバを落として「壊れない設計」を確認。Netflix の Chaos Monkey が元祖。

「いつか起きる障害は、好きなときに起こす」発想。

16.14 観測とデバッグ¶

分散システムのデバッグは特に難しいので、観測が命綱。

分散トレーシング: OpenTelemetry, Jaeger, Zipkin
構造化ログ + トレース ID 伝播
メトリクス: Prometheus, Grafana
因果関係追跡: Vector Clock の現代版

16.15 セキュリティ¶

mTLS（相互認証 TLS）
ゼロトラスト（信頼ゼロから始める）
API ゲートウェイで集中認証
機密管理 (Vault, KMS)
ネットワークポリシー (Calico, Istio AuthorizationPolicy)

16.16 演習問題¶

ベクトル時計を 3 ノードでシミュレートし、独立イベントと因果イベントを区別せよ。
CAP の AP システムでネット分断時に「読みは古い値」を返す具体例を述べよ。
Raft でリーダー選出が起こる契機と、スプリットブレインを防ぐ仕組みを説明せよ。
一貫性ハッシュが「ノード追加で 1/N のキーだけ移動」となる理由を述べよ。
2PC のブロッキング障害シナリオを 1 つ示せ。
Saga で「注文 → 決済 → 配送」を構築し、決済失敗時の補償を書け。
At-least-once の上で exactly-once 相当を実現するために必要な「冪等性キー」の設計を提案せよ。
サーキットブレーカーが「半開」状態を持つ理由を説明せよ。
分散システムで「最初からマイクロサービスにするのは間違い」とされる理由を述べよ。
Chaos Monkey で意図的に落とすべきサービスとその目的を 3 つ挙げよ。

16.17 この章のまとめ¶

概念	役割
Lamport / Vector	論理時間
CAP / PACELC	トレードオフの法則
レプリケーション	可用性とスケール
合意 (Raft)	一貫性の確保
冪等性	リトライの安全
サーキットブレーカー	障害伝播防止
Saga	分散トランザクション
観測性	デバッグの命綱

「障害は前提」「時間は信用するな」「すべては最終整合」のマインドセットで設計しましょう。

16.18 次に読むもの¶

Kleppmann, Designing Data-Intensive Applications — 必読の決定版
Tanenbaum & van Steen, Distributed Systems
Lamport の論文集 (Paxos, Time, Clocks)
Ongaro & Ousterhout, In Search of an Understandable Consensus Algorithm (Raft 論文)
Site Reliability Engineering (Google)
Jepsen の分散 DB 検証レポート

🌟 メッセージ 分散システムは CS で最も難しい分野の 1 つ。「1 台で済むなら 1 台で」「最終整合で十分なら最終整合で」――シンプルさを選ぶ勇気が、複雑な分散を制する第一歩です。

第 16 章 分散システム¶