分散ロック完全ガイド 2025: Redlock、Zookeeper、etcd、Fencing Token、安全な実装

TL;DR

分散ロックは本当に難しい: 単一マシンの mutex とは全く異なる
Redis 単一ロック: シンプルだが single point of failure
Redlock: Redis クラスタベース、論争中
Fencing Token: ロックの真の安全性を保証
Zookeeper/etcd: より安全だが複雑
結論: 可能なら分散ロックを避けよ

1. なぜ分散ロックは難しいのか?

1.1 単一マシンの mutex

lock = threading.Lock()

with lock:
    critical_section()

動作原理:

メモリ上のロック変数
CPU の atomic 命令
単一の OS カーネルが管理

保証:

一度に 1 スレッドのみ
自動解放 (GC、死亡)
非常に高速 (~10ns)

1.2 分散環境との違い

[Server A] ←─ network ─→ [Lock Service] ←─ network ─→ [Server B]

問題点:

ネットワーク遅延: 数 ms
ネットワーク分断: パケット損失
クロックのずれ: マシンごとに時計が異なる
GC pauses: JVM が 1 秒止まる可能性
障害: ロック保持者が死んだら?
部分障害: 一部のノードのみ死亡

→ 単一マシンの前提がすべて崩れる。

1.3 分散ロックの 2 つの目的

1. 効率性 (Efficiency):

同じ作業を 2 回しない
コスト削減
ロック失敗しても大問題ではない (一時的な非効率)

2. 正確性 (Correctness):

データ整合性の保証
ロック失敗 = データ破損
非常に厳格な保証が必要

多くの人は効率性を求めながら正確性の保証が必要と誤解している。

2. Redis 単一ロック

2.1 最もシンプルな試み

def acquire_lock(key, ttl=10):
    return redis.set(key, "locked", nx=True, ex=ttl)

def release_lock(key):
    redis.delete(key)

# 使用
if acquire_lock("my-resource"):
    try:
        do_work()
    finally:
        release_lock("my-resource")

SET key value NX EX ttl:

NX: キーが存在しない場合のみ
EX: TTL 設定

アトミック: Redis が保証する。

2.2 1 つ目の問題 — 他クライアントのロック解除

# Client A がロックを取得
acquire_lock("my-resource")
# Client A が作業中...
# 作業が 30 秒かかる (TTL 10 秒を超過)
# ロックが自動的に期限切れ

# Client B がロックを取得
acquire_lock("my-resource")

# Client A が作業を終えてロック解除
release_lock("my-resource")
# → Client B のロックを解除!

# Client C がロックを取得可能に
# Client B と C が同時に作業!

2.3 解決策 — ロック識別子

import uuid

def acquire_lock(key, ttl=10):
    token = str(uuid.uuid4())
    if redis.set(key, token, nx=True, ex=ttl):
        return token
    return None

def release_lock(key, token):
    # Lua スクリプトでアトミック性を確保
    script = """
    if redis.call('get', KEYS[1]) == ARGV[1] then
        return redis.call('del', KEYS[1])
    else
        return 0
    end
    """
    redis.eval(script, 1, key, token)

改善: 自分のロックのみ解除する。

2.4 2 つ目の問題 — Single Point of Failure

[Redis] ← 死ぬと全ロックを失う
   ↓
[Server A] [Server B] [Server C]

Replication:

[Master Redis]
    ↓ async replication
[Slave Redis]

問題: async replication。

Client A が master でロック取得
Master が死亡 (replication 前)
Slave が master に昇格 (ロックなし)
Client B がロック取得
両方がロックを保持 → データ破損

3. Redlock アルゴリズム

3.1 Salvatore Sanfilippo (Redis 作者) の答え

複数の独立した Redis インスタンス を使用する。過半数でロックを取得すれば成功。

[Redis 1] [Redis 2] [Redis 3] [Redis 4] [Redis 5]
  ↓        ↓         ↓         ↓         ↓
[Client] → すべてに SET NX EX を試行
        → 3/5 以上成功でロック取得

3.2 アルゴリズム

def acquire_redlock(key, ttl=10000):
    token = str(uuid.uuid4())
    quorum = len(redis_clients) // 2 + 1  # 3/5
    
    start_time = time.time() * 1000
    acquired = []
    
    for client in redis_clients:
        try:
            # 非常に短い timeout
            if client.set(key, token, nx=True, px=ttl):
                acquired.append(client)
        except:
            pass
    
    elapsed = time.time() * 1000 - start_time
    
    if len(acquired) >= quorum and elapsed < ttl:
        return token  # ロック取得成功
    else:
        # 失敗 - すべて解放
        for client in acquired:
            release_lock(client, key, token)
        return None

3.3 Redlock の前提

クロックが合理的に同期している
GC pauses が短い
ネットワーク遅延 < TTL

