太ったロックサービス

論文の翻訳を続けます。Chubby は Google 内部の多くの分散システムが依存する重要なコンポーネントの一つです。原文はこちら

設計#

理由#

まず、client Paxos ライブラリと centralized lock service の 2 つの方法の違いを比較しました。

client Paxos ライブラリは他のサービスに依存せず、標準的なプログラミングフレームワークを提供できますが、開発初期のプロトタイプ段階では高可用性を十分に考慮しておらず、一貫性プロトコルには適していません。ロックを使用することで、既存のプログラム構造と通信パターンをより便利に維持でき、合意を達成するために一定数のクライアントを維持する必要がなくなり、信頼できるクライアントシステムを実現するために必要なサーバーの数が減ります。これらの理由から、著者はロックサービスを選択し、主ノードの選挙や広告伝播などの機能を実現するために小さなファイルを保存できるようにしました。さらに、著者は大量のクライアントがファイルを監視し、イベント通知メカニズム、ファイルキャッシュ、安全メカニズムなどをサポートすることを含む、いくつかの期待される使用と環境に関する決定を紹介しました。

システム構造#

Chubby は主に RPC 通信を介して通信する 2 つのコンポーネント、サーバーとクライアントリンクライブラリで構成されています。クライアントとサーバー間のすべての RPC 通信は、クライアントライブラリを介して調整されます。

Chubby セルは、複数の（通常は 5 つの）サーバー（レプリカ）で構成されており、これらのレプリカは異なる場所（異なるラックなど）に配置され、関連する障害の可能性を低減します。レプリカは分散合意アルゴリズムを使用してマスターを選出し、過半数のレプリカの投票を得て、一定の期間（マスターリース）内に別のマスターを選出しないという約束を得る必要があります。主ノードが引き続きレプリカの過半数の票を獲得し続ける限り、リースは定期的に更新されます。

各レプリカは単純なデータベースのコピーを維持していますが、データベースへの読み書き操作はマスターのみが行うことができ、他のレプリカは合意プロトコルを介してマスターから更新をコピーします。クライアントは DNS にリストされたレプリカにマスターの位置を要求することでマスターを見つけます。非マスターノードがリクエストを受け取ると、マスターの識別子を返します。クライアントがマスターを特定すると、すべてのリクエストはそのマスターに送信され、ノードが応答を停止するか、自身がもはやマスターでないと識別するまで続きます。

書き込みリクエストは合意プロトコルを介してすべてのレプリカにブロードキャストされ、リクエストが call に到達した過半数のレプリカにのみ確認されます。読み取りリクエストはマスターノードが単独で処理し、マスターリースが期限切れでない限り安全です。なぜなら、同時に他のマスターが存在することは不可能だからです。

マスターが失敗した場合、他のレプリカはマスターリースが期限切れになると選挙プロトコルを実行し、通常数秒後に新しいマスターが選出されます。

レプリカが失敗し、数時間以内に復旧しない場合、シンプルな置換システムが空きプールから新しいマシンを選択し、ロックサーバープロセスを起動し、DNS テーブル内の対応するレプリカの IP を更新します。現在のマスターノードは定期的に DNS をポーリングし、最終的にこの変更を発見し、データベース内のセルメンバーリストを更新します。このリストは通常の複製プロトコルを介してすべてのメンバー間で一貫性を保たれます。同時に、新しいレプリカはファイルサーバー内のバックアップや他のアクティブなレプリカから最近のデータベースコピーを取得します。一旦新しいレプリカが現在のマスターが待機中のリクエストを処理すると、新しいマスター選挙に投票できます。

ファイル、ディレクトリ、およびハンドル#

Chubby はファイルシステムに似たインターフェースを提供しますが、UNIX インターフェースよりもシンプルです。システム全体はスラッシュで区切られた名前で構成されるツリー構造を持ち、例えば/ls/foo/wombat/pouchのようになります。ここで、/ls はすべての名前の共通接頭辞であり、ロックサービスを示します。2 番目の部分 foo は Chubby セルの名前であり、DNS クエリを介して 1 つまたは複数の Chubby サーバーに解決されます。特別なセル名localは、クライアントがローカルセルを使用すべきことを示します。通常、このセルはクライアントと同じ建物内にあります。残りの部分 /wombat/pouch はクライアントが独自に定義したものです。

このファイルシステムに似た構造を使用することで、基盤となるブラウジングや名前空間操作ツールを実装する必要がなくなり、ユーザー教育のコストが削減されます。

Chubby は、配布を容易にするために従来の UNIX ファイルシステム設計とは異なります。異なるディレクトリのファイル（異なるセル）が異なるマスターにサービスされることを許可するために、Chubby はファイルを 1 つのディレクトリから別のディレクトリに移動する操作をサポートせず、ディレクトリの変更時間を維持せず、パス依存権限（つまり、各ファイルの権限はファイル自体によって制御され、所在するディレクトリとは無関係）を回避します。

ファイルメタデータキャッシュを簡素化するために、システムは最終アクセス時間を表示しません。名前空間にはファイルとディレクトリのみが含まれ、総称してノードと呼ばれます。各ノードはそのセル内で唯一の名前を持ち、シンボリックリンクやハードリンクは使用されません。

ノードは永続的または一時的であり、すべてのノードは明示的に削除できます。一時的なノードは、クライアントがそれを開いていない（またはディレクトリが空である）場合に削除され、一時的なノードは一時ファイルとして使用され、他のノードにクライアントがアクティブであることを示します。

すべてのノードは読み取り / 書き込みの相談ロックとして使用できます。各ノードには、読み取り制御、書き込み制御、ノード ACL 名の変更に使用される 3 つの ACL（アクセス制御リスト）を含むさまざまなメタデータがあります。

