Tux3 Versioning Filesystem

Overview

Background

Since everybody seems to be having fun building new filesystems these days, I thought I should join the party. Tux3 is the spiritual and moral successor of Tux2, the most famous filesystem that was never released.[1] In the ten years since Tux2 was prototyped on Linux 2.2.13 we have all learned a thing or two about filesystem design. Tux3 is a write anywhere, atomic commit, btree based versioning filesystem. As part of this work, the venerable HTree design used in Ext3 and Lustre is getting a rev to better support NFS and possibly be more efficient.

The main purpose of Tux3 is to embody my new ideas on storage data versioning. The secondary goal is to provide a more efficient snapshotting and replication method for the Zumastor NAS project, and a tertiary goal is to be better than ZFS.

Tux3 is big endian, as the great penguin intended.

General Description

In broad outline, Tux3 is a conventional node/file/directory design with wrinkles. A Tux3 inode table is a btree with versioned attributes at the leaves. A file is an inode attribute that is a btree with versioned extents at the leaves. Directory indexes are mapped into directory file blocks as with HTree. Free space is mapped by a btree with extents at the leaves.

The interesting part is the way inode attributes and file extents are versioned. Unlike the currently fashionable recursive copy on write designs with one tree root per version[2], Tux3 stores all its versioning information in the leaves of btrees, using the versioned pointer algorithms described in detail here:

http://lwn.net/Articles/288896/

This method promises a significant shrinkage of metadata for heavily versioned filesystems as compared to ZFS and Btrfs. The distinction between Tux3 style versioning and WAFL style versioning used by ZFS and a similar method used by Btrfs is analogous to the distinction between delta and weave encoding for version control systems. In fact Tux3's pointer versioning algorithms were derived from a binary weave technique I worked on earlier for version control back in the days when we were all racing for the glory of replcaing the proprietary Bitkeeper system for kernel version control.[3]

Filesystem Characteristics and Limits

Versioning of individual files, directories or entire filesystem
Remote replication of single files, directories or entire filesystem
All versions (aka snapshots) writable
2^60 maximum file size
2^60 maximum volume size
2^48 maximum versions
2^48 maximum inodes
Variable sized, dynamically allocated inodes
New versioning method (Versioned pointers)
- versioned extents for file/directory data
- versioned standard attributes (e.g. mode, uid, mtime, size)
- versioned extended attributes (including immediate file data)
New atomic update method (Forward logging)
New physically stable directory index (PHTree)
Btree backpointers for robust fsck

Transactional Consistency

Atomic update in Tux3 is via a new method called forward logging that avoids the double writes of conventional journalling and the recursive copy behavior of copy on write.

Forward Logging

Atomic update is via a new technique called forward logging. Each update transaction is a series of data blocks followed by a commit block. Each commit block either stores the location where the next commit block will be if it is known, otherwise it is the end of a chain of commits. The start of each chain of commits is referenced from the superblock.

Commit data may be logical or physical. Logical updates are first applied to the target structure (usually a inode table block or file index block) then the changed blocks are logged physically before being either applied to the final destination or implicitly merged with the destination via logical logging. This multi level logging sounds like a lot of extra writing, but it is not because the logical updates are more compact than physical block updates and many of them can be logged with a periodic rollup pass to perform the physical or higher level logical updates.

A typical write transaction therefore looks like a single data extent followed by one commit block, which can be written anywhere on the disk. This is about as efficient as it is possible to do an atomic update.

Benefits of Forward Logging

Another very nice benefit of Tux3-style forward logging is that transaction size is limited only by available free space on the volume, because log commit blocks can be anywhere.

I dreamed up a log commit block variant where the associated transaction data blocks can be physically discontiguous, to make this assertion come true, shortly after reading Stephen Tweedie's horror stories about what you have to do if you must work around not being able to put an entire, consistent transaction onto stable media in one go:

http://olstrans.sourceforge.net/release/OLS2000-ext3/OLS2000-ext3.html

Most of the nasties he mentions just vanish if:

File data is always committed atomically

All commit transactions are full transactions

He did remind me (via time travel from year 2000) of some details I should write into the design explicitly, for example, logging orphan inodes that are unlinked while open, so they can be deleted on replay after a crash. Another nice application of forward logging, which avoids the seek-happy linked list through the inode table that Ext3 does.

Metadata Backpointers

While working on the tux3 announcement I noticed yet another advantage of versioned pointers vs the currently fashionable copy-on-write methods: metadata backpointers. Versioning is only done in two places:

Leaves of the inode table

Terminal index nodes of a file/directory btree

In both cases it is possible to store a single backpointer from the leaf block to the parent btree index node. This is impractical with a copy-on-write scheme where each version has its own tree root. Then, multiple backpointers would be required. Btrfs instead stores a "hint" consisting of the btree level and logical offset of the leaf. Tux3 can simply use direct backpointers with a corresponding increase in fsck robustness.

I should also note that versioned pointers require dramatically less metadata than copy-on-write with multiple roots. If a data block is altered in a file then the versioned pointer method only requires a single new (64 bit) pointer to be added to a terminal index node. Copy-on-write requires the entire parent block to be copied, and its parent and so on. Versioned pointer metadata representation is thus at least 512 times more space efficient than copy on write.

