差分の突き合わせ

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

クォーラムの読み修復には穴があった。読まれない key はいつまでも古いままになる。だから読みとは別に台どうしを突き合わせる仕組みが要る。全件送れば確実だが、違いが1件でも持ち物の数だけ通信が出る。要約を木にして根から降りると、比べる数が件数から離れる。1000件でも10万件でも、違いが1件なら21回で済む。

この章で作るもの

クォーラムの章で、読んだついでに古い台を直す仕組みを作った。だがそこには穴があると書いた。読まれない key はいつまでも古いままになる。誰も見ていない値ほど直らない。

だから、読みとは別に台どうしを突き合わせる仕組みが要る。台が落ちて戻ってきたとき、落ちていた間の書き込みを取り戻すのもこの仕組みになる。

素朴にやるなら、全部の key を送り合って比べればよい。確実だが、持ち物の数だけ通信が出る。100万件あって違いが1件でも、100万件送ることになる。しかも突き合わせは定期的に回すものなので、その無駄が繰り返し出る。

木にすると、この無駄が消える。まず全体の要約を1つだけ交換する。一致すれば、中身は見ずに「同じ」と分かる。違えば半分ずつに割って、違うほうだけ降りていく。

  区画 16、そのうち 11 番だけ中身が違う

                        [根] ✗
                   ┌──────┴──────┐
                 [0-7] ✓      [8-15] ✗          ← 左は一致。ここで打ち切る
                            ┌────┴────┐
                        [8-11] ✗   [12-15] ✓
                        ┌───┴───┐
                     [8-9] ✓  [10-11] ✗
                              ┌──┴──┐
                          [10] ✓  [11] ✗        ← ここだけ中身を送る

  比べた要約 9 個。送った中身 2 件(11 番の区画に入っている key の数)。

  全件で比べると

  key0 key1 key2 ... key31   32 件ぜんぶ送って、違ったのは 1 件だった

根が一致すれば、その下は全部一致している。違えば左右を比べて、違うほうだけ降りる。降りる回数は木の高さぶんで、送る中身は行き着いた区画だけになる

順に見ていく。

1. 要約を1つ交換すれば、同じかどうかは分かる: 一致したら中身は見なくてよい
2. 木にすると、違う枝だけ降りられる: 比べる数が、持ち物の数から離れる
3. 木は在処までしか言わない: どちらが新しいかは、別の判定が要る

① 要約を1つ交換すれば、同じかどうかは分かる

台が持っているのは key と値で、値の新しさはクォーラムと同じ版番号で決める。実際に quorum.Value と quorum.Newer をそのまま使っている:

// Store は1台が持つ key と値。値の新しさは [クォーラム](quorum)と同じ版番号で決める。
type Store struct {
	buckets int
	data    map[string]quorum.Value
}

// NewStore は区画の数を決めて台を作る。区画の数は2のべき乗にする。
func NewStore(buckets int) *Store {
	if buckets < 1 {
		buckets = 1
	}
	return &Store{buckets: buckets, data: map[string]quorum.Value{}}
}

// Buckets は区画の数を返す。
func (s *Store) Buckets() int { return s.buckets }

// Put は値を置く。版番号が古ければ何もしない。
func (s *Store) Put(key, data string, stamp int) {
	v := quorum.Value{Data: data, Stamp: stamp}
	s.data[key] = quorum.Newer(s.data[key], v)
}

// Get は値を返す。
func (s *Store) Get(key string) (quorum.Value, bool) {
	v, ok := s.data[key]
	return v, ok
}

// Keys は持っている key を名前順で返す。
func (s *Store) Keys() []string {
	out := make([]string, 0, len(s.data))
	for k := range s.data {
		out = append(out, k)
	}
	sort.Strings(out)
	return out
}

// Bucket は key が入る区画を返す。
func (s *Store) Bucket(key string) int { return int(hash(key) % uint64(s.buckets)) }

key は区画(バケツ)に割り振る。区画ごとに、中の key を名前順に並べて混ぜたものが、その区画の要約になる。

名前順にするのが効いている。台ごとに走査の順は違うが、名前順に並べてから混ぜるので、中身が同じなら必ず同じ要約になる。テストで、逆順に置いた台と昇順に置いた台の要約が一致することを固定した。

一致したら、それで終わりになる。1000件を持つ2台が同じ内容なら、交換するのは要約1つだけで済む。テストで、そのとき比べた数が 1、送った件数が 0 であることを固定した。

② 木にすると、違う枝だけ降りられる

区画の要約を葉にして、上へ木を組む:

// Tree は要約の木。葉が区画1つぶんの要約で、内側は子2つの要約になる。
type Tree struct {
	nodes  []uint64
	leaves int
}

