LogStructuredFileSystem Servey • 論文：The Design and Implementation of a Log-Structured File System (1991) • 著者：Mendel Rosenblum, John K. Ousterhout • ＰＤＦ： http://citeseer.ist.psu.edu/rosenblum91desig n.html Log Structured File System • 目的：書き込みパフォーマンスを向上させる info1 data1 FFS data2 data2’ data3 info1 info1’ LFS data1 data2 data3 info1’ data2’ •ばらばらだった書き込み要素を近くにまとめて、 一回のアクセスで書き込む（速度アップ） •書き込み、上書きは全てログの形で追記 (クラッシュリカバリのしやすさ） Unix FFSの構造 • • • • • • inodeをベースにしたファイルシステム ファイルの内容はブロック単位で書き込む ブロックへのアドレスをinodeが持つ 最初の10個のアドレスはinode 残りはin direct block ファイルの更新日時等の情報も持つ block block inode In direct block block Unix FFSの問題点 • Dir1/File1を書き込む場合を考える • inodeの位置が固定アドレス • 4回のシーク！ 4つを書き換え！ inode inode data Dir data Log Structured File System • • • • inodeをどこでも置けるようにする データとinodeを隣接させる 一回のシーク！ inodemapは十分に小さいのでメモリに乗る 追記 inode map Dir inode data inode data 容量の問題 • ログを書いていくと容量が不足 • いらなくなったログをガベージコレクトする 必要 • セグメント(1MByte)単位で空き領域を管理 セグメントクリーニング • • • • • いらなくなったログを回収する セグメント内で生きているブロックをコピー ブロックの生き死にを判断する必要 Segment Summary Blockを導入 ⇒セグメント内のブロックにファイル番号と ブロック番号を割り当てる • inode mapを見て生きているか判断 gabage gabage 空き！ クリーニングポリシー • ベーシックに実装すると・・・ • いつ？ バックグラウンドで • どこを？ 最も断片化している部分 • どのようにグルーピング？ Age Sort • これらは最適？ 最適なクリーニングポリシーの 決定をするために • 書き込みコストの指標 • Write cost=total bytes read and written / new data written • 新しいデータを書くたびに、どれだけアクセ スしなければならないか • これを最小化するような、クリーニングポリ シーが望ましい LSFの書き込みコストを計算 • 1セグメント書くときに1セグメント回収すると仮定 • 書き込みコストは回収セグメントの使用率に依存 • 理想は、少と一杯のbinualで、常に少を回収して いればよい状況 • そうなるようにクリーニングポリシーを決定したい 書き込みコスト実験 • 4kByteのファイルを上書きする実験 • A.全てのファイルに均等にアクセス • B.Hot-and-coldにアクセス • Hot:10%のファイル 90%アクセス • Cold:90%のファイル 10%アクセス 結果 • グラフ • ディスク使用率が低ければLFSよりいい • しかし空間局所性が上がると性能低下！？ なぜ局所性が上がると性能が落 ちるのか？ • • • • • 使用率が低いセグメントをクリーニング Hotなセグメントが上書きされやすい ⇒ガベージが生まれやすい ⇒クリーニングされやすい しかし、クリーニングしても、それもhotなの ですぐに死ぬ • 段々、 Coldがフラグメント化され、ディスク にガベージがたまる Cost-Benefit-Policy • Hotは後でまとめてクリーニングした方がいい • Coldはクリーニングした後、live dataがそのまま 残り続ける確率が高い • クリーニングした後、どれだけ生き続けるかを基 準にすることで、hotとcoldを分けて扱う • Benefit/cost=(1-u)*age/(1+u) • 回収された後に生まれる空き領域/コピーするの に必要なコスト u：使用率 Segmant Usage Table • • • • • Cost-benefit-policyを実現するため ⇒セグメント内のlive dataの数 ⇒もっとも若いブロックの年齢 を持つ ログとして書き出される 性能評価 • 80％のディスク使用率でも、ＦＦＳ改良版と 同程度の性能が出る • 詳しい評価は次章以降
© Copyright 2025 ExpyDoc