All Shutdowns are "Clean"

I'm just writing down points as they occur to me now. One small detail of Tux3 that should have quite a bit impact on robustness: Tux3 will always "initiate recovery" on mount, which is to say that it will read its forward logs and apply them to the memory image of btrees etc, to return to just the state it was in when it stopped. It will not roll the logs up, for example, and write out "perfect" copies of the btrees.

This will not only save time on shutdown, but it will give constant exercise to the recovery logic, which all too often is the last part of a filesystem to be perfected, if it ever is perfected.

Addendum to the last note: that is a 512 times advantage for changing one block of a file. If many or all blocks of a file are changed (a common case) then recursive copy-on-write gets closer to the space efficiency of versioned pointers, but it never quite gets there.

In the case of indexed directories it is very common for a single block to be changed, and in that case the metadata efficiency advantage of versioned pointers will be large.

End of content for now...

Versioning filesystems on rotating media are prone to fragmentation. With the write-anywhere strategy we have a great deal of latitude in choosing where to write, but translating this into minimzing seeks on read is far from easy. At least for metadata, we can fall back to update in place using the forward logging method acting as a "write twice" journal. Because the metadata is very small (at least when the filesystem is not heavily versioned) sufficient space of the single commit block required to logically log a metadata update will normally be available near the original location and the fallback will not often be needed.

When there is no choice but to write new data far away from the original location, a method called "write bouncing" is to be used, where the allocation target is redirected according to a repeatable generating function to a new target zone some distance away from the original one. If that zone is too crowded, then the next candidate zone further away will be checked and so on, until the entire volume has been checked for available space. (Remotely analogous to a quadratic hash.) What this means is, even though seeking to changed blocks of a large file is not entirely avoided, at least it can be kept down to a few seeks in most cases. File readahead will help a lot here, as a number of outlying extents can be picked up in one pass. Physical readahead would help even more, to deal with cross-file fragmentation in a directory.

An inode is a variable sized item indexed by its inode number in the inode btree. It consists of a list of attributes blocks, where standard attributes are grouped together according the their frequency of updating, and extended attributes. Each standard attribute block carries a version label at which the attribute was last changed. Extended attributes have the same structure as files, and in fact file data is just an extended attribute. Extended attributes are not versioned in the inode, but at the index leaf blocks. The atime attribute is handled separately from the inode table to avoid polluting the inode table with versions generated by mere filesystem reads.

Block count - Block sharing makes it difficult to calculate so just give the total block count for the data attribute btree

size - Update with every extending write or truncate mtime - update with every change

Either immediate file data or root of a btree index with versioned extents at the leaves

Extended attributes are tagged with attribute "atoms" held in a global, unversioned atom table, to translate attribute names into compact numbers.

The directory index scheme for Tux3 is PHTree, which is a (P)hysically stable variant of HTree, obtained by inserting a new layer of index blocks between the index nodes and the dirent blocks, the "terminal" index blocks. Each terminal index block is populated with [hash, block] pairs, each of which indicates that there is a dirent in with hash .

Thus there are two "leaf" layers in a PHTree: 1) the terminal nodes of the index btree and 2) the directory data blocks containing dirents. This requires one extra lookup per operation versus HTree, which is regretable, but it solves the physical stability problem that has caused so much grief in the past with NFS support. With PHTree, dirent blocks are never split and dirents are never moved, allowing the logical file offset to serve as a telldir/seekdir position just as it does for primitive filesystems like Ext2 and UFS, on which the Posix semantics of directory traversal are sadly based.

There are other advantages to physical stability of dirents besides supporting brain damaged NFS directory traversal semantics: because dirents and inodes are initially allocated in the same order, a traveral of the leaf blocks in physical order to perform deletes etc, will tend to access the inodes in ascending order, which reduces cache thrashing of the inode table, a problem that has been observed in practice with schemes like HTree that traverse directories in hash order.

Because leaf blocks in PHTree are typically full instead of 75% full as in HTree, the space usage ends up about the same. PHTree does btree node merging on delete (which HTree does not) so fragmentation of the hash key space is not a problem and a slightly less uniform but far more efficient hash function can be used, which should deliver noticeably better performance.

HTree always allocates new directories enties into btree leaf nodes, splitting them if necessary, so it does not have to worry about free space management at all. PHTree does however, since gaps in the dirent blocks left by entry deletions have to be recycled. A linear scan for free space would be far too inefficient, so instead, PHTree uses a lazy method of recording the maximum sized dirent available in each directory block. The actual largest free dirent may be smaller, and this will be detected when a search fails, causing the lazy max to be updated. We can safely skip searching for free space in any block for which the lazy max is less than the needed size. One byte is sufficient for the lazy max, so one 4K block is sufficient to keep track of 2^12 * 2^12 bytes worth of directory blocks, a 16 meg directory with about half a million entries. For larger directories this structure becomes a radix tree, with lazy max recorded also at each index pointer for quick free space searching without having to examine every lazy map.

