Some miscellanea


I wrote an FAQ on The CAP Theorem. The aim is to definitively settle some of the common misconceptions around CAP so as to help prevent its invocation in useless places. If someone says they got around CAP, refer them to the FAQ. It should be a pretty simple introduction to the theorem as well. I think that CAP itself is a pretty uninteresting result, but it does at least shine a light on tradeoffs implicit in distributed systems. I have a couple of residual thoughts about failures rather than partitions that I might write up at some point in the future, but otherwise I hope the FAQ helps move the conversation on.

Impala and aggregation trees

I also wrote a quick answer on Quora about Impala’s execution trees, and how deeper trees help do aggregation more effectively. There’s a lot more of interest to write about planning, partitioning and scheduling queries.

Not so HotOS

Matt Welsh talks about what he wishes systems researchers would work on. I partially agree: there are few papers in the HotOS 2013 program that pass the “if this were true, a lot of our assumptions would be wrong” test. I don’t think that IO is an unworthy topic however, but the main problem with improving IO interfaces is inertia rather than want for better ideas. I hope that SSDs and / or flash-as-RAM will be forcing functions here. Otherwise his big topics are all worthy research challenges, but I have always seen HotOS as a venue for new ideas, not new topics – despite its name. If it really were intended to be a venue for the fashionable areas of study in systems it would have much less potential value.

Building distributed systems

Andy Gross (Basho VP Eng) gave a closing keynote calling for more reusable primitives in distributed systems. I couldn’t agree more (and have been gently complaining about this for years to anyone who would listen), although I think doing this right is not straightforward and requires a lot of careful thought about RPC mechanisms, libraries vs. services and much more. I have some thoughts on this that I want to wrap up in a blog post sometime soon.

Highly available transactions

Peter Bailis, a Berkeley PhD candidate, has some solid work on Highly Available Transactions, based on exploring the space of consistency models available to databases and finding that there are demonstrably useful consistency guarantees that can be made when availability is kept high. This is the right way to move on from all the CAP arguments – given that we are stuck with certain impossibility results, let’s map out the vast terrain that we can conquer.

Images are back

Thanks to those of you who bugged me about putting images back up. They should all (except one that’s causing me a bit of a headache) be back now, after I discovered copies of all in an dusty corner of my hard drive.

Real post with actual content coming in the next week or so!

in Note | 55 Words

“Well, I’m back.”

Astute readers may have noticed that this blog was unavailable for the past three-and-a-half months. The short reason for this was that the computer on which Paper Trail was hosted was on a boat in the Atlantic and it is surprisingly hard to get a good internet connection out there, let alone a power supply to the shipping crate it was in.

The long reason was that I have now moved across the ocean, from Cambridge to San Francisco, where I am living in order that the commute to Cloudera be a little shorter than 24 hours. My possessions finally arrived on Thursday – over three months since we shipped them – and we are finally getting everything in order, including getting this blog back online. I’m now hosted at Bluehost, and have transferred all the old posts over to the new WordPress installation. I don’t yet have access to the images, so unfortunately those wil have to wait, but most other things are in order. Please excuse the dust as I find out which links are broken.

The old address – – will still work, but the correct link is now our very own domain: Hopefully we will start showing up in Google again when the crawlers do their thing. Please update your rss readers – those of you who are still following and haven’t deleted my feed in disgust. Does anyone even still use rss readers anymore?

I am in the process of deciding what to write about for the next few posts. I still have the remainder of the theory of computation posts to write, which would be fun to do but is a bit of a departure from the systems focus. I never really fully explained Byzantine Fault Tolerance – at least, I never got as far as describing Zyzzyva and other modern systems. At the same time, some interesting stuff in systems research has happened since the blog went quiet – Google released the Go programming language which is intriguing for writing user-space systems software. SOSP 2009 happened, with some very cool papers which I really want to write about. And I’ve been busy myself – I was recently made a committer on the Apache ZooKeeper project, which is a distributed coordination system written by some engineers and researchers at Yahoo!, and is very cool. My largest contribution was a patch for ‘observers’ – which are listeners, in Paxos terminology – which help maintain the read performance of the cluster as the number of clients scales.

So, lots going on, plenty to write about, and some exciting possibilities coming down the queue. Good to be back.

in Note | 447 Words

Miss me?

I’ve been away from this blog for far longer than I hoped. I’ve got plenty of content queued up though, so in the next few days I should start to get my postings back in order. Rumours of my death are greatly exaggerated; of my gainful employment less so. That, clearly, has been taking up some time, but I’m getting into my groove now.

A small conciliatory nugget that regular readers of this blog might find interesting: a trademark Robinson monster post on Cloudera’s blog describing how to build a simple distributed queue with Apache ZooKeeper.

More on ZooKeeper and our usual distributed systems programming to follow.

in Note | 107 Words

In Which I Prove Employable

Although I try and keep personal information to a relative minimum on this blog, here’s some news that’s relevant. Recently I accepted an offer to start work at Cloudera, a young company in the San Francisco area. Initially I’ll be working from the UK, with a view to a permanent move out to California when timing and visas allow.

Hadoop is Cloudera’s business. Hadoop is an open-source implementation of Google’s MapReduce Cloudera provides support for Hadoop, and their own fully supported distribution of the Hadoop toolset. Hadoop allows very large scale distributed and parallel processing of huge data sets in a fault-tolerant and efficient manner. Data sets are getting bigger all the time, and there’s a mismatch now between the desire and the ability of companies to handle and process all those data. Cloud computing, at least in the form of dynamic provision of computing resources, and distributed processing technologies such as Hadoop are helping to make this problem tractable. Cloudera provides the expertise and the experience to help businesses make best use of this seriously powerful tech.

I’m joining, as you might expect, as a distributed systems engineer. There are plenty of interesting problems to attack, both in Hadoop and the ecosystem of technologies that support and extend it, such as HDFS, Hbase, Pig, Hive and ZooKeeper. Cloudera already has a killer team (see some of the press from the New York Times), and I’m really looking forward to being a part of it.

in Note | 245 Words