Redisでより信頼性の高いロックを実現するための提案
-----------------
追記: このアルゴリズムは現在、Redisドキュメントのこちら => http://redis.io/topics/distlock で解説されています。この記事は古いバージョンのまま残してあります。今後のアップデートはRedisドキュメント側に反映されます。
-----------------
多くの人が分散ロックの実装にRedisを使っています。Redisは本来解決が難しい問題をうまく解決してくれる素晴らしいユースケースだと考える人もいれば、まったく壊れていて安全ではなく、Redisの誤った使い方だと考える人もいます。
基本的には、どちらも正しいと言えます。分散ロックは、安全にしようとすれば決して単純ではありません。同時に高い可用性も求めるとなると、Redisノードがダウンしてもクライアントがロックを取得・解放できる必要があります。一方で、高速なロックマネージャーは、本来解決が難しい多くの問題を実践的に解決してくれますし、時には完璧とは程遠い解決策でも、非常に遅い解決策よりはましな場合もあります。
Redisをベースに、高速かつ信頼性の高いシステムを両立させることはできるのでしょうか。このブログ記事では、その領域を探ってみます。N台のRedisインスタンスを使った、シンプルで分散かつ信頼性の高いロックのためのアルゴリズム案を説明し、コミュニティの皆さんに分析やコメントをいただき、このアルゴリズムが有効な候補になり得るか検証したいと思います。
# 本当に求めているものは何か？
安全性とライブネスの特性を明確にせずに分散システムを語っても、ほとんど意味がありません。この2つの要件が定義されて初めて、設計が正しいかを検証でき、他の人が設計を分析してバグを見つけることができるからです。ここでは、分散ロックを効果的に使うために最低限必要だと考える、3つの特性だけで設計をモデル化します。
1) 安全性: 相互排除。任意の時点で、ロックを保持できるクライアントは1つだけです。
2) ライブネスA: デッドロックしないこと。リソースをロックしたクライアントがクラッシュしたり分断されたりしても、最終的には必ずロックを取得できることです。
3) ライブネスB: フォールトトレランス。Redisノードの過半数が稼働している限り、クライアントはロックを取得・解放できます。
# 分散ロック、単純なやり方
何を改善したいのかを理解するために、現状を分析してみます。
Redisでリソースをロックする最も単純な方法は、1つのインスタンスにキーを作成することです。キーは通常、Redisのexpire機能を使って有効期限を付けて作成されるため、最終的には何らかの形で解放されます（上記リストの特性2）。クライアントがリソースを解放する必要があるときは、キーを削除します。
表面的にはうまく動いているように見えますが、問題があります。これはアーキテクチャ上の単一障害点になるのです。Redisのマスターがダウンしたらどうなるでしょうか。
そうだ、スレーブを追加して、マスターが利用できないときに使えばいい。残念ながら、これは有効な方法ではありません。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
これは、他のクライアントが作成したロックを削除してしまわないようにするために重要です。例えば、クライアントがロックを取得し、ロックの有効期限（キーがexpireする時間）よりも長く何らかの処理でブロックされ、その後でロックを削除しようとしたとき、そのロックはすでに別のクライアントによって取得されているかもしれません。
単にDELを使うだけでは安全ではありません。クライアントが他のクライアントのロックを削除してしまう可能性があるからです。一方、上記のスクリプトでは、各ロックがランダムな文字列で「署名」されているため、ロックを削除しようとしているクライアント自身が設定したロックがまだ存在する場合にのみ、ロックが削除されます。
このランダムな文字列は何にすべきでしょうか。/dev/urandomから20バイト取得するのが理想的ですが、タスクに応じて十分に一意性を確保できる、より安価な方法もあります。
例えば安全な方法としては、/dev/urandomでRC4をシードし、そこから疑似ランダムなストリームを生成する方法があります。
よりシンプルな方法としては、マイクロ秒精度のUNIX時間とクライアントIDを組み合わせる方法があります。安全性は前者ほど高くありませんが、ほとんどの環境では十分でしょう。
キーの有効期限として使う時間は、「ロック有効時間」と呼びます。これは自動解放までの時間であると同時に、相互排除の保証が技術的に破られることなく、別のクライアントが再びロックを取得できるようになるまでに、ロックを保持しているクライアントが要求された処理を実行するために与えられた時間でもあります。相互排除の保証は、ロックを取得した瞬間からの一定の時間枠に限られるという点に注意してください。
これでロックを取得・解放するための良い方法ができました。単一の、常に利用可能なインスタンスで構成された非分散システムとして考えれば、このシステムは安全です。この概念を、そのような保証がない分散システムに拡張してみます。
# 分散版
分散版のアルゴリズムでは、N台のRedisマスターがあると想定します。これらのノードは完全に独立しており、レプリケーションやその他の暗黙的な協調システムは使いません。単一インスタンスで安全にロックを取得・解放する方法はすでに説明しました。この手法を単一インスタンスでのロック取得・解放に使うことを前提とします。例ではN=5としますが、これは妥当な値です。5台のRedisマスターを異なるコンピュータや仮想マシンで実行し、できるだけ独立して障害が発生するようにする必要があります。
ロックを取得するために、クライアントは次の操作を実行します。
ステップ1) 現在時刻をミリ秒単位で取得します。
ステップ2) 同じキー名とランダムな値を使って、N台すべてのインスタンスで順番にロックの取得を試みます。
ステップ2で各インスタンスにロックを設定する際、クライアントはロックの自動解放時間全体と比べて十分に小さいタイムアウトを使います。
例えば自動解放時間が10秒であれば、タイムアウトは5〜50ミリ秒程度が目安です。
これにより、ダウンしているRedisノードとの通信を長時間ブロックされるのを防ぎます。もしインスタンスが利用できなければ、できるだけ早く次のインスタンスとの通信を試すべきです。
ステップ3) クライアントは、ステップ1で取得したタイムスタンプを現在時刻から差し引くことで、ロックの取得に要した経過時間を計算します。
過半数のインスタンス（少なくとも3台）でロックを取得でき、かつロック取得にかかった合計経過時間がロック有効時間よりも短い場合にのみ、ロックは取得できたとみなされます。
ステップ4) ロックが取得できた場合、その有効時間は、ステップ3で計算した経過時間を、最初の有効時間から差し引いたものとみなされます。
ステップ5) 何らかの理由でロックの取得に失敗した場合（N/2+1台のインスタンスをロックできなかったか、有効時間がマイナスになった場合）、クライアントはすべてのインスタンスのロック解除を試みます（ロックできなかったと思われるインスタンスも含めて）。
# 同期的か、そうでないか？
基本的に、このアルゴリズムは部分的に同期的です。プロセス間で同期された時計はないものの、各プロセスのローカルな時間はほぼ同じ速さで進み、その誤差はロックの自動解放時間と比べて十分に小さいという前提に依存しています。この前提は現実のコンピュータによく当てはまります。どのコンピュータにもローカルクロックがあり、異なるコンピュータ間でもクロックのドリフトは通常小さいとみなせるからです。
さらに、相互排除のルールをより厳密にする必要があります。相互排除が保証されるのは、ロックを保持しているクライアントが、ステップ3で得られたロック有効時間から、わずかな時間（プロセス間のクロックドリフトを補正するための数ミリ秒程度）を差し引いた時間内に処理を終える場合に限られます。
# リトライ
クライアントがロックを取得できなかったときは、同じリソースに対して同時にロックを取得しようとしている複数のクライアントの競合を解消するため、ランダムな遅延を置いて再試行すべきです（同時に試行すると、誰も勝てないスプリットブレイン状態になる可能性があります）。また、クライアントがN台のインスタンスの過半数でいかに速くロックを取得しようとするかが、スプリットブレインが発生する時間枠（そしてリトライの必要性）を小さくする鍵になります。そのため、理想的にはクライアントは多重化（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) クライアントがロックをリトライする際に、過半数のロックを取得するのに必要な時間と比べて十分に長い時間待機するため、リソース競合時のスプリットブレイン状態が確率的に起こりにくくなること。
しかし、非常に特殊なネットワーク分断と再結合のパターンが無限に繰り返されることで、システムの可用性が損なわれるシナリオが少なくとも1つ存在します。
例えば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のexpireは、サーバーが停止している間も仮想的に時間が経過し続けるように実装されているため、すべての要件は満たされます。
しかし、これはクリーンなシャットダウンである場合に限ります。停電の場合はどうでしょうか。Redisがデフォルトのように毎秒ディスクに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」に置き換えています。
とても有益なフィードバックをありがとうございます。