負荷を計測するにつれ、伝統的な分散ファイルシステムとはかなり異なるデザインになった
今と将来の予測に基づくアプリケーションの負荷と技術的環境によって、ファイルシステムのデザインは変わっていった。
- コンポーネントの障害は例外ではなく通常
- 巨大なファイル。数Gbが普通。全データでTbあるデータを数Kb単位で１０億管理するのは難しい
- 書き込みは追記。ランダム書き込みはしない。
- アプリケーションとファイルシステムAPIを一緒にデザインすることで、柔軟性やシンプルさを得る
複数のクラスター 大きい物は１０００台のノードで300Tb １００台のクライアントアクセス
仮定
- 常に障害の可能性をもつコモディティーハードウェア
- 適度な数の巨大なファイル。100Mbぐらいのファイル数百万。数Gbは普通。
- 負荷は主に２つのRead：大きなストリームReadと小さなランダムRead。
- 負荷は大きなシーケンシャルWriteもある。一度書いたファイルはほとんど変更されない。
- 並列に同じファイルに追記書き込みを行う複数のクライアントのよく定義されたセマンティックスを効率よく実装。ファイルは多様な方法でマージ可能なproduce-consumerキューとして使われる。数百のproducerをさばける。最小の同期オーバーヘッドのアトミック性が重要。consumerはファイルを後で読むか、同時に読み込む。
- 高い帯域は低いレイテンシよりも重要。我々のアプリケーションはデータをバルクで処理する
- create
- delete
- open
- close
- read
- write
- snapshot
- record append (アトミック性を保ちながら複数のクライアントが同じファイルに追記する操作。multi-way mergeやproduce-consumerキューを実装するときに使う)
１つのmasterと複数のchunkserverから成る。
ファイルは固定長のchunkに分割される。chunkはイミュータブルでグローバルに一意な64bitのchunk handleで識別される。ChunkserverはchunkをLinuxファイルとしてローカルのディスクに保存し、chunk handleとbyte rangeを与えられて読み書きする。chunkは複数のchunkserverにレプリケートされる。
masterはすべてのファイルシステムのメタデータを管理する。たとえばnamespace, access control, mapping from files to chunks, current location of chunksを管理する。 chunk lease management, 迷子chunkのガーベッジコレクション、chunkserver間のchunkのマイグレーションなどシステムワイドなアクティビティも管理する。masterはchunkserverと定期的にHeartBeatメッセージを送って命令を送ったり状態を収集したりする。
クライアントはメタデータ操作はmasterとやりとりするが、データは直接chunkserverとやりとりする。POSIX APIは実装していないのでLinuxのvnodeレイヤーはフックする必要がない。
クライアントもchunkserverもファイルデータをキャッシュしない。クライアントやシステムのキャッシュを実装しないことによって、キャッシュのコヒーレンス問題を考える必要がなく単純化できる（ただしクライアントはメタデータをキャッシュしている）。chunkはローカルのファイルとして保存されており、アクセス頻度の高いものはLinuxのバッファーキャッシュでメモリーに保持されるので、chunkserverはキャッシュを実装する必要はない。
single master をもつことはchunkの配置やレプリケーションの決定を単純にする。しかしボトルネックにならないようreadとwriteへの関与を最小化しなければならない。クライアントはmasterからファイルを読み書きしない。その代わりクライアントはどのchunkserverとコンタクトをとるか尋ねる。クライアントは情報を一定期間キャッシュし直接chunkserverを操作する。
Figure 1を説明する。クライアントは固定長のchunkサイズを使い、ファイル名とバイトオフセットをファイルのchunkインデックスに変換する。次にmasterにファイル名とchunk indexを含んだリクエストを送る。masterはchunk handleとレプリカの場所を返す。クライアントはこの情報をキャッシュしファイル名とインデックスをキーにする。クライアントは（最も近いだろう）レプリカの１つにリクエストを送る。リクエストはchunk handleとchunk中のbyte範囲を指定する。同一のchunkの後続の読み込みはキャッシュが切れるかファイルが再度openにならないかぎりmasterとのやりとりは必要ない。実際にはクライアントはおなじリクエストで複数のchunkを要求するから、masterは後続のchunkの情報を含めて返す。この追加情報は将来のmasterとのやりとりのコストを下げる。
- ブロックサイズは64 Mb。通常のファイルシステムよりはるかに大きい
メリット
- clientのmasterとのインタラクションを減らせる。最初にchunkの位置を尋ねるだけでよい。シーケンシャル書き込みのときは特に効果がある。ランダム読み込みのときでも数Tbアクセスするために必要なchunkの位置はすべてclientのキャッシュにおさまる
- クライアントは取得した大きなデータの処理にしばらくかかるので、永続コネクションを開放できる
- masterサーバーのメタデータのサイズを抑えることができる。これによりすべてのメタデータがmasterサーバーのメモリにおさまる
デメリット
- 数chunkしかない小さなファイルを保存してしまうとホットスポットになる。Googleではこのような使い方はしない。ただしバッチジョブの実行ファイルを保存して多くのサーバーが読み込んだ時にこの問題はおきた。問題を回避するためにreplication factorを上げる必要があった
masterサーバーは３つのメタデータを保持する
- ファイルとchunkの名前空間
- ファイルからchunkへのマッピング
- chunkのレプリカの場所
名前空間とファイルからchunkへのマッピングへの変更はディスクにoperation log として永続化される。これによってmasterがクラッシュしても不整合な状態にならない。
masterはchunkの場所を永続化しない。その代わり起動時やchunkserverがクラスターに参加したときにchunkserevrに尋ねる。
メタデータはmasterのメモリーにあるため、masterの操作は高速。
定期スキャンも高速
- chunk garbage collection
- chunkserver障害時のre-replication
- リバランスのためのchunkのマイグレーション
メタデータはmasterのメモリーにあるため、クラスターのキャパシティはmasterのメモリー量に制限される
しかし大した制限ではない
- 64Mb chunkにつき64byteのメタデータ
- ファイルの名前空間はファイルにつき64byte以下
masterはどのchunkserverがchunkをもっているかという情報を永続化しない。それは起動時にchunkserverから取得する。その後はmasterがchunkの場所を決定できる、かつchunkserverのHeartBeatを監視しているので、状態を完全に同期できる。
永続化しないことによって、chunkserverがクラスターに参加したり去ったり名前が変更されたり障害が起きたり再起動した時に、masterが状態を同期するさいの問題を消しされる。数百台のノードがあるとこれらは頻繁におきる。
masterではなくchunkserverが自身のディスク上のchunkの情報に責任をもつことにより、chunkserevrのディスク障害時やオペレーターが名前を変更したときにmasterの状態をなんとか整合性をもって同期する必要がない。
operation logはmasterのmetaデータの変更履歴となる。masterの唯一の永続データであるとともに、変更操作の順番を決定する。ファイルとchunkとそのバージョンは論理時間でユニークに識別できる。
operation logは非常に重要で、失うとクライアントの操作やファイルシステム全体を消失する。そのためlogをレプリケートしてローカルとリモートのディスクにフラッシュしてからクライアントにレスポンスを返す。
masterはファイルシステムの状態はoperation logをリプレイすることで復旧する。復旧を迅速にするため、logのサイズが大きくなると最新のcheckpointを読み込みその後のlogのみをリプレイすればいいようにする。
ファイルの名前空間の変更（e.g. ファイルの作成）はアトミック。masterしかこの操作を行わない。
変更後のファイル領域の状態は
- 変更の種類
- 成功か失敗か
- 並列か
に依存する
変更後のファイル領域の状態の定義
- consistent: すべてのクライアントがどのレプリカを見ても同じデータを観測する
- defined: consistentかつクライアントがすべての変更内容を観測すること
変更後のファイル領域の状態のシナリオ
- 並列書き込みが起きなかった場合：defined
- 並列書き込みが起きた場合：undefined but consistent。すべてのクライアントは同じデータを観測するが、その変更を反映しているものではないかもしれない。たいてい複数の変更が混在した結果となる。
- 変更が失敗した場合：incnsistent (hence also undefined)。異なるクライアントは異なる結果を観測する
データ変更の種類
- write：データをアプリケーションが指定したoffsetに書き込む
- record append：GFSが選んだoffsetにatomically at least onceに書き込む
一連の成功した変更のあとに、ファイル領域はdefinedであり最後の変更を含んでいることが保証される。 GFSはこれを以下の方法で実現している
- すべてのレプリカでchunkへの変更を同じ順番で行う
- chunkserverがダウンしている間変更が適用されず遅れたレプリカを判定するために、chunkのバージョン番号を使う
遅れたレプリカは変更されずゴミとして回収される。
クライアントはchunkの場所をキャッシュしているため、キャッシュをリフレッシュする前に遅れたレプリカからchunkを読んでしまうことがある。この間隔はキャッシュのタイムアウトと次のファイルopenに制限される。ほとんどのファイルは追記のみなので、遅れたレプリカは古いデータではなくchunkの早まった終了位置を返す。クライアントがリトライすればmasterから最新のchunkの場所を取得できる。
変更が成功しても障害がデータを壊すことはもちろんある。GFSは障害が起きたchunkserverをmasterとすべてのchunkserverとのハンドシェイクで特定し、チェックサムで破損を検知する。 破損したデータは正常なレプリカから直ちに修復される。GFSが反応するまでに（だいたい数分以内）すべてのレプリカが失われた時のみ、chunkが不可逆的に失われる。このとき利用不可能になるが、破損にはならない。クライアントは破損したデータではなくエラーを受け取る。
GFSはシンプルな技術でのゆるい整合性を受け入れている。
- 上書きではなく追記
- checkpointing
- self-validating
- self-identifying
追記は効率がよく耐障害性が高い。 checkpointingではwriterがインクリメンタルに再開でき、readerがまだ書き終わってないデータを処理することを防いでくれる。
レプリカ間の整合性のある変更を行うためにchunkのリースを使う。masterはレプリカの１つにchunkのリースを与える。そのレプリカを primary と呼ぶ。primaryはchunkのすべての変更への順序を選ぶ。なのでグローバルな変更順序はmasterに選ばれたリース貸与順序と、リースの中ではprimaryが与えた順番によって定義される。
masterがprimaryとの通信を失っても、古いリースが期限切れになったら他のレプリカが リースを得る。
Figure 2で書き込みのプロセスを示す。
- クライアントはどのchunkserverがchunkのリースをもっていて、他のレプリカがどこにいるのか聞く
- masterはprimaryとsecondaryレプリカの場所を返す。クライアントはそれをキャッシュする。
- クライアントはすべてのレプリカにデータをプッシュする。順番は問わない。各chunkserverはLRUバッファーキャッシュに書き込む。
- すべてのレプリカがデータを受け取りAckを返したら、クライアントはwriteリクエストをprimaryに送る。primaryは（他のクライアントのものも含め）受け取ったすべての変更操作に順番をつける。その順番で変更を適用し内部状態を変える。
- primaryはwriteリクエストをすべてのsecondaryレプリカにフォワードする。secondaryはprimaryが決めた順番どおりに変更を適用する。
- secondaryは変更が完了したらprimaryに通知する
- primaryはクライアントにレスポンスを返す。レプリカでおきたエラーはクライアントに報告される。このときsecondaryで書き込みが失敗しているかもしれないが、primaryでは成功している。なぜならprimaryで失敗したら順序が決定できずsecondaryにフォワードできないからだ。このときファイル領域はinconsistentとなり、リクエストはエラーとなる。
クライアントの操作は並列に起きるかもしれない。なので共有されたファイル領域はundefinedだが、すべてのレプリカで変更は同じ順番で起きており、結果は同一となるのでconsistentである。
ネットワーク効率のためにコントロールフローとデータフローを分離した。
目標
- 各マシンのネットワーク帯域をフルに使う
- ネットワークのボトルネックを回避する
- データをプッシュするレイテンシを最小化する
各マシンのネットワーク帯域をフルに使うために、データはchunkserverのチェーンに直列にプッシュされる。
ネットワークのボトルネックを回避してレイテンシを最小化するために、各マシンはデータを近いサーバーにフォワードする。ネットワークトポロジ上の距離はIPアドレスから推測する。
レイテンシを最小化するために、chunkserverはデータを受け取るとすぐにフォワードを開始する。
通常のwriteでは、クライアントがデータを書きたいoffsetを指定する。同一領域への並列書き込みは順序付けられていない。なのでファイル領域は複数のデータフラグメントを持つことがある。
appendでは、クライアントはデータのみを指定する。GFSはそれを１つの連続したバイト列としてat least onceにアトミックにファイルに追記する。offsetはGFSが選択し、クライアントに返す。
appendはmutation操作の１つで、primaryでの追加ロジックを伴うほかは3.1で解説したコントロールフローに従う。クライアントはファイルの最後のchunkをすべてのレプリカにプッシュし、それからprimaryにリクエストを送信する。primaryはchunkへのappendがchunkの最大サイズを超えないかチェックする。最大サイズを超える場合、chunkを最大サイズまで埋め、すべてのsecondaryでもそうするよう指示し、クライアントに次のchunkで操作を再開するよう要求する。chunkの最大サイズに収まるなら、primaryはレプリカにデータをappendし、secondaryに正確なoffsetに書き込むよう指示し、最後にクライアントに成功を返す。
もしレプリカで失敗が起きたら、クライアントはリトライする。この結果レプリカ間の同一のchunkは重複により異なるデータとなる可能性がある。GFSはすべてのレプリカがバイトレベルで同一であることを保証しない。データがアトミックでat least onceに書き込まれることを保証するだけだ。この特徴はクライアントが成功を帰す場合データはすべてのレプリカで同じoffsetに書かれるという制約に従う。整合性の保証という観点からは、appendが成功した領域はdefined(hence consistent)で、間にある領域はinconsistent(hence undefined)になる。私達のアプリケーションは2.7.2で説明したように不整合に対処できる。
スナップショットは現在起きている変更を阻害せずファイルやディレクトリツリーのコピーをほぼ瞬時に作れる。
AFSのように、スナップショットの実装にcopy-on-writeを使っている。
masterがスナップショットのリクエストを受け取ると、スナップショット対象のファイルのchunkのリースを無効にする。つまりその後そのchunkへの書き込みはリース所有者を探すためmasterに問い合わせることになる。これによってmasterは他の操作よりも先にchunkのコピーを作る機会を得る。
リースを無効にしたら、masterはスナップショット操作をlogとしてディスクに書き込む。そしてそのログからメモリー上のファイルのメタデータを複製する。このスナップショットファイルは元のファイルと同じchunkを指している。
クライアントがスナップショット後のchunkに最初に書き込むとき、masterにリースの所有者を尋ねる。masterはレスポンスを返すのを遅延させ、代わりに新しいchunk handleを選択する。masterはchunkのレプリカであるchnkserverに複製chunkを作るよう指示する。元のchunkと同じchunkserverに新しいchunkを作ることで、データはネットワークを介さずローカルにコピーできる。masterは新しいchunkのリースをレプリカの１つに与え、クライアントに返す。クライアントはそれが複製されたchunkだとは知らずに通常通りchunkに書き込む。
masterのオペレーションには時間がかかるものもあるので、複数のオペレーションを可能にして、適切に順序化するためにnamespaceに対してロックを用いる。
伝統的なファイルシステムとは違い、GFSはディレクトリの中にファイルがあるような構造を持っていない。ファイルやディレクトリのエイリアスもない。GFSはnamespaceをフルパスからメタデータへのルックアップテーブルとして表現している。namespaceの各ノード（絶対パスで指定されるファイル名やディレクトリ名）はread-writeロックと関連付けられている。
各masterのオペレーションは、それを行う前にロックを獲得する。例えば/d1/d2/.../dn/leafを操作したければ/d1, /d1/d2, ..., /d1/d2/.../dnディレクトリのreadロックをとり、/d1/d2/.../dn/leafのreadロックまたがwriteロックをとる。
この仕組の良い所は同じディレクトリの並列操作が可能なことだ。例えば複数ファイルの作成は同じディレクトリで並列に行える。そのディレクトリ名のreadロックとファイル名のwriteロックを取れば良い。ディレクトリのreadロックは削除やリネームやスナップショットを防いでくれる。writeロックは同じ名前が２つできないように操作に順番をつける。
chunkserverは複数のラックにまたがっている。chunkserverは同じあるいは異なるラックに存在する数百のクライアントからアクセスされることになる。さらに、ラックの帯域はラック内のマシンの帯域の合計よりも低いかもしれない。マルチレベルでのデータの分散はスケーラビリティ、信頼性、可用性の点でチャレンジである。
chunkのレプリカの配置ポリシーには２つの目的がある。データの信頼性と可用性を最大化することと、ネットワーク帯域の使用率を最大化することである。このためchunkレプリカを複数のラックに配置する必要がある。これによってラック障害があってもchunkを生き残らせ可用性を保つことができる。さらに特にreadで複数のラックの帯域を束ねて利用することができる。逆にwriteも複数のラックにトラフィックが言ってしまうが、選んだトレードオフである。
chunkレプリカは３つの理由で作られる。
- chunkの作成
- 再レプリケーション
- リバランス
masterがchunkを作るとき、どこにレプリカを配置するかの要因は３つある。
- ディスク使用量が平均以下のもの
- chunkサーバーごとに最近作られたレプリカの数を制限している
- 複数ラックへの分散
レプリカの数がユーザーが指定した数値よりも下回った場合、masterは再レプリケーションを行う。 様々な理由で再レプリケーションは起きる。
- chunkserverが利用不可能になった
- レプリカが破損したとchunkserverが報告した
- ディスクの障害
- レプリケーションファクター数が上げられた
再レプリケーションはいくつかの要因で優先度が決まる
- 利用可能なレプリカ数のレプリケーションファクターからの差
- ライブなファイル
- クライアントの進行を妨げているchunk
データの複製不可を抑えるために、masterはクラスターレベルとchunkserverレベルで同時複製回数を制限している。
masterは定期的にレプリカをリバランスする。masterはレプリカの分布を調べ、ディスク容量や負荷が少ない方へレプリカを動かす。masterはレプリカの除去も行う。除去するレプリカは平均以下のディスク容量のものを優先的に選択する。
ファイルが削除されたとき、GFSはすぐに物理ストレージから削除しない。それはファイルレベルとchunkレベルのガーベッジコレクションで行う。
ファイルが削除されると、他の変更と同じようにmasterはログに書き込む。すぐに削除する代わりに、ファイルは削除時のタイムスタンプつきの隠しファイル名にリネームされる。masterの通常のファイルシステムの名前空間のスキャン時に隠しファイルを削除する。隠しファイルが名前空間から削除されると、メモリー上のメタデータも削除される。
chunkの名前空間のスキャン時にmasterは迷子chunkを特定し、それのメタデータを削除する。HeartBeatメッセージで、chunkserverはそれが持っているchunkの一部を報告し、masterはそのchunkがmasterのメタデータに存在しないことを返答する。chunkserverはそのchunkをいつでも削除することができる。
プログラミング言語の文脈では分散ガーベッジコレクションは非常に難しい問題だが、我々のものは非常にシンプルだ。
ガーベッジコレクションは即時削除よりも以下の様なメリットがある
- chunkの作成はすべてのchunkserverで成功するとは限らない。これによりmasterが知らないレプリカができる。レプリカの削除メッセージはロストする可能性がある。masterはそれを再送する義務がある。ガーベッジコレクションは一貫してかつ信頼できる方法で不要なレプリカを削除できる。
- 名前空間のスキャンやchunkserverとのハンドシェイクなど、masterのバックグラウンド処理とともに一緒に実行できる。まとめて処理することでコストが低くなる。
- masterが忙しくないときにだけ実行できる
- 不慮の削除のときのセーフティーネットとなる
chunkserverがダウンしている間変更を逃した時、chunkレプリカのデータは古くなる。古いデータかどうか判断するために、各chunkに対してmasterはchunk version numberを管理している。
masterがchunkのリースを認めるたびに、chunkのバージョンを上げて、最新のレプリカに通知する。他のレプリカが利用不可能になっているときは、chunkのバージョン番号は上がらない。chunkserverが再起動してもっているchunkの集合とそのバージョンを報告してきたときに、masterはそのchunkが古いかどうか判定する。そのchunkよりも大きなバージョンを知っていた場合、ダウンしていたと判断して最新に更新する。
masterがガーベッジコレクションで古いレプリカを削除する。それまではその古いレプリカは存在しないものとしてclientへのレスポンスを返す。さらなるセーフガードとして、masterはクライアントやchunkserverにどのchunkserverがchunkのリースをもっているか教えるときにchunkバージョンも教える。クライアントやchunkserverはバージョンを確認して最新のデータかどうかチェックする。
最も難しいことの１つはコンポーネントの障害に対処することだ。コンポーネントの質と量の両方がこれらの問題を例外ではなく日常にしてしまう。それらの問題が回避不可能な状況で出会った挑戦とそれに対処するために作ったシステムの問題診断ツールを議論する。
速い復旧とレプリケーションという、２つのシンプルで効果的な戦略で高可用性を実現する。
masterとchunkserverをどのように停止したとしても、数秒で状態を復元できるようにしている。実際には、通常停止と異常停止を区別してはいない。サーバーはプロセスをkillすることで日常的に停止する。
各chunkはラックをまたがる複数のchunkserverにレプリケーションされている。デフォルトのレプリケーションレベルは３である。
レプリケーションは非常によいが、read-onlyのストレージが増えるにつれてparityやerasure codeなど他のクロスサーバー冗長性を模索している。私たちはそれは難しいが実装可能だと思っている。なぜなら私達のシステムはランダム書き込みは少ししかなく、appendと読み込みがほとんどな、とても疎結合なシステムだからだ。
masterの状態は可用性のためにレプリケーションされる。オペレーションログとチェックポイントは複数のマシンにレプリケーションされる。状態の操作はmasterとすべてのmasterレプリカにログをディスクにフラッシュしたあとにコミットしたとみなされる。簡単のためにただ１つのmasterがすべての操作に責任を持つ。
masterに障害が起きた時、ほぼ一瞬で再起動される。マシンやディスクの障害の時はGFS外のモニタリングシステムが新しいmasterプロセスを開始する。クライアントはmasterの完全修飾名のみを使う。それはDNSエイリアスになっており、masterが再配置されたら接続先が変わる。
shadowサーバーはプライマリmasterがダウンしていても読み込み専用のアクセスを可能にする。shadowはプライマリとラグがある点でミラーではない。データはchunkserverにあるので、shadowを使っても古いデータを読むことはない。古いのはメタデータで、つまりディレクトリの内容やアクセスコントロールの情報などである。
shadowはプライマリと同様起動時にchunkserverをポールする。
各chunkserverはデータの破損がないかchecksumを計算する。GFSは数千ものディスクを数百のマシン上で稼働させるので、データの破損は起きうる（７章で原因の１つをみる）。レプリカを使って破損から復旧も可能だが、現実的でない。さらに、レプリカの発散は想定された挙動である。特にアトミックなappendはレプリカの同一性を保証しない。なので各chunkserverは独立にchecksumを計算してデータの一貫性を保たなければならない。