「分散ロック」を理解するには、この記事を読んでください。

しかし、分散システムの急速な発展により、ローカル ロックではニーズを満たせないことが多くなり、上記のロック方法は分散環境では効果がなくなってしまいます。

そのため、分散環境でローカルロックの効果を実現するために、さまざまなトリックが考案されてきました。今日は、分散ロックを実装するための一般的なルーチンについて説明します。

分散ロックはなぜ必要なのでしょうか?

Martin Kleppmann 氏は、英国ケンブリッジ大学の分散システムの研究者です。彼は以前、Redis の生みの親である Antirez と、RedLock (後述) が安全かどうかについて激しい議論を交わしていました。

Martin は、分散ロックは一般的に次の 2 つのシナリオで使用されると考えています。

• 効率: 分散ロックを使用すると、異なるノードが同じ作業を繰り返すことを防ぎ、リソースを無駄にすることがなくなります。たとえば、ユーザーが支払いを済ませた後、異なるノードで複数のテキスト メッセージが送信されることがあります。
• 正確性: 分散ロックを追加すると、正確性違反の発生も回避できます。 2 つのノードが同じデータに対して操作する場合、たとえば、複数のノード マシンが同じ注文に対して異なるプロセスを実行すると、注文の最終状態でエラーが発生し、損失が発生する可能性があります。

分散ロックの特徴

異なるノードに分散ロックが必要であると判断した場合、分散ロックが持つべき特性を理解する必要があります。

分散ロックの特徴は次のとおりです。

• 相互排他性: ローカル ロックと同様に、相互排他性は最も基本的なものですが、分散ロックでは、異なるノード上の異なるスレッドの相互排他性を確保する必要があります。
• 再入可能性: 同じノード上の同じスレッドは、ロックを取得した後、再度ロックを取得できます。
• ロック タイムアウト: ローカル ロックと同様に、デッドロックを防ぐためにロック タイムアウトをサポートします。
• 効率性と高可用性: ロックとロック解除は効率的である必要があり、分散ロックの失敗とダウングレードの増加を防ぐために高可用性を保証する必要があります。
• ブロッキングと非ブロッキングをサポートします。ReentrantLock と同様に、lock、trylock、tryLock(long timeOut) をサポートします。
• 公平なロックと不公平なロックをサポートします (オプション): 公平なロックは、要求された順序でロックが取得されることを意味しますが、不公平なロックは順序付けされません。通常、これが達成されることはほとんどありません。

一般的な分散ロック

いくつかの特性を理解した後、一般的には分散ロックを次の方法で実装します。

• マイグレーション
• ゼック
• レディス
• 自社開発の分散ロック: Google の Chubby など。

以下では、これらの分散ロックの実装原理を個別に紹介します。

マイグレーション

まず、MySQL 分散ロックの実装原理について説明します。これは比較的理解しやすいです。結局のところ、データベースは私たちの開発者の日々の開発に密接に関係しています。

分散ロックの場合は、ロック テーブルを作成できます。

前述の lock()、trylock(long timeout)、trylock() メソッドは、次の疑似コードを使用して実装できます。

ロック（）

ロックは通常、ブロックロックの取得であり、ロックが取得されるまで停止しないことを意味します。次に、その操作を実行するための無限ループを記述します。

mysqlLock.lcok には SQL ステートメントが含まれています。再入可能ロックの効果を得るには、まずそれを照会する必要があります。値がある場合は、node_info を比較して一貫性があるかどうかを確認する必要があります。

ここでの node_info は、マシン IP とスレッド名で表すことができます。一貫性がある場合は、再入可能ロック カウント値が追加されます。矛盾する場合は false が返されます。値がない場合は、データを直接挿入します。

疑似コードは次のとおりです。

このコードセクションではトランザクションを追加する必要があり、この一連の操作のアトミック性が保証される必要があることに注意してください。

tryLock() と tryLock(long timeout)

tryLock() は非ブロッキングロック取得メソッドです。ロックを取得できない場合は、すぐに戻ります。コードは次のとおりです。

tryLock(long timeout) は次のように実装されます。

mysqlLock.lock は上記と同じですが、select ... for update はブロッキング行ロックであることに注意してください。同じリソースの同時実行量が大きい場合、ブロッキング ロックに悪化する可能性があります。

ロック解除()

ロック解除を使用すると、ここでのカウントが 1 であれば削除できます。 1 より大きい場合は、1 を引く必要があります。

ロックタイムアウト

