Log Structured Filesystems

(An LFS doesn't overwrite the old versions of blocks <#3078#> anyway<#3078#>, so it's trivial to implement tentative writes--- you just commit all the outstanding writes by overwriting the superblock. An LFS is essentially an applicative data structure, where you make virtual (mostly shared structure) copies of indexing structures The Butler Lampson ;SPM_quot;Hints;SPM_quot; paper mentions the, well-known, tactic of using logs for reliable store, and (plug alert) we implemented a log-structured UNIX style filesystem for the Auragen (r.i.p.) operating system back in 1981. The basic idea was to use two ;SPM_quot;superblocks;SPM_quot; so that the one on disk always rooted a consistent file system. The active superblock was equipped with a pointer to a inode table ( so inodes could be in any location on disk), to the free list, and to a ;SPM_quot;semi-free;SPM_quot; list of blocks used by the old file system but not writable until sync. All writes were to free-blocks from the free list used by both the old and new filesystem. Writing data to a block resulted in a copy and insertion of the old block onto the ;SPM_quot;semi-free;SPM_quot; list. On an sync, the semi-free list was appended to the free list, and the newly saved superblock was marked as safe. A paper on this file system can be obtained from David Arnow at Brooklyn College. <#3082#>#tex2html_wrap4630#<#3082#>