// Tree はこの台の持ち物から木を作る。
//
// 葉は区画ごとに、その中の key を名前順に並べて混ぜたもの。名前順にするので、
// 走査の順が違っても同じ要約になる。内側は左右の子を混ぜるだけ。
func (s *Store) Tree() *Tree {
	t := &Tree{nodes: make([]uint64, 2*s.buckets), leaves: s.buckets}

	byBucket := make([][]string, s.buckets)
	for _, k := range s.Keys() {
		b := s.Bucket(k)
		byBucket[b] = append(byBucket[b], k)
	}
	for i, keys := range byBucket {
		var h uint64
		for _, k := range keys {
			v := s.data[k]
			h = mix(h, hash(k+"="+v.Data+"@"+itoa(v.Stamp)))
		}
		t.nodes[s.buckets+i] = h
	}
	for i := s.buckets - 1; i >= 1; i-- {
		l, r := t.nodes[2*i], t.nodes[2*i+1]
		if l == 0 && r == 0 {
			continue // 空どうしは空のまま。空の区画が一致することを保てる
		}
		t.nodes[i] = mix(l, r)
	}
	return t
}

// Root は全体の要約を返す。ここが一致すれば、中身は見なくてよい。
func (t *Tree) Root() uint64 { return t.nodes[1] }

// Depth は木の高さを返す。降りる回数はここで決まる。
func (t *Tree) Depth() int {
	d := 0
	for n := t.leaves; n > 1; n /= 2 {
		d++
	}
	return d
}

// Diff は2つの木を突き合わせ、違う区画の番号を返す。
//
// 根から降りて、一致したところで打ち切る。だから比べる数は
// 持ち物の数ではなく、違いの数と木の高さで決まる。
func Diff(a, b *Tree) (buckets []int, compared int) {
	if a.leaves != b.leaves {
		return nil, 0 // 区画の切り方が違うと比べようがない
	}
	var walk func(i int)
	walk = func(i int) {
		compared++
		if a.nodes[i] == b.nodes[i] {
			return // ここから下は全部同じ
		}
		if i >= a.leaves {
			buckets = append(buckets, i-a.leaves)
			return
		}
		walk(2 * i)
		walk(2*i + 1)
	}
	walk(1)
	return buckets, compared
}

Diff が根から降りる。一致したところで打ち切るので、比べる数は持ち物の数ではなく、違いの数と木の高さで決まる。

区画 1024(高さ 10)、1000件、そのうち1件だけ違う場合の実測がこうなる:

	比べた数	送った件数
全件で比べる	1000	1000
木で降りる	21	1

21 という数は、根1つと、各段で子2つずつ、1 + 2 × 10 から出ている。高さが決まれば、この数も決まる。

だから、持ち物が増えても比べる数は変わらない。テストで、1000件・10000件・100000件のどれでも、違いが1件なら比べる数が 21 のままであることを固定した。

  区画 1024 のまま、件数だけ増やす(違いは常に1件)

    1000 件 → 比較 21   送信  1     1区画あたり  約 1 件
   10000 件 → 比較 21   送信  8     1区画あたり 約 10 件
  100000 件 → 比較 21   送信 95     1区画あたり 約 98 件

  比べる数は高さで決まるので動かない。
  送る量は「1区画に何件入っているか」で決まるので、件数に比例して増える。
  → 件数が増えたら区画も増やす

件数を100倍にしても、比べる数は変わらない。増えるのは行き着いた区画の中身だけになる

違いの数を増やしたときも測れる。区画 1024、1000件で:

違いの数	比べた数	送った件数
0	1	0
1	21	1
4	69	6
16	201	21
64	561	92

違いが増えるほど降りる枝が増え、木の得は減っていく。ほとんど同じ相手ほど得が大きい。定期的に回して差を溜めないほうがよいのは、このためだ。

動かす

下のデモは区画 16 の小さい木で、違いのある区画を書き換えると、降りる経路が変わる様子が見える。全件で比べた場合の数も並べてある。

デモ差分の突き合わせ違い 1 件 / 32 件中

片方だけ書き換える

根

1 段目

2 段目

3 段目

区画0123456789101112131415

一致したので打ち切り違うので降りる見ていない

やり方

比べた数

送った件数

全件で比べる

32

32

木で降りる

9

2

違う区画は 11 番。要約を 9 個比べて、中身は 2 件だけ送れば直る。全件で比べると 32 件送ることになる

32 件の key を 16 区画に割り振り、区画ごとの要約を葉にして木を組んでいる。片方だけ値を 書き換えると、その区画から根までの要約が変わる。突き合わせは根から降りて、一致したところで 打ち切るので、見ないまま済む枝が大きく残る。違いを増やすほど降りる枝が増え、木の得は減っていく。

③ 木は在処までしか言わない

木が答えるのは「この区画が違う」までになる。どちらが新しいかは言わない:

// Result は突き合わせの結果。
type Result struct {
	// Buckets は違いのあった区画。
	Buckets []int
	// Compared は比べた要約の数。
	Compared int
	// Sent は実際に中身を送った件数。
	Sent int
	// Updated は書き換わった key。
	Updated []string
}

