Redis による分散ロック¶
異なるプロセス同士が、相互に排他的な方法で共有リソースに対して操作を実行する、という環境において、分散ロックは非常に役に立ちます。
Redis を使った DLM (Distributed Lock Manager) の実装については、多くのライブラリやブログポストがあります。しかし、ライブラリごとに異なるアプローチがとられており、またその多くは、より複雑なデザインと比較するとシンプルで、そのぶん保証される内容が低いアプローチとなっています。
このページは、Redis 上で分散ロックを実装するにあたり、標準的なアルゴリズムを提供することを目指すものです。私たちはここで Redlock と呼ぶアルゴリズムを提供します。これは DLM 実装の一種で、よく見かけるような、ひとつのインスタンスを使うアプローチよりも安全である、と私たちは考えています。コミュニティがこのアプローチを分析し、フィードバックを提供してくれること、さらに、より複雑な、または代替となるデザインを実装する際のスターティング・ポイントとして使われることを希望します。
実装¶
アルゴリズムを説明する前に、入手可能な参照実装へのいくつかのリンクを紹介します。
- Redlock-rb (Ruby implementation).
- Redlock-php (PHP implementation).
- Redsync.go (Go implementation).
- Redisson (Java implementation).
安全性(Safety) と 応答性(Liveness) の保証¶
私たちのデザインは、以下の 3 つの性質からモデル化されます。これらは、私たちの観点では、分散ロックを効率的に使うために最低限必要となる保証です。
安全性(Safety): 相互に排他的である。どの時点においても、ひとつのクライアントのみがロックを取得できる。
応答性(Liveness) A: デッドロックフリー。ロックを取得したクライアントがクラッシュしたり不通になった場合でも、必ずいつかはロックを取得できる。
応答性(Liveness) B: 障害耐性。Redis ノードの過半数が生きているかぎり、クライアントはロックを取得したり解放したりできる。
なぜ、フェイルオーバー・ベースの実装は十分でないのか¶
私たちが何を改善しようとしているのか理解するため、多くの Redis ベースの分散ロックライブラリの現在の状況を分析しましょう。
リソースをロックするために Redis を使うにあたり、シンプルな方法はインスタンスにキーを作ることです。キーには通常、Redisの expire 機能を使って time to live が指定されるため、遅かれ早かれいつかは解放されます(リストの性質 2)。クライアントがリソースを解放するときは、キーを削除します。
表面上これはうまく働きますが、問題もあります: アーキテクチャ上、ここが単一障害点になります。Redis マスターがダウンしたときには、何が起こるでしょうか？よろしい、スレーブを追加しよう！そして、マスターが使用不能になったらそちらを使えば良い。不運なことに、これは実行不可能です。Redis のレプリケーションは非同期であるため、相互に排他的である、という安全性が実現できなくなるのです。
以下が、このモデルを使う場合に発生する明らかな競合状態です:
クライアント A がマスターに対してロックを取得する
マスターが、キーの書き込みをスレーブに送信する前にクラッシュする
スレーブがマスターに昇格する
A がすでにロックを取得しているリソースに対し、クライアント B がロックを取得する。 安全性違反!
障害発生時のような特殊な状況では、複数のクライアントが同時にロックを取得できる、という点が問題にならないこともしばしばあります。もしそうなら、レプリケーション・ベースの解法を使うことができます。そうでなければ、このドキュメントで説明する解決方法を実装することを勧めます。
ひとつのインスタンスを使う場合の正しい実装¶
上述の、ひとつのインスタンスのみを使う場合の制限を乗り越えようとする前に、このシンプルなケースについての正しいやり方を確認しておきましょう。これは、ときどき発生する競合状態が許容されるアプリケーションにおいては、実際上、可能なソリューションです。また、ひとつのインスタンスに対するロックは、ここで記述するアルゴリズムの基礎をなすものでもあります。
ロックを取得するための方法は以下です:
SET resource_name my_random_value NX PX 30000
このコマンドは、そのキーがすでに存在しない場合に限り(NX オプション)、30000 ミリ秒の有効期限つきで(PX オプション)キーをセットします。キーには “my_random_value” という値がセットされます。この値は、すべてのクライアント、またすべてのロックリクエストにまたがってユニークであることが求められます。
基本的に、このランダムな値は、次のようなスクリプトを使いロックを安全に解放するために使われます: 「キーが存在し、かつキーに格納されている値が、自分が期待しているものと正確に一致する場合にかぎり、キーを削除しなさい」。これは以下の 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 byte を想定していますが、あなたのタスクのために必要十分な、よりコストの低いやり方を見つけられるかもしれません。たとえば、安全なやり方として、RC4の安全なシードを /dev/random から選び、擬似乱数列を生成する方法があります。よりシンプルな解決法としては、ミリ秒精度の Unix 時刻をクライアントIDと結合する、というやり方もあります。これは安全ではありませんが、おそらく多くの環境では十分でしょう。
キーに設定する time to live は、”ロックの有効期間” と呼ばれます。これは、自動的なロック解放までの時間でもあり、他のクライアントがロックを再び取得できるようになるまでの、そのクライアントが操作に使える持ち時間でもあります。ロックが取得されてから、既定のウィンドウ時間内に限り、相互排他の保証が破られることはありません。
私たちは、ロックを取得し解放するための、望ましい方法を得ました。常に利用可能なひとつのインスタンスから構成される、非分散システムなら、これで安全です。こうした保証がない分散システムへ、コンセプトを拡張していきましょう。
Redlock アルゴリズム¶
分散環境バージョンのアルゴリズムにおいて、N 個の Redis マスターがあると仮定します。これらのノードは完全に独立しており、レプリケーションやその他の暗黙的な協調システムは想定しません。ひとつのインスタンスに対して、安全にロックを取得、解放する方法についてはすでに説明しました。ここでは、ひとつのインスタンスに対するロックの取得、解放の方式を所与のものとして使用します。ここではひとつの妥当な例として、N=5 を設定します。互いに無関係に障害が発生する状態を確保するため、異なるコンピュータ、または仮想マシン上で稼働する 5 つの Redis マスターが必要になります。
ロックを取得するため、クライアントは以下の操作を実行します:
現在時刻を取得します。
同一のキー名とランダム値を使い、全 N インスタンスに対し順番にロックの取得を試みます。ステップ 2 で各インスタンスにロックをセットする際、クライアントは、ロックの自動解放までの時間と比較して十分に小さなタイムアウト値を使います。たとえば自動解放までの時間が 10 秒の場合、タイムアウトは 5 ~ 50 ミリ秒程度の幅になるでしょう。これは、クライアントがダウン中の Redis ノードにアクセスしようとして長い間待たされることを避けるためです: もしあるインスタンスが使用できない場合、なるべく早く、次のインスタンスへのアクセスを試みるようにします。
クライアントは、現在時刻からステップ 1 で取得した時刻を引き、ロックを取得するまでにどれだけの時間が経過したかを計算します。インスタンスの過半数(最低 3 以上)に対してロックが得られ、かつロック取得までの総経過時間がロックの有効時間よりも短い場合にかぎり、ロックが取得できたとみなします。
ロックが取得できたら、その有効時間は、初期の有効時間からステップ 3 で計算された経過時間を引いた値となります。
もしなんらかの理由でロックの取得に失敗したら(N/2+1 個のインスタンスのロックが取得できなかった、もしくは有効時間が負の値となったか、のいずれか)、すべてのインスタンスについてアンロックを行います(ロックが取得できなかったと考えられるインスタンスについても)。
このアルゴリズムは非同期ですか？¶
このアルゴリズムは、プロセス間で時刻の同期はされないけれども、全プロセスのローカル時間が近似的に同じレートで動いている(ロックの自動解放時間と比較すると十分に小さなエラーを含みつつ)、という仮定をおいています。この仮定は、実世界のコンピューター環境とよく似ています: すべてのコンピューターはローカルなクロックを持ち、通常においては、異なるコンピューター間のクロック・ドリフトは小さいとみなして良い。
この観点から、私たちの相互排他のルールについてより詳細にしておく必要があります: 相互排他のルールは、ロックを保持しているクライアントが、ロックの有効時間(ステップ 3 で得られたもの)からさらに若干の時間(プロセス間のクロック・ドリフトを補正するための数ミリ秒)を差し引いた時間の間で、処理を完了させるかぎりにおいて保証される。
クロック・ドリフト がある範囲内に抑えられていることを要求する、同様のシステムについてより詳しい情報としては、次の興味深い論文があります: Leases: an efficient fault-tolerant mechanism for distributed file cache consistency
失敗時のリトライ¶
クライアントがロックを取得できなかった場合、同じリソースに対して同時にロックの取得を試みるクライアント同士でタイミングをずらすため(誰もロックを取得できないスプリット・ブレーン状態につながる)、あるランダムな待ち時間を入れた後に再度ロックの取得を試みなければなりません。クライアントが Redis インスタンスの過半数のロックを取得するのが速くなるほど、スプリット・ブレーン状態(これが発生するとリトライが必要となる)を避けるためのウィンドウは小さくて済みます。理想としては、クライアントは N インスタンスに対して、多重化を使って SET コマンドを送信すべきです。
クライアントが過半数のロックを取得するのに失敗した場合、(部分的に)取得したロックをできるだけ速やかに解放することは、非常に重要です。そうすることで、次にロックが取得されるまでにキーの expire を待たなくても良くなります(ただし、ネットワーク分断が発生した場合は、クライアントは Redis インスタンスと通信ができなくなるため、可用性の面でペナルティが発生し、expire を待つことになります)。
ロックの解放¶
ロックの解放は、シンプルに、すべてのインスタンスに対して、(クライアントがそのインスタンスに対してロックを取得できたかどうかに関わらず)ロックを解放することで行います。
安全性についての議論¶
このアルゴリズムは安全でしょうか？いくつかの異なるシナリオにおいて、どのような状況が発生するか、推測することができます。
クライアントが、過半数のインスタンスに対してロックを取得できたと仮定しましょう。すべてのインスタンスは、同じ time to live が設定されたキーを保持します。しかしキーは異なる時刻にセットされるため、異なる時刻に expire されます。もし最初のキーが最悪でも時刻 T1 にセットされ(最初のサーバーにアクセスする前に取得しておく)、最後のキーが最悪でも時刻 T2 にセットされる(最後のサーバーからの応答時刻から得られる)なら、最初のキーは最小で ‘MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT’ の期間存在した後に expire される、と確信できます。その他のすべてのキーはその後に expire されるため、最低でもこの期間はキーが同時にセットされた状態である、といえます。
過半数のキーがセットされている間、他のクライアントはロックを取得することができません。N/2+1 個の SET NX 操作は、N/2+1 個のキーがすでに存在していると成功しないためです。したがって、あるロックが取得されたら、同時に再取得(相互排他性に違反)することは不可能です。
さらに私たちは、複数のクライアントが同じタイミングでロックの取得を試みた場合に、同時に成功することがない、ということを確信できなければなりません。
クライアントが過半数のインスタンスのロックを取得するまでに、ロックの最大有効時間(SET 時の TTL)と同じかそれよりも長い時間がかかった場合、ロックは無効とみなされ、アンロックされます。したがって考慮する必要があるのは、クライアントが、過半数のインスタンスのロックを、有効時間内で取得できた場合のみです。この場合、前述の議論のとおり、’MIN_VALIDITY’ の期間内はどのクライアントもロックを再取得できません。ロックを取得するまでにかかった時間が TTL よりも長い場合にかぎり、複数のクライアントが N/2+1 個のインスタンスを同時に(ステップ 2 の最後の時刻)ロックできますが、このときロックは無効になっています。
類似する既存のアルゴリズムの観点から、安全性について形式的な証明が与えられるでしょうか。または、バグを見つけられるでしょうか？そうした指摘をとても歓迎します。
応答性についての議論¶
システムの応答性は、3 つの主要な特徴に基づきます:
(キーの expire による)ロックの自動解放: いずれは、キーは再ロック可能になる。
クライアントは通常において、ロックが取得できなかった場合、および仕事が完了した場合はロックを削除するよう、協調して動作する。それにより、ロックの再取得にあたりキーの expire を待つ必要がなくなる。
クライアントはロックに際してリトライが必要な場合、過半数のロック取得にかかるよりも長く、待ち時間を入れる。リソースの競合によるスプリット・ブレーン状態を確率的に抑えるため。
しかし、ネットワーク分断時には “TTL” に相当する時間だけ、可用性に対してペナルティが発生します。ネットワーク分断が継続する場合、永久にこのペナルティを受け続けることになります。
基本的に、永続的なネットワーク分断が発生する場合、システムは永久に利用不可能となります。
性能、クラッシュリカバリ、fsync¶
Redis をロックサーバーとして使う多くのユーザーは、ロックの取得解放にかかるレイテンシと、秒間に実行可能な取得/解放オペレーション数の両面において、高い性能を必要とします。要求に応えるため、N 個の Redis サーバーとの通信に要するレイテンシを削減する戦略は、明らかに通信の多重化(貧者の多重化、すなわち、ソケットをノンブロッキング・モードで使い、すべてのコマンドを一度に送り、すべての返信を一度に読む。ここでクライアントと、それぞれのインスタンスとの RTT は同等と仮定)です。
クラッシュリカバリを考慮する場合、永続化の面で別の考慮が必要になります。
問題を検討するため、Redis を一切永続化しない設定で稼働させると仮定してみましょう。あるクライアントが、5 インスタンスのうち 3 つのロックを取得したとします。クライアントがロックを取得したインスタンスのうち、ひとつが再起動した場合、同じリソースに対して、再び 3 つのインスタンスがロック可能となります。結果として、他のクライアントがロックを取得することが可能になり、ロックの排他制御による安全性が侵害されます。
もし AOF による永続化を有効にしている場合、状況は少し改善されます。たとえば、サーバーをアップグレードするために SHUTDOWN コマンドを送り、再起動する場合です。Redis の expire は意味的に正しく実装されており、サーバーが停止している間も実際上の時間が経過しているため、要件はすべて満たされます。しかし、問題が発生しないのはクリーンシャットダウンが行われた場合に限ります。電源が落ちたらどうなるでしょう？もし Redis がディスクに毎秒 fsync するよう設定されている(デフォルト)場合、再起動後にキーが失われている可能性があります。理屈上、どのようなインスタンスの再起動が発生してもロックの安全性を担保したい場合、永続化の設定において fsync=always を有効にしておく必要があります。これは、安全な分散ロックを実装するために、昔から CP システムで使われてきたのと同じレベルであり、全体的に性能を損ないます。
しかしながら、状況は一見したよりはいくぶんか良いものです。基本的に、アルゴリズムの安全性は、インスタンスがクラッシュから再起動したときに、 その時点でアクティブな ロックを保持していないかぎり保たれます。アクティブなロックは、システムに再ジョインしたインスタンス以外のインスタンスをロックすることで確保されています。
このことを保証するために、インスタンスのクラッシュ後は、最低でも、使っている最大の TTL よりも長い時間だけ利用できないようにしておく必要があります。すなわち、インスタンスがクラッシュした時点で保持しているロックキーがすべて無効となり、自動的に解放されるまでに必要とする時間です。
遅延リスタート を使うことで、いずれの Redis 永続化方式を使うかに関わらず安全性は達成されますが、これは可用性のペナルティにつながることに留意してください。たとえば、インスタンスの過半数がクラッシュしたら、システムは全体的に TTL の期間中は利用不可能になります(ここで、全体的に、とは、この期間中どんなリソースもロックできなくなることを意味します)。
アルゴリズムの信頼性を向上させる: ロックの拡張¶
クライアントの仕事が小さなステップから構成される場合、ロック有効時間の初期値としては小さな値を使い、ロック延長のメカニズムを実装するようにアルゴリズムを拡張できます。大筋としては次のようになります。処理の途中でロックの有効時間が小さくなってきたら、クライアントはすべてのインスタンスに Lua スクリプトを送信し、キーの TTL 延長を指示します。ただし、キーが存在し、かつその値が、クライアントがロックを取得した時点のランダム値から変更されていない場合に限ります。
クライアントは、インスタンスの過半数に対して、有効時間内にロックの延長ができた場合のみ、ロックが再取得できたと考えるべきです(基本的なアルゴリズムは、ロックの取得時に使うものとよく似ています)。
これは、アルゴリズムを技術的に変更するものではないですが、いずれにしても、ロックを再取得する最大回数は制限されるべきです。そうしない場合、応答性のひとつが侵害されることになります。