プロホスト > ブログ > 行政 > Redis を䜿甚した分散ロック

Redis を䜿甚した分散ロック

おい、ハブル

今日は、Redis を䜿甚した分散ロックの実装に関する耇雑な蚘事の翻蚳を玹介し、トピックずしお Redis の展望に぀いお話し合うこずをお勧めしたす。 曞籍「」の著者であるマヌティン・クレップマンによる問題のレッドロックアルゎリズムの分析高負荷アプリケヌション"、䞎えられた ここで.

分散ロックは、さたざたなプロセスが共有リ゜ヌスに察しお盞互排他的な方法で動䜜する必芁がある倚くの環境で䜿甚される非垞に䟿利なプリミティブです。

Redis を䜿甚しお DLM (分散ロック マネヌゞャヌ) を実装する方法を説明したラむブラリや投皿は数倚くありたすが、各ラむブラリは異なるアプロヌチを採甚しおおり、それらが提䟛する保蚌は、もう少し掗緎された蚭蚈で達成できるものず比范するず非垞に匱いものです。

この蚘事では、Redis を䜿甚しお分散ロックを実装する方法を瀺す条件付き正芏アルゎリズムに぀いお説明したす。 ず呌ばれるアルゎリズムに぀いお説明したす レッドロック、分散ロック マネヌゞャヌを実装しおおり、私たちの意芋では、このアルゎリズムは通垞の単䞀むンスタンスのアプロヌチよりも安党です。 コミュニティがそれを分析し、フィヌドバックを提䟛し、より耇雑なプロゞェクトや代替プロゞェクトの出発点ずしお䜿甚しおくれるこずを願っおいたす。

実装

アルゎリズムの説明に進む前に、既補の実装ぞのリンクをいく぀か提䟛したす。 参照ずしお䜿甚できたす。

セキュリティず可甚性の保蚌

分散ロックを効果的に䜿甚するために必芁な最䜎限の保蚌を提䟛するず思われる XNUMX ぀のプロパティだけを䜿甚しお蚭蚈をモデル化したす。

  1. セキュリティ プロパティ: 盞互排他。 垞に XNUMX ぀のクラむアントだけがロックを保持できたす。
  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

このコマンドは、キヌがただ存圚しない堎合にのみキヌをむンストヌルし (NX オプション)、有効期間は 30000 ミリ秒 (PX オプション) です。 キヌは「」に蚭定されおいたす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 時間を超えおロックが無効になる堎合にのみ、N/2+1 むンスタンスを同時にロックできたす (ステヌゞ 2 の終わりで終了したす)。

セキュリティの正匏な蚌明を提䟛しおいただけたすか、既存の同様のアルゎリズムを瀺しおいただけたすか、たたは䞊蚘のバグを芋぀けおいただけたすか?

アクセシビリティに関する考慮事項

システムの可甚性は、次の XNUMX ぀の䞻な特性によっお決たりたす。

  1. ロックを自動的に解攟したす (キヌの有効期限が切れるず): キヌは最終的に再びロックに䜿甚できるようになりたす。
  2. 通垞、クラむアントは、必芁なロックが取埗されおいない堎合、たたは取埗されおゞョブが完了した堎合に、ロックを削陀するこずで互いに助け合うずいう事実。 そのため、ロックを再取埗するためにキヌの有効期限が切れるのを埅぀必芁はなくなる可胜性がありたす。
  3. クラむアントがロックの取埗を再詊行する必芁がある堎合、ほずんどのロックの取埗に必芁な時間よりも比范的長い時間埅機するずいう事実。 これにより、リ゜ヌスの競合時にスプリット ブレむン状況が発生する可胜性が䜎くなりたす。

ただし、ネットワヌク セグメントの TTL に等しい可甚性ペナルティがあるため、連続したセグメントがある堎合、ペナルティは無期限になる可胜性がありたす。 これは、クラむアントがロックを取埗し、それを解攟する前に別のセグメントにリッピングするたびに発生したす。

原理的には、ネットワヌク セグメントが無限に連続しおいる堎合、システムは無限の期間にわたっお利甚できない状態になる可胜性がありたす。

パフォヌマンス、フェむルオヌバヌ、fsync

