-----------------
UPDATE: このアルゴリズムは現在、こちらのRedisドキュメントで解説されています => http://redis.io/topics/distlock。この記事は旧バージョンのまま残してあり、今後の更新はRedisドキュメントの方に反映されます。
-----------------

多くの人が分散ロックの実装にRedisを使っている。これが優れたユースケースであり、そうでなければ解決が難しい問題をRedisが見事に解決してくれると信じている人も多い。一方で、これは完全に壊れており、安全ではなく、Redisの誤った使い方だと考える人もいる。

基本的には、どちらも正しい。安全性を確保しつつ、同時に高可用性を求めるのであれば――Redisノードがダウンしてもクライアントがロックの取得・解放を続けられるようにしたいのであれば――分散ロックは決して自明なものではない。同時に、高速なロックマネージャーがあれば、実践上は解決が難しい多くの問題を解決できるし、時には完璧とは程遠い解決策の方が、非常に遅い解決策よりもましなこともある。

Redisをベースに、高速かつ信頼性の高いシステムを同時に実現することはできるのだろうか？このブログ記事は、その領域を探求する試みだ。N台のRedisインスタンスを使って分散かつ信頼性の高いロックを実現するためのシンプルなアルゴリズムの提案を説明してみたい。コミュニティの皆さんにこのアルゴリズムを分析し、コメントしてもらうことで、有効な候補となり得るかを検証できればと思っている。

# 本当に求めているものは何か？

求める安全性（safety）と活性（liveness）の特性を明示せずに分散システムについて語っても、ほとんど意味がない。この2つの要件が明確になってはじめて、設計が正しいかを検証でき、他の人が設計を分析してバグを見つけることが可能になるからだ。ここでは、分散ロックを効果的に使うために最低限必要だと私が考える、3つの特性だけで設計をモデル化することにする。

1) 安全性：相互排他。いかなる時点においても、ロックを保持できるクライアントはただ一つである。

2) 活性A：デッドロックがないこと。リソースをロックしたクライアントがクラッシュしたり分断されたりしても、最終的には必ずロックを取得できる。

3) 活性B：耐障害性。Redisノードの過半数が稼働している限り、クライアントはロックの取得と解放が可能である。

# 分散ロック、単純なやり方

何を改善したいのかを理解するために、まず現状を分析してみよう。

Redisでリソースをロックする最も単純な方法は、インスタンスにキーを作成することだ。キーは通常、Redisの有効期限（expires）機能を使って限られた生存時間（TTL）付きで作成され、最終的には何らかの形で解放されるようになっている（上記リストの特性2）。クライアントがリソースを解放する必要があるときは、そのキーを削除する。

一見するとこれはうまく機能するが、問題がある。アーキテクチャ上の単一障害点になってしまうのだ。もしRedisのマスターがダウンしたらどうなるだろうか？
そうだ、スレーブを追加すればいい！そしてマスターが利用できないときはスレーブを使えばいい。残念ながら、これは viable ではない。そうしてしまうと、相互排他という安全性が保証できなくなる。Redisのレプリケーションは非同期だからだ。

このモデルでは、明らかな競合状態が発生する。

1) クライアントAがマスターでロックを取得する。

2) キーへの書き込みがスレーブに転送される前にマスターがクラッシュする。

3) スレーブがマスターに昇格する。

4) クライアントBが、Aがすでにロックを保持しているのと同じリソースに対してロックを取得してしまう。 <- 安全性違反！

障害時などの特別な状況下で、複数のクライアントが同時にロックを保持してもまったく問題ない場合もある。
もしそうなら、ここで読むのをやめて、レプリケーションに基づくソリューションをそのまま使えばよい。そうでないなら、より安全な実装方法を求めて読み進めてほしい。

# まずは、1台のインスタンスで正しくやってみる

