分散ロック - Yige

分散型ロック#

内容は以下から引用されています

極客時間コラム:《分散型技術原理とアルゴリズム解析》

誰かが分散型ロックについて質問したら、この文章を渡してください

分散型ロックについてはこの文章で十分です

一、基本概念#

分散型ロックとは、分散環境において、システムが複数のマシンに展開されている場合に、複数プロセス間での分散排他制御を実現するためのロックです。複数のプロセスがロックを確認できるように、ロックは共有ストレージ（例えば Redis、Memcache、データベースなどのサードパーティストレージ）に保存され、複数のプロセスが同じクリティカルリソースに同時にアクセスできるようにします。同時に、共有リソースにアクセスできるのは 1 つのプロセスだけであり、データの一貫性を確保します。

アプリケーションシナリオ#

パフォーマンスと効率の向上: 分散型ロックを使用することで、異なるノードが同じ作業を繰り返すことを避けることができ、これによりリソースの無駄遣いを防ぎます。例えば、ユーザーが支払いを行った後、異なるノードが複数の SMS を送信する可能性があります。
データの正確性の保証: 分散型ロックを使用することで、正確性の破壊を防ぐことができます。例えば、複数のノードが同じデータに対して異なるプロセスを操作する場合、同じ注文に対して異なる処理が行われると、最終的な状態が誤ってしまい、損失を引き起こす可能性があります。

分散型ロックの特徴#

排他性: ローカルロックと同様に、排他性は最も基本的な特性ですが、分散型ロックは異なるノードの異なるスレッド間での排他性を保証する必要があります。
再入性: 同じノードの同じスレッドがロックを取得した場合、再度そのロックを取得することができます。
ロックのタイムアウト: ローカルロックと同様に、ロックのタイムアウトをサポートし、デッドロックを防ぎます。
高効率、高可用性: ロックとアンロックは高効率である必要があり、高可用性を保証して分散型ロックの無効化を防ぎ、ダウングレードを追加できます。
ブロッキングと非ブロッキングのサポート: ReentrantLock と同様に、lock、trylock、tryLock (long timeOut) をサポートします。
公平ロックと非公平ロックのサポート（オプション）: 公平ロックは、リクエストの順序に従ってロックを取得することを意味し、非公平ロックはその逆で無秩序です。一般的には、これは実装されることは少ないです。

分散型ロックを使用する際の注意事項#

分散型ロックのオーバーヘッドに注意
ロックの粒度に注意
ロックの方法

分散型ロックの実装#

データベースに基づく分散型ロック、ここでのデータベースはリレーショナルデータベース（MySQL）を指します。
Redisに基づく分散型ロック
ZooKeeperに基づく分散型ロック
その他のミドルウェアの実装、例えば Consul

二、データベースに基づく分散型ロックの実装#

主キーの一意性に基づく実装#

主キーの一意性の特性を利用し、複数のリクエストが同時にデータベースに送信される場合、データベースは 1 つの操作のみが成功することを保証します。したがって、操作が成功したスレッドがそのメソッドのロックを取得したと見なすことができます。メソッドの実行が完了した後、ロックを解放したい場合は、このデータベースレコードを削除するだけです。

欠点#

データベースの可用性に強く依存し、データベースの単一障害点の問題があります。
```
改善案: データベースの主従高可用性設計を行う
```
失効時間の制限がなく、ロックの解放やデータベースレコードの削除に失敗すると、ブロッキングが発生します。
```
改善案: 定期的なタスクを作成し、一定の時間ごとにデータベース内のタイムアウトデータをクリーンアップする
```
非ブロッキングのみをサポートします。ロックを取得するのはデータベースの insert 操作を通じて行われ、操作が失敗した場合は再度ロックを取得するリクエストを行う必要があります。
```
改善案: スピンロックの考え方を参考にし、外側のwhileループで挿入操作を成功するまで繰り返す
```

再入操作をサポートしていません。同じスレッドがロックを解放する前に再度そのロックを取得することはできません。なぜなら、データ内に一意のレコードが既に存在するからです。

改善案: ReentrantLockの実装思想を参考にし、現在ロックを取得しているマシンのホスト情報とスレッド情報を記録するフィールドを追加します。次回ロックを取得する際にデータベースを照会し、現在のマシンのホスト情報とスレッド情報がデータベースで確認できれば、直接そのロックを割り当てることができます。

非公平ロックであり、ロックを取得できるかどうかは運次第です。

改善案: 中間テーブルを作成し、ロックを待っているスレッドをすべて記録し、作成時間でソートします。最初に作成されたものだけがロックを取得できるようにします。

MySQL データベースでは主キーの衝突防止を行いますが、大規模な並行処理の状況ではロックの現象が発生する可能性があります。
```
改善案: プログラム内で主キーを生成し、データベースによって自動生成された主キーで防止します。
```

テーブルフィールドのバージョン番号に基づく実装#