// Sync は木で違いを探し、違った区画の中身だけを交換して両方を同じにする。
//
// 木が言うのは「この区画が違う」までになる。どちらが新しいかは
// [クォーラム](quorum)の版番号で決める。木は在処しか教えてくれない。
func Sync(a, b *Store) Result {
	buckets, compared := Diff(a.Tree(), b.Tree())
	res := Result{Buckets: buckets, Compared: compared}
	if len(buckets) == 0 {
		return res
	}

	want := map[int]bool{}
	for _, i := range buckets {
		want[i] = true
	}
	for _, k := range union(a, b) {
		if !want[a.Bucket(k)] {
			continue
		}
		res.Sent++
		av, aok := a.Get(k)
		bv, bok := b.Get(k)
		best := quorum.Newer(av, bv)
		if !aok || av != best {
			a.data[k] = best
			res.Updated = append(res.Updated, k)
			continue
		}
		if !bok || bv != best {
			b.data[k] = best
			res.Updated = append(res.Updated, k)
		}
	}
	sort.Strings(res.Updated)
	return res
}

// CompareAll は木を使わずに全件突き合わせる(対照用)。
//
// 違いが1件でも、持ち物の数だけ送ることになる。
func CompareAll(a, b *Store) Result {
	res := Result{}
	for _, k := range union(a, b) {
		res.Compared++
		res.Sent++
		av, aok := a.Get(k)
		bv, bok := b.Get(k)
		best := quorum.Newer(av, bv)
		if !aok || av != best {
			a.data[k] = best
			res.Updated = append(res.Updated, k)
			continue
		}
		if !bok || bv != best {
			b.data[k] = best
			res.Updated = append(res.Updated, k)
		}
	}
	sort.Strings(res.Updated)
	return res
}

だから、行き着いた区画の中身を突き合わせて、版番号で決める。クォーラムの Newer をそのまま呼んでいる。木は探す道具で、決める道具ではない。

テストで、片方が古い値を持っている場合に両方が新しい値へそろうこと、そのあと古い値を置き直しても戻らないことを固定した。

この分業は他の章でも同じ形で出てくる。クォーラムでは重なりが「最新を持つ台が居る」までしか言わず、版番号で決めた。次のゴシップの章でも、「返事が無い」は相手の死か断線かを言わず、別の観測で区別することになる。見つける仕組みと決める仕組みは、たいてい別々に要る。

そしてもう1つ、この木には前提がある。区画の切り方が両側で同じでなければ、比べようがない。テストで、区画 16 の台と区画 32 の台では突き合わせが成立しないことを固定した。台を増やして担当範囲が変わると、木を作り直すことになる。

設計の観点

• 読みに直しを頼りきらない: 読まれない値は直らない。読みとは別の経路が要る
• 要約を先に交換する: ほとんどの場合は「同じ」で終わる。その場合の費用をいちばん小さくする
• 費用を持ち物の数から切り離す: 木の高さで決まる形にすれば、規模が変わっても比べる数は変わらない
• 区画の粒度を件数に合わせる: 区画を固定したまま件数を増やすと、行き着いた先で送る量が増える
• こまめに回すほど得が大きい: 差が溜まってから回すと、降りる枝が増えて木の意味が薄れる
• 見つけると決めるを分ける: 木は在処まで。どちらが正しいかは別の判定に任せる
• 両側で切り方をそろえる: 区画の割り当てが違うと、中身が同じでも全部違って見える

対照と実例

	全件を送る	木で降りる	読み修復
通信量(差が無いとき)	件数ぶん	要約1つ	0
通信量(1件違うとき)	件数ぶん	高さぶん + 1区画	1件
読まれない key	直る	直る	直らない
落ちて戻った台	直る	直る	読まれた分だけ
前提	無し	区画の切り方が同じ	読みが起きること

裏どり:

• Merkle(1979): Ralph Merkle の学位論文が出典。要約の木という道具自体はここから
• Dynamo(2007): 担当範囲ごとに木を持ち、隣の台と突き合わせる。台を増やすと担当範囲が変わり、木を作り直す必要があることが論文中で弱点として挙げられている
• Cassandra: nodetool repair が範囲ごとの木を作って突き合わせる。定期的に回す運用が前提になっている
• Riak: active anti-entropy として木を常時保持し、更新のたびに葉を更新する。作り直しの費用を分散させる形
• 同じ木の別の使い方: ブロックチェーンの merkle root は、ある取引が含まれていることを、全部を持たずに示すために使う。こちらは「どこが違うか」を探す道具で、あちらは「含まれている」を示す道具になる

簡略化したこと

• 木を作り直している: 突き合わせのたびに全部から組み直す。実物は更新のたびに葉と親だけを直す
• 区画の数が固定: 件数に合わせて増やす話は入れていない
• 担当範囲の移動なし: 台が増えたときに区画の割り当てが変わる話は コンシステントハッシュ に置いた
• 2台だけ: 何台のうち誰と誰を突き合わせるか、どの順で回すかは扱わない
• 削除なし: 消したことを表す印(tombstone)が無いので、片方で消しても復活する
• 回す間隔なし: いつ突き合わせるかは呼び出し側が決める

参考資料

• Merkle, Secrecy, Authentication, and Public Key Systems(1979)
• DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store(2007) — 4.7 節が anti-entropy
• Cassandra: Repair
• 実装: distributed/antientropy