分散ロックに関する10,000語の記事

[[419431]]

「分散ロック」の問題はこれまで多くの議論がなされてきましたが、著者は満足のいく答えを見つけられなかったため、その答えを見つけるまでの過程を記録し、まとめています。分散ロックの設計には、分散システムに関連する多くの問題が含まれており、多くの側面が熟考する価値があり、非常に興味深いものです。

要約

長すぎて読めませんか?問題ありません。すでにマインドマップを作成しました。クリックして共有し、保存してサポートを示してください。今後の参照に便利です。

分散ロックの3つの特性と2つのカテゴリ

マルチスレッド プログラミングでは通常、同期にミューテックスまたはセマフォが使用されます。同じオペレーティング システム上の複数のプロセスも、共有メモリやその他の方法を通じて同期できます。しかし、分散システムでは、急ぎの購入注文など、複数のプロセス間でのリソースの競合には追加の分散ロックが必要になります。

ほとんどの分散ロックはアドバイザリ ロックです。つまり、データにアクセスする前にまずロック情報が取得され、その情報に基づいてアクセスが決定されます。対照的に、強制ロックでは、ロックされたデータへの不正アクセスがあった場合に例外が生成されます。

分散ロックは分散相互排他問題に属します。実際、ランポートは、彼の古典的な論文「分散システムにおける時間、クロック、およびイベントの順序付け」の中で、状態マシンの使用によってマルチプロセスの相互排他問題を分散的に解決できること、そしてコンセンサス アルゴリズムによってそのような状態マシンを実装できることをすでに証明しています。しかし、ほとんどの場合、コンセンサス ライブラリを構築する代わりに、分散ロックを使用します。主な理由は次のとおりです。

1. 多くの（ビジネス）システムはコンセンサス アルゴリズムを使用するように変換するのが難しく、ロック サービスは既存のプログラム構造と通信パターンを維持する可能性が高くなります。
2. ロックベースのインターフェースはプログラマーにとってより馴染み深いものです。表面的にしか馴染みがないかもしれませんが、コンセンサス ライブラリを使用するよりも確かに優れています。
3. ロック サービスを使用すると、クライアント システムで実行されるサーバーの数を減らすことができます。コンセンサス アルゴリズムでは、決定を下すためにクォーラム (定足数) が必要であり、これは半数以上のノードが利用可能であることを意味します。各クライアントのクォーラムを構築するには多数のサーバーが必要ですが、分散ロック サービスは複数のクライアントに安全にサービスを提供できます。

したがって、クライアントにコンセンサス ライブラリを実装する場合と比較して、分散ロック サービスを使用する方が緩やかで使いやすく、リソース効率も高くなります。

分散ロックというと、さまざまな実装方法や、Redis ベースの分散ロックが安全かどうかという議論がすぐに思い浮かぶかもしれません。これらの記事はおそらく多くの場所で見つけられるでしょう。しかし、これらのことを議論する前に、まず分散ロックに必要な特性について考えなければなりません。

一般に、分散ロック サービスには 3 つの重要なプロパティがあります。

