* 参照した論文
+ http://labs.google.com/papers/gfs-sosp2003.pdf

* 特徴
+ 安いPC(OSはGNU/Linux)で分散ファイルシステムを構築しています(*注1)。
+ PCは壊れるという前提で設計しています(*注2)。このため、分散システムを構成するノードが壊れた時、データが失われないことと、自動で復旧できることに主眼を置いています。
+ ファイルシステムを利用する側(アプリ)に、ある程度の想定を求めています。任意の利用ケースに対してそこそこのパフォーマンスを出す(=平均的に良い性能)のではなく、特定の利用ケースで性能を発揮できるように設計しています。
+ 性能を発揮できる利用ケースは次のようなケースです。
++ 主にサイズの大きいファイルを扱う(*注3)。
++ ファイルへの書き込みは追記(append)が多い(ファイルの一部分を何度も書き換えるような利用ではない)。
++ 書き込みより読み込みの方が多い。


* この文書での用語
ス トレージ: GFSはGNU/Linuxのファイルシステム上に構築された分散ファイルシステムです。以下、「ストレージ」と呼んだ場合は、GNU/Linuxのファ イルシステムを意味しています(ファイルシステムであることはGFSの本質では無いので、ストレージがRDBであっても本質は変わりません)。


* インターフェース(API)
+ POSIX互換では無いですが、一般的なファイル操作APIを提供しているようです。要は、gfs_open()やgfs_read()などのAPIです(API名は想像です)。
+ ファイルの指定は、ツリーベースのファイルパスです。つまり、/usr/bin/emacsなどのファイルパスで一意に識別します。言うまでも無く、ファイルの実体は分散したPCのディスクにばらまかれています。
+ 特別な書き込みインターフェースとして、record-appendがあります。次のような事情のためです。GFSのファイルを書き込むクライアントは複 数存在しえます。つまり、ひとつのクライアントがwriteを連続して行っても、他のクライアントに割り込まれて、意図通りの書き込みにならないことがあ ります。record-appendはある単位で書き込みが割り込まれないことを保証したAPIです(GFSはこのrecord-appendの効率に最 適化されています)
+ snapshotと呼ばれるAPIを提供しています。ディレクトリツリーの一部分を高速にコピーできる機能です。詳細は後述しますが、実際のファイルコピーを遅延することで、巨大ツリーのコピーであっても高速に実行できます。
+ リンク機構(ハードリンク、シンボリックリンク)はありません。


* 概要
+ 構成ノードは、マスターノード、チャンクサーバ、クライアントの3種類です。
+ 単一のマスターノードが、ファイルのディレクトリツリーの状態管理、ロック管理、チャンク(下記参照)の位置管理を担います。
+ 複数のチャンクサーバがマスターノードの下にぶら下がります。各ファイルは固定長のチャンクに分割されて、チャンクサーバのストレージに保存されます。各チャンクは、複数のチャンクサーバに複製されます(レプリケーション)。
+ クライアントは、GFSを利用するアプリと、それにリンクされるライブラリです。ライブラリはネットワークRPCを隠蔽したAPIを提供します。アプリ側 の視点で見ると、APIを通じてGFS上にファイルを作ったり、読み書きしたりします(*注4)。GFS側の視点で見ると、アプリにリンクされたライブラ リが、マスターやチャンクサーバとGFS通信プロトコルで話をします。
+ チャンク(ファイルのコンテンツの断片)自体の転送は、クライアントとチャンクサーバの間で直接行われます(マスターは転送に介在しません。マスターは、クライアントにチャンクサーバの位置を教えるだけです)。


* チャンク
+ GFS上に保存されたファイルは、固定サイズ(64MByte)に分割されて保存されます。この分割された断片をチャンクと呼びます。
+ 各チャンクは、GFS上でユニークかつ変化しない(immutable)ID(=64bitのchunk handle)で識別されます。
+ chunk handleの割り当てはマスターが一元的に行います(*注5)。
+ 1チャンクは、複製を持つ各チャンクサーバのファイルシステム上の1ファイルになります。chunk handleからローカルファイルパスへのマップは、各チャンクサーバが管理します。
+ 各チャンクは、複数のチャンクサーバ上に複製され同期されます。チャンクの複製数のデフォルトは3です。
+ チャンクはversionを持ちます。これは履歴管理のためではなく(GFSに履歴管理はありません)、チャンクの複製が正しく同期しているかを検出するためです(詳細後述)。