上記で説明した単一インスタンス構成の限界を克服しようとする前に、まずこのシンプルなケースで正しく行う方法を確認しておこう。たまに競合状態が発生しても許容できるアプリケーションでは、これは実際に有効な解決策となり得るし、単一インスタンスでのロックは、ここで説明する分散アルゴリズムの基礎となるからだ。

ロックを取得するには、次のようにするのが正しいやり方だ。

SET resource_name my_random_value NX PX 30000

このコマンドは、キーがまだ存在しない場合にのみキーをセットし（NXオプション）、有効期限を30000ミリ秒に設定する（PXオプション）。
キーの値は「my_random_value」に設定される。この値は、すべてのクライアントおよびすべてのロック要求にわたって一意でなければならない。

基本的に、このランダムな値はロックを安全に解放するために使われる。Redisに対して「キーが存在し、かつそこに保存されている値が自分が期待する値と正確に一致する場合にのみキーを削除せよ」と指示するスクリプトを用いるのだ。これは次のLuaスクリプトで実現できる。

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

これは、他のクライアントが作成したロックを削除してしまうのを避けるために重要だ。例えば、クライアントがロックを取得した後、ロックの有効時間（キーが期限切れになるまでの時間）よりも長い時間、何らかの処理でブロックされ、その後すでに別のクライアントによって取得されたロックを削除してしまうかもしれない。
単にDELを使うだけでは安全ではない。クライアントが他のクライアントのロックを削除してしまう可能性があるからだ。上記のスクリプトを使えば、すべてのロックはランダムな文字列で「署名」されるため、削除を試みたクライアント自身が設定したロックがまだ存在する場合にのみ、ロックが削除される。

このランダムな文字列は何にすべきか？私は/dev/urandomから取得した20バイトを想定しているが、用途に応じて十分に一意性を保てる、より軽量な方法を見つけてもよい。
例えば、安全な選び方としては、/dev/urandomでRC4をシードし、そこから疑似ランダムなストリームを生成する方法がある。
よりシンプルな方法としては、マイクロ秒精度のUNIX時間とクライアントIDを連結して使う方法もある。安全性は劣るが、ほとんどの環境では十分だろう。

キーの生存時間として使うこの時間を「ロック有効時間（lock validity time）」と呼ぶ。これは自動解放までの時間であると同時に、クライアントが、相互排他性の保証を技術的に破ることなく、別のクライアントが再びロックを取得できるようになる前に、必要な処理を実行するための時間でもある。この保証は、ロックが取得された瞬間から一定の時間窓にのみ限定される。

これでロックを取得・解放するための良い方法が得られた。単一インスタンスで常に利用可能という、非分散システムを想定すれば、このシステムは安全だ。次に、この概念を、そのような保証がない分散システムへと拡張してみよう。

# 分散版

アルゴリズムの分散版では、N台のRedisマスターがあると想定する。これらのノードは完全に独立しており、レプリケーションやその他の暗黙的な協調システムは一切使わない。単一インスタンスで安全にロックを取得・解放する方法はすでに説明した。この手法を単一インスタンスでのロック取得・解放に用いることを前提とする。ここでの例ではN=5とする。これは妥当な値であり、障害がなるべく独立して発生することを保証するために、異なるコンピュータや仮想マシン上で5台のRedisマスターを稼働させる必要がある。

ロックを取得するために、クライアントは次の操作を実行する。

ステップ1）現在の時刻をミリ秒単位で取得する。

ステップ2）すべてのN台のインスタンスで、同じキー名とランダムな値を使って、順番にロックの取得を試みる。

ステップ2で各インスタンスにロックを設定する際、クライアントはロックの自動解放時間全体と比べて小さなタイムアウトを使って取得を試みる。
例えば自動解放時間が10秒であれば、タイムアウトは5〜50ミリ秒程度にするとよい。
これにより、ダウンしているRedisノードとの通信を試みてクライアントが長時間ブロックされるのを防ぐ。もしインスタンスが利用できなければ、できるだけ早く次のインスタンスとの通信を試みるべきだ。