オーバーライドがない場合、ノードは作成時に親ディレクトリの ACL 名を継承します。ACL 自体も ACL ディレクトリ内のファイルであり、セルのローカル名前空間の一部です。これらの ACL ファイルには、責任者の名前のリストが含まれています。したがって、ファイル F の書き込み ACL 名が foo であり、ACL ディレクトリに foo という名前のファイルが含まれている場合、このファイルに bar というエントリが含まれていると、ユーザー bar は foo ファイルに書き込むことが許可されます。ユーザーは RPC システム内蔵のメカニズムを介して検証されます。

Chubby の ACL はシンプルなファイルであるため、他のサービスが同様の権限制御メカニズムを使用することが自動的に可能です。

各ノードのメタデータには、クライアントが変更を簡単に確認できるようにするための 4 つの単調に増加する 64 ビット数が含まれています：

インスタンス番号：同じ名前のインスタンス番号より大きい（削除、同じノードの作成）
コンテンツ生成番号（ファイルのみ）：ファイルコンテンツを書き込むときに増加
ロック生成番号：ノードロックがアイドルから保持に変わるときに増加
ACL 生成番号：ノードの ACL 名が書き込まれるときに増加

Chubby は 64 ビットのファイルコンテンツチェックサムも提供しており、クライアントはファイルに変更があるかどうかを知ることができます。クライアントはファイルを開くとハンドルを取得し、UNIX のファイルディスクリプタに似ています。ハンドルには以下が含まれます：

チェックビット、クライアントがハンドルを作成または推測するのを防ぐため、ハンドル作成時に完全なアクセス制御チェックを実行する必要があります。（UNIX がファイルを開くときにのみ権限ビットをチェックするのと似ています）
シーケンス番号、マスターがこのハンドルを自分自身または以前のマスターノードによって生成されたかを判断するために使用されます
ファイルを開くときに提供されたモード情報、古いハンドルが発生した場合に新しく起動したマスターがその状態を再構築できるようにします

ロックとシーケンサー#

Chubby の各ファイルとディレクトリは、読み書きロックのように振る舞います：クライアントハンドルが排他モードでロックを保持するか、複数のクライアントハンドルが共有モードでロックを保持します。

ここでのロックは相談ロックです：同じロックを取得しようとする他の操作とのみ衝突し、ロック F を保持することはファイル F にアクセスするために必須ではなく、他のクライアントがこのファイルにアクセスするのをブロックしません。対照的に、強制的にロックされたオブジェクトは、ロックを保持していない他のすべてのクライアントがアクセスできなくなります：

Chubby ロックが保護するリソースは、ロック関連のファイルだけでなく、他のサービスによって実装されます。強制ロックを強制する必要がある場合は、これらのサービスを変更する必要があります。
ユーザーがデバッグや管理の目的でロックされたファイルにアクセスする必要がある場合、アプリケーションを終了させることを強制したくありません（ロックを解除するために）。
エラー検出が簡単で、lock X is held のようなアサーションを行うだけで済みます。
バグや悪意のある操作は、ロックを保持していないときにデータを破損する多くの機会があるため、強制ロックが提供する追加の保証にはあまり価値がないと考えています。

Chubby では、どのタイプのロックを取得する場合でも書き込み権限が必要であり、これにより権限のないリーダーがライターの操作を妨げることはできません。

分散システムにおけるロックは非常に複雑です。なぜなら、通信は一般に不確実であり、プロセスが独立して失敗する可能性があるからです。したがって、ロック L を保持しているプロセスが R リクエストを発出し、その後自分自身が失敗する可能性があります。同時に、別のプロセスがロック L を取得し、R リクエストが目的地に到達する前にいくつかの操作を実行する可能性があります。もし R が後で到達した場合、ロック L の保護なしで不一致なデータを使用して操作を実行する可能性があります。メッセージの受信順序の混乱の問題は多くの研究が行われており、解決策には仮想時間、仮想同期が含まれます。これは、すべての参加者が観察する一貫した順序でメッセージを処理することを保証することで、この問題を回避します。

既存の複雑なシステムにすべての相互作用にシーケンス番号を導入するコストは非常に高いため、Chubby はロックを使用する相互作用にのみシーケンス番号を導入する方法を提供します。任意の時点で、ロックの保持者はシーケンサー（シーケンスコントローラー）にリクエストを行い、ロック取得後の瞬時の状態を説明する非透明なバイト列を生成します：ロックの名前、ロックモード（排他または共有）、ロック生成番号を含みます。

クライアントがサーバー上で保護された操作を実行したい場合、シーケンサーをサーバーに渡します。受信したサーバーはシーケンサーが依然として有効で適切なモードにあるかを確認し、そうでなければリクエストを拒否します。シーケンサーはサーバーの Chubby キャッシュを介して有効性を検証できます。サーバーが Chubby とのセッションを維持したくない場合は、サーバーが最後に観察したシーケンサーを使用して検証できます。シーケンサーのメカニズムは、メッセージに文字列を追加するだけで済み、開発者に説明するのも容易です。

シーケンサーは使いやすいですが、重要なプロトコルの進展は遅いです。したがって、Chubby はシーケンサーをサポートしていないサービスに対して、遅延や乱序リクエストのリスクを軽減するための不完全だがよりシンプルなメカニズムも提供しています。

クライアントが正常にロックを解放した場合、他のクライアントは直ちにそのロックを取得できます。その後、ロックが保持者のクラッシュやアクセス不能によって解放された場合、ロックサーバーは他のクライアントが一定期間そのロックを取得するのを防ぎます。これをロック遅延と呼び、クライアントは遅延時間を指定できますが、上限は 1 分です。この上限は、クラッシュしたクライアントがロック（およびそれに関連するリソース）を任意の長さの時間利用できないようにするためです。完璧ではありませんが、ロック遅延は未修正のサーバーとクライアントをメッセージ遅延や再起動による日常的な問題から保護します。

イベント#

Chubby クライアントはハンドルを作成する際に一連のイベントを購読でき、これらのイベントは Chubby ライブラリの上層呼び出しを介して非同期的にクライアントに配信されます。イベントには以下が含まれます：

