Tux2: The Filesystem That Would Be King

To all but a handful of a handful, a perfect filesystem would be boring: files would be where you expect them to be, corrupt files would never be an issue, and a power outage would result in nothing more than a few moments of darkness rather than minutes or hours of lost work. Even so -- perhaps a clue that the perfect example is far, far away -- the news on the Linux filesystem front is pretty exciting of late. In a low-key technical session Friday morning at ALS, kernel hacker Daniel Philips announced to the world the minor revolution he's planning -- which could end up replacing Linux's old standby ext2fs (and it's coming replacement ext3fs) with his Tux2 filesystem. Though Tux2 is an ext2 cousin in many ways, it carries at least one crucial improvement: according to Philips, you can literally pull the plug on a system running Tux2 and expect not to lose files or spend minutes watching fsck crawl by.

Phillips, an expatriate Canadian now employed by Berlin-based Innominate AG, claims 25 years of computer programming experience. He's had stints in everything from database design and game programming to embedded controller system development, and in a dual life which may sound familiar to many computer programmers, Phillips worked through music school by hacking Fortran code. With that background, perhaps it's unsurprising that just a few years after first encountering Linux, and a year from joining the ranks of the kernel hackers (there's a +5 informative thread in Zack Brown's excellent Kernel Traffic), he's come up with what could be a sea change in Linux filesystems.

A Filesystem You Can Live With And Pull The Plug On

The central point of a journaling file system is that in exhange for a small hit in performance, file integrity is assured by an ingenious mechanism: rather than being written directly (and riskily), filesystem changes are instead first recorded sequentially in a running list -- the journal -- the contents of which are then acted upon in turn. If the system should crash for any reason while a change is not yet accomplished, the recovery time upon reboot is greatly abbreviated, as long as this "edit decision list" remains intact. Journaling file systems are on the way from multiple projects, and rather than being theoretical, wouldn't-it-be-nice daydreaming, at least one is availble right now: the ReiserFS developed by Hans Reiser is even an option at install on some recent Linux distributions.

Why another, then? Wrong question: Tux2 is not a journaling filesystem. Phillips says that Tux2 offers Linux users the chief advantage of a journaling filesystem (namely, keeping files safe in the event of a system crash) but without a journal, and does so more efficiently.

"The big deal is when you compare it to journaling, which is a popular solution, and you see that it's just plain writing less blocks. That's a big savings. It's also not constantly going back to wherever the journal is on the disk to write to the journal, so there's a lot less seeking involved. So those two things together means that it should significantly outperform journaling." Perhaps more importantly, Tux2 is not actually a wholly new filesystem per se; it shares so much in common with ext2 that it is built as a patch to ext2, with the filesystem converted at runtime. How does Tux2 get around keeping a journal to do the things that a journaling filesystem does? Atomic updates are the key. (See also: soft updates) Instead of a journal, Tux2 uses what Phillips terms a "Phase Tree algorithm."

"I originally called it Tree Phase," he says, "and then Alan Cox mentioned it on the Linux kernel list. He called it Phase Tree on the Linux kernel list, and I decided I liked that better." The Phase Tree algorithm is simple at heart, but takes a little while to grasp -- at least it did for me. Happily, Phillips has written a lucid tutorial on his own site. Probably the best explanation is the one found on Phillips' project site: the exerpts which I found most illuminating are these:

All accesses to filesystem data are performed by descending through a filesystem tree starting at its metaroot.

Normally, three filesystem trees exist simultaneously, each with its own metaroot. One is recorded on disk with a complete, consistent tree descending from it. A consistent second tree, the 'recording' tree, in the process of being recorded to disk, descends from a metaroot in memory, and some of its blocks are in dirty buffers. A third tree, the 'branching' tree is in the process of being accessed and updated by filesystem operations, also with its metaroot in memory. The branching tree and is not required to be internally consistent at all times. In particular, some blocks that are free in the branching tree may not be marked as free in its block allocation maps but held on a 'deferred free' ('defree') list instead.

At some point the recording tree will be fully recorded on disk and its metaroot can be written to disk so that it replaces the metaroot of the recorded tree. This causes the filesystem to move atomically between states, as desired. At this point, the recording tree becomes the recorded tree, and the branching trees metaroot is copied to become the new recording tree. This event is called a 'phase transistion' and the interval between two such events is called a 'phase'.

"The problem is, it's not nice to block filesystem transactions. If you're using a KDE desktop or similar, you find your desktop moving in a very jerky way while the blocks are getting written -- no good. That's why we make another tree by copying the metaroot -- that's how we always start, we never start one by going up the tree -- meanwhile this second tree is undisturbed by that and can be written to the disk in peace."

This additional copy allows the user to work without noticing a system slowdown, while the intermediate branch is copied. Thus, there are always three "trees," and in the event of a system crash, recreating the system's correct state is as easy as identifying the latest succesfully written tree. "Each new tree is always incremented higher, so this is easy," Phillips says.

"There are a couple of other places where [Phase Tree] is obviously better than journaling. For instance, removeable media -- your removeable media is usually slowest, and you don't put a journal on it, because if you did, it would be really, really slow. So you put the journal on your hard disk, and the data on the removeable media. As soon as you pull your removeable media out, you have instant corruption, because you've removed yourself from your backup. Phase Tree doesn't do that -- you can just pull out your removeable media and you have something current up to the last tenth of second, quarter of a second."

Sleepless nights and database integrity

Phillips' work with Phase Trees began a decade ago, when he implemented a system with similar functionality for a specialized database called Nirvana which he had developed on his own. "I would have implemented this on a Unix filesystem at the time as well, except I didn't have one available."

Was there a Eureka moment in 1989? "Oh yeah. I dimly recall having a a week of sleepless nights, tossing and turning, trying to figure out if it was even possible to do something abot this, and eventually convinced myself that it was. And as I recall, it was quite tricky to get it to a hundred percent state, not 99.99. I could smell the idea in there, but I couldn't find it's actual realizaton for some time. After that, the generalization of its application to a general file system is pretty obvious."

Still, the idea stayed with him until he realized it would be an interesting way to improve the performance of Linux systems.

Like the puzzle with square pieces sliding around a single missing square, only scant disk resources are used to accomplish the extra data's movement because the information is moved incrementally -- in blocks rather than all at once. That means, says Phillips, that "It really adds very little [disk] overhead. Something on the order of 1 percent."

Additionally, it has one more feature which may appeal to the fsck-hater in you: "Really, it's nearly a defragmenter already," Phillips says. "It would be trivial to add that functionality."

The dual advantages of lower overhead and -- most importantly -- a close relation to the ext2 file system should make it an easier transition for most users. Tux2 is actually built as a patch to the ext2 filesystem; standard ext2 filesystems are converted to Tux2 at mount time. According to Phillips, that conversion takes on the order of a tenth of a second per gigabyte on a typical system.

Fly In The Ointment

Though Phillips downplays their significance, patent difficulties may lie ahead for Tux2 as well. Network Appliance applied for a patent in the early 90s which covers similar ground -- a few years after Phillips had implemented it in his database.

"What really steams me in this is that their [patent] application came three years after my invention," says Phillips. "I hate to use the word infringe, because that makes me sound like the bad guy -- but it seems as though my [method] doesn't infringe beause it uses a different algorithm. In fact," he says, "I've got two things: I've got prior art, and I've got a better algorithm ... We can fence them in [legally], so their best strategy is to be nice, but they haven't figured that out yet."

"I don't want to suggest that NetApp got the idea from me -- I don't think they did, I think they developed it independently. The only little problem is the chronology of it. I concieved the whole thing, essentially everything that they've written in their patent, so I was kind of upset when I saw it. I would have gone on to do in on a Unix file system at the time, if I'd only had one available. We know it's stupid, but you see people patenting things all the time on the web -- just because it is a business idea that is now being done on the web." The approach that Phillips has to the dispute is to simply keep working. "I don't want it to become a distraction, I just keep doing what I'm doing."

Do penguins have calendars?

Phillips says that Hans Reiser has approached him regarding integrating the file protection capabilities of Tux2 with the additional features of ReiserFS. "But it's pretty obvious where the priority has to be," he says, noting that ext2 is the default file system, and isn't going away any time soon. "Ext2 is what everyone has by default, and that's too big to ignore."

Does Phillips anticipate Tux2 becoming the default file system in Linux systems? "Well, who knows what's going to happen?" he laughs. "It could. But you can be sure of one thing, Tux2 will live a fairly long life as an independent patch that people apply, and I will be the 1st to apply it. But sure, of course I'd like that."

With a caution that fits someone whose last job was in embedded controls, Phillips warns against putting Tux2 in too soon: "It has to be proven, it has to be 100 percent. Because that's the whole point of this, is to 100 percent. So I think any bug which is not an ext2 bug already is just not acceptable."

And ultimately, like any other possible low-level change, "It's up to his high penguiness." Besides which, "it's quite clear what the next Linux filesystem standard is going to be. Well, it's my opinion that ext3 is going to be the most popular standard linux filesystem next year. And a couple years after that, well, I certainly will be using tux2 all the time, and we'll see where it goes."

The current status is heavy development: "I want to give it as a Christmas present to myself and start using it in my root system for my own development," says Phillips, "as soon as I port it to [the 2.4 kernel]." Soon after that, the code will be released to the developers on the Tux2 mailing list which Phillips has been assembling, who will work to make a public release in the months that follow, a process which Phillips says will likely take six months to a year.

"There is a prototype for kernel 2.2.13. I'm not going to release it -- I have my reasons for that, and the main reason is that the amount of cleanup to make it presentable to the public is roughly the same as the amount of work I have to do to bring it to [a newer kernel]. Probably if I'd done nothing else but worked on it for a couple of months, I'd be using it now, but I've done a few other things [in those months], like change from an industrial control systems job where they wanted me to do the next version of the control system in Windows NT to a nice linux job where I can hack the kernel."

Does this have anyone else itching for 2.5?

Re:this is not going to make microsoft happy...

That's a pretty funny quote, especially since NTFS is not a journalling filesystem.

What a pack of liars. I don't see how those Marketing guys can look at themselves in the mirror.

"Free your mind and your ass will follow"

Not Comfortable...

Maybe it's because I grew up on unstable filesystems, but....

The Tux2 filesystem project has the following goals:

[SNIP]

Eliminate the need to perform fsck after an interruption
[SNIP]

If I was saving a file, and my computer decided to take a shit and die on me, I'd want to run an integrety check on the file system whether it's stable or not. If not for anything, but my own sanity. I mean, you were in the middle of saving a file. If that was a large file, and the computer died.....well, logically, the saved data should be recoverable. However, experience says that the file would most likely be corrupted.

Stable filesystem or not, I'd still be running a filesystem check. (When Windows 95 died on me, I ran scandisk as soon as it was finished booting - even before OSR2. Just to be SURE everything was cool.)

-- Give him Head? Be a Beacon?

You still need an fsck program.

Unexpected power-off is NOT the only thing which can happen to a filesystem. What about these disasters?

1) Bad block takes out part of your disk unexpectedly.
2) Your OS screws up and spews a mess onto your filesystem before it crashes. (there ARE bugs in the kernel!)
3) You have a minor headcrash which takes out one of your tracks, but the disk is still functional.

