競合解決

競合の本質は、2つの操作がそれぞれ独自の既知の状態に基づいて生成され、システムが事前にそれらを共通の順序に並べなかった点にある。ネットワーク上での到着順序は、ビジネス上の因果順序とは一致しない。競合を解決する前に、各操作がどのような意図を表しているか、そしてどの結果がプロダクトのセマンティクスに合致するかを明確にする必要がある。

上書き更新とマージ操作は異なる意図を表す

「いいね数」を「11 に設定する」と「1 増やす」は異なる。2つのクライアントが 10 から始めてそれぞれ 11 を書き込み、最終的に 11 が保存されるのは代入のセマンティクスには合致するかもしれないが、1回分のいいねという意図が失われる。2回分のいいねを保持するには、独立した操作を記録するか、適切なカウント構造体を使用する必要がある。

同様に、ショッピングカートで集合の和集合を直接取ることは並行追加を保持できるが、削除済み商品が再出現する可能性がある。「全ての変更を保持する」だけでは不十分で、削除と再追加の関係を定義する必要がある。

LWW：全順序を用いて勝者を選ぶ

Last-Write-Wins (LWW) は、バージョンに全順序比較可能なソートキー（例：(timestamp, writer_id)）を割り当て、最大のバージョンを選ぶ。2番目のフィールドは、同じタイムスタンプでのタイブレークを決定論的に行うために使用され、各レプリカは同じ比較規則を使用しなければならない。

利点は結果が単一でマージが簡単であることだが、欠点は並行して失敗した側の値が上書きされることである。「最後」とはソートキーが最大であることを指し、必ずしも現実世界で最後に操作を行った者を指すわけではない。物理クロックの速いノードは他のノードを長期間上回ることがあり、論理時間は実際の時間とは一致しない。

LWW は、指定された優先ルールで上書きすることが実際に許容されるフィールドに適している。2人の編集者がそれぞれ修正した内容を自動的にマージすることはできず、複数の +1 の意図を代入後のカウント結果として直接保存することもできない。

バージョンベクトル：継承と並行性の認識

A、B という2つの書き込み者を例にとる。バージョンベクトル [a,b] は、そのバージョンが各書き込み者の論理更新進捗を既に含んでいることを表す。各コンポーネントについて vᵢ≤wᵢ が成り立ち、かつ少なくとも1つが厳密に小さい場合、v<w と表記する。これは、w がこのモデルにおいて v の因果履歴を継承していることを意味する。

共通バージョン [1,0] から出発し、A がローカルで更新して [2,0] を得る。B は古いバージョンを観測して更新し、[1,1] を得る。前者の A コンポーネントが大きく、後者の B コンポーネントが大きいため、2つのベクトルは比較不可能であり、並行性を示す。和が 2 と 2 であるからといって順序を決定することはできない。

マージ時には、まず逐コンポーネントの最大値 [2,1] を取って観測済みの履歴を表し、その後、新しい更新を実行した書き込み者が自身のコンポーネントをインクリメントする。⁠因果コンテキストのマージは、ビジネス値のマージではない⁠：アドレス、ショッピングカート、権限などは各自のルールを必要とする。バージョンベクトルは競合を検出するのに役立つが、製品上の決定を下す役割は負わない。

この簡略化されたモデルは、各書き込み者が信頼性が高く単調な ID とカウンターを持っていることを仮定している。ノードの再インストール後に旧 ID を無作為に再利用し、カウンターをゼロリセットすると、バージョンの意味が崩壊する。書き込み者の数が増加すると、メタデータのオーバーヘッドも増大する。

CRDT：マージセマンティクスをデータ構造に組み込む

CRDT は、制約付きのデータ表現と更新規則を用い、同じ更新を受信したレプリカが同じ状態に収束するようにする。ネットワーク分断中のレプリカが遠隔地の更新を即座に知ることを保証するものではなく、任意のビジネスルールが調整なしで成立することを保証するものでもない。

状態ベースの CRDT は通常、状態を半格（セミラティス）として整理する。更新は偏序に従って単調に進み、マージは最小上界（supremum）を取る。マージの可換性、結合法則、冪等性により、状態の伝播が重複したり順序が入れ替わったりしても最終結果は変わらない。この3つの法則を満たす関数が1つあれば十分ではなく、更新規則と状態の偏序も整合していなければならない。

操作ベースの CRDT は操作を伝播し、その規定された信頼性のある配信、重複排除、または因果配信の条件に依存して、交換可能な並行操作を可能にする。ある状態ベースの実装で許可されている重複配信を、単純な「メッセージを受信したら +1」を行う操作ベースの実装にそのまま適用してはならない。