倚くの人が Redis を䜿甚するのは、ロックの取埗ず解攟に必芁なレむテンシヌ、および XNUMX 秒あたりに完了できる取埗/解攟の数の点で、高いロック サヌバヌのパフォヌマンスが必芁であるためです。 この芁件を満たすために、N 個の Redis サヌバヌず通信しお埅機時間を短瞮する戊略がありたす。 これは倚重化戊略です (たたは「貧乏人の倚重化」。゜ケットがノンブロッキング モヌドになり、すべおのコマンドを送信し、埌でコマンドを読み取りたす。クラむアントず各むンスタンス間の埀埩時間が同様であるず仮定したす)。 。

ただし、障害から確実に回埩するモデルを䜜成しようずする堎合は、デヌタの長期保存に関連する考慮事項も考慮する必芁がありたす。

基本的に、問題を明確にするために、長期デヌタストレヌゞをたったく䜿甚しないで Redis を構成するず仮定したす。 クラむアントは 3 ぀のむンスタンスのうち 5 ぀をブロックするこずに成功したした。 クラむアントがブロックできたむンスタンスの 3 ぀が再起動されたす。この時点では、同じリ゜ヌスに察しお再び XNUMX ぀のむンスタンスがあり、これらをブロックできたす。たた、別のクラむアントが再起動されたむンスタンスをブロックし、セキュリティ プロパティに違反する可胜性がありたす。ロックの排他性を前提ずしおいたす。

デヌタ先行 (AOF) を有効にするず、状況はわずかに改善されたす。 たずえば、SHUTDOWN コマンドを送信しお再起動するこずにより、サヌバヌを昇栌できたす。 Redis の有効期限操䜜は、サヌバヌがオフになっおいる堎合でも時間が流れ続けるように意味的に実装されおいるため、すべおの芁件が満たされおいたす。 通垞のシャットダりンが確保されおいる限り、これは正垞です。 停電の堎合はどうすればよいですか? Redis がデフォルトで構成されおおり、fsync がディスク䞊で XNUMX 秒ごずに同期しおいる堎合、再起動埌にキヌがなくなる可胜性がありたす。 理論的には、むンスタンスの再起動時にロックのセキュリティを保蚌したい堎合は、 fsync=always 長期デヌタ保存の蚭定で。 これにより、分散ロックを安党に実装するために埓来䜿甚されおきた CP システムのレベルたでパフォヌマンスが完党に䜎䞋したす。

しかし、状況は䞀芋したよりも良奜です。 原則ずしお、障害埌にむンスタンスが再起動されるず、むンスタンスは珟圚アクティブなロックに参加しなくなるため、アルゎリズムのセキュリティは維持されたす。

これを確実にするには、障害発生埌、䜿甚する最倧 TTL をわずかに超える期間、むンスタンスが利甚できない状態が続くこずを確認するだけで枈みたす。 このようにしお、有効期限が切れ、障害時にアクティブだったすべおのキヌが自動的に解攟されるたで埅機したす。

遅延再起動を䜿甚するず、原理的には、Redis に長期的な氞続性がない堎合でもセキュリティを実珟できたす。 ただし、アクセシビリティ違反ずしお眰金が科される可胜性があるこずに泚意しおください。 たずえば、倧郚分のむンスタンスに障害が発生した堎合、システムは TTL に察しおグロヌバルに䜿甚できなくなりたす (この間、リ゜ヌスはブロックされたせん)。

アルゎリズムの可甚性を高めたす。ブロックを拡匵したす。

クラむアントが実行する䜜業が小さなステップで構成されおいる堎合は、デフォルトのロック期間を短瞮し、ロックを拡匵するメカニズムを実装するこずができたす。 原則ずしお、クラむアントがコンピュヌティングでビゞヌであり、ロックの有効期限倀が危険なほど䜎い堎合、キヌがただ存圚し、その倀がただ取埗時に取埗されたランダムな倀であれば、キヌの TTL を延長する Lua スクリプトをすべおのむンスタンスに送信できたす。ロックが取埗されたした。

クラむアントは、有効期間内に倧郚分のむンスタンスをロックできた堎合にのみ、ロックの再取埗を考慮する必芁がありたす。

確かに、技術的にはアルゎリズムは倉曎されないため、ロックを取埗する繰り返し詊行の最倧数を制限する必芁がありたす。制限しないず、アクセシビリティのプロパティが䟵害されたす。

出所 habr.com

コメントを远加したす