File System Crash Consistency

Question 1

File system data structures must _______

Answer 1

persist

Question 2

File system data structures are stored in _______ devices to survive for a long time

Answer 2

storage

Question 3

The main challenge is to _____ persistent data structures in spite of _________ and _____ failures

Answer 3

update, crashes, power

Question 4

In a scenario with 3 writes to data block, inode, and data bitmap with only 1 write succeeding, what happens of only the data block is written to disk?

Answer 4

This is as if the write did not happen because the inode was never updated -> nothing to worry about

Question 5

In a scenario with 3 writes to data block, inode, and data bitmap with only 1 write succeeding, what happens if only the inode is updated?

Answer 5

The inode points to a new data block, but there’s no actual data there -> inode reads garbage data (inconsistency)

Question 6

In a scenario with 3 writes to data block, inode, and data bitmap with only 1 write succeeding, what happens if only the bitmap is written?

Answer 6

Bitmap indicates data block is used, but nothing points to it -> space leak as data block will never be used (inconsistency)

Question 7

In a scenario with 3 writes to data block, inode, and data bitmap with 2 writes succeeding, what happens of the inode and bitmap are written?

Answer 7

The data block is not updated -> following inode leads to garbage data (inconsistency)

Question 8

In a scenario with 3 writes to data block, inode, and data bitmap with 2 writes succeeding, what happens when the inode and data block are written?

Answer 8

Allocation of data block not recorded -> data block may get re-allocated (data corruption)

Question 9

In a scenario with 3 writes to data block, inode, and data bitmap with 2 writes succeeding, what happens when the bitmap and data block are written?

Answer 9

We have no idea which file the new allocated data block belong to

Question 10

The goal of the crash consistency problem is to move the file system from one consistent state to another ________

Answer 10

atomically

Question 11

what are 2 challenges of the crash consistency problem?

Answer 11

1. Disk only commits one write at a time (but we need to do many)
2. Crashes a power failures may happen between writes

Question 12

One solution to the crash consistency problem is the file system _______

Answer 12

checker

Question 13

The fsck is a _____ used for finding inconsistencies in file system and ____ them

Answer 13

tool, fix

Question 14

What structures are checked by fsck?

Answer 14

superblock, free blocks, inode state, inode pointers, etc

Question 15

fsck cannot fix all problems because a file system may look ________ but the inode points to _______

Answer 15

consistent, garbage

Question 16

The real goal of the fsck is to make sure the file system ________ is consistent

Answer 16

metadata

Question 17

fsck performs _______ checks on the superblock, like making sure file system size > number of _____

Answer 17

sanity, blocks

Question 18

How does fsck check free blocks?

Answer 18

Scan inodes, direct, and indirect blocks to learn which blocks are allocated, then cross check with the bitmaps

Question 19

If the fsck suspects the inode state is corrupted after a ______ check, it clears it as it is not an easy fix

Answer 19

sanity

Question 20

What does fsck check for inode links and how does it do it?

Answer 20

fsck checks the link count. It does it by scanning the entire directory tree to build up new link counts

Question 21

fsck checks for duplicates by checking if 2 different _______ point to the same ____

Answer 21

inodes, block

Question 22

fsck checks for bad blocks by scanning through the list of _______ and checking for bad pointers i.e. pointer pointing to block number outside ______ size

Answer 22

pointers, partition

Question 23

How does fsck check directories?

Answer 23

fsck does integrity checks. Make sure . and .. are first 2 entries and each inode referred to in the directory is allocated

Question 24

fsck does not know about the _______ of normal files

Answer 24

content

Question 25

fsck needs detailed _______ of the file system

Answer 25

detailed

Question 26

fsck is an ________ tool and is typically invoked at ______

Answer 26

offline, boot

Question 27

What is the main disadvantage of fsck?

Answer 27

It is too slow as it scans the entire disk

Question 28

Another solution to crash consistency problem is __________

Answer 28

journaling

Question 29

In journaling, we note down “what to do” before actually doing the ________

Answer 29

updates

Question 30

Journaling is also known as _______-______ logging

Answer 30

write-ahead

Question 31

In journaling, any permanent change must be recorded in the ____ first

Answer 31

log

Question 32

In journaling, the log is also stored _______ on disk

Answer 32

permanently

Question 33

In journaling, if there is a ______, we look at the log upon reboot and try again

Answer 33

crash

Question 34