ファイルコンテンツの変更：ファイルを介してブロードキャストされるサービスロケーション（サービス発見）を監視するためによく使用されます。
子ノードの追加、削除、または変更：ミラーリングを実現するために使用されます。
Chubby マスターのフェイルオーバー：クライアントに他のイベントが失われる可能性があることを警告し、データを再スキャンする必要があります。
ハンドルおよびその関連ロックの失効：一般的に通信に問題があることを示します。
ロック取得：プライマリが選出されたかどうかを判断するために使用されます。
他のクライアントの衝突ロックリクエスト：ロックキャッシュを許可します。

イベントは対応する動作が発生した後に配信されるため、クライアントがファイルコンテンツの変更を通知された場合、その後読み取られるデータがすべて新しいことが保証されます。上記の後の 2 つのイベントはあまり使用されず、振り返ると省略可能です。例えば、選挙後、クライアントは通常、新しいプライマリと通信する必要があり、単にプライマリが存在することを知っているだけでは不十分です。そのため、彼らは新しいプライマリがそのアドレスをファイルに書き込んだことを示す変更イベントを待ちます。

衝突ロックイベントは理論的にはクライアントが他のサーバーが保持するデータをキャッシュすることを許可し、Chubby ロックを使用してキャッシュの一貫性を維持します。ロック衝突リクエスト通知はクライアントに未処理の操作を完了するように示し、変更をフラッシュし、キャッシュデータを破棄してロックを解放します（ロック衝突は別のクライアントがデータを変更しようとしていることを意味します）。しかし、現時点ではこの方法を採用した人はいません。

API#

クライアントは Chubby ハンドルをさまざまな操作をサポートする非透明なポインタとして扱います。ハンドルは Open を介してのみ作成され、Close を介して破棄されます。

Open は指定された名前のファイルまたはディレクトリを開き、ハンドルを生成します。これは UNIX のファイルディスクリプタに似ており、Open は名前を使用する唯一の操作であり、他のすべての操作はハンドルに基づいています。ここで使用される名前は、既存のディレクトリハンドルに対する相対パスです。その後、ライブラリは常に有効なハンドル/を提供し、ディレクトリハンドルは多層抽象のマルチスレッドプログラム内でグローバルに current directory を使用する際に発生する問題を回避します。

クライアントはさまざまなオプションを提供します：

ハンドルの使用方法（読み取り / 書き込み / ロック / ACL の変更）クライアントが適切な権限を持っている場合にのみハンドルが正常に作成されます。
発信されるべきイベント。
ファイルまたはディレクトリを直ちに作成する必要があるか（必須か）、作成された場合、呼び出し元は初期コンテンツと初期 ACL 名を提供でき、戻り値はファイルが作成されたかどうかを示します。

Close () は開いているハンドルを閉じ、その後ハンドルは使用できなくなります。この呼び出しは決して失敗しません。関連する呼び出し Poison () は、ハンドルを閉じる必要なく、すべての未完了および後続の操作を失敗させます。この方法により、クライアントは他のスレッドが実行している Chubby 呼び出しをキャンセルでき、これらの呼び出しがアクセスするメモリを解放することを心配する必要がありません。

ハンドル上で主に実行される呼び出しは：

GetContentsAndStat () はファイルの内容とメタデータを返し、ファイル内容は原子的に完全に読み取られます。部分的な読み取りや書き込みを避け、大きなファイルの使用を防ぎます。関連する呼び出し GetStat () はファイルのメタデータのみを返し、ReadDir () はディレクトリ内の子ノードの名前とメタデータを返します。
SetContents () はファイルに内容を書き込み、クライアントはファイル生成番号を提供してファイルの compare-and-swap をシミュレートできます。生成番号と現在の番号が一致する場合にのみ内容が変更されます。書き込み操作も原子的な全体書き込みです。類似の SetACL () 呼び出しもノードに関連する ACL 名に対して同様の操作を実行します。
Delete () はノードに子ノードがない場合にそのノードを削除します。
Acquire (), TryAcquire (), Release () はロックを取得および解放します。
GetSequencer () は現在のハンドルが保持しているすべてのロックのシーケンサーを返します。
SetSequencer () はハンドルとシーケンサーを関連付けます。シーケンサーがすでに無効な場合、関連するすべてのシーケンサー操作は失敗します。
CheckSequencer () はシーケンサーが有効かどうかを確認します。

ハンドルが作成された後にノードが削除されると、呼び出しは失敗します。たとえ後続のファイルが再作成されても、ハンドルは常にファイルインスタンスに関連付けられています。Chubby はすべての呼び出しに対してアクセス制御チェックを実行できますが、実際には Open 呼び出しのみをチェックします。

上記のすべての呼び出しは、使用されるパラメータに加えて、操作パラメータを添付して、任意の呼び出しに関連するデータや制御情報を保存します。具体的には、操作パラメータを介してクライアントは：

呼び出しを非同期にするためのコールバック関数を提供する。
呼び出しが終了するのを待つ。
拡張エラーおよび診断情報を取得する。

クライアントはこれらの API を使用してプライマリ選挙を実行できます。すべての潜在的なプライマリはロックファイルを開き、ロックを取得しようとします。そのうちの 1 つが成功し、プライマリとなり、他はレプリカとなります。その後、プライマリは SetContents () 呼び出しを使用して自分の識別子をロックファイルに書き込み、他のクライアントやレプリカが GetContentsAndStat () を介してファイルを発見できるようにします（ファイル変更イベントの応答として）。理想的には、プライマリは GetSequencer () を介してシーケンサーを取得し、後続の通信でサーバーに渡します。彼らは CheckSequencer () を実行して、依然としてプライマリであることを確認します。シーケンサーを確認できないサービスには、前述の遅延ロックを使用できます。

キャッシング#