• 相互排除: これはロックの最も基本的な機能です。同時にロックを保持できるのは 1 つのクライアントのみです。
• デッドロックを回避します（デッドロックフリー）。クライアントがロックを取得してから処理に時間がかかりすぎたり、クライアントに障害が発生したりした場合は、ロックを解除できず、処理フロー全体を続行できなくなるため、デッドロックを回避する必要があります。デッドロックを回避する最も一般的な方法は、TTL (Time To Live) を設定することです。 TTL が 3 秒に設定されていると仮定します。 3 秒経ってもロックが解除されない場合、システムは自動的にロックを解除します (TTL を設定するときは十分に注意してください。期間はビジネス ロジックによって異なります)。しかし、問題もあります。プロセス 1 がロックを取得した後、何らかの理由 (以下で説明) で TTL を更新する時間がない場合、 3 秒後、プロセス 2 がロックを取得します。 TTL が期限切れになったため、プロセス 2 はロックを取得して処理を開始できます。この時点で、2 つのクライアントが同時にロックを保持しているため、予期しない動作が発生する可能性があります。したがって、TTL だけではなく、ロックを識別するために一意の ID (またはフェンシング トークン) をロックに添付する必要もあります。上記のロジックでは、プロセス 1 がロックを取得すると、LOCK_1 として記録されます。 TTL後、プロセス2によって取得されたロックはLOCK_2として記録されます。その後、アプリケーション レベルで ID をチェックしたり、サービス レベルでロックして古いリクエストをブロックしたりできます。
• フォールト トレランス: 単一点障害を回避するには、ロック サービスに一定のフォールト トレランスが必要です。一般的に、フォールト トレラント方式は 2 つあります。 1 つは、ロック サービス自体が自動的にフェイルオーバーできるクラスターであることです (ZooKeeper、etcd)。もう 1 つは、クライアントが複数の独立したロック サービスに要求を開始することです。ロック サービスの 1 つに障害が発生した場合でも、他のロック サービス (Redlock) からロック情報を読み取ることができます。コストは、クライアントが複数のロックを取得する必要があり、各マシンのクロックが同じでなければならないことです。そうしないと、TTL が不整合になり、一部のマシンはロックを早く解放し、他のマシンはロックを遅く解放することになり、問題が発生する可能性があります。

フォールト トレランスはパフォーマンスを犠牲にして得られることに留意してください。フォールト トレランスはシステムのレベルによって異なります。システムが分散ロックのエラーに耐えられる場合は、単一ノードまたは単純なマスタースレーブレプリケーションで十分な場合があります。金融システムや航空宇宙システムなど、システムが非常に厳密な場合は、あらゆるコーナーケースを考慮する必要があります。この記事では、後者について主に説明します。

これら 3 つの特性を使用して、さまざまな分散ロックの実装を 1 つずつ分析します。その前に、分散ロックをスピン ロックと監視ロックの 2 つのカテゴリに分類します。

• スピン クラスには、データベース ベースの実装と Redis ベースの実装が含まれます。このタイプの実装では、クライアントはロックを取得できるかどうかを確認するためにロック サービスを繰り返し要求する必要があります。
• 監視カテゴリには、主に ZooKeeper または etcd に基づいて実装された分散ロックが含まれます。このタイプの実装では、クライアントは特定のキーを監視 (監視) するだけで済みます。ロックが利用可能になると、ロック サービスがクライアントに通知するため、クライアントはロック サービスを継続的に要求する必要がなくなります。

したがって、この記事では、読者が Redis、ZooKeeper、etcd が何であるかを大まかに理解していることを前提としています。

これで、頭の中に適切な枠組みができたので、マインドマップに知識を詰め込む作業を始めることができます。

データベースベースの実装

最も簡単な方法は、別のデータベース (またはファイル) を使用し、データが取得されたときにそのデータベースにデータを挿入することです。後続のプロセスがデータを取得したい場合、まずデータベースにレコードがあるかどうかを確認し、別のプロセスがロックを保持しているかどうかを知ることで、分散ロックの相互排他性を実現します。

データベースはマスターとスレーブの同期レプリケーションを通じてフォールト トレランスを実現できますが、マスターとスレーブのレプリケーション間の切り替えは簡単ではなく、管理者の介入が必要になる場合があります。

デッドロックを回避するには、タイムスタンプ フィールドと自動増分 ID フィールドを追加し、期限切れのロックを定期的に解放してクリーンアップするスレッドをバックグラウンドで開始する必要があります。

データベースベースの実装はより面倒であり、ロックの TTL を自分で管理する必要があることがわかります。分散データベースを使用しない限り、マスタースレーブレプリケーションのフェイルオーバーは容易ではありません。

トラブルに加えて、データベースを頻繁に使用する場合は、同時実行性が高いとデータベースの読み取りと書き込みが非常に遅くなり、システム パフォーマンスのボトルネックが発生することもご存知でしょう。フォールト トレランスのために複数の独立したデータベースを使用すると、パフォーマンスはさらに低下します。

