The CAP theorem states that a distributed data store (database) can only guarantee 2 of the 3 following: consistency, availability, and partition tolerance.

What is Consistency?

Consistency means that all read requests will return the same, most recent, writes to the database. In other words, reads will be consistent regardless of which node the data is read from. A database will not return a requested value until it can guarantee it contains the most recent data. This can cause timeouts or errors when the data being read is not in a consistent state.

What is Availability?

Availability means that all read requests will receive a non-error response. However this response is not guaranteed to have the most recent data. Often systems that guarantee availability are “eventually consistent”.

What is Partition Tolerance?

“Partition” here refers to a network partition (network split). Network partitions can be thought of as anything that will cause nodes in a system (that haven’t completely failed) from communicating with each other.

The Choice between Consistency vs Availability

All distributed databases can expect network partitions, and therefore are generally (but not always) partition tolerant. This means that most distributed databases must choose to guarantee either consistency or availability.

Are both Consistency and Availability possible?

Distributed databases that guarantee partition tolerance can in fact also guarantee consistency and availability when there are no network partitions. Systems like these will sometimes claim “effective” guarantees on consistency and availability when the possibility of a network partition is extremely rare.

Also databases that are not partition tolerant or that run on a single server can also guarantee both consistency and availability. This is common for RDBMS databases.

Examples of CP Databases

Databases that guarantee consistency and partition tolerance: Hbase, Redis, mongoDB, BigTable

Examples of AP Databases

Databases that guarantee availability and partition tolerance: DynamoDB, CounchDB, Cassandra, Voldemort

Examples of CA Databases

Databases that guarantee consistency and availability: MySQL, SQL Server