Redisを使用した分散ロック

こんにちは、Habr！



今日は、Redisを使用した分散ロックの実装に関する複雑な記事の翻訳に注目し、トピックとしてRedisの視点について話すことを提案します。 「高負荷アプリケーション」という本の著者であるMartinKleppmanが検討したRedlockアルゴリズムの分析をここに示します。





分散ロックは、さまざまなプロセスが相互に排他的な方法で共有リソースを処理する必要がある多くの環境で使用される非常に便利なプリミティブです。



RedisでDLM（Distributed Locking Manager）を実装する方法を説明するライブラリや投稿はたくさんありますが、各ライブラリは異なるアプローチを採用しており、提供される保証は、もう少し複雑な設計で達成できるものに比べてかなり弱いです。



この記事では、Redisを使用して分散ロックを実装する方法を示す条件付きの正規アルゴリズムについて説明します。Redlockと呼ばれるアルゴリズムについて説明します、分散ロックマネージャを実装しており、私たちの意見では、このアルゴリズムは従来の単一インスタンスアプローチよりも安全です。コミュニティがそれを分析し、フィードバックを提供し、より複雑なプロジェクトや代替プロジェクトの実装の出発点として使用することを願っています。



実装



アルゴリズムの説明に進む前に、既製の実装へのリンクをいくつか示します。それらは参照用に使用できます。