そのため、分散ロックのパフォーマンスを向上させるために、Redis や memcache などのメモリ ストレージ システムを使用して分散ロックを実装するようになりました。

Redisベースの実装

最も一般的な分散ロックの実装は、おそらく Redis に基づいています。まず、単一ノードの Redis から始めます。

単一ノードRedisに基づく分散ロック

通常、キーの書き込みと有効期限の設定には 1 つのコマンドが使用されます。そうしないと、アトミック性が保証されず、デッドロックが発生する可能性があります。したがって、次のコマンドがあります。

キー値をnxpx 10000に設定

set コマンドの後の 5 つのパラメータは次のとおりです。

1. 最初のものはロック名としてのキーです。
2. 2 番目は値で、通常は乱数やクライアントの MAC アドレス + UUID などの一意の ID を渡します。
3. 3 番目は NX で、これは SET IF NOT EXIST を意味します。つまり、キーが存在しない場合にのみ設定操作が実行されます。キーがすでに存在する場合（ロックがすでに使用されている場合）、操作は実行されません。
4. 4 番目は PX で、このキーに有効期限を追加するために使用されます。具体的な時間の長さは 5 番目のパラメータによって決まります。
5. 5 番目は特定の有効期限で、4 番目のパラメータ PX はミリ秒、EX は秒に対応します。

この方式は、相互排除とデッドロック回避の点で優れたパフォーマンスを発揮し、非常に軽量です。しかし、単一ノードの Redis には単一障害点があります。 Redis のマスター スレーブ レプリケーションは非同期であるため、スレーブ ノードを追加すると相互排他違反のリスクが高まることに注意してください。フォールト トレランスを実現するために、マルチノード Redis に基づく分散ロック、つまり Redlock があります。

マルチノードRedisに基づく分散ロック

Redlock は複数の独立した Redis ノードを使用します。つまり、複数の Redis ノードが実際にロックを取得するという考え方です。いずれかのノードがダウンした場合でも、半数以上のノードが利用可能であれば、ロック サービスを引き続き提供できます。

図に示すように、Redlock がロックを取得するための一般的な手順は次のとおりです。

1. 複数の Redis インスタンス (通常は 3 または 5) を順番にロックし、単一の Redis インスタンスと同じロック コマンドを使用します。
2. 特定のノードがロックを取得できない時間が長くなることでブロックされるのを回避するために、各ロック取得操作にもタイムアウト期間が設定されており、これは TTL よりもはるかに短くなっています。タイムアウト期間を超えると失敗とみなされ、次のノードを使用してロックが取得されます。
3. 複数のロック取得にかかる合計時間を計算します。半数以上のノードがロックの取得に成功し、消費された合計時間が TTL 未満である場合にのみ、ロックは正常に取得されたとみなされます。
4. ロックを正常に取得した後、TTL = TTL - 合計経過時間を再計算します。
5. ロックの取得に失敗した場合、すべての Redis インスタンスにロック解除コマンドが送信されます。

ロック解除操作は、すべてのインスタンスに削除キー コマンドを送信することです。

Redlock のフォールト トレランスはタイムスタンプの計算に依存しますが、これは分散システムでは一般的ではないため、有名な議論がありました。

レッドロック論争

DDIA の作者 Martin Kleppmann は、「分散ロックの実行方法」という有名な記事を公開し、Redlock は信頼できないと述べています。この記事は主に次の 2 つの点を説明しています。

1. Redis コマンドはデッドロックを回避しますが、2 つのクライアントが同時にロックを取得するのをブロックする自己増分 ID またはフェンシング トークンがないため、相互排他性を満たさない可能性があります。
2. タイムスタンプに基づく Redlock の合理性には疑問があり、複数のサーバー間で時間の一貫性を確保することは困難です。

最初のポイントは下の図に示されています。クライアント 1 がロックを取得した後、STW GC (またはページ欠落など) が発生します。 TTL が期限切れになると、クライアント 2 がロックを取得します。この時点で、2 つのクライアントがロックを保持しており、相互排他ルールに違反しています。当然、その後の書き込み操作では問題が発生する可能性があります。