3.4 Martin Kleppmann の批判 (2016)

有名なブログ記事 "How to do distributed locking":

1. GC Pause の問題:

1. Client A がロック取得 (TTL 10 秒)
2. Client A が GC で 15 秒停止 (ロック期限切れ)
3. Client B がロック取得
4. Client A が目覚める → 自分がロック保持者だと考える
5. Client A と B が同時に作業

2. クロックジャンプ:

1. Client A がロック取得 (TTL 10 秒)
2. Redis のクロックが突然 5 秒ジャンプ (NTP 同期)
3. ロックが早く期限切れ
4. Client B がロック取得

Kleppmann の結論: Redlock は 正確性が必要なシステムには不適。

3.5 Antirez の反論

Salvatore Sanfilippo の答え:

monotonic clock を使う (ジャンプなし)
GC pause はあらゆるシステムの問題
効率性目的なら十分

論争の結果: 合意なし。Kleppmann の立場がより広く認められている。

4. Fencing Token

4.1 核心アイデア

ロック + 単調増加するトークン。

1. Client A がロック取得、token = 33
2. Client A が GC で停止
3. Client B がロック取得、token = 34
4. Client B が storage に書き込み (token 34)
5. Client A が目覚め、storage に書き込み (token 33)
6. Storage が 33 < 34 を確認 → 拒否

4.2 実装

def acquire_lock_with_token(key):
    token = redis.incr(f"{key}:token")  # 単調増加
    if redis.set(key, token, nx=True, ex=10):
        return token
    return None

def write_to_storage(data, token):
    # Storage がトークンを検証
    if storage.last_token >= token:
        raise StaleTokenError()
    storage.write(data)
    storage.last_token = token

4.3 核心要件

Storage がトークンを検証する必要がある:

DB がトークンを追跡
古いトークンを拒否

ほとんどの storage はこれをサポートしない → 追加作業が必要。

4.4 どこで使われる?

HBase: ZooKeeper と組み合わせた fencing
Apache Cassandra: lightweight transactions
PostgreSQL: row のバージョン (optimistic locking)

5. ZooKeeper ベースのロック

5.1 ZooKeeper の強み

CP システム (一貫性優先)
Linearizable
ZooKeeper ephemeral sequential (クライアント死亡時に自動削除)
Watches (変更通知)

5.2 ロック実装

Recipe: 順序付き ephemeral node。

def acquire_lock(zk, lock_path):
    # 1. 順序付き ephemeral node を作成
    my_node = zk.create(
        f"{lock_path}/lock-",
        ephemeral=True,
        sequence=True
    )
    # 例: /lock/lock-0000000005
    
    while True:
        # 2. すべての子ノードを取得
        children = sorted(zk.get_children(lock_path))
        
        # 3. 自分が最小ならロック取得
        if my_node.endswith(children[0]):
            return my_node
        
        # 4. そうでなければ直前のノードを watch
        my_index = children.index(my_node.split('/')[-1])
        prev_node = children[my_index - 1]
        
        zk.exists(f"{lock_path}/{prev_node}", watch=callback)
        wait_for_callback()

5.3 ZooKeeper の利点

1. 自動解放:

クライアント死亡時に ephemeral node が自動削除
ゾンビロックなし

2. 正確な順序:

Sequence number で公平性を保証

3. ネットワーク分断で安全:

ZooKeeper が split-brain を防ぐ
ロック保持者が quorum から切り離されるとロックを保持できない

5.4 ZooKeeper の欠点

運用が複雑: 別クラスタが必要
性能: Redis より遅い
GC pause は依然として問題: クライアントが GC すれば同じ問題

5.5 Curator Framework (Java)

import org.apache.curator.framework.recipes.locks.InterProcessMutex;

InterProcessMutex lock = new InterProcessMutex(client, "/my-lock");
if (lock.acquire(10, TimeUnit.SECONDS)) {
    try {
        // 作業
    } finally {
        lock.release();
    }
}

Curator が ZooKeeper の複雑さを抽象化する。

6. etcd ベースのロック

6.1 etcd の特徴

CP システム (Raft ベース)
Linearizable
etcd lease (TTL に似ている)
Watches

6.2 ロック実装

import etcd3

client = etcd3.client()

# Lease を作成 (10 秒)
lease = client.lease(ttl=10)

# ロック取得
lock = client.lock("my-lock", ttl=10)
lock.acquire()

try:
    do_work()
finally:
    lock.release()

6.3 ZooKeeper との比較

	ZooKeeper	etcd
言語	Java	Go
合意	ZAB	Raft
運用	複雑	比較的シンプル
用途	Hadoop エコシステム	Kubernetes
API	Java 中心	gRPC

Kubernetes は etcd を使用 → etcd が徐々に標準化している。

