複製戦略

複数のマシンが同じデータの複製を保持する——どのようにしてそれらの整合性を保証するか? シングルリーダーは単純だが書き込みのボトルネックとなり、マルチリーダーは遠隔地での書き込みを許可するが競合が多発し、リーダーレスは一貫性を犠牲にして可用性を獲得する。一貫性、レイテンシ、耐障害性の間のトレードオフは、分散ストレージにおける最初の分岐点である。

シングルリーダー (Primary-Backup / Master-Slave)

すべての書き込み操作はリーダーを経由しなければならない。リーダーは書き込みを自身の WAL (Write-Ahead Log) に永続化し、その後、レプリケーション（同期または非同期）によってフォロワーへ伝播させる。

Client → Leader:   write(x=1)
Leader:             WAL への追加 → fsync → クライアントへ OK を返す (同期の場合)
                    → フォロワーへの非同期または同期レプリケーション
Followers:          new entries を受信 → ローカル状態に適用
Client → Follower: read(x) → 古い値を返す可能性がある (レプリケーション遅延のため)

複製方式

同期複製⁠：リーダーは少なくとも 1 つのフォロワーが確認を行うまでクライアントへの応答を待機する。これにより、少なくとも 1 つのフォロワーに最新データが存在することが保証され、リーダーがクラッシュした場合でも、そのフォロワーが引き継いでデータ損失を防ぐことができる。代償として、書き込みレイテンシは 2 ノード間の最も遅い fsync 時間になる。

非同期複製⁠：リーダーはフォロワーの確認を待たない。書き込みのレイテンシは最小限だが、リーダーがクラッシュした場合、未確認の書き込みは失われる (RPO > 0)。

準同期 (MySQL semisync)：少なくとも 1 つのフォロワーの確認を待つが、すべてのフォロワーを待たない。永続性とレイテンシのバランスを取る。

Read-Your-Writes 問題

非同期複製の場合、クライアントがリーダーへの書き込み直後にフォロワーから読み込むと、直前に書き込んだデータが読み取れない可能性がある。解決策：1) 書き込みに関連する因果関係を持つ後続の読み込みに対してリーダーへの読み込みを強制する; 2) フォロワーが現在適用されているログの位置を返し、クライアントは次の読み込みでトークンを指定する → フォロワーはトークン >= になるまで待機する。

マルチリーダー (Multi-Master)

すべてのノードが書き込みリクエストを受け付けることができ、他のノードへは非同期で複製される。利点：書き込みレイテンシが低い（リーダーを経由しない）、ネットワーク分断時に書き込みが可能（各分断内のノードが独立して書き込みを受け付ける）。代償：書き込み競合。

Node A: write(x=1) → 非同期複製 → Node B
Node B: write(x=2) → 非同期複製 → Node A
→ 競合発生! A は (x=1 → x=2) を確認、B は (x=2 → x=1) を確認
→ 競合解決が必要 (LWW, バージョンベクトル, CRDT — 03-02 を参照)

リーダーレス (Dynamo-style)

リーダーの役割がない——書き込みは複数のノードへ、読み込みも複数のノードから行われ、クォーラムによって整合性が保証される。

Dynamo (Amazon 2007) のモデル：

• N: データが複製されるノードの総数
• W: 書き込みの承認に必要なノード数 (コーディネーターを含む)
• R: 読み込みに関与するノード数 (コーディネーターを含む)
• R + W > N の場合: 読み書きのクォーラムには必ず重複が生じる → 少なくとも 1 つのノードに最新データが存在し、線形整合性が保証される

コーディネーター (任意——クライアントは直接、またはロードバランサー経由で任意のノードへアクセス可能):
  write(key, value, context):
    1. ベクトルクロックバージョンを生成
    2. N 個のレプリカへ並列送信
    3. W-1 個の確認を待機 (自身を含めて W 個)
    4. クライアントへ OK を返す

  read(key):
    1. N 個のレプリカから並列で読み込み (リクエスト送信)
    2. R 個の応答を待機
    3. ベクトルクロック比較により、バージョンが最新の value を選択
    4. 競合が見つかった場合 (バージョンが比較不可能) → 競合しているすべての sibling をクライアントへ返す (アプリケーション層で解決)
    5. 非同期修復 (read repair): コーディネーターが最新バージョンを遅れているノードへ書き戻す

Hinted Handoff

コーディネーターがすべての N 個のレプリカに到達できない場合、データをコーディネーター自身のローカルの "hint" に一時的に保存する。ターゲットレプリカが回復した際、コーディネーターは hint を転送する。これにより、ノード障害時にシステムが引き続き利用可能になる。

Sloppy Quorum vs Strict Quorum

厳密なクォーラムは、少なくとも W 個の "ターゲットレプリカ" への書き込みを要求する。Sloppy quorum: 合計で W 個のノードが確認を行えば（ターゲット以外のノードが引き受けても可）、可用性が確保される——ノード障害時に可用性が向上するが、R+W>N による整合性の保証が違反される可能性がある。

参考

• 論文⁠: "Dynamo: Amazon's Highly Available Key-value Store" (2007)
• Cassandra: cassandra.apache.org (Dynamo と BigTable のハイブリッド)
• MySQL: Group Replication (Paxos ベース、シングルリーダーの派生)

Keywords: リーダーベースのレプリケーション, マルチリーダー, リーダーレス, クォーラム, Dynamo, ヒントドハンドオフ, リードリペア, スロークォーラム