ddia-Chapter 9-Consistency and Consensus
Last updated: 2020-09-14 16:54:47
Last updated: 2020-06-18 22:43:47
This chapter took me three months to finish.
In a distributed system, it is important to have only one leader and for every node to recognise it. If two nodes both believe they are the leader, the situation is called a split brain and often causes data loss. Correctly implementing consensus helps avoid this problem.
Transaction isolation primarily avoids race conditions caused by concurrent transactions, whereas distributed consistency is about coordinating replica state in the presence of latency and failures.
Consistency guarantees
Eventual consistency: if you stop writing to a database and wait for an unspecified period, eventually every read returns the same value. In other words, inconsistency is temporary and ultimately resolves itself, assuming every network failure is eventually repaired. Eventual consistency is also called convergence.
Distributed consistency models have some similarities to the hierarchy of transaction-isolation levels discussed earlier.
Transaction isolation primarily avoids race conditions caused by concurrent transactions.
Distributed consistency is about coordinating replica state in the presence of latency and failures.
Linearizability
The core idea of linearizability is to make a system’s database appear to have only one copy and to make every operation atomic.
If a read concurrent with a write may return either the old or new value, the register is called a regular register.
Linearizability and serializability
Serializability is a transaction-isolation property: each transaction may read and write multiple objects (rows, documents, or records). It ensures that transactions behave as if they ran one at a time in some order, each completing before the next began. That order may differ from their actual execution order.
Linearizability is a freshness guarantee for reads and writes to a register—a single object. It does not group operations into transactions and therefore does not prevent issues such as write skew.
Although they overlap in some ways, they solve unrelated problems: transaction isolation avoids race conditions caused by concurrent transactions, while distributed consistency coordinates replica state under latency and failure.
Situations that rely on linearizability:
Locking and leader election. A system using single-leader replication must ensure that it has one true leader, rather than several in a split brain. One election method uses a lock: each node tries to acquire it at startup, and the successful node becomes leader. Regardless of how the lock is implemented, it must be linearizable; every node must agree on who owns it.
Constraints and uniqueness guarantees: a username or email address uniquely identifies one user; an account balance never becomes negative; inventory is never oversold; and two people cannot reserve the same flight or theatre seat at the same time.
Implementing linearizable systems
The simplest approach is to keep only one data copy, but it cannot tolerate faults: node failure causes data loss and makes the service unavailable.
The most common way to make a system fault tolerant is replication:
Single-leader replication (possibly linearizable): the leader holds the primary copy used for writes, while followers keep backups on other nodes. Reads from the leader or a synchronously updated follower may be linearizable. However, not every single-leader database is actually linearizable, whether by design—for example, because it uses snapshot isolation—or because of concurrency bugs.
Consensus algorithms (linearizable)
Applications that do not require linearizability tolerate network problems better. This insight is commonly called the CAP theorem.
333