マシン ノードがダウンしている場合、ロックは解除されません。スケジュールされたタスクを開始し、タスクの処理に通常かかる時間を計算できます。

たとえば、5ms の場合は、少し拡張することができます。ロックが 20 ミリ秒以上解除されない場合、ノードがハングしていると判断して直接解除することができます。

MySQLの概要:

• 適用可能なシナリオ: MySQL 分散ロックは、通常、データベースに存在しないリソースに適用できます。注文などのデータベースが存在する場合は、上記の面倒な手順を実行せずに、このデータに行ロックを直接追加できます。

たとえば、注文の場合、更新時に select * from order_table where id = 'xxx' を使用して行ロックを追加し、他のトランザクションがそれを変更できないようにすることができます。

• 利点: 理解しやすく、追加のサードパーティミドルウェア (Redis、ZK など) を維持する必要がありません。
• デメリット: 理解するのは簡単ですが、実装は複雑です。ロックのタイムアウト、トランザクションの追加などを考慮する必要があります。パフォーマンスはデータベースに制限され、通常はキャッシュよりも低くなります。同時実行性の高いシナリオにはあまり適していません。

楽観的ロック

以前にも悲観的ロックを紹介しました。ここで、楽観的ロックについて触れておきたいと思います。行ロックを追加するとパフォーマンス コストが比較的大きくなり、通常はそれほど競争力がないため、実際のプロジェクトでは楽観的ロックを実装することがよくあります。

ただし、同時実行の順次実行が楽観的ロックを使用して処理されるようにする必要があります。テーブルにバージョン番号フィールドを追加できます。

バージョン番号を照会した後、更新または削除するときには、照会したバージョン番号に基づいて、現在のデータベースが照会したバージョン番号と等しいかどうかを判断する必要があります。等しい場合は実行できます。そうでない場合は実行できません。

このような戦略は、比較とスワップがアトミック操作である CAS (Compare And Swap) と非常によく似ています。この方法では、更新行ロックに select * を追加するオーバーヘッドを回避できます。

動物園飼育員

ZooKeeper も分散ロックを実装するための一般的な方法です。データベースと比較すると、ZooKeeper について知らないと始めるのが難しいかもしれません。

ZooKeeper は、Paxos アルゴリズムに基づく分散アプリケーション調整サービスです。 ZK のデータノードはファイルディレクトリに似ているため、この機能を使用して分散ロックを実装できます。

リソースをディレクトリとして使用し、このディレクトリの下のノードがロックを取得する必要があるクライアントになります。ロックを取得していないクライアントは、ウォッチャーを前のクライアントに登録する必要があります。これは次の図で表すことができます。

/lock はロックに使用するディレクトリ、/resource_name はロックするリソース、その下のノードはロックする順序で配置されます。

キュレーター

Curator は基盤となる ZooKeeper API をカプセル化することで、ZooKeeper の操作をより簡単かつ便利にし、分散ロック機能をカプセル化することで、独自に実装する必要がなくなります。

Curator は、再入可能ロック (InterProcessMutex) と非再入可能ロック (InterProcessSemaphoreMutex) の両方を実装します。読み取り/書き込みロックは再入可能ロックにも実装されています。

プロセス間ミューテックス

InterProcessMutex は、Curator によって実装された再入可能ロックです。次のコードを使用して再入可能ロックを実装できます。

ロックするには acuire を使用し、ロック解除するには release を使用します。

ロックのプロセスは次のとおりです。

• まず、再入可能かどうかの判定を行います。ここでの再入可能ロックはConcurrentMapに記録されます。

threadData.get(currentThread) に値がある場合、それが再入可能ロックであることが証明され、レコードが 1 増加します。

以前の MySQL は実際にこの方法で最適化できます。 count フィールドの値は不要になりました。ローカルでメンテナンスするとパフォーマンスが向上します。

• 次に、リソース ディレクトリにノードを作成します。たとえば、ここにノード /0000000002 を作成します。このノードは EPHEMERAL_SEQUENTIAL に設定する必要があります。これは、一時的なノードであり、順序付けられていることを意味します。
• 現在のディレクトリ内のすべての子ノードを取得し、自分のノードが最初の子ノードであるかどうかを判断します。
• 最初であればロックが取得され、戻ることができます。
• 最初のものでない場合は、誰かがすでにロックを取得していることを意味するため、自分のノードの前のノードを取得する必要があります。

/0000000002 の前のノードは /0000000001 です。このノードを取得したら、そのノードに Watcher を登録します (ここでの Watcher は実際には object.notifyAll() を呼び出してブロックを解除します)。

