システムデザイン完全ガイド ③｜データを保存する

db_set() { echo "$1,$2" >> db.txt; }          # 追記するだけ
db_get() { grep "^$1," db.txt | tail -1; }    # 最後の行が最新

              ┌───────────────┐
              │  [30] [70]    │  ← 内部ノード（キーとポインタのみ）
              └──┬────┬────┬──┘
        ┌────────┘    │    └────────┐
   ┌────▼────┐  ┌─────▼────┐  ┌─────▼────┐
   │10,20,25 │→ │35,50,60  │→ │75,90,99  │  ← 葉ノード（実データ）
   └─────────┘  └──────────┘  └──────────┘
        葉ノードは連結リストで繋がる（範囲検索が速い）

書き込み
   │
   ├─► [WAL に追記]（クラッシュ復旧用）
   │
   └─► [MemTable]  メモリ上のソート済み構造（スキップリスト等）
            │ 一定サイズで凍結してディスクへフラッシュ
            ▼
      [SSTable L0]  ソート済み・イミュータブルなファイル
            │ コンパクション（マージ）
            ▼
      [SSTable L1] → [L2] → [L3] ...  （下位ほど大きく、古い）

users(id, name, city_id)
cities(id, name, country)

users(id, name, city_id, city_name, country)  ← 都市名をコピー

-- インデックスなし: 1000 万行を全部読む（数秒）
SELECT * FROM users WHERE email = 'a@example.com';

-- email にインデックスがある: B-Tree を 3 段辿る（1 ms 未満）
CREATE INDEX idx_users_email ON users(email);

CREATE INDEX idx ON orders(user_id, status, created_at);

WHERE user_id = 1                                    ✅
WHERE user_id = 1 AND status = 'paid'                ✅
WHERE user_id = 1 AND status = 'paid' AND created_at > '2026-01-01'  ✅
WHERE user_id = 1 AND created_at > '2026-01-01'      △（user_id だけ使える）

WHERE status = 'paid'                                ❌ 左端が欠けている
WHERE created_at > '2026-01-01'                      ❌

CREATE INDEX idx ON orders(user_id, status) INCLUDE (total_amount);
-- SELECT total_amount FROM orders WHERE user_id=1 AND status='paid'
-- → インデックスだけで完結。劇的に速い

EXPLAIN ANALYZE SELECT * FROM orders WHERE user_id = 42 AND status = 'paid';

BEGIN;
SELECT balance FROM accounts WHERE id = 1 FOR UPDATE;  -- 行をロック
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
COMMIT;

UPDATE items SET stock = stock - 1, version = version + 1
WHERE id = 1 AND version = 5;
-- 更新行数が 0 なら誰かに先を越された → 再読み込みしてリトライ（409 Conflict を返す）

UPDATE accounts SET balance = balance - 100
WHERE id = 1 AND balance >= 100;   -- 読み取ってから書くのではなく、1 文で完結

行 id=1 の履歴
  ├ version1: balance=1000, xmin=100, xmax=105   （tx100 が作り、tx105 が消した）
  └ version2: balance=900,  xmin=105, xmax=null  （tx105 が作った、現行）

トランザクション 103 から見ると → version1（balance=1000）が見える
トランザクション 110 から見ると → version2（balance=900）が見える

tx1: A をロック → B を待つ
tx2: B をロック → A を待つ    → 永遠に進まない

強いトランザクション（複数行 ACID）が必要か？
 ├─ YES
 │   └─ データ量、IOPS、ワーキングセット、可用性要件は単一ノードに収まるか？
 │        ├─ YES → PostgreSQL / MySQL（+リードレプリカ）  ← まずここを疑え
 │        └─ NO  → Spanner / CockroachDB / TiDB（分散 SQL）
 │                  or アプリ側でシャーディング（Vitess 等）
 └─ NO
     ├─ アクセスは常に単一キー？ 低レイテンシが最優先？
     │    └─ DynamoDB / Redis / Cassandra
     ├─ 書き込みが極端に多い？ 時系列？
     │    └─ Cassandra / Bigtable / 時系列 DB
     ├─ 全文検索・ファセット・スコアリング？
     │    └─ Elasticsearch（※ 真実の情報源には使わない）
     └─ 多段の関係を辿る？
          └─ グラフ DB

プライマリキー = パーティションキー + クラスタリングキー

例: ユーザーのタイムラインを新しい順に取得したい
CREATE TABLE timeline (
  user_id   uuid,        -- パーティションキー: どのノードに置くかを決める
  post_time timestamp,   -- クラスタリングキー: パーティション内のソート順
  post_id   uuid,
  content   text,
  PRIMARY KEY ((user_id), post_time)
) WITH CLUSTERING ORDER BY (post_time DESC);

→ SELECT * FROM timeline WHERE user_id=? LIMIT 20;   ← 1 ノードへの 1 回のシークで完了

