Case Study Two: A Reliable U^{1} File System

Marc Horowitz

Section 4: Prof. Peter Elias Luis Rodriguez May 2, 1991

1Berekeley CSRG has decided that, for copyright reasons, the U in UFS stands for nothing. Since they’re cooler than AT&T, I’m going to concur.

1 Overview

In order to implement a UFS which can recover from system crashes, the system must be able to back out of an uncommitted transaction, leaving the system in a consistent state.

The log will record only blocks which are written, since reads do not change the state of the �lesystem. Therefore, the only information in the log record will be the block address and the data written there. The log must also contain markers for the start and end of each operation, so that recovery can function properly.

2 Implementation

The LVD layer will be single-threaded. It will operate on calls from the �le layer and execute the operations in the disk cache and the log to insure that the �lesystem is recoverable. If the system become idle, periodic synch’s should be made in order to decrease the time a recovery will take, should a recovery become necessary.

2.1 Individual operations

start operation Writes a marker record to the log indicating that an external operation has begun. end operation

Writes a marker record to the log indicating that an external operation has ended.

synch All sectors in the cache are written to disk, then the log before the most recent start operation is deleted, since all the operations in it are now on disk. The rest of the log may still need to be undone, so the log is kept, and force’d to disk.

LVD read Reads a block off the disk. If the block was cached, then the LVD will not access the disk. If the block was not cached, it will be cached for future use.

LVD write Writes an entry into the log noting that the block was written, including enough information to redo or undo the write, then writes the block into the memory cache.

2.2 Recovery

During normal operation, only one external operation can be active at a time. When a close is executed, all state is �ushed to the disk, so the contents of the disk are well-known. After that, writes are buffered, so it is possible that a write in the log has not been committed to disk.

If the system fails, then recovery proceeds as follows. The log is read backwards, looking for the �rst marker record.

• If it is an end operation record, then there was no operation currently active. In this case, search backwards to the beginning of the log, and perform all writes in order to insure that all operations which returned have in fact been updated on disk.

• If it is a start operation record, then an operation was currently active. All writes in the log from the beginning to the most recent end operation record should be written, then the remaining transactions (the ones after the start operation) should be undone.

The system can crash at several times. If it crashes right after a synch, then the state on disk will exactly match the state which was in memory before the crash, and recovery will not need to do anything.

If the system crashes between operations, then the log may be missing the last few entries in the log from the last operation. If this is the case, then the recovery algorithm will undo this operation. Since this last operation could not have been a close, this is allowable according to the speci�cations.

If the system crashes in the middle of an operation, then the situation is similar to above, except that there is no completed transaction to be posthumously aborted.

3 Cache Mechanism

The cache should be a standard cache which uses LRU replacement, and keeps dirty bits on all its information. Since any information written to the cache is also con�rmed in the log, the information in the cache can be recovered if the system crashes. So, a write-behind cache which is periodically �ushed when the system is idle gives ef�ciency for both reading and writing, without wasting system time. The log assures that even in case of system failure, that the contents of the cache are not critical to any committed operation.

4 Extensions

4.1 Multiple Clients

In order to provide for multiple clients, you have the standard problems of locking. The easiest form of locking is to lock on the operation level, but this could be very inef�cient, forcing unnecessary synchronization. More ef�cient, but more dif�cult to implement, is to implement locking at the LVD level. This would involve a correspondingly more complex system to determine incomplete operations, and to synch only one thread at a time. Of course, there would need to be locking at the block level to keep two threads from modifying the same block and confusing each other.

4.2 Multiple Disks

Since multiple disks are completely independent, the implementation should be very simple. You would need to have a thread for each disk, and a �eld would have to be added to the addr structure containing a disk identi�er.

4.3 Distributed System

Currently, there are several well-known models for distributed �lesystems, including NFS and AFS. The LVD layer could be easily inserted into either of these systems, replacing the unreliable virtual disk system which these remote �lesystems have now. This would gain the advantages of these preexisting systems, while adding the bene�ts of reliability, with no change in client software.

Note: The case study is ambiguous, so I am assuming that the disk is stable storage. The design will only be able to recover from system crashes, not media failure.