distributed-lock(分散ロックとフェンシングトークン)

1 台なら mutex で排他できるが、複数ノードでは持ち主がいつクラッシュするか分からない。持ったまま死なれたら永遠に解放されないので、ロックにリース(有効期限)を付けて自動失効させる。だが GC の停止や遅延で、古い持ち主と新しい持ち主が同時に「持っているつもり」になり、二重取得が起きる。これを防ぐのがフェンシングトークンで、資源側が古い番号の書き込みを拒む。

この章で作るもの

排他制御は 1 台なら簡単だ。mutex を取って、使って、離す。分散させた途端に難しくなるのは、参加者がいつでも落ちるからだ。ロックを持ったまま落ちられたら、誰も解放できず全体が止まる。かといって「落ちたら奪う」には「本当に落ちたか」を確実には知れない(部分故障。分散はなぜ難しいか参照)。

   時刻 →
   A: [取得 token=1]───write(1)✓───[  GC 停止 …  ]───────[再開 write(1)]
                                    ↑リース失効                  ✗ 1<2 で拒否
   B:                         [取得 token=2]──write(2)✓
   ─────────────────────────────────────────────────────────────────
   資源 row-42:   max=1 "A"        →  max=2 "B"           →  "B" のまま(守られた)

リース失効による二重取得と、フェンシングトークンによる防御。A がロックを取り(token=1)、GC 停止している間にリースが失効。B が取り(token=2)書き込む。A が再開して古い token=1 で書こうとしても、資源は max=2 より小さいので拒否する。破壊されない

順に見ていく。

1. リース = 失効するロック: 持ち主のクラッシュに耐えるため、ロックは時間で自動失効する
2. 失効の罠 = 二重取得: GC 停止や遅延で「持っているつもり」の古い持ち主と新しい持ち主が同時に存在しうる
3. フェンシングトークン = 単調増加番号: 資源側が古い番号の書き込みを弾く。これで二重取得が起きても破壊を防ぐ

① リース: 失効するロック

ロックサービスは 1 本のロックを貸し出す。持ち主が死んでも詰まらないよう、貸すときにリース(有効期限)を付け、時間が過ぎたら自動的に空きへ戻す。そして貸すたびに単調増加するフェンシングトークンを発行する。これが後で持ち主を見分ける決め手になる:

// LockService は 1 本のロックを貸し出すサービス。論理時計を持ち、リースで
// 自動失効させ、貸すたびに単調増加するフェンシングトークンを発行する。
// 合意は取れている前提。実際は Raft 等の上に載せる。
// ここでは 1 本のロックの、リースとトークンの意味論だけを取り出す。
type LockService struct {
	clock     int    // 論理時刻
	holder    string // 現在の持ち主("" なら空き)
	expiry    int    // 現在のリースが失効する時刻
	token     int64  // 現在の持ち主に発行したトークン
	nextToken int64  // 次に発行するトークン(単調増加)
}

// New は空のロックサービスを作る。トークンは 1 から始まる。
func New() *LockService {
	return &LockService{nextToken: 1}
}

// Now は現在の論理時刻を返す。
func (s *LockService) Now() int { return s.clock }

// Tick は論理時刻を d だけ進める。時間が進むとリースが失効しうる。
func (s *LockService) Tick(d int) {
	if d > 0 {
		s.clock += d
	}
}

// refresh はリースが失効していたらロックを空きに戻す。
func (s *LockService) refresh() {
	if s.holder != "" && s.clock >= s.expiry {
		s.holder = ""
	}
}

// Acquire はロックの取得を試みる。空き(または失効済み)なら client に lease だけ
// 貸し、新しいフェンシングトークンを発行して (token, true) を返す。他が保持中なら
// (0, false)。トークンが**取得のたびに増える**のが肝——後で持ち主を見分ける鍵になる。
func (s *LockService) Acquire(client string, lease int) (int64, bool) {
	s.refresh()
	if s.holder != "" {
		return 0, false // 誰かが保持中(まだ失効していない)
	}
	if lease < 1 {
		lease = 1
	}
	s.holder = client
	s.expiry = s.clock + lease
	s.token = s.nextToken
	s.nextToken++
	return s.token, true
}

// Renew は現在の持ち主がリースを延長する(ハートビート)。持ち主でなければ false。
// トークンは変わらない(同じ保持の延長だから)。
func (s *LockService) Renew(client string, lease int) bool {
	s.refresh()
	if s.holder != client {
		return false
	}
	if lease < 1 {
		lease = 1
	}
	s.expiry = s.clock + lease
	return true
}