Like HTree, a PHTree is a btree embedded in the logical blocks of a file. Just like a file, a directory is read into a page cache mapping as its blocks are accessed. Except for cache misses, the highly efficient page cache radix tree mechanism is used to resolve btree pointers, avoiding many file metadata accesses. A second consequence of storing directory indexes in files is that the same versioning mechanism that versions a file also versions a directory, so nothing special needs to be done to support namespace versioning in Tux3.

The main worry is what happens as number of versions becomes very large. Then a lot of metadata for unrelated versions may have to be loaded, searched and edited. A relatively balanced symmetric version tree can be broken up into a number of subtrees. Sibling subtrees cannot possibly affect each other. O(log(subtrees)) subtrees need to be loaded and operated on for any given version.

What about scaling of completely linear version chain? Then data is heavily inherited and thus compressed. What if data is heavily versioned and therefore not inherited much? Then we should store elements in stable sort order and binsearch, which works well in this case because not many parents have to be searched.

This is just a matter of providing multiple inode btrees sharing the same free tree. Not much of a challenge, and somebody may have a need for it. Is there really any advantage if the volume manager and filesystem support on-demand expansion and shrinking?

Quotas

Linux quotas are derived from the "melbourne quotas" scheme from BSD. Userspace support and man pages are obtained by installing the "quota" package on Debian.

This includes documentation of the orignal BSD system, which is slightly different from the Linux incarnation, but the latter doesn't seem to be too well documented:

The quota syscall internal is largely defined by include/linux/quota.h in the kernel source. The syscall is sys_quotactl:

The VFS handles the high level quota logic by methods that may be overridden by the filesystem, defined by struct quotactl_ops in quota.h. Ext3 only overrides the quota_on method, and then only to check that a valid quota file has been specified and issue dire warnings if the quota file is not in the root directory. Otherwise, Ext3 just specifies that the default VFS library quota methods are used, which call back to low level quota methods in the filesystem, specified by struct dquot_operations. These are:

http://lxr.linux.no/linux+v2.6.26/include/linux/quota.h#L286 initialize, drop, alloc_space, alloc_inode, free_space, free_inode, transfer, write_dquot, acquire_dquot, release_dquot, mark_dirty, write_info

Confusingly, one finds "old" and "new" quota formats implemented there. I have not dug deeply into the history or implications of this distinction. The artist here appears to be Jan Kara of Suse.

It looks like the vast majority of quota implementation is already done for us, and we mainly need to worry about syncing the quota file efficiently. We can take advantage of logical forward logging here and record the allocation changes in the commit block, provided the quota is not too near a user or group hard limit. Then roll up the updates into the quota file and sync it periodically.

The quota file does not have to be versioned. Maybe. Hmm. Well, maybe users are going to get annoyed if they can't get back to quota because a snapshot is still hanging onto blocks they tried to free. OK, the quota file has to be versioned. Well that makes it like any other file.

There is no notion of directory quotas anywhere to be seen, so we do not have to feel compelled to implement that. XFS does implement directory quotas apparently, so there is a way. Just has to be done without (much) help from the VFS and no syscall interface.

The idea of inode quotas seems bogus to me because we have a 48 bit inode space. Who is going to use up 280 trillion inodes? I say we should just ignore inode quota processing and only account blocks. (With extents, "blocks" means "granularity of an extent".)

This should provide a reasonable orientation for somebody who wants to do the quota hookup once prototype filesystem code is available. Note: this would be a nice way to learn things about the VFS if you have never delved into this before, and not too challenging because most of the sweat has been expended at the VFS level (however rambling the implementation may be) and there are several existing implementations to use as models.

We do not have to wait for sample code in order to plan out the details of how the quota file is to be versioned, and how changes to the quota file sums should be logged efficiently.

The standard method for accessing a particular version of a volume is via a version option on the mount command. But it is also possible to access file versions via several other methods, including a new variant of the open syscall with a version tag parameter.

"Version transport" allows the currently mounted version to be changed to some other. All open files will continue to access the version under which they were opened, but newly opened files will have the new version. This is the "Git Cache" feature.

Tux3 introduces the idea of a version link, much the same as a symlink, but carries a version tag so that the opened file is some other than the mounted version. Like symlinks, there is no requirement that the referenced object be valid. Version links to not introduce any inter-version consistency requirement, and are therefore robust. Unlink symlinks, version links are not followed by default. This makes it easy to implement a Netapp-like feature of having a hidden .snapshot subdirectory in each directory by which periodic snapshots can be accessed by a user.

Metablocks Like traditional superblocks, but containing only variable data Distributed across volume, all read on start Contain variable fields, e.g., forward logs

Inode table Versioned standard attributes Versioned extended attributes Versioned data attribute Nonversioned file btree root

Atime table Btree tree versioned at the terminal index nodes leaf blocks are arrays of 32 bit atimes

Free tree Btree with extents at the leaves subtree free space hints at the nodes

Atom table A btree much like a directory mapping attribute names to internal attribute codes (atoms). Maybe it should just be a directory like any other?

Forward log commit block Hash of transaction data Magic Seq Rollup - which previous log entries to ignore Data blocks

Directory Index Embedded in logical blocks of directory file, therefore automatically versioned

