Fault-Tolerant File Storage

For Marvin Theimer, it all started with an earthquake. The aftermath of 1989’s massive Loma Prieta earthquake in Silicon Valley “was sort of surreal,” Theimer remembers. “I got in my car and had my radio on … silence! The radio stations within a 20-mile radius were out.”

And so were almost all the computers.

That earth-shaking experience got Theimer, then an operating systems researcher at Xerox Palo Alto Research Center, thinking about how to make computer file storage systems radically more fault tolerant. His work has helped to lead to Farsite, a fail-safe storage technology being created at Microsoft.

Backup to the Future

Businesses typically back up their critical data, but individuals typically don’t. And a catastrophe such as an earthquake could wipe out all of your computer files-and months or even years of work. Even if you’ve backed up your data, it’s inaccessible until you upload it to a replacement system. And in the worst case, you keep your backups right next to your computer and they’re lost as well.

So how do you solve the problem? By storing your data not just on your PC and your friendly local server but on many networked PCs, Theimer says. That way, even if 99 out of 100 machines are destroyed or rendered inoperable, there is still one PC that has all of your files stored-safe and easily recoverable.

Moreover, your distributed file storage system should not rely on a central server, not even to locate copies of files. “We think we can design these systems so you don’t have to have those back-end servers,” says Theimer.

Making It at Microsoft

Working as a senior researcher at Microsoft Research in Redmond, WA, Theimer hooked up in the late 1990s with systems software researcher Bill Bolosky. With Bolosky as team leader, a group of half a dozen researchers defined four key requirements for the system, dubbed Farsite:

• Provide highly available and reliable file service while running on normal desktop computers
• Ensure that users’ data are secure from others, including the users of the computers that store it
• Be automatically and adaptively self-configuring and self-tuning so that it’s able to respond to individual system failures and changes in usage patterns
• Work without a central server or central administrator

Wide Open Spaces

The researchers analyzed users’ personal hard disks within Microsoft and discovered that most were nowhere near full. In fact, they “are more than half empty and getting bigger all the time,” Bolosky says. Examining this three times over two years, they discovered that the percentage of users’ disks that remain unused is increasing, particularly as the size of new hard disks grows.

Furthermore, Bolosky predicts that drive manufacturers could produce terabyte-sized, half-height hard disks that would sell for less than $500 by 2003.

So why not take advantage of all that “wasted” space? That’s exactly what the prototype Farsite does.

To assure that each user’s files are only available to those who should see them, Farsite incorporates file encryption. That way, even if the files are stored on a “malicious” user’s system, they will still be secure. “We’re using fairly strong ciphers-RSA with big key lengths-and they are signed when they’re encrypted,” says Bolosky.

In addition, if a malicious user wants to gum up the works by deleting the other user’s files, all that is destroyed are the copies of those files stored on one machine. Copies on other machines remain safe.

Better than Servers

Because Farsite stores copies of a user’s files on multiple machines, that also makes it more network fault tolerant than a centralized server system. If there is a network fault that blocks access to one machine where the user’s files are stored, the odds are that another machine with the same files remains accessible. The files also remain accessible if some users turn off their machines at night.

Another benefit of storing files in multiple places is that it can help avoid the access bottlenecks inherent when a lot of users try to access their files on a single server simultaneously.

The Farsite meta-directory (which stores all file locations) functions similarly but does not need to be replicated to as many machines in order to provide reliability and fault tolerance.

When a new machine joins the group, its files are automatically replicated to other PCs’ disks. Farsite is smart enough to avoid copying duplicate files to the same disk and to continuously rebalance disk loads so that no one user’s disk drive suddenly fills up.

Farsite also promotes simplicity in use. Farsite appears as merely another disk drive-such as F:-with all of the complexity hidden from the user.

Built to Scale

Don’t expect to see Farsite in Windows XP or its follow-on systems any time soon. The current version has only been tested with about a dozen machines, with a more extensive test on 150 to 200 PCs planned for the near future.

Researchers say, though, that it conceivably could support up to 100,000 machines. In time, Farsite will be “the world’s largest, server-scalable, fault-tolerant file system,” predicts Bolosky. “[Ultimately,] we want to use hundreds of millions of machines.”