* 構成ノードの概要
** マスター
+ マスターノードはシステムで単一です。
+ マスターの主な役割(保持する状態)は次の6つです。
++ ファイルのディレクトリツリー(要は/usr/bin/emacsなどのファイルパス)の管理
++ ファイルからチャンクへのマップ(ファイルパスからchunk handlesへの対応)
++ チャンクの位置情報管理(チャンクがどのチャンクサーバ上にあるか)
++ ファイルのロック処理
++ ファイルのその他のメタデータ管理(ファイルオーナー、ファイルパーミッション)
++ チャンクサーバの生存確認(HeartBeatメッセージで死んだチャンクサーバを検出)、状態管理(空きディスク容量や負荷)。
+ 上の状態は、すべてオンメモリーに持ちます[GFSのポイント]。
++ ディレクトリツリーの状態は、ストレージに持ちません。ディレクトリツリーへの変更は、すべて操作ログ(operation log)の形でストレージに書き込まれます(シャドウマスターのストレージにも)(*注6)。
++ マスターがクラッシュしてオンメモリの状態が失われた場合、操作ログからディレクトリツリーをオンメモリに復元します(replay the operation log)。一般のファイルシステムであれば、ディレクトリツリーの状態をストレージに残すので、これはGFSの特徴的な点です。
++ 容易に想像できるように、操作ログは非常に巨大化します。巨大化した操作ログから状態を復元するには時間がかかります。このため、ある程度のタイミング で、操作ログにcheckpointを設定して、その時点の状態をストレージに保存します。クラッシュからの復帰は、最後のcheckpointとそれ以 降の操作ログから行います。
++ ファイルからチャンクへのマップも、同様に操作ログで保持します。
++ チャンクの位置情報とチャンクサーバの状態も、ストレージに持ちません。チャンクサーバの状態は、各チャンクサーバが知っていれば良い、という割り切りで す。マスターがクラッシュから復帰すると、各チャンクサーバに状態(どのチャンクを持っているか)を問い合わせます。また、後述するGCのために、マス ターと各チャンクサーバは定期的に、チャンクサーバがどのチャンクを持っているかの情報をやりとりします。
++ 全てをオンメモリに押し込むために、設計上の工夫がいくつかあります(後述)。


** マスターノードの障害対策
+ マスターノードが落ちたことの検出は、GFSの外部モニター機構で行っています。落ちると自動起動します。操作ログからオンメモリに状態を復元します。
+ マスターノードのハードウェア障害の場合は、別のマシンのマスターノードが起動します。切替えはDNSベースです。
+ シャドウマスターが複数存在して、操作ログで状態を同期しています。マスターが落ちている場合でも、read-onlyで稼働して、GFSを存続します。


** マスターノードのディレクトリツリー
+ ディレクトリツリーの内部データの持ち方は、普通のUnixのファイルシステムと違います。普通のUnixのファイルシステムの場合、ディレクトリごとに ファイル一覧を持ちます。つまり、/usr/bin/emacsであれば、/usrディレクトリの1エントリにbinがあり、/usr/binディレクト リの1エントリにemacsがあります。GFSは、ファイルパスからメタデータへの一元的なマップを持ちます。つまり、/usr、/usr/bin、 /usr/bin/emacsそれぞれのファイルパスからメタデータへマップする内部データ構造です(*注7)。
+ このメタデータマップ(ディレクトリツリー)をオンメモリで持つために、ファイルパスのprefix compressionをしてメモリを節約しています。詳細は書いてないのですが、おそらく、「/usrを/a、/binを/b、/emacsを/c」の ような変換テーブルを持たせて、メモリを節約していると思います(*注8)。


* ロック(排他制御)
+ 複数のクライアントが同時に同じファイルに書き込んだり、同名のファイルを作ろうとした時、排他制御が必要です。排他制御は、マスターが一元的にロック管理することで実現しています。
+ 全てのファイルパスは対応するロックオブジェクト(read-write lock)を持ちます。つまり、/d1/d2/.../dn/leafのファイルパスが存在すれば、/d1、/d1/d2、...、/d1/d2/... /dn、/d1/d2/.../dn/leafのそれぞれに、対応するロックが存在します(*注9)。
+ 例えば、/usr/bin/emacsに書き込んでいる間、マスターは、/usrと/usr/binのreadロック、/usr/bin/emacsのwriteロックをロックします(*注10)。


