Chaos and Order

💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

なぜ今、分散システムなのか — 2026 年、もう避けられない

2015 年までは「分散システムは Netflix や Google がやるもの」だった。2026 年、3 人のスタートアップでも分散システムを扱う。

PostgreSQL 単一インスタンスで始めたアプリが 6 か月後に Read Replica を追加し、1 年後にシャーディングを検討する。
Kubernetes を使った瞬間 etcd (Raft) と API Server、Scheduler 間の Consensus に乗っている。
Kafka を導入すればパーティション・レプリケーション・オフセット・Exactly-Once 問題が始まる。
Cloudflare Workers + D1 + Durable Objects も本質的には分散 Raft クラスタ。
LLM Inference が複数 GPU・複数リージョンで走るとき、推論レベルでも分散合意が必要になる。

分散システムは「選択」ではなく「条件」だ。しかし業界でもっとも誤解される主題でもある。「うちは CP です」という言葉がいかに空虚か、読後に分かるはず。

Part 1 — なぜ分散は本質的に難しいか

分散コンピューティングの 8 つの嘘

1994 年 Peter Deutsch (当時 Sun) のリスト。30 年経っても有効。

ネットワークは信頼できる — パケットは消える。
レイテンシはゼロ — 光速は有限 (NY-Sydney RTT ~200ms)。
帯域は無限。
ネットワークは安全 — MITM、DNS ハイジャック、BGP ハイジャックは実在する。
トポロジは変わらない。
管理者は 1 人。
転送コストはゼロ — クラウド egress 請求が証明する。
ネットワークは均質 — TCP/IP の下に Ethernet、WiFi、衛星、5G が混在する。

分散システム論文の 99% はこれらが嘘であることから生じる問題を扱う。

2 つのプロセスは「今」に合意できない

単一マシンでは now() は明確。2 台では根本的に不確実。

NTP 同期はミリ秒の誤差を持つ。
VM は hypervisor によって停止されうる (Stop-the-World)。
原子時計と GPS を使う Google Spanner ですら 7ms の uncertainty interval を認めている。

ゆえに分散システムでは事象の順序は絶対時間ではなく論理時間で決まる。Lamport (1978) の洞察だ。

Part 2 — CAP 定理を読み直す

元の定義 (Brewer 2000 / Gilbert & Lynch 2002)

「ネットワーク Partition (P) 発生時、システムは Consistency (C) と Availability (A) のいずれか一つしか保証できない。」

3 つの誤解:

誤解 1: 「CP か AP かを選ぶ」

誤り。パーティションがない平時は C も A も両立できる。 CAP はパーティション発生時のトレードオフだけを述べる。Brewer 本人が 2012 年「CAP Twelve Years Later」で明言:

"The 'two of three' formulation was always misleading. In reality, the 'choice' is only relevant during partitions."

誤解 2: 「Consistency = ACID の C」

誤り。CAP の C は Linearizability (単一オブジェクト・単一操作があたかも一度に起きたように見える性質)。ACID の C は「制約違反なし」という別概念。

誤解 3: 「Availability = サービスが落ちない」

誤り。CAP の A は全リクエストが非エラー応答を受け取るという厳格な定義。99.99% 可用性とは違う。

PACELC — CAP が見落としたもの

Daniel Abadi (2010) の提案。Partition 時は A vs C、Else (平時) は Latency vs Consistency。

システム	Partition 時	平時
DynamoDB (既定)	PA	EL (低レイテンシ、弱一貫性)
Cassandra	PA	EL
MongoDB	PA/PC (設定)	EC
HBase	PC	EC
PostgreSQL (単体)	該当なし	EC
Spanner	PC	EC (TrueTime で L も相殺)

PACELC が重要な理由: 平時動作がユーザ体験の 99.99% を占める。 CAP だけ見て「うちは CP」と答えるのはその 99.99% を説明できない。

Consistency Models のスペクトラム

強い順:

Linearizable (Strong) — 外部観察者から単一マシンのように見える。コスト最大。
Sequential — 全プロセスが同じ順序で見る、ただし実時間順は保証しない。
Causal — 因果関係のある事象のみ順序保証 (Vector Clock ベース)。
Read-Your-Writes — 自分の書いたものは即読める。
Monotonic Reads — 見た値より古い値は見ない。
Eventual — 十分待てば収束する。