Implementation work has begun. Much of the implementation consists of cutting and pasted bits of code I have developed over the years, for example, bits of HTree and ddsnap. The immediate goal is to produce a working prototype that cuts a lot of corners, for example block pointers instead of extents, allocation bitmap instead of free extent tree, linear search instead of indexed, and no atomic commit at all. Just enough to prove out the versioning algorithms and develop new user interfaces for version control.

[3] Linus won. A major design element of Git (the directory manifest) was due to me, and of course Graydon Hoare (google Quicksort) deserves more credit than anyone.

From phillips at phunq.net Thu Jul 24 13:26:27 2008 From: phillips at phunq.net (Daniel Phillips) Date: Thu, 24 Jul 2008 13:26:27 -0700 Subject: [Tux3] Comparison to Hammer fs design Message-ID: <200807241326.28447.phillips@phunq.net>

Link kindly provided by pgquiles. The big advantage Hammer has over Tux3 is, it is up and running and released in the Dragonfly distro. The biggest disadvantage is, it runs on BSD, not Linux, and it so heavily implements functionality that is provided by the VFS and block layer in Linux that a port would be far from trivial. It will likely happen eventually, but probably in about the same timeframe that we can get Tux3 up and stable.

Tux3 is a simpler design than Hammer as far as I can see, and stays closer to our traditional ideas of how a filesystem behaves, for example there is no requirement for a background process to be continuously running through the filesystem reblocking it to recover space. Though Tux3 does have the notion of followup metadata passes to "promote" logical forward log changes to physical changes to btree nodes etc. However this does not have to be a daemon, it can just be something that happens every so many write transactions in the process context that did the write. Avoiding daemons in filesystems is good - each one needs special attention to avoid deadlock, and they mess up the the ps list, a minor but esthetic consideration.

Matt hit on a similar idea to versioned pointers, that is, his birth and death version numbers for disk records. So we both saw independently that recursive copy on write as in WAFL, ZFS and Btrfs is suboptimal.

I found that only the birth version is actually required, simply because file data elements never actually die, they is only ever overwritten or truncated away. Therefore, a subsequent birth always implies the death of the previous data element, and only the birth version has to be stored, which I simply call the "version". Data element death by truncate is handled by the birth of a new (versioned) size attribute.

Eventually Matt should realize that too, and rev Hammer to improve its storage efficiency. Oddly, Hammer only seems to support a linear chain of versions, whereas I have shown that with no increase in the size of metadata (except for the once-per-volume version tree) you can store writable versions with arbitrary parentage. I think Matt should take note of that too and incorporate it in Hammer.

Some aspects of the Hammer seem quite inefficient, so I wonder what he means when he says it performs really well. In comparison to what? Well I don't have a lot more to say about that until Tux3 gets to the benchmark stage, and they we will be benchmarking mainly against Ext3, XFS and Btrfs.

Matt seems somewhat cavalier about running out of space on small volumes, whereas I think a filesystem should scale all the way from a handful of meg to at least terabytes and preferably petabytes. The heavy use of a vacuum like reblocking process seems undesirable to me. I like my disk lights to go out as soon as the data is safely on the platter, not continue flashing for minutes or hours after every period of activity. Admittedly, I did contemplate something similar for ddsnap, to improve write efficiency. I now think that fragmentation can be held down to a dull roar without relying on a defragger, and that defragging should only be triggered at planned times by an administrator. We will see what happens in practice.

Tux3 has a much better btree fanout than Hammer, 256 vs 64 for Hammer using the same size 4K btree index blocks. Fanout is an important determinant of the K in O(log(N)) btree performance, which turns out to be very important when comparing different filesystems, all of which theoretically are Log(N), but some of which have an inconveniently large K (ZFS comes to mind). I always try to make the fanout as high as possible in my btree, which for example is a major reason that the HTree index for Ext3 performs so well.

Actually, I think I can boost the Tux3 inode table btree fanout up to 512 by having a slightly different format for the next-to-terminal inode table index blocks with 16 bits inum, 48 bits leaf block, because at the near-terminal index nodes the inum space is already divided down to a small range.

From phillips at phunq.net Fri Jul 25 02:39:10 2008 From: phillips at phunq.net (Daniel Phillips) Date: Fri, 25 Jul 2008 02:39:10 -0700 Subject: [Tux3] Five kinds of btrees Message-ID: <200807250239.10215.phillips@phunq.net>

Me thinking out loud, which I tend to do better when I know people will be reading it...

Tux3 has five different kinds of btrees at the moment, all to be accessed by the same generic btree code. I thought I would list them now and consider the differences, as a prelude to writing the various methods needed to specialize to the different variants.

I tend to be obsessive about packing things into even binary sized chunks if I can, thinking that processors like to operate on data that way. It probably does not matter a whole lot, but it satisfies me esthetically and if it gains a tiny amount of speed, that is nice. Well, maybe it does actually matter. A whole lot of cpu time is spent binary searching btree index blocks, and if the index entries line up on nice boundaries then the L1 cache hit rate goes up.

A more important consideration is for the btree index node entries to be compact and achieve a high fanout. Except for directory btrees (which are mapped into the logical blocks of files and can therefore get away with 24 bit logical block pointers) Tux3 index nodes have 16 bytes per entry, generally consisting of a 48 bit key, 48 bit address of a lower level index node or leaf, and free space hints to round things out to even numbers.

