Slide 1File Systems: Consistency IssuesWhat about Multiple Updates?Which is a metadata consistency problem?Consistency: Unix ApproachConsistency: Unix Approach (Cont’d.)TransactionsImplementing TransactionsTransactions in File SystemsVista writing its journalWhere on the disk would you put the journal for a journaling file system?Transactions in File Systems: A more complete way1File Systems:Consistency Issues2File Systems: Consistency IssuesFile systems maintains many data structuresFree list/bit vectorDirectoriesFile headers and inode structuresData blocksAll data structures are cached for better performanceWorks great for read operations… but what about writes?If modified data is in cache, and the system crashes all modified data can be lostIf data is written in wrong order, data structure invariants might be violated (this is very bad, as data or file system might not be consistent)Solutions: Write-through caches: Write changes synchronously consistency at the expense of poor performanceWrite-back caches: Delayed writes higher performance but the risk of loosing data3What about Multiple Updates?Several file system operations update multiple data structuresExamples:Move a file between directoriesDelete file from old directoryAdd file to new directoryCreate a new fileAllocate space on disk for file header and dataWrite new header to diskAdd new file to a directoryWhat if the system crashes in the middle?Even with write-through, we have a problem!!The consistency problem: The state of memory+disk might not be the same as just disk. Worse, just disk (without memory) might be inconsistent.4Which is a metadata consistency problem?A. Null double indirect pointerB. File created before a crash is missingC. Free block bitmap contains a file data block that is pointed to by an inodeD. Directory contains corrupt file name5Consistency: Unix ApproachMeta-data consistencySynchronous write-through for meta-dataMultiple updates are performed in a specific orderWhen crash occurs:Run “fsck” to scan entire disk for consistencyCheck for “in progress” operations and fix up problemsExample: file created but not in any directory delete file; block allocated but not reflected in the bit map update bit mapIssues: Poor performance (due to synchronous writes)Slow recovery from crashes6Consistency: Unix Approach (Cont’d.)Data consistencyAsynchronous write-back for user dataWrite-back forced after fixed time intervals (e.g., 30 sec.)Can lose data written within time intervalMaintain new version of data in temporary files; replace older version only when user commitsWhat if we want multiple file operations to occur as a unit?Example: Transfer money from one account to another need to update two account files as a unitSolution: Transactions7TransactionsGroup actions together such that they areAtomic: either happens or does notConsistent: maintain system invariantsIsolated (or serializable): transactions appear to happen one after another. Don’t see another tx in progress.Durable: once completed, effects are persistentCritical sections are atomic, consistent and isolated, but not durableTwo more concepts:Commit: when transaction is completedRollback: recover from an uncommitted transaction8Implementing TransactionsKey idea:Turn multiple disk updates into a single disk write!Example:Begin Transactionx = x + 1 y = y – 1CommitSequence of steps:Write an entry in the write-ahead log containing old and new values of x and y, transaction ID, and commitWrite x to diskWrite y to diskReclaim space on the logIn the event of a crash, either “undo” or “redo” transactionCreate a write-ahead log for the transaction9Transactions in File SystemsWrite-ahead logging journaling file systemWrite all file system changes (e.g., update directory, allocate blocks, etc.) in a transaction log“Create file”, “Delete file”, “Move file” --- are transactionsEliminates the need to “fsck” after a crashIn the event of a crashRead logIf log is not committed, ignore the logIf log is committed, apply all changes to diskAdvantages:ReliabilityGroup commit for write-back, also written as logDisadvantage:All data is written twice!! (often, only log meta-data)10Vista writing its journal11Where on the disk would you put the journal for a journaling file system?1. Anywhere2. Outer rim3. Inner rim4. Middle5. Wherever the inodes are12Transactions in File Systems: A more complete wayLog-structured file systemsWrite data only once by having the log be the only copy of data and meta-data on diskChallenge: How do we find data and meta-data in log?Data blocks no problem due to index blocksMeta-data blocks need to maintain an index of meta-data blocks also! This should fit in memory.Benefits:All writes are sequential; improvement in write performance is important (why?)Disadvantage:Requires garbage collection from logs (segment
View Full Document
Unlocking...