What're you gonna do? Tux2 isn't gonna help you.

You could restore your latest dump. You could
also attempt to repair the filesystem.

You need fsck or some other means of filesystem repair.

Re:Not Comfortable...

But that's the whole point of how this new stuff works: You don't run an fsck. There is absolutely no point in doing so.

All the complex mechanisms behind the filesystem ensure that, if the FS thinks a file is there, then it *IS* there, period. If the power was yanked halfway through writing a file, it simply won't be there.

In the case of a Journalling system, this works because, instead of a fsck, you simply look at the journal. If there is stuff there, you know what hasn't been written (and now can't be, cause you crashed) and you can make the appropriate adjustments.
In the case of phase tree, it's even simpler to check: it appears to work something like... the new trees are written backwards, root last.. so if the root is htere, the write is complete. If it's not, you don't see it anyway!

TYPE & CREATOR CODES

TYPE & CREATOR CODES

i really hope they use this excellent opportunity to
be able to get rid of REGISTRY TYPE TRACKING once and
for all.

basically all those little three letter extensions
that are used to keep track of the file type like
.txt .tif .jpg etc. are a cludge.

if you simply make one extra entry in the file directory
system (in addition to filename, date, block pointers) itself:
TYPE & CREATOR -- then you will never again need to keep track
of file types externally by a sort of 'Registry' file.