ステップ3）クライアントは、現在の時刻からステップ1で取得したタイムスタンプを差し引くことで、ロック取得に要した経過時間を計算する。
過半数のインスタンス（少なくとも3台）でロックを取得でき、かつロック取得にかかった合計経過時間がロック有効時間よりも短い場合に限り、ロックは取得されたとみなされる。

ステップ4）ロックが取得された場合、その有効時間は、初期の有効時間からステップ3で計算した経過時間を差し引いたものとみなされる。

ステップ5）何らかの理由でロックの取得に失敗した場合（N/2+1台のインスタンスをロックできなかったか、有効時間がマイナスになった場合）、クライアントはすべてのインスタンスのロック解除を試みる（ロックできなかったと思われるインスタンスも含めて）。

# 同期か非同期か？

基本的に、このアルゴリズムは部分的に同期的である。プロセス間で同期された時計はないものの、各プロセスのローカル時間はほぼ同じ速さで進み、その誤差はロックの自動解放時間と比べて小さいという仮定に依存している。この仮定は現実のコンピュータの状況によく即している。どのコンピュータもローカルクロックを持っており、通常、異なるコンピュータ間での時計のドリフトは小さいと期待できるからだ。

さらに、相互排他性のルールを精緻化する必要がある。その保証が成り立つのは、ロックを保持しているクライアントが、（ステップ3で得られる）ロック有効時間からわずかな時間（プロセス間の時計ドリフトを補正するための数ミリ秒）を差し引いた時間内に処理を完了する場合に限られる。

# リトライ

クライアントがロックを取得できなかった場合は、ランダムな遅延を置いて再試行すべきだ。同じリソースに対して同時にロックを取得しようとする複数のクライアントを非同期化するためである（そうしないと、誰も勝者になれないスプリットブレイン状態を招く可能性がある）。また、クライアントが過半数のRedisインスタンスでより速くロックを取得しようとすればするほど、スプリットブレインが発生する時間窓（ひいてはリトライの必要性）は小さくなる。したがって、理想的にはクライアントは多重化（multiplexing）を用いて、N台のインスタンスに対してSETコマンドを同時に送信すべきだ。

過半数のロック取得に失敗したクライアントが、（部分的に）取得したロックをできるだけ早く解放することがいかに重要かを強調しておきたい。そうすれば、キーの期限切れを待たずに再びロックを取得できるようになるからだ（ただし、ネットワーク分断が発生してクライアントがRedisインスタンスと通信できなくなった場合は、可用性のペナルティを払い、期限切れを待たなければならなくなる）。

# ロックの解放

ロックの解放はシンプルで、クライアントが特定のインスタンスでロックに成功したと考えているかどうかに関わらず、すべてのインスタンスでロックを解放するだけだ。

# 安全性に関する議論

このシステムは安全だろうか？さまざまなシナリオで何が起こるかを考えてみよう。

まず、クライアントが過半数のインスタンスでロックを取得できたと仮定しよう。すべてのインスタンスは同じTTLのキーを保持することになる。しかしキーは異なる時刻にセットされたため、期限切れになる時刻も異なる。ただし、最初のキーが最悪でも時刻T1（最初のサーバーに問い合わせる前にサンプリングした時刻）にセットされ、最後のキーが最悪でも時刻T2（最後のサーバーから応答を得た時刻）にセットされたとすれば、セットの中で最初に期限切れになるキーは、少なくとも MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT の間は存在することが確実だ。他のすべてのキーはそれより後に期限切れになるため、少なくともこの時間の間は、キーが同時に存在することが保証される。

過半数のキーがセットされている間は、別のクライアントがロックを取得することはできない。N/2+1個のキーがすでに存在する場合、N/2+1回のSET NX操作が成功することはあり得ないからだ。したがって、ロックが取得されたなら、同時にそれを再取得すること（相互排他性を破ること）は不可能だ。

