分散ロック
Distributed Lock ・ ぶんさんろっく
複数のサーバにまたがって「同時に一人だけ」を保証する鍵。期限と番号で安全を保つ。
✦ 30秒で試す — 航海止まっていた1台が目を覚ますと、何が起きる？15秒後に目を覚ましたAの書き込みは、どうなる？予想してみる概要
分散ロックは、ネットワーク越しに存在する複数のノード（サーバやプロセス）が同じ資源に同時に手を出さないよう、「今この資源を触ってよいのは一人だけ」という排他制御を分散環境で実現する仕組みです。1台のマシンの中なら、OS やプログラミング言語が用意するロックで同時アクセスを防げますが、資源を奪い合う主体が別々のマシンにまたがると、その手が使えなくなります。分散ロックは、その隙間を埋めるための道具です。
典型的な場面は、「ワーカーが何台も動いているが、ある集計バッチは同時に一つしか走らせたくない」「在庫が一つの商品を、二つの注文が同時に確定させるのを防ぎたい」「外部 API への書き込みを一度に一つに絞りたい」といったケースです。データベースのトランザクションの外側にある、アプリケーションの単位の「同時に一つ」を保証したいときに登場します。
実装としては、Redis のような高速なデータストアを使う方式と、ZooKeeper や etcd のような合意アルゴリズムを備えた調停基盤を使う方式が代表的です。どちらを使うにしても、ロックには「期限（リース）」を付け、資源の側では「番号（フェンシングトークン）」で古い持ち主を締め出す、という二つの工夫が安全の要になります。
なぜ生まれたか
1台のマシンの中では、共有資源への同時アクセスは OS や言語ランタイムが提供するミューテックス（排他制御の鍵）で防げました。あるスレッドがロックを握っている間、ほかのスレッドは待たされます。ロックの状態はメモリという一箇所にあり、「今、鍵を持っているのは誰か」に曖昧さはありません。持ち主のスレッドが死ねば、OS がそれを確実に知っています。
ところがスケーリングのためにアプリを複数台のサーバに増やすと、この前提が崩れます。各サーバは独立したメモリを持ち、サーバ A の中のロックは、サーバ B のプロセスには見えません。両方が「自分がこの資源を独占している」と思い込んだまま、同じ在庫を二重に引き当てたり、同じジョブを二重に実行したりします。そこで、全ノードが同じ場所に鍵を取りに行く「ロックサービス」が必要になりました。
ただし、分散の世界ではロックサービスにも「持ち主が死んだのか、遅いだけなのか分からない」問題がついて回ります。Google が2006年に発表したロックサービス Chubby の論文は、この問題に正面から取り組み、ロックに期限を付けること、そして鍵を取るたびに増える番号（シーケンサ）を資源側で確かめることを示しました。この「期限と番号」の組み合わせが、その後の分散ロックの基本形になっています。
詳細
獲得と解放の基本的な流れ
分散ロックの本質は、全ノードが共通して見られる場所（ロックサーバ）に「鍵」を一つだけ置き、それを取れた者だけが資源を触れる、という約束事です。Redis を使った代表的な方式では、ロックの実体は「特定のキーに値を書き込めるかどうか」で表します。
鍵を取るときは、「キーが存在しなければ書き込む」と「有効期限を付ける」を一つの不可分な操作（アトミック操作）で行うのが要点です。Redis なら SET lock:job <ランダムな値> NX PX 30000 のように、NX（無ければ書く）と PX（ミリ秒の期限）を同じ命令に載せます。古い資料には SETNX で確保してから EXPIRE で期限を付ける2段階の書き方がありますが、2つの命令の間でワーカーが落ちると、期限のない鍵が残って永遠に外れなくなります。確認と書き込みを別々にしても同じで、その隙間に別のワーカーが割り込みます。
値にはワーカーごとのランダムな値を入れ、解放するときは「キーの値が自分の入れたものと同じなら消す」をやはり一息で行います（Redis では Lua スクリプトで比較と削除をまとめます）。こうしないと、次に述べる期限切れのあとで、他人の鍵を消してしまいます。
二つの落とし穴——期限と、期限切れ
一つ目の問題は、鍵を持ったまま持ち主が死ぬことです。ロックを握ったワーカーがクラッシュして解放処理にたどり着けなければ、鍵は返されず、資源は誰にも触れなくなります。これはデッドロック（複数の主体が互いの鍵を待ち合って動けなくなる状態）とは別の、「ロックの取りっぱなし」です。これを防ぐために、ロックには必ず有効期限を付けます。期限付きのロックは「リース（貸し出し）」とも呼ばれ、持ち主が一定時間で更新しなければ自動で外れます。
ところがこの期限が、二つ目の問題を生みます。ワーカー A の処理が想定より長引いて、鍵の期限が先に切れると、ロックサーバは A が死んだとみなしてワーカー B に鍵を渡します。A は死んだのではなく、たとえばガベージコレクションの全停止（ストップ・ザ・ワールド）や、仮想マシンの一時停止、スワップで固まっていただけかもしれません。止まっている間は時計も見られないので、A は期限が切れたことに気づけません。目覚めた A は、まだ自分が持ち主だと思ったまま資源に書き込みます。
「処理の前に期限を確かめればよい」と思うかもしれませんが、確かめた直後に止まれば同じことです。持ち主の側の注意では、この問題は原理的に防げません。
フェンシングトークン: 資源の側で締め出す
そこで、ロックサービスは鍵を渡すたびに単調に増える番号（フェンシングトークン）を添え、ワーカーは資源に書き込むときにその番号を一緒に送ります。資源（ストレージ）はこれまでに見た最大の番号を覚えておき、それより小さい番号の書き込みを拒否します。期限切れに気づかない古い持ち主がいても、資源の側で締め出せるわけです。
期限と番号は、守っているものが違います。期限は「持ち主が死んでも、いつか鍵を取り返せる」ことを守ります（ないと、システムが止まる）。番号は「期限切れに気づかない持ち主が、次の持ち主の仕事を壊さない」ことを守ります（ないと、データが壊れる）。下の部品で、ワーカー A の GC 停止の帯を伸ばしながら、期限とフェンシングのオン・オフを切り替えて確かめてください。
A は期限（10秒）の内に目覚めて書き込み、ロックを返しました。B はその後で番号 34 を取ったので、衝突は起きません。A の「GC 停止」の帯の右端をドラッグして、長く伸ばしてみてください。
フェンシングには、資源の側が番号を確かめられる必要があります。データベースなら、最後に書いた番号を列に持たせ、UPDATE の条件に「保存済みの番号が自分の番号より小さい」を入れる条件付き書き込みで実現できますが、番号を理解しない外部サービスやファイルシステムが相手だと使えません。その場合は、処理そのものを冪等性のある形にして、二重に実行されても結果が壊れないようにするのが次善の策です。
実装の選択肢とトレードオフ
Redis の単一インスタンスは極めて高速ですが、その Redis 自体が単一障害点になります。可用性のためにレプリケーションで冗長化すると、今度は「プライマリがロックを渡した直後に落ち、まだ複製されていなかった」場合に、昇格したレプリカが同じロックを二重に渡す危険が出てきます。この弱点を補うために、Redis の作者 Salvatore Sanfilippo（antirez）は複数の独立した Redis の過半数で鍵を取る Redlock を提案しました。これに対してマーティン・クレップマンは2016年のブログ記事で、Redlock はプロセスの停止や時計のずれに対して安全ではなく、フェンシングトークンも生成できないと批判し、antirez が反論する論争になりました。安全性が本当に必要な用途では Redlock に頼らない、というのが現在の一般的な受け止め方です。
もう一つは、ZooKeeper や etcd のように合意アルゴリズムで裏打ちされた方式です。内部で過半数の合意を取りながら状態を管理するので、「二つの真実」が生まれません。ロックの寿命をクライアントの接続（セッションやリース）と結び付けられるので、「死んだら自動で鍵が外れる」も自然に実現でき、ZooKeeper の zxid や etcd のリビジョンのような、単調に増える番号をフェンシングトークンとしてそのまま使えます。代償は速度で、合意のための往復が入るぶん Redis 方式より重くなります。
現実的な指針は、「二重実行が多少起きても後で辻褄を合わせられる（冪等性で吸収できる）性能重視の用途なら Redis、同時に二つ走ると困る厳密な用途なら合意ベース＋フェンシング」という使い分けです。そして、分散ロックは並行性を犠牲にするので、乱用すればシステム全体の直列化を招きます。本当にロックが要るのか、データベースのトランザクションや条件付き更新（楽観ロックと悲観ロックの楽観ロック）、冪等な設計で回避できないかを先に検討するのが、良い設計への近道です。
試問
2台のワーカー A・B が、ロック（期限10秒）を取ったときだけ資源に書き込みます。ロックを渡すたびに番号が増え、A は33番、B は34番です。A はロックを取った直後に GC（メモリの掃除）で止まり、その停止の長さはタイムラインの紫の帯の右端をドラッグして変えられます。リース期限とフェンシング（資源が番号を確かめる仕組み）は、枠の上の切り替えで付け外しできます。
A は期限（10秒）の内に目覚めて書き込み、ロックを返しました。B はその後で番号 34 を取ったので、衝突は起きません。A の「GC 停止」の帯の右端をドラッグして、長く伸ばしてみてください。