CSE 120 Principles of Operating Systems Winter 2007 Lecture 15 Fast Metadata Updates Rio Journaling and Soft Updates Keith Marzullo and Geoffrey M Voelker A metadata update problem Consider creating a file A which is assigned an inode X a the link A X is added to a directory b the inode X is marked as allocated Since these writes are to different disk blocks one will be written first Which one is preferable to be first March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 2 Metadata update rules Metadata update rules that ensure consistency in the face of failures 1 Never point to a structure before it has been initialized 2 Never reuse a resource before nullifying all previous pointers to it 3 Never reset the last pointer to a live resource before a new pointer has been set March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 3 FFS approach Reliability induced synchronous writes a the link A X is added to a directory mark in memory copy of inode X as allocated force inode X to disk add link A X to buffered block of directory March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 4 Rio approach Why is disk more stable than physical memory Battery backup removes chances of suddenly losing power Processors don t have to reset memory upon reboot and so old value of memory can persist across crashes so why not recover from file buffer cache in memory Do modification of file buffers in the correct order Force contents of unflushed file buffers to disk upon restart What do you think March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 5 Protecting the buffer cache Write protect the buffer cache File cache procedures enable writing to buffer cache before writing a page and disable it afterwards The only time a file cache page is vulnerable is when it is being modified by a file cache procedure Existing systems already have such vulnerabilities Similar protection needed if kernel uses memory mapped files User memory mapped files pose no additional vulnerabilities March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 6 How do you know Use fault injection Inject 20 faults If no crash within 10 minutes discard run and reboot 50 of the time Checked for corruption Direct a series of events eventually causes a procedure usually not I O procedure to accidentally write to file data Find by using checksums of memory blocks in file cache Indirect a series of events eventually causes a procedure to call an I O procedure with the wrong parameters Find by creating deterministic memTest that generates a repeatable stream of file actions March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 7 Fault injection results March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 8 Performance results March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 9 Journaling approach Maintain an auxilary log that records all metadata operations Ensure that log is written to disk before any pages containing data modified by the corresponding operations When recovering from a crash any unapplied metadata operations in the log are applied March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 10 Variations Store log in pre allocated file that is maintained as a circular buffer File cache buffers point to last entry in log that refers to them so writing back buffer requires log to be forced out to that point Store log in auxiliary file system that supports logs Locate on same drive as primary file system Locate on separate drive Synchronous vs asynchronous updates March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 11 Soft Updates approach Be lazy about writing back but follow the ordering rules Use delayed writes for metadata Maintain dependency information that specifies the order in which data must be written back to disk When forcing out a block first force out all blocks that need to be written first and haven t yet made it out There s a hitch though March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 12 Circular dependencies March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 13 Breaking circular dependencies 1 March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 14 Breaking circular dependencies 2 March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 15 Another Soft Updates feature Soft Updates also defers work in some cases When a file is deleted Remove the file name from the directory hierarchy Create a remove dependency associated with the buffer holding the corresponding directory entry When buffer is written all delete dependencies are passed to a separate background syncer task When syncer finally runs every minute or so it walks inode and frees associated file data blocks March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 16 Comparisons March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 17 Microbenchmarks March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 18 Macrobenchmark March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 19 Summary Metadata consistency can be addressed in several ways Reliability induced synchronous writes Ordered writes to resilient RAM Logging metadata operations Imposing an order on writes which requires some rollback to avoid circular dependencies March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 20 Next class Virtual machines March 6 2007 Lecture 15 Fast Metadata Updates 2007 Keith Marzullo and Geoffrey M Voelker 21
View Full Document
Unlocking...