Experience with ePaxos: Systems Research using Go

Writing our to-appear SOSP'13 paper on Egalitarian Paxos ("There is More Consensus in Egalitarian Parliaments") was a journey made more interesting because of our choice to use Go as the implementation language.

1.  It rocked, and it let us do some things in the evaluation that we likely wouldn't have in C++;
2.  It had a few drawbacks that we had to deal with, mostly with performance variation and optimization;
3.  Our community wasn't used to it and we got yelled at once by a reviewer (!).

[Note:  While I (Dave) am writing this post, please realize that the standard professorial disclaimer applies here:  When I say "we", I really mean, "the student who did all the work", who in this case is Iulian Moraru, a CS Ph.D. student at Carnegie Mellon.  If you think "woah, that's cool work", he's the one who should be credited.  But if you want to yell at someone for the strong opinions expressed here or the way they're expressed, yell at me.]

In to the details:

Huge positive:  Go made it straightforward to implement and compare, apples-to-apples, numerous Paxos variants.

Normally, you see systems papers implement their own system and compare to someone else's implementation of the competition, or perhaps implement something "standard" to compare against.  In ePaxos, we took a different tack:  As you can see from the source repository, there are multiple protocols all extending the "generic state machine replication" type.  The server simply instantiates one of these replica types, depending on its configuration, and things go from there.

To my knowledge, this is the most comprehensive comparison of Paxos variants done to date:  It compares standard "Multi-Paxos", ePaxos, Mencius, and Generalized Paxos, and Go made this possible.  The code isn't that tiny -- for example, the implementation of Mencius is 900 lines including whitespace -- but it's also not hideous.  We're one of only two implementations of Generalized Paxos that I know of.

As almost always happens in Go, the reasons for this non-hideousness were:

• Lack of nasty verbosity at the language level, helped by type inference for declarations and built-in maps with decent performance;
• Channels!  Building a distributed system in Go is a natural fit.  Messages arrive from the network, get sent internally across channels, get sent out, etc.  The select loops for this are clear.

Real Drawbacks of Using Go:  Mostly performance-related

We had to do a lot of performance optimization in order to match the speed of previously-published protocols and working systems such as Zookeeper.  In the end, we were able to do so, but it didn't happen on our first iteration.

• The performance of the built-in Go RPC is horrible and was our first bottleneck.  (Clarification added a bit later:  The bottlenecks we identified and fixed were due to the marshaling and unmarshaling, not the actual communication and method invocation.  I'm not sure where the split was between the two, because we abandoned both in order to use our faster version.)
  
  To overcome this, we implemented our own marshaling and RPC compiler.  It emits code that you then compile in, which emits a slight tweak on the existing go encoding/binary format (but supports variable-length arrays).  Fortunately, this wasn't too hard.  Dave is not a compiler person, but even so, it's only about 700 lines of code.  You can see an example of this by looking at the ePaxos message format and the automatically-generated marshaling code.
• ePaxos prioritizes the processing of already-started commands over new ones to keep queues smaller.  We found the implementation of this tricky, and based upon some older traffic to the golang-nuts list, we thought that the only way to do it was to duplicate our select loop.  But Go's channels saved the day in the end thanks to a tip from Russ Cox.  (To execute same select twice but change the assignment of the channel.)
• Getting the performance variation down was a little tricky.  In several spots, we had to think carefully (and experiment with some dead-ends) about how to reduce the amount of garbage we were generating.  We also had a longer-standing performance glitch resulting from waiting for some of the maps we use to reach their final size.  Nothing hard, and I think that many of these issues would have arisen in many languages.  We unfairly blamed the garbage collector a bit more than we should have, though GC still introduces performance variation that makes our experimentation a little harder.  But then again, we ran on EC2, which has its own wild mood swings.
• Also performance-related:  Goroutine scheduling bit us in a few ways, we think.  We still haven't fully tracked this down, but there were some odd cases where doing less work in a goroutine caused things to go faster or slower in ways that we had a hard time explaining, and we think it was due to the way the goroutines were being scheduled (or not).  It's nice to not have to think about explicitly managing the threads, but when we were trying to make the system fast, these issues kept turning up.

In the end, our implementation of all of the protocols is quite fast: Just over 50,000 tiny operations per second in a cluster without batching, and with 5ms of command batching, can hit over 400,000, though at the cost of higher latency.

Social Drawback of Using Go:  Perceived Credibility of a New Language

Using a different framework than what everyone is used to is a deliberate risk.  Interestingly, all of these reviews were from NSDI.  It may be that that community is less familiar with Go than the systems community.  But regardless, there's a lesson here that applies more broadly.  I recall Matt Welsh fighting hard against the perception of Java as a slow pig during the course of his own dissertation research, for example.

One reviewer wrote:

                      ===== Paper weaknesses ===== 

Evaluated using prototypes of protocols in Go

...

Correspondingly, I am very very skeptical aboutcomparing ePaxos with other Paxos variants using a fast prototyping language. 

Another noted:

... a lot of the work here looks like a class programming project in Go that has been substantially expanded.

And other:

Use of the Go programming language is odd. There was no discussion about the performance properties of Go, and I couldn't find any information online. It's possible the performance differences are due to oddities in Go.

I think that in 2014, these same reviewers wouldn't have made the same comments.  Go is becoming better known, and we're starting to see more and more case studies of people using it in high-performance production environments.  But it takes a while for that knowledge to diffuse.

Was it worth it?

Yes.  Quoting from some of the SOSP reviewers who accepted the paper:

"The evaluation is extensive."

"good evaluation of major cases to consider."

"Very thorough evaluation."

"The system is evaluated against all of its competitors." [listed as a strength]

Obviously, not all of that is Go - I know that Iulian put in a ton of effort getting everything working and running and re-running experiments on EC2.  But Go directly contributed to the thoroughness.

We aren't using Go for all of our projects, particularly those that are performance critical and/or involve things like cache, coherence, or TLB-level optimizations.  But in the case of a complex protocol such as Paxos (or ePaxos) in a field littered with different competitors, it proved a huge win.  We've of course open-sourced our implementations, and I hope we're able to grow the codebase into an easy-to-use way of comparing any new Paxos variant against all of the existing options.