Log-Strucutred File Systems Flashcards
What are 3 motivations for log-structured file systems?
- Growing memory size (performance determined by writes)
- File systems perform many random operations (especially random writes with in-place update)
- File systems were not RAID- aware (RAID setups incur many writes)
In a LFS, we turn writes _______
sequential
Writing single blocks _________ does not guarantee _______ writes
sequentially, efficient
An example of a inefficient sequential write is writing A1, then having to wait for ____ _______ to write A2
disk rotation
To increase write efficiency, we keep track of all updates in a ________ ______ AKA ______
memory buffer, segment
When the memory buffer has enough _______ write them to disk all at once
updates
What is the equation used to calculate how big the memory buffer should be?
D = (F/1-F) * R_peak * T_position where F = % of R_peak R_peak = disk transfer rate T_position = positioning time
Inodes are ______ throughout the disk in a LFS
scattered
We can find scattered inodes by using an ______ _____
inode map
An inode map maps inode numbers to the address of the most ______ version inode
recent
To maintain the _______ _______ guarantee in a LFS, we place the inode map next to where it is updating all the other new information
sequential writes
To find the inode map spread across the disk, we maintain a fixed location on _____ to begin a file lookup
disk
A ________ _______ contains pointers to the latest pieces of the inode map
checkpoint region
The checkpoint region is only updated _____________
periodically
What are the four steps in reading a file from disk in a LFS?
- Read checkpoint region
- Read entire inode map and cache to memory
- Read the most recent inode
- Read a block from by using in/direct or doubly indirect pointers
The ________ structure of a LFS is identical to classic UNIX file systems
directory
A directory is a file whose data blocks consist of _______ __________
directory information
LFS produces ________ since new file versions are written to new locations while older versions are scattered all over disk
garbage
The garbage produced by LFS must be ______/_______ to allow for space reuse
cleaned/collected
What are 2 alternatives to handling garbage inodes and data blocks?
- Versioning
2. Garbage collection
In versioning, the file system keeps old versions of inodes and data blocks so users can ________ and use ______ ______ __________
restore, old file versions
In garbage collection, the file system keeps only the ______ version and _________ cleans old versions
latest, periodically
In garbage collection, old data is deleted on a _________-__-_______ basis
segment-by-segment
In garbage collection, why isn’t old data deleted on a block-by-block basis?
The cleaner will leave many free hole in random locations, making write non-sequential
LFS handles garbage inodes and data blocks using the ______ ________ method
garbage collection
What does a segment summary block do?
Records inode number and offset for each data block
A segment summary block is located in each ______
segment
A data block is live id the latest inode ______ the block
indicates
Liveness can be determined using _______ ______
version number
When are three time block are cleaned?
- Periodically
- During idle time
- When the disk is full
A hot segment is a segment where blocks are frequently _____-________
over-written
A cold segment is a segment that is relatively _____
stable
____ segments should be cleaned sooner than ___ segments
cold, hot
In LFS crash recovery, the CR points to the head and tail segment of the ___
log
In LFS crash recovery, each log ________ points to the next
segment
In LFS crash recovery, LFS can easily recover by reading the latest valid __
CR
How do we ensure the atomicity of CR updates in LFS crash recovery?
Keep two CRs
In LFS crash recovery, what is the CR update protocol?
timestamp -> CR -> timestamp
In LFS crash recovery, when it rolls forward, we start from the ____ of the log and read segments, adopting updates as we go along
end
