分散システムの基礎完全ガイド：CAP定理から合意アルゴリズム、一貫性モデルまで

単一サーバー                  分散システム
+-----------+               +-----+  +-----+  +-----+
|  App + DB |    vs         | N1  |--| N2  |--| N3  |
+-----------+               +-----+  +-----+  +-----+
                                  \    |    /
                             ネットワーク（不安定）

ネットワーク分断発生！

  [Node A]  ----X----  [Node B]
  data=1                data=1

  ClientがNode Aにwrite(data=2)をリクエスト

  選択肢1 (CP): Node Bと同期不可 → リクエスト拒否（可用性を犠牲）
  選択肢2 (AP): Node Aだけ更新 → 不整合を許容（一貫性を犠牲）

if (Partition) then
    Availability vs Consistency
else
    Latency vs Consistency

厳密な一貫性（Strict）
    ↓
線形化可能性（Linearizability）
    ↓
順序一貫性（Sequential）
    ↓
因果一貫性（Causal）
    ↓
結果整合性（Eventual）

時間 →
Client A:  write(x=1) ------>
Client B:              read(x) → 必ず1を返す

実時間:     A:write(x=1)  B:write(x=2)
順序一貫性: B:write(x=2), A:write(x=1) も許可
           （すべてのノードがこの順序に同意すれば）

Aが投稿を作成 → Bがコメントを作成（因果関係あり）
  → すべてのノードで投稿がコメントより先に見える

Cが投稿作成 / Dが別の投稿作成（因果関係なし）
  → ノードごとに順序が異なる可能性あり

時間 →
Node A:  x=1 ......... x=1（変更伝播） → x=1
Node B:  x=0 ......... x=0 → x=1（若干の遅延後）
Node C:  x=0 ......... x=0 → x=1

           書込み
Client → [Leader] → 複製 → [Follower 1]
                        → [Follower 2]
                        → [Follower 3]
           読取り
Client → [Follower 1, 2, 3のいずれか]

# 半同期レプリケーション擬似コード
def write(data):
    leader.write(data)
    ack_count = 1  # リーダー自身
    for follower in followers:
        if follower.replicate(data):
            ack_count += 1
            if ack_count >= 2:  # 最低1つのフォロワー確認
                return SUCCESS
    return FAILURE

[Leader A] ←→ [Leader B] ←→ [Leader C]
    ↓              ↓              ↓
[Follower]    [Follower]    [Follower]

         write(x=1)
Client → [Node A] OK
       → [Node B] OK
       → [Node C] NG（障害）

W=2成功 → 書込み成功！

         read(x)
Client → [Node A] x=1
       → [Node B] x=1
       → [Node C] x=0（古い値）

R=2 → 最新値（x=1）を返す

hash(key) mod N = partition_number

key="user_123" → hash → 7 → 7 mod 3 = 1 → Partition 1
key="user_456" → hash → 2 → 2 mod 3 = 2 → Partition 2

Partition 0: A-F
Partition 1: G-M
Partition 2: N-S
Partition 3: T-Z

        0
       / \
     330   30
     /       \
   300        60
   |    Ring    |
   270        90
     \       /
     240   120
       \ /
       180

Node A: 0-90
Node B: 90-180
Node C: 180-270
Node D: 270-360

Node E追加（位置135） → Node Bの90-135だけNode Eに移動

Phase 1: Prepare
  Proposer → Acceptor: 「提案番号nを準備してください」
  Acceptor → Proposer: 「OK」（以前受け入れた値があれば一緒に伝達）

Phase 2: Accept
  Proposer → Acceptor: 「提案番号n、値vを受け入れてください」
  Acceptor → Proposer: 「受入済」（過半数が受入れれば合意完了）

時間 →
           Term 1          Term 2
Follower: [Heartbeat]... [Timeout!] → Candidate
Candidate: 自分に投票 + 他ノードにRequestVote
           過半数得票 → Leader当選！

Leader:   [Heartbeat]→[Heartbeat]→[Heartbeat]→...

# Raftリーダー選出擬似コード
class RaftNode:
    def __init__(self):
        self.state = "follower"
        self.current_term = 0
        self.voted_for = None
        self.election_timeout = random(150, 300)  # ms

    def on_timeout(self):
        self.state = "candidate"
        self.current_term += 1
        self.voted_for = self.id
        votes = 1  # 自分自身

        for peer in self.peers:
            if peer.request_vote(self.current_term, self.log):
                votes += 1

        if votes > len(self.peers) // 2:
            self.state = "leader"
            self.send_heartbeats()

Client → Leader: write(x=5)

Leader Log: [Term1:x=3] [Term1:y=7] [Term2:x=5]
                                        ↓ AppendEntries
