クォーラム

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

レプリケーションではリーダーが最新を持っていた。リーダーを置かないと、どの台が最新かは聞いてみるまで分からない。担当 N 台のうち書きで W 台、読みで R 台の返事を待つとき、R + W > N なら読む集合と書く集合は必ず重なる。重なりが言うのは最新を持つ台が居ることだけで、どれが最新かは版番号が決める。

この章で作るもの

レプリケーションの章では、書き込みを受け付けるのはリーダー1台だった。何台の複製を待って確定とするかは選べたが、どこに最新があるかで迷うことはない。リーダーに聞けばよい。

リーダーを置かないと、その拠り所が消える。書き込みは複数の台に散り、どの台が最新を持っているかは聞いてみるまで分からない。全台に聞けば確実だが、それでは1台落ちただけで読めなくなる。

答えは台数の勘定になる。担当が N 台、書きで返事を待つのが W 台、読みで返事を待つのが R 台。この3つの数の間に R + W > N という関係を作ると、読む集合と書く集合が必ず1台以上を共有する。共有する台は書き込みを受けているので、R 台の返事の中に必ず最新が混ざる。

  N = 3(担当)  W = 2(書きで待つ)  R = 2(読みで待つ)

    担当    a       b       c        a が落ちている間に書いた
    書く    ✗     [v2]    [v2]       → 古い台は N - W = 1 台だけ

    読む    2台に聞く。選び方は3通りしかない
            a,b → v2      b,c → v2      c,a → v2
            どれを選んでも v2 が混ざる(12回読んで古い値は0回)


  R = 1, W = 1 に緩めると

    担当    a       b       c
    書く  [v2]      ✗       ✗        → 古い台が 2 台
    読む    1台に聞く。a なら v2、b なら v1、c なら v1

            12回読んで 8回が古い値


  数として言うと

    古い台は N - W 台。R > N - W なら埋めきれない。
    移項して   R + W > N

古い台は N - W 台しかない。R がそれより多ければ、R 台すべてを古い台で埋められない

順に見ていく。

重なりは台数の引き算で作れる: 古い台は N - W 台しかない。R をそれより多くすればよい
重なっても、どれが最新かは別に決める: 重なりは最新を持つ台が居ることまでしか言わない
緩めた quorum は重なりを手放す: 可用性のために担当外へ預けると、読みはそこに聞かない

① 重なりは台数の引き算で作れる

条件そのものは1行になる:


// Config は複製の本数と、返事を待つ台数を決める。
type Config struct {
	// N は1つの key を担当する台数(複製の本数)。
	N int
	// R は読みで返事を待つ台数。
	R int
	// W は書きで返事を待つ台数。
	W int
	// Sloppy は、担当が落ちているとき担当外の台を代役に使うかどうか。
	Sloppy bool
	// ReadRepair は、読んだついでに古い台を直すかどうか。
	ReadRepair bool
}

// Overlaps は、読む集合と書く集合が必ず1台以上重なるかを返す。
//
// N 台のうち W 台が書き込みを持っている。残りの古い台は N - W 台しかない。
// R > N - W なら、R 台すべてを古い台で埋めることはできない。
// 移項すると R + W > N になる。これがこの章のすべてになる。
func (c Config) Overlaps() bool { return c.R+c.W > c.N }

N 台のうち W 台が新しい値を持っている。だから古い台は N - W 台しかない。R がそれより多ければ、R 台の返事を古い台だけで埋めることはできない。移項すると R + W > N になる。

大事なのは、これが確率の話ではないことになる。「たいてい最新が混ざる」ではなく、どう選んでも混ざる。テストで、1台を古いまま残した状態で12回読み、聞く順がどう回っても古い値が返らないことを固定した。同じ手順を R=1, W=1 で踏むと、12回中8回が古い値になる。

R と W をどう振り分けるかは用途で決まる。合計さえ N を超えていればよいので、片方に寄せられる:

読みを速くしたい: R=1, W=N。読みは1台でよいが、書きは全台そろわないと通らない
書きを速くしたい: R=N, W=1。書きは1台でよいが、読みは全台に聞く
どちらも落ちてよい: R=W=過半数。1台落ちても読み書きが続く

R=W=過半数 は Raft の commit 規則と同じ形になる。あちらは1つのログを全員で合意する話で、こちらは合意しないまま台数だけで押し切る話だが、重なりを作るという一点は共通している。

② 重なっても、どれが最新かは別に決める

重なりが保証するのは「最新を持つ台が返事の中に居る」ことだけになる。返ってきた R 個の値のうちどれが新しいかは、まだ決まっていない:


// Value は1件の値。Stamp は書き込みごとに1つ増える版番号。
type Value struct {
	Data  string
	Stamp int
}

// Newer は2つの値のうち新しいほうを返す。版番号が大きいほうが勝つ。
//
// 重なりが保証するのは「最新を持つ台が返事の中に居る」ことだけで、
// 返ってきた値のどれが最新かは、この判定が決める。
func Newer(a, b Value) Value {
	if b.Stamp > a.Stamp {
		return b
	}
	return a
}