In two cases (file index and atime table) I could not think of anything useful to round out the twelve bytes of essential payload, so I call that unused and probably will eventually relax my obsession with binary sized data and make those entries 12 bytes long to improve the fanout by 25%.

inode table node: { inum:48 node:48 freehint:32 }[] // 16 bytes/entry node: { inum:10 node:48 freehint:6 }[] // 8 bytes/entry variant leaf: attributes

file index node: { offset:48 node:48 unused:32 }[] // 16 bytes/entry... maybe 12? leaf: { block:48 count:6 version:10 }[] // 8 bytes/entry

free extents node: { block:48 node:48 freehint:32 }[] // 16 bytes/entry leaf: { block:48 count:16 }[] // 8 bytes/entry

atime table node: { inum:48 node:48 unused:32 }[] // 16 bytes/entry... maybe 12? leaf: { version:10 ablock:48 unused:6 }[] // 8 bytes/entry ablock: { date:32 }[] // 4 bytes

directory node: { hash:31 cont:1 node:32 }[] // 8 bytes leaf: { hash:31 dblock:32 }[] // 8 bytes dblock: ext2 dirents

For those who have not lived and breathed btrees (most of us) I should state the definition of a btree node: N block pointers separated by N-1 keys. There is one less key than block pointers because there is always a higher level btree block that supplies the key that separates two btree nodes. Anyway, a vector of [pointer, key] pairs makes a btree index, with one of the keys being unused. I sometimes fiendishly coopt that unused field for something else, even though this saves only .2% of the space in a block. I will try to resist that temptation this time, and maybe even always fill in that unused field with a copy of the higher level key and use it for an internal cross check.

Free hints give an idea of the density and maximum size of the free space on the volume in the case of the free tree, or density in case of the inode table. This allows me to avoid having a secondary structure like Ext3's inode bitmap in order to locate free inodes. Instead we look in a part of the inode table with a suitable density, and search through the leaf block for the free inode we know is there.

Free space in PHTree directories is handled by an entirely different method described in the original Tux3 post (which I should eventually repost here with improvements). The free hint idea cannot be used here because there are potentially multiple terminal index blocks referring to any given dirent block, and no way to find the referers other than the one we used to reach the block. Fortunately, the non-sparse logical space of the directory file lends itself to mapping by a radix tree, which as I mentioned earlier can map freespace for about half a million dirents with a single 4K block, lazily updated.

There are two different kinds of index nodes for the inode btree: the 16 byte kind and the 8 byte kind, the latter being useful deeper in a huge inode table where the btree indexes have cut the inode space up pretty small so that the low ten bits or so of the inum is a unique index. The free hint can also be smaller. The thing is, there should end up being a lot more of the eight byte kind of inode index node because they are on the bushy end of the tree, so this should be a significant time and space saver and well worth the little bit of extra code to implement it.

The file index btree is almost as important to optimize as the inode table btree, because while there may not be many huge files, they are often things like databases and virtual machine root filesystems that require good performance. So I try to keep the terminal index extents to 8 bytes including the version, which means that any gaps between extents for a particular version have to be filled in explicitly with extents of empty space. This should be the rare case. I don't know how well this is going to work out. It would obviously be easier to put a logical offset in each versioned extent. I will probably try to code it the 8 byte way and see if the problem yields easily.

The atime table is a unwanted stepchild of ancient unix. It is hard to feel much love for it, but there it is, it has its own unique structure because the atimes have to be versioned. There is not much point in packing atimes into the leaf blocks like attributes are packed into the inode table. The leaves of the atime index tree are actually nonterminals because they reference blocks of atime dates. Hmm, I suppose those could be versioned extents of atimes, which would make the atime index really small but then raises the tough question of how big to make the extent when somebody accesses an inode. For now, no extents there.

I might as well specify the structures for the non-extent prototype while I am in here.

Considerably simpler, no? And yet it should prove the concept of this filesystem versioning method nicely.

The prototype will lift the btree leaf code for file indexes directly from ddsnap, including the leaf format that I have come to hate, but does the job. I will probably improve the leaf format shortly after and backport that into ddsnap.

It seems kind of odd, but Ext2 dirent blocks may well end up as the final directory leaf format for Tux3 because the prime requirement is that dirents not move around (physical stability) which lets out all the fancy in-leaf indexing schemes I know of. It would be kind of nice if that little piece of Ext2 survived, because Tux3 pretty much tosses out all the rest of it.

The inode table leaf format is new territory, somewhat described in the Tux3 project announcement. The details are worth a post in their own right.

The generic btree will probably get coded over the weekend, including methods for the inode table and file index, all in userspace for the time being.

From phillips at phunq.net Fri Jul 25 15:13:58 2008 From: phillips at phunq.net (Daniel Phillips) Date: Fri, 25 Jul 2008 15:13:58 -0700 Subject: [Tux3] Comparison to Hammer fs design Message-ID: <200807251513.59912.phillips@phunq.net>

