CRDT

実装: distributed/crdt/ / 実行: go test ./distributed/crdt/

同時に起きた2つを見分けられるようになった。では、捨てないなら何をするのか。答えの1つは、まとめ方をあらかじめ決めておくことになる。可換・結合的・冪等の3つがそろえば、届く順も回数も関係なくなる。合意が要らなくなる代わりに、表せる操作が狭くなる。引けないなら引く用のものを足し、消したいなら何を消したかを覚える。

この章で作るもの

論理時計とベクタークロックの章で、同時に起きた2つの出来事を見分けられるようにした。見分けられると、片方を黙って捨てずに済む。

では、捨てないなら何をするのか。

素直な答えは、人に選ばせることになる。両方を残しておいて、次に読んだ人に「こちらとこちら、どちらですか」と聞く。実際にそうしている系もある。だが毎回聞かれるのは重い。

もう1つの答えが、この章になる。まとめ方をあらかじめ決めておく。どちらが先かを決めるのをやめて、2つを1つにする規則だけを用意する。その規則が3つの性質を持っていれば、順序も回数も関係なくなる。

そうすると、合意が要らなくなる。Raft のように「全員で1つの順序に合意する」手続きを踏まずに、各自が勝手に更新して、後から突き合わせるだけで全員が同じ値に落ち着く。

代わりに、表せる操作が狭くなる。その狭さと、狭さの中でどこまでやれるかがこの章になる。

  3つのノードが勝手に更新して、後から突き合わせる

  a: +3          ╲
  b: +5          ─→  どの順で合流しても 10
  c: +2          ╱

     (a∪b)∪c = 10    a∪(b∪c) = 10    c∪a∪b = 10
     a∪b∪b   = 10  ← 二度届いても変わらない


  必要な3つの性質

    可換    a∪b = b∪a          届く順が関係なくなる
    結合的  (a∪b)∪c = a∪(b∪c)  どこから括っても同じ
    冪等    a∪a = a            二度届いても壊れない


  集合で「消した」を表すのが難しい

    2P-Set                      OR-Set
    消した集合に入れる           見えている印だけ消す

    add x  → {x}                add x@a1  → {x: [a1]}
    del x  → {}                 del x     → {x: []} = 無い
    add x  → {}  ✕ 戻らない      add x@a2  → {x: [a2]}  ✓ 戻る

    並行して足したものは          並行して足したものは
    まとめて消える  ✕            見ていない印なので残る  ✓

3つの性質がそろうと、どの順で届いても、二度届いても、同じ値に落ち着く

順に見ていく。

1. 3つの性質が順序と重複を無関係にする: 可換・結合的・冪等
2. 引けないなら、引く用のものを足す: 減算を持てないので、減らした量を別に数える
3. 消したことを表すのがいちばん難しい: 何を消したかを覚えないと、足し直せない

① 3つの性質

まず、増えるだけの数え上げから:

// GCounter は増えるだけの数え上げ。
//
// ノードごとに自分の数を持ち、まとめるときは要素ごとに大きいほうを取る。
// [ベクタークロック](clock)とまったく同じ形になっている。あちらは出来事を数え、
// こちらは値を数えているだけで、まとめ方は同一になる。
type GCounter map[string]int

// Inc は自分の要素だけを増やす。他人の要素には触らない。
func (g GCounter) Inc(node string, n int) {
	if n < 0 {
		panic("crdt: 増える一方の数え上げに負を足そうとした")
	}
	g[node] += n
}

// Value は全員のぶんを合計した値を返す。
func (g GCounter) Value() int {
	sum := 0
	for _, v := range g {
		sum += v
	}
	return sum
}

// Merge は2つをまとめた新しいものを返す。元は変えない。
func (g GCounter) Merge(o GCounter) GCounter {
	out := GCounter{}
	for k, v := range g {
		out[k] = v
	}
	for k, v := range o {
		if v > out[k] {
			out[k] = v
		}
	}
	return out
}

// PNCounter は増えも減りもする数え上げ。
//
// 減らす操作を直接は持てないので、減らした量を別の数え上げに足していく。
// 値は2つの差になる。[2の補数](numbers)が引き算を足し算にしたのと同じ発想で、
// 「引けないなら、引く用のものを足す」という形になっている。
type PNCounter struct {
	P GCounter // 増やした量
	N GCounter // 減らした量
}

// NewPN は空の数え上げを作る。
func NewPN() *PNCounter { return &PNCounter{P: GCounter{}, N: GCounter{}} }