読み取りトラフィックを減らすために、Chubby クライアントはメモリ内にファイルデータとノードのメタデータをキャッシュします。キャッシュはリースメカニズムによって維持され、マスターから送信される無効化リクエストによって一貫性が保たれます。このプロトコルは、クライアントが一貫した Chubby 状態を見たり、エラーが発生したりすることを保証します。

ファイルデータまたはメタデータが変更されると、変更操作はマスターがすべての可能性のあるキャッシュデータを持つクライアントに無効化リクエストを送信するまでブロックされます。このメカニズムは KeepAlive RPCs の上にあります。無効化リクエストを受信すると、クライアントは無効な状態をクリアし、次回の KeepAlive 呼び出しで確認を行います。変更プロセスは、サーバーが各クライアントがキャッシュを無効化することを知るまで続きます：クライアントが無効化メッセージを確認した場合、またはクライアントがキャッシュのリースを期限切れにすることを許可した場合です。

無効化を確認する必要がないのは、キャッシュの無効化が確認できない場合、マスターはノードをキャッシュできないと見なすからです。この方法により、読み取りリクエストは遅延処理されることはなく、読み取り操作が書き込み操作を大幅に上回る場合に非常に便利です。代替案は、無効化中にすべてのアクセスをブロックすることですが、これにより一部のホットクライアントが無効化中にマスターに対して爆発的な非キャッシュアクセスを行うことが減少しますが、時折の遅延という代償が伴います。これが問題である場合、混合戦略を採用し、過負荷が検出されると戦略を切り替えることを想像できます。

キャッシュプロトコルは非常にシンプルで、変更があった場合に直接無効化し、キャッシュを更新することはありません。更新は無効化よりも簡単かもしれませんが、更新のみのプロトコルは非常に非効率的になる可能性があります。クライアントがファイルにアクセスする際に無限に多くの更新を受け取る可能性があり、無限に多くの不必要な更新（無効化後に最新のものを取得すればよい）を引き起こす可能性があります。

厳密な一貫性を提供するコストは非常に高いため、プログラマーにとって使いにくい弱い一貫性モデルの使用を拒否しています。例えば、仮想同期メカニズムは、事前に存在する多様な通信プロトコルの環境では、クライアントがすべてのメッセージでシーケンス番号を交換する必要があるため、適切ではありません。

Chubby クライアントはキャッシュデータとメタデータに加えて、オープンされたハンドルもキャッシュします。したがって、クライアントが以前にオープンしたファイルを再度オープンする場合、最初の Open リクエストのみがマスターに送信されます。このキャッシュにはいくつかの小さな制限があり、クライアントが観察するセマンティクスに影響を与えないようにしています：一時ファイルのハンドルはアプリケーションがそれを閉じた後にオープン状態を保持できず、ロック可能なハンドルは再利用できますが、複数のハンドルで同時に使用することはできません。後者の制限が存在するのは、クライアントが Close () または Poison () を使用して未完了の Acquire () 呼び出しをマスターにキャンセルし、副作用を引き起こす可能性があるためです。

Chubby プロトコルはクライアントがロックをキャッシュすることを許可します。つまり、必要以上に長くロックを保持することができ、同じクライアント上で再利用できます。他のクライアントがロックの衝突を要求すると、ロックの保持者にイベントが通知され、保持者は他の場所でロックが必要な場合に解放することができます。

セッションと KeepAlives#

Chubby セッションは Chubby セルとクライアントの関係を指し、一連のイベントを持ち、KeepAlives と呼ばれる周期的なハンドシェイクによって維持されます。クライアントがマスターに通知しない限り、クライアントのハンドル、ロック、およびキャッシュデータはセッションが有効な間は有効のままです（セッション維持メッセージは、セッションを有効に保つためにクライアントがキャッシュ無効化を確認する必要がある場合があります）。

クライアントは Chubby セルとの最初の接触時に新しいセッションを要求し、セッションの終了は暗黙的であり、クライアント自身が終了するか、セッションがアイドル状態（1 分間ハンドルを開かず、呼び出しがない）になる可能性があります。

各セッションには関連するリース（更新間隔）があり、将来の一定期間内にマスターが一方的にセッションを終了しないことを保証します。この時間間隔の終了はセッションリースのタイムアウトと呼ばれ、マスターは自由にタイムアウト時間を将来に延長できますが、過去に移動することはできません。

マスターは以下の 3 つの状況でリースタイムアウト時間を延長します：セッション作成時、マスターがフェイルオーバーしたとき、クライアントの KeepAlive RPC に応答するとき。KeepAlive リクエストを受信すると、マスターは一般的に RPC をクライアントの前のリース間隔がほぼ期限切れになるまでブロックし、その後 RPC をクライアントに返し、新しいリースタイムアウト時間を通知します。マスターは任意の長さの時間にタイムアウトを延長することができ、デフォルトの延長時間は 12 秒ですが、負荷が高いマスターは処理する必要がある KeepAlive 呼び出しの数を減らすためにより長い時間を使用する可能性があります。クライアントは前の応答を受け取った後、すぐに新しい KeepAlive を開始するため、クライアントはほぼ常にマスター上で KeepAlive がブロックされていることを保証できます。

リースを延長することに加えて、KeepAlive の応答はイベントやキャッシュの無効化を伝送するためにも使用できます。マスターはイベントを配信するか無効化する際に早期に KeepAlive を返すことを許可し、応答にイベントを搭載することで、クライアントがキャッシュ無効化を確認する前にセッションを維持できなくし、すべての Chubby RPC がクライアントからマスターに流れることを可能にします。これにより、クライアントが簡素化され、プロトコルが単方向接続の初期化を許可するファイアウォール上で実行できるようになります。

クライアントは、マスターに対して比較的保守的なリースタイムアウト時間をローカルに維持します。これは、クライアントが応答メッセージの戻りにかかる時間や、マスター上の時計が進んでいる可能性を考慮する必要があるためです。一貫性を保つために、サーバーの時計がクライアントの時計よりも既知の定数因子を超えて進んでいないことを保証する必要があります。