ほとんどのアプリは Linearizable まで不要。Causal + Read-Your-Writes で十分。

Part 3 — 時間と順序 — Lamport から HLC へ

Lamport Clock (1978)

Leslie Lamport「Time, Clocks, and the Ordering of Events in a Distributed System」— 分散コンピューティング史上もっとも重要な論文。

1. 各ノードは単調増加のローカルカウンタ L を持つ。
2. ローカルイベント: L = L + 1
3. メッセージ送信: L = L + 1, L をメッセージに添付
4. メッセージ受信: L = max(L_local, L_message) + 1

限界: Happens-Before を部分的にしか捉えない。Total Order は得られるが Causal Order は X。

Vector Clock (Fidge, Mattern 1988)

各ノードが全ノードのカウンタをベクトルで保持。

ノード A: [A=3, B=1, C=0]
ノード B: [A=2, B=4, C=0]

A から B へ送信時、A のベクトルを添付。
B は要素ごとの max で更新。

V1, V2 の比較:
- V1 <= V2 (全要素): V1 happens-before V2
- どちらでもない: concurrent

初期 DynamoDB、Riak、Cassandra の conflict detection に利用。欠点: ノード数増加でベクトルサイズが線形に増加。

HLC — Hybrid Logical Clock (2014)

物理時間 + 論理時間のハイブリッド。CockroachDB、MongoDB 4.0+、YugabyteDB が採用。

(wall_time, logical_counter)

NTP ドリフトに強く、人間が読めるタイムスタンプで、Causal Order を保持。

TrueTime — Google Spanner の秘密兵器 (2012)

各データセンタに原子時計 + GPS を配置。API:

TT.now() -> { earliest: t1, latest: t2 }  # 不確実区間
TT.after(t)  # t は確実に過去か?
TT.before(t) # t は確実に未来か?

Spanner コミット:

1. commit timestamp s を選ぶ (TT.now().latest 以降)
2. s が確実に過去になるまで待つ (commit wait) -- 通常 7ms 以下
3. 応答を返す

この commit wait により、全世界データセンタ規模の External Consistency を達成。ハードウェア (原子時計) に依存する唯一の本番分散 DB。AWS TimeSync (2023, μs 精度) が TrueTime 級の精度をカスタムハードウェアなしで提供しつつある。

Part 4 — Consensus — Paxos と Raft

FLP Impossibility (1985)

Fischer, Lynch, Paterson: 非同期ネットワーク + 1 プロセスでも故障しうる → 決定的合意アルゴリズムは不可能。

では Paxos/Raft はどう動くのか? タイムアウト + ランダム化で回避する。100% 決定的ではないが、実用的には収束する。

Paxos (Lamport, 1989 提出 / 1998 出版)

Leslie Lamport「The Part-Time Parliament」。ギリシャの島の議会の比喩で書いたためレビュアーに酷評され、出版が 9 年遅延。出版後も「理解不能」という悪名。

役割:

Proposer: 値を提案
Acceptor: 提案の受諾/拒否 (過半数が鍵)
Learner: 決定値を学習

2 phase:

Phase 1 (Prepare):
  Proposer -> Acceptor: 「提案番号 n を受けるか?」
  Acceptor -> Proposer: 「n が以前のどれより大きければ受諾。以前の受諾値を返す。」

Phase 2 (Accept):
  Proposer -> Acceptor: 「値 v で提案 n を受諾してほしい」
  (v は Phase 1 で見た最新受諾値か提案者の選択)
  Acceptor -> Proposer: 「受諾/拒否」

過半数受諾で値が確定。

悪名の理由:

Multi-Paxos、Fast Paxos、Generalized Paxos など変種過多。
論文スタイルがエンジニア向けでない。
実装時のエッジケースが論文に明示されない。

利用: Google Chubby、初期 ZooKeeper、Megastore、Spanner。

Raft (Ongaro & Ousterhout, 2014)

Stanford 博士課程の Diego Ongaro が「Paxos が難しすぎる」と作った合意アルゴリズム。論文タイトルは「In Search of an Understandable Consensus Algorithm」。

3 つのサブ問題に分解:

1. Leader Election