ユーザー・注文・決済 → PostgreSQL（トランザクションが要る）
セッション・カウンタ  → Redis（低レイテンシ）
商品検索             → Elasticsearch（全文検索）
イベントログ         → Kafka → S3 / BigQuery（分析）
画像・動画           → S3（オブジェクトストレージ）
レコメンド用の関係   → グラフ DB or 事前計算テーブル

       書き込み
          │
          ▼
    ┌───────────┐  レプリケーションログ
    │  リーダー  │────┬────────┬────────┐
    └───────────┘    ▼        ▼        ▼
                 [フォロワ1][フォロワ2][フォロワ3]
                     │        │        │
                     └────── 読み取り ──┘

ユーザーがプロフィールを更新 → 直後にページを再読み込み → 古い情報が表示される

1 回目の読み取り → レプリカ A（新しい）→ 「コメントが 5 件」
2 回目の読み取り → レプリカ B（古い）  → 「コメントが 3 件」← 消えた？！

実際: A「今何時？」→ B「3 時です」
表示: B「3 時です」→ A「今何時？」   ← 意味不明

1. リーダーの故障を検知（ハートビート途絶、通常 10〜30 秒）
2. 新しいリーダーを選出（最も進んだフォロワ、または合意アルゴリズム）
3. ルーティングを切り替える

シャード1: id 1〜1000万 / 日付 2024年
シャード2: id 1000万〜2000万 / 日付 2025年

shard = hash(user_id) % N

lookup_table: tenant_id → shard_id  （別途保存）

EU のユーザーデータは EU リージョンに（GDPR のデータ主権要件）

            0 / 2^32
               │
      NodeC ●──┼──● NodeA
           ╱   │   ╲
          │  (円)   │  ← key1 は時計回りで NodeA へ
          │        │
           ╲      ╱
      key2  ●────●  NodeB

     ネットワーク分断が発生！
  [ノードA] ✕✕✕ [ノードB]
     │              │
  書き込み要求    読み取り要求

  CP を選ぶ: B は「今は答えられません」とエラーを返す（可用性を捨てる）
  AP を選ぶ: B は古いデータを返す（一貫性を捨てる）

分断時: A or C
平常時: L or C

注文サービス: 注文を作成 ✅
決済サービス: 課金        ✅
在庫サービス: 在庫を減らす ❌（ここで失敗）

→ 課金だけ済んで商品が確保されていない。どうする？

       コーディネータ
   ① Prepare（準備できる？）
        ├──► 参加者A: 「はい」（ロックを取って待機）
        ├──► 参加者B: 「はい」
        └──► 参加者C: 「はい」
   ② Commit（全員 Yes なら）
        ├──► A: コミット
        ├──► B: コミット
        └──► C: コミット

【正常系】
注文作成 → 課金 → 在庫引当 → 配送手配

【在庫引当で失敗したら（補償トランザクション）】
注文作成 ← 注文キャンセル
課金     ← 返金
在庫引当 ✕

❌ 危険な実装:
   db.save(order)        ← 成功
   kafka.send(event)     ← ここで落ちる → イベントが失われる

❌ 逆順も危険:
   kafka.send(event)     ← 成功
   db.save(order)        ← ここで落ちる → 存在しない注文のイベントが流れる

【同一トランザクション内】
  BEGIN;
    INSERT INTO orders (...);
    INSERT INTO outbox (event_type, payload, created_at);   ← 同じ DB なので原子的
  COMMIT;

【別プロセス】
  outbox テーブルをポーリング or CDC（Debezium 等で WAL を読む）
  → Kafka へ publish → 送信済みマーク

配信保証の 3 段階:
  at-most-once  : 送って忘れる。失うかもしれない
  at-least-once : ACK が来るまで再送。重複するかもしれない ← 実用の基本
  exactly-once  : 保証範囲を限定すれば実現可能。外部副作用まで含むかを明記する

1. そもそも 1 つのサービス/DB のトランザクションに収まらないか？（境界の再設計）
   ↓ 無理なら
2. Outbox + イベント駆動 + 冪等な消費（結果整合）
   ↓ 補償が必要なら
3. Saga（オーケストレーション型）
   ↓ どうしても同期的な強整合が必要なら
4. 分散 SQL（Spanner / CockroachDB）に任せる
   ↓ 最後の手段
5. 2PC

すべてのノードは Follower として起動
  │ 一定時間リーダーからの心拍がない
  │ （150〜300ms は論文の例。RTT、処理時間、障害検知要件で調整）
  ▼
Candidate になり、term（任期番号）を +1 して投票を求める
  │ 過半数の票を得たら
  ▼
Leader になり、定期的に心拍を送る

※ タイムアウトをランダムにすることで、同時立候補（票の分裂）を防ぐ

クライアント → Leader
   Leader: 自分のログに追記
   Leader → 全 Follower に AppendEntries
   過半数が ACK → コミット確定 → クライアントに成功を返す
   （残りには後から伝わる）

ノード A: 「10 秒間リーダーです」というリースを取得
  → 10 秒間は他の誰もリーダーになれない
  → A が落ちても、10 秒経てば自動的に他が取れる（デッドロックしない）
  → A は 10 秒経つ前に更新（renew）し続ける

ロックを取るたびに単調増加する番号を発行する
  A がロック取得 → token=33
  A が停止
  B がロック取得 → token=34
  A が復活して書き込み: 「token=33 で書きます」→ ストレージ側が「34 を見たので拒否」