---
title: 競合解決
url: https://doc.liz6.com/ja/distributed-systems/03-replication-and-consistency/02-conflict-resolution
locale: ja
area: distributed-systems
tags:
- distributed-systems
- replication-and-consistency
date: 2026-06-30
modified: 2026-07-16
description: マルチリーダーおよびリーダーレスレプリケーションでは競合が避けられず、2つのノードが同時に同一キーに対して書き込みを行います。粗暴な「最終書き込みが勝つ」方式から、因果関係を追跡するバージョンベクトル、さらに数学的性質（結合則・交換則・冪等性）を用いて自動マージを保証するCRDTへと、競合解決の手法が強力になるほど、その代償も大きくなります。
---

# 競合解決

> マルチリーダーおよびリーダーレスレプリケーションでは競合が避けられず、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 が記録される → 結果は正しい
```

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

| シナリオ | 推奨 |
|------|------|
| シンプルなキーバリュー、データ消失を許容 | LWW (Cassandra デフォルト) |
| 並行変更においてセマンティクスを保持する必要がある | バージョンベクトル (Dynamo, Riak) |
| カウンター | PN-Counter |
| 集合/リスト | OR-Set, RGA (Replicated Growable Array) |
| リッチテキスト共同編集 | CRDT (Yjs/Automerge) |

## 参考

- **論文**: "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*