leader election
実装:
orchestration/leaderelection// 実行:go test ./orchestration/leaderelection/
コントローラを冗長化したいが、同時に働かれては困る。置き場に1つオブジェクトを作り、持っている者だけが働く形にする。難しいのは時計が共有されていないことで、待つ側は絶対時刻でなく自分の時計で測った経過だけを見る。そして降りるほうが先でなければならない。2つの猶予の大小が逆だと、逆転した幅ぶんだけ持ち主が2人になる。
この章で作るもの
この編のコントローラは、ずっと1つだけ動いている前提だった。調整ループもスケジューラも、自分が唯一の判断者だと思って現状を数え、差を埋めていた。
だがコントローラ自身も落ちる。載っているノードが死ぬこともあるし、更新のたびに止まりもする。落ちている間、誰も調整しない。壊れた Pod は作り直されないし、増やせという指示は無視される。だから複数台で動かしておきたい。
ところが複数台が同時に調整すると、今度は別の問題が起きる。2つのコントローラが同じ「Pod が2個足りない」を見て、それぞれ2個ずつ作る。冗長化はしたいが、同時に働いてほしくはない。
答えは、置き場に1つオブジェクトを作って、それを持っている者だけが働く形になる。持ち主は定期的に更新し、他は更新が止まったのを見て奪う。分散ロックの章で見たリースと同じ形だが、ここでは奪う側と降りる側の時間関係が主題になる。
持ち主 c1 が t=6 に置き場へ届かなくなった。以降 c1 は更新できない
猶予10 / 期限15 (降りるのが先)
c1 │████████████ 持ち主 ████│ │
│ └ t=16 自分から降りる │
c2 │ │████ 持ち主 ████
│ └ t=22 奪う
├─── 誰も居ない 6 ───┤
猶予20 / 期限15 (奪うのが先)
c1 │████████████ 持ち主 ██████████████████│
│ └ t=26 自分から降りる
c2 │ │████████████████ 持ち主 ████
│ └ t=22 奪う
├─ 2人 4 ─┤順に見ていく。
- 時刻は共有できないが、経過は共有できる: 他人の書いた時刻は比べられない。変化を見てからの経過だけを見る
- 降りるほうが先: 猶予を期限より短くしておく。逆だと、逆転した幅ぶん重なる
- それでも重なりは消えない: だから調整ループが冪等でなければならない
① 他人の時計を読まない
まず、3つの時間を決める:
// Config は3つの時間で leader election の性質を決める。
//
// 大小の関係が正しさそのものになっている。RenewDeadline が LeaseDuration より
// 短くなければ、持ち主が降りるより先に他が奪ってしまう。
type Config struct {
// LeaseDuration は、変化を見なくなってから他が奪ってよいと判断するまでの長さ。
LeaseDuration int
// RenewDeadline は、持ち主が更新に失敗し続けたとき自分から降りるまでの猶予。
RenewDeadline int
// RetryPeriod は更新や奪取を試みる間隔。
RetryPeriod int
}
// Safe は重なりが起きえない設定かを返す。
func (c Config) Safe() bool {
return c.RenewDeadline < c.LeaseDuration && c.RetryPeriod < c.RenewDeadline
}
// Default は実物の既定値と同じ比を持つ設定を返す(15 / 10 / 2)。
func Default() Config {
return Config{LeaseDuration: 15, RenewDeadline: 10, RetryPeriod: 2}
}実物の既定値は 15 秒 / 10 秒 / 2 秒になっている。Safe が見ているのはこの大小関係だけで、これがそのまま正しさの条件になる。
次が置き場のオブジェクトになる:
// Lease は置き場にある1つのオブジェクト。これを持っている者だけが働く。
//
// Version が更新のたびに増える。待つ側は、書かれた時刻ではなくこの値の
// 変化を見る。時刻は他人の時計の値なので比べられないが、変化したかどうかは
// 自分の時計で測れる。
type Lease struct {
Holder string
Version int
}
type cand struct {
name string
leader bool
lastRenew int // 自分が最後に更新できた時刻(自分の時計)
obsVersion int // 最後に見た Version
obsAt int // それを見た時刻(自分の時計)
nextAct int
down bool
}
// Sim は複数の候補が1つの Lease を取り合う様子を、時刻を1つずつ進めながら再現する。
type Sim struct {
cfg Config
now int
lease Lease
cands []*cand
// Overlap は2人以上が自分を持ち主だと思っていた時刻の数。
Overlap int
// DoubleActs は、その重なりによって二重になった操作の回数。
DoubleActs int
// Vacant は誰も持ち主が居なかった時刻の数。安全にした代償がここに出る。
Vacant int
Log []string
}
// New は名前の候補たちで選出を始める。名前順に行動するので結果は決定的になる。
func New(cfg Config, names ...string) *Sim {
s := &Sim{cfg: cfg}
sorted := append([]string(nil), names...)
sort.Strings(sorted)
for _, n := range sorted {
s.cands = append(s.cands, &cand{name: n, obsAt: 0, nextAct: 0})
}
return s
}
// Now は現在の論理時刻を返す。
func (s *Sim) Now() int { return s.now }
// Holder は置き場のオブジェクトが誰のものになっているかを返す。
func (s *Sim) Holder() string { return s.lease.Holder }
// Believers は「自分が持ち主だ」と思っている候補の名前を返す。
// これが2つ以上になっている時刻が、この章で数えたいものになる。
func (s *Sim) Believers() []string {
var out []string
for _, c := range s.cands {
if c.leader {
out = append(out, c.name)
}
}
return out
}
// Partition は候補を置き場から切り離す。読むことも書くこともできなくなる。
func (s *Sim) Partition(name string) {
if c := s.find(name); c != nil && !c.down {
c.down = true
s.logf(name + " が置き場に届かなくなった")
}
}
// Heal は切り離しを解く。
func (s *Sim) Heal(name string) {
if c := s.find(name); c != nil && c.down {
c.down = false
s.logf(name + " が置き場に届くようになった")
}
}Lease に Version しか入れていないのが、この章でいちばん言いたいところになる。実物のオブジェクトには更新時刻も入っているが、待つ側はそれを読まない。読んでも使えないからだ。
その時刻は持ち主の時計で刻まれた値であり、自分の時計とどれだけずれているかは分からない。2秒ずれていれば2秒ぶん誤るし、ずれていることに気づく方法も無い。時刻を共有するには時計を合わせる必要があり、時計を合わせる仕組み自体が壊れたり遅れたりする。
だから比べない。代わりに Version が変わったかどうかだけを見て、「最後に変化を見てから、自分の時計でどれだけ経ったか」で判断する。経過時間なら自分の時計だけで測れる。時刻は共有できないが、経過は共有できる。
各候補が obsAt を持っているのがそれで、これは自分のローカルな時刻になる。実物の実装も同じで、リース内の時刻ではなく、変化を観測したローカル時刻を記録して比べている。
② 降りるほうが先
行動の中身がこうなる:
// Tick は時刻を1つ進める。候補は名前順に行動する。
func (s *Sim) Tick() {
for _, c := range s.cands {
s.act(c)
}
s.tally()
s.now++
}
// act は候補1人ぶんの行動。
//
// 観測が先で、判断が後になっている。この順序でないと、切り離しから復帰した
// 候補が古い観測のまま「期限が切れている」と判断して奪ってしまう。
func (s *Sim) act(c *cand) {
if c.down {
// 届かないので、読むことも更新もできない。できるのは降りることだけ。
if c.leader && s.now-c.lastRenew >= s.cfg.RenewDeadline {
c.leader = false
s.logf(c.name + " は更新できないまま猶予 " + itoa(s.cfg.RenewDeadline) +
" を使い切った。自分から持ち主を降りる")
}
return
}
// ① 観測。Version が変わっていれば、その変化を見た時刻を自分の時計で記録する。
if s.lease.Version != c.obsVersion {
c.obsVersion = s.lease.Version
c.obsAt = s.now
}
if s.now < c.nextAct {
return
}
c.nextAct = s.now + s.cfg.RetryPeriod
// ② 判断。
if c.leader {
if s.lease.Holder != c.name {
// 更新しようとしたら、すでに他人のものになっていた。
c.leader = false
s.logf(c.name + " は更新しようとして、持ち主が " + s.lease.Holder + " に変わっているのを見た。降りる")
return
}
s.write(c)
return
}
if s.lease.Holder == "" || s.now-c.obsAt >= s.cfg.LeaseDuration {
// 自分の時計で LeaseDuration ぶん、変化を見ていない。奪う。
prev, waited := s.lease.Holder, s.now-c.obsAt
s.lease.Holder = c.name
s.write(c)
c.leader = true
if prev == "" {
s.logf(c.name + " が持ち主になった")
} else {
s.logf(c.name + " が " + itoa(waited) + " のあいだ変化を見なかったので " + prev + " から奪った")
}
}
}
// write は Version を進め、自分の観測も同時に更新する。
func (s *Sim) write(c *cand) {
s.lease.Version++
c.lastRenew = s.now
c.obsVersion = s.lease.Version
c.obsAt = s.now
}
// tally はこの時刻の重なりと空位を数える。
//
// 重なっている間、持ち主だと思っている全員が働く。冪等な操作なら結果は
// 変わらないが、外部への操作は人数ぶん実行される。
func (s *Sim) tally() {
n := len(s.Believers())
switch {
case n == 0:
s.Vacant++
case n > 1:
s.Overlap++
s.DoubleActs += n - 1
}
}観測が先で、判断が後になっている。この順序を逆にすると壊れる。長く切り離されていた候補が復帰した瞬間、自分の観測は何十も古い。判断が先だと「期限をとっくに過ぎている」と見えて、元気に働いている持ち主から奪ってしまう。観測を先に置けば、復帰した瞬間に変化を見るので、そこから測り直すことになる。テストで、40 以上切り離されていた候補が復帰しても奪わないことを固定した。
そして大小の関係になる。持ち主が置き場に届かなくなったとき、2つの時計が別々に走り出す。
持ち主のほうは、最後に更新できた時刻から RenewDeadline を数える。使い切ったら自分から降りる。これは他の誰とも相談せずにできる判断で、届かなくても実行できる。
待つ側は、最後に変化を見た時刻から LeaseDuration を数える。使い切ったら奪う。
この2つは同じ瞬間から数え始まる。持ち主が最後に更新した時刻に、待つ側もその変化を見ているからだ。同じ起点から数えるので、短いほうが先に起きる。RenewDeadline を短くしておけば、降りるほうが必ず先になる。
テストで、既定の設定なら重なりが 0 になること、RenewDeadline を 20 にすると重なりが 4 になることを固定した。4 は 20 と 15 の差ではなく、試行間隔の刻みで丸められた実際の幅になる。
代償もテストで固定してある。安全な設定では、降りてから奪われるまでの間、誰も持ち主でない時間ができる。この空位の間、調整は止まる。重なりと空位はどちらかしか消せない。速く引き継ぎたければ期限を短くするしかなく、短くすれば一瞬の遅延でも奪われるようになる。
③ それでも重なりは消えない
ここまでの仕組みは、置き場に届かなくなった場合を扱っている。届いているのに動けない場合は扱えていない。
持ち主のプロセスがガベージコレクションで長く止まったとする。止まっている間、猶予を数える処理も動かない。待つ側から見れば更新が止まって見えるので、期限を過ぎたところで奪う。そのあと持ち主が動き出すと、自分が降りるべきだったことにまだ気づいていない。次に置き場を読むまでの間、自分は持ち主だと思って1手打つ。
分散ロックの章で見たのと同じ形になっている。あの章の答えはフェンシングトークンで、資源の側が古い番号の書き込みを拒む仕掛けだった。だがコントローラが行う操作にはトークンが付かない。Pod を作る操作に「私は第3代の持ち主です」とは書けない。置き場のオブジェクト自体は版で守られているが、守られているのはそのオブジェクトへの書き込みだけで、持ち主が外に対して行う操作は守られない。
だから重なりは消えない。消えないという前提で設計されている。
ここで 調整ループに戻ることになる。あの章の中心は、命令ではなく現状を見て差を埋める形だった。同じ調整が二重に走っても、2人とも同じ現状を見て同じ差を計算するので、片方が埋めれば片方の差は 0 になる。何度実行しても結果が変わらないので、重なっても壊れない。
冪等でない操作は、この保護を受けられない。外部の API を叩いて課金する、通知を送る、といった操作は人数ぶん実行される。デモで数えている二重操作がそれになる。leader election は重なりを短くはするが、無くしはしない。無くならない前提で、外に出る操作の側を冪等にしておく必要がある。
動かす
下のデモは、持ち主を置き場から切り離して何が起きるかを見る。設定を切り替えると、同じ切り離しから違う結果が出る。安全な側は空位ができ、危険な側は重なりができる。重なっている間、二重に実行された操作の数が数えられていく。切り離しを解けば、古い持ち主は次に置き場を読んだ瞬間に降りる。
緑が「自分が持ち主だ」と思っている時刻、黄が届かないまま持ち主だと思っている時刻、破線が置き場に 届かない時刻。いちばん下の帯が全体の様子で、 赤が2人とも持ち主だと思っている時刻、黄が誰も持ち主でない時刻。上下で違うのは猶予の長さだけで、 切り離す時刻も期限も同じになっている。繋ぎ直すと、古い持ち主は次に置き場を読んだ瞬間に降りるので、 重なりはそこで終わる。届かない間は降りる以外に取れる行動が無い、というのがこの仕組みの土台になっている。
設計の観点
- 絶対時刻を比べない: 分散した相手の時刻は使えない。使えるのは自分の時計で測った経過だけ
- 観測を先に、判断を後に: 順序を逆にすると、古い観測のまま判断して生きている持ち主から奪う
- 同じ起点から数える: 降りる側と奪う側が同じ瞬間から数え始めるので、猶予の大小だけで順序が決まる
- 重なりと空位の取引: どちらかしか消せない。速い引き継ぎと安全な引き継ぎは同じ目盛りの両端になっている
- 単独では判断できる: 降りる判断だけは相手と通信せずにできる。届かない状況で唯一取れる行動が「やめる」であることに意味がある
- 調整ループが最後の砦: 重なりは消えないので、二重に走っても壊れない形が要る。level-triggered はここでも効いている
- 分散ロックとの違い: あちらはフェンシングトークンで資源側が守る。こちらはトークンを運べないので、操作の冪等性に頼る
対照と実例
| 単独で動かす | 複数を同時に動かす | leader election | |
|---|---|---|---|
| 落ちたとき | 誰も調整しない | 残りが続ける | 期限のあと引き継ぐ |
| 二重の調整 | 起きない | 常に起きる | 引き継ぎのときだけ |
| 引き継ぎの速さ | 再起動を待つ | 不要 | 期限ぶん待つ |
| 必要な性質 | なし | 操作が冪等 | 操作が冪等(重なりが残るため) |
| 空位 | 落ちている間ずっと | なし | 降りてから奪われるまで |
裏どり:
- Lease オブジェクト: 選出には
coordination.k8s.io/v1の Lease を使う。holderIdentityとrenewTime、leaseDurationSecondsを持つ - 既定値:
leaseDuration15 秒、renewDeadline10 秒、retryPeriod2 秒。この大小が保たれない設定は起動時に拒否される - 観測はローカル時刻で: 実装は
observedTimeをローカルに記録し、リース内のrenewTimeを直接は比べない - 重なりは仕様: 公式の説明も、GC ポーズなどで2つの持ち主が短時間できうると認めている。防ぐのではなく短くする仕組みになっている
- kube-controller-manager と kube-scheduler: どちらも複数台で動かし、この仕組みで1台だけが働く
簡略化したこと
- 合意なし: 置き場が唯一の真実であることを前提にする。その置き場自体の合意は Raft が担う
- 楽観ロックなし: 実物は版を見て書き込みを弾く。ここでは同時書き込みが起きない順序で動かしている
- 停止を再現しない: 切り離しは扱うが、プロセスが止まって復帰する場面は扱わない。③ の話は文章だけになっている
- 時計のずれを注入しない: ずれても壊れないことを設計で示すだけで、ずれた時計そのものは持たせていない
- 働く中身なし: 持ち主が何をするかは扱わない。二重になった操作を数えるだけ
参考資料
- Coordinated Leader Election — Lease オブジェクトと選出の仕組み
- client-go: leaderelection — 既定値と、重なりが起きうることの注記
- 実装: orchestration/leaderelection