「分散ロック」の問題はこれまで多くの議論がなされてきましたが、著者は満足のいく答えを見つけられなかったため、その答えを見つけるまでの過程を記録し、まとめています。分散ロックの設計には、分散システムに関連する多くの問題が含まれており、多くの側面が熟考する価値があり、非常に興味深いものです。 要約長すぎて読めませんか?問題ありません。すでにマインドマップを作成しました。クリックして共有し、保存してサポートを示してください。今後の参照に便利です。 分散ロックの3つの特性と2つのカテゴリマルチスレッド プログラミングでは通常、同期にミューテックスまたはセマフォが使用されます。同じオペレーティング システム上の複数のプロセスも、共有メモリやその他の方法を通じて同期できます。しかし、分散システムでは、急ぎの購入注文など、複数のプロセス間でのリソースの競合には追加の分散ロックが必要になります。 ほとんどの分散ロックはアドバイザリ ロックです。つまり、データにアクセスする前にまずロック情報が取得され、その情報に基づいてアクセスが決定されます。対照的に、強制ロックでは、ロックされたデータへの不正アクセスがあった場合に例外が生成されます。 分散ロックは分散相互排他問題に属します。実際、ランポートは、彼の古典的な論文「分散システムにおける時間、クロック、およびイベントの順序付け」の中で、状態マシンの使用によってマルチプロセスの相互排他問題を分散的に解決できること、そしてコンセンサス アルゴリズムによってそのような状態マシンを実装できることをすでに証明しています。しかし、ほとんどの場合、コンセンサス ライブラリを構築する代わりに、分散ロックを使用します。主な理由は次のとおりです。
したがって、クライアントにコンセンサス ライブラリを実装する場合と比較して、分散ロック サービスを使用する方が緩やかで使いやすく、リソース効率も高くなります。 分散ロックというと、さまざまな実装方法や、Redis ベースの分散ロックが安全かどうかという議論がすぐに思い浮かぶかもしれません。これらの記事はおそらく多くの場所で見つけられるでしょう。しかし、これらのことを議論する前に、まず分散ロックに必要な特性について考えなければなりません。 一般に、分散ロック サービスには 3 つの重要なプロパティがあります。
フォールト トレランスはパフォーマンスを犠牲にして得られることに留意してください。フォールト トレランスはシステムのレベルによって異なります。システムが分散ロックのエラーに耐えられる場合は、単一ノードまたは単純なマスタースレーブレプリケーションで十分な場合があります。金融システムや航空宇宙システムなど、システムが非常に厳密な場合は、あらゆるコーナーケースを考慮する必要があります。この記事では、後者について主に説明します。 これら 3 つの特性を使用して、さまざまな分散ロックの実装を 1 つずつ分析します。その前に、分散ロックをスピン ロックと監視ロックの 2 つのカテゴリに分類します。
したがって、この記事では、読者が Redis、ZooKeeper、etcd が何であるかを大まかに理解していることを前提としています。 これで、頭の中に適切な枠組みができたので、マインドマップに知識を詰め込む作業を始めることができます。 データベースベースの実装最も簡単な方法は、別のデータベース (またはファイル) を使用し、データが取得されたときにそのデータベースにデータを挿入することです。後続のプロセスがデータを取得したい場合、まずデータベースにレコードがあるかどうかを確認し、別のプロセスがロックを保持しているかどうかを知ることで、分散ロックの相互排他性を実現します。 データベースはマスターとスレーブの同期レプリケーションを通じてフォールト トレランスを実現できますが、マスターとスレーブのレプリケーション間の切り替えは簡単ではなく、管理者の介入が必要になる場合があります。 デッドロックを回避するには、タイムスタンプ フィールドと自動増分 ID フィールドを追加し、期限切れのロックを定期的に解放してクリーンアップするスレッドをバックグラウンドで開始する必要があります。
データベースベースの実装はより面倒であり、ロックの TTL を自分で管理する必要があることがわかります。分散データベースを使用しない限り、マスタースレーブレプリケーションのフェイルオーバーは容易ではありません。 トラブルに加えて、データベースを頻繁に使用する場合は、同時実行性が高いとデータベースの読み取りと書き込みが非常に遅くなり、システム パフォーマンスのボトルネックが発生することもご存知でしょう。フォールト トレランスのために複数の独立したデータベースを使用すると、パフォーマンスはさらに低下します。 そのため、分散ロックのパフォーマンスを向上させるために、Redis や memcache などのメモリ ストレージ システムを使用して分散ロックを実装するようになりました。 Redisベースの実装最も一般的な分散ロックの実装は、おそらく Redis に基づいています。まず、単一ノードの Redis から始めます。 単一ノードRedisに基づく分散ロック通常、キーの書き込みと有効期限の設定には 1 つのコマンドが使用されます。そうしないと、アトミック性が保証されず、デッドロックが発生する可能性があります。したがって、次のコマンドがあります。 キー値をnxpx 10000に設定 set コマンドの後の 5 つのパラメータは次のとおりです。
この方式は、相互排除とデッドロック回避の点で優れたパフォーマンスを発揮し、非常に軽量です。しかし、単一ノードの Redis には単一障害点があります。 Redis のマスター スレーブ レプリケーションは非同期であるため、スレーブ ノードを追加すると相互排他違反のリスクが高まることに注意してください。フォールト トレランスを実現するために、マルチノード Redis に基づく分散ロック、つまり Redlock があります。 マルチノードRedisに基づく分散ロックRedlock は複数の独立した Redis ノードを使用します。つまり、複数の Redis ノードが実際にロックを取得するという考え方です。いずれかのノードがダウンした場合でも、半数以上のノードが利用可能であれば、ロック サービスを引き続き提供できます。 図に示すように、Redlock がロックを取得するための一般的な手順は次のとおりです。
ロック解除操作は、すべてのインスタンスに削除キー コマンドを送信することです。 Redlock のフォールト トレランスはタイムスタンプの計算に依存しますが、これは分散システムでは一般的ではないため、有名な議論がありました。 レッドロック論争DDIA の作者 Martin Kleppmann は、「分散ロックの実行方法」という有名な記事を公開し、Redlock は信頼できないと述べています。この記事は主に次の 2 つの点を説明しています。
最初のポイントは下の図に示されています。クライアント 1 がロックを取得した後、STW GC (またはページ欠落など) が発生します。 TTL が期限切れになると、クライアント 2 がロックを取得します。この時点で、2 つのクライアントがロックを保持しており、相互排他ルールに違反しています。当然、その後の書き込み操作では問題が発生する可能性があります。 デッドロックを回避しようとしていたとき、各ロックを識別するために単調に増加する ID (Martin はこれをフェンシング トークンと呼び、シリアル番号とも呼ばれる) を使用する必要があると述べました。 ID を追加した後のロジックは、下の図のようになります。トークンが古いため、クライアント 1 からの最終書き込み要求はストレージ システムによって拒否されます。 第二に、マーティンは、Redlock のタイムスタンプ計算方法は信頼できないと考えています。各サーバーの時刻管理は絶対的に正確ではありません。たとえば、NTP が同期されると、システムでクロック ドリフトが発生します。つまり、現在のサーバーのタイムスタンプが突然大きくなったり小さくなったりするため、Redlock の計算に影響します。 マーティンの記事は分散ロックに関する幅広い議論を巻き起こした。 Redis の作者 antirez も負けじと、「Redlock は安全か?」というタイトルの記事を公開しました。上記の2つの疑問に反論します。私はantirezの主張を要約しました:
この問題を議論している 2 つの記事をぜひ読んでいただきたいのですが、スペースの制限があるため、ここでは視点のみを抜粋しました。議論の詳細については、張鉄雷教授の論文「Redis に基づく分散ロックは安全か(第 2 部)」をご覧ください。比較的充実した中国語のレビューもあります。 これら2つの質問に対する私の理解についてお話ししたいと思います。 最初の質問に関しては、記事の冒頭で「3つの主要なプロパティ」を分析しました。デッドロックを回避するために TTL を追加すると、相互排他性に影響します。この問題は、Redis ベースか Zookeeper ベースかに関係なく発生します。 antirez の視点では、Redlock は値を一意の識別子として使用して操作をブロックすることもできるとのことですが、これは確かに問題なく、欠点は見つかりません。しかし、考えてみましょう。実際のプログラミングでは、自動インクリメント ID を使用するか、読み取り、変更、書き込み操作を使用する方が簡単だと思いますか? (実際、最初は読み取り、変更、書き込み操作が何なのかよく理解していませんでした。) フェンシングトークンの方が良い解決策だと思います。単調に増加する ID は私たちの直感に合っており、デバッグも簡単です。 フェンシング トークンの実用的なリファレンスとして、Hazelcast の記事「分散ロックは死んだ; 分散ロック万歳!」を参照してください。 Jepsen テストに合格する FencedLock ソリューションを提供します。 2 番目の質問は、クロックのドリフトに注意を払う必要があるかどうかです。 Antirez の見解では、クロックは Redlock に影響を与えるが、適切な運用とメンテナンスによって回避できるとのことです。 Julia Evans (有名な技術ブロガーでもある) も、クロック ドリフトの問題が本当に注目に値するかどうかについて議論するフォローアップ記事「TIL: クロック スキューが存在する」を執筆しました。最終的な結論は、制限されたクロックドリフトは安全な仮定ではないということです。 実際、クロックの問題は珍しいことではありません。たとえば、次のようになります。
うるう秒も時計のずれを引き起こす可能性がありますが、うるう秒が発生することは実際には非常にまれです (現在でも、うるう秒は依然として多くの問題を引き起こしますが、これについては後で説明します)。 上記の例から、クロックの問題は現実のものであることがわかります。システムに分散ロックのセキュリティに関する厳しい要件があり、システムおよび財務上の損失を発生させたくない場合は、すべてのエッジ ケースを考慮する必要があります。 Martin Kleppmann氏はHacker Newsのコメントに一切反応しなかった。彼は言いたいことはすべて言ったと感じ、討論に参加する気がなかった。彼は、分散システムを実際にどのように実行すべきかは、システムをどのように管理するかによって決まると信じていました。 この記事でも同じ観点を述べたいと思います。ソフトウェア エンジニアリングには特効薬はなく、これらのトレードオフはシステムの重要度レベルと分散システムの管理方法によって異なります。 分散システムの研究者は、通常、コンピュータ上で発生する可能性が非常に低いと思われる事象 (クロック スキューなど) について非常に懸念しています。その理由は次のとおりです。 この問題を解決するアルゴリズムを見つける必要があるため、すべてのコーナーケースを考慮する必要があります。 数万台のマシンを備えた分散システムでは、起こりそうにないイベントが発生する可能性が非常に高くなります。 これらの問題のいくつかは実際には非常に一般的です (例: ネットワーク パーティション)。 ZooKeeper に基づく実装Redlock に加えて、障害を許容し、デッドロックを回避できる他の方法はありますか? もちろん、フォールト トレランスは、私たちの古くからの友人であるコンセンサス アルゴリズムと切り離すことはできません。クライアントが複数のロックを順番にロックすることはなくなり、ロック サーバーがコンセンサス アルゴリズムを通じて多数派ノードに複製し、クライアントに応答するようになります。コンセンサス アルゴリズム自体はシステム タイムスタンプではなく論理クロック (Raft の項または Paxos のエポック) に依存するため、クロックのドリフトの問題はありません。 第二に、デッドロックを回避するには、依然として TTL と自己増分 ID が必要です。ロック サービスを使用して、各ロック要求に単調に増加する ID をマークします。 上記の 2 つの方法により、より信頼性の高い分散ロックを実現できます。コストは、コンセンサス アルゴリズムを実装するサードパーティ コンポーネントが必要になることです。以下では、主に ZooKeeper、etcd、Chubby の 3 つの実装を紹介します。 ZooKeeper は分散調整サービスです。「ZooKeeper の設計原則」を参照してください。 ZooKeeper に基づく分散ロックは、次の 2 つのノード プロパティに依存します。
ZooKeeper の公式ドキュメントには、すぐに使える分散ロックの実装方法が提供されています。
上の図に示すように、各クライアントは自分よりも小さい znode のみをリッスンするため、Thundering Herd 効果を回避できます。 ロックを取得するための疑似コードは次のとおりです。
ロックの解除は非常に簡単です。クライアントは、ステップ 1 で作成した znode を削除するだけです。 注意すべき点がいくつかあります:
もちろん、ZooKeeper の実装はより信頼性が高いように見えますが、ロックの実装方法によっては、ロック ロジックのデバッグ、ロックの競合、その他の問題が依然として多く発生する可能性があります。 ZooKeeper ベースの分散ロックのパフォーマンスは、MySQL ベースと Redis ベースの実装の中間であり、単一ノードの Redis ほど優れているわけではありません。 ZooKeeper のもう 1 つの欠点は、別の ZooKeeper サービスを維持する必要があることです (既に存在する場合は無視してください)。 などEtcd は、Kubernetes での使用で有名な、よく知られた分散キー値ストレージ構造です。 etcd は分散ロックの実装にも使用できます。公式では、開発者が分散ロックを迅速に実装できるように、clientv3 パッケージも配慮して提供しています。 etcd が分散ロックの「3 つの大きな問題」をどのように解決するかを見てみましょう。
開発者が分散ロックを迅速に実装できるように、etcd は clientv3 パッケージを提供しており、分散ロックは concurrency パッケージに含まれています。公式ドキュメントに記載されている例 1 によると、最初に新しいセッションを作成し、リースの TTL を指定してから、NewMutex() をインスタンス化し、Lock() と Unlock() を呼び出してロックを取得および解放します。コードは次のとおりです。
Lock() 関数のソース コードは簡単に見つけられるので、スペースの制約によりここでは含めませんが、ソース コードで確認できるその他のメカニズムには次のものがあります。
本質的には、etcd と ZooKeeper は分散ロックの実装が似ています。 etcd を選択する理由としては、次のようなものが考えられます。
ぽっちゃり最後に、Chubbyについて簡単にお話しましょう。 Chubby はオープンソースではないため、直接使用することはできず、詳細を知ることは困難です。 Chubby を構築する需要はほとんどありません (ただし、私の以前の雇用主は実際に C++ を使用して Chubby を構築しました)。したがって、Chubby 部分は論文のレビューに過ぎず、興味のない読者は読み飛ばしてかまいません。 Chubby は、Google が開発した疎結合の分散ロック サービスです。さらに、GFS と BigTable は、一部のメタデータを保存するために Chubby を使用します。 Chubby の主な機能は次のとおりです。
Chubby はフォールト トレランスを実現するために Paxos コンセンサス アルゴリズムに依存しています。データは UNIX ファイル システム方式 (ノードと呼ばれる) で整理されます。切断後に削除される一時的なノードも存在します。特定のノードのリッスンをサポートします。つまり、ZooKeeper では Chubby の影がたくさん見られます。 ZooKeeper と Chubby が解決する問題は比較的似ています。そのため、多くの人は ZooKeeper が Chubby のオープンソース実装であると考えていますが、両者の具体的なアーキテクチャは少し異なります。
フォールト トレランスのため、Chubby クラスターは 5 つのノードで構成され、Chubby セルを形成します。これら 5 つのノードのうち、マスターは 1 つだけで、残りはレプリカです。マスターのみがリクエストを処理し、ファイルを読み書きできます。他のレプリカ ノードは、フォールト トレランスのために Paxos アルゴリズムを通じてマスターの動作を複製します。 Chubby は以下もサポートしています:
さらに興味深いのは、チャビーの失敗からの回復です。マスターに障害が発生すると、そのメモリ内のセッションとロックの情報だけでなく、セッション内の最も重要なリース情報も失われます。 Paxos アルゴリズムは新しいマスターを選出し、次の処理を実行します。 新しいエポックを選択することは、Raft の用語として理解できます。エポック未満のクライアント要求は拒否され、マスターが古いマスターからの要求に応答しないことが保証されます。 データベース (永続ストレージ) のデータに基づいてセッションおよびロック関連情報を復元し、セッション リースを可能な限り最大期間まで延長します。 KeepAlive リクエストのみが受け入れられます。下の図のステップ 4 の最初の KeepAlive 要求はエポック エラーのため Maser によって拒否されますが、クライアントも最新のエポックを取得します。ステップ 6 の 2 番目の KeepAlive は成功し、前のステップで延長されたリースは十分に長いため、ステップ 7 の応答によってクライアントのローカル リース時間が延長されます。その後、通常の通信が再開されます。 古いマスターによって作成されたハンドルが新しいリクエストで見つかった場合、新しいマスターも再構築する必要があります。一定期間(通常は 1 分)が経過すると、ハンドルのない一時ノードは削除されます。 全体のプロセスは図に示されています。緑色の部分が安全期間、オレンジ色の部分が危険期間です。 Chubby クラスターは新しいマスターに切り替わります。 チャビーについてあまり深く考えたくない。もう一つのチャビーを作ろうという動機はないと思う。 結論この記事を書いているとき、私はとても緊張しました。自分の自尊心を守るため、また他人に叱られるのを避けるために、私は間違いをしないように努めました。しかし、間違いは避けられず、時間が経つにつれて、いくつかの解決策は 2、3 年後には適用できなくなる可能性があります。この記事を書くのには本当に多くの時間と労力がかかりました。 分散ロックの問題をさらに深く探求したい学生には、Lamport の「分散システムにおける時間、クロック、およびイベントの順序」を読むことをお勧めします。もちろん、私の新しい本にもこの論文の分析が含まれており、今年後半に出版される予定です。 最後に、本記事に不適切な点がありましたら、ご指摘いただければ積極的に修正させていただきます。 参照1. ランポート、レスリー。 「分散システムにおける時間、時計、イベントの順序」並行性: レスリー・ランポートの著作。 2019年179-196頁。 2. 分散ロックの実施方法、https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html 3. Redlock は安全ですか? http://antirez.com/news/101 4. 分散ロックは死んだ。分散ロック万歳! https://hazelcast.com/blog/long-live-distributed-locks/ 5. TIL: クロック スキューが存在する、http://jvns.ca/blog/2016/02/09/til-clock-skew-exists/ 6. NTP ネットワークの調査、http://alumni.media.mit.edu/~nelson/research/ntp-survey99/ 7. タイムスタンプのトラブル、https://aphyr.com/posts/299-the-trouble-with-timestamps 8. コルベット、ジェームズC.、他「Spanner: Google のグローバル分散データベース」 ACM Transactions on Computer Systems (TOCS) 31.3 (2013): 1-22. 9. ハント、パトリック、他「ZooKeeper: インターネット規模のシステムのための待機なしの調整」 USENIX 年次技術会議。巻8. 第9号. 2010年. 10. 分散ロックに関する ZooKeeper 公式ドキュメント、https://zookeeper.apache.org/doc/r3.7.0/recipes.html#sc_recipes_Locks 11. 分散ロック実装のetcd公式例、https://github.com/etcd-io/etcd/blob/main/tests/integration/clientv3/concurrency/mutex_test.go 12. バロウズ、マイク。 「疎結合分散システム向けの Chubby ロック サービス」第 7 回オペレーティング システムの設計と実装に関するシンポジウムの議事録。 2006年。 |
<<: Longhorn、エンタープライズレベルのクラウドネイティブコンテナ分散ストレージ - 高可用性
>>: クラウドネイティブの初体験: K8s への Springboot アプリケーションのデプロイ
SEO 業界は標準化されていません。SEO エンジニアの中には、高額の給与を稼ぎ、大規模な Web ...
ハイブリッド クラウドは、今日のテクノロジー環境において大きな差別化要因へと進化しました。クラウド ...
人気スローガントップ10では、「元福道(全国で計4億人のユーザーが元福道を選んでおり、オンラインコー...
外部リンクを構築する際には、品質と長期性を追求します。これらの要件を見ると、最初の反応はおそらく B...
Xiaomao は、ウェブマスター仲間は皆、外部リンクがウェブサイトのランキングに与える重要性を認識...
Hewlett Packard Enterprise の子会社である Aruba は本日、業界初の ...
利用者数、訪問数、資金調達などでリードするソーシャル電子商取引が頻繁に話題となると、インターネット大...
Baidu Index に関しては、どのウェブマスターにとってももはや馴染みのない話ではないと思いま...
WeChatは2011年に開始されて以来、1年半以上でユーザーベースが2億人に達しました。 WeCh...
Tencent Cloudは、中国の3大クラウドベンダーの1つとして、多くの人に知られています。私た...
一年間の努力を経て、年末の総括から私たちは何を得たのでしょうか?また一年が過ぎ、今年はインターネット...
Web ページのクロールの優先順位戦略は、「ページ選択問題」とも呼ばれます。通常、重要な Web ペ...
rawvps は主に、OpenVZ と KVM という 2 つの基盤となる仮想化方式に基づく VPS...
[51CTO.com からのオリジナル記事]企業がビジネスを革新し、効率性を向上させたい場合、データ...
ウェブサイトのキーワードランキングについて言えば、正直言って、SEOにとっては本当に頭痛の種です。キ...