Journaling makes more work during _______, but reduces work during ______ ________

Answer 34

updates, crash recovery

Question 35

The journal occupies space within the _______

Answer 35

partition

Question 36

In data journaling, update content is wrapped in a _________

Answer 36

transaction

Question 37

What is a transaction?

Answer 37

Updates that must all happen atomically or not

Question 38

Transactions are also called _______ _______

Answer 38

physical logging

Question 39

What are the 5 components in a transaction?

Answer 39

TxB, I[v], B[v], Db, TxE

Question 40

In data journaling, both the TxB and TxE contains the __________ ID

Answer 40

transaction

Question 41

In journaling, a _______ is when the transaction is safely logged and the updates actually happen on disk

Answer 41

checkpoint

Question 42

In our first naive procedure for write(), what 2 steps do we have?

Answer 42

1. Journal write (transaction data to log)

2. Checkpoint (write updates to final location)

Question 43

Our first naive procedure for write() with 2 steps doesn’t work because our transaction data may be written to the…

Answer 43

out of order

Question 44

What are 3 ways to write a transaction to log?

Answer 44

1. One request at a time (for a total of 5 writes)
2. One big write containing all the writes
3. Two writes. One for everything except TxE, and one for TxE

Question 45

Writing the transaction one request at a time 5 times is ___

Answer 45

slow

Question 46

Writing the transaction with one big request is _______ because the writes finish in any order and items between TxB and TxE could be missing, but seems fine to the system after a crash.

Answer 46

unsafe

Question 47

Writing the transaction with 2 requests depends on the _______ guarantee of the storage device. TxE has to be ________than a fixed size

Answer 47

atomicity, smaller

Question 48

In our second naive procedure for write(), what 3 steps do we have?

Answer 48

1 Journal Write (everything except TxE)

2. Journal Commit (TxE)
3. Checkpoint

Question 49

How do we recover when a crash happens before the transaction is written?

Answer 49

Skip the pending updates

Question 50

When a crash happens after a transaction is written bu before the checkpoint, we scan all _______ transactions then checkpoint them

Answer 50

committed

Question 51

When a crash happens during checkpointing, we ____ the checkpointing process

Answer 51

redo

Question 52

If we modify two files in the same directory, the same block gets updated twice using two __________, leading to ________ writes

Answer 52

transactions, excessive

Question 53

To prevent the same block getting updated twice, we can _______ journal writes into a ________ transaction

Answer 53

buffer, global

Question 54

When batching log writes, we mark relevant block as _____, add them to a list of blocks to write for the current ___________, then commit the global transaction after a _________

Answer 54

dirty, transaction, timeout

Question 55

What two problems arise when the log becomes full?

Answer 55

1. Long recovery time

2. No further transactions can be committed to the disk

Question 56

To prevent the log from becoming full, we treat the log as a ________ structure and reuse journal space once the transaction has been __________

Answer 56

circular, checkpointed

Question 57

The journal superblock marks the _____ and ______ transactions in the log

Answer 57

oldest, newest

Question 58

What four steps do we have in the final write procedure with journaling?

Answer 58

1. Journal Write (except TxE)
2. Journal Commit
3. Checkpoint
4. Free (mark log space as free by updating journal superblock)

Question 59

A problem of data journaling is that every data block is written to disk _____-

Answer 59

twice

Question 60

In metadata journaling, we only log changes to _______

Answer 60

metadata

Question 61

Metadata journaling is also known as _______ ______

Answer 61

ordered journaling

Question 62

What are the 2 alternatives to picking when to write data blocks to disk during metadata journaling?

Answer 62

1. Write data after transaction

2. Write data to disk before transaction

Question 63

In metadata journaling, if we write data to disk after the transaction, the inode may end up pointing to ________ _____ if the data write fails

Answer 63

garbage data

Question 64

What are the 5 steps in the write protocol with metadata journaling?

Answer 64

1. Data Write )write data to final location)
2. Journal metadata write (no TxE)
3. Journal Commit
4. Checkpoint metadata
5. Free

Question 65

Block reuse can cause data corruption when say block 1000 is updated, deleted, then created into something else. If a crash occurs, the newly created directory would be ______ instead of the old thing that was at block 1000

Answer 65

modified

Question 66

On solution to the problem of block reuse is adding a ______ _______ to the journal

Answer 66

revoke record

Question 67

The revoke record prevents data from being __________ during journal replay

Answer 67

replayed