7. データベースベースのロック

7.1 SELECT FOR UPDATE

BEGIN;
SELECT * FROM accounts WHERE id = 123 FOR UPDATE;
-- ロック保持、他のトランザクションは待機
UPDATE accounts SET balance = balance - 100 WHERE id = 123;
COMMIT;
-- ロック解放

利点:

DB が面倒を見てくれる
トランザクションと統合
自動解放 (commit/rollback)

欠点:

DB 負荷
ロック競合時の性能低下
分散トランザクションが難しい

7.2 Advisory Locks (PostgreSQL)

-- ロック取得
SELECT pg_advisory_lock(12345);

-- 作業
UPDATE ...;

-- ロック解放
SELECT pg_advisory_unlock(12345);

利点:

非常に高速
メモリロック (行ロックではない)
セッション終了時に自動解放

用途: バックグラウンドジョブ同期、マイグレーション。

7.3 Optimistic Locking

-- 1. データとバージョンを読む
SELECT *, version FROM users WHERE id = 1;
-- version = 5

-- 2. 作業後に更新
UPDATE users SET name = 'New', version = version + 1
WHERE id = 1 AND version = 5;
-- 影響を受けた行 = 0 なら失敗 (他者が先に変更)

利点:

ロックなし (待機なし)
同時実行性が良い
分散に適している

欠点:

衝突時はリトライ
頻繁に衝突すると非効率

8. パターンと落とし穴

8.1 Lock Renewal (Heartbeat)

長時間の作業の場合:

import threading

class RenewingLock:
    def __init__(self, key, ttl=10):
        self.key = key
        self.token = None
        self.ttl = ttl
        self.stop_renewal = False
    
    def acquire(self):
        self.token = acquire_lock(self.key, self.ttl)
        if self.token:
            self.renewal_thread = threading.Thread(target=self._renew)
            self.renewal_thread.start()
        return self.token
    
    def _renew(self):
        while not self.stop_renewal:
            time.sleep(self.ttl / 3)
            redis.expire(self.key, self.ttl)
    
    def release(self):
        self.stop_renewal = True
        release_lock(self.key, self.token)

問題: GC pause の間は lease renewal ができず → ロックが期限切れ。依然として安全ではない。

8.3 Backoff with Jitter

import random

def acquire_with_retry(key, max_retries=10):
    for attempt in range(max_retries):
        if token := acquire_lock(key):
            return token
        # Exponential backoff + jitter
        delay = (2 ** attempt) * 0.1 + random.uniform(0, 0.5)
        time.sleep(delay)
    return None

Jitter が重要: すべてのクライアントが同時にリトライすると thundering herd になる。

8.3 Reentrant Lock

同じクライアントが再入可能。

class ReentrantLock:
    def __init__(self, key):
        self.key = key
        self.count = 0
        self.token = None
    
    def acquire(self):
        if self.count > 0:
            self.count += 1
            return True
        
        self.token = acquire_lock(self.key)
        if self.token:
            self.count = 1
            return True
        return False
    
    def release(self):
        self.count -= 1
        if self.count == 0:
            release_lock(self.key, self.token)
            self.token = None

8.4 デッドロック防止

複数のロックを使う場合:

# 間違い - デッドロックの可能性
def transfer(from_id, to_id, amount):
    lock1 = acquire_lock(f"account:{from_id}")
    lock2 = acquire_lock(f"account:{to_id}")
    # ...

# 2 ユーザーが同時に相互送金:
# A → B: lock A, lock B
# B → A: lock B, lock A
# → デッドロック

# 正解 - ソート済みの順序
def transfer(from_id, to_id, amount):
    first, second = sorted([from_id, to_id])
    lock1 = acquire_lock(f"account:{first}")
    lock2 = acquire_lock(f"account:{second}")
    # ...

9. 分散ロックを避ける方法

9.1 単一責任者

各作業を 1 つの worker だけが処理:

[Job Queue]
    ↓
[Worker 1] (jobs A, B)
[Worker 2] (jobs C, D)
[Worker 3] (jobs E, F)

パーティショニング:

ユーザー ID の hash → どの worker?
同じユーザーは常に同じ worker へ
ロック不要

9.2 冪等性 (Idempotency)

def process_payment(payment_id, amount):
    if db.exists(f"processed:{payment_id}"):
        return  # すでに処理済み
    
    db.atomic_set(f"processed:{payment_id}", True)
    actually_charge(amount)

何度実行しても安全 → ロック不要。

9.3 Compare-and-Swap (CAS)

UPDATE inventory 
SET quantity = quantity - 1 
WHERE product_id = 123 AND quantity > 0;

アトミック、ロックなし。影響を受けた行が 0 なら在庫なし。

9.4 Event Sourcing

状態変更の代わりにイベントを追加:

events.append(OrderCreated(...))
events.append(InventoryReserved(...))
events.append(PaymentCharged(...))

append-only、ロックはほぼ不要。結果はイベントの再生で得る。

9.5 Actor Model

各 actor が自身の状態と mailbox を持つ。

class AccountActor extends Actor {
  var balance: BigDecimal = 0
  
  def receive = {
    case Deposit(amount) => balance += amount
    case Withdraw(amount) => balance -= amount
  }
}

一度に 1 メッセージ → ロック不要。

Erlang/Elixir、Akka がこのモデル。

10. 推奨事項

10.1 決定木

本当に分散ロックが必要か?
├─ いいえ → 冪等性、CAS、パーティショニングを使う
└─ はい
   ├─ 効率性目的 (概ね OK)
   │  └─ Redis 単一ロック (シンプル)
   └─ 正確性目的 (絶対ダメ)
      ├─ ZooKeeper / etcd
      └─ Fencing token (storage がサポートする場合)

10.2 Kleppmann の結論

"効率性が目的なら Redlock で十分かもしれない。正確性が目的なら合意アルゴリズム (ZAB、Raft) を使え。"

10.3 実践的推奨

多くの場合:

シンプルな Redis ロック (SET NX EX)
短い TTL
冪等性によるバックアップ
「ロック失敗しても大問題にならない」システム

重要な場合:

ZooKeeper / etcd
Fencing token
トランザクションを使う
正確性をコードで保証

クイズ

1. Redlock の核心的な問題は?

答え: GC pause とクロックジャンプ です。Martin Kleppmann が 2016 年に批判: (1) GC pause — Client A がロック取得後、15 秒の GC pause で停止、ロック期限切れ、Client B がロック取得、A が目覚めて自分がロック保持者だと考える → 両方が作業 → データ破損。(2) クロックジャンプ — NTP 同期でクロックがジャンプするとロックが早く期限切れ。結論: Redlock は 効率性 には OK、正確性 には不適。正確性が必要なら ZooKeeper/etcd + fencing token を使う。

2. Fencing Token はどのように安全性を保証するか?

答え: 単調増加するトークン とともにロックを発行する。ロック保持者が storage に書き込む際、トークンも一緒に渡す。Storage がトークンを検証 — 古いトークンの書き込みは拒否。シナリオ: Client A token=33 → GC pause → Client B token=34 → B が storage に書き込み (last_token=34) → A が目覚めて storage に書き込み (token=33) → storage が 33 < 34 を見て拒否。核心要件: storage がトークンを追跡すること。ほとんどの DB はこれをサポートしないため、追加作業が必要。

3. ZooKeeper の ephemeral node がなぜ分散ロックに有利か?

答え: クライアント接続が切れると自動削除される からです。シナリオ: ロック保持クライアントが死亡 → ZooKeeper セッション timeout → ephemeral node が自動削除 → ロック自動解放 → 他のクライアントが即座にロック取得可能。ゾンビロックなし。また ZooKeeper は CP システム (ZAB、Raft 系) なので split-brain を防止する。欠点: GC pause の間クライアントが生きていると認識されると、同じ問題が起こる。Kubernetes は同様の理由で etcd を使用。

4. SELECT FOR UPDATE の限界は?

答え: (1) DB 負荷 — ロック保持時間中 DB リソースを占有、(2) 競合 — 多くのトランザクションが同じ行をロックすると直列化、(3) デッドロック — ロック順序が異なると発生、(4) 分散トランザクションが困難 — 複数 DB にまたがるロックは非常に難しい (2PC)、(5) 長時間トランザクションのリスク — トランザクションが長いと他の作業をブロック。代替: optimistic locking (version カラム)、CAS、パーティショニング、冪等性。単純なケースでは SELECT FOR UPDATE が最も安全。

5. 分散ロックをどう避けられるか?

答え: 5 つのパターン: (1) 単一責任者 — パーティショニングで同じキーを常に同じ worker に、ロック不要、(2) 冪等性 — 何度実行しても安全な操作、(3) CAS (Compare-and-Swap) — UPDATE ... WHERE version=? パターン、(4) Event Sourcing — append-only、衝突なし、(5) Actor Model — 各 actor が一度に 1 メッセージのみ処理。分散ロックは最後の手段。可能な限りデータモデルやアルゴリズムで同時実行性の問題を解決する。

参考資料

How to do distributed locking — Martin Kleppmann
Is Redlock safe? — Antirez の回答
Redlock Spec — 公式
ZooKeeper Lock Recipe
etcd Concurrency
Curator Framework — Java ZooKeeper クライアント
Redisson — Java Redis クライアント with locks
Designing Data-Intensive Applications — Martin Kleppmann
PostgreSQL Advisory Locks
Hazelcast — インメモリデータグリッド
Apache Curator Recipes