分散ロック / リーダー選出 ── 「2人のリーダー」を防ぐ
扱うCS概念：排他制御（Mutual Exclusion）、フェンシングトークン、Redlock アルゴリズム、ZooKeeper の ZAB プロトコル、リース（Lease）
この章で何ができるようになるか：分散システムで「同時に1つだけ」を保証する仕組みの設計と、その限界を説明できるようになる。Martin Kleppmann の Redlock 批判を理解し、安全な分散ロックの設計判断ができるようになる。
問題設定
以下のシナリオで「同時に1つだけ」を保証したい。
シナリオ1：在庫の最後の1つを2人が同時に購入
→ ロックなしだと2人とも「在庫あり」と読み、2人に販売してしまう
シナリオ2：分散ワーカーが cron ジョブを実行
→ 3台のワーカーが同時に同じジョブを重複実行
シナリオ3：リーダー選出
→ 3台のサーバーのうち1台だけが「プライマリ」として書き込みを受け付ける
→ 2台が同時にリーダーになると split-brain（データ不整合）単一プロセスなら mutex で済む。複数プロセス・複数サーバーにまたがると「分散ロック」が必要になる。
素朴な解法：Redis の SETNX
import redis
import uuid
import time
class SimpleRedisLock:
def __init__(self, redis_client: redis.Redis, key: str, ttl: int = 10):
self.redis = redis_client
self.key = key
self.ttl = ttl
self.token = str(uuid.uuid4()) # ロック所有者の識別子
def acquire(self, timeout: int = 5) -> bool:
end = time.time() + timeout
while time.time() < end:
# SETNX: キーが存在しなければセット（アトミック）
acquired = self.redis.set(
self.key, self.token,
nx=True, # Not eXists のときだけ
ex=self.ttl # 自動解放（TTL）
)
if acquired:
return True
time.sleep(0.01) # 10ms リトライ
return False
def release(self):
# ❌ 危険なパターン
# if self.redis.get(self.key) == self.token:
# self.redis.delete(self.key)
# ↑ GET と DELETE の間にロックが期限切れ → 別のクライアントが取得 → 誤削除
# ✅ Lua スクリプトでアトミックに実行
lua_script = """
if redis.call('GET', KEYS[1]) == ARGV[1] then
return redis.call('DEL', KEYS[1])
else
return 0
end
"""
self.redis.eval(lua_script, 1, self.key, self.token)なぜ UUID トークンが必要か：自分が取得したロックだけを解放するため。トークンなしだと、タイムアウトで失効した後に別クライアントが取得したロックを誤って解放してしまう。
TTL の罠：GC Pause と時計のずれ
sequenceDiagram
participant C1 as クライアント1
participant Redis
participant C2 as クライアント2
participant DB
C1->>Redis: SETNX lock=token1 (TTL=10s)
Redis-->>C1: OK（ロック取得）
Note over C1: GC Pause 15秒...
Note over Redis: TTL 経過 → ロック自動解放
C2->>Redis: SETNX lock=token2 (TTL=10s)
Redis-->>C2: OK（ロック取得）
C2->>DB: UPDATE stock（在庫を減らす）
Note over C1: GC Pause 終了
C1->>DB: UPDATE stock（在庫を減らす）
Note over DB: 2重更新！ロックの意味がないJava の GC Pause、ネットワークの遅延、NTP の時刻ずれ──いずれも「ロックを持っていると思っているが、実はもう失効している」状態を引き起こす。
フェンシングトークン（Fencing Token）
Martin Kleppmann が 2016年のブログ記事で推奨した解決策。ロック取得時に**単調増加する番号（フェンシングトークン）**を発行し、リソースアクセス時にこのトークンを検証する。
class FencedLock:
"""ロック取得ごとに単調増加するトークンを発行する"""
def acquire(self) -> int | None:
acquired = self.redis.set(self.key, self.token, nx=True, ex=self.ttl)
if acquired:
# INCR でグローバルに単調増加するフェンシングトークンを取得
fencing_token = self.redis.incr(f"{self.key}:fence")
return fencing_token
return None
# リソース側（DB など）がトークンを検証する
class StockService:
def __init__(self):
self.last_token = 0 # 受け付けた最大トークン
def update_stock(self, product_id: int, fencing_token: int):
if fencing_token <= self.last_token:
raise StaleTokenError(
f"Fencing token {fencing_token} <= {self.last_token}. "
"Lock likely expired; rejecting stale operation."
)
self.last_token = fencing_token
# 安全に更新を実行
db.execute("UPDATE stock SET quantity = quantity - 1 WHERE id = ?", product_id)sequenceDiagram
participant C1 as クライアント1
participant Lock as 分散ロック
participant C2 as クライアント2
participant DB as DB（フェンシング検証あり）
C1->>Lock: acquire → token=33
Note over C1: GC Pause 15秒...
Note over Lock: TTL 経過 → 解放
C2->>Lock: acquire → token=34
C2->>DB: UPDATE (token=34) ✅ 受理
Note over C1: GC 復帰
C1->>DB: UPDATE (token=33) ❌ 拒否（33 < 34）ポイント：ロックの安全性を「ロック側だけ」で保証しようとするのではなく、リソース側にもバリデーションを入れる。
Redlock：複数 Redis ノードでの分散ロック
Redis が単一ノードだと SPOF になる。Redis の開発者 Salvatore Sanfilippo が提案した Redlock は、複数の独立した Redis ノードでロックを取得する。
class Redlock:
"""5台の独立した Redis インスタンスを使った分散ロック"""
def __init__(self, redis_nodes: list[redis.Redis]):
self.nodes = redis_nodes
self.quorum = len(redis_nodes) // 2 + 1 # 過半数
self.drift_factor = 0.01 # 時計のずれ許容（1%）
def acquire(self, resource: str, ttl_ms: int = 10000) -> dict | None:
token = str(uuid.uuid4())
start_time = time.time() * 1000 # ms
acquired_count = 0
for node in self.nodes:
try:
if node.set(resource, token, nx=True, px=ttl_ms):
acquired_count += 1
except redis.ConnectionError:
pass # ノード障害は無視
# 経過時間を計算
elapsed_ms = time.time() * 1000 - start_time
# ドリフトを考慮した有効残り時間
validity = ttl_ms - elapsed_ms - (ttl_ms * self.drift_factor)
if acquired_count >= self.quorum and validity > 0:
return {"token": token, "validity_ms": validity}
else:
# 過半数取れなかった → 全ノードで解放
self._release_all(resource, token)
return None
def _release_all(self, resource: str, token: str):
lua = """
if redis.call('GET', KEYS[1]) == ARGV[1] then
return redis.call('DEL', KEYS[1])
end
return 0
"""
for node in self.nodes:
try:
node.eval(lua, 1, resource, token)
except redis.ConnectionError:
passRedlock のルール：
- 5台の独立した Redis（レプリカではない）を用意
- 全ノードに同じ TTL でロック取得を試みる
- 過半数（3台以上）で取得でき、かつ有効期限内なら成功
- 失敗したら全ノードで解放
Kleppmann の Redlock 批判
Martin Kleppmann は 2016年のブログ記事 “How to do distributed locking” で Redlock の安全性に疑問を呈した。
Kleppmann の主張：
1. 時計の仮定が強すぎる
Redlock は「各ノードの時計がおおむね正確」を前提とする。
NTP の障害やVM のクロックジャンプで崩れる。
2. GC Pause への脆弱性は変わらない
過半数取得後に GC Pause が起きると、TTL が切れた状態で操作される。
→ フェンシングトークンがないと安全でない。
3. そもそもフェンシングできるなら Redlock は不要
リソース側でトークン検証するなら、
単一 Redis の SETNX + フェンシングで十分。
Kleppmann の結論：
「効率のため」のロック（重複排除）→ 単一 Redis で十分
「正確さのため」のロック（データ整合性）→ ZooKeeper / etcd を使えZooKeeper によるリーダー選出
ZooKeeper は分散合意（ZAB プロトコル）を基盤とした、より強い保証を持つ分散調整サービスだ。
from kazoo.client import KazooClient
zk = KazooClient(hosts='zk1:2181,zk2:2181,zk3:2181')
zk.start()
# リーダー選出
class LeaderElection:
def __init__(self, zk_client, path="/election"):
self.zk = zk_client
self.path = path
self.my_node = None
def participate(self) -> bool:
# エフェメラルシーケンシャルノードを作成
# → セッションが切れたら自動削除（リース）
self.my_node = self.zk.create(
f"{self.path}/candidate-",
ephemeral=True, # セッション切断で自動削除
sequence=True, # 連番が付与される
makepath=True
)
return self._check_leader()
def _check_leader(self) -> bool:
children = sorted(self.zk.get_children(self.path))
my_name = self.my_node.split("/")[-1]
if children[0] == my_name:
print("I am the leader!")
return True
else:
# 自分の直前のノードを watch（Herd Effect 回避）
prev_idx = children.index(my_name) - 1
prev_path = f"{self.path}/{children[prev_idx]}"
@self.zk.DataWatch(prev_path)
def watch_prev(data, stat):
if stat is None: # 直前のノードが消えた
self._check_leader()
return Falseエフェメラルノード（Ephemeral Node）：クライアントのセッションが切れると自動的に削除される。クラッシュしたリーダーのノードが自動的に消え、次の候補がリーダーに昇格する。ハートビートのタイムアウトが実質的なリースになる。
Herd Effect の回避：全候補がリーダーノードを watch すると、リーダー交代時に全候補に通知が飛ぶ（Thundering Herd）。代わりに「直前のノードだけ watch」することで通知を1件に限定する。
etcd / Raft ベースのロック
Kubernetes が使う etcd も分散ロック・リーダー選出に使える。
// Go での etcd リース（Lease）ベースのロック
cli, _ := clientv3.New(clientv3.Config{
Endpoints: []string{"etcd1:2379", "etcd2:2379", "etcd3:2379"},
})
// リースを作成（TTL = 10秒、KeepAlive で延長）
lease, _ := cli.Grant(context.TODO(), 10)
// バックグラウンドで KeepAlive
ch, _ := cli.KeepAlive(context.TODO(), lease.ID)
// ロック取得（リースにバインド）
// → リースが切れたら自動解放
_, err := cli.Put(context.TODO(), "/locks/my-resource", "owner-1",
clientv3.WithLease(lease.ID))ロック vs リース vs CAS の使い分け
ロック（Lock）:
→ 排他制御。取得したプロセスだけがリソースにアクセスできる。
→ 問題：取得者がクラッシュするとデッドロック（→ TTL で軽減）
リース（Lease）:
→ 期限付きロック。KeepAlive で延長しないと自動解放。
→ ZooKeeper のエフェメラルノード、etcd の Lease。
→ クラッシュ時のデッドロックを防ぐ。
CAS（Compare-And-Swap）:
→ ロックを取らずに楽観的に更新。衝突したらリトライ。
→ DB: UPDATE ... WHERE version = ?
→ Redis: WATCH + MULTI/EXEC
→ 競合が少ない場合に最も効率的。| ロック | リース | CAS | |
|---|---|---|---|
| デッドロックリスク | あり | 低い（TTL） | なし |
| 性能 | 中（待機あり） | 中 | 高（衝突少なら） |
| 競合が多い場合 | 安定 | 安定 | リトライ嵐 |
| 用途 | 厳密な排他制御 | リーダー選出 | 楽観的更新 |
まとめ
| 課題 | 解決策 | 安全性保証 |
|---|---|---|
| 単純な排他制御 | Redis SETNX + TTL | 弱い（GC/NTP で崩れる） |
| 重複排除（効率目的） | Redis SETNX + UUID | 十分（たまに重複しても致命的でない） |
| データ整合性（正確さ目的） | ZooKeeper / etcd | 強い（合意ベース） |
| 二重リーダー防止 | フェンシングトークン | リソース側で保証 |
| クラッシュ時の自動回復 | リース（Lease） | セッション切断で自動解放 |
Kleppmann の名言：「分散ロックを使うなら、何のためかを明確にせよ。効率のためなら単純でよい。正確さのためならフェンシングが必須。」