今日のゴール

CRDT（Conflict-free Replicated Data Types）の概念を理解する
ベクタークロックによる因果関係追跡を学ぶ
競合解決の仕組みを理解する

CRDTとは

CRDT（Conflict-free Replicated Data Types）は、分散システムで競合なくデータを複製できるデータ構造です。

重要な性質

性質	説明
可換性	A + B = B + A（順序に依存しない）
冪等性	A + A = A（重複適用しても同じ）
結合性	(A + B) + C = A + (B + C)

これらの性質により、どの順番でマージしても同じ結果になります。

Nindaで使用するCRDT

CRDT	用途
LWW-Element-Set	タプルの追加・削除
Vector Clock	因果関係の追跡
Claims Map	take操作の調整

ベクタークロック

分散システムで因果関係を追跡するための仕組みです。

ベクタークロックの比較

var vc1 = newVectorClock()
vc1.increment("node-1")  # {node-1: 1}

var vc2 = newVectorClock()
vc2.increment("node-2")  # {node-2: 1}

# 比較結果
if vc1 < vc2:
  echo "vc1 happens before vc2"
elif vc2 < vc1:
  echo "vc2 happens before vc1"
else:
  echo "Concurrent"  # ← この場合（並行）

比較結果	意味
vc1 < vc2	vc1がvc2より前に発生
vc1 > vc2	vc1がvc2より後に発生
比較不能	並行（因果関係なし）

CRDTタプルスペース

let space = newCRDTTupleSpace("node-1")

# タプル追加
let entry = space.add(toTuple(strVal("data"), intVal(1)))

# 検索
let found = space.findFirst(toPattern(strVal("data"), nilValue()))

# デルタ取得（同期用）
let delta = space.getDelta(lastSyncClock)

# デルタ適用（他ノードから受信）
otherSpace.applyDelta(delta)

デルタ同期

全データを送信するのではなく、**差分（デルタ）**のみを送信します。

Take操作のClaim Protocol

タプルスペースのtake操作は、分散環境では特別な処理が必要です。

ポイント:

複数ノードが同時に同じタプルをtakeしようとすると競合
Claim Protocolで競合を検出・解決
1つのノードのみがtakeに成功

競合解決の例

戦略	説明
先着優先	先にclaimが伝播したノードが勝つ
タイムスタンプ	LWW（Last Writer Wins）
ノードID優先	同時の場合はノードIDで決定

まとめ

学んだこと

トピック	ポイント
CRDT	競合のない分散データ構造
ベクタークロック	因果関係の追跡
デルタ同期	差分のみを送信
Claim Protocol	take操作の調整

いつ使うか

場面	推奨
読み書きが多い	CRDT（低遅延）
一時的な不整合OK	CRDT
厳密な整合性必要	Raft（次回）

演習問題

問題18-1: ベクタークロック実装

簡易的なベクタークロッククラスを実装してください。increment、merge、compareメソッドが必要です。

ヒント

内部はTable[string, int]（ノードID → カウンタ）
increment(nodeId): 指定ノードのカウンタを+1
merge(other): 各ノードで最大値を取る
compare: すべてのノードで自分が大きければ「後」、すべてで小さければ「前」、それ以外は「並行」

問題18-2: LWW-Element-Set

Last Writer Wins方式のセット型を実装してください。同じ要素の追加と削除が競合した場合、タイムスタンプが新しい方が勝ちます。

ヒント

各要素に(value, timestamp, isDeleted)を保持
add(value, timestamp): タイムスタンプが新しければ追加
remove(value, timestamp): タイムスタンプが新しければ削除フラグをON
contains: 削除フラグがOFFの要素のみtrue

問題18-3: 競合シミュレーション

2つのノードが同時に同じタプルをtakeしようとするシミュレーションを実装し、競合解決の動作を確認してください。

ヒント

2つのCRDTTupleSpaceインスタンスを作成
同じタプルを両方に追加（同期）
同時にclaimを発行
sleepAsyncで伝播を待ち、confirmClaimで結果を確認
片方のみが成功し、もう片方は失敗するはず

前回: 分散システム基礎 | 目次 | 次回: Raft合意