* 書き込みの同期(レプリカ間の同期)
+ あるチャンクに書き込む時、マスターは、そのチャンクのレプリカを持つチャンクサーバの中のひとつを選んでleaseを与えます(*注11)。
+ leaseを与えられたチャンクサーバを「主(primary)レプリカ」と呼び、その他を「副(secondary)レプリカ」と呼びます。
+ 複数のクライアントから同時に同じチャンクに書き込み要求が来た場合、主レプリカがそれらの書き込み要求に順序(serial number)を付け、副レプリカはその順序に従ってチャンクに書き込みます。
+ マスターは各チャンクの最新versionを知っています。チャンクサーバがダウン中に同期の機会を逸しても、マスターが保持する最新versionと比 較することで、同期の機会を逸したことを検出できます(このような同期できていないチャンクをstale replicaと呼びます)。ちなみに、この場合、チャンクサーバはそのチャンクを捨てます。最新versionを持つチャンクサーバを探して同期を試み るような複雑なことはしません。その代わり、チャンクの複製がひとつ失われたことをマスターに通知します。マスターは最新versionのチャンク(これ を持つチャンクサーバをマスターは知っています)の複製を増やして、レプリカ数を保ちます。
+ クライアントはマスターから、チャンクサーバの位置と同時に現在のversionを受け取ります。クライアントがチャンクサーバにアクセスした時、チャンクサーバの持つチャンクのversionを確認して、stale replicaを検出します(エラー扱い)。
+ 各チャンクサーバが独自にチャンクのchecksum(32bit)確認をします。ディスク障害などでチャンクが壊れた場合、そのチャンクはstale replicaです。
+ [issue] クライアントはチャンクサーバの位置をキャッシュするので、stale replicaを読む可能性はゼロではありません。append-onlyで使っていると、あまり問題にはならない、という主張をしています。



