Bit Mountain

I have been working on a project in the family and church history department called Bit Mountain. Bit Mountain is a distributed system designed to reliably store petabytes of archival information. I believe I have discovered and solved the primary issues. Some of the issues I have encountered:

- Standard replication is not reliable enough. Statistically, even if we kept two or three copies of all the data and refreshed the copies yearly, we would still lose a lot of data. The chances are too high that all of the copies would be lost. Bit Mountain employs a better technique called error correction, which yields far greater statistical reliability.

- We can't rely on system administrators to replace media. Our staff is already overtaxed. Therefore, Bit Mountain repairs itself when media is lost. It rebuilds the lost files and puts them on new media. During the rebuild, Bit Mountain transparently recovers files on the fly as they are requested.

- We have to choose the media carefully. Hard drives are easy but consume significant power. DVDs don't hold much data--we would need 200,000 to build a petabyte. Tapes require a big robot. MAID (massive array of idle disks) is my favorite technology of the bunch, but I don't have access to any MAID systems to test. Bit Mountain currently uses spinning disks but it should be possible for it to use any of the other technologies.

I have built several small Bit Mountain clusters now and they are all working well. One of the clusters even weathered the simultaneous loss of 8 of the 20 hard drives without any downtime or loss. The hardware in the two nodes holding the drives became unstable, causing the nodes to crash and eventually shut down, while the cluster kept the data 100% intact and initiated recovery. I don't know of any RAID system that can achieve that level of reliability.

Does massive and highly reliable yet inexpensive distributed data storage interest the people in this group? Speak up!

I want Bit Mountain to gain more exposure and feedback from others who are solving similar problems. As nice as Bit Mountain might be, I don't want our department to use a system that no one else uses. Therefore, I want a community around the software so that archivists can help each other and build a great system for archiving data.

I believe that making Bit Mountain open source is the best way to start that community. Unfortunately, I'm having trouble getting attention from the people who could authorize an open source release. I believe some of them don't see the wisdom in releasing open source software. What should I do?

I have no idea what you should do. However, within the past six months I have read several articles about Google and Microsoft buidling huge data centers. They must have the same issues. I wonder how they are solving the problem?

Shane, get authorization from your managers on what technical information you can or cannot share and let's get a dialog around this. We may be able to come up with some interesting ways that the community can contribute and this may help you argue the case of open source. The project sounds very interesting.

Tom

This is cool indeed. I think I'm gonna show a few of my friends that have been in the business quite a bit longer and see what they think about the technology. They stradle business and open source pretty well.

I've got a few of questions:

- What are the single source failures that could occur that would take out the system? Keep in mind, that not all devices fail "dead" but may in fact malfunction in such a way as to scramble data.

- Second, this sounds like a fancier array. The big problems with arrays is that they don't protect from things like viruses, accidental erasure or other accidents or malfunctions of the application software. So what is the backup strategy?

- When you say that you are not going to rely on the media being replaced, are you saying that you're not relying on it being replaced to begin rebuilding or that it will never be replaced?

- If you are going to allow for replacement of media, are you going to be able to accommodate different models of drives? Any given drive model only seems to last a few years before it's discontinued. Can the system take a mix of 500GB, 750GB or whatever size drives you use now and expect to be available in the future? What about drive interface? Right now we're transitioning from IDE to SATA. Maybe you're dodging that by going with SCSI, but can SCSI last forever? How are you future proofing the product?

- The last question is really a social engineering question. How do you prevent all your safeguards that create a high reliability environment from fostering complacency such that the system no longer gets the service response that you specify as part of the assurance that it won't fail?

How much storage is lost to redundancy using your method?

tomw wrote:Shane, get authorization from your managers on what technical information you can or cannot share and let's get a dialog around this. We may be able to come up with some interesting ways that the community can contribute and this may help you argue the case of open source. The project sounds very interesting.

Thank you. I presented a paper on it last year at the family history workshop at BYU, so quite a bit of technical information has already been released. I am especially interested in finding out what the community would like to do with it.

