Slashdot Mirror
Tux2: The Filesystem That Would Be King
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?
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
when Push Comes to Shove
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.
--
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
Appears to be this:
http://innominate.org/~phillips/tux2/
Two els
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!
GPL Deconstructed
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.
---- "If we have to go on with these damned quantum jumps, then I'm sorry that I ever got involved" - Erwin Schrodinger
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.
Need a Python, C++, Unix, Linux develop
# 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.
--
send all spam to theotherwhitemeat@ropine.com
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.
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.