designing-distributed-systems

分散システムの設計

実績のあるパターンと整合性モデルを使用して、スケーラブルで信頼性が高く、障害に強い分散システムを設計します。

目的

分散システムは、現代のクラウドネイティブアプリケーションの基盤です。正確性と可用性を維持しながらグローバルにスケールするシステムを構築するには、基本的なトレードオフ（CAP 定理、PACELC）、整合性モデル、レプリケーションパターン、耐障害性戦略を理解することが不可欠です。

このスキルを使用する場面

次の場合に適用します：

• 複数のサービスを含むマイクロサービスアーキテクチャを設計する場合
• 複数のデータセンターやリージョンにまたがってスケールする必要があるシステムを構築する場合
• ネットワーク分断時に整合性と可用性のどちらを優先するかを選択する場合
• レプリケーション戦略（シングルリーダー、マルチリーダー、リーダーレス）を選択する場合
• 分散トランザクション（サーガパターン、イベントソーシング、CQRS）を実装する場合
• 適切な整合性保証を備えた、分断に耐性のあるシステムを設計する場合
• サーキットブレーカー、バルクヘッド、リトライを使って耐障害性のあるサービスを構築する場合
• サービスディスカバリーとサービス間通信を実装する場合

コアコンセプト

CAP 定理の基礎

CAP 定理： ネットワーク分断が発生している分散システムでは、整合性（C）または可用性（A）のどちらかを選択します。分断耐性（P）は必須です。

Network partitions WILL occur → Always design for P

During partition:
├─ CP (Consistency + Partition Tolerance)
│  Use when: Financial transactions, inventory, seat booking
│  Trade-off: System unavailable during partition
│  Examples: HBase, MongoDB (default), etcd
│
└─ AP (Availability + Partition Tolerance)
   Use when: Social media, caching, analytics, shopping carts
   Trade-off: Stale reads possible, conflicts need resolution
   Examples: Cassandra, DynamoDB, Riak

PACELC： CAP を拡張し、通常時（分断がない場合）についても考慮します。

• 分断時： 可用性（A）または整合性（C）を選択します
• それ以外（通常時）： レイテンシー（L）または整合性（C）を選択します

整合性モデルの範囲

Strong Consistency ◄─────────────────────► Eventual Consistency
      │                    │                      │
  Linearizable      Causal Consistency     Convergent
  (Slowest,         (Middle Ground,        (Fastest,
   Most Consistent)  Causally Ordered)     Eventually Consistent)

強整合性（線形化可能性）：

• すべての操作が、順序付けられた一連の処理としてアトミックに行われるように見えます
• 読み取りでは常に直近の書き込みが返されます
• 用途：銀行口座の残高、在庫数、座席予約
• トレードオフ：レイテンシーが高くなり、可用性が低下します

結果整合性：

• 新たな更新がなければ、すべてのレプリカは最終的に収束します
• 用途：ソーシャルフィード、製品カタログ、ユーザープロフィール、DNS
• トレードオフ：古いデータが読み取られる可能性があり、競合解決が必要です

因果整合性：

• 因果関係のある操作が、すべてのノードで同じ順序で認識されます
• 用途：チャットアプリ、共同編集、コメントスレッド
• トレードオフ：結果整合性より複雑で、因果関係の追跡が必要です

有界陳腐化：

• 陳腐化の程度が時間またはバージョン数によって制限されます
• 用途：リアルタイムダッシュボード、リーダーボード、モニタリング
• トレードオフ：遅延を監視する必要があり、結果整合性より複雑です

レプリケーションパターン

1. リーダー・フォロワー（シングルリーダー）：

• すべての書き込みをリーダーに送り、フォロワーに複製します
• フォロワーが読み取りを処理します（負荷分散）
• 同期： フォロワーの ACK を待ちます（強整合性、レイテンシーは高め）
• 非同期： 待ちません（結果整合性、データ損失の可能性あり）
• 用途：最も一般的なパターン。同期レプリケーションによる強整合性

2. マルチリーダー：

• 複数のリーダーが異なるデータセンターで書き込みを受け付けます
• リーダー同士でデータを複製します
• 競合解決が必要： 最終書き込み優先、アプリケーションによるマージ、ベクタークロック
• 用途：マルチデータセンター、書き込みレイテンシーの低減、地理的に分散したユーザー
• トレードオフ：競合解決が複雑になります

3. リーダーレス（Dynamo 形式）：

• 単一のリーダーを持たず、クォーラムに基づいて読み取りと書き込みを行います
• クォーラムルール： W + R > N（W＝書き込みクォーラム、R＝読み取りクォーラム、N＝レプリカ数）
• 例：N=5、W=3、R=2 → 強整合性（重複が保証されます）
• 用途：最大限の可用性、分断耐性
• トレードオフ：複雑さが増し、読み取り修復が必要です

