Slashdot Mirror

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?

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?

AnonymousCow writes "At LinuxTag, an unbiased comparison of performance of FreeBSD, NetBSD, OpenBSD, Linux, and Solaris." I'll let Tim's comment on this story stand: "Unbiased is hard to claim - all tests can be seen as biased in their formulation - but this is thorough, with 45 slides and well-explained methodology -- BSD does very well ..."