Consistency and consensus
How to build fault-tolerant systems? Which keeps running even if some parts are faulty.
Consistency guarantees
Most databases provide eventual consistency, which means that if you stop writing, and wait for some time, all read operations will return the same results on all nodes. Inconsistency is "temporary". It is a weak guarantee.
Stronger guarantees can be achieved, but they don't come for free: less performance or less fault-tolerant to name a few.
In an eventually consistent database, if you ask two different replicas the same question at the same time, you may get two different answers.
Typical eventually consistent database:
Linearizability
Linearizability is also known as atomic consistency, strong consistency, immediate consistency, or external consistency.
In a linearizable system, as soon as one client successfully completes a write, all clients reading from the database must be able to see the value just written. It's a recency guarantee.
After a value has been set and one node returned a successful read operation with this new value, all other nodes are obliged to return this value.
Implementation
- Not linerarizable
- Multi-leader replication
- Leaderless replication (demonstration)
- Potentially linerarizable
- Single-leader replication: Not supported by all databases
- Linearizable
- Consensus algorithm (eg. Zookeeper or etcd)