A primer on Log Structured Filesystems

The concept of a Log Structured File System was first developed by Mendel Rosenblum ¹and was extended by Margo Seltzer et.al. for the BSD operating system. logfs has been available on some flavours of BSD, but does not appear to be well supported.

A couple of effort have been reported which aimed to create a log structured filesystem for Linux, possibly the most notable being LinLogFS, previously known as dtfs².

LinLogFS was hampered somewhat by being developed on a 2.2 kernel which would have made much of the implementation much more awkward than in a 2.6 kernel. It also embodied some design decisions that do not fit with my goal. Thirdly, development seems to have stopped nearly 3 years ago. For these reasons, LinLogFS was not considered as a starting point for LaFS.

To understand how a log structured filesystem works two basic ideas are needed. The first involves storing the entire filesystem as a tree, providing a single starting point for all addressing. The second involves dividing the storage device into large segments to which new data is written.

Representing a filesystem as a single tree is not an idea unique to log structure filesystems. reiserfs works this way as does TUX2. Indeed any Unix filesystem is largely a tree already, as there is a 'root' directory and all files and directories are attached to that single root by way of one or more intermediate levels in the tree.

In a traditional Unix filesystem, the parts of the filesystem that are not addressed as part of a tree are the inode table and the map of free blocks. Rather than having locations on the device described by higher levels in the tree, these have fixed locations on the device.

Taking such a filesystem, and storing the inode table and the free-block map in special files is a simple way to create a filesystem that is fully based on a tree and this is exactly what TUX2 does.

The result of having all the metadata in files is that the only datum that has a fixed location on the device is a pointer to the root of the tree. This root then points, possibly via indirect blocks, to the file containing all inodes. One of these inodes addresses a file that contains the free block bitmap. Another inode contains the root directory. Following this pattern, the entire filesystem can be found.

Once we have all addressing for the filesystem in a single tree we have a great deal of flexibility about what data gets store on which part of the device. As there are no fixed locations, anything can be stored anywhere on the device. This leads us to the second important aspect of a log structured filesystem -- the segments.

The device is conceptually divided into a number of segments, each a few megabytes in size. When data needs to be written to the filesystem, an unused segment is found, and all dirty data is written to that segment together with any indexing information needed to find the data. This could involve:

• Some data blocks from a number of modified or created files.
• A few indirect block that contain the addresses of some of those blocks, where the file is too large of all addressing to fit in the inode.
• Possibly some blocks of directories where files were create or deleted.
• Inodes for all of the files that have been changed containing (at least) new addressing information.
• Possibly some indirect blocks which store the addresses of these inodes in the inode file.
• Finally the inode for the file that contains all other inodes is written

All this data is written contiguously into one or more segments, and finally the address of the root inode is written to some fixed location on the device. From that inode, the entire new state of the filesystem can be found.

This approach seems simple and elegant, until you run out of unused segments. At that point is suddenly seems horribly flawed. To get us out of this sticky situation, we have a service called a cleaner.

As files are created, updated, and deleted, some segments that at one time were full of useful data, will eventually become full of uninteresting, unreachable data, and maybe just a few blocks of live data. It is the task of the cleaner to identify those segments which have just a few blocks of interesting data, and to gather the interesting blocks from a number of segments together and relocate them to a new, previously clean, segment. Once this is done, all those old segments can be marked as 'clean' and can be re-used.

To help the cleaner in its task we store some extra metadata in the filesystem. These include:

• A segment usage table that keeps a count of the number of live data blocks in each segment. This is kept up-to-date as new blocks are allocated and as old blocks become inaccessible.
• An 'age' for each segment giving an ordering to all segments indicating how old the data is. As newly written data is likely to be more volatile than data that has been stable for a while, this is used to help guide the cleaner. Cleaning a new segment is not as productive a cleaning an old segment as, if we wait a little while, the new segment my soon have much less live data in it that it does now and so can be cleaned more cheaply.
• Summary information in each segment. This summary information indicates, for each block in the segment, which file it is part of, and which block in that file it is. When the cleaner chooses to clean a particular segment, it reads this summary information and checks each file/block to see if it is still live in that segment, or if it has already been relocated by an update. Any block that has not already been relocated gets relocated. This will bring the usage count for the segment down to zero, at which point it can be re-used.

The summary information is not really per-segment, but is per-write-cluster. A write-cluster is a header containing the summary plus a number of data and metadata blocks that are all written at once. A write cluster may span an entire segment, but in the face of synchronous writes there could be many write clusters per segment.

From the above description, it would appear that to update a single block, and to force that change safely to disk, would require writing the block, possibly an indirect block, the inode, an indirect block to locate the inode, and the root inode, and then recording the new location of the root inode in its fixed home. Performing lots of synchronous writes, as an NFS server typically does, would cause a substantial waste in write throughput.

However because of the summary information in each segment we do not need to do this. To flush a single block to storage, all that is needed is to write out the block together with some summary information that describes it. Each write cluster contains this summary information and also the address of the next write cluster, and some information for internal validation. This allows recently written write clusters to be found at filesystem mount time, and to be incorporated into the filesystem through a process called roll-forward. Thus committing a single write cluster is all that is needed to commit a block of data.

Typically several blocks will be written together even when doing synchronous writes, so the overhead will only be one block for the summary information, rather than several blocks for all indexing and inode information.

Some useful characteristics of a log structured filesystem as outlined above are:

• Data is written in large contiguous blocks, so a very high write throughput can be achieved, at least in smallish bursts.
• Data is only ever written to unused portions of the device, so we never over-write live data. This means that an interrupted write can never corrupt live data.
• Recently written data can easily be found and examined, so an unclean shutdown need not cause any filesystem inconsistencies.
• Data is continuously being re-arranged by a background task -- the cleaner. This means that file defragmentation can easily be incorporated.
• As new data does not over-write old data, it is possible to keep old images of the filesystem accessible, as long as we don't run out of storage space. These old images are referred to as 'snapshots'. In order to manage cleaning in the presence of snapshots, we keep a segment usage table for each active snapshot. Segments used by a snapshot typically do not get cleaned until the snapshot it released.

Some other aspects of lafs that are not general to all Log structure filesystem, are not specific to any of the needs which will be discussed in the following sections, but are none-the-less interesting are:

• Inodes are stored one per block. This is largely because an LFS gains no particular benefit, and some costs, from storing multiple inodes in a single block. Thus small files will be wholly contained within the inode, and many large files will have all index information in the inode.

• Indexing of large files is achieved with a B-tree that addresses extents rather than individual blocks (but that is pretty common these days).

• As noted, we need to keep an age for each segment, and we need to keep the table of ages in memory for easy access by the cleaner, so we don't want to use too many bits. To achieve this we note that we do not need a high level of granularity for old segments: very old and extremely old are much the same as far as the cleaner is concerned. So we store the age in a 16bit field and when we get close to running out of new values, we decay all values currently in the table: values less than 32768 are halved, values greater have 16384 subtracted. The means that we can still differentiate where we need to without wasting bits. The summary information in each segment stores an actual 64bit age (well, date-of-birth really) for the rare occasions when it is needed.

• Access time is a fairly frustrating aspect of filesystem design, as it needs to be updated often, accessed whenever an inode is accessed (whether the application will use it or not) but is very rarely used.

  lafs does not store the access time in the inode, but rather stores all access times in a special non-logged area of storage that will be described in more detail in the next section. Access times are thus not guaranteed to be uptodate and can more easily be corrupted, but are mostly close enough.