mkmurray wrote:This is cool indeed. I think I'm gonna show a few of my friends that have been in the business quite a bit longer and see what they think about the technology. They stradle business and open source pretty well.

That would be helpful, especially if some of your friends work at large companies. While I've witnessed personally how a small company can make open source work in their favor, big corporations seem to have a lot more trouble with the idea of open source.

RussellHltn wrote:I've got a few of questions:

- What are the single source failures that could occur that would take out the system? Keep in mind, that not all devices fail "dead" but may in fact malfunction in such a way as to scramble data.

- Second, this sounds like a fancier array. The big problems with arrays is that they don't protect from things like viruses, accidental erasure or other accidents or malfunctions of the application software. So what is the backup strategy?

- When you say that you are not going to rely on the media being replaced, are you saying that you're not relying on it being replaced to begin rebuilding or that it will never be replaced?

- If you are going to allow for replacement of media, are you going to be able to accommodate different models of drives? Any given drive model only seems to last a few years before it's discontinued. Can the system take a mix of 500GB, 750GB or whatever size drives you use now and expect to be available in the future? What about drive interface? Right now we're transitioning from IDE to SATA. Maybe you're dodging that by going with SCSI, but can SCSI last forever? How are you future proofing the product?

- The last question is really a social engineering question. How do you prevent all your safeguards that create a high reliability environment from fostering complacency such that the system no longer gets the service response that you specify as part of the assurance that it won't fail?

Good questions.

- The system is not very susceptible to data corruption, missing sectors, or hardware glitches in the storage nodes, since it periodically compares the data with an MD5 hash (any other hash is also possible) and automatically falls back to other storage nodes if the primary node does not reply within a configurable time limit. The only parts administrators should worry about are the network and the central database, although it's possible to build a redundant network and the database is replicated asynchronously.

- The right backup strategy is to build two repositories in separate locations and keep them in sync.

- When Bit Mountain decides a storage device has failed, it stops using it, marking it offline and unhealthy. An administrator can choose to bring that device back into service by marking it online and healthy, but Bit Mountain will never do that on its own.

- Each storage node in Bit Mountain is an ordinary computer with its own storage media and filesystems. Bit Mountain works at a level that's independent of media size, format, or electrical interface. Even if we all switch to flash drives and Infiniband, Bit Mountain may not need any changes.

- If the Bit Mountain health monitor process stops, or the system runs out of places to store recovered files, the probability of losing data rises. Therefore administrators are still not absolved of their responsibility to run Nagios.

gblack wrote:How much storage is lost to redundancy using your method?

You get to choose! There's a simple pair of numbers you need to set up: the number of data and error correction segments per chain. Then the system will maintain the files at the level you specified. I have a spreadsheet that helps you choose those numbers. I have projected that if you choose 20 data and 10 error correction segments, put the data on hard drives, let Bit Mountain verify the media once a week, and always ensure Bit Mountain has extra space for recovered data, you can be quite confident the data will remain perfect for 1000 years.

Note that simple duplication requires you to buy 1 GB extra for every 1 GB of data, while a 20 + 10 Bit Mountain configuration requires only .5 GB extra for every 1 GB of data. In fact, the Bit Mountain configuration is statistically far more reliable. It's surprising, but I've spent weeks on the math and I believe it's correct.

Michael wrote:I have no idea what you should do. However, within the past six months I have read several articles about Google and Microsoft buidling huge data centers. They must have the same issues. I wonder how they are solving the problem?

Google is solving this with simple replication across ordinary servers. Bit Mountain can implement simple replication as well, but I believe error correction is a better solution for archiving data.

Shane Hathaway wrote:you can be quite confident the data will remain perfect for 1000 years.

Are you saying that it will only fail once in 1000 years or the risk of failure is very low even over the course of 1000 years?


