分散型読み書きパス

ストレージリクエストは通常、ルーティング、レプリカ間やり取り、ローカルストレージ、応答の4層を経由する。パーティショニングは「誰に問い合わせるか」を決定し、レプリケーションプロトコルは「誰を待つか」を決定し、ローカル永続化は「単一ノードがどのように回復するか」を決定し、読み書きセマンティクスは「成功とは何を意味するか」を決定する。これらの責任がシステムを構成するが、すべてのシステムが一貫してハッシュリング、Raft、および同一のWALを使用する必要はない。

まず レプリケーション戦略 を参照し、リーダーありとリーダーレスを区別できる。本稿では、その差異を2つの独立したパスで説明する。

リーダーレス書き込み：コーディネーターは固定されたリーダーではない

クライアントは、あるノードをリクエストコーディネーターとして接続できる。コーディネーターはパーティションメタデータに基づいてキーのレプリカ集合を特定し、書き込みリクエストをレプリカに送信し、指定された数の成功応答を待つ。次のリクエストは異なるノードによってコーディネーションされる可能性があり、リーダーシップ選挙を完了する必要はない。

レプリカ数 N=3、書き込み確認数 W=2 とする。A、B が完了すれば成功を返すことができるが、C はまだ追いついていない可能性がある。これは、今回の操作が宣言された確認条件を満たしたことを意味するが、すべてのレプリカが同時に更新されたことを意味するものでも、同じキーへの並行書き込みがグローバルに順序付けられたことを意味するものでもない。

各レプリカは通常、変更をローカルログに記録し、メモリ構造を更新した後、ディスクデータファイルにフラッシュする。ACK がディスクへのフラッシュを待つかどうかは、ストレージエンジンと設定に依存しており、すべての実装を「すべての書き込みが最初に fsync を行う」という図式で一律に描くことはできない。ログはローカル回復を保証し、W はレプリカ確認の閾値を決定する。これら2つは組み合わせて分析する必要がある。

クォーラムの共通部分の導出

固定された N 個のレプリカ内で、書き込み集合のサイズを W、読み込み集合のサイズを R とする。2つの集合が交差しない場合、総サイズは最大でも N である。したがって、R + W > N は、それらが少なくとも1つのレプリカを共有することを保証する。

この集合の結論には、固定されたレプリカ集合、応答が要求された書き込み状態を本当に表していることなどの前提が必要である。これは完全な線形整合性レジスタアルゴリズムではない：

• 並行書き込みは、部分的なノードでそれぞれ成功する可能性があり、バージョンを比較または保持する方法を定義する必要がある。
• タイムアウトした書き込みは、少数のノードに伝播している可能性があり、後続の読み込みでそれが見えるかもしれない。タイムアウトはロールバックを意味しない。
• 応答バージョンが信頼できない物理クロックによって順序付けられている場合、数値が大きいからといって、ビジネスロジック上でより新しいことを意味するわけではない。
• スロークォーラム（Sloppy Quorum）が一時代替ノードへの書き込みを許可する場合、元のレプリカ集合での読み込みは、実際の書き込み集合と必ずしも交差しない。

したがって、R+W>N だけで「あらゆる状況で最新値が読める」と書いてはならない。バージョン順序、読み込み修復／書き戻し、失敗した書き込みとメンバー変更ルールについてさらに説明する必要がある。

失敗した書き込みが、2回のクォーラム読み込みで値が後退する仕組み

初期状態で A、B、C はすべてバージョン 0 を保持している。バージョン 1 の書き込みは A だけに到達し、W=2 の確認を得ずにタイムアウトした。その後、新しい書き込みはない。最初の読み込みで A、B を読み、より新しいバージョン 1 を取得する。最初の読み込みが完了した後、2回目の読み込みで B、C を読むと、バージョン 0 しか取得できない。両方の読み込みは R=2 を満たし、R+W>N であっても、「先に新しい値を見て、次に古い値を見る」ということが発生する。

from itertools import combinations

replicas = {"A": 1, "B": 0, "C": 0}  # 数字は順序付きバージョンであり、物理時間ではない
quorums = list(combinations(replicas, 2))
assert all(set(w) & set(r) for w in quorums for r in quorums)

def read(nodes):
    return max(replicas[node] for node in nodes)

assert read(("A", "B")) == 1
assert read(("B", "C")) == 0

# プロトコルを変更：最初の読み込みが返す前に、選択されたバージョンを多数派に書き戻す。
chosen = read(("A", "B"))
for node in ("A", "B"):
    replicas[node] = max(replicas[node], chosen)