デッドロックを回避しようとしていたとき、各ロックを識別するために単調に増加する ID (Martin はこれをフェンシング トークンと呼び、シリアル番号とも呼ばれる) を使用する必要があると述べました。 ID を追加した後のロジックは、下の図のようになります。トークンが古いため、クライアント 1 からの最終書き込み要求はストレージ システムによって拒否されます。

第二に、マーティンは、Redlock のタイムスタンプ計算方法は信頼できないと考えています。各サーバーの時刻管理は絶対的に正確ではありません。たとえば、NTP が同期されると、システムでクロック ドリフトが発生します。つまり、現在のサーバーのタイムスタンプが突然大きくなったり小さくなったりするため、Redlock の計算に影響します。

マーティンの記事は分散ロックに関する幅広い議論を巻き起こした。 Redis の作者 antirez も負けじと、「Redlock は安全か?」というタイトルの記事を公開しました。上記の2つの疑問に反論します。私はantirezの主張を要約しました:

• 最初の点に関して、Redlock は自動インクリメント ID などのフィールドを提供していませんが、クライアントによって指定されたフィールド値も、読み取り、変更、書き込みのアトミック操作を通じて一意に識別およびチェックできます。
• クロックのドリフトは間違いなく Redlock のセキュリティに影響しますが、クロックを勝手に変更しない、大きな NTP クロック調整を複数の小さな調整に変換するなど、適切な操作とメンテナンスを行うことで、クロックの変更は一定の範囲を超えず、Redlock に影響しません。

この問題を議論している 2 つの記事をぜひ読んでいただきたいのですが、スペースの制限があるため、ここでは視点のみを抜粋しました。議論の詳細については、張鉄雷教授の論文「Redis に基づく分散ロックは安全か（第 2 部）」をご覧ください。比較的充実した中国語のレビューもあります。

これら2つの質問に対する私の理解についてお話ししたいと思います。

最初の質問に関しては、記事の冒頭で「3つの主要なプロパティ」を分析しました。デッドロックを回避するために TTL を追加すると、相互排他性に影響します。この問題は、Redis ベースか Zookeeper ベースかに関係なく発生します。 antirez の視点では、Redlock は値を一意の識別子として使用して操作をブロックすることもできるとのことですが、これは確かに問題なく、欠点は見つかりません。しかし、考えてみましょう。実際のプログラミングでは、自動インクリメント ID を使用するか、読み取り、変更、書き込み操作を使用する方が簡単だと思いますか? (実際、最初は読み取り、変更、書き込み操作が何なのかよく理解していませんでした。)

フェンシングトークンの方が良い解決策だと思います。単調に増加する ID は私たちの直感に合っており、デバッグも簡単です。

フェンシング トークンの実用的なリファレンスとして、Hazelcast の記事「分散ロックは死んだ; 分散ロック万歳!」を参照してください。 Jepsen テストに合格する FencedLock ソリューションを提供します。

2 番目の質問は、クロックのドリフトに注意を払う必要があるかどうかです。 Antirez の見解では、クロックは Redlock に影響を与えるが、適切な運用とメンテナンスによって回避できるとのことです。

Julia Evans (有名な技術ブロガーでもある) も、クロック ドリフトの問題が本当に注目に値するかどうかについて議論するフォローアップ記事「TIL: クロック スキューが存在する」を執筆しました。最終的な結論は、制限されたクロックドリフトは安全な仮定ではないということです。

実際、クロックの問題は珍しいことではありません。たとえば、次のようになります。

• ネルソン・ミナールは 1999 年に、NTP サーバーが不正確な時刻を提供することが多いことを発見した論文を発表しました。
• Aphyr の記事「タイムスタンプのトラブル」でも、分散システムにおけるタイムスタンプのトラブルがまとめられています。
• Google は時間の問題に対処するために Spanner に多大な労力を費やし、TrueTime タイミング システムを発明しました。

