LogStructuredFileSystem Servey 論文：The Design and Implementation of a Log-Structured File System (1991) 著者：Mendel Rosenblum, John K. Ousterhout ＰＤＦ：http://citeseer.ist.psu.edu/rosenblum91design.html
Log Structured File System 目的：書き込みパフォーマンスを向上させる info1 data1 data1 FFS LFS data2 data2’ data2 data3 data3 info1’ info1 info1’ data2’ ばらばらだった書き込み要素を近くにまとめて、 一回のアクセスで書き込む（速度アップ） 書き込み、上書きは全てログの形で追記 (クラッシュリカバリのしやすさ）
Unix FFSの構造 inodeをベースにしたファイルシステム ファイルの内容はブロック単位で書き込む 残りはin direct block ファイルの更新日時等の情報も持つ inode block block In direct block block
Unix FFSの問題点 Dir1/File1を書き込む場合を考える inodeの位置が固定アドレス 4回のシーク！ 4つを書き換え！ data Dir data
Log Structured File System inodeをどこでも置けるようにする データとinodeを隣接させる 一回のシーク！ inodemapは十分に小さいのでメモリに乗る inode data inode Dir data 追記 inode map
容量の問題 ログを書いていくと容量が不足 いらなくなったログをガベージコレクトする必要 セグメント(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にアクセス
結果 グラフ ディスク使用率が低ければ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％のディスク使用率でも、ＦＦＳ改良版と同程度の性能が出る 詳しい評価は次章以降