パーティショニング戦略

ハッシュパーティショニング（コンシステントハッシング）：

• キー → Hash(Key) → パーティションの割り当て
• 均等に分散し、ノードの追加・削除時の再バランシングを最小限に抑えます
• 用途：ID によるポイントクエリ、均等な分散が重要な場合
• 例：Cassandra、DynamoDB、Redis Cluster

範囲パーティショニング：

• キーの範囲をパーティションに割り当てます（A-F、G-M、N-S、T-Z）
• 範囲クエリと順序付きデータに対応します
• リスク：データに偏りがある場合、ホットスポットが発生する可能性があります
• 用途：時系列データ、リーダーボード、範囲スキャン
• 例：HBase、Bigtable

地理的パーティショニング：

• 場所ごとにパーティション分割します（US-East、EU-West、APAC）
• 用途：データのローカリティ、GDPR への準拠、低レイテンシー
• 例：Spanner、Cosmos DB

レジリエンスパターン

サーキットブレーカー：

[Closed] → Normal operation
   │ (failures exceed threshold)
   ▼
[Open] → Fail fast (don't call failing service)
   │ (timeout expires)
   ▼
[Half-Open] → Try single request
   │ success → [Closed]
   │ failure → [Open]

• 障害の連鎖を防ぎます
• タイムアウトを待つのではなく、すばやく失敗させます
• references/resilience-patterns.md を参照してください

バルクヘッド分離：

• リソース（スレッドプール、接続プール）を分離します
• 1 つのパーティションの障害がほかに影響しません
• 船の区画が船全体の浸水を防ぐ仕組みに似ています

タイムアウトと再試行：

• タイムアウト： 期限を設定し、超過した場合はすばやく失敗させます
• 再試行： ジッターを加えた指数バックオフを使用します
• 冪等性： 安全に再試行できることを確認します（重要）

レート制限とバックプレッシャー：

• サービスを過負荷から保護します
• トークンバケット、リーキーバケットアルゴリズム
• バックプレッシャー：上流に処理を遅らせるよう通知します

トランザクションパターン

Saga パターン：

• サービス間の分散トランザクションを調整します
• 分散 2PC（二相コミット）は使用しません

コレオグラフィー： サービスがイベントに反応します

Order Service → OrderCreated event
Payment Service → listens → PaymentProcessed event
Inventory Service → listens → InventoryReserved event
(Compensating: if payment fails → InventoryReleased event)

オーケストレーション： 中央コーディネーター

Saga Orchestrator:
1. Call Order Service
2. Call Payment Service
3. Call Inventory Service
(If step fails → call compensating transactions in reverse)

イベントソーシング：

• 状態の変更を不変のイベントとして保存します
• イベントを再生して状態を再構築します
• 監査証跡、タイムトラベル、デバッグに対応します
• トレードオフ：クエリの複雑さ、スナップショットによる最適化

CQRS（コマンドクエリ責務分離）：

• 読み取りモデルと書き込みモデルを分離します
• 書き込みモデル：正規化され、トランザクションに対応
• 読み取りモデル：非正規化され、キャッシュされ、最適化済み
• 用途：読み取りと書き込みのパターンが異なる場合、読み取りと書き込みの比率が高い場合（10:1 以上）
• イベントソーシングと併用されることがよくあります

サービスディスカバリー

クライアントサイドディスカバリー：

• クライアントがサービスレジストリ（Consul、etcd、Eureka）に問い合わせます
• クライアントが負荷分散を行い、サービスを直接呼び出します
• メリット：プロキシのオーバーヘッドがありません
• デメリット：クライアントが複雑になります

サーバーサイドディスカバリー：

• クライアントがロードバランサーを呼び出します
• ロードバランサーがレジストリに問い合わせ、ルーティングします
• メリット：クライアントがシンプルになります
• デメリット：ロードバランサーが単一障害点になります

サービスメッシュ：

• サイドカープロキシがディスカバリー、ルーティング、再試行、サーキットブレーカーを処理します
• 例：Istio、Linkerd
• メリット：通信ロジックをサービスから切り離せます
• デメリット：運用が複雑になります

キャッシュ戦略

キャッシュアサイド（遅延読み込み）：

Read:
1. Check cache → hit? return
2. Miss? Query database
3. Store in cache, return

ライトスルー：

Write:
1. Write to cache
2. Cache writes to database synchronously
3. Return success

ライトビハインド（ライトバック）：

Write:
1. Write to cache
2. Return success
3. Cache writes to database asynchronously (batched)

キャッシュ無効化：

• TTL（有効期間）：一定時間後に期限切れにします
• イベントベース：データ変更時に無効化します
• 手動：更新時に明示的に無効化します

意思決定フレームワーク

整合性モデルの選択

Decision Tree:
├─ Money involved? → Strong Consistency
├─ Double-booking unacceptable? → Strong Consistency
├─ Causality important (chat, edits)? → Causal Consistency
├─ Read-heavy, stale tolerable? → Eventual Consistency
└─ Default? → Eventual (then strengthen if needed)

レプリケーションパターンの選択

├─ Single region writes? → Leader-Follower
├─ Multi-region writes + conflicts OK? → Multi-Leader
├─ Multi-region writes + no conflicts? → Leader-Follower with failover
└─ Maximum availability? → Leaderless (quorum)

パーティショニング戦略の選択

├─ Need range scans? → Range Partitioning (risk: hot spots)
├─ Data residency requirements? → Geographic Partitioning
└─ Default? → Hash Partitioning (consistent hashing)

クイックリファレンステーブル

CAP/PACELC システム比較

システム	パーティション時	それ以外（通常時）	用途
Spanner	PC	EC（強整合性）	グローバル SQL
DynamoDB	PA	EL（結果整合性）	高可用性
Cassandra	PA	EL（調整可能）	ワイドカラムストア
MongoDB	PC	EC（デフォルト）	ドキュメントストア
Cosmos DB	PA/PC	EL/EC（5 段階）	マルチモデル

整合性モデルのユースケース

ユースケース	整合性モデル
銀行口座の残高	強整合性（線形化可能）
座席予約（航空会社）	強整合性（線形化可能）
在庫数	強整合性または有界整合性
ショッピングカート	結果整合性
商品カタログ	結果整合性
共同編集	因果整合性
チャットメッセージ	因果整合性
ソーシャルメディアの「いいね」	結果整合性
DNS レコード	結果整合性

クォーラム構成

構成	W	R	N	整合性	ユースケース
強整合性	3	3	5	強整合性	銀行業務
バランス型	3	2	5	強整合性	デフォルト
書き込み重視	2	3	5	強整合性	ログ
読み取り重視	3	1	5	結果整合性	キャッシュ
可用性最大	1	1	5	結果整合性	分析

段階的な情報開示

詳細なリファレンス

特定のトピックを詳しく知りたい場合は、以下を参照してください。

• references/cap-pacelc-theorem.md - CAP と PACELC の詳細解説、および PACELC マトリクス
• references/consistency-models.md - 強整合性、結果整合性、因果整合性、有界陳腐化のパターン
• references/replication-patterns.md - リーダー・フォロワー、マルチリーダー、リーダーレスのレプリケーション
• references/partitioning-strategies.md - ハッシュ、範囲、地理的なパーティショニングの例
• references/consensus-algorithms.md - Raft と Paxos の概要（コンセンサスが必要な場合）
• references/resilience-patterns.md - サーキットブレーカー、バルクヘッド、タイムアウト、再試行、レート制限
• references/saga-pattern.md - コレオグラフィーとオーケストレーションの実用例
• references/event-sourcing-cqrs.md - イベントソーシングと CQRS の実装パターン
• references/service-discovery.md - クライアント側、サーバー側、サービスメッシュのパターン
• references/caching-strategies.md - キャッシュアサイド、ライトスルー、ライトビハインド、無効化

実用例

パターンを示す、完全で実行可能な例です。

• examples/consistent-hashing/ - 仮想ノードを使用した一貫性ハッシュの実装
• examples/circuit-breaker/ - 状態遷移を伴うサーキットブレーカーパターン
• examples/saga-orchestration/ - 補償トランザクションを使用した Saga オーケストレーター
• examples/event-sourcing/ - リプレイとスナップショットに対応したイベントストア
• examples/cqrs/ - 読み取りモデルと書き込みモデルを分離した CQRS
• examples/service-discovery/ - Consul ベースのサービスディスカバリーと登録

ASCII 図

複雑な概念を視覚的に表現した図です。

• diagrams/cap-theorem.txt - CAP 定理の判断ツリー
• diagrams/replication-topologies.txt - リーダー・フォロワー、マルチリーダー、リーダーレス
• diagrams/saga-flow.txt - Saga のコレオグラフィーとオーケストレーションのフロー
• diagrams/caching-patterns.txt - キャッシュアサイド、ライトスルー、ライトビハインド

他のスキルとの連携

関連スキル：

Kubernetes のデプロイについて：Pod のアンチアフィニティとサービスメッシュについては、kubernetes-operations スキルを参照してください
インフラストラクチャについて：分散システムのデプロイについては、infrastructure-as-code スキルを参照してください
データベースについて：レプリケーションの設定については、databases-sql と databases-nosql を参照してください
メッセージングについて：イベント駆動型アーキテクチャと Saga オーケストレーションについては、message-queues スキルを参照してください
モニタリングについて：分散トレーシングとモニタリングのパターンについては、observability スキルを参照してください
テストについて：分散システムの負荷テストについては、performance-engineering スキルを参照してください
セキュリティについて：mTLS とサービス認証については、security-hardening スキルを参照してください

一般的なパターン

マルチデータセンターパターン

1. Choose replication: Multi-leader or Leaderless
2. Partition data geographically
3. Implement conflict resolution (LWW, vector clocks, app-specific)
4. Monitor replication lag
5. Add circuit breakers between datacenters

イベント駆動型 Saga パターン

1. Define saga steps and compensating actions
2. Choose choreography (events) or orchestration (coordinator)
3. Implement idempotent handlers (retries safe)
4. Publish events with outbox pattern (transactional)
5. Monitor saga progress and timeouts

高可用性パターン

1. Use leaderless replication (N=5, W=3, R=2)
2. Partition with consistent hashing
3. Add circuit breakers for failing nodes
4. Implement read repair and anti-entropy
5. Monitor quorum health

ベストプラクティス

障害を想定して設計する：

• ネットワーク分断は発生します。常に分断耐性を考慮して設計してください
• タイムアウトと、指数バックオフを使った再試行を使用してください
• 連鎖障害を防ぐために、サーキットブレーカーを実装してください
• カオスエンジニアリングのシナリオ（ノードの分断、遅延の注入）をテストしてください

一貫性は慎重に選択する：

• デフォルトでは結果整合性を採用し、必要な箇所でのみ強化してください
• 強整合性には実際のコスト（レイテンシ、可用性）が伴います
• 中間的な選択肢として、期限付きの古さを許容する一貫性を使用してください

冪等性は不可欠です：

• 安全に再試行できる操作を設計してください
• 重複排除には一意のリクエスト ID を使用してください
• Saga の補償トランザクションには不可欠です

監視と可観測性を確保する：

• 相関 ID を使った分散トレーシング
• レプリケーション遅延とクォーラムの健全性を監視する
• サーキットブレーカーの状態変化をアラートで通知する
• Saga の進行状況と失敗を追跡する

戦略的にパーティション分割する：

• 均等に分散するにはハッシュパーティショニングを使用する
• 範囲クエリには範囲パーティショニングを使用する（ホットスポットを監視してください）
• コンプライアンスやレイテンシへの対応には地理的パーティショニングを使用する

すべてにバージョンを付ける：

• イベントスキーマは変更されるため、バージョン管理を使用してください
• サービスの互換性を保つために API のバージョン管理を行ってください
• 分散システムにおけるデータベーススキーマのマイグレーション

避けるべきアンチパターン

分散モノリス：

• 密結合されたマイクロサービス
• サービス間でデータベースを共有する
• 対策：サービスごとにデータベースを分け、非同期通信を使用する

二相コミット（2PC）の過剰使用：

• 遅く、ブロッキングが発生し、可用性が低下する
• 対策：分散トランザクションには Saga パターンを使用する

ネットワーク障害を無視する：

• ネットワークは信頼できると想定する
• 対策：必ずタイムアウト、再試行、サーキットブレーカーを追加する

あらゆる箇所で強整合性を使う：

• 不必要なレイテンシと複雑さが生じる
• 対策：デフォルトでは結果整合性を使用し、必要な箇所で強化する

競合解決戦略がない：

• マルチリーダー構成で競合に対処しない
• 対策：LWW、ベクタークロック、またはアプリ固有のマージ方法を選択する

キャッシュスタンピード：

• TTL の期限が切れると、すべてのクライアントがデータベースに問い合わせる
• 対策：確率的な早期期限切れ、リクエストの集約を使用する

トラブルシューティング

レプリケーション遅延が大きすぎる：

• データセンター間のネットワーク帯域幅を確認する
• リーダーの書き込みスループットを監視する
• 非同期レプリケーションまたはマルチリーダー構成を検討する

スプリットブレインのシナリオ：

• 分断中に複数のリーダーが選出される
• 対策：リーダー選出にはコンセンサス（Raft、Paxos）を使用する
• 二重書き込みを防ぐためにフェンシングトークンを実装する

ホットパーティション：

• データに偏りがある範囲パーティショニング
• 対策：ハッシュ要素を追加する、手動で再分配する、複合キーを使用する

Saga のタイムアウト／停滞：

• サービスが利用できず、Saga を完了できない
• 対策：自動ロールバックを伴う Saga のタイムアウトを実装する
• 手動対応用にデッドレターキューを用意する

競合解決の失敗：

• マルチリーダーの競合に対処できていない
• 対策：明確な解決戦略（LWW、マージ、手動）を実装する
• 競合率を監視し、急増時にアラートを通知する