so, if you have a text file, you don't need to put .tif
on the end of it, simply, you would have the type and
creator of the file set to: 'TIFF' and '8BIM' which would
mean that its a TIFF file, and it should be opened by
photoshop if in a GUI you go and double-click it.

this approach makes it much more difficult for any
accidental SEPARATING of the file type info from the
info that determines which app should open it - and thus
makes the user-experience and OS less prone to error and
frusteration.

it would be simple to add - if only someone bothered to
put it in now - while the system is being determined.

please consider this.

regards,
[e-mail]

Re:Don't forget the cache

One thing I was thinking is that journaling data or disk cache could be written to a battery backed up RAM-disk. That way, if the power fails, all the data would still be on the RAM disk, and the disk could be properly updated. The RAM disk would be as fast as regular RAM (well, depending on where it is located) so writes would be nice and fast. RAM is cheap, batteries are cheap, so whats holding it up?

This is terrible!

First they don't allow dogs in dorms, now our computers won't eat our papers! How am I ever going to get another paper extension again???

Sounds great, but BFS...

the Beos Filesystem, which is now at least five years old has been offering these sort of essentials for now 5 years. The only real regret is how its no longer a true database....

Still, this beats the pants off of FAT :)

Re:Version control system

VMS has had this for many, many years. Files are listed as such:

ex: README.TXT;4 would be version 4 of README.TXT

There's a command you can type to purge all but the 'x' most recent versions, but I don't remember what it is, as I'm actively trying to forget I ever even used VMS. Anyway, you could really eat up some disk space if you didn't run this command every so often.

I always found the versioning to be a pain in the ass to deal with, but I guess it did come in handy occasionally. I think the negatives outweigh the benefits though.

--

Re:Patents? This algorithm was published in 1977

The Phase Tree algorithm is actually an improvement on this idea. Instead of recursively updating trees for every filechange, you keep 3 'phases' of the tree and cache which blocks have changed - then atomically write the metablock (et. al) after X changes or X milliseconds. This drastically reduces the amount of work that must be done and removes the constant recursion problem. This is better described in the info given on the Tux2 site.

Put your hand in the puppethead

Correct Link to "Tux2"

Appears to be this:

http://innominate.org/~phillips/tux2/ [innominate.org]

Two els

Another case...

Of a user trained by the machine, and not the machine designed to accomodate the user!

Of course there should always be system integrity checks available to the user for the paranoid among us (scandisk, fsck, etc)...

But one would imagine a properly designed computer system has the capability of *never* having corrupted data! The machine would be pointing out to the user that FileA.ext was lost due to problems, and that the user needs to check on the integrity of the data, or that the data seems to be okay, does the user want to double check, or that nothing seems to be wrong.

It's like... driving your car to the grocery, and then checking the oil, air, gas, transmission fluid, and brake fluid. The analogy is broken because the car didn't die, ala Windows, but it should be that the machine should be smart enough to tell you when something is wrong. I think.

The nick is a joke! Really!

Patents? This algorithm was published in 1977

