太ったロックサービス

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

設計#

理由#

まず、クライアント Paxos ライブラリと集中型ロックサービスの 2 つの方法の違いを比較しました。

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

システム構造#

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

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

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

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

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

レプリカが失敗し、数時間以内に回復しない場合、シンプルな置き換えシステムが空きプールから新しいマシンを選択し、ロックサーバープロセスを起動し、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 RPC の上に位置しています。無効化リクエストを受信すると、クライアントは無効な状態をクリアし、次回の KeepAlive 呼び出しで確認を行います。変更プロセスは、サーバーが各クライアントがキャッシュを無効にすることを知るまで続きます：クライアントが無効化メッセージを確認した場合、またはクライアントがキャッシュのリースを期限切れにすることを許可した場合です。

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

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

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

キャッシュデータとメタデータに加えて、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 の開始までの間隔をカバーしているため、クライアントは遅延を感じるだけです。猶予期間がこの間隔よりも短い場合、クライアントはセッションを放棄し、アプリケーションレイヤーにエラーを報告します。

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

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

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

データベース実装#

最初の 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 を超えるクライアントが直接 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 自体はファイルであるため、あるパーティションが他のパーティションを使用して権限を確認する可能性があります。ただし、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 のキャッシュは、セルが大量のクライアントを支えることを許可しますが、負荷のピークは依然として問題です。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 RPC を UDP で送信することを余儀なくされました。UDP には混雑回避メカニズムがないため、上位の時間制限を考慮する必要がある場合、UDP を使用することを好みます。

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