On Friday 25 July 2008 11:53, Matthew Dillon wrote: > > :Hi; > : > :The announcement of yet another filesystem: > : > :http://lkml.org/lkml/2008/7/23/257 > : > :led to some comments about hammer fs: > : > :http://tux3.org/pipermail/tux3/2008-July/000006.html > : > :enjoy, > : > : Pedro. > > Those are interesting comments. I think I found Daniel's email address > so I am adding him to the To: Dan, feel free to post this on your Tux > groups if you want.

How about a cross-post? > I did consider multiple-parentage... that is the ability to have a > writable snapshot that 'forks' the filesystem history. It would be > an ultra cool feature to have but I couldn't fit it into the B-Tree > model I was using. Explicit snapshotting would be needed to make it > work, and the snapshot id would have to be made part of the B-Tree key, > which is fine. HAMMER is based around implicit snapshots (being able > to do an as-of historical lookup without having explicitly snapshotted > bits of the history).

Yes, that is the main difference indeed, essentially "log everything" vs "commit" style versioning. The main similarity is the lifespan oriented version control at the btree leaves.

> I would caution against using B-Tree iterations > in historical lookups, B-Trees are only fast if you can pretty much > zero in on the exact element you want as part of the primary search > mechanic. Once you have to iterate or chain performance goes out the > window. I know this because there are still two places where HAMMER > sometimes has to iterate due to the inexact nature of an as-of lookup. > Multiple-parentage almost certainly require two inequality searches, > or one inequality search and an iteration. A single timeline only > requires one inequality search.

Once I get down to the leaf level I binary search on logical address in the case of a file index btree or on version in the case of an inode table block, so this cost is still Log(N) with a small k. For a heavily versioned inode or file region this might sometimes result in an overflow block or two that has to be linearly searched which is not a big problem so long as it is a rare case, which it really ought to be for the kinds of filesystem loads I have seen. A common example of a worst case is /var/log/messages, where the mtime and size are going to change in pretty much every version, so if you have hourly snapshots and hold them for three months it adds up to about 2200 16 byte inode table attributes to record, about 8 inode table leaf blocks. I really do not see that as a problem. If it goes up to 100 leaf blocks to search then that could be a problem.

Usually, I will only be interested in the first and last of those blocks, the first holding the rarely changing attributes including the root of the file index btree and the last holding the most recent incarnation of the mtime/size attribute.

The penultimate inode table index block tells me how many blocks a given inode lives in because several blocks will have the same inum key. So the lookup algorithm for a massively versioned file becomes: 1) read the first inode table block holding that inum; 2) read the last block with the same inum. The latter operation only needs to consult the immediate parent index block, which is locked in the page cache at that point.

It will take a little care and attention to the inode format, especially the inode header, to make sure that I can reliably do that first/last probe optimization for the "head" version, but it does seem worth the effort. For starters I will just do a mindless linear walk of an "overflow" inode and get fancy if that turns out to be a problem.

> I couldn't get away from having a delete_tid (the 'death version > numbers'). I really tried :-) There are many cases where one is only > deleting, rather then overwriting.

By far the most common case I would think. But check out the versioned pointer algorithms. Surprisingly that just works, which is not exactly obvious:

Versioned pointers: a new method of representing snapshots http://lwn.net/Articles/288896/

I was originally planning to keep all versions of a truncate/rewrite file in the same file index, but recently I realized that that is dumb because there will never be any file data shared by a successor version in that case. So the thing to do is just create an entirely new versioned file data attribute for each rewrite, bulking up the inode table entry a little but greatly constraining the search for versions to delete and reducing cache pressure by not loading unrelated version data when traversing a file.

> Both numbers are then needed to > be able to properly present a historical view of the filesystem. > For example, when one is deleting a directory entry a snapshot after > that deletion must show the directory entry gone.

...which happens in Tux3 courtesy of the fact that the entire block containing the dirent will have been versioned, with the new version showing the entry gone. Here is one of two places where I violate my vow to avoid copying an entire block when only one data item in it changes (the other being the atime table). I rely on two things to make this nice: 1) Most dirent changes will be logically logged and only rolled up into the versioned file blocks when there are enough to be reasonably sure that each changed directory block will be hit numerous times in each rollup episode. (Storing the directory blocks in dirent-create order as in PHTree makes this very likely for mass deletes.) 2) When we care about this is usually during a mass delete, where most or all dirents in each directory file block are removed before moving on to the next block.

> Both numbers are > also needed to be able to properly prune out unwanted historical data > from the filesystem. HAMMER's pruning algorithm (cleaning out old > historical data which is no longer desired) creates holes in the > sequence so once you start pruning out unwanted historical data > the delete_tid of a prior record will not match the create_tid of the > following one (historically speaking).

Again, check out the versioned pointer algorithms. You can tell what can be pruned just by consulting the version tree and the create_tids (birth versions) for a particular logical address. Maybe the hang is that you do not organize the btrees by logical address (or inum in the case of the inode table tree). I thought you did but have not read closely enough to be sure.

> At one point I did collapse the holes, rematching the delete_tid with > the create_tid of the following historical record, but I had to remove > that code because it seriously complicated the mirroring implementation. > I wanted each mirror to be able to have its own historical retention > policy independant of the master. e.g. so you could mirror to a backup > system which would retain a longer and more coarse-grained history then > the production system.

