CSE221 - lec12: File System: FFS & LFS
date
Nov 13, 2024
slug
cse221-lec12
status
Published
tags
System
summary
type
Post
12 - File System: FFS & LFS
A Fast File System for UNIX
File System Objectives
- performance (focus in today’s lecture)
- reliability (next lecture)
Limitations of original UNIX File System (Old FS)
- poor layout: i-nodes and their data blocks are stored far from each others, entailing a lot of seek, which is slow.
- block size: 512 B Block Size, which requires more transfer transactions.
FFS Solutions to Old FS’s Problem
Problem | FFS Solution |
random block placement | cylinder groups: store related data in the same cylinder groups |
inodes far from data | cylinder groups: inodes and their related data in the near or same groups |
low bandwidth utilization | increase block size to 4 KB |
small maximum file size | larger block size (so more indirect block) |
waste space with large block size | fragments: file consists of multiple blocks + at most 1 fragments at the end |
recovery superblock | replicate and distribute superblocks |
device oblivious | FS parameterization |
Allocation Policy
- global: which cylinder groups (dir + files in the same cylinder group)
- local: which block within a cylinder group (rotationally optimal placement)
- leave 10% of space unused for good performance
Summary
- FS is aware of device characteristics
- improve upon UNIX FS in several ways
- assume and matain some kind of locality: file in the same dir tend to be accessed together → pay for this assumption, if it is correct (in most cases), then you get the benefit, if it is not you still need to pay the price of maintain this logical locality.
The Design and Implementation of a Log-Structured File System
Motivating Trends
- larger memory, lower cost: more file caching, reading file is faster, performance is write-dominated
- cpu speed is increasing at a fast speed
- FS is more likely to become the bottleneck
- disk improves little in terms of performance
- transfer bandwidth improves a lot
- other does not improve much
- sequential access much better than random access
Problems of FFS
- layout: still need to seek within cylinder groups
- writing metadata is synchronous (to ensure consistency)
LFS Approach
- store file as append-only logs
Challenges
- managing free space: need some kinds of garbage collection (hard)
- retrieve information from log: maintain an inode map (cached in memory when used)
Cleaning
- read a segment (fixed-size array of blocks) into memory
- discard unused blocks
- copy live blocks
Policy
- initial policy: clean low utilization segments
- more reasonable policy: distingush between cold and hot segments
- cost benefit policy
- clean cold segments aggressively: retrive space from cold segments is more effective since they use new space slowly, we can “keep” these retrieved space longer
- wait longer before cleaning hot segments: wait longer so we could retrieve more space at one time since blocks in hot segments are short live.
LFS Today
- not used in common FS
- used in SSDs: make different parts wear evenly
Summary
- FS design exploited hardware and workload trends
- write data sequentially to log