Metadata Update Performance in File Systems

File systems have multiple inter-related data structures. This diagram shows the data structures relevant for file ‘/foo’ with one data block. The inode bitmaps shows allocated inodes for ‘/’ and ‘foo’, the data block bitmap shows allocated blocks for ‘/’ and ‘foo’, the directory entry of ‘foo’ in ‘/’, and the inode of ‘foo’ which points to the data block. All of these structures are required to access the data block.
The image shows the state of the data structures before and after appending a block to the file ‘/foo’. The data block bitmap, inode for ‘foo’ and the new data block itself are all updated. The file system needs to ensure that the on-disk state can transition from the before image to the after image atomically in the problem of failures. This is the problem of crash-consistency for file system metadata.
The image shows the state of updated file system data structures in memory. With journaling, the file system writes the updated state to a journal in the form of a log entry. A log entry is identified by its begin and end blocks. The image shows the data bitmap and inode in the log entry. Here we assume that the file system only cares about crash consistency of the metadata. If the crash consistency of data is also required, the data would need to be added to the journal as well. Once the log entry has been committed to the disk, the file system is free to write back the blocks from memory to the disk in any order.
The image shows the three ordering rules enforced by soft updates.
  • The pointed-to structure should be written before the pointed-by structure. For example, the data block should be written to disk before an inode pointing to it, and a new inode must be written to disk before its corresponding directory entry. This ensures that the file system never accesses any garbage.
  • All previous pointers to a freed structure should be written as null before the structure is re-used. For example, if a data block is freed as part of a file truncation, the corresponding file’s inode with the nullified pointer must be written to disk before the data block can be reused for any other file. If this was not enforced, the file system can incorrectly associate re-used resources with their previous owners.
  • Write the new pointer to an allocated structure before removing its previous pointer. For example, when renaming a file, the new directory entry pointing to the file’s inode must be written before the previous directory entry is removed. This ensures that the structure is not left orphaned (pointed-to by neither the old nor the new owner) as part of the move.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store