うるう秒も時計のずれを引き起こす可能性がありますが、うるう秒が発生することは実際には非常にまれです (現在でも、うるう秒は依然として多くの問題を引き起こしますが、これについては後で説明します)。

上記の例から、クロックの問題は現実のものであることがわかります。システムに分散ロックのセキュリティに関する厳しい要件があり、システムおよび財務上の損失を発生させたくない場合は、すべてのエッジ ケースを考慮する必要があります。

Martin Kleppmann氏はHacker Newsのコメントに一切反応しなかった。彼は言い​​たいことはすべて言ったと感じ、討論に参加する気がなかった。彼は、分散システムを実際にどのように実行すべきかは、システムをどのように管理するかによって決まると信じていました。

この記事でも同じ観点を述べたいと思います。ソフトウェア エンジニアリングには特効薬はなく、これらのトレードオフはシステムの重要度レベルと分散システムの管理方法によって異なります。

分散システムの研究者は、通常、コンピュータ上で発生する可能性が非常に低いと思われる事象 (クロック スキューなど) について非常に懸念しています。その理由は次のとおりです。

この問題を解決するアルゴリズムを見つける必要があるため、すべてのコーナーケースを考慮する必要があります。

数万台のマシンを備えた分散システムでは、起こりそうにないイベントが発生する可能性が非常に高くなります。

これらの問題のいくつかは実際には非常に一般的です (例: ネットワーク パーティション)。

ZooKeeper に基づく実装

Redlock に加えて、障害を許容し、デッドロックを回避できる他の方法はありますか?

もちろん、フォールト トレランスは、私たちの古くからの友人であるコンセンサス アルゴリズムと切り離すことはできません。クライアントが複数のロックを順番にロックすることはなくなり、ロック サーバーがコンセンサス アルゴリズムを通じて多数派ノードに複製し、クライアントに応答するようになります。コンセンサス アルゴリズム自体はシステム タイムスタンプではなく論理クロック (Raft の項または Paxos のエポック) に依存するため、クロックのドリフトの問題はありません。

第二に、デッドロックを回避するには、依然として TTL と自己増分 ID が必要です。ロック サービスを使用して、各ロック要求に単調に増加する ID をマークします。

上記の 2 つの方法により、より信頼性の高い分散ロックを実現できます。コストは、コンセンサス アルゴリズムを実装するサードパーティ コンポーネントが必要になることです。以下では、主に ZooKeeper、etcd、Chubby の 3 つの実装を紹介します。

ZooKeeper は分散調整サービスです。「ZooKeeper の設計原則」を参照してください。

ZooKeeper に基づく分散ロックは、次の 2 つのノード プロパティに依存します。

• シーケンス: シーケンシャル ノード。ZooKeeper は、クライアントによって設定された znode パスに 0 パディングを含む 10 ビットのシーケンス番号を追加します。たとえば、locknode/guid-lock- は locknode/guid-lock-0000000001 を返します。
• 一時的: 一時的なノード。クライアントが ZooKeeper から切断されると、デッドロックを回避するために一時ノードが削除されます。ただし、この切断検出には一定のハートビート遅延があるため、相互排他性が破壊されるのを避けるために ID を自己増分する必要があります。

ZooKeeper の公式ドキュメントには、すぐに使える分散ロックの実装方法が提供されています。

1. まず、locknode/guid-lock- などのロック パスを使用して create() を呼び出し、シーケンスとエフェメラル フラグを設定します。 guid はクライアントの一意の識別子です。 create() が失敗した場合は、以下で説明する guid を通じて確認できます。
2. getChildren() を呼び出して子ノードのリストを取得し、ウォッチ フラグを設定しないでください (Herd Effect を回避するために非常に重要です)。
3. 2. の子ノードリストを確認します。ステップ 1. の作成が成功し、返されたシリアル番号サフィックスが最小の場合、クライアントは分散ロックを保持し、ここで終了します。
4. シーケンスが最小でない場合は、子ノードリストから現在のシーケンス番号よりも小さいシーケンス番号を持つノードを選択し、それを p として記録します。クライアントは、p を監視することを意味する、exist(p, watch=true) を呼び出します。 p が削除されると、通知されます (ノードは、自分よりも小さいシーケンス番号を持つノードが解放された場合にのみロックを取得できます)。
5. existing() が null を返す場合、つまり以前の分散ロックが解放されている場合は、手順 2 に進みます。それ以外の場合は、ステップ 4 のウォッチの通知を待つ必要があります。