assert all(read(nodes) == 1 for nodes in quorums)

集合論は機能していないわけではない。そのタイムアウトした書き込みは、W=2 の成功集合を形成しなかったのである。最初の読み込みがローカルバージョンを安定して観測可能な結果として扱いたい場合、追加の伝播ルールが必要である。上記の例では、多数派への書き戻し後、後続の各読み込みがそのバージョンに必ず接触する。

これは、Cassandra がブロッキング読み込み修復を使用して単調なクォーラム読み込みを維持する動機を説明するものである。具体的な保証は Read Repair を参照。このモデルは、単一値、順序付きバージョン、固定レプリカ、および新しい書き込みが発生しないシナリオのみを含む。これに基づいて「修復を1回追加する」ことで完全なマルチライター線形整合性アルゴリズムを概括することはできない。マルチライターでは、一意のバージョン生成、並行順序付け、およびすべての読み書きフェーズのプロトコル条件も解決する必要がある。

両方が多数派を読み取っても、値が後退するのはなぜか？

まず、書き戻しを無効にして AB、BC を順に読み取ると、1→0 を再現できる。リセットして書き戻しを有効にし、同じ読み取りを行うと、B は最初の読み取りの返却前にバージョン 1 を取得し、2回目の読み取りでもそれに遭遇できる。ここで安定するのは、すでに読み取られたバージョンである。失敗した書き込み自体は W 回の確認を得ておらず、それをこっそり成功した書き込みとしてカウントして共通部分の証明を適用することはできない。

リーダーレス読み取り：最も速い応答を奪って返すのではなく、バージョンを集める

コーディネーターは、読み込み整合性レベルを満たす応答を集め、システムルールに基づいてバージョンをマージする。あるバージョンが因果関係で他のバージョンをカバーしている場合、古いバージョンを破棄できる。2つのバージョンが並行している場合、ベクトルクロックは並行性を識別できるだけで、どちらのビジネス値が正しいかを凭空で決定することはできない。

例えば、2人のクライアントが同時にショッピングカートを変更する。1人は商品を追加し、もう1人は商品を削除する。集合の和集合を採用すると、削除された商品が再出現する可能性がある。最終タイムスタンプに基づく選択を採用すると、並行して追加された商品が失われる可能性がある。ストレージの読み取りパスは、競合解決 のビジネスルールと連携する必要がある。

読み込み修復は、遅延しているレプリカを発見した後にデータを補完できるが、読み込みをブロックする場合もあれば、バックグラウンドで実行される場合もあり、一律に非同期と呼ぶことはできない。Cassandra の動作は、対応するテーブル設定と読み取りパスによって決定される。Read Repair を参照。

リーダーレプリケーション：ログの順序を確定してから状態変化を実行する

Raft もまた、部分的なレプリカ確認を使用する。通常は多数派である。異なる点は、ログの一貫性、任期、選挙の制約、およびコミットルールが、コミットされるプレフィックスを共同で維持していることである。これは「すべてのレプリカの確認が必要」というプロトコルではない。

リーダーは現在の任期のログを多数派にレプリケートした後、プロトコルに従ってコミットを進める。以前の任期のエントリのコミットは、追加のルールによって制約される。committed と applied は2つの位置である。ログは確定しているが、ローカル状態マシンがまだそこに到達していない可能性がある。Raft 論文 および本リポジトリの Raft を参照。

読み込みリクエストも、「リーダーに送信したから」というだけで線形整合性があるとはみなせない。古いリーダーは、パーティション後に新しいリーダーが生成されたことを知らない可能性がある。安全な読み込みには、リーダーシップの確認、読み込み位置の決定、およびローカル状態マシンがその位置まで適用されるまでの待機が必要である。フォロワーへの読み込みを許可するとレイテンシを低減できるが、それが陳腐な読み込み、タイムスタンプに基づくスナップショット読み込み、または追加の同期条件を持つ強整合性読み込みのいずれであるかを明確にする必要がある。

コミット済み 43 なのに、なぜローカル読み取りでは 41 しか見えないのか

ローカルでログ 41 まで適用済みで、残高が 50 だとする。ログ 42 は +5、43 は -2 であり、これらはすでにコミットされているが、apply スレッドはまだ実行していない。強整合性読み取りは、プロトコルを通じて少なくとも 43 まで読む必要があることを決定する。現在の残高 50 を直接読み取ることはできない。commit_index=43 だけでは、メモリ状態が瞬時に 53 になるわけではない。

