This is great! We have sorely needed this for quite a while what with terabyte size filesystems getting into common use.

Some random comments:

Would it make sense to treat the journal as a circular buffer? Then commit to the underlying provider starts when the buffer has $hiwater blocks or the upper layer wants to sync. The commit stops when the buffer has $lowater blocks or in case of sync the buffer is empty. This will allow parallel writes to the provider and the journal, thereby reducing latency.

I don't understand why you need FS synchronization. Once the journal is written, the data is safe. A "redo" may be needed after a crash to sync the filesystem but that is about it. Redo should be idempotent. Each journal write block may need some flags. For instance mark a block as a "sync point" -- when this block is on the disk, the FS will be in a consistent state. In case of redo after crash you have to throw away all the journal blocks after the last sync point.

It seems to me if you write a serial number with each data block, in the worst case redo has to do a binary search to find the first block to write but normal writes to journal and reads from journal (for commiting to the provider) can be completely sequential. Since redo will be much much faster than fsck you can afford to slow it down a bit if the normal case can be speeded up.

Presumably you disallow opening any file in /.deleted.

Can you gjournal the journal disk? Recursion is good:-)

-- bakul