CAP と整合性モデル

整合性モデルは、クライアントが観察できる実行履歴の範囲を規定する。「新しいデータを取得する」ことを議論する前に、オブジェクト、操作、クライアントの順序、完了時間を明確にする必要がある。「可用性」を議論する前に、それが数学モデルにおける停止性質を指しているのか、それとも実際のサービスの成功率とレイテンシ目標を指しているのかを明確にする必要がある。

CAP：衝突は特定の障害モデルと保証の間に生じる

CAP における C は通常、原子性のある読み書きレジスタに対する線形整合性を指す。A は、障害のないノードに到達した操作が最終的に完了することを要求する。P は、モデルがノード間のメッセージがパーティションによって遮断されることを許容することを示す。A には統一されたミリ秒単位のレイテンシ上限はなく、単にエラーページを返せばサービス操作の完了契約を満たすわけではない。

任意の長さのネットワークパーティションを許容する場合、そのような C と A を同時に保証することはできない。これはアーキテクトが 2 つのアルファベットを自由に選べるという意味ではなく、また、すべての実際のネットワークがいつか特定の固定形式のパーティション必然的に発生するという意味でもない。Gilbert と Lynch：CAP の理論的および実践的視点

x が初期値 0 で、他の書き込みがない前提において、A での 1 への書き込みは成功しており、その後 B が読み取りリクエストを受信する。B はメッセージを通じて、「相手が書き込み 1 を完了した世界」と「相手が書き込みを行わなかった世界」を区別できないが、履歴に適合する回答を下さなければならない。永久に回復しないパーティションの中で、待ち続けることで停止要件を満たすことはできない。

システムは、過半数の側で一部の強い整合性操作を継続して完了させ、少数派の側で拒否または待機させることができる。また、特定のビジネスロジックに対して、ローカルでの更新を許容し、回復後にマージすることも可能である。CAP は、製品全体がすべてのインターフェースで同じアルファベットラベルを永久的に選択することを要求するものではない。

線形整合性：操作は呼び出しと戻り値の間に瞬時に有効になる

あるオブジェクトの操作履歴において、各完了した操作を、その呼び出しと戻り値の間の何らかの点に配置し、オブジェクトの仕様に従った順序実行が得られる場合、線形整合性を持つという。A が戻り値を返した後に B が呼び出しを行う場合、A は B より前に配置されなければならない。時間的に重複する操作は、任意の合法な順序で並べることができる。

例えば、write(x=1) が戻り値を返した後に read(x) が呼び出され、他の書き込みがない場合、読み取りは 1 を返さなければならない。読み取りと書き込みが重複している場合、古い値 0 または新しい値 1 のいずれを返しても合法であり、これは線形化点の位置に依存する。したがって、「読み取りは常に壁時計の意味での最新値を返す」という記述は正確ではない。

線形整合性は観察可能な動作に対する制約であり、必ずリーダーを使用したり、特定のネットワーク往復を経由したり、すべての物理レプリカが同一瞬間に適用を完了したりすることを要求するものではない。実装は、異なるレプリケーションおよび読み取りプロトコルを通じてこの動作を提供できる。

順序整合性：各クライアントの順序を保持し、クライアント間のリアルタイム順序を余分には保持しない

順序整合性は、オブジェクトのセマンティクスに適合し、各プロセス自身の操作順序を保持するグローバル順序が存在することを要求するが、異なるクライアント間のリアルタイムな完了関係によって生じる順序のみを保持することを要求しない。

例えば、クライアント A が x=1、x=2 と順に書き込み、クライアント B がその後に現実時間で 1 を読み取ったとする。この履歴だけを見れば、それは論理順序「書き込み 1、読み取り 1、書き込み 2」として解釈され、順序整合性を満たすが、2 回目の書き込み完了後の読み取りに対する線形整合性の要件に違反する。

これは現実のメッセージが時間を遡ることを意味するものではなく、また、任意の非同期レプリカでの読み取りが順序整合性を満たすことを意味するものでもない。同じクライアントがまず 2 を読み取り、次に 1 を読み取り、他の書き込みがない場合、その読み取り順序を保持する上記の単調書き込み履歴では説明できない。

定義を小さな履歴チェッカーに変換する

初期値が 0 のレジスタに対して、以下の 4 つの情報を記録する：クライアント、操作タイプ、書き込み値または読み取り結果、呼び出しと戻り値のイベント位置。ここでいう位置は、異なるマシンからの校正されていない壁時計時間で直接ソートしたものではなく、既知のイベントシーケンスからの位置である。各クライアントは未完了の操作を一度に 1 つだけ持ち、すべての記録は成功した戻り値を持つ。

