GFS

パフォーマンス (Performance) のために、データを多数のサーバーに分割して並行してデータを読み取ることを実現する、これがシャーディング (Sharding) です。
成功と失敗を繰り返すマシンでは常にエラーが発生するため、フォールトトレランス (Fault Tolerance) が必要です。
フォールトトレランスを実現する最も簡単な方法はレプリケーション (Replication) であり、1 つが故障した場合は別のものに切り替えます。
レプリケーションを使用すると、注意が足りないとそれらの間で不一致が生じる可能性があります。データに問題が発生する可能性があるため、不一致の問題 (Inconsistency) が生じます。
一貫性 (Consistency) を実現するためには、一貫性を保証するために追加のインタラクションが必要であり、そのコストは低パフォーマンス (Low Perf) となりますが、これは私たちの最初の希望とは一致しません。

{{< block type="tip">}}
したがって、強い一貫性は低パフォーマンスを意味します。
{{< /block >}}

設計目標#

GFS は多数のコンピュータ上に構築されているため、これらのコンピュータは避けられない故障が発生します。したがって、チェック、フォールトトレランス、および迅速な障害からの回復が必要です。
大きなファイル（例えば数 GB のファイル）を主にサポートし、小さなファイルもサポートしますが、特別な最適化は行いません。
ワークロードは主に 2 種類の読み取りから構成されます：大きなストリーミング読み取りと小さなランダム読み取りです。パフォーマンスに特別な配慮がなされているアプリケーションは通常、バッチ処理を行い、読み取る内容をソートします。これにより、読み取りは常に単方向の順次読み取りとなり、データを逆に読み取る必要がなくなります。
- 大きなストリーミング読み取りでは、単一の操作で通常数百 k、場合によっては 1m またはそれ以上のデータを読み取ります。同じクライアントに対しては、通常、連続して読み取り操作を行い、1 つのファイルを順次読み取ります。
- 小さなランダム読み取りは通常、任意のオフセット位置で数 kB のデータを読み取ります。小規模なランダム読み取りは通常、ファイルの異なる位置で数 kB のデータを読み取ります。
GFS 内のファイルは通常、書き込みが完了すると再度修正されることはほとんどないため、主に大きなストリーミング読み取りを対象とし、任意の位置での小規模な書き込み操作もサポートします。
GFS は、複数のクライアントが同じファイルに並行して追加することを非常に効率的かつ明確な意味でサポートする必要があります。つまり、原子操作です。通常、複数のクライアントが同じファイルに対して並行して追加操作を行います。
高性能で安定した帯域幅のネットワークは、低遅延よりも重要です。私たちのほとんどのターゲットアプリケーションは非常に高速なバッチ処理データを重視しており、単一の読み書き操作に対して厳格な応答時間の要求を持つ人はほとんどいません。

アーキテクチャ#

単一のマスター、複数のチャンクサーバー（具体的なファイルを保存）、複数のクライアント。
各ファイルは一定のサイズ（64MB）のチャンクに分割され、各チャンクには一意の 64 ビットの識別子（チャンクハンドル）が付与されます。
各チャンクは異なるチャンクサーバーにバックアップが保存されます（デフォルトは 3 つ）、ユーザーは異なるレプリケーションレベルを指定できます。
マスターはメタデータ（metadata）を管理します。例えば、ファイルとチャンクのマッピング関係、チャンクの位置情報などです。
マスターはチャンクの分割、孤立したチャンクのガベージコレクションメカニズム、チャンクサーバー間のミラー管理などを管理します。
各チャンクサーバーはマスターとの間にハートビートメカニズムを持ち、検出プロセス中に指示を発出し、状態を収集します。

GFS マスターのメタデータ#

filename -> chunk ids(chunk handles) NV
チャンクハンドルとチャンクデータの対応関係
- チャンクが保存されているサーバー（チャンクサーバーリスト）
- チャンクのバージョン番号 NV
- チャンクのプライマリチャンクサーバー、書き込み操作が行われる場所
- プライマリチャンクサーバーのリース期限

これらのデータテーブルはすべてマスターのメモリ内に保存され、フォールトトレランス（例えば、再起動後にデータが失われないように）を確保するために、ディスク上にログを保存します。読み取りはメモリから行い、書き込み時にはメモリとディスクの両方に書き込みます。
データが変更されるたびに、ディスク上のログに追加され、定期的に（ログが特定のサイズを超えた場合）チェックポイント（スナップショットのようなもの）を作成します（最初から読み取る必要はありません）。

GFS 読み取り手順#

最初の読み取りリクエストは、クライアントがファイル名と読み取りたい位置（オフセット）を持っていることを示し、マスターに送信します。
マスターはリクエストを受け取ると、ファイル名から対応するチャンクハンドルを取得します。各チャンクのサイズは固定されているため、具体的な開始チャンクハンドルが得られます。
次に、チャンクハンドルに基づいて、データを保存しているチャンクサーバーのリストを見つけてクライアントに返します。
クライアントは、読み取りを行うためにサーバーを選択できます（論文では、最近のサーバーを選択すると述べられています。Google 内では IP が連続しているため、IP で近さを判断できます）。クライアントは毎回 1MB または 64KB のデータを読み取るため、チャンクとチャンクサーバーの関係をキャッシュし、毎回リクエストを行う必要はありません。
チャンクサーバーはリクエストを受け取ると、チャンクハンドルに基づいて（チャンクはチャンクハンドルに基づいて命名されていると推測されます）対応するチャンクとオフセットに対応するデータをクライアントに提供します。