Fair enough. I have an entirely different approach to what you call mirroring and what I call delta replication. (I reserve the term mirroring to mean mindless duplication of physical media writes.) This method proved out well in ddsnap:

http://phunq.net/ddtree?p=zumastor/.git;a=tree;h=fc5cb496fff10a2b03034fcf95122f5828149257;hb=fc5cb496fff10a2b03034fcf95122f5828149257

What I do in ddsnap is compute all the blocks that differ between two versions and apply those to a remote volume already holding the first of the two versions, yielding a replica of the second version that is logically but not physically identical. The same idea works for a versioned filesystem: compute all the leaf data that differs between two versions, per inum, and apply the resulting delta to the corresponding inums in the remote replica. The main difference vs a ddsnap volume delta is that not all of the changes are physical blocks, there are also changed inode attributes, so the delta stream format has to be elaborated accordingly.

> I also considered increasing the B-Tree fan-out to 256 but decided > against it because insertions and deletions really bloated up the > UNDO FIFO. Frankly I'm still undecided as to whether that was a good > idea, I would have prefered 256. I can actually compile in 256 by > changing a #define, but I released with 64 because I hit up against > a number of performance issues: bcopy() overheads for insertions > and deletions in certain tests became very apparent. Locking > conflicts became a much more serious issue because I am using whole-node > locks rather then element locks. And, finally, the UNDO records got > really bloated. I would need to adjust the node locking and UNDO > generation code significantly to remove the bottlenecks before I could > go to a 256-element B-Tree node.

I intend to log insertions and deletions logically, which keeps each down to a few bytes until a btree rollup episode comes along to perform updating of the btree nodes in bulk. I am pretty sure this will work for you as well, and you might want to check out that forward logging trick.

That reminds me, I was concerned about the idea of UNDO records vs REDO. I hope I have this right: you delay acknowledging any write transaction to the submitter until log commit has progressed beyond the associated UNDO records. Otherwise, if you acknowledge, crash, and prune all UNDO changes, then you would end up with applications believing that they had got things onto stable storage and be wrong about that. I have no doubt you did the right thing there, but it is not obvious from your design documentation.

> HAMMER's B-Tree elements are probably huge compared to Tux3, and that's > another limiting factor for the fan-out I can use. My elements > are 64 bytes each.

Yes, I mostly have 16 byte elements and am working on getting most of them down to 12 or 8.

> 64x64 = 4K per B-Tree node. I decided to go > with fully expanded keys: 64 bit object id, 64 bit file-offset/db-key, > 64 bit create_tid, 64 bit delete_tid), plus a 64-bit storage offset and > other auxillary info. That's instead of using a radix-compressed key. > Radix compressed keys would have doubled the complexity of the B-Tree > code, particularly with the middle-of-tree pointer caching that > HAMMER does.

I use two-stage lookup, or four stage if you count searches within btree blocks. This makes the search depth smaller in the case of small files, and in the case of really huge files it adds depth exactly as appropriate. The index blocks end up cached in the page cache (the buffer cache is just a flavor of page cache in recent Linux) so there is little repeated descending through the btree indices. Instead, most of the probing is through the scarily fast radix tree code, which has been lovingly optimized over the years to avoid cache line misses and SMP lock contention.

I also received a proposal for a "fat" btree index from a collaborator (Maciej) that included the file offset but I really did not like the... fattening. A two level btree yields less metadata overall which in my estimation is more important than saving some bree probes. The way things work these days, falling down from level 1 cache to level 2 or from level 2 to level 3 costs much more than executing some extra CPU instructions. So optimization strategy inexorably shifts away from minimizing instructions towards minimizing cache misses.

> The historical access mechanic alone added major complexity to the > B-Tree algorithms. I will note here that B-Tree searches have a very > high cpu overhead no matter how you twist it, and being able to cache > cursors within the B-Tree is absolutely required if you want the > filesystem to perform well. If you always start searches at the root > your cpu overhead will be horrendous... so plan on caching cursors > from the get-go.

Fortunately, we get that for free on Linux, courtesy of the page cache radix trees :-)

I might eventually add some explicit cursor caching, but various artists over the years have noticed that it does not make as much difference as you might think.

> If I were to do radix compression I would also want to go with a > fully dynamic element size and fully dynamic fan-out in order to > best-compress each B-Tree node. Definitely food for thought.

Indeed. But Linux is braindamaged about large block size, so there is very strong motivation to stay within physical page size for the immediate future. Perhaps if I get around to a certain hack that has been perenially delayed, that situation will improve:

> I'd love to do something like that. I think radix compression would > remove much of the topological bloat the B-Tree creates verses using > blockmaps, generally speaking.

> Space management is currently HAMMER's greatest weakness, but it only > applies to small storage systems. Several things in HAMMER's design > are simply not condusive to a small storage. The storage model is not > fine-grained and (unless you are deleting a lot of stuff) needs > reblocking to actually recover the freed space. The flushing algorithms > need around 100MB of UNDO FIFO space on-media to handle worst-case > dependancies (mainly directory/file visibility issues on crash recovery), > and the front-end caching of modifying operations, since they don't > know exactly how much actual storage will be needed, need ~16MB of > wiggle room to be able to estimate the on-media storage required to > back the operations cached by the front-end. Plus, on top of that, > any sort of reblocking also needs some wiggle room to be able to clean > out partially empty big-blocks and fill in new ones.

