分散読み書きパス

1回のノード間読み書きで、quorum、WAL、Raftログ、一貫性ハッシュが同時に動作します。coordinatorからN個のレプリカへ、そしてread repairに至るこの完全なパスは、分散ストレージシステムの中心的なデータフローです。

概要

前述のレプリケーション戦略では、シングルリーダー/マルチリーダー/リーダーレスの3つのモードについて解説しました。コンセンサスプロトコルでは、Raftがどのようにして複数のノードでログシーケンスの合意形成を行うかを説明しました。一貫性ハッシュでは、データがどのように異なるノードに分散配置されるかを解説しました。しかし、1回のノード間読み書きにおいて、これら3つのプロセスは同時に発生します——書き込みリクエストが特定のノードに到達した後、どのようにレプリカを選択し、どのようにWALに書き込み、どのようにquorumを待ち、データの不整合が発生した場合に読み込みパスでどのように修復するか？ここでは、読み書きパスを一通り追ってみます。

分散書き込みパス: 1つの書き込みリクエストの旅

リーダーレス + quorum モード (Dynamo/Cassandra スタイル) を例に、1つの書き込みリクエストの経路を追います。

flowchart TD
    C["① Client → Coordinator<br/>write key=user:42<br/>N=3, W=2"]

    C --> HASH["② Coordinator 一貫性ハッシュ<br/>keyが3つのノードに<br/>[Node-A, Node-B, Node-C] 属することを算出"]

    HASH --> SEND["③ Coordinator 並列書き込み<br/>→ 3つのノードへ、W=2個のACKを待つ"]

    SEND --> NODE["各ターゲットノード上で:"]

    NODE --> WAL["a. WALへの追記<br/>→ fsync<br/>クラッシュリカバリ保証"]
    WAL --> MEM["b. MemTableへの書き込み<br/>(メモリ内の順序付き構造)"]
    MEM --> ACK["c. ACKを返す<br/>(バージョン番号/タイムスタンプ含む)"]

    ACK --> QUORUM{"④ Coordinator<br/>≥2個のACKを受信したか?"}
    QUORUM -->|"✅ W=2 を満たす"| SUCCESS["Clientへ成功を返す"]
    QUORUM -.->|"未受信"| STALE["残りのノードのデータは<br/>一時的に不整合"]

    classDef client fill:#e3f2fd,stroke:#1565c0
    classDef coord fill:#fff3e0,stroke:#ef6c00
    classDef node fill:#f3e5f5,stroke:#7b1fa2
    classDef done fill:#e8f5e9,stroke:#2e7d32
    class C client
    class HASH,SEND,QUORUM coord
    class NODE,WAL,MEM,ACK node
    class SUCCESS done

重要: W ≤ N は「可用性」と「一貫性」の調整ノブです。 W=N の場合、書き込み操作はすべてのレプリカを待ち受けます——ノードの障害が発生すると書き込みがブロックされます。W=1 の場合が最速ですが、古いデータを読み取る可能性があります (R に依存します)。バランスの取れた地点は通常、W + R > N (R は読み込みquorum) であり、読み書きの集合間に必ず交差点ができることを保証します。

Raftの書き込みパスとの違い

Raftの書き込みは強力なリーダーによる直列処理です。すべての書き込みはリーダーを経由し、リーダーはローカルログに書き込み、フォロワーの多数派へ複製し、コミットされ、ステートマシンに適用されます。quorumの調整ノブはなく、「一部のACKがあれば成功」という概念はありません——コミットされた場合（確定的に永続化）、またはコミットされなかった場合（後のリーダーによって上書きされる可能性あり）のいずれかです。これはリーダーレスquorumとは別の世界です：コンセンサスプロトコルの確実性 vs レプリケーション戦略の可用性優先。

分散読み込みパス: 正しいデータを読み取る方法

上記のシナリオと同じく、N=3, R=2 (読み込みquorum) とします。

flowchart TD
    C2["① Client → Coordinator<br/>read('user:42')"]

    C2 --> HASH2["② Coordinator 一貫性ハッシュ<br/>N=3個のレプリカノードを検出"]

    HASH2 --> SEND2["並列読み込みリクエスト、R=2個の応答を待つ"]

    SEND2 --> COMPARE["③ 2つの応答を受信<br/>Node-A: version=5<br/>Node-B: version=3"]

    COMPARE --> PICK["最新 version=5 を取得<br/>Clientへ返す ✅"]

    COMPARE --> REPAIR["④ read repair (非同期)<br/>Node-Bが古いことを検出<br/>バックグラウンドで version=5 を Node-B へプッシュ"]

    classDef client fill:#e3f2fd,stroke:#1565c0
    classDef coord fill:#fff3e0,stroke:#ef6c00
    classDef done fill:#e8f5e9,stroke:#2e7d32
    classDef repair fill:#f3e5f5,stroke:#7b1fa2
    class C2 client
    class HASH2,SEND2,COMPARE coord
    class PICK done
    class REPAIR repair