クライアントのローカルリースがタイムアウトすると、マスターがこのセッションを終了したかどうかを確認できなくなります。クライアントはキャッシュを無効にし、クリアし、不確定な状態に置かれます。クライアントは猶予期間（デフォルトは 45 秒）を待ち、この期間が終了する前に KeepAlive を正常に交換できた場合、クライアントは再びキャッシュを有効にします。そうでなければ、クライアントはセッションが期限切れになったと仮定します。このようにすることで、Chubby セルにアクセスできない場合、Chubby API 呼び出しが無期限にブロックされることを防ぎます。猶予期間が終了する前に通信が再確立されない場合、呼び出しはエラーを返します。

猶予期間が始まると、Chubby ライブラリはアプリケーションに危険なイベントを通知できます。セッション通信の問題が回復した後、安全なイベントが送信され、逆にセッションがタイムアウトした場合はタイムアウトイベントが送信されます。これらの情報は、アプリケーションが自身のセッションの状態を不確定に保つことを可能にし、一時的な問題に直面した場合でも再起動せずに回復できるようにします。起動コストが非常に高いサービスにとって、中断を防ぐことは重要です。

クライアントがノードのハンドル H を保持しており、関連するセッションが期限切れになったため、H 上のすべての操作が失敗した場合、以降のすべてのリクエスト（Close を除く）は同様に失敗します。クライアントはこれを利用して、ネットワークやサービスの中断が操作シーケンスの一部の後継部分の喪失を引き起こすだけであり、任意の部分シーケンスが失われることはないことを保証できます。したがって、最終的な書き込みを使用して複雑な変更をコミット済みとしてマークできます（最終的な書き込みが成功すれば、前のすべての操作は必ず成功しています）。

フェイルオーバー#

マスターが故障したり、主権を失ったりすると、すべてのメモリ状態が破棄されます。これには、セッションハンドルやロックが含まれます。セッションリースの権威あるタイマーはマスター上で実行されるため、新しいマスターが選出されるまでリースタイマーは停止します。これは、クライアントのリースを延長するのと同等です。マスターの選挙が迅速であれば、クライアントはローカル（緩やかに）リースタイマーが期限切れになる前に新しいマスターに接続できます。しかし、リースが長時間かかる場合、クライアントはローカルキャッシュをクリアし、猶予期間内に新しいマスターを待ちます。したがって、猶予期間は通常のリースタイムアウトを超えるフェイルオーバー中にセッションを維持することを許可します。

フェイルオーバー

上の図は、長いマスターのフェイルオーバーイベントプロセス中の一連のイベントを示しています。クライアントは猶予期間を使用してセッションを保護する必要があります。初期マスターはクライアントリース M1 を持ち、次にクライアントは比較的保守的な推定 C1 を持ちます。その後、マスターは M2 リースを提出し、クライアントはリースを C2 に延長します。その後、次の KeepAlive の応答の前にマスターがクラッシュし、新しいマスターが選出されるまでにしばらく時間が経過します。最終的にクライアントリース C2 が期限切れになり、クライアントはキャッシュをクリアし、新しい猶予期間タイマーを開始します。

この期間中、クライアントはそのリースがマスター上で期限切れになったかどうかを確認できません。クライアントはセッションを直ちに破棄することはありませんが、すべてのアプリケーション層の API 呼び出しをブロックし、アプリケーション層が不一致なデータを観察するのを避けます。猶予期間の開始時に、Chubby ライブラリはアプリケーションに危険なイベントを送信し、セッション状態を確認できるまでリクエストを送信し続けるようにします。

最終的に新しいマスターが選出され、マスターは以前に保持していた可能性のあるリースに保守的な推定リース M3 を初期化します。クライアントから新しいマスターへの最初の KeepAlive リクエストは、誤ったマスターサイクル番号を含むため拒否されます。リトライリクエスト（6）は成功しますが、一般的にはマスターリースを延長しません。なぜなら、M3 自体が保守的な推定（延長）だからです。しかし、応答（7）はクライアントが再び自分のリースを C3 に延長できることを許可し、アプリケーション層にセッションがもはや危険ではないことを通知できます。猶予期間が十分に長く、C2 の終了から C3 の開始までの間隔をカバーしているため、クライアントは遅延を感知するだけで済みます。もし猶予期間がこの間隔よりも短い場合、クライアントはセッションを放棄し、アプリケーション層にエラーを報告します。

クライアントが新しいマスターに接続すると、クライアントライブラリとマスターは協力してアプリケーション層に障害が発生したことがなかったかのような錯覚を提供します。この目標を達成するために、新しいマスターは以前のマスターに対する保守的なメモリ状態を再構築する必要があります。これは、ディスク上のデータ（通常のデータベース複製プロトコルバックアップを介して）を読み取ることによって部分的に行われ、部分的にはクライアントから取得した状態を取得し、部分的には保守的な推定を行います。データベースは各セッション、保持しているロック、および一時ファイルを記録します。

選出された新しいマスターは以下の手順を実行します：

