Thursday, September 21, 2006

Boxwood from Microsoft Research

If you enjoyed the Google Bigtable, Chubby, and GFS papers, you might also enjoy a recent paper out of Microsoft Research, "Boxwood: Abstractions as the Foundation for Storage Infrastructure".

The basic idea is to create a distributed data store over a small cluster. It is similar in motivation to Bigtable and GFS, but lower-level. From the paper:
The overall goal of the Boxwood project is to experiment with data abstractions as the underlying basis for storage infrastructure ... [that includes] redundancy and backup schemes to tolerate failures, expansion mechanisms for load and capacity balancing, and consistency maintenance in the presence of failures.

The principal client-visible abstractions that Boxwood provides are a B-tree abstraction and a simple chunk store abstraction provided by the Chunk Manager.
It is worth noting right away that Boxwood is a research project, not a deployed system. The Boxwood prototype runs on a small cluster of eight machines. GFS and Bigtable run on tens of thousands of machines and provide the backend for many of Google's products.

It is also worth noting that they have different standards for failure tolerance. For one of several examples, the Boxwood paper says that "failures are assumed to be fail-stop". Contrast that with the experience of the folks at Google working on Bigtable:
One lesson we learned is that large distributed systems are vulnerable to many types of failures, not just the standard network partitions and fail-stop failures assumed in many distributed protocols.

For example, we have seen problems due to all of the following causes: memory and network corruption, large clock skew, hung machines, extended and asymmetric network partitions, bugs in other systems that we are using (Chubby for example), overflow of GFS quotas, and planned and unplanned hardware maintenance.
In any case, the Boxwood paper is an interesting read. This is work at Microsoft that may follow a similar path to GFS and Bigtable.

See also my previous post, "Yahoo building a Google FS clone?", that talks about Yahoo's involvement in Hadoop.

See also the Eclipse project at Microsoft Research.

Update: Mary Jo Foley mentions another Microsoft Research project called Dryad and quotes Bill Gates as saying, "[Google] did MapReduce; we have this thing called Dryad that's better." Unfortunately, there appears to be very little public information on Dryad; I can find no publications on the work.

Update: A year later, Microsoft Researcher Michael Isard gives a Google Tech Talk on Dryad with plenty of details.


Sorin said...

Isn't this very similar to Amazon's S3 web service? Which is not a research project anymore, but a real-world implementation.

Greg Linden said...

I do not think so, no.

My understanding is that Amazon S3 does is not trying to be a high performance clustered filesystem, a candidate for replacing traditional fileservers and usable for rapid access to data. As such, I do not think S3 is seeking to have the same level of performance or reliability as these other systems.

I could be wrong. Do you know of anyone using S3 for data mining or some other high performance, data-intensive operation? I'd be amazed, but please let me know if it is happening.

Sorin said...

I don't know for sure how S3's speed compares to traditional filesystem servers, BUT:

1. S3 is reliable (by replicating data)

2. They claim to be suitable for high-availability applications. It is being used by YouOS as a fileserver (see the "Success stories" at:

My guess is that they are as reliable and fast as any remote-storage system can be.

Anonymous said...

I believe Powerset uses S3. As a matter of fact, they use Hadoop on top of S3. Nice, eh? I'm curious to see what Powerset will turn into.
There are S3 success tories on their blog.

Greg Linden said...

Really? Hadoop on top of S3? That is surprising.

Where is the Powerset weblog? I can't seem to find it. I'd like to see more about what they are doing there.

burtonator said...

I would expect the latency of S3 would be too high for many applications. Assuming you kept the amount of S3 calls small or had thousands of threads performing smaller calls on top of S3 you might be ok....

It just seems easier for some people to deploy their own DFS ...

Unfortunately the OSS tools still don't exist to do this stuff right...