// Inc と Dec は、それぞれの側を増やす。どちらも増やすだけになる。
func (c *PNCounter) Inc(node string, n int) { c.P.Inc(node, n) }
func (c *PNCounter) Dec(node string, n int) { c.N.Inc(node, n) }

// Value は差を返す。
func (c *PNCounter) Value() int { return c.P.Value() - c.N.Value() }

// Merge は両側をそれぞれまとめる。
func (c *PNCounter) Merge(o *PNCounter) *PNCounter {
	return &PNCounter{P: c.P.Merge(o.P), N: c.N.Merge(o.N)}
}

GCounter は、ノードごとに自分の数を持ち、まとめるときは要素ごとに大きいほうを取る。前の章のベクタークロックとまったく同じ形になっている。あちらは出来事を数え、こちらは値を数えているだけで、まとめ方は同一だ。

なぜこれで衝突しないかというと、他人の要素に触らないからになる。自分の要素は自分しか増やさないので、2つを突き合わせたときに「どちらが正しいか」を決める必要がない。両方とも正しく、大きいほうが新しい。

Merge が3つの性質を持つことは、要素ごとの最大が持つ性質から出てくる。最大は可換で、結合的で、冪等になっている。だから全体もそうなる。

テストで、3つの性質を個別に固定し、そのうえで6通りすべての合流順で同じ値になること、二度合流させても変わらないことを固定した。この「順序も回数も関係ない」性質のおかげで、知らせが入れ替わっても、二度届いても、結果が変わらない。後の調整ループの章が取りこぼしに強いのも、同じ性質の働きになる。

② 引けないなら、引く用のものを足す

GCounter には減らす操作がない。負を足そうとすると止まるようにしてある。

なぜ持てないのかというと、要素ごとの最大が使えなくなるからだ。減らしたぶんを引いて要素に書くと、後から古い値とまとめたときに最大が古いほうを選ぶ。減ったことが取り消される。

だから、減らす操作を別の数え上げとして持つ。PNCounter は増やした量と減らした量を別々の GCounter で持ち、値をその差として出す。減らす操作が「減らす側を増やす操作」に変わっている。

同じ形は、後の2の補数とバイト順の章にも出てくる。あちらは引き算のための回路を持たずに、引く数の符号を反転して足す(2の補数)。こちらは減算を持たずに、減らした量を足す。引けないなら、引く用のものを足すという発想が、まったく違う層で2回出てくる。

テストで、両側をそれぞれまとめれば差が正しく出ること、減らす側も増える一方の数え上げのままであることを固定した。

代償もある。値が 0 に戻っても、P と N の中身は増え続ける。何度も増減を繰り返すと、値は小さいのに持っているものは大きくなる。「消しても軽くならない」という同じ性質は、後の etcd の章にも出てくる。

③ 消したことを表すのがいちばん難しい

集合に移ると、話が急に難しくなる。

// TwoPSet は足すのと消すのを、それぞれ集合で覚える。
//
// 消したものは「消した側」に入るので、後から足し直しても出てこない。
// まとめ方としては正しいが、使い方が制限される。
type TwoPSet struct {
	Added   map[string]bool
	Removed map[string]bool
}

// NewTwoP は空の集合を作る。
func NewTwoP() *TwoPSet {
	return &TwoPSet{Added: map[string]bool{}, Removed: map[string]bool{}}
}

func (s *TwoPSet) Add(v string)    { s.Added[v] = true }
func (s *TwoPSet) Remove(v string) { s.Removed[v] = true }

// Has は、足されていて消されていないかを返す。
func (s *TwoPSet) Has(v string) bool { return s.Added[v] && !s.Removed[v] }

// Values は今ある要素を名前順で返す。
func (s *TwoPSet) Values() []string {
	var out []string
	for v := range s.Added {
		if s.Has(v) {
			out = append(out, v)
		}
	}
	sort.Strings(out)
	return out
}

// Merge は両側の和を取る。
func (s *TwoPSet) Merge(o *TwoPSet) *TwoPSet {
	out := NewTwoP()
	for _, m := range []map[string]bool{s.Added, o.Added} {
		for v := range m {
			out.Added[v] = true
		}
	}
	for _, m := range []map[string]bool{s.Removed, o.Removed} {
		for v := range m {
			out.Removed[v] = true
		}
	}
	return out
}

// tag は1回の追加を区別する印。誰が何回目に足したかで一意になる。
type tag struct {
	Node string
	Seq  int
}

// ORSet は追加ごとに印をつけ、消すときは「そのとき見えていた印」だけを消す。
//
// 見ていない印は消えないので、並行して足された値は残る。
// 消してから足し直すと新しい印がつくので、ちゃんと出てくる。
type ORSet struct {
	live map[string]map[tag]bool
	seq  map[string]int
}

