Google Blogoscoped

Thursday, July 24, 2008

Google Chubby and the Paxos Algorithm

Nope, this is not the title of a children’s book (though it would be great as that!). Quote Google:

Chubby is a fault-tolerant system at Google that provides a distributed locking mechanism and stores small files. Typically there is one Chubby instance, or “cell”, per data center. Several Google systems – such as the Google Filesystem (GFS) and Bigtable – use Chubby for distributed coordination and to store a small amount of metadata.

Chubby achieves fault-tolerance through replication. A typical Chubby cell consists of five replicas, running the same code, each running on a dedicated machine. Every Chubby object (e.g., a Chubby lock, or file) is stored as an entry in a database. It is this database that is replicated. At any one time, one of these replicas is considered to be the “master”.

Chubby clients (such as GFS and Bigtable) contact a Chubby cell for service. The master replica serves all Chubby requests. If a Chubby client contacts a replica that is not the master, the replica replies with the master’s network address. The Chubby client may then contact the master. If the master fails, a new master is automatically elected, which will then continue to serve traffic based on the contents of its local copy of the replicated database. Thus, the replicated database ensures continuity of Chubby state across master failover.

The first version of Chubby was based on a commercial, third-party, fault-tolerant database; we will refer to this database as “3DB" for the rest of this paper. This database had a history of bugs related to replication. In fact, as far as we know, the replication mechanism was not based on a proven replication algorithm and we do not know if it is correct. Given the history of problems associated with that product and the importance of Chubby, we eventually decided to replace 3DB with our own solution based on the Paxos algorithm.

If this made sense to you, you may be interested to read the full PDF from 2007 in which Tushar Chandra, Robert Griesemer and Joshua Redstone describe the engineering challenges building a Paxos algo based fault-tolerant database, which “proved to be non-trivial,” as the paper says. To find out more about Chubby itself, another PDF from 2006 is available. As Greg Linden once noted, it includes amusingly direct semi-rants by Google’s Mike Burrows (co-creator of the Burrows-Wheeler transform used to optimize compression efficiency):


Blog  |  Forum     more >> Archive | Feed | Google's blogs | About


This site unofficially covers Google™ and more with some rights reserved. Join our forum!