上の図に示すように、各クライアントは自分よりも小さい znode のみをリッスンするため、Thundering Herd 効果を回避できます。

ロックを取得するための疑似コードは次のとおりです。

 n =作成(l + “/guid-lock-”, EPHEMERAL|SEQUENTIAL)
 C = getChildren(l, false )
 nがCの最低のznodeの場合、終了する
p = Cのznode はn の直前に順序付けられる
2へ進む

ロックの解除は非常に簡単です。クライアントは、ステップ 1 で作成した znode を削除するだけです。

注意すべき点がいくつかあります:

• 各ノードは 1 つのクライアントによって監視されるため、znode を削除しても 1 つのクライアントのみが起動されます。このようにして、雷鳴のような群集効果を回避することができます。
• ポーリングやタイムアウトはありません。
• ZooKeeper がロックを正常に作成したが、create() の呼び出し時にクライアントにロックを返さずに失敗した場合、クライアントはエラー応答を受け取った後にこの問題を回避するために getChildren() を呼び出してパスに GUID が含まれているかどうかを確認する必要があります。

もちろん、ZooKeeper の実装はより信頼性が高いように見えますが、ロックの実装方法によっては、ロック ロジックのデバッグ、ロックの競合、その他の問題が依然として多く発生する可能性があります。

ZooKeeper ベースの分散ロックのパフォーマンスは、MySQL ベースと Redis ベースの実装の中間であり、単一ノードの Redis ほど優れているわけではありません。

ZooKeeper のもう 1 つの欠点は、別の ZooKeeper サービスを維持する必要があることです (既に存在する場合は無視してください)。

など

Etcd は、Kubernetes での使用で有名な、よく知られた分散キー値ストレージ構造です。 etcd は分散ロックの実装にも使用できます。公式では、開発者が分散ロックを迅速に実装できるように、clientv3 パッケージも配慮して提供しています。

etcd が分散ロックの「3 つの大きな問題」をどのように解決するかを見てみましょう。

• 排他制御: etcd はトランザクションをサポートします。キーを作成し、トランザクションを通じてキーが存在するかどうかを確認することで、相互排除を保証できます。
• フォールト トレランス: etcd は Raft コンセンサス アルゴリズムに基づいています。キーの書き込みが成功するには、少なくとも半数のノードからの確認が必要であり、これによりフォールト トレランスが保証されます。
• デッドロック: etcd はリース メカニズムをサポートしており、キーのリースのタイムアウト (TTL) を設定できます。有効期限が切れると、デッドロックを回避するためにキーは無効になり、削除されます。 etcd はリースの更新もサポートしており、クライアントがまだプロセスを完了していない場合にリースを更新できます。同時に、etcd には自動インクリメント ID もあります。これについては後述します。

開発者が分散ロックを迅速に実装できるように、etcd は clientv3 パッケージを提供しており、分散ロックは concurrency パッケージに含まれています。公式ドキュメントに記載されている例 1 によると、最初に新しいセッションを作成し、リースの TTL を指定してから、NewMutex() をインスタンス化し、Lock() と Unlock() を呼び出してロックを取得および解放します。コードは次のとおりです。

 cli、err := clientv3.New(clientv3.Config{エンドポイント: エンドポイント})
 err != nil の場合 {
   ログ.致命的(エラー)
 }
 CLI を延期します。近い（） 
 
 s、エラー:= concurrency.NewSession(cli、concurrency.WithTTL(10))
 err != nil の場合 {
   ログ.致命的(エラー)
 }
 s.Close ()を延期する
 
 m := concurrency.NewMutex(s, "/my-lock/" )
