The Google File System

My Reserches

INDEX †

著者 †

• Google
  • Sanjay Ghemawat
  • Howard Gobioff
  • Shun-Tak Leung

目的、問題 †

• 論文の目的や対象とする問題は何か？

動機、背景 †

• 増え続けるデータ処理に対応できる、ファイルシステムを提供する必要がある。
  • パフォーマンス
  • 信頼性
  • 可用性

貢献 †

• 機器の故障を前提として設計すべき
  • モニタリング、エラー検出、耐障害性、アトミックリカバリを提供
• ファイルのブロックサイズの見直し
• I/Oの特徴を生かした最適化
  • ファイルは上書きより、appendされることのほうが多い。つまり、一度書き込んだファイルはほどんど変化しない
  • appendの最適化を図る
• 有用なAPIを提供

提案手法、アイディア、システム †

DESIGN OVERVIEW †

仮定 †

• 故障しやすい低性能PC上で動かすことを仮定
• 100MB以上のファイルが、数百万保存できるようなシステムを仮定
• 以下に読み込みを２種類に分類
  • Large streaming read
  • Small random read
• 以下に書き込みはほとんどappend
• 多くのクライアントがいると仮定
  • 同じファイル上に多生産者(write)-多消費者(read)モデルを仮定
• 広帯域　＞　低遅延

Interface †

• 標準的なAPIを提供するがPOSIXとは異なる
  • create, delete, open, close, read, writeなど
• その他
  • snapshot：低コストでファイルやディレクトリのコピーを生成する
  • record append：atomicityを保障しながら、同一のファイルに複数のクライアントが同時にappendできる

Architecture †

• Figure1のようにGFSmaster, GFSchunkserver, GFSclientが存在
• ファイルは固定長のchunkに分割される。
  • chunkは64bitのmasterが管理するchunk handleによってユニークに特定できる
• chunk serverは、ローカルにchunkを保存し、chunk handleとbyte-rangeによって読み書きする
  • chunkは他のchunkserver上にその3つのレプリカを置く
• masterは全てのファイルのメタデータを管理
  • name space、access control information, ファイルとchunkのマッピング,chunkのlocation
  • chunk lease管理,orphaned chunkedのgarbage collection,chunk server間のchunk migration
  • 定期的にchunk serverとメッセージを交換し、serverの状態を更新
• GFSclientは、masterからメタデータを取得しchunk serverと直接接続する
• GFSclientやchunk server上ではキャッシュを行わない
  • 一貫性の問題を排除してシステムを単純化するため
  • chunk serverでは既にlinux bufferが頻繁にキャッシュしている。

Single Master †

• clientはmasterに最適なchunk serverを訊く
  • clientは一定時間その情報をキャッシュしてその後のファイル操作はそのchunk serverにリクエストする
• 基本的な流れ(Figure1の説明)

1. clientはbyte-offsetをchunk indexに変換(applicationによって行われる)
2. File nameとChunk indexをmasterに送信
3. masterは対応する、Chunk handleとreplica locationを返す
4. clientはこの情報をキャッシュし、replicaにリクエストを送信する(たいていは近いreplica)
   1. この情報の期限が切れるまで、再びmasterと通信する必要はない

Chunk Size †

• chunk sizeを64MBに設定
  • これは、典型的なファイルシステムのblock sizeより大きい
• large chunk sizeの利点
  • 同一のchunkのリクエスト数が減るため、masterとの通信を削減
  • Networkのoverheadを減らすことができる
  • master上のメタデータサイズを抑えることができる
• large chunk sizeの欠点
  • ファイルサイズが小さいとchunkが一つになってしまうため、もしそのファイルに多数のクライアントがアクセスしたらそのchunk serverは大変
    • でも、そのような状況は少ないと言っている。

Metadata †

• masterは以下の3つのメタデータをメモリ上に保存
  • namespace
  • file-to-chunk mapping
  • chunkレプリカのlocation
• namespaceとfile-to-chunk mappingは、masterがローカルディスクにoperation logとして保存
• chunk locaitonは保存しない。
  • masterのsetup時やchunkserverがクラスタに追加されたときに、chunkserverに訊く

------In-Memory Data Structures------