q1: 読み取るデータがチャンクを越えた場合はどうしますか？#

例えば、クライアントが読み取ろうとしているデータが 64MB を超える場合、または単に 2 バイトだけでチャンクを越える場合、クライアントはリクエストを送信する際にこのリクエストが境界を越えていることに気づきます。したがって、1 つのリクエストを 2 つのリクエストに分割してマスターに送信します。したがって、ここでマスターに 2 回の読み取りリクエストを送信する可能性があります。その後、異なるチャンクサーバーからデータを読み取ります。

複数のレプリカ間の変更順序の一貫性#

1 つのチャンクに対して

マスターは、このチャンクを持つサーバーに 60 秒のリースを付与し、プライマリと呼びます。
プライマリはすべての変更操作を順序付け（シリアル順序）し、他のセカンダリはこの順序に従って変更を行います。
このチャンクが変更されている限り、プライマリはマスターにリースの延長を申請できます。

GFS 書き込み手順#

クライアントはマスターにリクエストを送信してチャンクサーバーリスト（プライマリ、セカンダリ）を取得します。プライマリがない場合、マスターはセカンダリの 1 つをプライマリとして選択します。
クライアントはチャンクサーバーリストを取得した後、それをキャッシュします。プライマリが応答しないかリースが期限切れになるまで再リクエストは行いません。
クライアントはすべてのレプリカにデータをプッシュし、クライアントはプッシュの順序を保証しません。各チャンクサーバーは、データが使用されるか期限切れになるまで内部の LUR キャッシュにデータを保存します。
すべてのレプリカがデータを受け取った後、クライアントはプライマリに書き込みリクエストを送信します。これは、以前に各レプリカにプッシュされたデータを示します。プライマリはこれらの書き込みを一定の順序に整理して自分のローカルに適用します。
プライマリはこの適用順序を各セカンダリに転送します。
セカンダリはこの順序を適用して変更を完了し、プライマリに応答します。
プライマリはクライアントに応答し、エラーが発生した場合はクライアントにも応答します。エラーが発生した場合、書き込みリクエストはプライマリとセカンダリの両方で成功する可能性があります（プライマリが直接失敗した場合、シリアル順序をセカンダリに転送しません）。クライアントはこのリクエストが失敗したと見なし、リトライを通じて処理します（3-7 は数回再書き込みを試みます）。

GFS 原子レコード追加#

{{<block type="tip" title="同じ領域への並行書き込みは非シリアライズ可能です">}}
この領域には最終的に複数のクライアントのデータセグメントが含まれる可能性があります。
{{< /block >}}

原子的な追加操作。recored appendは、指定されたオフセット（GFS が選択する、ここでは失敗する可能性があるため、いくつかのチャンクサーバーにこのデータが存在する可能性があります）に少なくとも 1 回追加され、クライアントにそのオフセットを返します。これはO_APPENDに似ており、原子性を保証します。recored appendは GFS 書き込み手順のプロセスに従いますが、いくつかの特別な点があります：

クライアントがすべてのデータをプッシュした後、プライマリはそのチャンクに追加した後、単一のチャンクのサイズを超えているかどうかを確認します。
超えている場合、現在のチャンクが最大オフセットに達した時点で（セカンダリも保存する必要があります）、クライアントに応答し、この操作は次のチャンクで再試行する必要があることを指摘します（レコードのサイズは単一のチャンクの最大値の 4 分の 1 に制御する必要があり、フラグメンテーションが受け入れられるレベルに保たれます）。
最大サイズを超えない場合は、通常の方法で保存します。

期限切れレプリカの検出#

チャンクサーバーが故障してダウンするか、いくつかの更新リクエストを失った場合、それは期限切れになる可能性があります。各チャンクに対して、マスターは最新のレプリカと期限切れのレプリカを識別するためにバージョン番号を維持します。

マスターがチャンクのプライマリサーバーに権限を付与またはリースを更新する際に、バージョン番号が増加し、すべてのレプリカに更新を通知します。

データが一致している場合、マスターとすべてのレプリカのバージョン番号は一致します（クライアントが書き込みリクエストを送信する前に保証できます）。

チャンクサーバーが再起動するか、バージョン番号を報告する際、マスターはそれが期限切れのレプリカを含んでいるかどうかを確認します。もしマスターがバージョン番号が記録よりも大きいことを発見した場合、マスターはより高いバージョン番号を使用して更新します。

マスターは定期的なガベージコレクションを通じて期限切れのレプリカを削除します。削除する前に、すべてのクライアントのチャンク情報リクエストの応答にこの期限切れのレプリカが含まれていないことを確認します。

クライアントはマスターからチャンクサーバーリストを取得する際にバージョン番号を取得するため、比較を行い、最新のレプリカを選択して操作を行うことができます。

まとめ#

これは、適切なマルチレプリカ、マルチアクティブ、高可用性、障害自己修復の分散システムではありません。