// NewOR は空の集合を作る。
func NewOR() *ORSet {
	return &ORSet{live: map[string]map[tag]bool{}, seq: map[string]int{}}
}

// Add は新しい印をつけて足す。
func (s *ORSet) Add(node, v string) {
	s.seq[node]++
	if s.live[v] == nil {
		s.live[v] = map[tag]bool{}
	}
	s.live[v][tag{Node: node, Seq: s.seq[node]}] = true
}

// Remove は、今このノードから見えている印だけを消す。
//
// ここが肝になる。値そのものを消すのではなく、自分が観測した追加を取り消す。
// 見えていない追加は残るので、並行して足されたものは生き残る。
func (s *ORSet) Remove(v string) {
	delete(s.live, v)
}

// Has は要素があるかを返す。印が1つでも残っていればある。
func (s *ORSet) Has(v string) bool { return len(s.live[v]) > 0 }

// Values は今ある要素を名前順で返す。
func (s *ORSet) Values() []string {
	var out []string
	for v := range s.live {
		if s.Has(v) {
			out = append(out, v)
		}
	}
	sort.Strings(out)
	return out
}

// Tags は要素についている印の数を返す(観測用)。
func (s *ORSet) Tags(v string) int { return len(s.live[v]) }

// Merge は印の和を取る。片方で消され、もう片方で足されていれば、足したほうが残る。
func (s *ORSet) Merge(o *ORSet) *ORSet {
	out := NewOR()
	for _, src := range []*ORSet{s, o} {
		for v, tags := range src.live {
			if out.live[v] == nil {
				out.live[v] = map[tag]bool{}
			}
			for t := range tags {
				out.live[v][t] = true
			}
		}
		for n, q := range src.seq {
			if q > out.seq[n] {
				out.seq[n] = q
			}
		}
	}
	return out
}

素朴な答えが TwoPSet になる。足したものの集合と、消したものの集合を別々に持ち、両方とも増える一方にする。まとめ方は和を取るだけなので、3つの性質は素直に満たす。

だが、使えない。一度消したものは「消した集合」に入ったままなので、後から足し直しても出てこない。テストで、消してから足し直しても現れないことを固定した。買い物かごに入れて、外して、もう一度入れる。これができない。

ORSet が答えになる。追加のたびに一意な印をつけ、削除はそのとき見えていた印だけを消す。

この一行がすべてになる。値そのものを消すのではなく、自分が観測した追加を取り消す。だから、見ていない追加は消えない。

2つの結果が出てくる。

1つは、消してから足し直せること。足し直すと新しい印がつくので、古い印を消してあっても関係なく現れる。

もう1つが面白い。2つのノードが同じ値を独立に足して、片方だけが消した場合、その値は残る。消した側は自分の印しか見ていないので、相手の印は消せない。テストで、まとめた後に印が1つだけ残ること、つまり並行して足したぶんが生き残ることを固定した。

これは規則として「並行なら追加が勝つ」を選んだということになる。逆の選び方もできるし、実際にそういう変種もある。大事なのは、どちらかを選ばなければならないことと、選んだ結果が使う人に見えることになる。

比べるために、最後を残す形も置いてある:

// LWW は最後の書き込みを残す入れ物。時刻とノード名で決める。
//
// 同時に書かれた2つを、決まった規則で片方に倒す。まとめ方としては成立するが、
// 倒されたほうは消える。消えたことも残らない。
type LWW struct {
	Value string
	Stamp int    // 論理時計の値
	Node  string // 同点を解くための持ち主
}

// Set は新しい値を返す。元は変えない。
func (r LWW) Set(v string, stamp int, node string) LWW {
	return LWW{Value: v, Stamp: stamp, Node: node}
}

// Merge は勝ったほうを返す。時刻が同じならノード名で決める。
func (r LWW) Merge(o LWW) LWW {
	if o.Stamp > r.Stamp || (o.Stamp == r.Stamp && o.Node > r.Node) {
		return o
	}
	return r
}

// Lost は、まとめたときに消えたほうを返す(観測用)。
// 消えた値が何だったかを知りたいなら、まとめる前に自分で持っておくしかない。
func (r LWW) Lost(o LWW) (LWW, bool) {
	m := r.Merge(o)
	switch {
	case m == r && r != o:
		return o, true
	case m == o && r != o:
		return r, true
	}
	return LWW{}, false
}