マスターは新しいエポック番号を選択します。クライアントは各呼び出しでマスターにこの番号を渡す必要があり、マスターはこのエポック番号よりも低いリクエストを拒否し、現在の最新の番号を提供します。これにより、新しいマスターは以前のマスターに送信されたデータパケットに応答しないことが保証されます。たとえ同じマシン上で実行されていてもです。
マスターはマスター位置リクエストに応答することがありますが、最初はセッション関連のリクエストを処理しません。
マスターはメモリ内でデータベースに記録されたセッションとロックのデータ構造を再構築します。セッションリースは前のマスターが使用する可能性のある最大の期間に延長されます。
マスターはクライアントに KeepAlives を実行させますが、他のセッション関連の操作は実行しません。
マスターはすべてのセッションにフェイルオーバーイベントを送信します。これにより、クライアントはキャッシュをクリアします（キャッシュ無効化通知を見逃す可能性があるため）し、アプリケーション層にいくつかのイベントが失われた可能性があることを警告します。
マスターはすべてのセッションがフェイルオーバーイベントを確認するか、期限切れになるのを待ちます。
マスターはすべての操作を処理することを許可します。
クライアントがフェイルオーバー前に作成されたハンドルを使用している場合（ハンドル内のシーケンス番号で特定されます）、マスターはこのハンドルのメモリ内の表現を再作成し、呼び出しに応答します。この新しく作成されたハンドルが閉じられた場合、マスターはメモリ内に記録し、現在のエポック内で再作成されないようにします。これにより、遅延または重複したネットワークパケットが意図せずに閉じられたハンドルを再作成することがないようにします。故障したクライアントは後のエポックで閉じられたハンドルを再作成できますが、これは無害です。
一定時間後、マスターは開かれていないハンドルの一時ファイルを削除します。クライアントもフェイルオーバー後に一時ファイル上のハンドルを更新する必要があります。このメカニズムの不幸な結果は、最後のファイルを使用していたクライアントがフェイルオーバー中にセッションを失った場合、一時ファイルが適時に消失しない可能性があることです。

データベース実装#

最初の Chubby 版は、Berkeley DB の複製バージョンをデータベースとして使用しました。Berkeley DB は B ツリーを提供し、バイト列キーを任意のバイト列値にマッピングします。私たちはキー比較関数を使用しました：まず、パス内の階層数を比較し、すべてのノードをパス名に基づいてキーに分割し、兄弟ノードがソート内で隣接することを保証します。Chubby はパスベースの権限を使用しないため、ファイルアクセスごとにデータベースで 1 回の検索で済みます。

Berkeley DB は、分散合意プロトコルを使用して複数のサーバー間でデータベースログを複製します。マスターリースが追加されると、これは Chubby の設計と一致し、実装が簡単で直接的になります。

Berkeley DB の B ツリーコードは広く使用されており、非常に成熟していますが、複製コードは最近追加されたもので、ユーザーはほとんどいません。ソフトウェアのメンテナは、最も流通している製品機能の維持と改善を優先する必要があります。Berkeley DB のメンテナは私たちの問題を解決し、私たちは複製コードを使用することで、私たちが引き受けるよりも多くのリスクに直面することになると感じました。最終的に、私たちは WAL とスナップショット技術を使用してシンプルなデータベースを書きました。以前と同様に、データベースログは分散合意プロトコルを介してすべてのレプリカ間で配布されます。Chubby は Berkeley DB のごく一部の機能を使用しているため、この再実装により、システム全体を大幅に簡素化できました。たとえば、原子的な操作が必要な場合、トランザクションは不要です。

バックアップ#

数時間ごとに、各 Chubby セルのマスターはそのデータベーススナップショットを異なる建物の GFS サーバーに書き込みます。異なる建物を使用することで、建物が損傷した場合でもバックアップが生存でき、レプリカがシステム内に循環依存を導入することはありません。同じ建物内の GFS セルは、選挙された Chubby セルに依存する可能性があります。

バックアップは災害復旧を提供し、稼働中のサービスに負荷をかけることなく新しい代替レプリカのデータベースを初期化する方法を提供します。

ミラーリング#

Chubby は、ファイルのセットを 1 つのセルから別のセルにミラーリングすることを許可します。ミラー操作は非常に迅速で、ファイルが小さく、イベントメカニズムがファイルの追加 / 削除 / 変更時にミラーコードに即座に通知できるためです。ネットワークの問題がないと仮定すると、変更は 1 秒未満で数十のミラーに反映されます。ミラーが到達できない場合、その状態は接続が回復するまで変わりません。ファイルの更新は、チェックサムを比較することで識別されます。

ミラーリングは、世界中の異なる計算クラスターに設定ファイルをコピーするために最も頻繁に使用されます。globalという名前の特別なセルは、すべての他のセルにミラーリングされるサブツリー/ls/global/masterを含んでいます。global セルは特別で、5 つのレプリカが世界中に広く分散しているため、ほとんどの場所でアクセス可能です。

global セルのミラーリングファイルには、Chubby 自身の権限制御リストや、Chubby セルと他のサービスが監視サービスに存在を通知するファイルが含まれており、クライアントが Bigtable セルのような大規模データセットのポインタや、他の多くのシステムの設定ファイルを特定できるようにします。

スケーリングのメカニズム#

Chubby のクライアントは独立したプロセスであるため、Chubby は予想以上に多くのクライアントを処理する必要があります。私たちは 90000 を超えるクライアントが 1 つの Chubby マスターに直接接続しているのを見たことがあります。各セルには 1 つのマスターしかなく、そのマシンとクライアントは同じであるため、クライアントデータは処理能力を大幅に超えています。したがって、最も効果的なスケーリング技術は、マスターとの通信を大幅に減少させることによって実現されます。マスターに深刻なパフォーマンスバグがないと仮定すると、リクエスト処理におけるマスターのわずかな改善はその影響が小さいです。私たちはいくつかの方法を使用しています：

任意の数の Chubby セルを作成できますが、クライアントはほぼ常に最近のセルを使用してリモートマシンに依存することを避けます。私たちの典型的なデプロイメントは、数千台のマシンのデータセンターで 1 つの Chubby セルを使用することです。
マスターは高負荷時にリース時間を 12 秒から最大 60 秒に延長できます。これにより、KeepAlive RPC の処理が少なくなります（KeepAlive は主要なリクエストタイプであり、リクエストをタイムリーに処理できないことは、過負荷サーバーの典型的な故障モードです。クライアントは他の呼び出しの遅延変化に非常に鈍感です）。
Chubby クライアントはファイルデータ、メタデータ、欠落ファイル、およびオープンされたハンドルをキャッシュして、サーバーへの呼び出しを減らします。
プロトコル変換サーバーを使用して、Chubby プロトコルを DNS などのよりシンプルなプロトコルに変換します。

ここでは、代理とパーティショニングという 2 つの馴染みのあるメカニズムを説明します。これらは Chubby をさらに拡張できると期待しています。私たちはまだ生産環境で使用していませんが、すでに設計されており、すぐに使用される可能性があります。私たちは現在、5 倍を超える拡張を考慮する必要はありません。まず、データセンターに配置されたマシンや単一サービスのインスタンスには数の制限があります。次に、Chubby クライアントとサーバーで同様のマシンを使用しているため、ハードウェアの最適化は各マシン上でクライアントの数を増やすだけでなく、各サーバーの容量も増加させます。

プロキシ#

Chubby のプロトコルは信頼できるプロセスによって代理されることができます。プロキシは KeepAlive や読み取りリクエストを処理することでサーバーの負荷を軽減できますが、書き込みトラフィックを減らすためにプロキシキャッシュを使用することはできません。しかし、積極的なクライアントキャッシュ戦略を使用しても、書き込みフローは Chubby の通常の作業負荷の 1％未満しか占めません。したがって、プロキシを使用することでクライアントの数を大幅に増やすことができます。

プロキシが N 個のクライアントの KeepAlive トラフィックを処理すると、N が 10k 以上になる可能性があるため、トラフィックが減少します。プロキシキャッシュは、読み取りトラフィックを約 10 倍の要因で減少させることができます。ただし、読み取りは Chubby の負荷の 10％未満しか占めないため、KeepAlive トラフィックを節約する効果がより重要です。さらに、プロキシは書き込みや最初の読み取りの追加 RPC 呼び出しを追加します。人々は、プロキシがセルの一時的な利用不可性を以前の 2 倍に増加させることを期待するかもしれません。なぜなら、各プロキシクライアントは、故障する可能性のある 2 台のマシン、すなわちプロキシサーバーと Chubby マスターサーバーに依存するからです。鋭い読者は、以前に説明したフェイルオーバー戦略がプロキシサーバーには理想的ではないことに気付くかもしれません。

パーティショニング#

Chubby のインターフェースは、セルの名前空間を異なるサーバーにパーティショニングできるように設計されています。現在は必要ありませんが、コードはディレクトリを介して名前空間をパーティショニングできます。これが有効になれば、Chubby セルは N 個のパーティションで構成され、各パーティションにはレプリカのセットとマスターがあります。各ディレクトリ D 内のノード D/C は、パーティションP(D/C) = hash(D) mod Nに保存されます。D のメタデータは異なるパーティションに保存される可能性がありますP(D) = hash(D0) mod N。ここで、D0 は D の親ディレクトリです。

パーティショニングは、通信がほとんどない大規模な Chubby セルを実現することを目的としています。Chubby はハードリンク、ディレクトリの変更時間、ディレクトリをまたぐ名前変更操作を欠いていますが、一部の操作は依然としてパーティション間の通信を必要とします：

ACL 自体がファイルであるため、1 つのパーティションが他のパーティションで権限チェックを行う可能性があります。ただし、ACL ファイルは簡単にキャッシュでき、Open () および Delete () 呼び出しのみが ACL チェックを必要とし、ほとんどのクライアントが公開アクセス可能なファイルを読み取るため、ACL は必要ありません。
ディレクトリが削除されると、パーティション間の呼び出しがこのディレクトリが空であることを確認する必要がある場合があります。

各パーティションが処理する呼び出しの大部分は他のパーティションに依存しないため、パーティション間の通信がパフォーマンスや可用性に与える影響は限られていると予想されます。パーティションの数 N が大きくても、各クライアントは大多数のパーティションに接続することが期待されるため、パーティションはパーティション上の読み書きトラフィックを N 倍に減少させることができますが、KeepAlive トラフィックには必ずしも当てはまりません。

Chubby がより多くのクライアントを処理する必要がある場合、私たちの戦略にはプロキシとパーティショニングの組み合わせが含まれます。

使用、驚き、設計エラー#

... 関連データと使用状況を省略します。

名前サービスとしての使用#

Chubby はロックサービスとして設計されていますが、最も一般的な用途は名前サーバーとしての使用です。一般的なインターネットの名前システムは、時間に基づくキャッシュ DNS エントリを使用し、TTL が設定されています。この期間内に更新されないと、DNS データは破棄されます。通常、適切な TTL 値を選択することは非常に直感的ですが、失敗したサービスを迅速に置き換えたい場合、TTL は DNS サーバーを圧倒するほど小さくなる可能性があります。

例えば、私たちの開発者にとって、数千のプロセスを含むジョブを実行することは非常に一般的で、各プロセスは他のプロセスと通信する必要があり、平方レベルの DNS クエリを引き起こします。私たちは 60 秒の TTL を使用したいと考えています。これにより、行動が不適切なクライアントは過度の遅延なしに置き換えられ、私たちの環境では過度に短い置き換え時間とは見なされません。

この場合、約 3000 のクライアントを維持するために、毎秒 150k の DNS キャッシュクエリが必要です。より大規模なジョブはより深刻な問題を引き起こし、多くのジョブが同時に実行される可能性があります。Chubby を導入する前、私たちの DNS 負荷の変動は Google にとって深刻な問題でした。

対照的に、Chubby のキャッシュは無効化を表示するため、変更がない限り、一定の速度でセッション KeepAlive を要求することで、クライアント上で無期限に任意の数のキャッシュエントリを維持できます。2 コア 2.6GHz の Chubby マスターは、直接接続された 90k のクライアントを処理でき、その中には上記の大規模なジョブのクライアントが含まれています。各名前を個別にポーリングする必要がなく、迅速な名前更新の能力を提供できることは非常に魅力的であり、現在 Chubby は会社の多くのシステムに名前サービスを提供しています。

