狠狠撸

JSON CRDT
安田裕介
@TanUkkii007

共同編集アプリケーション
において
? 自分の編集が拒絶されるのはいやだ
? →書き込み時のロックやチェックではなく、読み
込み時のコンフリクト解決
? 自分の編集が上書きされるのはいやだ
? →システムサイドのコンフリクト解決ではなく、
アプリケーションサイドのコンフリクト解決

CRDT
? Conflict Free Replicated Data Types
? コンフリクトの自動解決が可能なデータ型
? コンフリクトを起こしても情報を欠落させない
? Counter, Set, Map, Registerなどがある
A comprehensive study of convergent and commutative
replicated data types

JSON CRDT
? M. Kleppmann & A R. Beresfordが考案
? A Conflict-Free Replicated JSON Datatype
? http://arxiv.org/abs/1608.03960
? CRDTを任意のネストが可能なデータ構造である
JSONに適用

実装
? https://github.com/fthomas/crjdt
? Scala & Scala.js
? Kleppmann & Beresfordの論文の擬似コードをDSL
として表現
? ScalaCheckを使ったプロパティーベーステストで
すべての法則を証明

Mapの同一キーへの代入
A Conflict-Free Replicated JSON Datatype

import crdt.json.playground.CRDTNodeToJson._
import eu.timepit.crjdt.core._
import eu.timepit.crjdt.core.syntax._
val initCmd = doc.downField("key") := "A"
val p0 = Replica.empty("p").applyCmd(initCmd)
p0.document.toJson
//{
// "key" : "A"
//}
def merge(r1: Replica, r2: Replica): Replica = {
r1.applyRemoteOps(r2.generatedOps)
}
val q0 = merge(Replica.empty("q"), p0)
q0.document.toJson
//{
// "key" : "A"
//}
val p1 = p0.applyCmd(doc.downField("key") :=
"B")
p1.document.toJson
//{
// "key" : "B"
//}
val q1 = q0.applyCmd(doc.downField("key") :=
"C")
q1.document.toJson
//{
// "key" : "C"
//}
val p2 = merge(p1, q1)
p2.document.toJson
//{
// "key" : "B",
// "key" : "C"
//}
val q2 = merge(q1, p1)
p2.document.toJson
//{
// "key" : "B",
// "key" : "C"
//}

{}で上書きされたMapの編集
A Conflict-Free Replicated JSON Datatype

import
crdt.json.playground.CRDTNodeToJson._
import eu.timepit.crjdt.core.Replica
import eu.timepit.crjdt.core.syntax._
def merge(r1: Replica, r2: Replica): Replica = {
r1.applyRemoteOps(r2.generatedOps)
}
val colors = doc.downField("colors")
val initCmd = colors.downField("blue") :=
"#0000ff"
val p0 = Replica.empty("p").applyCmd(initCmd)
p0.document.toJson
//{
// "colors" : {
// "blue" : "#0000ff"
// }
//}
val q0 = merge(Replica.empty("q"), p0)
q0.document.toJson
//{
// "colors" : {
// "blue" : "#0000ff"
// }
//}
val p1 = p0.applyCmd(colors.downField("red") := "#ff0000")
p1.document.toJson
//{
// "colors" : {
// "blue" : "#0000ff",
// "red" : "#ff0000"
// }
//}
val q1 = q0
.applyCmd(colors := `{}`)
.applyCmd(colors.downField("green") := "#00ff00")
q1.document.toJson
//{
// "colors" : {
// "green" : "#00ff00"
// }
//}
val p2 = merge(p1, q1)
p2.document.toJson
//{
// "colors" : {
// "red" : "#ff0000",
// "green" : "#00ff00"
// }
//}
val q2 = merge(q1, p1)
q2.document.toJson
//{
// "colors" : {
// "green" : "#00ff00",
// "red" : "#ff0000"
// }
//}

レプリカ
? クライアントに相当
? レプリカ間で独立なJSONドキュメントの状態をもつ
? コマンドを適用してオペレーションを生成する
? yieldコマンドでオペレーションを他のレプリカに同期する
? オペレーションは因果関係を満たしつつドキュメントの状
態を更新する

コマンド
? ローカル変数の宣言：let x = EXPR
? 代入：x := v
? 挿入：EXPR.insert(v)
? 削除：EXPR.delete
? レプリカ間のオペレーションの同期とドキュメント
の更新：yield

オペレーション
? Id：Lamport タイムスタンプ（レプリカIDとオペレーションIDのペア）
? deps: 因果の依存。つまりどのオペレーションが適用されたドキュメン
トを編集しようとしてるのか。
? cur: カーソル。ドキュメントの位置
? mut: insert/delete/assign
case class Operation(id: Id, deps: Set[Id], cur: Cursor, mut: Mutation)

オペレーションの性質
? 結果整合性：レプリカにすべてのオペレーションを適
用すると、すべてのレプリカは必ず同じ状態になる
? 結合性（バッチに依存しない）：a + (b + c) = (a + b) +
c
? 可換性（順番に依存しない）: a + b = b + a
? 冪等性: a + a = a

狠狠撸

JSON CRDT

More Related Content

JSON CRDT