6.826—Principles of Computer Systems 1999 Handout 7. Disks and File Systems 1 7. Disks and File Systems Motivation The two lectures on disks and file systems are intended to show you a number of things: Some semi-realistic examples of specs. Many important implementation techniques for file systems. Some of the tradeoffs between a simple spec and an efficient implementation. Examples of abstraction functions and invariants. Encoding: a general technique for representing arbitrary types as byte sequences. How to model crashes. Transactions: a general technique for making big actions atomic. There are a lot of ideas here. After you have read this handout and listened to the lectures, it’s a good idea to go back and reread the handout with this list of themes in mind. Outline of topics We give the specifications of disks and files in the Disk and File modules, and we discuss a variety of implementation issues: Crashes Disks Files Caching and buffering of disks and files Representing files by trees and extents Allocation Encoding and decoding Directories Transactions Redundancy Crashes The specs and implementations here are without concurrency. However, they do allow for crashes. A crash can happen between any two atomic commands. Thus the possibility of crashes introduces a limited kind of concurrency. 6.826—Principles of Computer Systems 1999 Handout 7. Disks and File Systems 2 When a crash happens, the volatile global state is reset, but the stable state is normally unaffected. We express precisely what happens to the global state as well as how the module recovers by including a Crash procedure in the module. When a crash happens: 1. The Crash procedure is invoked. It need not be atomic. 2. If the Crash procedure does a CRASH command, the execution of the current invocation (if any) stops, and its local state is discarded. After CRASH, no procedure in the module can be invoked from outside until Crash returns. 3. The Crash procedure may do other actions, and eventually it returns. 4. Normal operation of the module resumes; that is, external invocations are now possible. You can tell which parts of the state are volatile by looking at what Crash does; it will reset the volatile variables. Because crashes are possible between any two atomic commands, atomicity is important for any operation that involves a change to stable state. The meaning of a Spec program with this limited kind of concurrency is that each atomic command corresponds to a transition. A hidden piece of state called the program counter keeps track of what transitions are enabled next: they are the atomic commands right after the program counter. There may be several if the command after the program counter has [] as its operator. In addition, a crash transition is always possible; it resets the program counter to a null value from which no transition is possible until some external routine is invoked and then invokes the Crash routine. If there are non-atomic procedures in the spec with many atomic commands, it can be rather difficult to see the consequences of a crash. It is therefore clearer to write a spec with as much atomicity as possible, making it explicit exactly what unusual transitions are possible when there’s a crash. We don’t always follow this style, but we give some examples of it, notably at the end of the section on disks. Disks Essential properties of a disk: Storage is stable across crashes (we discuss error models for disks in the Disk spec). It’s organized in blocks, and the only atomic update is to write one block. Random access is about 100k times slower than random access to RAM (10 ms vs. 100 ns) Sequential access is 10-50 times slower than sequential access to RAM (20 MB/s vs. 200-1000 MB/s) Costs 50 times less than RAM ($.02 MB vs. $1/MB from the back of a PC magazine) in January 1999. MTBF 1 million hours = 100 years.6.826—Principles of Computer Systems 1999 Handout 7. Disks and File Systems 3 Performance numbers: Blocks of .5k - 4k bytes 10-20 MB/sec sequential, sustained (more with parallel disks) 4 ms average rotational delay (7200 rpm = 8.5 ms rotation time) 8 ms average seek time; 3 ms minimum It takes 12 ms to get anything at all from a random place on the disk. In another 12 ms you can transfer 120 KB. Hence the cost to get 120 KB is only twice the cost to get 1 byte. By reading from several disks in parallel (called striping or RAID) you can increase the transfer rate by a factor of 5-10. Performance techniques: Avoid disk operations: use caching Do sequential operations: allocate contiguously, prefetch, write to log Write in background (write-behind) A spec for disks The following module describes a disk Dsk as a function from a DA to a disk block DB, which is just a sequence of DBSize bytes. The Dsk function can also yield nil, which represents a permanent read error. The module is a class, so you can instantiate as many Disks as needed. The state is one Dsk for each Disk. There is a New method for making a new disk; think of this as ordering a new disk drive and plugging it in. An extent E represents a set of consecutive disk addresses. The main routines are the read and write methods of Disk: read, which reads an extent, and write, which writes n disk blocks worth of data sequentially to the extent E{da, n}. The write is not atomic, but can be interrupted by a failure after each single block is written. Usually a spec like this is written with a concurrent thread that introduces permanent errors in the recorded data. Since we haven’t discussed concurrency yet, in this spec we introduce the errors in reads, using the AddErrors procedure. An error sets a block to nil, after which any read that includes that block raises the exception error. Strictly speaking this is illegal, since read is a function and therefore can’t call the procedure AddErrors. When we learn about concurrency we can move AddErrors to a separate thread; in the meantime we take the liberty, since it would be a real nuisance for read to be a procedure rather than a function. Since neither Spec nor our underlying model deals with probabilities, we don’t have any way to say how likely an error is. We duck this problem by making AddErrors completely non-deterministic; it can do anything from introducing no errors (which we must hope is the usual case) to clobbering the entire disk. Characterizing errors would be quite tricky, since disks usually have at least two classes of