* 書き込み時の通信フロー
- [クライアント=>マスター] 主/副レプリカのチャンクサーバの位置を問い合わせます(クライアントはチャンクサーバの位置をキャッシュします)。主レプリカが未定の場合、マスターは主レプリカを決めます(leaseを渡します)。
- [クライアント=>1チャンクサーバ] チャンクサーバのうち、ネットワーク的に最も近い(*注12)チャンクサーバに書き込みデータを送信します。
- [チャンクサーバ=>チャンクサーバ=>...] 書き込みデータはレプリカを持つチャンクサーバ間を転送されます(*注13)。例えば、レプリカを持つチャンクサーバが3台ありA,B,Cとします。ネッ トワーク的にクライアントから近い順にB,A,Cだとすると、書き込みデータは「クライアント=>B=>A=>C」の順に転送されま す。この時、クライアントは(おそらく)3台と、制御メッセージのやりとりはしているはずです。この時点ではまだ、それぞれのチャンクサーバはローカル ディスクのチャンクに書き込みはしません。
- [クライアント=>主レプリカ(のチャンクサーバ)] レプリカを持つ全チャンクサーバが書き込みデータを受信した後、クライアントは主レプリカに書き込み要求を送信します。
- [主レプリカ(のチャンクサーバ)=>副レプリカ(のチャンクサーバ)] 主レプリカは、書き込み要求にシリアル番号を割り振ります。主レプリカは、シリアル番号順にローカルディスクのチャンクに、書き込みデータを反映させま す。ディスクエラーなどで書き込みに失敗した場合、クライアントにエラーを返します。主レプリカは、副レプリカ(達)に書き込み要求(シリアル番号付)を 送信します。各副レプリカは、シリアル番号順にローカルディスクのチャンク(レプリカ)に、書き込みデータを反映します。反映後、主レプリカに応答を返し ます。
- [主レプリカ(のチャンクサーバ=>クライアント] 主レプリカは、全ての副レプリカから応答を受信すると、クライアントに応答を返します。副レプリカのひとつでもエラーが発生すると(レプリカに齟齬が生じ ると)、主レプリカはクライアントにエラーを返します(*注14)。


* 読み込み時の通信フロー
- [クライアント=>マスター] チャンクサーバの位置を問い合わせます(クライアントはチャンクサーバの位置をキャッシュします)。
- [クライアント=>1チャンクサーバ] チャンクサーバに受信要求を投げて、チャンクデータを受け取ります。


* レプリカの配置
+ 次の3つの基準でレプリカを置くチャンクサーバを決定します(*注15)。
-- ディスクの空き容量の多いチャンクサーバ
-- レプリカ作成要求が、ひとつのチャンクサーバに連続し過ぎないこと
-- 主レプリカと物理的に離れていること(同じラックのPCにレプリカが固まっていると、物理的な障害ですべて失われる可能性があります)、
+ チャンクサーバが落ちると、そのチャンクサーバの持つチャンクのレプリカ数が不足します。すぐに新しいレプリカが作られます
+ マスターは、定期的にレプリカの再配置(rebalance)を行います。チャンクサーバの負荷とディスク容量を見て、再配置を決定しているようです(詳細不明)。
+ これらの戦略により、新しいチャンクサーバがクラスタに追加されると、徐々にレプリカの対象となって、新しいディスクが使われていきます。


* 削除ファイルの扱い(GC)
+ ファイルを削除しても、すぐに実体は消しません。削除時は、マスターの(オンメモリの)メタデータに反映(特別な隠れファイル名にrename)するだけなので、高速です。
+ マスター上の定期タスク(別スレッド)が、ディレクトリツリーをスキャンして、削除済みファイルを検出します。削除から3日(長い!)以上経っていれば、 実際の削除処理(GC:Garbage Collection)を行います。3日以内であれば、undeleteが可能です。
+ GCで、マスターが削除ファイルのメタデータをオンメモリから削除します(操作ログも残します)。この時点では、まだチャンクサーバのチャンクの実体は削除しません(*注16)。
+ 各チャンクサーバは定期的に、持っているチャンクの一覧をマスターに提出します。この時、マスターは、削除済みファイルのチャンク(orphaned chunk)があれば、チャンクサーバに伝えます。チャンクサーバは、チャンクの実体を削除します。
+ 課題: 削除をかなり遅延させるアプローチなので、「作ってすぐ消す一時ファイル」大量に作る用途に向いていません。

* snapshot
+ ファイルやディレクトリツリー(の部分)の高速コピーです。
+ snapshotを取った瞬間は、マスターのオンメモリ上でメタデータの複製を行うだけです(*注17)。マスターは、snapshotされたチャンクの 参照カウンタを上げます。クライアントからマスターへ、そのチャンクへの書き込み要求が来た時、マスターは参照カウンターを見て、チャンク自体の複製をし てから(それぞれのチャンクオーナー上で複製)、書き換えます(copy-on-write)。


* リンク(日本語)
+ http://internet.watch.impress.co.jp/cda/event/2004/11/16/5430.html
+ http://blog.melma.com/00078988/20041024144056
+ http://www.moodindigo.org/blog/archives/000200.html
+ http://www.radiumsoftware.com/0404.html#040406
+ http://d.hatena.ne.jp/kazama/20041207　(MapReduceの説明)


* 脚注
注1
安いと言っても、いわゆるPCサーバと呼ばれるレンジのPCでしょう。

注2
"component failures are the norm rather than exception"が前提です。

注3
google のアプリ、例えばサーチエンジンやgmailが直接GFSのAPIを呼んでいるとしたら(ここは不明です。別のAPI層が存在する可能性もあります)、 WebのHTML文書やメールの一文書はGFSのファイルとしては小さすぎます。アプリ層で複数文書を一ファイルにまとめる仕組み(compound document)があるはずです。

注4
アプリのプログラムは、ファイルの実体がどこにあるかを意識する必要はありません。

注5
chunk handleの実装は、単にシリアルナンバーかもしれません(実装は不明です)。

注6
つ まり、ディレクトリツリーをゼロ状態から始めて、/usr/bin/emacsというファイルを作る場合、mkdir("/usr"); mkdir("/usr/bin"); create("/usr/bin/emacs");のような操作ログがストレージに残るイメージです。
操作ログは重要です。マスターのローカルディスクおよびシャドウマスターのディスクに書き込んでflushしているようです(パフォーマンス?)。

注7
このマップの実装方法は不明です。/usrディレクトリの下の一覧取得(lsコマンドをイメージしてください)という操作もGFSは提供しているので、それも可能である必要があります。

注8
prefix compressionにより、1ファイル当たり、ほとんどが100バイト以内に収まっているようです。

注9
ロックオブジェクト自体は、全てがあらかじめ用意してあるわけではなく、使い回しています(スレッドプールのような実装イメージです)。

注10
Unix の通常のファイルシステムのディレクトリのデータの持ち方であれば、/usr/bin/emacsファイルを作成中は/usr/binをwriteロック すべきですが、GFSでは/usr/binはreadロックのみです(/usr/bin/emacsにはwriteロックです)。
ロックの獲得のdeadlockを避ける工夫: 常に決まった順序でロックします。順序は、ファイルツリーのレベル順で、同一レベルの場合はファイル名の辞書順です。

注11
leaseにはタイムアウト値があります。しかし、しょっちゅうleaseのやりとりをするとマスターに負荷がかかるので、一度主レプリカを選ぶと、問題が無い限り任せっぱなしです。

注12
IPアドレスで判定。

注13
この時、BやCは、受信と送信を同時に行います。(ethernet)スイッチ化されたネットワークでは、(ethernet)リンクの帯域を効率的に利用可能です。

注14
かなり大胆な割り切りがあります。エラーが返った時、同期がずれたレプリカの間のロールバック機能をGFSは持ちません。エラーへの対処はアプリの責任です。

注15
このアルゴリズムに凝ってもあまり意味が無いので、おそらくかなり単純なはずです。物理的な距離なんて、単に(物理位置をある程度反映するような)ラック番号をあらかじめチャンクサーバに割り振っているだけでしょう。

注16
この辺は富豪的です。不要なチャンクをすぐ消すために頑張ることはしません。どうせどこからも参照されていないので、しばらく放置しています。

注17
当然、操作ログは残します。それでも、充分に高速です。