• object.wait(timeout) または object.wait(): ブロック待機。これはステップ 5 の Watcher に対応します。

ロック解除プロセス:

• まず、ロックが再入可能かどうかを判断します。再入可能なロックがある場合は、回数から 1 を引くだけです。ロック回数から 1 を引いた値が 0 の場合は、次の手順に進みます。 0 でない場合は直接戻ります。
• 現在のノードを削除します。
• threadDataMap 内の再入可能ロック データを削除します。

読み取り書き込みロック

Curator は読み取り/書き込みロックを提供します。その実装クラスは InterProcessReadWriteLock です。ここでの各ノードには次のプレフィックスが付きます:

プライベート静的最終文字列 READ_LOCK_NAME = "__READ__" ;
プライベート静的最終文字列 WRITE_LOCK_NAME = "__WRIT__" ;

読み取りロックか書き込みロックかを区別するために、異なるプレフィックスが使用されます。読み取りロックの場合、その前に書き込みロックが見つかった場合は、それに最も近い書き込みロックにウォッチャーを登録する必要があります。書き込みロックのロジックは、4.2 での以前の分析と同じです。

ロックタイムアウト

ZooKeeper ではロック タイムアウトを構成する必要はありません。ノードを一時ノードとして設定しているため、各マシンは ZK セッションを維持します。このセッションを通じて、ZK はマシンがダウンしているかどうかを判断できます。

マシンがクラッシュした場合、対応する一時ノードは削除されるため、ロックのタイムアウトを心配する必要はありません。

ZK要約:

• 利点: ZK ではロック タイムアウトを心配する必要がなく、実装用の既製のサードパーティ パッケージが用意されているため、より便利です。読み取り/書き込みロックもサポートします。 ZK はロックされた順序でロックを取得するため、公平なロックとなります。高可用性を確保するため、ZK クラスターが使用されます。
• デメリット: ZK には追加のメンテナンスが必要であり、メンテナンス コストが増加します。パフォーマンスは MySQL とそれほど変わらず、依然として比較的低いです。そして、開発者は ZK が何であるかを理解する必要があります。

レディス

インターネットで分散ロックを検索すると、最も一般的な実装は Redis です。 Redis は、優れたパフォーマンスとシンプルな実装により非常に人気があります。

Redis分散ロックのシンプルな実装

Redis に精通している学生は、setNx (存在しない場合は設定) メソッドにも精通している必要があります。存在しない場合は更新されます。分散ロックを実装するのに有効です。

リソースをロックするには、次のものだけが必要です。

 setNx リソース名の値

ここに問題があります。ロック後、マシンがクラッシュするとロックが解除されないため、有効期限が追加されます。有効期限を追加するには、setNx と同じアトミック操作が必要です。

Redis 2.8 より前では、目的を達成するには Lua スクリプトを使用する必要がありましたが、Redis 2.8 以降では、Redis は nx 操作と ex 操作を同じアトミック操作としてサポートします。

 resourceName の値を設定するex 5 nx

レディス

Java 開発者なら誰でも、Redis の Java 実装クライアントである Jedis を知っています。その API は、Redis コマンドに対して比較的包括的なサポートを提供します。

Redission も Redis クライアントであり、その機能は Jedis よりもシンプルです。 Jedis は Redis と対話するためにブロッキング I/O を使用するだけですが、Redis は Netty を通じてノンブロッキング I/O をサポートします。

Jedis の最新バージョン 2.9.0 は 2016 年にリリースされ、ほぼ 3 年間更新されていませんが、Redis の最新バージョンは 2018 年 10 月に更新されました。

Redission は、java.util.concurrent.locks.Lock のインターフェースを継承するロックの実装をカプセル化します。これにより、ローカルのロックを操作するのと同じように、Redission のロックを操作できるようになります。

分散ロックを実装する方法は次のとおりです。

Redis は、いくつかの Java 組み込みメソッド (lock、tryLock) を提供するだけでなく、非同期プログラミングに便利な非同期ロックも提供します。

内部ソースコードが多数あるため、ソースコードは掲載しません。ここでは、テキストの説明を使用して、ロック方法を分析します。以下は tryLock メソッドの分析です。

① ロックしてみる：まずはロックしてみます。古いバージョンのRedisとの互換性を保つ必要があるため、ex、nxアトミック操作APIを直接使用することはできず、Luaスクリプトのみ使用できます。関連する Lua スクリプトは次のとおりです。