版番号で決める。書き込みごとに1つ増える数で、大きいほうが新しい。古い書き込みが遅れて届いても、この判定を通すので値は戻らない。テストで、新しい値を入れた後に古い値を入れても上書きされないことを固定した。

読みの側はこうなる:


// ReadResult は読みの結果。
type ReadResult struct {
	// OK は R 台ぶんの返事が集まったか。
	OK bool
	// Asked は実際に返事をもらった台。
	Asked []string
	// Value は返事の中でいちばん新しい値。
	Value Value
	// Found は値が見つかったか。
	Found bool
	// Repaired は読み修復で直した台。
	Repaired []string
}

// Get は key を読む。担当のうち R 台に聞いて、いちばん新しい値を返す。
//
// 誰が先に返事するかは決まっていないので、聞く順は読みの回数で回す。
// R + W > N なら、この順がどう回っても最新を持つ台が必ず混ざる。
func (c *Cluster) Get(key string) ReadResult {
	home := c.Home(key)
	c.reads++

	var asked []string
	var got []Value
	for i := 0; i < len(home) && len(asked) < c.cfg.R; i++ {
		n := home[(c.reads+i)%len(home)]
		if c.down[n] {
			continue
		}
		asked = append(asked, n)
		v, _ := c.nodes[n].Get(key)
		got = append(got, v)
	}

	res := ReadResult{Asked: asked}
	if len(asked) < c.cfg.R {
		c.logf(key + " は返事が足りない(" + itoa(len(asked)) + "/" + itoa(c.cfg.R) + ")ので読めない")
		return res
	}
	res.OK = true

	best := Value{}
	for _, v := range got {
		best = Newer(best, v)
	}
	if best.Stamp > 0 {
		res.Value, res.Found = best, true
	}

	if c.cfg.ReadRepair && res.Found {
		for i, n := range asked {
			if got[i].Stamp < best.Stamp {
				c.nodes[n].put(key, best)
				res.Repaired = append(res.Repaired, n)
			}
		}
	}
	c.logf(key + " を " + itoa(len(asked)) + " 台に聞いた → " + res.Value.Data + "(版 " + itoa(res.Value.Stamp) + ")")
	return res
}

聞く順を読みの回数で回しているのは、誰が先に返事するかは決まっていないからだ。実物では最初に返ってきた R 台を採るので、どの台が選ばれるかは毎回違う。ここを固定してしまうと、重なりの保証を試したことにならない。

そして、古い台をそのままにしておく理由は無い。R 台に聞いて最新が分かったなら、そのついでに古かった台へ書き戻す。これが読み修復になる。テストで、読みを3回通すと古い台が消えることを固定した。

ただしこれには穴がある。読まれない key はいつまでも古いままになる。誰も見ていない値ほど直らないので、実物は読み修復とは別に、台どうしを定期的に突き合わせる仕組みを持つ。

③ 緩めた quorum は重なりを手放す

担当 N 台のうち2台が落ちたら、W=2 の書き込みは通らない。ここで「担当でなくてもいいから、誰かに預かってもらう」と決めると書き込みは通る:


// Handoff は、代役が預かっているぶんを戻ってきた担当へ渡す。
//
// これが済むまで、値は担当の上に無い。読みは担当にしか聞かないので、
// R + W > N でも古い値が返りうる。緩めた quorum が手放したのはこの重なりになる。
func (c *Cluster) Handoff() int {
	moved := 0
	for _, name := range c.names {
		n := c.nodes[name]
		var keep []Hint
		for _, h := range n.hints {
			if c.down[h.Owner] {
				keep = append(keep, h)
				continue
			}
			c.nodes[h.Owner].put(h.Key, h.Value)
			moved++
			c.logf(name + " が預かっていた " + h.Key + " を " + h.Owner + " へ渡した")
		}
		n.hints = keep
	}
	return moved
}

担当外の台を代役に立てて預かってもらい、返事の数に数える。担当が戻ったら渡す。書き込みが止まらなくなるので、可用性は上がる。

だが、値は担当の上に無い。そして読みは担当にしか聞かない。

  担当 a, b が落ちている状態で書く(N=3, R=2, W=2, 代役あり)

    担当 →    a       b       c       担当外 →   d        e
              ✗       ✗     [v2]                 預かり    預かり
                                                (a のぶん)(b のぶん)

    返事は 3(c と d と e)なので W = 2 を満たし、書き込みは通る

  a, b が戻ってから読む

    担当 a, b, c のうち 2 台に聞く
      a,b → v1 ✗ 古い      b,c → v2      c,a → v2

    R + W = 4 > 3 なのに、6回中2回が古い値
    → 預けた先が読む集合の外に居る

  受け渡しが済むと

    d, e の預かりが a, b へ渡る → 担当3台が v2 → 6回中0回

返事の数は満たしているが、値が担当の上に無い。読む集合と書く集合が別の場所を指している

