Distributed Databases, CAP, and BASE
Why distribute data?
A distributed database stores data across multiple machines connected by a network. The motivations are:
| Motivation | Explanation |
|---|---|
| Scalability | The dataset or workload is too large for a single machine. Adding more machines increases capacity. |
| Fault tolerance | If one machine fails, the service survives using replicas on other machines. |
| Lower latency | Data can be located physically closer to its users (e.g., serving European users from a European data centre). |
The cost of distribution: consistency
After an update is applied to one replica, there is a massive overhead in ensuring that all other replicas reflect the change immediately. If a user reads from a stale replica, they see outdated data.
There is a multitude of successively-relaxed consistency models that trade stronger guarantees for better performance:
- Linearizability (strongest, hardest to achieve)
- Sequential consistency
- Causal consistency
- Read-your-writes consistency
- Monotonic reads
- Eventual consistency (weakest, easiest to achieve)
The CAP theorem
Formulated by Eric Brewer in 2000, the CAP theorem states that a distributed database can provide at most two of the following three guarantees simultaneously:
| Guarantee | Meaning |
|---|---|
| Consistency | All reads return the most up-to-date data. Every read sees all previous writes. |
| Availability | All clients can find some replica of the data, even during failures. |
| Partition tolerance | The system continues to operate despite arbitrary message loss or failure of part of the network. |
It is impossible, with current technology, to achieve all three. In practice, network partitions are inevitable, so the real choice is between CP (consistency over availability) and AP (availability over consistency).
A system can sit anywhere on the edges of this triangle, but not at the centre.
Approximating CAP is the subject of the Part IB Concurrency and Distributed Systems course.
BASE: the alternative to ACID
When a system chooses AP over CP, it adopts the BASE model as an alternative to ACID:
| Letter | Term | Meaning |
|---|---|---|
| BA | Basically Available | The system prioritises availability over immediate consistency. It will respond to every request, even if the response might be stale. |
| S | Soft state | Stored values may change without application intervention, owing to eventual consistency updates or network partition recovery. The system does not need to be externally updated to change state — it changes by itself as replicas converge. |
| E | Eventual consistency | If update activity ceases, the system will eventually reach a consistent state. There is no guarantee of when this will happen, only that it will. |
Comparison
| Property | ACID | BASE |
|---|---|---|
| Consistency model | Strong, immediate | Eventual |
| Partition behaviour | May refuse requests (CP) | Continues serving (AP) |
| Application burden | Low — DBMS handles consistency | High — app must tolerate stale reads |
| Examples | PostgreSQL, MySQL (single-node) | DynamoDB, Cassandra, CouchDB |
Summary
- Distribution provides scalability, fault tolerance, and lower latency — at the cost of consistency.
- The CAP theorem says you can have at most two of Consistency, Availability, and Partition tolerance.
- BASE (Basically Available, Soft state, Eventual consistency) is the practical alternative to ACID for distributed systems.