R + W > N の場合、読み書きのquorumには必ず重複が生じます⁠——読み込みは必ず最新の書き込みを確認できます。ただし、注意すべき点があります：coordinatorは少なくともR個の応答を受信した後、⁠バージョンを比較しなければなりません（最も速いものを選ぶのではなく）、そうでないと古いデータを読み取る可能性があります。

read repair vs hinted handoff: 2つの修復方法とタイミング

hinted handoff の核心思想：⁠書き込み時に妥協せず、ダウンしたノードへの書き込みデータを他場所に一時保存し、回復後に補完する。 これにより、一部のノードが一時的に到達不能でも、Wは依然として達成可能 (Nは不変) ——書き込み可用性が低下しません。Cassandraではデフォルトでhintを3時間保存し、期限を過ぎると破棄します。

sloppy quorum: 可用性を極限まで高める

上記で述べたquorumは strict quorum です：書き込みは、一貫性ハッシュで算出されたN個の「正しい」ノードに確実に到達しなければなりません。もしそのN個の中に障害が発生しすぎた場合、hinted handoffがあってもWを揃えることができません。

sloppy quorum はこれを緩和します：coordinatorは、Nに含まれない任意のノードを選択してWを補うことができます。データは一時的に「本来このデータを持つべきではないノード」に書き込まれ、正しいノードが回復した後に移動されます。これにより書き込み可用性がさらに向上しますが、その代償として読み込みは書き込んだ直後のデータを完全に認識できない可能性があります⁠（読み込みquorumがその「一時的なノード」をカバーしていない場合）——最終一貫性のウィンドウが大幅に拡大する可能性があります。

Dynamo論文ではstrictとsloppyの両方が記載されており、Cassandraではstrictがデフォルト（hinted handoffでフォールバック）、DynamoDBのon-demandモードはsloppyに近い動作をします。

ログからステートマシンへ: 分散環境におけるWALの二重の役割

Raft では、ログは「コンセンサスの担い手」です。単一ノードのストレージエンジンでは、WALは「永続性の担い手」です。実際のシステムでは、これら2つの層が相互作用します。

• Raftログは、どの操作が「クラスタレベルで確定したか」を管理し、障害復旧後にログを再生してステートマシンを再構築します。
• ローカルWALは、「単回のapplyがまだSSTableにフラッシュされていない間に失われないこと」を管理します——apply後、flush前に障害が発生した場合、WALから復元します。flush後、WALの対応部分は切り捨て可能です。
• これが、コンセンサスプロトコル: Raft で「committed → apply to state machine」と言いつつ、state machine が何かを詳しく展開していない理由です——state machine の内部には、この層の WAL + ストレージエンジンが存在します。

書き込み増幅: 分散化による既存の増幅の複雑化

単一ノードのLSMにおける書き込み増幅は、compaction（段階的な書き換え）に起因します。分散化により、さらに2つの層が加わります。

• ネットワーク増幅⁠: N=3の場合、1回の書き込みが3つのネットワークメッセージ（N個のレプリカ）になります。hinted handoff が加わるとさらに増加する可能性があります。
• Raft複製増幅⁠: Raftではまずログに書き込み（多数派）、その後ステートマシンにapply（ローカルWAL + MemTableへの書き込み）を行います。1つの論理書き込みが、2回のローカルfsync（ログfsync + WAL fsync）を引き起こす可能性があります——CockroachDB/Yugabyteの最適化は、これらを1回に統合することです。

したがって、分散システムの「書き込みスループット」は、単一ノードのストレージエンジンのスループットだけでなく、ネットワークとコンセンサスのオーバーヘッドも考慮に入れなければなりません。

トレードオフと失敗パターン

• W + R ≤ N の場合、最新の書き込みを読み取れない⁠: 読み書きのquorumが重複することを保証しない → 常に W + R > N を設定する。
• read repair の遅延⁠: 読み込みで検出されるが修復されない（非同期プッシュを忘れる）→ レプリカのバージョン差を監視し、定期的に反エントロピーを実行（次回の記事参照）。
• hinted handoff の蓄積⁠: ターゲットノードが長期間回復せず、hintsがcoordinatorのディスクを圧迫 → hintの有効期限を設定し、hintsキューの長さを監視する。
• fsync ポリシーの緩さ⁠: WALのバッチfsync中に障害が発生し、最後のバッチが消失 → 永続性の要件に応じてfsyncポリシーを決定する（Raftログ自体はすでに永続化されているため、ローカルWALは緩和できる）。

参考文献

• 論文⁠: "Dynamo: Amazon's Highly Available Key-value Store"(DeCandia 2007)——quorum + hinted handoff + sloppy quorum の起源

Keywords: quorum write, quorum read, N/W/R, strict quorum, sloppy quorum, read repair, hinted handoff, coordinator, WAL, fsync, Raft log vs WAL, write amplification, network amplification, consistent hashing + replication, 最終一貫性ウィンドウ