// Release は持ち主が自発的にロックを手放す。持ち主でなければ何もしない。
func (s *LockService) Release(client string) {
	s.refresh()
	if s.holder == client {
		s.holder = ""
	}
}

// Holder は現在の持ち主とそのトークンを返す(失効を反映)。空きなら ("", 0)。
func (s *LockService) Holder() (string, int64) {
	s.refresh()
	if s.holder == "" {
		return "", 0
	}
	return s.holder, s.token
}

// Expiry は現在のリースの失効時刻を返す(観察用)。
func (s *LockService) Expiry() int { return s.expiry }

Acquire のたびに nextToken が増えるのがポイント。Renew(ハートビート)では増えない。同じ保持の延長だからだ。持ち主は定期的に Renew してリースを延ばし、死ねば Renew が止まってリースが失効し、他が取れるようになる。

ここで注意: 「1 本のロックを誰に貸すか」の合意そのものは、実際には Raft や Zookeeper/etcd の上に載る。本章はその合意は取れている前提で、リースとトークンの意味論だけを取り出している。

② 二重取得の罠

リースは「持ち主が死んだ場合」を救う。だが、死んでいないのに止まっている場合はどうか。よくあるのが GC の一時停止だ。持ち主のプロセスが数秒間 stop-the-world で止まると、その間ハートビートが送れず、リースが失効する。別ノードがロックを取る。やがて元の持ち主が、自分がまだロックを持っていると信じたまま何事もなかったように再開する。

いまや 2 つのノードが同じロックを持っているつもりでいる。両方が資源に書けば、片方の更新がもう片方を上書きして壊す。リースだけでは、この二重取得を防げない。リースを短くしても、短くするほど正当な持ち主まで誤って失効させやすくなるだけで、長さの調整では根本解決にならない。

③ フェンシングトークン: 資源側で古い書き込みを弾く

解決は、資源側に持たせる。保護する資源が、書き込みに添えられたフェンシングトークンを検査する。今まで受理した最大トークンを覚えておき、それより小さいトークンの書き込みを拒否する:

// Resource はロックで守りたい共有資源(DB 行・ファイル・外部 API など)。
// フェンシングが有効なら、**今まで見た最大トークン以上**の書き込みしか受けない。
// 出遅れた古い持ち主(小さいトークン)の書き込みは弾かれ、二重取得による破壊を防ぐ。
type Resource struct {
	Name     string
	fenced   bool   // フェンシングを有効にするか
	data     string // 現在の値
	maxToken int64  // これまで受け入れた最大のフェンシングトークン
	Rejected int    // フェンシングで弾いた回数(観察用)
	writes   int    // 受け入れた書き込み回数(観察用)
}

// NewResource はフェンシング有効のリソースを作る。
func NewResource(name string) *Resource {
	return &Resource{Name: name, fenced: true}
}

// NewUnfencedResource はフェンシング無効のリソースを作る(比較用——古い持ち主の
// 書き込みを素通しさせ、破壊が起きる様子を見せる)。
func NewUnfencedResource(name string) *Resource {
	return &Resource{Name: name, fenced: false}
}

// Write はトークン付きの書き込みを試みる。フェンシング有効なら token が今まで見た
// 最大値以上のときだけ受理する。古いトークンは拒否して true でなく false を返す。
// フェンシング無効なら常に受理する(=古い持ち主が新しい値を上書きしてしまう)。
func (r *Resource) Write(token int64, value string) bool {
	if r.fenced && token < r.maxToken {
		r.Rejected++
		return false // フェンス落ち: 古い持ち主の書き込み。破壊を未然に防ぐ
	}
	if token > r.maxToken {
		r.maxToken = token
	}
	r.data = value
	r.writes++
	return true
}

// Data は現在の値を返す。
func (r *Resource) Data() string { return r.data }

// MaxToken はこれまで受理した最大トークンを返す。
func (r *Resource) MaxToken() int64 { return r.maxToken }

// Fenced はフェンシングが有効かを返す。
func (r *Resource) Fenced() bool { return r.fenced }

これで二重取得が起きても安全だ。B が token=2 で書けば資源の maxToken は 2 になる。出遅れた A が token=1 で書こうとしても、1 < 2 なので弾かれる。古い持ち主は、自分が古いことを知らなくても、資源に拒まれる。

決定的に大事なのは、フェンシングは資源側でしか効かないことだ。ロックサービスがどれだけ賢くリースを管理しても、資源がトークンを見なければ二重書き込みは防げない。だから「ロックを取れたから安全」ではなく、「トークンを資源まで運んで検査させて初めて安全」。これが Redlock 論争の核心だった。

動かす