Chubby のキャッシュは、1 つのセルが大量のクライアントを支えることを許可しますが、負荷のピークは依然として問題です。Chubby ベースの名前サービスを最初に展開したとき、3000 のプロセス（900 万のリクエストを生成）を開くと、マスターがダウンしました。この問題を解決するために、私たちは一連の名前クエリをバッチ処理し、単一のクエリが大量（通常は 100 個）のジョブに関連するプロセスの名前マッピングを返すことができるようにしました。

Chubby が提供するキャッシュセマンティクスは、名前サービスよりも正確です。名前解決は完全な一貫性ではなく、タイムリーな通知が必要です。名前クエリ専用のシンプルなプロトコル変換サーバーを導入することで、Chubby への負荷を軽減する機会があります。Chubby が名前サービスとして使用されることを予見していれば、私たちはこのシンプルなニーズを避けるために完全なプロキシを早期に実装していたかもしれません。

さらに、別のプロトコル変換サーバーがあります：Chubby DNS サーバーは、Chubby 上の名前データを DNS クライアントに提供します。このサービスは、DNS 名から Chubby 名への移行を簡素化し、既存のアプリケーション（ブラウザなど）を適応させるのに重要です。

学んだ教訓#

開発者は可用性をほとんど考慮しない、私たちは開発者が故障の可能性をほとんど考慮せず、Chubby のようなサービスを常に利用可能と見なす傾向があることを発見しました。例えば、私たちの開発者は数百台のマシンを使用したシステムを構築したことがあり、Chubby がマスターを選出すると、このプログラムは復旧プログラムを起動し、数十分かかります。これは、単一の故障を時間的に 100 倍に拡大し、数百台のマシンに影響を与えます。私たちは、開発者が Chubby の短期的な中断に備えることを望んでおり、そのため、これらのイベントが彼らのアプリケーションにほとんど影響を与えないようにしたいと考えています。

開発者は、サービスの起動とサービスがアプリケーションに利用可能であることの違いを理解していません。例えば、global セルは基本的に常に稼働しており、地理的に遠く離れた 2 つ以上のデータセンターが同時にダウンすることはほとんどありません。しかし、クライアントが観察する可用性は常にクライアントのローカルセルよりも低くなります。まず、クライアントがローカルセルと分離される確率は低く、ローカルセルがメンテナンスのために頻繁にダウンする可能性があるため、同じメンテナンスがクライアントにも直接影響を与えます。そのため、Chubby の不可用性はクライアントには観察されません。

私たちの API 選択も、開発者が Chubby の中断を処理する方法に影響を与えます。例えば、Chubby はイベントを提供してクライアントがマスターのフェイルオーバーを発見できるようにします。元々の目的は、クライアントが可能な変更を確認することでしたが、他のイベントが失われる可能性があるためです。不幸なことに、多くの開発者はこのイベントを受け取ると、アプリケーションを直接クラッシュさせるため、システムの可用性が著しく低下します。私たちは、冗長なファイル変更イベントを送信するか、フェイルオーバー中にイベントが失われないことを確認する方が良いかもしれません。

現在、私たちは開発者が Chubby の可用性を過度に楽観視しないようにするために 3 つのメカニズムを使用しています。特に global セルに対してです。まず、以前に述べたように、私たちはエンジニアリングチームが Chubby をどのように使用するかを確認し、彼らのシステムの可用性を Chubby と密接に関連付ける技術を使用しないように提案します。次に、私たちは現在、開発者と Chubby の中断を自動的に隔離するためにいくつかの高レベルのタスクを実行するライブラリを提供しています。第三に、私たちは各 Chubby の中断について事後分析を行い、Chubby と私たちの運用プロセスのバグを排除するだけでなく、アプリケーションが Chubby の可用性に敏感でなくなるようにします。これらの 2 つは、システム全体の可用性を向上させることができます。

細粒度のロックは無視される可能性がある、前の章で、クライアントが細粒度ロックを使用できるサービスの設計について説明しました。驚くべきことに、これまでのところ、私たちはそのようなサービスを実装する必要がありません。私たちの開発者は、アプリケーションを最適化するために不必要な通信を削除する必要があることを発見しましたが、これは通常、粗粒度ロックを使用する方法を見つけることを意味します。

悪い API 選択は予期しない影響をもたらす、全体として私たちの API は順調に進化していますが、顕著なエラーが発生しました。私たちの意図は、長時間実行される呼び出しをキャンセルする API である Close () と Poison () RPCs を作成することでした。これにより、サーバー上のハンドルの状態が破棄されます。これにより、ロックを取得できるハンドルが共有されるのを防ぎます。例えば、複数のスレッドで共有されることができます。私たちは、オープンなハンドルが共有されることを許可する Cancel () RPC を追加できます。

RPC の使用はトランスポートプロトコルに影響を与える。KeepAlives は、クライアントのセッションを更新し、イベントを伝達し、マスターからのキャッシュ無効化を配信するために使用されます。この設計により、クライアントはキャッシュ無効化を確認できないときにセッションを更新できなくなります。これは理想的に見えますが、設計プロトコルを慎重に行う必要があります。TCP のバックオフ戦略は、Chubby のリースのような上位のタイムアウトを気にしません。したがって、TCP ベースの KeepAlives は、ネットワークの混雑時に非常に多くのセッションを失うことになります。私たちは、KeepAlive RPCs を送信するために UDP を使用せざるを得ません。UDP には混雑回避メカニズムがないため、上位の時間制限を考慮する必要がある場合、UDP を使用することを好みます。

通常、私たちは、イベントと無効化を伝達するために TCP ベースの GetEvent () RPC を追加してプロトコルを拡張できます。使用法は KeepAlive と同様で、KeepAlive 応答には未確認のイベントのリストが含まれ、イベントが最終的に確認されることを保証します。