グーグルファイルシステム

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

概要#

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

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

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

インターフェース#

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

アーキテクチャ#

GFS アーキテクチャ

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

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

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

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

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

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

チャンクサイズ#

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

単一ファイルのチャンク数が少なくなり、クライアントとマスターの間でチャンクサーバーの位置情報を取得するリクエストが減少します。
クライアントは同じチャンク上で複数の操作を実行でき、持続的な 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 秒のタイムアウトが設定されていますが、チャンクの変更が完了するたびにプライマリはタイムアウトを延長できます。マスターは、特定の状況下でリースを取り消すことがあります。たとえば、マスターがすでに名前が変更されたファイルでの変更を無効にしたい場合、マスターとプライマリの通信が失われた場合、新しいリースを再付与するためにタイムアウトメカニズムを使用できます。

データフローと制御フロー

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

クライアントは指定されたチャンクのリースを保持するチャンクサーバーおよび他のレプリカの位置情報をマスターにリクエストします。現在リースがない場合、マスターはレプリカを選択してリースを付与します。
マスターはすべてのレプリカの位置情報を返し、どれがプライマリであるかを示します。その後、クライアントはこれらの情報をキャッシュして後で使用します。クライアントは、プライマリとの通信ができない場合やプライマリがもはやリースを保持していない場合にのみ、再度マスターノードにリクエストします。
クライアントは任意の順序でデータをすべてのレプリカにプッシュします。各チャンクサーバーは、データが使用されるか期限切れになるまで内部の LRU バッファキャッシュにデータを保存します。データフローと制御フローを分離することで、ネットワークトポロジーに基づいてデータフローをスケジュールし、パフォーマンスを向上させることができます。
すべてのレプリカがデータを受信したことを確認した後、クライアントはプライマリに書き込みリクエストを送信し、以前にすべてのレプリカにプッシュしたデータを示します。プライマリは受信したすべての変更に連続したシーケンス番号を割り当て、その後、シーケンス番号に従ってすべての変更をローカルの状態に適用します。
プライマリは書き込みリクエストをすべてのセカンダリに転送し、セカンダリはプライマリが割り当てたシーケンス番号の順序に従ってすべての変更を実行します。
すべてのセカンダリがプライマリに応答し、操作が完了したことを示します。
いずれかのセカンダリが失敗した場合（すなわち、すべてのセカンダリで成功しなかった場合）、プライマリは対応する失敗のエラーをクライアントに返します。変更されたファイル領域は現在不一致の状態になり、クライアントは失敗した変更を再試行し、手順 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 は、スナップショットを実現するためにコピーオンライト技術を使用します。マスターがスナップショットリクエストを受け取ると、まず関連ファイルのチャンクのすべての未完了のリースを取り消し、これらのチャンクへの後続の書き込みがマスターから新しいリースの保持者を取得する必要があることを保証します。これにより、マスターはその前にチャンクのコピーを作成する機会を持ちます。

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

新しく作成されたスナップショットファイルは、元のファイルのチャンクを指し、スナップショット操作が完了した後、クライアントがチャンクに内容を書き込もうとすると、現在のリースの保持者をマスターにリクエストします。この時、マスターは対応するチャンクの参照カウントが 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 つの状況で作成されます：チャンクの作成、再複製（再レプリケーション）、再バランス。

マスターがチャンクを作成する際には、レプリカの保存位置を選択します。主にいくつかの要因を考慮します：

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

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

再複製が必要な各チャンクは、以下の条件に基づいて優先順位が付けられます：

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

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

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

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

ガベージコレクション#

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

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

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

この GC 方式の利点：

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

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

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

レプリカは、チャンクサーバーがオフラインになることによって古くなったり、変更が失われたりする可能性があります。マスターは各チャンクのバージョン番号を維持して最新のレプリカと古いレプリカを区別します。マスターがチャンクにリースを付与する際、バージョン番号を増加させ、すべての現在の最新レプリカに通知します。その後、チャンクサーバーが再起動する際、マスターは古いレプリカを持っていることを検出し、対応する古いチャンクおよび最新のバージョン番号を通知します。マスターが現在の記録よりも高いチャンクバージョンを検出した場合、これはリース付与の失敗過程で発生したものと見なされ（リース失敗時には書き込みは発生しません）、この高いチャンクバージョンを現在のバージョンに直接変更できます。

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

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

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

高可用性#

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

迅速な回復#

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

チャンクの複製#

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

マスターの複製#

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

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

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

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

データの完全性#

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

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

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

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

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

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

診断ツール#

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

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

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

経験#

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

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

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

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

結論#

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