February 27, 2009

Clustering and CAP Theorem

When designing an application for clustering one should first be aware of the CAP (Consistency, Availability and Partitioning) theorem. The theorem states that you can only have two of the three CAP properties at the same time.

The Consistency means that all users see the same set of data, even when data updated or deleted. This is normally achieved with storing data to a database and using transactions.

Availability is achieved through replicating data, so that data is always available even in case of failure.

The last, Partitioning, means that the system is partitioning tolerant, i.e. the system holds when it is distributed over several servers and machines.

So which one should go? Well when building highly loaded applications as Google or Amazon the natural answer is Consistency, because letting the system not be available during failure or being not responsive during high load is not a options. This is quite interesting because most programmers are raised with the idea of using a database as a foundation for an application. And this idea must now go. Or? Well it is not so black and white.

The main key of building clustered application is twofold:
  • Asynchronous communication. E.g. Amazon has a separate service displaying what books other people has also bought. Failure of this service should not hinder the rest of the page to be rendered.
  • Brake down your application and analyze each part individually according to CAP properties. Does payment must be consistent? Probably. Does user information needs to be consistent. Probably not. Etc.
After you analyzed your application into different clustering functions you keep these data separated, because they will be deployed differently and independently.

So to achieve an High Availability and Partitioned Tolerant application is through scaling out, I.e. using more machines and using:
  • Stateless data, i.e. the applications server only holds request data.
  • Replicate read intensive data through a master/slave setup.
  • Caching data.
  • Sharding database, i.e. using multiple databases and manually decide which tables goes into which database.

No comments: