且听风吟

分布式システム分野の古典的な論文で、ChatGPT と Claude の助けを借りて一度読んで翻訳しています。主に最初の 5 章です。こちらで原文を確認

概要#

GFS は、大規模な分散データ集約型アプリケーション向けのスケーラブルな分散ファイルシステムです。

GFS の適用シーンと設計のポイント#

1. GFS システムは、多くの安価な一般的なハードウェア上で動作するため、アプリケーションのバグ、オペレーティングシステムのバグ、人為的エラー、ディスク / メモリ / ドライバ / ネットワーク / 電源の故障など、故障が非常に一般的です。そのため、常態的な監視、エラー検出、フォールトトレランス、自動回復メカニズムが必要であり、コンポーネントの故障を異常ではなく常態として扱います。
2. GFS システムが保存するファイルは通常大きく、100MB や GB レベルに達することが一般的です。そのため、大きなファイルを効率的に管理する必要があり、小さなファイルはサポートできますが、最適化は必要ありません。
3. ファイルの変更は主に追加書き込みであり、上書きは非常に稀です。ファイルの読み取りは一般的に大規模なストリーミング読み取り（数百 KB から数 MB）または小規模（数 KB）のランダム読み取りです。
4. 負荷は主に次のようなものから来ます：大規模なストリーミング読み取り（数百 KB から数 MB）、小規模（数 KB）のランダム読み取り、および大量のシリアライズされた追加書き込み。
5. GFS のファイルはしばしば生産 - 消費キューやマルチウェイマージに使用されるため、システムは複数のクライアントによる同一ファイルへの並行追加セマンティクスを効率的に実装する必要があります。
6. 高持続帯域幅は低遅延よりも重要です。

インターフェース#

GFS インターフェースは次の操作を提供します：create、delete、open、close、read、write、snapshot、record append。ここで snapshot は低コストのファイル作成またはディレクトリコピー操作であり、record append は原子追加操作であり、複数のクライアントが同一ファイルに並行して追加できることを保証します。

アーキテクチャ#

GFS クラスターには 1 つのマスターノードと複数のチャンクサーバーがあり、すべてのファイルは固定サイズのチャンクに分割され、各チャンクは作成時にマスターによってグローバルに一意で不変の 64 ビットチャンクハンドルが割り当てられます。チャンクはチャンクサーバーによってローカルディスクに保存され、チャンクハンドルとバイト範囲を介して読み書きされます。信頼性を保証するために、各チャンクは複数のチャンクサーバーにレプリカが作成され、デフォルトでは 3 つ作成されます。

マスターノードはすべてのファイルのメタデータを保存し、名前空間の権限制御情報、ファイルからチャンクへのマッピング、およびチャンクの位置情報を含みます。マスターノードは同時にシステムレベルの活動を制御し、チャンクのリース管理、孤児チャンクのガベージコレクション、およびチャンクのチャンクサーバー間の移動を行います。マスターノードは定期的にハートビートメッセージを介してチャンクサーバーと通信し、指示を送信し、チャンクサーバーの状態情報を収集します。

クライアントはマスターと対話してメタデータを取得および変更します。すべてのデータを保持する通信は直接チャンクサーバーに接続され、クライアントとチャンクサーバーはファイルをキャッシュしません（ただし、クライアントはメタデータをキャッシュします）。以下の理由があります：

• クライアントがキャッシュする利点は非常に小さいです。ほとんどのリクエストは大きなファイルをストリーミングするか、大きな作業セットを持っているため、キャッシュできません。キャッシュがないことで、クライアントの実装が簡素化され、システム全体がキャッシュの無効化（整合性）問題を考慮する必要がなくなります。
• チャンクサーバーも別のキャッシュ層を持つ必要はありません。なぜなら、チャンク自体は通常のファイルとして保存されており、Linux のバッファキャッシュは頻繁にアクセスされるファイルをメモリ内に保持できます。

インタラクションフロー#

1. クライアントは固定のチャンクサイズに基づいてファイル名とオフセットをチャンクインデックスに変換します。
2. クライアントはファイル名とチャンクインデックスをマスターに送信します。
3. マスターは対応するチャンクの複数のレプリカのチャンクハンドルと位置情報を返します。
4. クライアントはファイル名にチャンクインデックスを追加して、サーバーから返された情報をキャッシュします。
5. クライアントはチャンクハンドルとバイト範囲を指定し、最も近いチャンクサーバーにデータリクエストを送信します。
6. 同じチャンクへの後続の読み取りリクエストはローカルキャッシュを使用し、マスターと対話する必要はありません。キャッシュ情報が無効になるか、ファイルが再度オープンされるまで続きます。
7. 通常、クライアントは 1 つのリクエストで複数のチャンクを含め、マスターも後で必要になる可能性のある複数のチャンクを一緒に返します。

チャンクサイズ#

GFS が選択したチャンクサイズは 64MB で、通常のオペレーティングシステムのディスクブロックよりも大きく、各チャンクのレプリカはチャンクサーバー上で Linux の通常のファイルの形式で保存され、スペースの割り当ては遅延的で、内部の断片化によるスペースの浪費を避けます。大きなチャンクサイズを選択することには以下の利点があります：

• 単一ファイルのチャンク数が少なくなり、クライアントとマスターの間でチャンクサーバーの位置情報を取得するリクエストが減少します。
• クライアントは同じチャンク上で複数の操作を実行でき、1 つの持続的な TCP 接続を維持するだけで済むため、多くの接続の作成に伴う追加のコストが削減されます。
• システム全体のチャンクの総数が少なくなり、マスターが保存する必要のあるメタデータのサイズが減少し、メタデータをメモリ内に保持できるようになります。

通常、小さなファイルは少量または 1 つのチャンクしか含まれません。同じファイルに多くのクライアントがアクセスする場合、これらのチャンクサーバーはホットスポットになる可能性があります。実際には、ホットスポットは主な問題ではありません。なぜなら、アプリケーションはほとんどが順次読み取りの多チャンクファイルだからです。しかし、GFS が初めてバッチ処理キューシステムに適用されたとき、確かにホットスポットの問題が発生しました：実行可能ファイルが GFS に単一のチャンクファイルとして書き込まれ、その後数百台のマシンが同時にアクセスし、ファイルを保存している少数のチャンクサーバーが数百の同時リクエストにより過負荷になりました。この問題を修正するために、2 つの方法を使用しました：1. レプリカの数を増やす 2. アプリケーションがチャンクの読み取り時間をずらして同時リクエストを避ける。もう 1 つの効果的な解決策は、このシナリオでクライアントが他のクライアントのデータを読み取ることを許可することです。

メタ情報#

マスターは 3 種類のメタデータを保存します：ファイルとチャンクの名前空間、ファイルからチャンクへのマッピング、各チャンクレプリカの位置情報。すべてのメタデータは常にマスターのメモリ内に存在し、マスターは前の 2 つの情報の変更ログをローカルおよびリモートのディスクに永続化します。ログの再生により、マスターの状態を簡単に更新でき、信頼性とクラッシュ後の状態回復の整合性問題を保証します。

マスターはチャンクレプリカの位置情報を永続化して保存せず、起動時にチャンクサーバーに問い合わせるか、新しいチャンクサーバーがクラスターに参加したときに問い合わせます。

メモリ状態#

メタデータがメモリに保存されているため、マスターの操作は一般的に非常に迅速であり、バックグラウンドで完全な状態を定期的に効率的にスキャンできます。定期的なスキャンは、ガベージコレクションを実現し、無効なチャンク上のチャンクのレプリカを再作成し、チャンクの移動を実行してチャンクサーバー間の負荷とディスクスペースの負荷を均等化します。

すべてがメモリに存在することの問題は、システム全体のチャンクの容量がマスターのメモリ制限を受けることです。実際には、64MB のチャンクのメタデータは通常 64 バイト未満であり、ほとんどのファイルのチャンクは満杯であり、最後のチャンクを除いて多くの断片化したチャンクはありません。同時に、ファイル名前空間のメタデータも通常 64 バイト未満であり、ファイル名はプレフィックス圧縮を使用して非常にコンパクトに保存されています。最後に、実際により大きなファイルシステムをサポートする必要がある場合は、マスターのメモリを単純に増やすだけで済みます。

チャンク位置#

マスターはどのチャンクサーバーがどのチャンクのレプリカを持っているかの永続的な記録を保存せず、起動時にすべてのチャンクサーバーをポーリングし、マスターはこれらの情報が最新であることを保証できます。なぜなら、マスターはすべてのチャンクの位置の配置を制御し、ハートビートを介してすべてのチャンクサーバーの状態を監視するからです。

起動時のクエリにより、マスターとチャンクサーバー間の同期問題による多くの問題を排除できます。たとえば、チャンクサーバーがクラスターに参加したり、クラスターから離れたり、名前を変更したり、再起動したり、クラッシュしたりすることがあります。比較的大きなクラスターでは、これらのことが頻繁に発生します。もう一方の側面では、チャンクサーバー上の多くのエラーがチャンクを無効にする可能性があり（たとえば、ディスク障害による使用不可）、チャンクサーバー自身だけが有効なチャンクを実際に保存しているかどうかを知っているため、マスターにこの情報を保存することは意味がありません。

操作ログ#

操作ログには、重要なメタデータの変更履歴が含まれており、メタデータの唯一の永続化情報でもあり、すべての並行操作に論理的なタイムライン順序を提供します。すべてのチャンクの作成とバージョン番号の変更時に、論理的な時間がマークされます。操作ログの重要性により、十分に信頼性のあるストレージを保証する必要があり、永続化が完了する前にクライアントには見えません。操作ログはリモートマシンにレプリカが作成され、ローカルとリモートのディスクの両方でフラッシュされてからクライアントに返されます。

マスターは操作ログを再生して回復し、マスターの起動時間を最小限に抑えるために、ログはできるだけ小さくする必要があります。ログの量が一定のサイズに達すると、マスターは現在の完全な状態のチェックポイントを作成し、次回の起動時には最後のチェックポイントからログを再生するだけで済みます。チェックポイント自体はコンパクトな B ツリー構造で、メモリに直接マッピングでき、名前空間のクエリを追加の解析なしで実行できます。

チェックポイントの作成には一定の時間が必要ですが、マスター内部の状態は構造化されており、新しいチェックポイントの作成は現在の変更操作をブロックすることはありません。チェックポイントを作成する際は、別のスレッドで新しいログファイルに切り替え、作成されたチェックポイントには以前のすべての変更が含まれます。百万レベルのファイルシステムのチェックポイントは 1 分以内に作成でき、作成が完了した後にローカルおよびリモートのディスクに書き込まれて初めて成功と見なされます。マスターが回復する際は、最後の完全な有効なチェックポイント以降の操作ログを再生するだけで済み、より早いチェックポイントは直接削除できます。チェックポイントの作成中の失敗は正確性に影響を与えず、回復時に不完全なチェックポイントを検査してスキップします。

一貫性モデル#

GFS は比較的緩やかな一貫性モデルを使用していますが、GFS の実装を比較的単純かつ効率的に保証することができます。GFS の保証は次のとおりです：名前空間の変更（ミューテーション）（ファイルの作成など）は原子性を持ち、マスターノードは名前空間に対して排他ロックを追加して操作を実行し、マスターノードの操作ログは変更のグローバルな順序を定義できます。

ファイル領域（ファイル領域はストレージデバイス上のファイルのバイト範囲を指します）のデータ変更後の状態は、データ変更のタイプに依存します：成功 / 失敗、並行変更の有無。

ファイル領域は、ストレージデバイス上のファイルのバイト範囲を指します。すべてのクライアントがどのレプリカからでも常に同じデータを読み取ることができる場合、このファイル領域は一貫しています。ファイルデータが変更された後、一貫性を保ちながら、すべてのクライアントが変更書き込みの完全な内容を見ることができる場合、この領域は定義されている（この言葉は翻訳が難しいですが、このファイル領域の内容がクライアントによって確定できることを理解できます）。

• 書き込み失敗：結果は当然不一致です。
• 非並行（順次）書き込み成功：結果は確実に定義されており、対応するファイル領域の内容はクライアントが書き込んだ内容です。
• 並行書き込み成功後：ファイル領域は一貫していますが、対応するファイル領域に書き込まれた内容は複数の書き込み断片が混在している可能性があるため、未定義です。
• 順次 / 並行追加成功：追加は原子性を持つため、最終的に成功した領域のファイル内容は確定しており、定義されていますが、その前に成功または失敗した書き込みや埋め込みデータが存在する可能性があります。

データ変更は書き込みまたは追加である可能性があります：書き込みはクライアントがオフセットを指定する必要があり、追加はクライアントがファイルの末尾と見なす位置をオフセットとして書き込みます。追加操作は少なくとも 1 回原子性を持って実行され、並行変更が存在しても、追加を実行する際の最終的なオフセットは GFS によって選択され、最終的に書き込み成功に使用されるオフセットがクライアントに返され、この追加レコードを含む定義されたファイル領域の起点としてマークされます（前に成功または失敗した書き込みがあったかもしれません）。

GFS は埋め込みや重複追加レコードを挿入する可能性があり、この領域は不一致と見なされます。一連の変更の後、最終的なファイルは一定の範囲内で定義されており、最後の変更書き込みのデータを含むことが保証されます。

GFS は、すべてのレプリカに変更を順次適用することによってアーカイブを行い、その後、チャンクバージョン番号を使用してすべての古いレプリカをチェックします。これらのレプリカは、チャンクサーバーのダウンによって変更が失われた可能性があります。古いレプリカは、以降のすべての変更に参加せず、クライアントがマスターにリクエストする際にクライアントに返されることはありません。できるだけ早くガベージコレクションされます。クライアントがチャンクの位置情報をキャッシュしているため、このキャッシュが更新される前に、クライアントは古いレプリカからデータを読み取る可能性があります。この時間ウィンドウは、キャッシュユニットのタイムアウト時間と次回ファイルがオープンされる時間によって制限されます。ほとんどのファイルは追加専用であるため、古いレプリカは最新のデータに対してファイルの終了位置が早いだけです。最新のデータを読み取る必要があるクライアントは読み取りに失敗し、再試行時にマスターにチャンク情報を再リクエストします。この時点で、最新のチャンク位置情報を即座に取得できます。

変更が成功してから長い時間が経過した後、コンポーネントの故障もデータの損傷や喪失を引き起こす可能性があります。GFS は、すべてのチャンクサーバーとのハンドシェイクリクエストを通じて、チェックサムを確認し、データの損傷を検出し、チャンクサーバーを無効としてマークします。エラーが発見されると、データは他の有効なレプリカから迅速に再コピーされる可能性があります。チャンクは、GFS が反応する前にすべてのレプリカが無効になった場合にのみ不可逆的に失われる可能性があります。通常、この時間は数分です。この場合、クライアントにはデータが利用できないと返され、損傷ではありません。

GFS を使用するアプリケーションは、この緩やかな一貫性に適応するために、できるだけ追加書き込みを使用し、ランダム書き込みではなく、書き込み位置に基づいてファイルを定義し、定期的に書き込みが完了したチェックポイントを設定し、アプリケーション層のチェックサムを含めるべきです。その後、チェックポイント以前のデータのみを読み取り、チェックサムを確認します。一貫性の問題や並行性の問題に関して、これによりうまく対処できます。書き込みエラーが発生した場合、アプリケーションは自分が記録したチェックポイントの後で再度増分書き込みを行うことができます。アプリケーションはチェックサムに基づいて埋め込みデータや断片記録を破棄することができます。アプリケーションは各レコードに一意の ID を追加して重複レコードを識別することもできます。

システムインタラクション#

リースと変更順序#

変更はデータまたはメタデータを変更する操作であり、各変更はチャンクのすべてのレプリカに適用されます。GFS はリースメカニズムを使用してすべてのレプリカ間の変更の一貫性を維持します。変更を実行する前に、GFS はチャンクのすべてのレプリカから 1 つを選択してリースを付与します。このレプリカはプライマリと呼ばれ、プライマリはこのチャンクで変更操作を実行するための直列順序を決定します。他のすべてのレプリカは、チャンクの変更操作を実行する際にこの順序に従います。

これにより、システム全体のグローバルな変更順序は、マスターがリースを付与する順序と各プライマリの変更実行順序によって決定されます。リースメカニズムは、マスターノード上の管理オーバーヘッドを最小限に抑えるために設計されています。リースには初期の 60 秒のタイムアウトがあり、チャンクの変更が完了するたびにプライマリはタイムアウトを延長できます。マスターは、特定の状況下でリースを取り消すことがあります。たとえば、マスターがすでに名前が変更されたファイル上の変更を無効にしたい場合、マスターとプライマリの通信が失われた場合、タイムアウトメカニズムを介して新しいリースを再付与できます。

クライアントが変更を実行するプロセスは次のとおりです：

1. クライアントは指定されたチャンクのリースを保持しているチャンクサーバーと他のレプリカの位置情報をマスターにリクエストします。現在リースがない場合、マスターは 1 つのレプリカを選択してリースを付与します。
2. マスターはすべてのレプリカの位置情報を返し、どれがプライマリであるかを示します。その後、クライアントはこれらの情報をキャッシュして後で使用します。クライアントはプライマリと通信できない場合やプライマリがもはやリースを保持していない場合にのみ、再度マスターノードにリクエストします。
3. クライアントは任意の順序でデータをすべてのレプリカにプッシュします。各チャンクサーバーはデータを内部の LRU バッファキャッシュに保存し、データが使用されるか期限切れになるまで保持します。データフローと制御フローを分離することで、ネットワークトポロジーに基づいてデータフローをスケジュールし、パフォーマンスを向上させることができます。
4. すべてのレプリカがデータを受信したことを確認した後、クライアントはプライマリに書き込みリクエストを送信し、以前にすべてのレプリカにプッシュしたデータを示します。プライマリは受信したすべての変更に連続したシーケンス番号を割り当て、その後、シーケンス番号に従ってすべての変更をローカルの状態に適用します。
5. プライマリは書き込みリクエストをすべてのセカンダリに転送し、セカンダリはプライマリが割り当てたシーケンス番号の順序に従ってすべての変更を実行します。
6. すべてのセカンダリがプライマリに応答し、操作が完了したことを示します。
7. 任意のセカンダリで失敗が発生した場合（すなわち、すべてのセカンダリで成功しなかった場合）、プライマリは対応する失敗のエラーをクライアントに返します。変更されたファイル領域は現在不一致の状態になり、クライアントは失敗した変更を再試行し、ステップ 3 からステップ 7 を繰り返します。

非常に大きな書き込みやチャンクをまたぐ書き込みがある場合、GFS のクライアントコードはそれを複数の書き込み操作に分割し、上記のプロセスに従って書き込みを行います。しかし、複数のクライアントが並行して実行する場合、交互に実行されることで上書きが発生し、共有ファイルの末尾には複数のクライアントの書き込み断片が含まれることになります。この場合、すべてのレプリカが同じ順序で実行されるため、ファイル領域は一貫していますが、ファイルの状態は未定義であり、どちらが先でどちらが後かは不明です。

データフロー#

制御フローとデータフローを分離することで、ネットワーク伝送をより効率的にするため、制御フローはクライアントからプライマリへ、次に他のセカンダリへと進み、データフローはパイプライン方式で慎重に選択されたチャンクサーバーのチェーンに沿って線形にプッシュされます。目的は、各マシンの帯域幅を最大限に活用し、すべてのデータをプッシュする遅延を最小限に抑えることです。各マシンのすべての出口帯域幅は、できるだけ早くデータを伝送するために使用され、複数の受信者のためにデータを分割することはありません。

ネットワークボトルネックや高遅延リンクをできるだけ回避するために、各マシンはネットワークトポロジー上で最も近い、まだデータを受信していないマシンを選択してデータを転送します。GFS 内部のネットワークトポロジーは非常にシンプルで、IP アドレスを使用して距離を正確に推定できます。GFS は内部でパイプラインを使用してデータを伝送し、遅延を低減します。チャンクサーバーがデータの受信を開始すると、すぐに転送を開始します。

原子性レコード追加#

GFS は原子性のある追加操作を提供し、これを record append と呼びます。一般的な書き込みとは異なり、record append は書き込み位置を指定しません。GFS はこのデータを原子性を持ってファイルの末尾に少なくとも 1 回追加することを保証し、オフセットをクライアントに返します。これは Unix の O_APPEND モードに似ており、ファイルへの並行書き込みではデータ競合が発生しません。通常の書き込みでこの効果を達成するには、分散ロックが必要です。

record append は変更操作の一種であり、同じ制御フローに従いますが、プライマリ上では少し異なります。クライアントは追加データをファイル末尾の最後のチャンクのすべてのレプリカにプッシュし、その後リクエストをプライマリに送信します。プライマリは、現在のチャンクに追加レコードを追加した後に最大サイズ（64MB）を超えるかどうかを確認します。

• 超えた場合、プライマリはまず現在のチャンクを最大サイズまで埋め、すべてのセカンダリに同じ操作を実行するように指示し、その後クライアントにこの操作を次のチャンクで再試行するように返します（record append のサイズは、比較的極端な断片化の状況を避けるために 1/4 のチャンクサイズに制限されています）。
• 超えない場合、プライマリはローカルのレプリカに追加レコードを追加し、オフセットをすべてのセカンダリに送信してデータを書き込み、最終的にクライアントに応答を返します。

record append がいずれかのレプリカで追加に失敗した場合、クライアントはこの操作を再試行します。最終的に同一チャンクの異なるレプリカは異なるデータを含む可能性があり、同じレコードのすべてまたは一部の重複を含むことがあります。

GFS はすべてのレプリカがバイトレベルで完全に同じであることを保証せず、データが少なくとも 1 回原子性を持って書き込まれることを保証します。書き込みが成功した操作に対して、データは必ずチャンクのすべてのレプリカに同じオフセットで書き込まれ、すべてのレプリカの長さは追加データの長さと同じかそれ以上になります。後続の追加はより高いオフセットのみを持ちます。以前の一貫性の定義に従って、record append 操作が成功した後、ファイル領域は定義されていると見なされ、当然一貫性も持ちます。

スナップショット#

スナップショット操作は、ファイルまたはディレクトリツリーのコピーをほぼ即座に作成し、進行中の変更や中断を最小限に抑えます。

GFS は copy-on-write 技術を使用してスナップショットを実現します。マスターがスナップショットリクエストを受け取ると、まず関連ファイルのチャンクのすべての未完了のリースを取り消し、これらのチャンクへの後続の書き込みがマスターから新しいリースの保持者を取得する必要があることを保証します。これにより、マスターはその前にチャンクのコピーを作成する機会を得ます。

リースが取り消されたり期限切れになった後、マスターはスナップショット操作ログをローカルディスクに書き込み、メモリ状態を変更し、元のファイル / ディレクトリツリーのメタデータのコピーを作成します。

新しく作成されたスナップショットファイルは、スナップショット操作が完了した後も元のファイルのチャンクを指し続けます。クライアントがチャンクに内容を書き込もうとすると、マスターに現在のリースの保持者をリクエストします。この時、マスターは対応するチャンクの参照カウントが 1 より大きいことを確認し、クライアントへの応答を遅延させ、まず新しいチャンクハンドルを選択し、チャンク C のレプリカを持つすべてのチャンクサーバーに新しいチャンクを作成するように通知します。各チャンクサーバーはネットワークを介さずにローカルでファイルをコピーします（GFS システム内のディスク速度はネットワークの 3 倍であり、ここで比較されるのはファイルの読み取り速度です）。その後、マスターは新しいチャンクに新しいリースを付与し、クライアントに返します。以降はコピーされたチャンクに通常通り書き込むことができます。

マスター操作#

マスターはすべての名前空間関連の操作を実行し、システム内のすべてのチャンクのレプリカを管理し、新しいチャンクとそのレプリカをどこに作成するかを決定し、さまざまなシステムレベルの活動を調整し、すべてのチャンクのバックアップが完全であることを保証し、チャンクサーバーの負荷をバランスさせ、未使用のストレージを回収します。

名前空間管理とロック#

マスター上の多くの操作は非常に時間がかかります。単一の時間のかかる操作が他の操作に影響を与えないように、GFS は複数の操作を同時に実行することを許可し、名前空間の特定の領域にロックをかけて正しい直列化を保証します。

従来のファイルシステムとは異なり、GFS ではディレクトリ自体に単独のデータ構造がなく（従来のファイルシステムにおけるディレクトリ内のファイルなどに相当）、ファイル / ディレクトリのエイリアス（ソフト / ハードリンク）もサポートしていません。論理的には、ファイルの完全な名前からメタデータ情報へのマッピングを含む 1 つのテーブルしか存在せず、プレフィックス圧縮を利用してこのテーブルをメモリ内で効率的に表現できます。

名前空間内の各ノード（ファイル名またはディレクトリ名の絶対パス）には関連する読み取り / 書き込みロックがあり、マスターは各操作を実行する前にこれらのロックの集合を取得する必要があります。たとえば、ある操作が /d1/d2/.../dn/leaf に関連している場合、/d1、/d1/d2、...、/d1/d2/.../dn の読み取りロックと /d1/d2/.../dn/leaf の読み取りロックまたは書き込みロック（対応する操作の必要に応じて）を取得する必要があります。ここで、パス上の葉ノードは異なる操作の中でファイルである場合もあれば、ディレクトリである場合もあります。

シナリオを考えてみましょう：/home/user が /save/user にスナップショットされる過程で /home/user/foo が作成されると、最初にスナップショット操作は /home と /save の読み取りロック、/home/user と /save/user の書き込みロックを取得します。一方、/home/user/foo の作成には /home と /home/user の読み取りロック、/home/user/foo の書き込みロックが必要です。この 2 つの操作は /home/user でロックの競合を引き起こします。ファイル作成操作は /home/user で書き込みロックを取得する必要はありません。なぜなら、GFS の「ディレクトリ」には変更する必要のある情報がないため、ディレクトリに読み取りロックをかけるだけで、削除 / 名前変更やスナップショットの状況を回避できます。

このロックモデルは、同じディレクトリ内での並行変更操作をうまくサポートできます。たとえば、同じディレクトリ内で複数のファイルを並行して作成することができます。名前空間内には多くのノードが存在できるため、読み取り / 書き込みロックオブジェクトは遅延的に作成され、使用されなくなったらすぐに削除されます。

デッドロックを避けるために、すべてのロックは一貫した順序で取得されます：まず名前空間内の階層に従って順序付けされ、次に同じ階層内で辞書順に順序付けされます。

レプリカ位置#

GFS クラスターには数百のチャンクサーバーがあり、これらのチャンクサーバーは同じまたは異なるラックにある数百のクライアントからアクセスされます。異なるラックのマシン間の通信は、1 つまたは複数のスイッチを越える必要があります。また、ラック自体の入出力帯域幅は、ラック内のすべてのマシンの帯域幅の合計よりも小さい場合があります。

レプリカの選択戦略は、データの信頼性と可用性を最大化し、ネットワーク帯域幅の利用を最大化することを目的としています。

レプリカをすべてのマシンに分散させることで、ディスクやマシンの故障を回避し、各マシンのネットワーク帯域幅を最大限に活用できますが、異なるラックにも分散させる必要があります。これにより、全ラックが利用できなくなった場合（共有リソースの故障 / スイッチ / 電源の故障など）でも、チャンクには利用可能なレプリカが残ります（可用性を保証）。さらに、チャンクの読み取りは複数のラックの合計帯域幅を利用できますが、一方でデータの書き込みは複数のラック間で転送される必要があり、これはトレードオフのポイントです。

レプリカの作成、再作成（コピー）およびバランス#

チャンクレプリカは、次の 3 つの状況で作成されます：チャンクの作成、再レプリケーション、再バランス。

マスターがチャンクを作成する際、レプリカの保存位置を選択します。主に考慮される要素は次のとおりです：

1. ディスク利用率が平均値よりも低いチャンクサーバーに保存することで、長期間にわたってすべてのチャンクサーバーのディスク利用率が相対的に均等になります。
2. 各チャンクサーバー上で最近作成されたレプリカの数を制限します。一般的にファイルが作成された後は大きな書き込みトラフィックが発生するため、この状況でのネットワークの混雑を避ける必要があります。
3. できるだけ異なるラックのチャンクサーバーにチャンクを分散させます。

チャンクの利用可能なレプリカの数がユーザーが指定した目標を下回る場合、たとえばチャンクサーバーが利用できない場合やディスク障害によってレプリカが損傷した場合、またはユーザーが指定したレプリカの数を増やした場合、マスターはできるだけ早く再レプリケーションを行います。

再レプリケーションが必要な各チャンクは、次の条件に基づいて優先順位が付けられます：

1. レプリケーションの目標までの距離、たとえば 2 つのレプリカを失ったチャンクは 1 つのレプリカを失ったチャンクよりも優先度が高くなります。
2. 最近削除される予定のファイルよりも、現在生存しているファイルを優先してレプリケーションします。
3. 障害が実行中のアプリケーションに与える影響を最小限に抑えるため、クライアントリクエストをブロックしているチャンクの優先度が上がります。

マスターは優先度が最も高いチャンクを選択し、指定されたチャンクサーバーに指示を出して、現在存在する有効なレプリカからデータをコピーします。新しいレプリカの位置の選択ルールは、チャンク作成時の選択ルールと一致します。

レプリカのコピー中にトラフィックがクライアントのトラフィックを圧倒しないように、マスターはクラスター内および各チャンクサーバー上で実行されるコピーの数を制限します。さらに、各チャンクサーバーは、ソースチャンクサーバーへのリクエストを制限することで、レプリカコピーの帯域幅の使用を制限します。

マスターは定期的にレプリカの再バランスを行います。マスターは現在のレプリカの分布状況を確認し、レプリカをより適切なディスクスペースに移動させて負荷を均等化します。新しいレプリカの位置の選択戦略は同様であり、新しいレプリカが作成された後、レプリカの数が増えたため、マスターは現在存在するレプリカの中から削除する必要があります。一般的には、平均値よりも空きスペースが少ないチャンクサーバーを選択してディスクスペースの使用を均等化します。

ガベージコレクション#

ファイルが削除された後、GFS はその占有する物理スペースを即座に回収せず、通常の GC 期間中にファイルとチャンクレベルの回収を行います。この方法により、システム全体がよりシンプルで信頼性のあるものになります。

アプリケーションがファイルを削除すると、マスターは即座に削除ログを記録し、それを削除時間を含む隠しファイルに名前を変更します。マスターがファイルシステムを定期的にスキャンする際、3 日以上存在する隠しファイルを削除します。削除前に、隠しファイルはその特殊なファイル名を介してアクセス可能であり、通常のファイル名に名前を変更することで削除のロールバックを実現できます。

隠しファイルが名前空間から削除されると、そのメモリ内のメタデータも同時に消去され、これによりチャンクとの接続が切断されます。通常のチャンク名前空間スキャン中に、マスターは孤児チャンク（すなわち、どのファイルからもアクセスできないチャンク）をマークし、これらのチャンクのメタデータを消去します。マスターとチャンクサーバー間の通信のハートビートメッセージの中で、チャンクサーバーは自分が持つチャンクのサブセットを報告し、マスターは応答の中でマスターにメタデータがないチャンクをマークし、チャンクサーバーはいつでもそのレプリカを削除できます。

この GC 方式の利点：

1. 大規模な分散システムでは、この実装方法は非常にシンプルで信頼性が高く、各チャンクの作成は特定のチャンクサーバーで失敗する可能性があり、レプリカ削除のメッセージが失われる可能性がありますが、マスターはこれらの失敗したレプリカを再試行したり記憶したりする必要はありません。
2. すべてのストレージスペースの回収はバックグラウンドで段階的に行われ、マスターが比較的空いている時期に行われます。通常、マスターはより迅速に緊急のクライアントリクエストに応答できます。
3. スペースの遅延回収は、意図しない不可逆的な削除を防ぐことができます。

遅延削除の主な欠点は、ストレージが不足しているときにユーザーのスペース調整作業を妨げることです（たとえば、一部のファイルを削除したい場合）。アプリケーションが一時ファイルを繰り返し作成して削除しても、ストレージを直接再利用することはできません。解決策は、削除されたファイルが再度削除された場合、システム内部で対応するストレージの回収プロセスを加速し、アプリケーションが異なる名前空間で異なるレプリカと回収戦略を使用できるようにすることです。たとえば、ユーザーは特定のディレクトリツリー内のすべてのチャンクがレプリカを必要とせず、ファイル削除が即座に実行されるように指定できます。ファイルシステム上で不可逆的に削除されます。

古いレプリカのチェック#

レプリカはチャンクサーバーのダウンにより古くなったり、変更が失われたりする可能性があります。マスターは各チャンクのバージョン番号を維持して最新のレプリカと古いレプリカを区別し、マスターがチャンクにリースを付与する際にそのバージョン番号を増加させ、すべての最新のレプリカに通知します。その後、マスターとこれらのレプリカは新しいバージョン番号を永続化します。これらのステップは、クライアントがチャンクに書き込む前に発生します。

現在利用できないレプリカがある場合、そのチャンクバージョンは遅れます。チャンクサーバーが再起動すると、マスターはそのサーバーが古いレプリカを持っていることを検出し、対応する古いチャンクと最新のバージョン番号を通知します。マスターが現在の記録よりも高いチャンクバージョンを検出した場合、それはリース付与の失敗過程で発生したものと見なされ（リースの失敗では書き込みは発生しません）、この高いチャンクバージョンを現在のバージョンに変更できます。

マスターは通常の GC 期間中に古いレプリカを削除し、クライアントにチャンク関連情報を返す際には古いレプリカを無視します。別の保証として、マスターがクライアントにどのチャンクサーバーがリースを保持しているかを通知したり、チャンクサーバーに別のチャンクサーバーからデータをコピーするよう指示したりする際には、チャンクバージョンを含めます。そのため、クライアントとチャンクサーバーは操作を実行する際にチャンクバージョンを確認し、最新のデータにアクセスしていることを保証します。

フォールトトレランスと診断#

GFS システム設計の最大の課題の 1 つは、頻繁なコンポーネントの故障に対処することです。コンポーネントの品質と数量により、故障は異常ではなく常態となります：すなわち、マシンやディスクを完全に信頼することはできません。コンポーネントの故障は、システムの利用不可やデータの損傷を引き起こす可能性があります。

高可用性#

GFS クラスターには数百のサービスがあり、その中には任意の時点で利用できないものもあります。GFS は、システムの高可用性を保証するために、迅速な回復とレプリカ（コピー）の 2 つのシンプルで効果的な方法を使用します。

迅速な回復#

マスターとチャンクサーバーは、どのような理由であれ終了しても、数秒以内に状態を回復して起動できるように設計されています。実際、GFS は正常終了と異常終了を区別しません。サーバーが定期的にシャットダウンする際には、プロセスを直接 kill します。クライアントや他のサービスが未完了のリクエストのタイムアウトに達すると、一時的に停止し、再接続して再起動したサービスにリトライします。

チャンクのコピー#

チャンクのコピーについては、すでに多くのことが述べられています。マスターはチャンクサーバーがダウンしたり、レプリカが損傷したりした場合（チェックサムを介して）に clone 操作を使用してコピーします。さらに、GFS はパリティやエラーレートを使用して、ますます増加する読み取り専用ストレージのニーズを満たします。

マスターのコピー#

信頼性を保証するために、マスターの状態もコピーされ、操作ログとチェックポイントは複数のマシンにコピーされます。各状態変更操作は、ログがローカルディスクとすべてのマスターのレプリカにフラッシュされるまで、コミットされたと見なされません。

シンプルさを保証するために、すべての変更操作と GC などのバックグラウンド活動を担当するのは 1 つのマスターだけです。マスターのプロセスが故障した場合、ほぼ瞬時に再起動できます。マスターのマシンやディスクに障害が発生した場合、GFS 以外の監視インフラストラクチャが新しいマスタープロセスを起動し、操作ログのレプリカを使用して処理を続行します。クライアントは、IP や他のマシンの変更に基づいて変更される名前ではなく、gfs-test のような標準名を使用してマスターにアクセスします。

さらに、マスターのレプリカであるシャドウマスターもファイルシステムへの読み取り専用アクセスを提供できます。プライマリマスターがダウンしている場合でも、シャドウマスターはプライマリに対してわずかに遅れることがあります。あまり頻繁に変更されないファイルや、リアルタイム性の要求が比較的弱い場合、この方法は読み取りの可用性を向上させます。実際、ファイル内容はチャンクサーバーから読み取られ、アプリケーションはファイル内容が古いかどうかを認識しません。ディレクトリ内容や権限制御情報などのメタデータのみが、非常に短い時間ウィンドウ内で期限切れになります。

各シャドウマスターは、読み取りと操作ログのレプリカ上の増分操作を実行し、プライマリと同様に順序に従って実行し、自身のメモリ状態を変更します。プライマリマスターと同様に、シャドウマスターは起動時にすべてのチャンクサーバーをポーリングしてすべてのチャンクレプリカの情報を特定し、その後、頻繁なハンドシェイクメッセージの交換を通じて彼らの状態を監視します。これに加えて、レプリカの作成や削除など、プライマリが行った決定によって引き起こされるレプリカ位置の更新のみがプライマリマスターに依存します。

データの完全性#

各チャンクサーバーは、チェックサムを使用してデータが損傷していないかを確認します。GFS クラスターは、数百台のマシンに分散した数千のディスクを持つ可能性があり、読み取りまたは書き込み時にデータが損傷したり失われたりすることが非常に一般的です。この場合、他のチャンクレプリカを使用して回復できます。異なるチャンクサーバー上のレプリカを比較してデータの損傷を確認することはあまり現実的ではありません。さらに、atomic record append のような操作では、すべてのレプリカが完全に一致することを保証できませんが、これらのレプリカも合法です。そのため、各チャンクサーバーはチェックサムを維持してデータの完全性を独立して検証する必要があります。