しかし、同時にロックを取得しようとする複数のクライアントが、同時に成功してしまわないことも保証したい。

クライアントがロックの最大有効時間（基本的にSETで使うTTL）に近い、あるいはそれ以上の時間をかけて過半数のインスタンスをロックした場合、そのクライアントはロックを無効とみなし、インスタンスのロックを解除する。したがって、考慮する必要があるのは、クライアントが有効時間よりも短い時間で過半数のインスタンスをロックできた場合だけだ。この場合、上ですでに述べた議論により、MIN_VALIDITYの間はどのクライアントもロックを再取得できないはずだ。つまり、複数のクライアントが同時にN/2+1台のインスタンスをロックできるのは（ここでの「同時」とはステップ2の終了時点を指す）、過半数をロックするのに要した時間がTTLを超え、ロックが無効とされる場合に限られる。

安全性の形式的証明を提供できる方、あるいはバグを発見された方は、ぜひ教えてほしい。大歓迎だ。

# 活性に関する議論

システムの活性は、主に次の3つの特徴に基づいている。

1) ロックの自動解放（キーが期限切れになるため）。最終的にはキーは再びロック可能な状態に戻る。

2) クライアントは通常、ロックが取得できなかった場合や、ロックを取得して処理が完了した場合に、協力的にロックを削除すること。これにより、キーの期限切れを待たずにロックを再取得できる可能性が高まる。

3) クライアントがロックをリトライする必要があるとき、過半数のロックを取得するのに必要な時間と比べて十分に長い時間待機すること。これにより、リソース競合時のスプリットブレイン状態の発生を確率的に低く抑える。

しかし、非常に特殊なネットワーク分断と再結合のパターンが無限に繰り返されることで、システムの可用性が損なわれるシナリオが少なくとも一つ存在する。
例えばN=5の場合、2つのクライアントAとBが同時に同じリソースをロックしようとし、どちらも過半数のロックを取得できないとする。ただし、AとBのロック数を合計すれば過半数のノードをロックできているかもしれない（例えばクライアントAが2台、クライアントBが1台をロックしたなど）。
その後、クライアントがロックしたインスタンスのロックを解除する前に分断されてしまう。すると、そのリソースは自動解放時間とほぼ等しい時間、ロック不可能な状態のままになる。そしてキーが期限切れになると、2つのクライアントAとBは再び分断から復帰し、同じパターンを繰り返す。これが無限に続くのだ。

上記の問題を別の観点から見ると、ネットワーク分断に対してTTL時間に等しい可用性のペナルティを支払っていることになる。したがって、分断が継続的に発生すれば、このペナルティを無限に支払い続けることになる。

保証された活性を実現するシンプルな方法は見つけられていない（正直、さほど熱心には探していないが）、ただ最悪のケースは引き起こすのが難しいように思える。
基本的に、このアルゴリズムで提供できるのは、特性2の近似に過ぎないということだ。

# パフォーマンス、クラッシュリカバリとfsync

ロックサーバーとしてRedisを使う多くのユーザーは、ロックの取得・解放のレイテンシと、1秒あたりに実行可能な取得／解放操作の数の両面で高いパフォーマンスを必要としている。この要件を満たすために、N台のRedisサーバーと通信してレイテンシを削減する戦略は、間違いなく多重化である（あるいは貧者の多重化、すなわちソケットをノンブロッキングモードにしてすべてのコマンドを送信し、クライアントと各インスタンス間のRTTがほぼ同じであると仮定して後からすべての応答を読み取る手法）。

しかし、クラッシュリカバリを想定したシステムモデルを目指すのであれば、永続化についても考慮すべき点がある。

問題を理解するために、Redisをまったく永続化なしで設定したと仮定しよう。クライアントが5台中3台のインスタンスでロックを取得する。そのうちロック取得に成功した1台のインスタンスが再起動される。この時点で、同じリソースに対して再びロック可能なインスタンスが3台存在することになり、別のクライアントが再びロックを取得できてしまい、排他性という安全性が破られてしまう。