commands = {42: 5, 43: -2, 44: 100}
applied, balance, committed = 41, 50, 43

def read_if_ready(leadership_confirmed, read_index):
    if not leadership_confirmed or applied < read_index:
        return None  # この読み込みリクエストの条件でまだ返せない
    return balance

assert read_if_ready(True, 43) is None
while applied < committed:
    applied += 1
    balance += commands[applied]
assert read_if_ready(True, 43) == 53
assert read_if_ready(False, 43) is None
assert applied == 43 and balance != 153  # コミットされていない 44 は適用不可

モデルは、有効なリーダーシップ確認と読み込みバリアを入力として受け取るが、ReadIndex プロトコルは実装していない。実際のシステムでは、確認が現在の読み込みリクエストが依存する任期とプロトコルプロセスに属していることを保証し、対応するコミット前提を満たす必要がある。前回の成功したハートビートを永続的に有効な True としてキャッシュすることはできない。Raft の只読リクエストの条件は Raft 論文第 8 節 を参照。

1つの確認は「このノードが今回の読み込みの安全な位置を決定する資格があるか」を解決し、もう1つの待機は「ローカル状態マシンがすでにそこに到達しているか」を解決する。コンセンサスネットワークのレイテンシが非常に低くても、apply キューの蓄積は強整合性読み込みを遅らせる可能性がある。トラブルシューティングの際は、コミットから適用までの距離と実行時間の両方を見る必要がある。

Raft ログとローカル WAL：論理的役割は分離可能、物理的実装は統合可能

コンセンサスログは、クラスターが決定した操作シーケンスを保持し、ローカル WAL は、安定したデータファイルにまだ書き込まれていない状態をストレージエンジンが回復するのを助ける。状態マシンはメモリ構造、B-tree、LSM エンジン、またはその他の実装であり、すべてに WAL を重ねる必要はない。

システムが状態マシン層の WAL をスキップすることを選択した場合、スナップショット、永続化されたコンセンサスログ、および apply 進捗が回復に十分であり、ログの切り捨てが唯一の回復ソースを先に削除しないことを証明する必要がある。「Raft ログがある」という事実だけで、「ローカル永続化を自由に緩和できる」とは導出できない。

同様に、バッチ fsync、ログのマージ、および apply のバッチ処理は実装の選択である。1つのビジネス書き込みが何回のディスク同期に対応するかは、具体的なシステムで測定し、ソースコードで説明するものであり、すべての分散データベースに固定の倍数を適用してはならない。

ヒント、修復、および代替レプリカ

Hinted handoff は、ターゲットが一時的に到達不能な場合に、後で補完する書き込み情報を保持し、回復後に再生するものである。これは、期限と容量制限のある回復メカニズムであり、任意の一貫性レベルで利用可能な追加の正式なレプリカではない。Cassandra において hints がリクエストを満たすかどうかは、一貫性レベルに依存する。通常のクォーラムでは、hint を保存しただけで、それをターゲットレプリカの確認として自動的に扱うことはできない。Hints 文書 に明確な境界が示されている。

Sloppy quorum は、正常なレプリカ集合外の到達可能なノードを使用して、一時的なレプリカを引き受けることを許可する。これは読み書きの共通部分の前提を変更し、後続の戻しと修復が必要になる。これは Dynamo 論文における設計であり、DynamoDB の課金モデルから内部レプリケーションメカニズムを逆算してはならない。

システムアーキテクチャ図の読み方

1つのリクエストに沿って、以下を特定する。ルーティングの根拠は何か。誰が書き込みの順序を決定するか。ACK はログの追記、永続化、レプリケーション、または apply のいずれをカバーするか。リクエストがタイムアウトした場合、何が残り得るか。読み込みはどの境界まで見えるか。欠落したレプリカは誰が補完するか。

スループットは、レプリケーションネットワーク、ログ書き込み、状態マシン書き込み、圧縮マージ、およびバックグラウンド修復も考慮する。各層が拡大するリソースは異なる。次の記事 反エントロピーとデータ修復 で、バックグラウンド回復がこのループをどのように閉じるかについてさらに説明する。

参考

• Dynamo 論文：レプリカ間やり取りと回復設計
• Raft 論文：コミットと状態マシンの安全性
• Cassandra：Read Repair
• Cassandra：Hints

キーワード：quorum、N/W/R、coordinator、leader、committed、applied、WAL、read repair、hinted handoff