各チャンクは 64KB のブロックに分割され、各ブロックには 32 ビットのチェックサムがあります。このチェックサムはメモリに保存され、ユーザーデータとは分離してログに永続化されます。読み取りリクエストの場合、クライアントまたはチャンクサーバーにデータを返す前に、チャンクサーバーは読み取り範囲内のブロックのチェックサムを検証します。チェックサムが失敗した場合、チャンクサーバーは損傷したデータを送信せず、リクエスト者にエラーを返し、マスターにエラーを報告します。リクエスト者は他のレプリカからデータを再リクエストし、マスターはレプリカの再作成を実行します（この時、有効なレプリカの数が不足しています）、その後、チェックサムエラーのチャンクサーバーにそのレプリカを削除するよう通知します。

チェックサムの計算は読み取り性能にほとんど影響を与えません。なぜなら、ほとんどの読み取りリクエストの範囲は非常に少数のブロックに過ぎないため、関連するごく少数の追加データがチェックサムに必要であり、GFS のクライアントコードはできるだけブロックサイズに合わせて読み取りを調整し、この部分のオーバーヘッドを減らします。さらに、チェックサムの検索と検証自体には I/O オーバーヘッドはなく、チェックサムの計算は通常 I/O 操作と重複できます（ファイルを読み取る際にチェックサムを計算します）。

チャンクの追加書き込み操作におけるチェックサム計算は高度に最適化されており、この作業は負荷の中で主導的な役割を果たします。最後の不完全なブロックを増分更新し、その後追加書き込みの新しいブロックに対して新しいチェックサムを計算します。たとえ最後の不完全なブロックのデータが損傷していても、現在は検出できませんが、新しいチェックサムがデータと一致しなくなり、次回このデータブロックを読み取るときに検出できます。

対照的に、書き込み操作がチャンク内の既存の範囲を上書きする場合、最初から最後までのブロックを読み取ってチェックサムを計算し、その後書き込み操作を実行し、最後に新しいチェックサムを計算して記録する必要があります。

空いている時間に、チャンクサーバーは非アクティブなチャンクのデータをスキャンしてチェックします。一度損傷が検出されると、マスターは新しいレプリカを作成し、損傷したレプリカを削除します。これにより、マスターが知らない間に非アクティブなチャンクが静かに損傷し、有効なレプリカが不足することを防ぎます。

診断ツール#

詳細で詳細な診断ログは、問題の隔離、デバッグ、パフォーマンス分析において計り知れない助けを提供します。GFS サービスは多くの診断ログを生成し、重要なイベント（たとえば、チャンクサーバーのオンラインまたはオフライン）やすべての RPC リクエストと応答を含みます。これらのログはいつでも削除可能ですが、ストレージスペースが許す限り、できるだけ長く保持するようにしています。

RPC ログには、通信ライン上で送信された正確なリクエストと応答が含まれており、リクエストと応答のログを照合し、異なるマシンでの記録を照合することで、問題を診断するための全体的なインタラクションの履歴を再構築できます。ログは負荷テストの追跡やパフォーマンス分析にも使用できます。

ログがパフォーマンスに与える影響は非常に小さく、これらのログは順次かつ非同期的に書き込まれます。最近のイベントの大部分もメモリ内に保存され、継続的なオンライン監視に使用されます。

経験#

ビジネスシステムは常に厳密で制御可能ですが、ユーザーはそうではないため、ユーザー間の相互干渉を防ぐためにより多くのインフラストラクチャが必要です。

私たちの多くの問題はディスクと Linux に関連しています。多くのディスクはドライバが一連の IDE プロトコルをサポートしていると主張しますが、実際には最近のバージョンにのみ信頼性を持って応答します。プロトコルは複数のバージョン間で非常に似ているため、大部分のケースではドライバは正常に動作しますが、時折発生するエラーがドライバとカーネルの状態の不一致を引き起こし、データが徐々に損傷することになります。これが私たちがチェックサムを使用する動機でもあり、これらのプロトコルのエラーを修正するためにカーネルも変更しました。

初期の Linux2.2 カーネルを使用していたときに、fsync の遅延がファイル全体のサイズに比例することがわかりました。これは大量の操作ログにとって問題であり、特にチェックポイントを実装する前に問題が発生しました。最初は同期書き込みを使用してこの問題に対処し、その後 Linux2.4 に移行しました。

もう 1 つの Linux の問題は、単一（グローバル）読み取り / 書き込みロックです。アドレス空間内の任意のスレッドがディスクをメモリに読み込む（読み取りロック）か、mmap でマッピングされたメモリアドレスを変更する（書き込みロック）には、このロックを取得する必要があります。システムの負荷が非常に低い場合でも、短時間のタイムアウトが発生することがわかりました。その後、リソースボトルネックや間欠的なハードウェア障害を調査した結果、単一（グローバル）ロックがネットワークのメインスレッドをブロックし、新しいデータをメモリにマッピングできなくなっていることがわかりました。ディスクスレッドが以前にマッピングされたメモリを読み込んでいるためです。私たちは主にネットワークインターフェースの帯域幅の制限を受けており、メモリコピーの帯域幅ではないため、mmap を pread に置き換えることでこの問題を解決しました。

結論#

GFS は私たちのストレージニーズを成功裏にサポートし、Google 内で検索およびビジネスデータ処理のストレージプラットフォームとして広く使用されています。