CRDT（衝突なしレプリケーション型データ構造）

CRDT が解こうとしている問題

複数のレプリカに同時に書き込みが入る環境では、どこかで更新がぶつかります。素朴な解決は「最後に書いた人が勝つ」や、サーバー間で合意を取って順序を決める方法ですが、前者は更新を捨て、後者は合意プロトコルによる調整コストと、分断時の可用性低下を招きます。CAP 定理でいう AP（可用性優先）に倒したいとき、調整なしで競合を解消したい――この要求に数学的に答えるのが CRDT（Conflict-free Replicated Data Type） です。

CRDT の核心は単純です。マージ操作が代数的に良い性質を持つように型を設計しておけば、更新がどんな順序・重複で届いても、全レプリカは必ず同じ状態に収束する。競合検出も巻き戻しも要らず、ただマージするだけで整合します。これは結果整合性（eventual consistency）の一形態ですが、アプリ側で衝突を解く必要がない点で 強結果整合（strong eventual consistency, SEC） と呼ばれます。

なぜ収束するのか：半束という土台

CRDT が収束する理由は、状態の集合とマージ操作が 結合半束（join-semilattice） をなすからです。状態の集合を S、マージを join（記号では二項演算）とすると、次の3性質が成り立ちます。

• 可換律（commutative）: join(a, b) = join(b, a)。どちらを先にマージしても同じ。
• 結合律（associative）: join(join(a, b), c) = join(a, join(b, c))。グループ化を変えても同じ。
• 冪等律（idempotent）: join(a, a) = a。同じ状態を二度マージしても変わらない。

この3つが揃うと、状態の集合に半順序が入ります。a ≤ b を「join(a, b) = b」と定義すると、join は任意の2要素の 最小上界（least upper bound, LUB） になります。各レプリカの状態は、更新が進むほどこの順序を 単調に上って（monotonically） いきます。

形式的には、全レプリカが互いの更新を最終的に1回以上は受け取る（最終配送）と仮定すれば、各レプリカの状態はすべての更新の join、すなわち半束の同じ LUB へ収束します。順序や重複に依存しないのは、上の3性質が「混ぜる順番と回数を結果から消す」からです。

状態ベースと操作ベース

CRDT には伝播方式の異なる2系統があります。

状態ベース（CvRDT, convergent） は、各レプリカが自分の 状態全体 を相手に送り、受け手は merge = join で自分の状態と併合します。半束なので順不同・重複に強く、配送は冪等・可換。ゴシップ通信のように「ときどき状態をまるごと交換する」運用に向きます。欠点は状態が大きいと転送量がかさむことです（差分だけ送る delta-state CRDT で軽減します）。

操作ベース（CmRDT, commutative） は、状態ではなく 操作（更新） を他レプリカへ配送し、各レプリカでローカルに適用します。収束の条件は「並行する操作どうしが可換」であること。ただし操作は重複適用すると壊れるものが多いため、各操作を高々一度ずつ（重複なく）全レプリカへ届ける 配送層が必要です。順序は因果順（causal delivery）まで緩められますが、配送保証は状態ベースより重くなります。

両者は理論上等価で、片方で表せる型はもう片方でも表せます。実装の都合（帯域か配送保証か）で選びます。

代表的な CRDT を組み立てる

カウンタ：GCounter と PNCounter

増加だけを扱う GCounter は、レプリカごとの増加量を持つベクタです。各レプリカ i は自分のスロットだけ増やし、merge は 要素ごとの max を取ります。max は可換・結合・冪等なので半束になり、合計値は全スロットの和で読み出します。

GCounter（レプリカ A, B, C）
  A: [a=3, b=0, c=0]
  B: [a=0, b=2, c=0]
merge(A,B) = [max(3,0), max(0,2), max(0,0)] = [3,2,0]  → 合計 5

なぜ max なのか。各スロットは「そのレプリカが出した増加の累計」で 単調増加 します。古い値と新しい値を混ぜたとき、欲しいのは新しい方（大きい方）だけ。だから要素ごと max で、遅れて届いた更新も二重に届いた更新も正しく1回ぶんに収まります。

減算もしたい場合は、増加用 P と減算用 N の2本の GCounter を持つ PNCounter にします。値は sum(P) - sum(N)。減算を単独で冪等にするのは難しいため、「増える一方のカウンタ2本の差」に分解するのが定石です。

集合：ORSet

集合は要素ごとに「最後の操作が add か remove か」を決めねばならず、素朴には競合します。ORSet（Observed-Remove Set） は、add のたびに一意なタグ（ユニークID）を付け、remove は その時点で観測したタグだけ を消すことで解決します。要素が「生きている」とは、追加タグの集合から削除タグの集合を引いた差が空でないこと。

レジスタ：LWWRegister

単一値を上書きするだけなら LWWRegister（Last-Write-Wins） が使えます。各書き込みにタイムスタンプを付け、merge は タイムスタンプが大きい方 を採る（同着はレプリカIDで決定的に破る）。これも max ベースの半束です。実装が軽い反面、並行更新の一方を捨てる ため、データを失いたくない用途には向きません。物理時計のずれを避けるためにロジカルクロックを使うのが通例です。

できること・できないこと

CRDT は調整なしで収束する代わりに、収束する状態は「マージ規則が決める唯一の解」 に限られます。たとえば「残高は絶対にマイナスにならない」のような 大域不変条件 は、各レプリカが独立に書く以上、マージ後に破れることがあります（2拠点が同時に引き出すと合計が在庫を超える等）。こうした不変条件には、結局なんらかの調整（予約・上限の事前配分）か、強整合な経路が必要です。

まとめ