今日のゴール
- 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合意