###### tags: `memo` `systems`
# Google File System (GFS)
Paper URL: http://web.mit.edu/6.033/www/papers/gfs-sosp2003.pdf

## GFS?
- 分散ファイルシステム
- 安価な部品を使って構築されたシステム上で動作する

## Assumption
- ファイルサイズは 100MB 以上、ファイル数は数百万を想定
- read/write 特性
- read: シーケンシャルリード (1回数KB~) がメイン
- write: 追記がメイン
- 複数のマシンから同時に同じファイルに追記することも考慮

## Architecture
<small>※論文より引用</small>

大きく分けて構成要素は
1. GFS client
2. GFS master
3. GFS chunk server

ファイルは 64 MB のチャンクに分けられ、 GFS chunkserver に保存され、ファイルの名前空間とチャンクの対応など、メタデータ類は GFS master に保存される

### GFS master
- ファイルのメタデータ類を保存
- 定期的に GFS chunkserver にハートビートメッセージを送る
- GFS client とはメタデータのやりとりのみをする

### GFS chunkserver
- 複数個ある
- 可用性を高めるため
- チャンクは自動で 3 つ以上の GFS chunkserver に複製される
- 64 MB サイズに分割されたファイルを保存
- GFS client とは実データの read/write のやりとりをする

## Metadata
3 種類のメタデータがある。すべて in-memory で保持しているが、1. と 2. への変更は Operation Log が取られる

1. 名前空間
2. ファイルとチャンクのマッピング
3. チャンクのレプリカの場所

Operation Log が一定サイズを超えると B-tree like な形でチェックポイントが生成される。チェックポイントはそのままメモリ上に展開可能で余計のパースは必要ないとのこと

## Consistency Model
<small>※論文より引用</small>

- consistent / inconsisntent
- どのレプリカから読んでも同じ内容の場合 consistent であり、そうじゃなければ inconsistent
- defined / undefined
- 書き込んだデータが consistent で、チャンクに反映されていれば defined であり、チャンクに反映されないことがあれば undefined
- 書き込みに失敗すると inconsistent になる
- 追記の場合、成功しても部分的に inconsistent になることも…

## Write Control and Data Flow
<small>※論文より引用</small>

大まかに 3 つのフェーズがある

1. GFS chunkserver の場所特定（step 1, 2）
2. 書き込むデータのプッシュ (step 3)
3. 書き込みの実行 (step 4 ~ step 7)

なお、書き込むデータのプッシュは 1 台の GFS chunkserver にのみ実行すればよく、他の GFS chunkserver への転送は勝手にやってくれる

## Atomic Record Appends
- GFS は追記操作(record append)が少なくとも 1 回は実行され、それが atomic であることを保証する
- すべての GFS chunkserver でレプリカが同一であること（一貫性）は保証しない
- GFS は追記操作時、一部のレプリカで失敗が発生するとリトライを実行する
- このとき 1 回目に追加が成功していたレプリカでは、同じデータが 2 回追加されることになる
- なので、一貫性は保証できない

## Fault Tolerance and Diagnosis
### 高可用性
2 つの戦略がある

1. fast recovery
- どういう終了の仕方をした場合でも、GFS master と GFS chunkserver はどちらも数秒で再起動可能
- 実のところ終了操作はプロセスを殺すだけなので、異常時も通常時も対処は同じ
3. replication
- GFS chunkserver: 前述の通り、チャンクは複数のサーバにレプリケーションされる
- GFS master: operation log とチェックポイントは複数マシン上にレプリケーションされる
- 実は master は複数存在するが、client は DNS を通してアクセスするので、1 つに見える

### データ整合性
- チェックサムによるデータ整合性のチェックを実行する
- チャンクは 64KB ごとに 32bit のチェックサムが取られる

### 診断ツール
- GFS は診断ログを生成する
- 重大なイベント
- すべての RPC ログ
- ログは負荷テストやパフォーマンス解析に使われる

## その他の参考文献
- https://www.slideshare.net/romain_jacotin/the-google-file-system-gfs
- https://www.slideshare.net/suma_/the-google-file-system-42351946
- http://dev.ariel-networks.com/column/tech/google_file_system/