Follower1: [Term1:x=3] [Term1:y=7] [Term2:x=5] OK
Follower2: [Term1:x=3] [Term1:y=7] [Term2:x=5] OK
Follower3: [Term1:x=3] [Term1:y=7] （ネットワーク遅延）

過半数（3/5）複製完了 → コミット！ → クライアントに応答

Phase 1: Prepare（投票）
  Coordinator → Participant A: 「コミット可能？」
  Coordinator → Participant B: 「コミット可能？」
  A → Coordinator: 「Yes」
  B → Coordinator: 「Yes」

Phase 2: Commit（実行）
  Coordinator → A: 「コミット！」
  Coordinator → B: 「コミット！」

Phase 1: CanCommit
Phase 2: PreCommit（タイムアウト設定）
Phase 3: DoCommit

注文作成Saga:

T1: 注文作成 → T2: 決済処理 → T3: 在庫差引 → T4: 配送開始
                     ↓ 失敗！
C2: 決済取消 ← C1: 注文取消

# Saga Orchestrator擬似コード
class OrderSaga:
    steps = [
        ("create_order", "cancel_order"),
        ("process_payment", "refund_payment"),
        ("update_inventory", "restore_inventory"),
        ("arrange_shipping", "cancel_shipping"),
    ]

    def execute(self):
        completed = []
        for action, compensation in self.steps:
            try:
                getattr(self, action)()
                completed.append(compensation)
            except Exception:
                # 補償トランザクションを逆順実行
                for comp in reversed(completed):
                    getattr(self, comp)()
                raise SagaFailed()

ルール:
1. イベント発生時にカウンターをインクリメント
2. メッセージ送信時に自身のカウンターを含める
3. メッセージ受信時にmax(自身カウンター, 受信カウンター) + 1

Process A:  (1)→ (2)→ (3)────→ (6)
                       send     recv
Process B:       (1)→ (2)→ (4)→ (5)
                       recv     send

3ノード A, B, C

A: [1,0,0] → [2,0,0] → [2,0,0] Bに送信
B: [0,0,0] → [0,1,0] → [2,2,0] Aから受信 → [2,3,0] Cに送信
C: [0,0,0] → [0,0,1] → [2,3,2] Bから受信

def compare_vector_clocks(vc1, vc2):
    """ベクトル時計の比較"""
    less = False
    greater = False
    for a, b in zip(vc1, vc2):
        if a < b:
            less = True
        elif a > b:
            greater = True

    if less and not greater:
        return "BEFORE"      # vc1 < vc2
    elif greater and not less:
        return "AFTER"       # vc1 > vc2
    elif not less and not greater:
        return "EQUAL"
    else:
        return "CONCURRENT"  # 並行イベント！

HLC = (物理的時間, 論理的カウンター)

物理的時間が同じ場合、論理的カウンターで順序を決定
→ NTP誤差範囲内で因果関係を保証

Node A → 「生きてる？」 → Node B
Node A ← 「うん！」 ← Node B

... タイムアウト ...

Node A → 「生きてる？」 → Node B
Node A ← （無応答） ← Node B
→ Node B障害と判断

Phi(φ)値:
  φ = 1  → 10%の確率で障害
  φ = 2  → 1%の確率で障害
  φ = 3  → 0.1%の確率で障害

閾値（例：φ > 8）を超えたら障害と判断

1. Node AがNode Bにping
2. 応答なし → Node C, Dに「Bにindirect pingして」と依頼
3. C, DがBにping → 応答なしならBを疑い（suspect）
4. 一定時間後もまだ応答なしならBを除去
5. ゴシップでメンバーシップ変更を伝播

アーキテクチャ:
  - Leaderless、コンシステントハッシング
  - Quorum読取り/書込み（W + R > N）
  - ゴシッププロトコルでメンバーシップ管理
  - Last-Write-Wins競合解決
  - SSTable + Memtableストレージ

PACELC: PA/EL
  - 分断時：可用性優先
  - 正常時：低遅延優先

アーキテクチャ:
  - 全世界分散、強い一貫性
  - TrueTime API：GPS + 原子時計で時間不確実性区間を提供
  - Paxosベースのレプリケーション
  - 外部一貫性（External Consistency）を保証

TrueTime:
  TT.now() → [earliest, latest]
  不確実性区間は通常1-7ms

  トランザクションコミット時：
  1. タイムスタンプsを割り当て
  2. commit-wait：TT.after(s)がtrueになるまで待機
  3. 不確実性区間分だけ待機して順序を保証

アーキテクチャ:
  - コンシステントハッシング + 仮想ノード
  - Sloppy Quorum：障害時に他のノードが代わりに応答
  - Hinted Handoff：復旧後に元のノードにデータを引き渡し
  - Vector Clockでバージョン管理
  - Merkle Treeでアンチエントロピー