競合解決

マルチリーダーおよびリーダーレスレプリケーションでは競合が避けられず、2つのノードが同時に同一キーに対して書き込みを行います。粗暴な「最終書き込みが勝つ」方式から、因果関係を追跡するバージョンベクトル、さらに数学的性質（結合則・交換則・冪等性）を用いて自動マージを保証するCRDTへと、競合解決の手法が強力になるほど、その代償も大きくなります。

マルチリーダーおよびリーダーレスレプリケーションの代償は、⁠競合が避けられないことです。2つのノードが同時に同一キーに対する異なる書き込みを受け取り、happens-before 関係によって順序を判定することができません。

Last-Write-Wins (LWW)

タイムスタンプに基づいて決定します：最新のタイムスタンプが勝ち、古い値は破棄されます。シンプルで効率的ですが、データ消失の可能性があります。

Node A: write(x="Alice")  ts=1000
Node B: write(x="Bob")    ts=1001
→ "Bob" が勝ち、"Alice" は上書きされる
もしこれらの書き込みが並行して行われた場合（因果関係がない場合）、LWW は "Alice" を破棄する —— データの消失

LWW は Cassandra のデフォルト戦略であり、Riak ではオプションとして選択可能です。その代償は「データが消失する可能性がある」ことであり、カウンター（いいね数など）にとっては許容できません。

バージョンベクトル (Version Vectors)

物理的な時刻に依存せず、各ノードの論理クロックを用いて happens-before 関係を判定します（01-02 を参照）。バージョンベクトルが比較できない場合、⁠並行競合としてマークされ、アプリケーション層または自動マージに委ねられます。

Dynamo のアプローチ：読み取り操作は、比較できないすべてのバージョン（siblings）を返します。クライアントはそれらを自分でマージする必要があります（例：ショッピングカートのマージ。ユーザーが異なるデバイスで同時に異なる商品を追加した場合 → クライアントはそれらの和集合を表示する）。もしクライアントがマージせずに直接書き込む場合、サーバーも複数の siblings を保存します。

CRDT (Conflict-free Replicated Data Types)

数学的に並行操作の交換可能性を保証し、アプリケーション層での競合処理なしに自動的に収束します。

G-Counter (Grow-only Counter)

各ノードが独立した counter[N] を維持する:
  node_i の Increment(): counter[i] += 1
  Value = sum(counter[0..N])   ← 常に正しい合計値 (増加のみで減少しないため、競合なし)

merge(self, other): 各 i に対して: counter[i] = max(self[i], other[i])
→ マージ時に各ノードごとの最大値を取得する (increment はローカルで行われるため、他のノードは最新の値を受信していない可能性がある)

PN-Counter (Positive-Negative Counter)

インクリメントとデクリメントの両方をサポートします。

各ノードが2つの G-Counter を維持する: P[i] (正) と N[i] (負)
  Increment(): P[i] += 1
  Decrement(): N[i] += 1
  Value = sum(P[0..N]) - sum(N[0..N])

OR-Set (Observed-Remove Set)

add と remove をサポートする集合。

各要素の add ごとに一意のタグ (UUID など) を割り当てる
  add(e): タグ t を生成; S = S ∪ {(e, t)}
  remove(e): S 内の e に対応するすべてのタグを tombstones に記録
  Value = {e | (e,t) in S かつ t が tombstones に含まれない}

merge(self, other): S = self.S ∪ other.S (集合の和), tombstones = self.T ∪ other.T
→ タグが "removed" としてマークされていない限り、要素は存在する
→ 並行して add(e) と remove(e) が行われた場合: add にはタグ t があり、remove には t を含む tombstones が記録される → 結果は正しい

アプリケーションでの選択

参考

• 論文⁠: "A Comprehensive Study of Convergent and Commutative Replicated Data Types" (Shapiro et al, 2011)
• 実際の実装⁠: github.com/automerge/automerge, docs.yjs.dev

Keywords: LWW, version vector, CRDT, G-Counter, PN-Counter, OR-Set, causal consistency, concurrent writes