操作を実行するために sexNx を使用せず、ハッシュ構造を使用していることがわかります。ロックする必要がある各リソースは、HashMap と見なすことができます。ロックされたリソースのノード情報がキーとなり、ロックの数が値となります。

この方法はリエントラント効果を非常にうまく実現できます。再入可能ロックを実行するには、値に 1 を追加するだけです。もちろん、最適化のために、前述したローカル カウントを使用することもできます。

②ロックに失敗した場合は、タイムアウトしたかどうかを判断します。そうであれば、false を返します。

③ロックが失敗してもタイムアウトがない場合は、redisson_lock__channel+lockName というチャンネルをサブスクライブしてロック解除メッセージをサブスクライブし、タイムアウトになるかロック解除メッセージが出るまでブロックする必要があります。

④ ロックが最終的に取得されるか、ロックを取得する手順がタイムアウトするまで、手順 1、2、3 を再試行します。

私たちのロック解除方法は比較的シンプルで、Lua スクリプトを通じてもロック解除されます。再入可能ロックの場合は、1 を引くだけです。ロックしていないスレッドがスレッドのロックを解除すると、ロック解除は失敗します。

Redission には公平なロック実装もあります。公平なロックのために、リスト構造とハッシュセット構造を使用して、キューに入れられたノードとノードの有効期限をそれぞれ保存します。これら 2 つのデータ構造は、公平なロックを実装するのに役立ちます。ここでは詳しく紹介しません。ご興味がございましたら、ソースコードをご参照ください。

レッドロック

マシン A がロックを申請した後、Redis マスターがクラッシュし、スレーブがまだロックを同期しておらず、再度申請したときにマシン B が再びロックを取得するというシナリオを想像してみましょう。

この問題を解決するために、Redis の作者は RedLock アルゴリズムを提案し、Redission にも RedLock を実装しました。

上記のコードを通じて、複数の Redis クラスターを実装し、赤いロックをロックおよびロック解除する必要があります。

具体的な手順は次のとおりです。

① まず、Redis クラスターの Rlock を複数生成し、RedLock に構築します。

② 3つのクラスターを順番にロックします。ロックのプロセスは 5.2 と同じです。

③巡回ロック処理中にロックに失敗した場合、ロック失敗回数が最大値を超えていないか判定する必要がある。ここでの最大値はクラスターの数に基づきます。たとえば、3 つある場合、失敗は 1 つだけ許可されます。 5 つの場合、大多数の成功を確実にするために、失敗は 2 つだけ許可されます。

④ ロック処理中に、ロックがタイムアウトしたかどうかを判断する必要があります。ロックに 3 ミリ秒しかかからないように設定しているのに、最初のクラスター ロックですでに 3 ミリ秒が消費されている可能性があります。するとロックが失敗します。

⑤手順3と4でロックに失敗した場合は、ロック解除操作が実行され、ロック解除では一度にすべてのクラスターのロック解除が要求されます。

RedLock の基本原則は、複数の Redis クラスターを使用し、大多数のクラスターで正常にロックして、Redis クラスターの障害によって分散ロックの問題が発生する可能性を減らすことであることがわかります。

Redis の概要:

• 利点: Redis の実装が簡単で、ZK や MySQL よりもパフォーマンスが優れています。特に複雑な要件が必要ない場合は、setNx を使用して自分で実装できます。複雑な要件が必要な場合は、Redission を使用したり、Redission から学習したりできます。 RedLock は、厳しい要件のある一部のシナリオで使用できます。
• デメリット: Redis クラスターをメンテナンスする必要があります。 RedLock を実装する場合は、さらに多くのクラスターを維持する必要があります。

分散ロックのセキュリティ問題

上記では赤いロックを紹介しましたが、Martin Kleppmann 氏はそれでも安全ではないと考えています。

Martin の反論に関しては、RedLock に限ったことではないと思います。基本的に、上記のすべてのアルゴリズムにこの問題があります。これらの問題について以下で議論しましょう。

GC の長い一時停止

Java に精通している学生は GC にも精通している必要があります。 GC 中に STW (stop-the-world) が発生します。

たとえば、CMS ガベージ コレクターには、参照が継続的に変更されるのを防ぐための 2 つの STW フェーズがあります。すると、次のような状況が発生する可能性があります (Redlock を反駁する Martin の記事から引用)。

クライアント1はロックを取得し、ロック タイムアウトを設定します。ただし、その後、クライアント 1 では長い STW 期間が発生し、分散ロックが解放されます。