エラーの場合:= m.Lock(context.TODO());エラー != ゼロ {
   ログ.致命的(エラー)
 }
 fmt.Println( "s のロックを取得しました" ) 
 
エラーの場合:= m.Unlock(context.TODO());エラー != ゼロ {
   ログ.致命的(エラー)
 }
 fmt.Println( "s のロックが解放されました" )

Lock() 関数のソース コードは簡単に見つけられるので、スペースの制約によりここでは含めませんが、ソース コードで確認できるその他のメカニズムには次のものがあります。

• 改訂メカニズム。 ZooKeeper のシーケンス番号に似たグローバル シーケンス番号。監視集団のパニックを回避するために使用できます。
• プレフィックスメカニズム。つまり、上記のコードでは、etcd はプレフィックス /my-lock/ (/my-lock/ + LeaseID) を持つキーを作成し、このプレフィックスの下で最も小さいリビジョン (最も早く作成) を持つキーによって分散ロックが取得されます。
• 時計の機構。 ZooKeeper と同様に、クライアントは自身のキーよりも小さいキーのリビジョンをリッスンし、自身のキーよりも小さいキーがリリースされたときにロックを取得しようとします。

本質的には、etcd と ZooKeeper は分散ロックの実装が似ています。

etcd を選択する理由としては、次のようなものが考えられます。

• etcd クラスターは実稼働環境に大規模に導入されています。
• etcd は、Redis と ZooKeeper 間のパフォーマンスにより、強力な一貫性を確保しながら非常に高速です。
• 使いやすい etcd クライアント ライブラリが多くの言語で提供されています。

ぽっちゃり

最後に、Chubbyについて簡単にお話しましょう。 Chubby はオープンソースではないため、直接使用することはできず、詳細を知ることは困難です。 Chubby を構築する需要はほとんどありません (ただし、私の以前の雇用主は実際に C++ を使用して Chubby を構築しました)。したがって、Chubby 部分は論文のレビューに過ぎず、興味のない読者は読み飛ばしてかまいません。

Chubby は、Google が開発した疎結合の分散ロック サービスです。さらに、GFS と BigTable は、一部のメタデータを保存するために Chubby を使用します。 Chubby の主な機能は次のとおりです。

• 粒度が粗い。細粒度のロックと比較すると、粗粒度のロックは数時間または数日間持続する場合があります。
• 可用性、信頼性;
• 一部のメタデータを保存できます。
• 安価な機械の大量導入。

Chubby はフォールト トレランスを実現するために Paxos コンセンサス アルゴリズムに依存しています。データは UNIX ファイル システム方式 (ノードと呼ばれる) で整理されます。切断後に削除される一時的なノードも存在します。特定のノードのリッスンをサポートします。つまり、ZooKeeper では Chubby の影がたくさん見られます。 ZooKeeper と Chubby が解決する問題は比較的似ています。そのため、多くの人は ZooKeeper が Chubby のオープンソース実装であると考えていますが、両者の具体的なアーキテクチャは少し異なります。

[[419432]]

フォールト トレランスのため、Chubby クラスターは 5 つのノードで構成され、Chubby セルを形成します。これら 5 つのノードのうち、マスターは 1 つだけで、残りはレプリカです。マスターのみがリクエストを処理し、ファイルを読み書きできます。他のレプリカ ノードは、フォールト トレランスのために Paxos アルゴリズムを通じてマスターの動作を複製します。

Chubby は以下もサポートしています:

• シーケンサー: シーケンス番号をロックします (デッドロックと監視をより適切に回避するため)。
• セッション: リース時間を含むクライアント セッション。
• KeepAlive: リースの有効期限が切れそうになったら、KeepAlive を送信してリースを更新できます。
• キャッシュ: ロック サービスは多数のクライアントをサポートし、読み取り要求を削減するためにクライアントを認識しないキャッシュをサポートします。

さらに興味深いのは、チャビーの失敗からの回復です。マスターに障害が発生すると、そのメモリ内のセッションとロックの情報だけでなく、セッション内の最も重要なリース情報も失われます。 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年。