File systems

Required reading: soft updates.

Overview

A key problem in designing file systems is how to obtain performance on file system operations while providing consistency and stability of file systems.

The performance bottleneck in a file system is the disk. The bandwidth to a disk is reasonable high for large transfer, but latency is low, because of the cost of moving the disk arm(s). Thus, in general, we want to:

• Avoid disk operations. For read operations, caching data. For write operations, delay write operations, and absorb writes.
• Avoid seeks. Give a lot of operations to the disk so that it can do good disk scheduling. This reduces latency and improves disk throughput.
• Group many small writes into large disk operations. This means we want to be smart about disk layout.

These techniques improve throughput. To improve latency, we count on caching, read-ahead, and writing asynchronously. Today we will focus on write operation (i.e., operations that modify data that needs to be written back at some point).

The naive solution is for the file system to delay writes as long as possible, because that results in big writes, high absorption, and many dirty blocks that can be written at the same time, leading to good disk scheduling. For example, the file systems waits until it all blocks in memory are dirty and it needs a new clean block. Then, it selects the oldest one and writes it to the disk.

This strategy has two potential problems: (1) stability guarantees are weak; if the power fails before the system flushes a block, the modifications are lost; (2) loss of consistency; if the oldest block, for example, contains an inode that points to dirty data block, then after the write the disk will contain an inode pointing to old data blocks. When the file system recovers the inode may be inconsistent with what is on disk (wrong data blocks, wrong size, etc.).

The solution to the first problem is pushed to the applications in UNIX. If an application desires that a file is stable, it must call fsync, or sync (to flush all dirty blocks). To keep of the window of vunerability small, the file system also flushes ditry blocks every 30 seconds.

The second problems can be solved by ensuring that the file system respects dependencies between operations:

• Never point to a structure before it is initialized. An inode must be initialized before a directory entry references it. An block must be initialized before an inode references it.
• Never reuse a structure before nullifying all pointers to it. An inode pointer to a disk block must be reset before the file system can reallocate the disk block.
• Never reset the last point to a live structure before a new pointer is set. When renaming a file, the file system should not remove the old name for an inode until after the new name has been written.

This paper

The paper surveys some of the existing techniques and introduces a new to achieve the goal of performance and integrity for write operations in the context of a UNIX file system.

Techniques possible:

• Synchronous writes. v6 used this solution partially. FFS uses this solution for all its metadata (inodes, directory blocks, etc.) updates.
• Equip system with NVRAM.
• Atomic updates using logging. Often used in UNIX file systems for metadata updates. LFS is an extreme version of this strategy.
• Scheduler-enforced ordering. The disk driver is aware of the dependencies, but doesn't work well with delayed writes (ok with asynchronous write).
• Flusher-enforced ordering. All writes are delayed. This flusher is aware of dependencies between blocks, but doesn't work because circular dependencies need to be broken by writing blocks out.

Soft updates is the solution explored in this paper. It doesn't require NVRAM, is simpler than complete logging (e.g., no changes on disk datastructures), and performs as well as the naive strategy of keep all dirty block in main memory.

Soft updates is a sophisticated variant of flusher-enforced ordering. Instead of maintaining dependencies on the block-level, it maintains dependencies on file structure level (per inode, per directory, etc.), reducing circular dependencies. Furthermore, it breaks any remaining circular dependencies by undo changes before writing the block and then redoing them to the block after writing. (See figure 2 for an example).

Pseudocode for some of the file operations:

create (f) {
   allocate inode in block i  (assuming inode is available)
   add i to directory data block d  (assuming d has space)
   mark d has dependent on i, and create undo/redo record
   update directory inode in block di
   mark di has dependent on d
}

rename (from, to) {
   i = namei(from);
   increase refcnt in inode in block i
   add "to" directory data block td a reference to inode i
   mark td dependent on block i
   update directory inode "to" tdi
   mark tdi as dependent on td
   remove "from" directory data block fd a reference to inode i
   mark td as dependent on tdi
   decrease refcnt in inode in block i
   mark block i as dependent on td 
   update directory inode in block fdi
   mark fdi as dependent on fd
}

Pseudocode for the flusher:

flushblock (b)
{
  lock b;
  for all dependencies that b is relying on
    "remove" that dependency by undoing the change to b
    mark the dependency as "unrolled"
  write b 
}

write_completed (b) {
  remove dependencies that depend on b
  reapply "unrolled" dependencies that b depended on
  unlock b
}

Apply flush algorithm to example in figure 2:

• A list of two dependencies: directory->inode, inode->directory.
• Lets say syncer picks directory first
• Undo directory->node changes (i.e., unroll )
• Write directory block
• Remove met dependencies (i.e., remove inode->directory dependency)
• Perform redo operation (i.e., redo )
• Select inode block and write it
• Remove met dependencies (i.e., remove directory->inode dependency)
• Select directory block (it is dirty again!)
• Write it.

What needs to be done on recovery? (Inspect every statement in rename and see what inconsistencies could exist on the disk; e.g., refcnt inode could be too high.) None of these inconsitencies require fixing before the file system can operate; they can be fixed by a background file system repairer.

Paper discussion

Do soft updates perform any useless writes? (A useless write is a write that will be immediately overwritten.) (Answer: yes.) Fix syncer to becareful with what block to start. Fix cache replacement to selecting LRU block with no pendending dependencies.

Does FFS provide better stability than soft updates? (Answer: yes. FFS writes metadata updates synchronously. Before create() returns the file has been created on disk!

Can a log-structured file system implement rename better? (Answer: yes, since it can get the refcnts right).

Discuss all graphs.