Another question - are you keeping stats of the equipment that fails? I assume that you're expecting that failed components are changed out within a certain time frame, and that drives will fail at a certain rate. However, drive failure isn't random. As the collection of drives approach end of life, the number of failures in a unit of time will go up. Possibly quite dramatically. (I'm not sure if anyone gives the standard deviation to the MTBF.) How will you monitor the situation to warn that the statical probability of failures is reaching an unacceptable risk and that either parts must be changed more quickly or that aging components need to be proactively changed?

As far as I'm concerned, the MTBF is a educated guess based on accelerated testing and reality might well be different. The question is how much are you betting the farm on the manufacture supplied MTBF number?

RussellHltn wrote:Are you saying that it will only fail once in 1000 years or the risk of failure is very low even over the course of 1000 years?

The latter.

RussellHltn wrote: Another question - are you keeping stats of the equipment that fails? I assume that you're expecting that failed components are changed out within a certain time frame, and that drives will fail at a certain rate.

I've seen how often failed components need to be replaced in a big SAN. Emergencies seem to happen often. But Bit Mountain isn't like that; it doesn't care if you leave failed components in the system. What's important is always having spare space. As long as Bit Mountain has enough space to recover, you can postpone drive replacement as long as you want. Even lack of recovery space is not really an emergency, though it's an integrity risk.

RussellHltn wrote: However, drive failure isn't random. As the collection of drives approach end of life, the number of failures in a unit of time will go up. Possibly quite dramatically. (I'm not sure if anyone gives the standard deviation to the MTBF.) How will you monitor the situation to warn that the statical probability of failures is reaching an unacceptable risk and that either parts must be changed more quickly or that aging components need to be proactively changed?

As far as I'm concerned, the MTBF is a educated guess based on accelerated testing and reality might well be different. The question is how much are you betting the farm on the manufacture supplied MTBF number?

I don't yet have a system for tracking expected media lifetime, since it seems to be quite unpredictable. For example, I have an 11 year old desktop hard drive that has gone through periods of 24/7 operation yet still works great. So currently I'd rather base the calculations on pessimistic estimates, then just let the storage devices fail over time. If the failure rate turns out higher than expected, then we'll put the actual failure rate into the spreadsheet and it will tell us whether we need to increase the number of error correction segments to compensate. This is certainly an area where we need more experience to make a good judgment.

I would also be interested in seeing bit mountain open sourced.

I currently have a large personal data vault spread across two raid5 servers that are nearing capacity. Everything is dumped semi-randomly in directories, and I was looking into setting up a new monolithic storage system where I can store files with associated metadata in a reasonably fault tolerant way. The best (and cheapest) method publicly available seems to be Mogile, which would allow me to store files in an easily expandable archive, and I can add my own metadata to the mogile database. However, if you store things at a minimum replica count of X and happen to lose X disks before being able to replace them, there is a significant chance you've lost some files. Since I'm doing this as a home user, I'm trying to do it as cheaply as possible. A replica count of 2 is pretty much my maximum. Between my family and my job, there are times when I won't be able to repair any failures for weeks at a time.

This is why Bit Mountain is extremely interesting to me. If I understand your paper correctly, with 10 data segments and 5 error correction segments, you can lose any 5 of those 15 segments, and still have lost no data. That is simply fantastic and I'm interested to see how it works. Not only is the system several orders of magnitude more fault tolerant than mogile, it will only take 75% of the disk space that mogile would.

Unfortunately, since you've been talking about this for over a year, I'm betting bit mountain isn't going to be released anytime soon. Since I'm hoping to setup my new system in the next two weeks, I'll most likely end up going with mogile.

Thanks, Don

Yes I remember reading and studying up on this about 1 1/2 years ago when it was in research and they had a small prototype model. Anyway through this time I have always mentioned to friends and acquaintances as the next jump in storage technology IF people adopt it. Similar to the protein cube http://ieeexplore.ieee.org/Xplore/login ... 897894.pdf which could store around 1 TB on a sugar cube size.
What you need it content that you can put on a device that uses an appreciable amount of room. For example, if I backed up all the computer in our house I would fill up about 700 GB. (This is a full disc image backup without compression) But since a HVD holds roughly 3 TB I would be wasting 2.3 TB if you had to burn the disc all-at-once.
Mostly I think these discs will go to businesses that need to backup their servers until personal information becomes large enough to occupy at least 75% of the disc (roughly 2.25 TB) and since Hard Drives can't even hold that much information yet (Largest I've seen was 1 TB External) it will take awhile for people to use this technology.