• Redlock-rb（Rubyの実装）。Redlock-rbのフォークもあります。これは、これだけでなく、配布を容易にするためのパッケージ（gem）を追加します。
• Redlock-py（Python実装）。
• Aioredlock（Asyncio Pythonの実装）。
• Redlock-php（PHP実装）。
• PHPRedisMutex ( PHP)
• cheprasov/php-redis-lock (PHP- )
• Redsync ( Go).
• Redisson ( Java).
• Redis::DistLock ( Perl).
• Redlock-cpp ( C++).
• Redlock-cs ( C#/.NET).
• RedLock.net ( C#/.NET). async lock.
• ScarletLock ( C# .NET )
• Redlock4Net ( C# .NET)
• node-redlock ( NodeJS). .

セキュリティと可用性の保証



分散ロックを効果的に使用するために必要な最小限の保証を提供すると思われる3つのプロパティのみを使用して設計をモデル化します。

1. セキュリティプロパティ：相互除外。一度に1つのクライアントのみがロックを保持できます。
2. アクセシビリティプロパティA：デッドロックはありません。最終的に、リソースをロックしたクライアントに障害が発生したり、別のディスクセグメントに移動したりした場合でも、常にロックを取得できます。
3. アクセシビリティプロパティB：フォールトトレランス。ほとんどのRedisノードが実行されている間、クライアントはロックを取得して解放できます。

この場合、フェイルオーバーベースの実装では不十分な理由

何を改善するかを理解するために、Redisに基づくほとんどの分散ロックライブラリの現状を分析してみましょう。



Redisを使用してリソースをロックする最も簡単な方法は、インスタンスにキーを作成することです。通常、キーは限られた有効期間で作成されます。これは、Redisで提供される有効期限機能を使用して実現されるため、遅かれ早かれこのキーがリリースされます（リストのプロパティ2）。クライアントがリソースを解放する必要がある場合、クライアントはキーを削除します。



一見、このソリューションはうまく機能しますが、問題があります。アーキテクチャに単一の障害点があります。マスターRedisインスタンスに障害が発生した場合はどうなりますか？それではフォロワーを追加しましょう！また、ホストが利用できない場合に使用します。残念ながら、このオプションは実行可能ではありません。これを行うと、Redisのレプリケーションは非同期であるため、セキュリティに必要な相互除外プロパティを正しく実装できなくなります。



明らかに、このようなモデルではレース条件が発生します。

1. クライアントAはマスターのロックを取得します。
2. キーへの書き込みがスレーブに転送される前に、マスターは失敗します。
3. フォロワーはリーダーに昇格します。
4. クライアントBは、Aによってすでにロックされているのと同じリソースのロックを取得します。セキュリティ違反！

障害などの特別な状況では、複数のクライアントが同時にロックを保持できることが完全に正常な場合があります。このような場合、レプリケーションベースのソリューションを適用できます。それ以外の場合は、この記事で説明されているソリューションをお勧めします。



正しいシングルインスタンスの実装



上記のシングルインスタンス構成の欠点を克服する前に、この単純なケースを処理する方法を理解しましょう。これは、レース条件が時折許容されるアプリケーションで実際に許容されるためです。また、単一のインスタンスでのロックは、ここで説明する分散アルゴリズムの基礎として機能するためです。



ロックを取得するには、次のようにします。



SET resource_name my_random_value NX PX 30000



このコマンドは、有効期限が30,000ミリ秒（オプションPX）で、キーがまだ存在しない場合（オプションNX）にのみキーをインストールします。キーは「myrandomvalue」に設定されています。この値は、すべてのクライアントおよびすべてのロック要求で一意である必要があります。

基本的に、ランダムな値はロックを安全に解放するために使用され、キーが存在し、そこに格納されている値が正確に期待どおりである場合にのみキーを削除するように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バイトになるはずですが、達成しようとしている目的に十分なだけ文字列を一意にするためのより安価な方法を見つけることができます。たとえば、RC4に/ dev / urandomをシードして、それに基づいて疑似ランダムストリームを生成しても問題ありません。より簡単な解決策は、マイクロ秒の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で取得）からさらに時間を引いた時間（合計プロセス間の時間差を補正するために数ミリ秒）。



次の興味深い記事では、タイミングギャップを必要とするこのようなシステムについて詳しく説明しています。リース：分散ファイルキャッシュの一貫性のための効率的なフォールトトレラントメカニズム。



失敗時に再試行



クライアントがロックの取得に失敗した場合、ランダムな遅延を使用して、再度取得を試みる必要があります。これは、同じリソースのロックを同時に取得しようとする複数のクライアントを非同期化するために行われます（これにより、勝者がいないスプリットブレインの状況が発生する可能性があります）。さらに、クライアントがほとんどのRedisインスタンスでロックを取得しようとする速度が速いほど、スプリットブレイン状況が発生する可能性のあるウィンドウが狭くなります（再試行が少なくて済みます）。したがって、理想的には、クライアントは多重化を使用してN個のインスタンスに同時にSETコマンドを送信しようとする必要があります。



ここで強調する価値があるのは、ほとんどのロックを取得できなかったクライアントが、取得したロックを（部分的に）解放して、リソースのロックを再度取得できるようになる前にキーの有効期限を待つ必要がないようにすることです（ネットワークの断片化が発生した場合でも）クライアントがRedisインスタンスとの接続を失った場合、キーの有効期限が切れている間、アクセス違反のペナルティを支払う必要があります）。



ロックの



解除ロックの解除は、特定のインスタンスを正常にロックできたと顧客が考えているかどうかに関係なく、すべてのインスタンスのロックを解除するだけの簡単な操作です。



安全上の考慮事項



アルゴリズムは安全ですか？さまざまなシナリオで何が起こるか想像してみましょう。



まず、クライアントがほとんどのインスタンスでロックを取得できたと仮定しましょう。各インスタンスには、全員が同じ有効期間を持つキーが含まれます。ただし、これらの各キーはそれぞれの時点でインストールされているため、異なる時間に期限切れになります。ただし、最初のキーがT1（最初のサーバーに接続する前に選択した時間）以上の時間にインストールされ、最後のキーがT2（最後のサーバーから応答を受信した時間）以上の時間にインストールされた場合、期限切れになるセットの最初のキーが少なくとも続くことを確認してくださいMIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT..。他のすべてのキーは後で期限切れになるため、少なくとも今回はすべてのキーが同時に有効になることを確認できます。



N / 2 + 1キーがすでに存在する場合、N / 2 + 1 SET NX操作は成功できないため、ほとんどのキーが有効なままである間、別のクライアントはロックを取得できません。したがって、ロックが取得された場合、同時に再取得することはできません（これは相互排除のプロパティに違反します）。

ただし、同時にロックを取得しようとする複数のクライアントが同時に成功しないようにする必要があります。



クライアントがほとんどのインスタンスをロックし、この時間の最大ロック期間以上を費やしている場合、クライアントはロックを無効にし、インスタンスのブロックを解除します。したがって、お客様が有効期限内にほとんどのインスタンスをブロックできた場合のみを考慮する必要があります。この場合、上記の議論に関して、MIN_VALIDITYクライアントは時間内にロックを再取得できないはずです。したがって、複数のクライアントは、大部分をロックする時間がTTL時間よりも長く、ロックが無効になった場合にのみ、同じ時間（ステージ2の終わりで終了）でN / 2 +1インスタンスをロックできます。



セキュリティの正式な証拠を提供したり、既存の同様のアルゴリズムを指摘したり、上記のバグを見つけたりできますか？ 可用性



に関する考慮事項



システムの可用性は、次の3つの主な特性によって異なります。

1. ロックの自動解放（キーの有効期限が切れたとき）：最終的に、キーはロックに使用できるようになります。
2. クライアントは通常、目的のロックが取得されていないか、取得されて作業が完了したときにロックを削除することで互いに助け合うという事実。したがって、ロックを再取得するためにキーの有効期限が切れるのを待つ必要はない可能性があります。
3. 顧客がロックを取得するために再試行する必要がある場合、ほとんどのロックを取得するのにかかる時間よりも比較的長い時間待機するという事実。これにより、リソースを奪い合うときに脳が分裂する可能性が低くなります。

ただし、ネットワークセグメントのTTL時間に等しい可用性の低下に対してペナルティを支払う必要があるため、連続するセグメントがある場合、このペナルティは未定義のサイズになる可能性があります。これは、クライアントがロックを取得し、それを解放する前に別のセグメントにクランプするたびに発生します。



原則として、無限の連続したネットワークセグメントが与えられると、システムは無限の期間使用できなくなる可能性があります。



パフォーマンス、フェイルオーバー、およびfsync



多くの人がRedisを使用します。これは、ロックサーバーの高性能、ロックの取得と解放に必要な遅延のレベル、および1秒あたりに実行できるそのような取得/解放操作の数を提供する必要があるためです。この要件を満たすために、遅延を減らすためのNRedisサーバーとの通信戦略があります。これは多重化戦略です（または、クライアントと各インスタンス間のラウンドトリップ時間が類似していると仮定して、ソケットを非ブロッキングモードにし、すべてのコマンドを送信し、後でコマンドを読み取る貧乏人の多重化）。



確かに、障害後の信頼性の高いリカバリを備えたモデルを作成するかどうかを検討するための長期的なデータストレージの考慮事項もあります。



基本的に、問題を明確にするために、長期的なデータストレージをまったく使用せずにRedisを構成していると仮定します。クライアントは、5つのインスタンスのうち3つをブロックすることに成功しました。クライアントがブロックできたインスタンスの1つが再起動され、この時点で同じリソースに対して3つのインスタンスが再び表示されます。これをブロックできます。次に、他のクライアントが再起動されたインスタンスをブロックして、セキュリティプロパティに違反します。ロックの独占権。



データアドバンス（AOF）を有効にすると、状況はわずかに改善されます。たとえば、SHUTDOWNコマンドを送信してから再起動することで、サーバーを昇格させることができます。 Redisの有効期限操作は、サーバーの電源がオフになっていても時間が流れ続けるように意味的に実装されているため、すべての要件で問題ありません。通常のシャットダウンが保証されている限り、通常です。停電が発生した場合はどうすればよいですか？ Redisがデフォルトで構成されており、fsyncがディスク上で毎秒同期している場合、再起動後にキーを見逃す可能性があります。理論的には、インスタンスの再起動時にロックの安全性を保証する場合は、有効にする必要がありますfsync=always長期データストレージの設定で。これにより、分散ロックを安全に実装するために従来使用されていたCPシステムのレベルまで、パフォーマンスが完全に低下します。



しかし、状況は目に見えるよりも良いです。原則として、インスタンスが障害後に再起動されると、現在アクティブなロックに参加しなくなるため、アルゴリズムは安全なままです。



これを確実にするには、障害が発生した後、使用している最大TTLをわずかに超えてインスタンスが一定期間使用できないことを確認する必要があります。そのため、拒否時にアクティブだったすべてのキーの有効期限が切れて自動的に解放されるのを待ちます。



遅延再起動を使用することにより、原則として、Redisで長期間永続化することなくセキュリティを実現できます。ただし、これによりアクセシビリティが低下する可能性があることに注意してください。たとえば、ほとんどのインスタンスに障害が発生した場合、システムはTTL時間の間グローバルに使用できなくなります（この時点ではリソースをブロックできません）。



アルゴリズムの可用性の向上：ロックの拡張



クライアントが行う作業が小さなステップで構成されている場合、デフォルトのロックの有効期限を短縮し、ロック延長メカニズムを実装することができます。基本的に、クライアントが計算でビジーで、ロックの有効期限の値が危険なほど低い場合、キーがまだ存在し、その値がまだランダムで、ロックが取得されたときに取得された場合、キーのTTLを拡張するスクリプトをすべてのインスタンスに送信できます。



顧客は、有効期間中にほとんどのインスタンスを正常にロックした場合にのみ、ロックを再取得したと見なす必要があります。



ただし、技術的には、これによってアルゴリズムが変更されることはないため、ロックを取得するための最大繰り返し試行回数を制限する必要があります。そうしないと、アクセシビリティプロパティに違反します。