> On the flip side, the reblocker doesn't just de-fragment the filesystem, > it is also intended to be used for expanding and contracting partitions, > and adding removing volumes in the next release. Definitely a > multi-purpose utility.

Good point. I expect Tux3 will eventually have a reblocker (aka defragger). There are some really nice things you can do, like:

2) We want to bud off a given directory tree into its own volume, so start by deleting the subtree in the current version. If any link counts in the directory tree remain nonzero in the current version then there are hard links into the subtree, so fail now and drop the new version.

3) Reblock a given region of the inode table tree and all the files in it into one physically contiguous region of blocks

5) The new region is now entirely self contained and even keeps its version history. At the volume manager level, map it to a new, sparse volume that just has a superblock in the zeroth extent and the new, mini filesystem at some higher logical address. Remap the region in the original volume to empty space and add the empty space to the free tree.

6) Optionally reblock the newly budded filesystem to the base of the new volume so utilties that do not not play well with sparse volumes do not do silly things.

> So I'm not actually being cavalier about it, its just that I had to > make some major decisions on the algorithm design and I decided to > weight the design more towards performance and large-storage, and > small-storage suffered a bit.

Cavalier was a poor choice of words, the post was full of typos as well so I am not proud of it. You are solving a somewhat different problem and you have code out now, which is a huge achievement. Still I think you can iteratively improve your design using some of the techniques I have stumbled upon. There are probably some nice tricks I can get from your code base too once I delve into it.

> In anycase, it sounds like Tux3 is using many similar ideas. I think > you are on the right track.

Thankyou very much. I think you are on the right track too, which you have a rather concrete way of proving.

> I will add one big note of caution, drawing > from my experience implementing HAMMER, because I think you are going > to hit a lot of the same issues. > > I spent 9 months designing HAMMER and 9 months implementing it. During > the course of implementing it I wound up throwing away probably 80% of > the original design outright. Amoung the major components I had to > rewrite were the LOG mechanic (which ultimately became the meta-data > UNDO FIFO), and the fine-grained storage mechanic (which ultimately > became coarse-grained). The UNDO FIFO was actually the saving grace, > once that was implemented most of the writer-ordering dependancies went > away (devolved into just flushing meta-data buffers after syncing the > UNDO FIFO)... I suddenly had much, much more freedom in designing > the other on-disk structures and algorithms. > > What I found while implementing HAMMER was that the on-disk topological > design essentially dictated the extent of HAMMER's feature set AND > most of its deficiencies (such as having to reblock to recover space), > and the algorithms I chose often dictated other restrictions. But the > major restrictions came from the on-disk structures. > > Because of the necessarily tight integration between subsystems I found > myself having to do major redesigns during the implementation phase. > Fixing one subsystem created a cascade effect that required tweaking other > subsystems. Even adding new features, such as the mirroring, required > significant changes in the B-Tree deadlock recovery code. I couldn't get > away from it. Ultimately I chose to simplify some of the algorithms > rather then have to go through another 4 months of rewriting. All > major designs are an exercise in making trade-offs in topology, feature > set, algorithmic complexity, debuggability, robustness, etc. The list > goes on forever. >

* Forward logging - just say no to incomplete transactions * Version weaving - just say no to recursive copy on write

Essentially I have been designing Tux3 for ten years now and working seriously on the simplifying elements for the last three years or so, either entirely on paper or in related work like ddsnap and LVM3.

One of the nice things about moving on from design to implementation of Tux3 is that I can now background the LVM3 design process and see what Tux3 really wants from it. I am determined to match every checkbox volume management feature of ZFS as efficiently or more efficiently, without violating the traditional layering between filesystem and block device, and without making LVM3 a Tux3-private invention.

Hopefully not too much later. I find this dialog very fruitful. I just wish such dialog would occur more often at the design/development stage in Linux and other open source work instead of each group obsessively ignoring all "competing" designs and putting huge energy into chatting away about the numerous bugs that arise from rushing their design or ignoring the teachings of history.

From phillips at phunq.net Fri Jul 25 15:54:05 2008 From: phillips at phunq.net (Daniel Phillips) Date: Fri, 25 Jul 2008 15:54:05 -0700 Subject: [Tux3] Comparison to Hammer fs design In-Reply-To: <200807251853.m6PIrZY1015569@apollo.backplane.com> References: <4889fdb4$0$849$415eb37d@crater_reader.dragonflybsd.org> <200807251853.m6PIrZY1015569@apollo.backplane.com> Message-ID: <200807251554.05902.phillips@phunq.net>

How about a cross post? > I did consider multiple-parentage... that is the ability to have a > writable snapshot that 'forks' the filesystem history. It would be > an ultra cool feature to have but I couldn't fit it into the B-Tree > model I was using. Explicit snapshotting would be needed to make it > work, and the snapshot id would have to be made part of the B-Tree key, > which is fine. HAMMER is based around implicit snapshots (being able > to do an as-of historical lookup without having explicitly snapshotted > bits of the history).