Subject: Re: Journaling for FFS
To: None <tech-kern@NetBSD.org>
From: Cary G. Gray <Cary.G.Gray@wheaton.edu>
Date: 10/05/2006 13:05:08
The "log near the inodes" idea misses one of the advantages of
journalling, which is to improve the locality of writes by concentrating
them in the log. Journalling just the metadata wins, because that's where
lots of small, carefully ordered, writes can be required.
Working out how to journal isn't trivial. Log analysis has to find the
last complete log record, and modern disk interfaces are likely to write
the blocks of even a large contiguous write out of order. So there is
considerable care required...
Fifteen years ago I worked for DEC, and I was in the middle of a project
that included adding metadata journalling to the FFS. We used Bob
Hagmann's paper on the Cedar File System as our roadmap. I left DEC
before the work was completed; Uresh Vahalia finished implementation of
the filesystem code and wrote a nice paper for USENIX.
Here are the references:
Robert B. Hagmann, Reimplementing the Cedar File System Using Logging and
Group Commit, Proc. 11th ACM Symposium on Operating Systems Principles,
pp. 155-162, Austin, TX, 1987, ACM.
(You can find it in the ACM Digital Library or through CiteSeer at
Uresh Vahalia, Cary G. Gray, and Dennis Ting. Metadata logging in an NFS
server. In Proceedings of the Winter 1995 USENIX Technical Conference,
pp. 265-76, New Orleans, LA, January 1995. USENIX.
for a link to it in PostScript.)
Hagmann's paper is especially good on log management and analysis of
possible failures, including what happens if you fail in the middle of
writing a log record. The way that bits get to a disk has changed a
lot in twenty years; so Hagmann's analysis would not apply, but he does
provide a good example of careful analysis of assumptions.
The approach we took was mostly-physical redo logging, as in Hagmann.
The biggest complication from the FFS data structures is that some blocks
change between being metadata and regular file contents--those containing
directory data and indirect blocks. Those transitions must somehow be
dealt with; what I figured out back then was a way to do it via multiple
passes during replay, one way for each level of indirection.
It would probably be better to log the transitions of blocks to/from
metadata status, so that decision about whether to replay modificiations
can be based on log analysis alone. If you do something like Hagmann's
transaction header/trailer record scheme, you can leave room in those
records to record the changes--you probably need to pad to keep blocks
Doing so would also allow you to log and lazily reclaim the blocks pointed
to by indirect blocks: you can log to indicate that a particular
nth-indirect block should be freed. The actual freeing of the blocks
pointed to by it can be recorded later along with the actual freeing of
the block. That spares you from having huge transaction records for
delete/truncate--you end up with some number of later transactions to
handle the freeing. Recovery would need to enqueue any intend-to-free
indirect blocks it finds that haven't completed so that the freeing could
Now that I think about it, such an "intent to free" record could be one
way to handle the removed-but-still-open inode problem. You can record
its removal from the directory and an "intend-to-free" for the inode. When
it is finally closed, you can then either synchronously log it to be freed
(including logging freeing the blocks it points to), or you could enqueue
it for lazy reclamation (possibly piggybacked on another transaction).
If a crash (or forced remount readonly, etc.) happens before it is
reclaimed (i.e., before the actual free is written to the log),
recovery--whenever it runs--would handle the actual freeing of the inode
and any associated blocks.
The mostly-physical logging scheme you get in this way includes logical
(operation) logging of just a few important state transitions for blocks
and inodes: allocation (as data), allocation (as metadata) [both of which
might include zeroing], intent-to-free (for inodes and blocks of indirect
pointers), freeing. I'd have to spend some time working on the details to
tell whether that list is complete...
As you can probably tell, I've wanted to get back to putting these ideas
into an implementation, but (as right now) I always seem to need to be
taking care of one of my classes.