チェック時には、まず操作を並べ替え、2 つのフィルターを実行する：順序が保持すべき順序関係を満たしているか。この順序で実行した際、各読み取りがレジスタの現在の値と一致するか。順序整合性は同クライアントの順序制約のみを追加し、線形整合性はすべてのクロスクライアントの非重複制約も追加する。

from dataclasses import dataclass
from itertools import permutations

@dataclass(frozen=True)
class Op:
    client: str
    kind: str
    value: int
    start: int
    end: int

def witness(history, linear=True):
    assert all(o.kind in ("W", "R") and o.start < o.end for o in history)
    # 教学用入力では、同一クライアントの呼び出しは直列化され、イベント位置に曖昧さがないことを要求する。
    for i, a in enumerate(history):
        for b in history[i + 1:]:
            if a.client == b.client:
                assert a.end < b.start or b.end < a.start
    edges = [(i, j) for i, a in enumerate(history)
             for j, b in enumerate(history)
             if a.end < b.start and (linear or a.client == b.client)]
    for order in permutations(range(len(history))):
        position = {op: rank for rank, op in enumerate(order)}
        if any(position[i] >= position[j] for i, j in edges):
            continue
        value = 0
        for i in order:
            op = history[i]
            if op.kind == "W":
                value = op.value
            elif op.value != value:
                break
        else:
            return order
    return None

stale = [Op("A", "W", 1, 0, 1), Op("A", "W", 2, 2, 3),
         Op("B", "R", 1, 4, 5)]
assert witness(stale, linear=False) == (0, 2, 1)
assert witness(stale, linear=True) is None

# 読み書きの重複：2 つの戻り値のいずれにも合法な解釈があるが、任意の値を返せるわけではない。
for result in (0, 1):
    overlap = [Op("A", "W", 1, 0, 5), Op("B", "R", result, 2, 3)]
    assert witness(overlap) is not None
assert witness([Op("A", "W", 1, 0, 5), Op("B", "R", 2, 2, 3)]) is None

# B が先に 2 を読み、次に 1 を読む場合、A の単調書き込み順序と整合する合法な全順序に収められない。
backward = stale[:2] + [Op("B", "R", 2, 4, 5), Op("B", "R", 1, 6, 7)]
assert witness(backward, linear=False) is None
assert witness([]) == ()

最初のグループは (0, 2, 1) を返す。これは B の読み取りを A の 2 回の書き込みの間に配置するものである。これは A のプログラム順序を保持しているが、現実には 2 回目の書き込みがすでに返却されたという事実を無視している。最後のグループでは、このような調整を許容しても解がない：読み取り 2 は書き込み 2 の後に配置する必要があり、その後の読み取り 1 は書き込み 2 の前に戻ることを要求するため、制約が環を形成する。

このチェッカーの並べ替え数は階乗で増加するため、少数の操作を含む小さな履歴の理解にのみ使用される。証人が存在すれば、その完全な履歴が選択された制約を満たすことが示される。チェックが通過しても、実装のすべての実行が正しいことを証明するものではない。実際のテストでは、タイムアウト後の結果不明、戻り値を待たない操作、オブジェクト仕様および履歴収集の誤差を処理する必要がある。特に、タイムアウトした書き込みを履歴から直接削除してはならない。それはすでに有効になっている可能性があるからである。Herlihy と Wing：線形整合性

同じ履歴において、どの順序が依然として成立するか？

「整合性があるかどうか」を、順序制約とレジスタの読み書きルールを同時に満たす操作の並べ替えが存在するかどうかという具体的な問題に書き換えることができる。以下では、A の 2 回の直列書き込みを保持し、B の読み取り区間と戻り値の変更を許可する。順序整合性の証人は履歴の合法な解釈であり、現実のイベントを過去に移動するものではない。制約を切り替える際、実際の時間軸は変更されない。

因果整合性：依存関係を見てから、それによって依存する結果を見る

A が記事を投稿し、B が記事を読んで返信する。返信は記事に依存する。観察者が返信を閲覧できる場合、システムは対応する因果的可視性の要件を満たし、記事のバージョンを見ずに返信だけを見ることを避ける必要がある。因果関係を持たない並行操作については、すべての観察者が同じ順序を採用する必要はない。