下のデモは、この筋書きをそのままブラウザで動かしている。「1手すすめる」で、A がロックを取り→GC 停止→リース失効→B が取得→A 再開→A の古い書き込み、と進む。右の切り替えでフェンシング有無を比べられる。有りなら A の出遅れた書き込みは拒否されて資源は守られ、無しなら A が B の値を破壊する。トークン番号が守りの要になっているのが見えるはずだ。

デモdistributed-lock(リース + フェンシング)step 1

フェンシング 有無

ロックサービス

持ち主(空き)

発行トークン—

リース失効 t=0 / 現在 t=0

資源 row-42 フェンシング有

(空)

maxToken0

拒否した書き込み0

初期状態

まだ誰もロックを持っていない。資源 row-42 は空

1 / 7

リースは持ち主のクラッシュに耐えるが、GC 停止で「持っているつもり」の古い持ち主を生む。 資源側がトークンを検査してはじめて、出遅れた書き込みを弾いて破壊を防げる。

設計の観点: 分散ロックの落とし穴

• なぜリースが要るか: 分散では「持ち主が死んだか」を確実に知れない(部分故障)。だから所有を時間で区切る。リースは「たぶん生きている」を「期限まで有効」に変換する道具
• リースだけでは不十分: GC 停止・ページフォールト・ネットワーク遅延で、生きている持ち主が「止まって見える」→ 失効 → 二重取得。リース長のチューニングでは消せない。フェンシングトークンが必要
• フェンシングは資源側の責任: ロックの取得可否だけ見ても安全にならない。トークンを実際の書き込みまで運び、資源(DB/ストレージ)がそれを検査してはじめて正しい。多くの実障害はこの検査が無いことに起因
• Redlock 論争: Redis の N ノード多数決ロック(Redlock)は、フェンシング無しでは GC 停止・クロックスキューで安全性が崩れる、と Kleppmann が指摘。反論もあるが「安全性が要るならフェンシングトークンを使え」は広く受け入れられた教訓
• そもそもロックが要るか: 分散ロックは「効率」(重複作業を避ける)のためか、「正しさ」(絶対に同時実行させない)のためかで要件が違う。正しさが要るなら、ロックだけでなく資源側の冪等性やフェンシングまで含めて設計する

メリット・デメリットと実例

方式	クラッシュ耐性	二重取得の防止	依存	実例
単純ロック(TTL 無し)	無い(持ち主死で永久ロック)	—	—	素朴な実装(避けるべき)
リースロック(TTL)	自動失効で耐える	フェンス無しだと破壊される	時計	Redlock(単体)、素朴な Redis ロック
リース + フェンシング	自動失効で耐える	資源側で拒否できる	合意 + 資源の検査	Chubby、Zookeeper + fencing、etcd lease
合意ベース(Raft/Paxos)	過半数が残れば耐える	フェンシング併用で防げる	合意プロトコル	etcd、Zookeeper、Consul

裏どり:

• Google Chubby: リース付きロックサービスの古典。分散ロック + 少量のメタデータ保存を、Paxos で複製した信頼できるサービスとして提供。GFS/Bigtable のマスタ選出に使われた
• Zookeeper / etcd: 合意(ZAB/Raft)の上にリースとシーケンス番号を提供。etcd の lease + revision、Zookeeper の zxid/version は、まさにフェンシングトークンとして使える
• Redlock 論争: Redis の Redlock を Kleppmann が「フェンシング無しでは不十分」と批判(2016)。以後、「分散ロックで正しさが要るならフェンシングトークン」が定説に
• DB の楽観ロック: UPDATE … WHERE version = ? の version 列は、資源側フェンシングそのもの。分散ロックが無くても、資源が単調な番号を検査すれば二重更新を防げる

簡略化したこと

• 合意層は前提: ロックの一意性を保証する合意(Raft/Paxos)は取れているものとし、単一の LockService が真実を持つ(実際はここが分散合意)
• 論理時計: 実時計・クロックスキュー・NTP ずれは扱わない(Redlock の時計依存は設計の観点の節で説明)
• 1 本のロックのみ: 複数ロック・デッドロック検出・公平な待ち行列は扱わない
• 故障は時間で表現: ノードの停止・遅延は Tick で時間を進めることでモデル化する

参考資料

• Martin Kleppmann, "How to do distributed locking"(2016) — フェンシングトークンの必要性。本章の下敷き
• Redis, "Distributed locks with Redis"(Redlock) — 議論の対象になった多数決ロック
• Mike Burrows, "The Chubby lock service for loosely-coupled distributed systems"(2006) — リースロックの古典
• 実装: distributed/dlock