この戦略は MySQL の MVCC メカニズムに由来し、この戦略自体には特に問題はありませんが、唯一の問題はデータテーブルへの侵入が大きいことです。各テーブルにバージョン番号フィールドを設計し、毎回判断するための SQL を記述する必要があり、データベース操作の回数が増え、高並行性の要求下ではデータベース接続のオーバーヘッドが耐えられないものになります。

データベース排他ロックによる分散型ロックの実装#

クエリ文の後にfor updateを追加すると、データベースはクエリの過程でデータベーステーブルに排他ロックを追加します。特定のレコードに排他ロックが追加されると、他のスレッドはその行のレコードに排他ロックを追加できなくなります。排他ロックを取得したスレッドは分散型ロックを取得したことになります。ロックを取得した後、メソッドのビジネスロジックを実行し、メソッドの実行が完了したら、connection.commit () 操作を通じてロックを解放します。
注意: InnoDB エンジンはロックを追加する際、インデックスを使用して検索する場合にのみ行レベルロックを使用し、そうでない場合はテーブルレベルロックを使用します。ここでは行レベルロックを使用したいので、実行するメソッドのフィールド名にインデックスを追加する必要があります。このインデックスは必ず一意のインデックスとして作成する必要があり、そうでないと複数のオーバーロードメソッドが同時にアクセスできない問題が発生します。オーバーロードメソッドの場合、パラメータの型も追加することをお勧めします。

分析#

主キーの一意性に基づく実装のタイムアウトでロックが解放されない問題とブロッキングロックの問題を解決しました:

for update 文は成功後すぐに返され、失敗時は成功するまでブロッキング状態にあります。
この方法を使用すると、サービスがダウンした後、データベースは自動的にロックを解放します。

不足点：

依然としてデータベースの単一障害点と再入性の問題を直接解決できません。
パフォーマンス上の問題が存在する可能性があります: MySQL はクエリを最適化します。条件にインデックスフィールドを使用しても、データを検索する際にインデックスを使用するかどうかは、MySQL が異なる実行計画のコストを判断して決定します。MySQL が全表スキャンの効率が高いと判断した場合、例えば非常に小さなテーブルに対しては、インデックスを使用しません。この場合、InnoDB はテーブルロックを使用し、行ロックを使用しません。
排他ロックを使用して分散型ロックを行うと、排他ロックが長時間コミットされないと、データベース接続を占有します。類似の接続が多くなると、データベース接続プールが爆発する可能性があります。

三、Redis に基づく分散型ロックの実装#

Redis の setnx ()、expire () メソッドに基づく分散型ロック#

setnx()
setnx の意味は SET if Not Exists で、主に 2 つのパラメータ setnx (key, value) を持ちます。このメソッドは原子的で、key が存在しない場合は現在の key を設定し成功を返します（1）。現在の key が既に存在する場合は、設定に失敗し失敗を返します（0）。

expire()
expire は有効期限を設定します。注意すべきは、setnx コマンドは key のタイムアウトを設定できず、expire () を通じて key を設定する必要があることです。

手順

setnx (lockkey, 1) が成功した場合は 0 を返し、占有に失敗したことを示します。1 を返した場合は占有に成功したことを示します。
expire () コマンドで lockkey にタイムアウトを設定し、デッドロックの問題を回避します。
ビジネスコードの実行が完了したら、delete コマンドを使用して key を削除できます。

注意
最初のステップ setnx () が成功した後、expire () コマンドが成功する前にダウンする現象が発生すると、デッドロックの問題が依然として発生します。

Redis の setnx ()、get ()、getset () メソッドに基づく分散型ロック#

このソリューションの背景は、setnx () と expire () のソリューションに対して存在する可能性のあるデッドロック問題に対していくつかの最適化を行ったものです。

getset()
このコマンドは主に 2 つのパラメータ getset (key, newValue) を持ちます。このメソッドは原子的で、key に newValue を設定し、key の元の旧値を返します。仮に key が元々存在しなかった場合、このコマンドを何度も実行すると、以下のような効果が得られます：

getset (key, "value1") は null を返し、この時 key の値は value1 に設定されます。
getset (key, "value2") は value1 を返し、この時 key の値は value2 に設定されます。
以降同様です。

手順

setnx (lockkey, 現在の時間 + 有効期限) が成功した場合はロック取得成功、0 を返した場合はロック取得失敗、2 に進みます。
get (lockkey) で値 oldExpireTime を取得し、この value 値を現在のシステム時間と比較します。もし現在のシステム時間より小さい場合、このロックはタイムアウトしたと見なし、他のリクエストが再取得できるようにします。3 に進みます。
newExpireTime = 現在の時間 + 有効期限を計算し、getset (lockkey, newExpireTime) は現在の lockkey の値 currentExpireTime を返します。
currentExpireTime と oldExpireTime が等しいかどうかを判断します。等しい場合、現在の getset が成功し、ロックを取得したことを示します。等しくない場合、このロックは他のリクエストに取得されているため、現在のリクエストは失敗を直接返すか、再試行を続けることができます。
ロックを取得した後、現在のスレッドは自分のビジネス処理を開始できます。処理が完了した後、自分の処理時間とロック設定のタイムアウトを比較し、ロック設定のタイムアウトより小さい場合は直接 delete を実行してロックを解放します。タイムアウトより大きい場合は、ロックでの処理は不要です。

