Software Engineering Radio : CAP Theorem

On the way to work today I enjoyed an excellent episode of Software Engineering Radio which featured an interview with Eric Brewer, a VP of Infrastructure at Google,  probably more famous for his CAP Theorem.

In theoretical computer science, the CAP theorem, also known as Brewer’s theorem, states that it is impossible for a distributed computer system to simultaneously provide all three of the following guarantees:

  • Consistency (all nodes see the same data at the same time)
  • Availability (a guarantee that every request receives a response about whether it succeeded or failed)
  • Partition tolerance (the system continues to operate despite arbitrary message loss or failure of part of the system)

The discussion around “2 out of 3” was very thought-provoking and, at first, a little bit counter-intuitive.  If you don’t want to listen to the show, read though this page, which covers the important bits.

The easiest way to understand CAP is to think of two nodes on opposite sides of a partition. Allowing at least one node to update state will cause the nodes to become inconsistent, thus forfeiting C. Likewise, if the choice is to preserve consistency, one side of the partition must act as if it is unavailable, thus forfeiting A. Only when nodes communicate is it possible to preserve both consistency and availability, thereby forfeiting P. The general belief is that for wide-area systems, designers cannot forfeit P and therefore have a difficult choice between C and A. In some sense, the NoSQL movement is about creating choices that focus on availability first and consistency second; databases that adhere to ACID properties (atomicity, consistency, isolation, and durability) do the opposite.

This puts some of the current trends into perspective.

Scaling the Facebook data warehouse to 300 PB

Scaling the Facebook data warehouse to 300 PB

At Facebook, we have unique storage scalability challenges when it comes to our data warehouse. Our warehouse stores upwards of 300 PB of Hive data, with an incoming daily rate of about 600 TB. In the last year, the warehouse has seen a 3x growth in the amount of data stored. Given this growth trajectory, storage efficiency is and will continue to be a focus for our warehouse infrastructure.

On scalability of MySQL

Anyone who says that MySQL is not scalable has no idea.  Facebook is one of the examples for a large deployment of MySQL:

How big is Facebook’s Internet infrastructure? Facebook VP of Technology Jeff Rothschild provided some details in a panel at the recent MySQL user conference. Rothschild says Facebook is now running 10,000 servers, including 1,800 MySQL servers that are overseen by just two database administrators.

Facebook recently surpassed 500,000,000 users – half a billion!

Bloat is bad for you and your code

Steve Yegge has posted yet another of his excellent (and long) rants.  This time he talks about the size of code and why one should jump out of its skin to keep it minimal.

 Most programmers have successfully compartmentalized their beliefs about code base size. Java programmers are unusually severe offenders but are by no means the only ones. In one compartment, they know big code bases are bad. It only takes grade-school arithmetic to appreciate just how bad they can be. If you have a million lines of code, at 50 lines per “page”, that’s 20,000 pages of code. How long would it take you to read a 20,000-page instruction manual? The effort to simply browse the code base and try to discern its overall structure could take weeks or even months, depending on its density. Significant architectural changes could take months or even years.

As I said, it’s a long piece. But it’s worth every paragraph. Even though some Java programmers might be slightly offended by the article, I’m sure it’s not intentional.