G-Counter と PN-Counter：書き込み者ごとの寄与を保存

G-Counter では、各書き込み者は自分のコンポーネメントのみをインクリメントし、読み取りは全コンポーネントの和を取り、マージは逐コンポーネントの最大値を取る。A が現在 [3,0]、B が [1,2] であると仮定すると、マージ結果は [3,2] となり、値は 5 となる。2つのローカル合計値 3 と 3 を足して 6 にするのではなく、A の1回の増加分が両方の状態に同時に存在しているためである。

[1,2] を繰り返しマージしても [3,2] が得られ、マージ順序を変えても同じ結果になる。これは、「各書き込み者がどこまで累積したか」を記録することで、重複計算を回避できる理由を説明している。ただし、B の状態を受信していない段階では、A が読み取る 3 はその時点で知られている結果であり、リアルタイムのグローバル合計値ではない。

PN-Counter は2つの G-Counter を使用し、それぞれ増加量 P と減少量 M を記録する。読み取りは sum(P)-sum(M) を行う。基盤となる2つの状態は依然として増加のみを行うが、表示される数値は増減可能である。

しかし、PN-Counter は在庫が負にならないことを保証しない。在庫が 1 の状態で、2つの地域がそれぞれ 1 ずつ減らすと、マージ後に正しく -1 に収束する可能性がある。オーバーセールを許容しない場合は、調整によるチェックが必要か、消費可能なクレジットを事前に割り当て、有界カウンタープロトコルでクレジットの移動を管理する必要がある。収束自体はこの制約を守らない。

両地域とも「残り 1 を確認」しているのに、マージ後に -1 になる理由

初期の増加コンポーネントは seed=1 のみであり、A、B はお互いの減価をまだ認識していないため、それぞれが1回の減価を発生させる。各自のローカルで確認できる在庫残高は 0 だが、2回の減価はマージ後にすべて保持されなければならない：

P = {"seed": 1}
minus_A, minus_B = {"A": 1}, {"B": 1}
assert sum(P.values()) - sum(minus_A.values()) == 0
assert sum(P.values()) - sum(minus_B.values()) == 0
merged_minus = {writer: max(minus_A.get(writer, 0), minus_B.get(writer, 0))
                for writer in minus_A.keys() | minus_B.keys()}
assert sum(P.values()) - sum(merged_minus.values()) == -1

# 代わりに、消費可能な1つのクレジットを事前に A に割り当てます。各地域は自分が持つクレジットのみを消費できます。
rights = {"A": 1, "B": 0}
def consume_local(node):
    if rights[node] == 0:
        return False
    rights[node] -= 1
    return True

assert consume_local("A")
assert not consume_local("B")
assert not consume_local("A")
assert sum(rights.values()) == 0

クレジット方式は即時可用性のいくらかを犠牲にする：A にクレジットが残っていても、B がネットワーク的に分断されている場合、B は自分が販売できることを装うことはできない。B は待機するか、拒否するか、許可された場合は A に移動をリクエストする必要があるが、移動プロセスでは同じクレジットが両地域で同時に使用されないように防止しなければならない。上記の辞書は、事前割り当てと各地域でのアトミックな減価を示した簡略化されたモデルに過ぎず、分散移動、永続化、またはリクエストの重複排除は実装されていない。完全な有界カウンター設計については、数値不変量に関する論文 を参照のこと。

OR-Set：観測された追加ラベルの削除

理解しやすい状態ベースの OR-Set は、各追加に一意のラベルを割り当て、追加集合 A と削除済みラベル集合 T を保存する。要素が存在するのは、その要素に T に含まれない追加ラベルが少なくとも1つある場合のみである。要素を削除する際、ローカルで既に観測されたその要素のラベルのみを記録する。

マージでは A と T それぞれの和集合を取ることができる。上記の図では、t1 の削除は並行して生成された t2 には影響しないため、並行追加が勝ったように見える。もし A が t2 を先に観測してから x を削除すれば、t1 と t2 の両方を削除でき、最終的に x は存在しなくなる。この違いは因果関係に由来しており、メッセージがちょうど先に到着したか後から到着したかという偶然ではない。

教育用の実装では tombstone（墓標）が成長し続ける。クリーンアップ時には、古いラベルが遅延メッセージ、オフラインレプリカ、またはバックアップから再出現しないことを証明する必要がある。実際の最適化された実装では、因果コンテキストの圧縮によってメタデータを削減できる。「削除から数日が経過した」という理由だけで無条件にクリアすることはできない。

墓碑を保持する OR-Set を実行する

