分散読み書きパス

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

概要

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

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

leaderless + quorum モード (Dynamo/Cassandra スタイル) を例に、書き込みリクエストの処理を追ってみましょう。

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 の場合、書き込み操作はすべてのレプリカを待ち受けます。そのため、1つのノードが障害を起こすと書き込みがブロックされます。W=1 の場合、処理速度は最速ですが、古いデータを読み取る可能性があります（R に依存します）。バランスの取れたポイントは通常、W + R > N です（R は読み込みquorum）。これにより、読み書きのquorum集合には必ず重複が生じます。

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

Raftの書き込みは強力なリーダーによる直列処理です。すべての書き込みはリーダーを経由し、リーダーはローカルログに書き込み、フォロワーの多数派へ複製し、コミットされ、ステートマシンに適用されます。quorumの調整ノブはなく、「一部のACKだけで成功とする」という概念はありません。コミットされていれば（確定的に永続化）、コミットされていなければ（後続のリーダーによって上書きされる可能性がある）のどちらかです。これはleaderless 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つの修復と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は、「1回の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, 最終整合性ウィンドウ