全ノードは Follower で開始。
リーダーからのハートビートを一定時間受け取れなければ Candidate に遷移、ランダムタイムアウト後に投票要求。
過半数獲得で Leader。
term 番号がハートビートに含まれ、スプリットブレインを防止。

2. Log Replication

全書き込みはリーダーのみ受ける。
リーダーがログに追加 -> AppendEntries RPC で Follower に伝播。
過半数が複製完了 -> コミット -> ステートマシンに適用。

3. Safety

Election Safety: 1 term に最大 1 人のリーダー。
Leader Append-Only: リーダーはログを上書きしない。
Log Matching: 同じ index/term なら、それ以前も同一。
Leader Completeness: コミット済みエントリは以降の全リーダーに存在。
State Machine Safety: 同じ index は全ノードで同じ値。

Raft 採用システム: etcd (Kubernetes)、Consul、TiKV/TiDB、CockroachDB、NATS JetStream、Redpanda、Cloudflare Durable Objects。

Paxos は「検証済み理論」、Raft は「実戦エンジニアリング」。2020 年代の新規システムの 90% は Raft。

Multi-Paxos、EPaxos、Flexible Paxos

Multi-Paxos: リーダー選出後、Phase 1 は 1 回のみ。以後 Phase 2 だけ。
EPaxos (Egalitarian): リーダーなしで全ノードが提案。地理分散に有利。
Flexible Paxos: Phase 1/2 のクォーラムサイズを分離。

Part 5 — トランザクション — 2PC, 3PC, Saga

2PC (Two-Phase Commit)

もっとも単純で、もっとも危険なトランザクションプロトコル。

Phase 1 (Prepare):
  Coordinator -> Participants: 「コミット可能?」
  Participants -> Coordinator: 「Yes / No」

Phase 2 (Commit):
  全 Yes -> 「Commit!」
  1 つでも No -> 「Abort!」

致命的欠陥: Coordinator が Phase 2 直前に死ぬと参加者がブロック。 手動介入なしでは復旧不可。本番で 2PC を使うのは XA トランザクションベースのレガシ (DB2、Oracle RAC) くらい。

3PC — Phase を追加してブロック回避を試みるが、ネットワーク分断では依然不整合が起こりうる。実務ではほぼ使われない。

Saga Pattern (Garcia-Molina & Salem, 1987)

長いトランザクションを複数のローカルトランザクション + 補償トランザクションに分解。

注文 -> 決済 -> 在庫引当 -> 配送

失敗時は逆順補償:
配送失敗 -> 在庫復元 -> 決済返金 -> 注文取消

2 種類:

Choreography: 各サービスがイベント発行/購読。中央調整者なし。
Orchestration: Saga Orchestrator が各ステップを呼ぶ。中央集権。

2020 年代の主流:

Temporal.io (Uber Cadence の OSS 化) — Workflow as Code 標準。
AWS Step Functions — サーバーレス Saga。
Netflix Conductor — Orchestrator 初期モデル。

Saga の限界: Isolation がない。 中間状態が外部に露出する。「semantic lock」で補うが完全ではない。

TCC (Try-Confirm-Cancel)

Alibaba がマイクロサービス向けに採用。リソース予約 (Try) + 確定 (Confirm) / キャンセル (Cancel) の 3 段階。

Part 6 — Event Sourcing + CQRS

Event Sourcing

「状態ではなくイベントの連続を保存する。」

[現在状態: 残高 $100]  -- 伝統的

[イベント: +$50, -$20, +$70]  -- Event Sourcing
-> 再生で $100

長所: 完璧な監査証跡、タイムトラベル、自然なイベント統合。短所: スナップショット必須、スキーマ進化が難しい、現在状態クエリが高コスト (CQRS 併用へ)。

CQRS

書き込みモデルと読み込みモデルを物理的に分離。

Command -> Write Model (Event Store) -> Event
                       -> Read Model (Materialized View)
                       -> Read Model (ElasticSearch)
                       -> Read Model (Redis)
Query   -> Read Models

強力だが複雑度が爆発。単純 CRUD に導入すると維持コストが激増。

主流: EventStoreDB、Kafka + ksqlDB、Axon Framework (Java)、Marten + PostgreSQL JSONB (.NET)。

Outbox Pattern — Exactly-Once の秘密