As a personal observation, I think that the gaming industry will be the first to use these drives since I am sure they can come up with a way to get HD Video and HD textures into their games to fill up 3 TB:D

Shane Hathaway wrote:Good questions.

- The system is not very susceptible to data corruption, missing sectors, or hardware glitches in the storage nodes, since it periodically compares the data with an MD5 hash (any other hash is also possible) and automatically falls back to other storage nodes if the primary node does not reply within a configurable time limit. The only parts administrators should worry about are the network and the central database, although it's possible to build a redundant network and the database is replicated asynchronously.

FYI, cryptographers are recommending that new systems no longer use md5. I would recommend SHA1 as a minimum, or, even better, SHA512. Even with a 128 bit hash, the odds of a colision are extremly small, but since you are designing a system that is supposed to last for decades, you may as well use the best technology you can.

Just a thought.

Aaron

SHA1 has been found this year to have collisions and is being phased out for SHA256 at minimum.

I ran across an interesting article today: Why RAID 5 stops working in 2009. The premise of the article is that as drives get bigger, one is more likely to encounter/cause successive drive failures as the system attempts to rebuild from the first disk failure.

What impact, if any, does this pose to Bit Mountain?

A follow-up question - given the vast amount of data, it stands to reason that some parts of the data may never be accessed in years. How would one know if the data is starting to go corrupt unless all the data is accessed frequently enough to detect when that part of the data is starting to go? Or to put it in other words, how long could a drive failure(s) go undetected? If they are not detected and corrected soon enough, one could end up going beyond what the system can recover from.

Correct me if I'm wrong. If I read things correctly, you can set Bit Mountain to verify integrity on a regular basis. That way it will verify truly "archived" files even when they are not accessed to fix any inconsistencies that may have cropped up. I liked the article, Russell. One of my instructors a couple of years ago actually did the math for us, and I've actually experienced what the author talks about. I may be working on a project that might require Bit Mountain or a similar solution here in the future. I like the concept. I'm going to definitely keep my eye on this project.

Fascinating project. I am wondering, however, about a couple of things.

(1) If the data is to remain intact for 100+ years, how will Bit Mountain handle changing data media and changing computer architectures, programming languages, etc? For example, will Python still be a viable programming language in 20, 30, or 100 years?

(2) What about software errors? Some have approached this through Byzantine fault recovery methods; "shells" of redundancy in the software. Given that you'll have to update or probably re-write Bit Mountain every few decades, and a software error could be catastrophic in those transitions, how would you handle it?

I hope Bit Mountain survives and prospers. Again, it's a fascinating project.

-Rod

RussellHltn wrote:Another question - are you keeping stats of the equipment that fails? I assume that you're expecting that failed components are changed out within a certain time frame, and that drives will fail at a certain rate. However, drive failure isn't random. As the collection of drives approach end of life, the number of failures in a unit of time will go up. Possibly quite dramatically. (I'm not sure if anyone gives the standard deviation to the MTBF.) How will you monitor the situation to warn that the statical probability of failures is reaching an unacceptable risk and that either parts must be changed more quickly or that aging components need to be proactively changed?

According to the Stat's class I took, the failure distribution is usually modeled as an exponential decay function. One feature of such a distribution is that the remaining life of a particular device is independent of the history of the device. Assuming that this distribution is a reasonable model of real failures, there is no increased risk due to using many similar devices of similar age. This distribution also has no standard deviation.

cannona wrote:FYI, cryptographers are recommending that new systems no longer use md5. I would recommend SHA1 as a minimum, or, even better, SHA512. Even with a 128 bit hash, the odds of a colision are extremly small, but since you are designing a system that is supposed to last for decades, you may as well use the best technology you can.

Just a thought.

Aaron

I don't believe that cryptographic attack of the hash is relevant to this project. It sounds like the hash is used for integrity check against accidental errors rather than malicious modification. The cryptographic vulnerability is relevant to the latter, but not the former.