その他の拡張ソリューション#

Redlock に基づく分散型ロック
redisson に基づく分散型ロック、GitHub アドレス

四、ZooKeeper に基づく分散型ロックの実装#

ZooKeeper ロック関連の基礎知識#

zkは通常、複数のノード（奇数）で構成され、zab 整合性プロトコルを採用しています。したがって、zk は単一ポイント構造と見なすことができ、データを変更すると内部で自動的にすべてのノードのデータが変更され、その後にクエリサービスを提供します。
zkのデータはディレクトリツリーの形式であり、各ディレクトリは znode と呼ばれ、znode 内にデータを保存できます（一般的に 1M を超えない）。また、子ノードを追加することもできます。
子ノードには3種類のタイプがあります。シーケンシャルノードは、ノードの下にノードを追加するたびに自動的にそのノードの名前に自動インクリメントが付与されます。テンポラリノードは、この znode を作成したクライアントとサーバーが接続を失うと、この znode も自動的に削除されます。最後は通常のノードです。
Watchメカニズムにより、クライアントは各ノードの変化を監視でき、変化が発生するとクライアントにイベントが発生します。

基本的なソリューション#

原理: テンポラリノードと watch メカニズムを利用します。各ロックは通常のノード /lock を占有し、ロックを取得する必要がある場合は /lock ディレクトリにテンポラリノードを作成します。作成が成功すればロック取得成功、失敗すれば watch/lock ノードを監視し、削除操作が行われた後に再度ロックを争います。テンポラリノードの利点は、プロセスがダウンした場合、ロックを自動的に削除してキャンセルできることです。
欠点: ロック取得に失敗したすべてのプロセスが親ノードを監視するため、羊群効果が発生しやすく、ロックを解放した後、すべての待機プロセスが一斉にノードを作成し、高い並行性が発生します。

最適化ソリューション#

原理#

ロックを取得する際、テンポラリシーケンシャルノードを作成します。各ロックノードはノードを作成することに成功しますが、シーケンス番号が異なります。シーケンス番号が最小のノードのみがロックを所有でき、このノードのシーケンス番号が最小でない場合は、シーケンス番号が自分より小さい前のノードを watch します（公平ロック）。

手順#

/lock ノードの下にテンポラリシーケンシャルノード（EPHEMERAL_SEQUENTIAL）を作成します。作成したノードのシーケンス番号が最小かどうかを判断します。最小であればロック取得成功、そうでなければロック取得失敗となり、自分より小さいシーケンス番号の前のノードを watch します。
ロック取得に失敗した場合、watch を設定した後、watch イベントが発生するのを待ち、再度シーケンス番号が最小かどうかを判断します。
ロック取得成功であればコードを実行し、最後にロックを解放します（ノードを削除します）。

五、分散型ロックの安全性の問題#

参考リンク#

GC の STW（stop-the-world）#

Java の仮想マシンは、ガベージコレクションを行う際に STW 現象が発生する可能性があり、全体が一時停止します。例えば、CMS ガベージコレクタは、参照が引き続き変化しないようにするために、2 つの段階で STW を行います。以下のような状況が発生する可能性があります：

図のように、クライアント 1 がロックを取得した後、長時間の GC ポーズが発生し、その間に取得したロックが期限切れになり、クライアント 2 がロックを取得します。クライアント 1 が GC ポーズから復帰したとき、保持していたロックが期限切れになったことを知らず、共有リソース（上図ではストレージサービス）にデータ書き込みリクエストを発起しますが、この時ロックは実際にはクライアント 2 が保持しているため、2 つのクライアントの書き込みリクエストが衝突する可能性があります（ロックの排他作用が無効になります）。

時計のジャンプ#

5 つの Redis ノード A、B、C、D、E があると仮定します：

クライアント 1 が Redis ノード A、B、C からロックを正常に取得しました（多数のノード）。ネットワークの問題により、D と E との通信が失敗する可能性があります。
ノード C の時計が前にジャンプし、その上で保持しているロックが急速に期限切れになります。
クライアント 2 が Redis ノード C、D、E から同じリソースのロックを正常に取得しました（多数のノード）。
クライアント 1 とクライアント 2 は現在、両方ともロックを保持していると考えています。

この例から、ロックの期限切れ無効化メカニズムが時間に強く依存している場合、システムの時計が不正確になると、アルゴリズムの安全性が保証されなくなることがわかります。しかし、ZooKeeper に基づく分散型ロックは時間に依存せず、各ノードのセッションに依存します。

長時間のネットワーク遅延#

分散システムでは、ネットワークの問題は避けられません。長時間のネットワーク遅延は、上記の 2 つの問題に類似した状況を引き起こす可能性があります。ノード A がロックを取得したが、ネットワーク遅延が超過してタイムアウトになり、ノード B がロックを取得しようとリクエストします。復帰後、ノード A はロックが期限切れになったことを知らず、A と B の衝突問題が発生します。