LWW は時刻の大きいほうを残し、同点はノード名で決める。まとめ方としては3つの性質を満たすので、これも立派な CRDT になる。

だが同時に書かれた2つのうち、片方は消える。しかも消えたことが残らない。Lost を用意してあるのは観測のためで、実際に何が消えたかを知りたいなら、まとめる前に自分で持っておくしかない。前の章で「Lamport の数で並べて後を採用すると、片方が黙って消える」と書いた、その実装がこれになる。

動かす

下のデモは、3つのノードが独立に更新してから合流する。合流の順序を変えても、同じ操作を二度送っても、値が変わらないことが見える。集合のタブでは、同じ操作列を2つの型に与えて、足し直せるかどうかの差を見る。

デモCRDT6通りすべて 10

各ノードが自分の要素だけを増やす

a{"a":3}

b{"b":5}

c{"c":2}

a → b → c10

a → c → b10

b → a → c10

b → c → a10

c → a → b10

c → b → a10

6通りすべての合流順で同じ値になる。しかも最初と最後をもう一度合流させてあるので、 二度届いても変わらないことも含まれている

「合流の順序」では、3つのノードが勝手に増やしてから合流する。どの順で合流しても、 二度合流させても、同じ値になる。「消したものを足し直す」では、同じ操作列を2つの型に与える。 2P-Set は消した集合に入れる形なので足し直せず、並行して足したものまで消える。 OR-Set は追加ごとの印を消す形なので、どちらも正しく残る。

設計の観点

• 順序を決めないで済むなら決めない: 合意は高い。まとめ方で済むなら、そちらのほうが壊れにくい
• 3つの性質を先に確かめる: 可換・結合的・冪等。1つでも欠けると、再送や遅延で壊れる
• 他人の持ち物に触らない形にする: 自分の要素だけを更新する形にすると、衝突がそもそも起きない
• 取り消せない操作は、別の操作として足す: 減算も削除も、増える一方のものに置き換える
• 選択が使う人に見えるようにする: 並行なら追加が勝つ、最後が勝つ。どちらも設計判断で、隠すと事故になる
• 増え続けるものの掃除を考える: 印も、減らした量も、放っておけば増える。etcd の履歴と同じ問題が来る

対照と実例

	合意を取る(Raft)	最後を残す(LWW)	まとめ方を決める(CRDT)
必要な通信	過半数との往復	無し	無し
分断中の書き込み	できない	できる	できる
失われるもの	無し	同時に書かれた片方	無し(規則で吸収する)
表せる操作	何でも	何でも	限られる
実装の重さ	重い	軽い	型ごとに設計が要る

型	足し直せるか	並行な追加と削除	増え続けるもの
GCounter	(該当なし)	(該当なし)	参加者の数だけ
PNCounter	(該当なし)	(該当なし)	増減の回数に応じて
TwoPSet	できない	削除が勝つ	消した値の分
ORSet	できる	追加が勝つ	印の分

裏どり:

• 収束の条件: 半束(join-semilattice)になっていること。要素ごとの最大、集合の和、いずれもこの形になる
• 状態ベースと操作ベース: 状態をまるごと送るか、操作だけを送るか。ここで実装したのは状態ベース(CvRDT)になる
• OR-Set の変種: 並行なら追加が勝つのが一般的だが、削除を勝たせる設計もある。使う場面で選ぶ
• タグの掃除: 印は増え続けるので、実装では全員が観測したことを確かめてから捨てる仕組みを足す
• 実際に使われている場所: Riak のデータ型、Redis の CRDT、Automerge や Yjs のような共同編集の基盤
• 共同編集: 文字列の CRDT(RGA、Logoot など)は、この章の集合よりさらに難しい。位置そのものを CRDT にする

簡略化したこと

• 文字列の CRDT なし: 共同編集で使う、順序のある列は扱わない。この章でいちばん重い題材になる
• 操作ベースなし: 状態をまるごと送る形だけ。操作を送る形は、届いた回数の管理が別に要る
• 印の掃除なし: ORSet の印は増え続ける。実装では捨てる仕組みが要る
• 通信なし: 合流は関数を呼ぶだけ。実際の伝播はゴシップなどが担う
• 並行実行なし: 単一のゴルーチンで動く前提にしている
• 時刻の生成なし: LWW の時刻は呼ぶ側が渡す。論理時計から取ってくる想定になる

参考資料

• A comprehensive study of Convergent and Commutative Replicated Data Types — Shapiro ら(2011)。型の分類と収束の条件
• CRDTs illustrated — 集合の設計がなぜ難しいかの解説
• 実装: distributed/crdt