セマンティクスを明確にするため、以下では不変集合を用いて全ての追加ラベルと削除ラベルを保存する。新しいラベルは「書き込み者の一意な ID ＋ 単調なシーケンス番号」によって提供され、マージでは既存のラベルのみを伝播し、ラベルを再生成しない。このモデルは、レプリカ間でも同じラベルが生成されないことを仮定しており、関数は自分が既に確認した重複のみをチェックできる。

from dataclasses import dataclass
from itertools import permutations

@dataclass(frozen=True)
class ORSet:
    adds: frozenset = frozenset()  # (element, tag)
    removed: frozenset = frozenset()

    def add(self, element, tag):
        if tag in self.removed or any(t == tag for _, t in self.adds):
            raise ValueError("新しい追加には未使用のラベルを使用する必要があります")
        return ORSet(self.adds | {(element, tag)}, self.removed)

    def remove(self, element):
        observed = {tag for item, tag in self.adds if item == element}
        return ORSet(self.adds, self.removed | observed)

    def merge(self, other):
        return ORSet(self.adds | other.adds, self.removed | other.removed)

    def values(self):
        return {item for item, tag in self.adds if tag not in self.removed}

base = ORSet().add("x", "A:1")
left = base.remove("x")
right = base.add("x", "B:1")
third = base.add("y", "C:1")
for order in permutations((left, right, third)):
    merged = ORSet()
    for state in (*order, order[0]):  # 順序を変えて繰り返し伝播
        merged = merged.merge(state)
    assert merged.values() == {"x", "y"}
    assert merged.removed == {"A:1"}

# 並行追加を既に見た後に削除すれば、2つの x ラベルを削除できる。
deleted = merged.remove("x")
assert deleted.values() == {"y"}
assert deleted.removed == {"A:1", "B:1"}
assert deleted.merge(right).values() == {"y"}  # 遅れて届いた古い状態は x を復活させない
assert deleted.add("x", "A:2").values() == {"x", "y"}

# 削除ラベルをクリアすると、古い追加記録は即座に再表示される。
assert ORSet(deleted.adds, frozenset()).values() == {"x", "y"}

最初の削除では A:1 しか認識していないため、B:1 を削除する権利はない。2回目の削除では2つのラベルを既に観測しているため、x を消去できる。その後、A:2 を使って再追加するのは、新しいビジネス操作を表している。3つの結果は操作の因果コンテキストによって決定され、ネットワークメッセージの到着順序を入れ替えてもそれらは変わらない。

この素朴な表現では、adds と removed はどちらも増加のみを行い、クエリ時にのみラベルをフィルタリングするため、「単調なメタデータがどのように削除可能な可視集合を生成するか」を見ることができる。最後の断言は、墓碑を無条件にクリアすると、遠隔地のメッセージを待たずに、ローカルに保持されていた古い追加を復活させることができることを示している。本番環境の実装ではメタデータを圧縮できるが、十分な因果証拠を保持しなければならない。最適化の方向性については、最適化された競合フリーレプリケートセット を参照。

同じビジネスの「カート追加」リクエストが再試行時に新しいラベルを再生成すると、それは2回目の追加として扱われる。OR-Set の重複状態伝播に対する冪等性は、2つの新しいラベルが実は同じユーザーリクエストに由来することを識別するものではなく、ビジネスリクエスト ID は別途処理する必要がある。

削除されるのは「追加」であり、「名前」ではない

x を単一のスイッチではなくラベルで表現することで、並行削除が実際に何を覆しているかを見ることができる。まず B で新しいラベルを追加し、まだ同期されていない A で削除する。マージ後、新しいラベルは依然として存在する。先にマージし、A が新しいラベルを確認してから削除すれば、結果は異なる。2つの結果は、観測済み集合が異なることに由来しており、マージ関数がどちらかの側に偏っているわけではない。

ルールを選択する際はセマンティクスを確認し、収束可能かどうかだけでなく確認する

CRDT カウンターは、「ユーザーが同じいいねを重複して送信した」ことを自動的に識別しない。基盤となるマージでの重複排除と、ビジネスリクエストでの重複排除は異なるレイヤーであり、後者には安定したイベント ID やその他のビジネスルールが必要である。

続きを読む：レプリケーション戦略、反エントロピーとデータ修復。

参考文献

• Shapiro 他：CRDT 総合研究。
• An Optimized Conflict-Free Replicated Set：集合セマンティクスおよびメタデータの最適化。
• Extending Eventually Consistent Cloud Databases for Enforcing Numeric Invariants：有界カウンターと数値制約。

Keywords: conflict resolution, LWW, version vector, CRDT, G-Counter, PN-Counter, OR-Set, convergence