CSE 120CSE 120Principles of Operating SystemsPrinciples of Operating SystemsWinter 2007Winter 2007Lecture 15: Fast Metadata Updates: Rio, JournalingLecture 15: Fast Metadata Updates: Rio, Journalingand Soft Updatesand Soft UpdatesKeith Keith Marzullo Marzullo and Geoffrey M. and Geoffrey M. VoelkerVoelkerMarch 6, 2007 Lecture 15: Fast Metadata Updates 2© 2007 Keith Marzullo and Geoffrey M. VoelkerA metadata update problem• Consider creating a file A, which is assigned an inodeX.– (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, onewill be written first. Which one is preferable to befirst?March 6, 2007 Lecture 15: Fast Metadata Updates 3© 2007 Keith Marzullo and Geoffrey M. VoelkerMetadata update rulesMetadata update rules that ensure consistency in theface of failures:1. Never point to a structure before it has been initialized.2. Never reuse a resource before nullifying all previouspointers to it.3. Never reset the last pointer to a live resource before a newpointer has been set.March 6, 2007 Lecture 15: Fast Metadata Updates 4© 2007 Keith Marzullo and Geoffrey M. VoelkerFFS approachReliability-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 5© 2007 Keith Marzullo and Geoffrey M. VoelkerRio 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 soold value of memory can persist across crashes.• ... so, why not recover from file buffer cache inmemory?– 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 6© 2007 Keith Marzullo and Geoffrey M. VoelkerProtecting the buffer cache• Write protect the buffer cache.– File cache procedures enable writing to buffer cache beforewriting a page and disable it afterwards.– The only time a file cache page is vulnerable is when it isbeing 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 additionalvulnerabilities.March 6, 2007 Lecture 15: Fast Metadata Updates 7© 2007 Keith Marzullo and Geoffrey M. VoelkerHow do you know?• Use fault injection– Inject 20 faults.– If no crash within 10 minutes, discard run and reboot (50% of thetime).• Checked for corruption– Direct: a series of events eventually causes a procedure (usuallynot 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 anI/O procedure with the wrong parameters.• Find by creating deterministic memTest that generates a repeatablestream of file actions.March 6, 2007 Lecture 15: Fast Metadata Updates 8© 2007 Keith Marzullo and Geoffrey M. VoelkerFault injection resultsMarch 6, 2007 Lecture 15: Fast Metadata Updates 9© 2007 Keith Marzullo and Geoffrey M. VoelkerPerformance resultsMarch 6, 2007 Lecture 15: Fast Metadata Updates 10© 2007 Keith Marzullo and Geoffrey M. VoelkerJournaling approachMaintain an auxilary log that records all metadataoperations.• Ensure that log is written to disk before any pagescontaining data modified by the correspondingoperations.• When recovering from a crash, any unappliedmetadata operations in the log are applied.March 6, 2007 Lecture 15: Fast Metadata Updates 11© 2007 Keith Marzullo and Geoffrey M. VoelkerVariations• Store log in pre-allocated file that is maintained as acircular buffer.– File cache buffers point to last entry in log that refers tothem, so writing back buffer requires log to be forced out tothat 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 12© 2007 Keith Marzullo and Geoffrey M. VoelkerSoft Updates approachBe lazy about writing back, but follow the ordering rules.• Use delayed writes for metadata.• Maintain dependency information that specifies theorder in which data must be written back to disk.• When forcing out a block, first force out all blocks thatneed to be written first (and haven't yet made it out).There's a hitch, though...March 6, 2007 Lecture 15: Fast Metadata Updates 13© 2007 Keith Marzullo and Geoffrey M. VoelkerCircular dependenciesMarch 6, 2007 Lecture 15: Fast Metadata Updates 14© 2007 Keith Marzullo and Geoffrey M. VoelkerBreaking circulardependencies: 1March 6, 2007 Lecture 15: Fast Metadata Updates 15© 2007 Keith Marzullo and Geoffrey M. VoelkerBreaking circulardependencies: 2March 6, 2007 Lecture 15: Fast Metadata Updates 16© 2007 Keith Marzullo and Geoffrey M. VoelkerAnother Soft Updates featureSoft 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 bufferholding the corresponding directory entry.– When buffer is written, all delete dependencies are passedto a separate background syncer task.– When syncer finally runs (every minute or so) it walks inodeand frees associated file data blocks.March 6, 2007 Lecture 15: Fast Metadata Updates 17© 2007 Keith Marzullo and Geoffrey M. VoelkerComparisonsMarch 6, 2007 Lecture 15: Fast Metadata Updates 18© 2007 Keith Marzullo and Geoffrey M. VoelkerMicrobenchmarksMarch 6, 2007 Lecture 15: Fast Metadata Updates 19© 2007 Keith Marzullo and Geoffrey M. VoelkerMacrobenchmarkMarch 6, 2007 Lecture 15: Fast Metadata Updates 20© 2007 Keith Marzullo and Geoffrey M. VoelkerSummary• Metadata consistency can be addressed in severalways.– Reliability-induced synchronous writes.• Ordered writes to resilient RAM.– Logging metadata operations.– Imposing an order on writes (which requires some rollbackto avoid circular dependencies).March 6, 2007 Lecture 15: Fast Metadata Updates 21© 2007 Keith Marzullo and Geoffrey M. VoelkerNext class...• Virtual
View Full Document
Unlocking...