I read about tux2 a few weeks ago, and noticed that it was implementing an algorithm I had read about a few weeks before, in a book on database architecture. Hopefully the discovery of some prior art will counter any patent claims.

Tux2's reliability algorithm essentially goes as follows:

1. At the beginning of a transaction, the "metablock" (including the block allocation table) at the root of the filesystem tree is copied into a buffer.

2. Whenever a block in a file is updated, the updated image of the block is written to a newly allocated block, and the "new" metablock is updated with the new allocation. Blocks pointing to the old block may also be updated, in recursive fashion, eventually copying and updating an entire subtree from the original. The blocks in the "old" subtree are marked as free in the new metablock. The newly allocated blocks can live in memory, but must be written to disk before commit.

3. At commit time, the new subtree replaces the old one. This operation simply involves overwriting the original metablock with a new one, which contains pointers to the new subtree as well as to the other subtrees which have not changed. If this operation does not complete, the complete picture of the old metablock, the old subtree linked to it, and free blocks where the new subtree was written, is maintained. If the operation does complete, the new image of the filesystem with the new, updated subtree, and free blocks where the old subtree used to be, is obtained.

This is a good algorithm, and it's the only way to achieve atomicity and reliability without any logging, but it does have a few tradeoffs. Each update necessitates allocating a new block, so, for instance, changing one byte in the middle of a 2G, contiguous file will require allocating a block at least 1G away (and putting a hole where the old block was). There is also a ripple effect as pointers are updated up the tree, so changing one byte of data may will mean cloning a block, then cloning the blocks that point to the block, and so on up to the root.

Re:can user processes schedule phase transitions?

While that would be nice, using it to create a system snapshot for backup would be even nicer. You could tell all of your applications to write everything they need to write and freeze temporarily. Then you start a backup application as a transaction to your filesystem and it gets the frozen snapshot while your apps are unfrozen and work merrily away. The unfrozen applications see all their updates, and the backup sees the frozen filsystem.

can user processes schedule phase transitions?

It would be kind of cool if, for example, I could do something like:

# tux2_transaction && make && make test && make install && tux2_commit

and then if there was a power failure in the middle of the build, I wouldn't have a build directory half-full of compiled files.

On the other hand, I'm not sure how useful this would be; it would be easy (I assume) to defer phase transitions for an entire file system until a moment convenient for the superuser, but it could degrade performance for all other users on the system, and to get around that problem, you'd have to do all the grunt work of implementing a multi-user relational database within your file system.
--

*BSD SoftUpdates provide crash resistance NOW

IMHO, *BSD with it's "soft updates" by Kirk McKusick is far superior to Linux ext2 in crash fs corruption resistance. I deliberately hit the power-bar off switch during four FreeBSD 3.3 kernel SMP compiles fairly late in the process
(78 sec total vs 125 sec Linux 2.2.14) to make sure that data was going to disk.

In all four cases I ran, the fsck upon repowering was fast, minor and automatic, mostly freeing unattached blocks whose metadata presumably wasn't fully written at powerout. More surprising, in three of the four trials, `make -j 4` _resumed_ the compile and as best as I could tell completed the interrupted kernel compiles without error. (Same ksize. md5 doesn't work because of timestamp) About 30-45 seconds
worth of data was lost in dirty buffers at poweroff. In the fourth case, I got compile errors, but only had to `make clean`.

I am seriously impressed. I've had poweroffs during Linux kernel compiles and had manual fsck work to do. There some info at Kirks's site http://www.mckusick.com/softdep/index.html
and there's a very interesting paper whose URL I don't have handy.

Version control system

Has anyone produced a file system that was essentially a version control system (MS SourceSafe, MKS SI etc)...you could delete a file, write a new version of a file etc, and be assured you could go back and get older versions if needed (ie each time you boot up your os you `label` the existing version numbers of all files so you could go back to that state if you screw up before the next `label`.
Do you follow me? Is this a good idea? Has it been done? Too slow? Etc.. :)

a.