AOF永続化を有効にすれば、状況はかなり改善する。例えばSHUTDOWNを送信して再起動することでサーバーをアップグレードできる。Redisの有効期限は意味的に、サーバーが停止している間も仮想的に時間が経過するように実装されているため、要件はすべて満たされる。
しかし、これはクリーンなシャットダウンである場合に限ってうまくいく。では電源障害の場合はどうだろうか？Redisがデフォルトのように1秒ごとにディスクへfsyncする設定になっていると、再起動後にキーが失われている可能性がある。端的に言えば、あらゆる種類のインスタンス再起動に対してロックの安全性を保証したいのであれば、永続化設定でfsync=alwaysを有効にする必要がある。そうすると今度はパフォーマンスが完全に台無しになり、従来安全な分散ロックの実装に使われてきたCPシステムと同程度のレベルにまで落ちてしまう。

良い知らせは、このアルゴリズムでは過半数のサーバーに到達した時点でロック取得を止めるわけではないため、実際に安全性違反が起こる確率は小さいということだ。ほとんどの場合、ロックは5台すべてのサーバーで保持されるため、たとえ1台がキーを失った状態で再起動しても、実際に安全性違反が起こる可能性は現実的には低い（不可能ではないが）。端的に言えば、これはユーザーの選択であり、大きなトレードオフだ。競合状態が発生する確率が小さいことを考えれば、クラッシュリカバリの後に極めて低い確率で複数のクライアントが同時にロックを取得してしまうことが許容できるのであれば、操作ごとのfsyncは回避できるし、回避すべきだ。

# リファレンス実装

Rubyによるシンプルなリファレンス実装を、redis-rbを使って作成した。こちらにある： http://github.com/antirez/redlock-rb

# 協力をお願いします

分散システムに詳しい方は、ぜひ意見や分析を聞かせてほしい。
また、他の言語によるリファレンス実装も大歓迎だ。

よろしくお願いします！

追記：このブログ記事のコメント欄やHacker News経由で、記事に取り入れる価値のあるフィードバックをいただいたので、以下に追記する。

1) 下のコメントでSteven Benjamin氏が指摘しているように、インスタンスを再起動した後、そのインスタンスを使っていたすべてのロックが期限切れになるのに十分な時間、そのインスタンスを利用不可にしておくことができれば、fsyncは不要になる。実際、永続化自体がまったく不要であり、純粋なインメモリ構成でも安全性の保証を提供できる。

例：先ほど説明した競合状態の例では、5台中3台のサーバーでロックが取得され、ロックを取得したサーバーの1台が空の状態で再起動すると、別のクライアントがこのサーバーと、以前のクライアントがロックしていなかった残りの2台をロックすることで、同じロックを取得できてしまう。しかし、再起動したサーバーを、そのサーバーで取得されたすべてのロックが期限切れになるまで十分な時間、クエリに対して利用不可にしておけば、この競合が発生しないことが保証される。

2) Hacker Newsのユーザーeurleif氏が指摘したように、クライアントが処理の完了に時間がかかりすぎていることに気づいた場合、ロックを再取得するという戦略を取ることも可能だ。これは、保存されている値が期待通りである場合にキーの有効期限を延長するスクリプトを送信することで、既存のロックを延長するだけで実現できる。新たな分断がなく、キーが期限切れになる前に十分な余裕を持ってロックの延長を試みれば、ロックが延長されることが保証される。

3) Hacker Newsのユーザーmjb氏が、「skew」という用語は異なる時計がローカル時間を進める速度の差を表すのに適切ではなく、実際には「drift（ドリフト）」について話しているのだと指摘してくれた。正しい用語を使うため、「skew」を「drift」に置き換える。

非常に有益なフィードバックに感謝する。