クライアント2がロックを取得し、クライアント1がロックを復元します。すると、クライアント 1 とクライアント 2 が同時にロックを取得し、分散ロックのセキュリティ上の問題が発生します。

これは RedLock に限ったことではありません。当社の ZK と MySQL にも同じ問題があります。

時計が飛ぶ

Redis サーバーの時刻がジャンプすると、ロックの有効期限に確実に影響します。

そうすると、ロックの有効期限が予想どおりではなくなり、クライアント 1 とクライアント 2 が同じロックを取得する可能性があり、安全でない可能性があります。これは MySQL でも発生します。ただし、ZK は有効期限を設定していないため、ジャンプの影響を受けません。

長いネットワークI/O

この問題は、GC の STW と非常によく似ています。つまり、ロックを取得した後、ネットワーク呼び出しを行い、呼び出し時間がロックの有効期限よりも長くなる可能性があり、その場合は安全でない問題が発生します。 MySQL でもこの問題は発生しますが、ZK ではこの問題は発生しません。

これら 3 つの問題については、Redis の作者を含め、オンラインで多くの議論が行われています。

GCのSTW

ほぼ全員がこの問題に悩まされることがわかります。マーティンは解決策を提示した。 ZK の場合、自己増分シーケンスが生成されます。次に、実際にリソースを操作するときに、現在のシーケンスが最新であるかどうかを判断する必要があります。これは、楽観的ロックに少し似ています。

もちろん、Redis の作者はこの解決策に反論しました。自己増加シーケンスを生成できるため、それをロックする必要はまったくありません。つまり、MySQL の楽観的ロックに似たソリューションに従って実行できます。

個人的には、この解決策は複雑さを増すと思います。リソースを操作するときは、シリアル番号が最新であるかどうかを判断する必要があります。どのような判断方法を採用しても、複雑さは増します。後ほど、より良い解決策を提案する Google の Chubby を紹介します。

時計が飛ぶ

Martin 氏は、RedLock が安全でない大きな理由もクロック ジャンプにあると考えています。ロックの有効期限は時間に大きく依存しますが、ZK は時間に依存する必要はなく、各ノードのセッションに依存するためです。

Redis の作者も回答を出しており、時間のジャンプについては手動調整と NTP 自動調整に分かれています。

• 人間による調整: 人間による調整の影響は、制御可能な人間による調整によって完全に排除できます。
• NTP 自動調整: ジャンプ時間を制御可能な範囲内に保つように最適化できます。ジャンプはありますが、全く問題ありません。

長いネットワークI/O

これは彼らの議論の焦点では​​ありません。個人的には、この問題の最適化により、ネットワーク呼び出しのタイムアウトを制御し、すべてのネットワーク呼び出しのタイムアウトを合計できると考えています。

そうすると、ロックの有効期限は実際にはこの時間よりも長くなるはずです。もちろん、シリアルをパラレル、非同期などに変更するなど、ネットワーク呼び出しを最適化することもできます。

Chubbyの最適化

ZK を検索すると、ZK は Chubby のオープンソース実装であり、Chubby の内部動作原理は ZK に似ていると書かれていることがわかります。しかし、分散ロックとしての Chubby の位置付けは ZK とは少し異なります。

Chubby も、分散セキュリティの問題を解決するために上記の自己増分シーケンス ソリューションを使用していますが、複数の検証方法を提供しています。

• CheckSequencer(): Chubby の API を呼び出して、現時点でシーケンス番号が有効かどうかを確認します。
• リソース サーバーにアクセスして、現在のリソース サーバーの最新のシリアル番号と当社のシリアル番号のサイズを確認し、決定します。
• lock-delay: 検証ロジックがリソース サーバーに侵入するのを防ぐために、クライアントが接続を失ったときにすぐにロックを解除せず、一定時間 (デフォルトは 1 分) 内に他のクライアントがロックを取得できないようにする方法を提供します。

これは、STW 回復を待機するために一定のバッファが与えられることを意味します。 GC の STW 時間が 1 分を超える場合は、分散ロックを疑うのではなく、プログラムを確認する必要があります。

まとめ

この記事では主に、さまざまな分散ロックの実装方法と、それらの長所と短所について説明します。最後に、分散ロックのセキュリティ問題についても話しました。

ビジネスによって必要なセキュリティのレベルはまったく異なります。ビジネスシナリオに基づいてさまざまな側面から分析し、最適なソリューションを選択する必要があります。