因果関係は、プロセス順序、ある書き込みの読み取りなどの依存関係およびその推移的閉包に由来する。サービス間のメッセージやユーザーセッションの切り替えを因果コンテキストに含めるかどうかは、API および実装契約の一部である。Lamport 時刻戳記を単独で付与したり、バージョンベクトルを使用したりするだけでは、完全な因果整合性読み取りサービスが自動的に形成されるわけではない。

セッション保証：ユーザーの連続した体験をまず保護する

「自身の書き込みの読み取り」は、セッションの後の読み取りが、ユーザー自身が完了した関連する書き込みを見逃さないことを要求する。単調読み取りは、セッションが観察する状態がより古い履歴に後退しないことを要求する。その他のセッション保証は、連続する書き込みおよび読み取り後の書き込みの伝播順序を制約する。

これらの保証には明確なスコープがある。ブラウザセッションに対して「自身の書き込みの読み取り」を可能にしても、他のすべてのユーザーがその変更を即座に可視化できることを意味するものではない。セッションが別のノードに移動する場合、進捗トークンを保持し、ターゲットノードが追いつくのを待つ必要があるかもしれない。

最終整合性：収束を記述し、中間過程を保証しない

更新が停止し、必要な情報が引き続き伝播され、マージが完了するなどの条件下で、レプリカは最終的に収束する。この保証のみでは、収束までの時間を規定するものではなく、それ以前の読み取りが後退するかどうか、並行更新がどのように処理されるか、またはビジネス更新が上書きされるかどうかについても規定しない。

最終整合性は、セッション保証や因果保証とともに提供されるべきであり、すべてのモデルを単一の強弱の目盛りに機械的に並べるべきではない。LWW（Last Writer Wins）、CRDT、またはアプリケーションレベルのマージを採用するかどうかについても、追加の説明が必要である。競合解決 を参照。

トランザクション分離とオブジェクト整合性は異なる問題である

Serializable（直列化可能）は、複数のトランザクションの効果が、ある直列トランザクション順序と同等であることを要求する。Strict serializability（厳密直列化可能）は、さらに、その順序がリアルタイム順序を尊重することを要求する。単一キー操作が線形整合性であっても、クロスキーの「残高を最初に読み取り、その後送金する」といった処理が原子性トランザクションとして自動的に構成されるわけではない。

同様に、serializable という名前の API オプションがあっても、その製品定義を読む必要がある。例えば、etcd の serializable 読み取りオプションは古 stale な読み取りを許可しており、SQL の分離レベルの名前から直接推論することはできない。

各操作が線形整合性であっても、インクリメントが 1 つ失われる可能性がある

2 つのクライアントがともにカウンターを 1 増やそうとするが、独立した read、ローカル加算、write を使用して実装する。サービスは、以下の表の順序ですべての単一操作を実行し、各戻り値がレジスタの仕様を満たすことが可能である。

ここでは単一の読み書きの線形整合性は違反されていないが、2 つのビジネスインクリメントの結果、1 しか残っていない。解決策は、インクリメント自体を原子操作にすること、またはバージョン条件付きの CAS/トランザクションを使用し、競合後に再読み取りして計算することである。通常の書き込みにリトライ回数を追加しても、自動的に原子性インクリメントにはならない。

CAS を使用する場合、A と B は初めにバージョン v0 を持つ。A の成功後、バージョンは v1 になり、B の v0 条件は失敗しなければならない。B は値 1 と v1 を再読み取りし、2 を再計算して、再試行してコミットする。これもまた、検証対象をビジネスの約束と一致させる必要があることを示している：基礎となるレジスタの履歴のみを検証し、呼び出し元が組み合わせた複合操作は検証していない。

早見表とエンジニアリングのトレードオフ

PACELC は、パーティション発生時のみならず、発生しない場合のレイテンシと整合性の選択についても考慮すべきことを提醒するが、「すべての強い整合性操作が固定で 1〜2 RTT 余分にかかる」という法則ではない。地理的配置、リース、キャッシュ、バッチ処理、読み取りパスは、実際のコストを変更する。

レビュー時には、どの書き込みがすでに成功し、どの読み取りがいつ開始し、障害がどの接続で発生し、どのような値を返すことが許容されるかという具体的な履歴を記述するのが望ましい。これは、データベース全体に CP または AP のラベルを貼るよりも、インターフェース設計をより適切に導くものである。

参考

• Perspectives on the CAP Theorem。
• etcd API 保証。
• 時間と時計、障害モデル。

Keywords: CAP, PACELC, linearizability, sequential consistency, causal consistency, eventual consistency, serializability