24. Journaling and FFS

Question 1

What is not atomic when it comes to consistency?

Answer 1

Writing multiple disk blocks

Question 2

What is atomic when it comes to consistency?

Answer 2

Writing one disk block.

Question 3

What is journaling?

Answer 3

Track pending changes to the file system in a special area on disk called the journal.

Following a failure, replay the journal to bring the file system back to a consistent state

Question 4

Walk through an example of a journal.

Answer 4

Dear Journal, here’s what I’m going to do today:

1. Allocate inode 567 for a new file
2. Associate data blocks 5, 87, and 98 with inode 567
3. Add inode 567 to the directory with inode 33
4. That’s it!

Question 5

What happens when we flush cached data to disk?

Answer 5

We have to update the journal.

This is called a checkpoing

Question 6

What happens on recovery (as it pertains to journaling)?

Answer 6

Start at the last checkpoint and work forward, updating on-disk structures as needed.

Ex:
Dear Journal, I did everything listed above. Checkpoint!
Dear Journal, here’s what I have to do today:
1. Allocate … [Did this]
2. Associate …
3. Add …
4. That’s it!

[Go through to last checkpoint and go through remaining lines line by line and check to see if they’ve been done already, then add checkpoint]

Question 7

What do we do with incomplete journal entries when in recovery?

Answer 7

These are ignored as they may leave the file system in an incomplete state.

Question 8

What would happen if we processed the following journal entry?

Dear Journal, here’s what I’m going to do today:

1. Allocate inode 567 for a new file
2. Associate data blocks 5, 87, and 98 with inode 567

Answer 8

Who tf knows

Question 9

Observation: metadata updates (allocate inode, free data block, add to directory, etc) can be represented compactly and probably written to the journal atomically.

What about data blocks themselves changed by write()?

Answer 9

We could include them in the journal meaning that each data block would potentially be written twice (ugh).

We could exclude them from the journal meaning that file system structures are maintained but not file data

Question 10

What is the FFS?

Answer 10

The Berkeley Fast File System

Included in the Berkeley Software Distribution (BSD) Unit release in 1982.

Developed by Kirk McKusick.

FFS is the basis of the Unix File System (UFS), which is still in use and still developed by Kirk today

Question 11

What are some disk geometry-related questions that file systems might try to address?

Answer 11

1. Where to put inodes?
2. Where to put data blocks, particularly where with respect to the inodes that they are linked to?
3. Where to put related files?
4. What files are likely to be related?

Question 12

Why did many file systems prioritize writes to disk on the outside of the spinning disk over the inside?

Answer 12

Because assuming you can keep up with the speed of the disk, you can read data faster from the outside edge than from the inside.

Think about the physics. The outside edge has farther to travel than the inside, but both edges make the same number of revolutions per second. That means the outside edge moves faster.

Question 13

Given multiple heads stacked on top of each other, one per platter, how can we safe a file to take advantage of this feature?

Answer 13

Safe the file across all of the heads so the tracks of each platter are in the same position across all platters. This means we can access a file on disk without having to move the heads.

Moving the heads is extremely slow.

Question 14

How did FFS improve memory blocks?

Answer 14

Early file systems had a small block size of 512 B.

FFS introduced larger 4K blocks

Question 15

How did FFS improve allocating contiguous blocks on disk?

Answer 15

Early file systems had no way to allocate contiguous blocks on disk.

FFS introduced an ordered free block list allowing contiguous or near-contiguous block allocation

Question 16

What new features did FFS introduce?

Answer 16

FFS added symbolic links, file locking, unrestricted file name lengths, and user quotas

Question 17

What are the two enemies of closeness on disks?

Answer 17

1. Lateral movement, or seek times. This is major.
2. Rotational movement or delay. This is minor.

See visual in notes.

Question 18

What is a cylinder group?

Answer 18

All of the data that can be read on the disk without moving the head. Comes from multiple platters.

Question 19

What 4 things does a cylinder group have on FFS?

Answer 19

1. A backup copy of the superblock.
2. A cylinder-specific header with superblock-like statistics
3. A number of inodes
4. Data blocks

It’s almost like it’s own mini file system!

Question 20

FFS superblock contained detailed disk geometry information. What can FFS do with that?

Answer 20

This allows FFS to attempt to perform better block placement.

Example:
Imagine that the speed at which the heads can read information off the disk is greater than the speed at which the disk can return data to the operating system.

So the disk cannot read consecutive blocks off of the disk. Can’t read 0, 1, 2, 3, etc…, because after I finish transferring Block 0 the heads are over a different block.

FFS will incorporate this delay and attempt to lay out consecutive blocks for a single file as 0, 3, 6, 9, etc

Gross.

Question 21

What are the tradeoffs of hardware and software in the battle for making the slow disk fast?

Answer 21

Hardware is fixed and fast.

Software is flexible and slow.

Ex:
Software folks assume that files are contiguous on disk, but they might not be. If a disk recognizes that block 5 failed, it could map block 5 to a working block 78,329. This is great because it makes blocks 0-8 appear contiguous, but they are not, so the software folks’ assumption of contiguity is incorrect and won’t produce the locality speedup they were hoping for.

Question 22

What does it mean to put the OS in control of the disk?

Answer 22

OS - put this block exactly where I tell you to right now, slave!
Disk - Yes, master.

Question 23

What are the pros and cons of putting the OS in control of the disk?

Answer 23

Pros:
OS has better visibility into workloads, users, relationships, consistency requirements, etc. This information can improve performance.

Cons:
Operating systems are slow and buggy.

Question 24

What are the pros and cons of leaving control of the disk to hardware?

Answer 24

Pros:
The device knows much more about itself than the operating system can be expected to.
Device buffers and caches are closer to the disk

Cons:
Device opaqueness may violate guarantees that the operating system is trying to provide

Question 25

What does it mean to leave control of the disk to hardware?

Answer 25

OS - “Oh disk, you are so clever. Here’s some data! I trust you’ll do the right thing with it.”

Disk - “I AM so clever”

Question 26

How does FFS continue to improve in the way of block sizing?

Answer 26

Block sizing continues to respond to changes to average file sizes.

Small blocks: less internal fragmentation, more seeks
Large blocks: more internal fragmentation, fewer seeks

Question 27

What is the problem and the solution associated with co-locating inodes and directories with FFS?

Answer 27

Problem: Accessing directory contents is slow

Solution: jam inodes for directory into directory file itself