3.5 Distributed Consistency Models

1. What Are Distributed Consistency Models?

• Different consistency models solve consistency problems to different degrees.

2. Categories of Distributed Consistency Models

2.1. Strong Consistency

• C in CAP.md.
• Also called linearizability.

2.2. Weak Consistency

• Eventual consistency
  • Causal consistency
    • Read-your-writes consistency
      • Session consistency
  • Monotonic-read consistency
  • Monotonic-write consistency
  • Prefix-read consistency

3. Linearizability

3.1. What It Is

• Once one client successfully completes a write, all clients reading data from the database must be able to see the value that was just written.
• 
• If the storage satisfies linearizability, client processes can treat the storage as if:
  • There is only one copy of the data.
  • All operations are atomic.

3.2. Use Cases

• Distributed locks and Leader election: for example, Leader election is essentially that whoever acquires the lock becomes the Leader.
• Uniqueness guarantees: for example, usernames must be unique.
• Ordering across multiple channels: for example, RPC calls + message queues.

3.3. Implementation

• Single-Leader replication + consistency algorithm:
  • The consistency algorithm solves split-brain and stale-read problems in single-Leader replication.
  • Use synchronous rather than asynchronous replication.

3.4. Problem

• Linearizability sacrifices A in CAP.

4. Eventual Consistency

4.1. What It Is

• E in BASE.md.
• Eventual consistency requires that once an update succeeds, data on each replica will eventually reach a completely consistent state, but the time required to reach that state cannot be guaranteed.
• 

4.2. Problem

• There is no specified waiting time.

5. Causal Consistency

5.1. What It Is

• If processes a and b have a causal relationship, after a is updated, process b needs to be notified.
• 

5.1.1. Total Order and Partial Order

• A total order means that given two values a and b, we can always know either a > b or a < b.
• A partial order means that given two values a and b, it may be that a > b, a < b, or a and b cannot be compared.

5.1.2. Causality

• If a is the cause and b is the effect, then a happens before b, and b cannot happen before a.
• Causality is a partial-order relation.
• Linearizability is a total-order relation.

5.2. Implementation

• Causal-consistency sequence number + total-order broadcast.

5.2.1. Causal-Consistency Sequence Number

• It is an increasing ID used to establish a total order for all operations.
  • Single Leader: it can be generated by the primary.
  • Multiple Leaders: Lamport clock.

5.2.2. Total-Order Broadcast

• Used to determine when the total order takes effect.
• Through a single-Leader, multiple-Follower mechanism, all operations are ordered on the Leader node, which determines the overall operation order and broadcasts that order.
• It is a protocol for exchanging messages between distributed nodes, with two properties:
  • Reliability: messages are not lost.
  • Ordering: the order in which messages are sent is the order in which they are received.

5.2.3. Problems with Total-Order Broadcast

• If throughput exceeds the processing capacity of a single Leader, how should the system be scaled?
• If the Leader fails, how should failover be performed?

6. Read-Your-Writes Consistency

• A user has just written data to the Leader and can read it from the Leader, but if the user immediately reads from a Follower, the data may not yet be readable.
• 

6.1. Implementation

• Read from the Leader
  • Within one minute after an update, the user reads the data they wrote from the Leader node, and reads data written by other users from Follower nodes.
  • Disadvantage: this only applies to scenarios where each user modifies only their own data.
• Timestamp mechanism
  • The client records the logical time of its last write. When reading from a Follower, it must read data after that time; otherwise, route to another node or wait. The timestamp can be logical time or system time.

7. Session Consistency

7.1. What It Is

• 
• Read-your-writes consistency can be guaranteed during a session.

8. Monotonic-Read Consistency

8.1. What It Is

• The Leader has synchronized to follower1 but not to follower2:
  • The user first reads from follower1 and gets the new data.
  • Then the user reads from follower2 and the data disappears.
• Monotonic-read consistency guarantees that if a process reads version v2 of data x, all subsequent reads by that process cannot see a version older than v2, such as v1.
• 

8.2. Implementation

• Route the same user to the same replica for reads through hash(uid).

9. Monotonic-Write Consistency

9.1. What It Is

Monotonic-write consistency can guarantee serialization of a process’s multiple write operations. Without this guarantee, application development is difficult for developers.

10. Prefix-Read Consistency

10.1. What It Is

• User 1 writes data1 to leader1.
• User 2 writes data2 to leader2.
• leader2 synchronizes data2 to follower2.
• User 3 reads from follower1 and does not see data1.
• User 3 reads from follower2 and sees data2.
• leader1 synchronizes data1 to follower1.
• User 3 reads from follower1 and sees data1.

10.2. Implementation

• Ensure that all causally related writes are written to the same partition.

11. References

• JGrowing/谈谈数据一致性.md at master · javagrowing/JGrowing
• 线性一致性与全序广播——《Designing Data-Intensive Applications》读书笔记12 - HappenLee - 博客园
• 通俗易懂 强一致性、弱一致性、最终一致性、读写一致性、单调读、因果一致性 的区别与联系 - 知乎
• 谈谈数据一致性