The CAP Theorem for Distributed Database Systems

Introduction

There’s a well known computer science theorem proposed by Eric Brewer that says for a database with distributed data you can only promise two out of the following three qualities:

• Consistency
• Availability
• Partition tolerance

This is very abstract and the terminology is not exactly intuitive so in this article we’ll do our best to break this theory down from abstract to more real world talk and examples. This theorem can will make you think about your database architecture in terms of what your application really needs and the sacrifices it might have to make to achieve those.

Defining CAP Terminology

Let’s get some basic definitions out of the way so we can be on the same page as we move forward talking about this theorem.

CAP – Consistency, Availability, Partition Tolerance

• Consistency – All your data servers have the same data, so you can query any server in the system and get the exact same data.
• Availability – Every request to the data servers gets a response. If one server is busy, it gets routed to another that is able to respond.
• Partition Tolerance – The ability for the system to continue working even if there are network failures and some of the servers can’t communicate.

Underlying Assumption – P is Impossible

In a distributed database system your data is split up over different servers and those servers talk to each other over a network so that they can maintain the same set of data. The problem is that networks break and so we assume that it will always communicate, ie we can’t have a perfect network. In terms of this theory that means that in the real world you have to sacrifice Partition Tolerance. If the perfect unfailing network did exist then we wouldn’t have a problem attaining Consistency and Availability, but this is the real world built upon physical wires that fail and so we assume that it will fail.

If P is Impossible, What are our Choices?

Since we’ve given up on Partition Tolerance the theorem says that we now have to choose between Consistency and Availability.

You can choose to have Availability where your application can satisfy all the incoming requests but it CANNOT guarantee that the data is the most recent.

What does your application need?

If your application is a social media site and does not need to have the most recent data at all times then you may want to choose Availability. Does it matter that your users sees a post after a 30 second delay? If not, then you might prefer Availability, because you prioritize that your users can access data even if it is not the most up to date data.

If on the other hand your application requires that every read to the database be the absolute most recent data then you’ll have to sacrifice Availability and choose Consistency. Some requests will have to error out due to the information not being able to be guaranteed that it is the absolute most recent.

The Choices Made by Relational and NoSQL

Database tech like SQL and other relational database systems designed with ACID prioritize Consistency. On the other hand most NoSQL databases prioritize Availability.

Conclusion

We believe examining this theorem in terms of your application is an excellent exercise and helps you to evaluate the priorities of your application. If you have a distributed data system examine your architecture and understand which sacrifice you are making.

MongoDB, CockroachDB, and Postgres are all great database tech today that make our database architectures extremely robust but as we discussed they are not perfect. We have no perfect network and there is always “user error”. If you are moving to a production environment and want to discuss the best options for your application please don’t hesitate to reach out to us at Object Rocket.