「DB コミット + メッセージ発行」を原子的に?

素朴な方法 (誤り):

1. DB コミット
2. Kafka 発行

2 が失敗すると不整合。逆順も同様。

Outbox Pattern:

BEGIN;
  INSERT INTO orders (...);
  INSERT INTO outbox (event_type, payload) VALUES (...);
COMMIT;

-- 別プロセスが outbox テーブルをポーリングして Kafka に発行
-- 発行成功で outbox 行削除 or フラグ更新

Debezium (Kafka Connect CDC) がこれを自動化する。PostgreSQL WAL -> Kafka にリアルタイムストリーミング。

Part 7 — Exactly-Once Semantics は存在するか

「Exactly-Once」の 3 つの意味

メッセージ送信 ExO: ネットワーク上で根本的に不可能 (Two Generals Problem)。
メッセージ処理 ExO: 重複検出 + 冪等性で可能。
最終効果 ExO: 消費者側の冪等性が鍵。

At-Least-Once + Idempotency = 実質的 Exactly-Once

Kafka 公式ガイドライン。Producer が重複送信しうると仮定し、Consumer を冪等に設計。

INSERT INTO processed_events (event_id, result)
VALUES ('evt-123', ...)
ON CONFLICT (event_id) DO NOTHING;

Kafka Transactional Producer (2017+)

producer.initTransactions();
producer.beginTransaction();
producer.send(record1);
producer.send(record2);
producer.commitTransaction();

パーティション・オフセットの原子的コミット + Consumer の isolation.level=read_committed で Exactly-Once。ただし Producer・Consumer・Broker 全ての設定一致が必要。

Part 8 — 実戦分散 DB — Spanner, CockroachDB, TiDB, YugabyteDB

Google Spanner

2012 年 OSDI 論文公開。
TrueTime による External Consistency。
Paxos + 2PC 併用 (パーティション内 Paxos、パーティション間 2PC)。
SQL + 分散トランザクション + 水平スケール — 2010 年代中盤まで「不可能」とされた組合せ。
2017 年 Google Cloud Spanner として商用化。

CockroachDB (2015)

「Spanner を OSS に。」元 Google エンジニアが創業。

Raft (Paxos の代わり)。
HLC (TrueTime の代わり — ハードウェア非依存)。
PostgreSQL wire protocol 互換。
Geo-partitioning — 行単位の地理配置。

2022 年 BSL ライセンス化でコミュニティの一部が反発。2024 年 Series F $278M 以降、本番採用が急増。

TiDB (PingCAP, 2016)

中国 PingCAP 創業。

MySQL 互換 (CockroachDB は PostgreSQL)。
TiKV (Raft) + TiDB (SQL) + PD (Placement Driver) の 3 層構造。
HTAP — 行ストア (TiKV) + 列ストア (TiFlash) 両方。
2024 年、PingCAP の売上が $100M を突破。

YugabyteDB (2016)

元 Facebook/Nutanix 出身。

Spanner-inspired + PostgreSQL 100% 互換。
Raft + HLC。
2.18 (2023) で真の read-your-writes をサポート。

Part 9 — ストリーミングの分散 — Kafka, Pulsar, Redpanda

Kafka

パーティション = 分散単位。
ISR (In-Sync Replicas) — リーダと同期した複製。
acks=all で内構性最大。
KRaft (2022 GA) — ZooKeeper 廃止、Raft でメタデータ管理。

Pulsar (Apache, Yahoo 2016 寄贈)

Compute/Storage 分離 (Broker と BookKeeper)。
ジオレプリケーションが 1 級市民。
Kafka より運用複雑だが、マルチテナンシが強力。

Redpanda (2019)

Kafka 互換を C++ で再実装。
ZooKeeper/KRaft 不要、内蔵 Raft。
Thread-per-core (Seastar) でレイテンシ激減。
fsync なしでも安全 (WAL + Raft で保証) と主張。

Part 10 — 実際の障害事例

1. Roblox 73 時間障害 (2021 年 10 月)

原因: Consul の BoltDB writeback contention により書き込み遅延 -> リーダー選出不可 -> 全面障害。教訓: KV ストアのバックグラウンド compaction が合意に影響する。

2. GitLab データ損失 (2017 年 1 月)

原因: エンジニアが primary で rm -rf を誤実行。5 つのバックアップ全てが機能せず (設定誤り/サイズ 0/古い)。教訓: 「バックアップがある」ではなく「復旧が検証済み」が重要。

3. Knight Capital 45 分で $440M 損失 (2012)

原因: デプロイ時、8 サーバ中 1 台だけ新コード適用。旧コードが無限買い注文。教訓: デプロイの原子性欠如 = 分散不整合 = 経済的災害。

4. Cloudflare 2022 Regex 障害

原因: 正規表現 1 つが CPU 100% -> 全エッジ停止。教訓: 分散システムの可用性は最弱リンクの原子的影響半径が決める。

5. AWS us-east-1 DynamoDB 2015

原因: メタデータサービス過負荷 -> テーブル一覧取得失敗 -> 連鎖障害。教訓: 「全てをサービス化」は分散化された単一障害点になりやすい。

Part 11 — 実務チェックリスト (12 項目)

CAP ではなく PACELC で語れ — 平時動作が 99.99%。
Exactly-Once は神話 — At-Least-Once + Idempotency を設計。
時計を信じるな — HLC/TrueTime ベース DB か Lamport Clock を採用。
新規に 2PC を入れるな — Saga か Outbox。
合意が必要なら Raft — 自作せず etcd/Consul/検証済ライブラリを使う。
リーダー選出に依存する系は「リーダー不在期間」を設計する。
クォーラムサイズを理解せよ — N=3 は 1 台障害のみ許容。
リトライは必ず指数バックオフ + ジッター。
分散キャッシュ無効化は設計段階で。
観測なしに分散なし — 分散トレース、メトリクス、ログの 3 点セット。
Chaos Engineering を導入 — パーティションを故意に注入。
データ復旧訓練を定期的に — GitLab は毎年起こりうる。

Part 12 — 10 大アンチパターン

「うちは CP です」と言う — CAP を誤解している証拠。
単一 Coordinator 依存 — SPOF 保証。
分散ロックでビジネスロジック保護 — 多くは冪等性で解決可能。
ローカル時計で順序決定 — NTP ドリフトがバグの温床。
トランザクションをマイクロサービス境界越し — Saga/Outbox で再設計。
リトライにタイムアウトなし — リトライ爆発で障害拡大。
分散モノリス — サービスは多いが全員一緒にデプロイ。
ローカルのみでテスト — 分散バグはレイテンシに住む。
Single Leader DB + Read Replica を「水平スケール」と呼ぶ。
「どうせ eventual consistency」で全ての不整合を正当化 — ユーザは「eventual」を理解しない。

Part 13 — 学習リソース

書籍: Designing Data-Intensive Applications (Kleppmann) — 現時点最良の入門書。
書籍: Database Internals (Petrov) — LSM/B-Tree/Consensus 内部。
書籍: Understanding Distributed Systems (Vitillo)。
論文: Lamport「Time, Clocks」/ Raft / Spanner OSDI 2012 / Bigtable / Dynamo 2007。
講義: MIT 6.824 Distributed Systems (YouTube 公開)。
Jepsen.io — CockroachDB/MongoDB/Redis などが「一貫性」をどう破るか実際に見られる。

おわりに — 分散システムは「哲学」である

Lamport の有名な定義:

"A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable."

分散システムとは、完全に制御できない世界で十分に信頼できる結果を作り出す技術だ。完璧はない。妥協だけがある。その妥協を明示的・意識的に行えば、ほぼ無限のスケールを扱える。

2026 年のエンジニアにとって分散システムの知識はもはや選択ではない。あなたが書く全てのコードは既に分散環境にある。ただ、多くはその事実に気付いていないだけだ。

次回予告 — 「データベース内部構造完全解剖」 — B-Tree, LSM, WAL, MVCC, Vacuum, Replication, Index 性能の秘密

本稿は分散「上」の話だった。次は分散「下」 — 単一 DB の心臓部 — B-Tree vs LSM、WAL、MVCC 内部、Vacuum/Compaction、Index 構造 (BRIN、GIN、GiST、HNSW)、Query Planner、レプリケーション内部、パーティショニング戦略。「なぜ DB は遅くなるのか?」への完全な答え — 次回。