• メタデータをメモリ上に置くことによって処理を早くする
• masterは定期的にメモリをスキャンする
  • garbage collection
  • 故障したchunkserverのためのre-replication
  • 効率的配置のためのchunk migration
• masterのメモリが足りなくなるかもしれないが、大丈夫
  • 64MBのChunkに64byte以下のメタデータでよい
  • file namespace dataも64byte
  • 仮に足りなくなっても、追加によるコストは低い

------Chunk Locations------

• ディスクなどには保存しない
• masterが逐次chunk serverに訊く
• これによりchunk serverとmasterでのconsisytencyが保たれるので、無駄な処理が必要ない。

------Operation Log------

• メタデータの履歴を保存する
• logical time line(操作の順番)も保存
• persistentになるまでclientには見せない
  • メタデータがローカルディスクに保存されそのレプリカがリモートマシンに保存されるまで
  • flushはバッチ処理を用いてスループットをあげる
• masterのリカバリを早くするためにlogのサイズを小さくする
  • logが規定のサイズ以上になったらcheckpointを入れる
  • checkpointはB-tree likeな型で管理
  • 最新のcorrectなcheckpointを用いてリカバリを行うのでcheckpoint作成の際クラッシュが起きても大丈夫

Consistency †

------Guarantees by GFS------

SYSTEM INTERACTIONS †

Leases and Mutation Order †

• mutation：ファイルの内容やメタデータを変えること
• リース(lease): 特定時間以内は更新をプッシュし続けるというサーバによる約束
• mutationの概要

1. clientがmasterにleaseをもつchunk serverとそのほかのレプリカをもつchunk serverのlovationを訊く。
   1. なければ、masterが選んだreplicaに渡す
2. masterはprimaryとその他のレプリカ(secondary)の位置を返す
   1. clientはその情報をキャッシュする
3. すべてのレプリカにデータを送信, chunkserverはそのデータをバッファに保存
   1. clientはどの順に送信してもよい
4. すべてのレプリカからackをもらったらwrite requestをprimaryに送信、primaryはデータを特定しwriteを適用する
5. primaryはすべてのsecondaryにwrite requestを送信。secondaryはprimaryと同じorderでmutationを行う
6. primaryに完了メッセージに返す
7. primaryはclientに完了メッセージを返す
   1. ここでclientへerrorなどの情報も渡す
   2. errorが起こっていたら3-7を何度か繰り返す
   3. それでもだめなら最初からやり直す 以上のように、データフロートとコントロールフローを分離することによってパフォーマンスを向上できらたらしい。

Data Flow †

• Data flowとControl flowを分離することによって、ネットワークを効率的に利用
  • Data flowはchunkserver間のチェーンを使う
  • 送信する順番は近い順
    • このトポロジー情報は(正確ではないがIPアドレスから近いchunkserverを探してるらしい)
• パイプライン転送を行いlatencyを最小化
  • elapse time：B/T + RL
    • B：送信データ量
    • T：バンド幅
    • R：レプリカの数
    • L：ノード間のlatency

MASTER OPERATION †

Replica Placement †

• スイッチや電気回路の障害からデータの信頼性や可用性を保持するために、レプリカはなるべく異なるラックへ分散させる

Garbage Collection †

• クライアントによって削除された、ファイルは削除しないて一定期間(3日など)とっておく。
• 孤児ファイルなどがあった場合は削除する

Stale Replica Detection †

• またchunkのバージョンを記録しておき、chunkのバージョンが古かった場合はupdateする
  • 障害などでupdateができないときにchunkのバージョンが古くなることがある

FAULT TOLERANCE AND DIAGNOSIS †

High Availability †

• Chunkserverやmasterは状態ログを記録しているので数秒でリカバリができる
  • masterは新しいmasterを選出する
  • DNS新たに新しいmasterへのエイリアスをつくる

Data Integrity †

• あらかじめファイルのチェックサム計算しておく
• たとえば、readのとき現在のファイルとチェックサムが一致しない場合は、errorを返し、他のレプリカからreadを行うようにする
  • この壊れたファイルは削除される
• チェックサムはread処理とオーバーラップさせて計算するのでこれによるオーバヘッドはない

提案したものの評価 †

• read
  • clientが増えると同一のchunkserverからのreadが増えるため性能が落ちる

その他 †

• とりあえず内容が難しかった。経験値をためて再度挑戦する必要があるかも。