テストで、代役を立てた直後は R+W>N でも古い値が返ること、受け渡しが済むと返らなくなることを、両方固定した。

これは実装の粗さではなく、緩めた quorum が実際に持っている性質になる。台数の条件を満たしているのは「返事の数」であって「担当の中での重なり」ではない。買っているのは書き込みが失われないことで、手放しているのは読めば最新が見えることになる。

そして、そもそも「担当が落ちた」という判断自体が誤りうる。断線しただけの台を落ちたと見なせば、要らない代役が立つ。障害検知の精度が、そのままこの仕組みの精度になる。判断がなぜ誤りうるかは、後のゴシップの章で扱う。

動かす

下のデモは5台の系を動かす。R と W を変えると重なりの有無が切り替わり、台を落としてから書き、戻してから何度も読むと、古い値が返るかどうかが見える。代役を使う設定にすると、R+W>N のまま古い値が返る状態を作れる。

デモクォーラムR+W = 4 > N = 3

R 2 W 2

a担当v1

b担当v1

c担当v1

d担当外空

e担当外空

直近の読みまだ読んでいない

担当がそろっている。どの台に聞いても最新が返る。台を落としてから書き、戻してから読むと差が出る

(まだ何もしていない)

担当は key ごとに決まる 3 台で、この key では a・b・c。書き込みは担当へ送って W 台の返事で成功、読みは担当のうち R 台に聞いていちばん新しい値を返す。聞く順は読むたびに回るので、どの台に当たるかは毎回違う。担当を 1 台落として書き、戻してから読むと、R + W が N を超えていれば古い値は返らない。代役に預ける設定にすると、返事の数は満たすのに値が担当の外に残り、受け渡しまで古い値が返る。

設計の観点

保証を確率から台数へ移す: 「たいてい大丈夫」を「どう選んでも大丈夫」に変えられる場所を探す
合計だけ守って配分は用途で決める: R と W の振り分けが、読み重視か書き重視かの目盛りになる
保証の範囲を正確に言う: 重なりは最新の在処までしか言わない。判定と修復は別に要る
緩めるときは何を手放したか書く: 代役は可用性を買うが、読みの保証を手放している
直る道を読みに頼りきらない: 読まれない値は直らないので、別の突き合わせが要る
検知の精度が保証の精度になる: 落ちたという判断を間違えると、条件を満たしても最新が読めない

対照と実例

	リーダーあり(replication)	クォーラム	緩めたクォーラム
最新の在処	リーダーが持つ	R 台の返事に混ざる	担当の外に居ることがある
書きの受け口	1台	担当 N 台のどれでも	生きている台のどれでも
リーダー故障	昇格が要る	起きない	起きない
読みの保証	リーダーから読めば最新	`R + W > N` なら最新	受け渡しが済むまで無い
買うもの	単純さ	落ちても読み書きできる	書き込みが失われない

裏どり:

Dynamo(2007): Amazon の論文。N/R/W を key ごとに選ばせる形と、代役への預けと受け渡し(sloppy quorum / hinted handoff)の出所
Cassandra: ONE / QUORUM / ALL などを読み書きごとに指定する。QUORUM どうしなら R+W>N を満たす
DynamoDB: 読みは既定が結果整合で、強い一貫性を求めるときだけ明示する。読み1回のコストが変わる
Riak: n_val / r / w をバケットごとに設定できる。Dynamo にいちばん近い形
緩めた quorum は quorum ではない: Kleppmann は、返事の数を満たしていても担当の中で重なっていない以上、これは耐久性の保証であって一貫性の保証ではないと書いている
満たしても崩れる場合: 同時書き込み、W に届かなかった書き込みが一部の台に残る、台を復元したときに値が消える。台数の条件は必要ではあるが十分ではない

簡略化したこと

同時書き込みの衝突なし: 版番号は全体で一意なので、並行した書き込みが起きない。実物はベクタークロックで並行を検出し、CRDT のようなまとめ方か、両方残して読み手に選ばせる形を採る
遅延なし: 届くか届かないかの2択で、遅れて届く場合は扱わない
担当の決め方は固定: 台の増減で担当が移る話はコンシステントハッシュに置いた
突き合わせなし: 読み修復だけで、Merkle 木による定期的な差分検出は入れていない
書き込みの取り消しなし: W に届かなくても、書けた台の値は残したまま
代役の選び方は輪の続き: 実物は負荷や場所を見て選ぶ

参考資料

Dynamo: Amazon's Highly Available Key-value Store — DeCandia ら(2007)。N/R/W と代役への預けの出所
Kleppmann, Designing Data-Intensive Applications 5章(Leaderless Replication)。R+W>N を満たしても崩れる場合の一覧
Cassandra: Consistency levels — 読み書きごとに待つ台数を選ぶ
実装: distributed/quorum

クォーラム ​

この章で作るもの ​

① 重なりは台数の引き算で作れる ​

② 重なっても、どれが最新かは別に決める ​

③ 緩めた quorum は重なりを手放す ​

動かす ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​