25. Log-Structured File Systems Flashcards
From 1982 to 1991, what happened to the relative speed of seeks on hard disks?
Disk seek times are still dog slow.
They are becoming a performance bottleneck
How do we make a big, slow thing look faster?
Use a cache (IOW, put a smaller, faster thing in front of it)
In the case of the file system, the smaller, faster thing is memory
What do we call the memory used to cache file system data?
The buffer cache
With a large cache, what benefit do we get when it comes to disk reads?
With a large cache, we should be able to avoid doing almost any disk reads
How does a cache assist with the latency associated with writes to disk?
The cache will help collect small writes in memory until we can do one larger write
What is the best way to avoid seeks when writing?
Write everything to the same place
More realistically, write everything really really close to each other
What is LFS?
Log-structured File System
What is the main idea behind log-structured file systems?
All writes go to an append-only log
What is an example of a write to disk using a normal and cached-read write approach?
Let’s say we want to change an existing byte in a file
Normally, we do this:
- Seek to read the inode map
- Seek to read the inode
- Seek to write (modify) the data block
- Seek to write (update) the inode
Let’s assume that our big friendly cache is going to soak up the reads. Now what happens?
- Seek to read the inode map
- Seek to read the inode
- Seek to write (modify) the data block
- Seek to write (update) the inode
When do we write to the log?
When the user calls sync, fsync, or when blocks are evicted from the buffer cache
How did FFS translate an inode number to a disk block?
It stored the inode map in a fixed location on disk
Why is it a problem for LFS that it stores the inode map in a fixed location on disk?
Inodes are just appended to the log and so they can move!
What does LFS do to handle the fact that the inodes can move?
It logs the inode map
How does LFS handle file system metadata, like inode and data block allocation bitmaps, etc?
We can log that stuff too!
What happens when the log reaches the end of the disk?
There is probably a lot of unused space earlier in the log due to overwritten inodes, data blocks, etc.
This space is reclaimed when we clean the log by identifying empty space and compacting used blocks
Conceptually you can think of this happening across the entire disk all at once, but for performance reasons LFS divides the disk into segments which are cleaned separately
When should we run the cleaner in LFS?
Probably when the system is idle, which may be a problem on systems that don’t idle much
What size segments should we clean when doing a log clean?
Large segments amortize the cost to read and write all of the data necessary to clean the segment
But small segments increase the probability that all blocks in a segment will be “dead”, making cleaning trivial
What can we say about the performance effects of log cleaning?
Cleaner overhead is very workload-dependent, making it difficult to reason about the performance of log-structure file system
(and easy to fight about their performance!)
Let’s say that the cache does not soak up as many reads as we were hoping. What problem can LFS create?
Block allocation is extremely discontiguous, meaning that reads may seek all over the disk
What are three arguments in favor of reading research papers?
- Researchers have some great ideas about how to improve computer systems! Many times the design principles apply outside of the specific project described in the paper
- Both academic and industrial research labs publish papers. Frequently the best/only way to find out details about exciting production systems in use by companies like Google, Microsoft, Facebook, etc.
- Because reading the code takes way too long!
What drives research in computer systems?
It aint features.
Hardware changes and other technology trends which both expose problems with existing systems and create new opportunities for better systems.
