# Consistency Models

The consistency model is an abstraction of the contract between the distributed system and developers. It is defined from the two perspectives, adapted from Linearizability versus Serializability:

• Serializability guarantees concurrent transactions on multiple objects with some serial execution. It represents the I in ACID.
• Linearizability defines the recent guarantee on the behavior of single operation on the single object. It represents the C in CAP Theorem.

transaction isolation is primarily about avoiding race conditions due to concurrently executing transactions, whereas distributed consistency is mostly about coordinating the state of replicas in the face of delays sand faults

Designing Data-Intensive Applications, Chapter 9. Consistency and Consensus

The below diagram is copied from the jepsen.io to guide our exploration of consistency models in the Designing Data-Intensive Applications, Chapter 7. Transactions and Chapter 9. Consistency and Consensus.

## Serializability Challenges

Assuming alice has two accounts, saving and checking, each deposited $500, with$1000 in total. We MAY encounter the following problems when dealing with concurrent transactions.

### Dirty write

The dirty write defined as that the transaction A overwrite transaction B’s uncommitted write. This is literally data loss, and it is not acceptable in any circumstance, even for the least restrictive Read Uncommitted.

If the transaction A can read transaction B’s uncommitted write, we call it dirty read. It is also bad as the partial update is leaking outside the transaction, and it MAY not represent the final state if the transaction is aborted.

Considering Alice transfers $100 from checking account to the saving account, and checks the total account balancing during the transaction. Alice MAY see the balance as$900, $1000, or$1100 depending on the order of operations and timing.

### Write skew

However, the Snapshot Isolation does not enforce a total order of transactions, the write skew MAY happen:

Considering the bank requires the combined balance of checking and saving accounts MUST exceeds $500 to avoid service fees, and Alice opts-in the overdraw protection; then Alice withdraw$300 each from checking and saving account concurrently. Each transaction reads the overlapped data set, aka checking account and saving account, then concurrently make disjoint updates, and concurrently commit. Everything works, except Alice’s balance drops to $400, and she has to pay the fees. The Serializable isolation level enforce the transactions appear to have occurred in some total order to prevent the write skew. The write skew can also be coped with row locks in the application side. Before any deposit, we issue the SELECT FOR UPDATE to lock all Alice’s accounts. Another approach is materialized conflict: if we manage to create a materialized view to store the sum of balances of checking and saving accounts, and enforce the >=$500 constraint, the second write will trigger integration error.

## Linearizability Challenges

Due to the physical limit of light speed, the replication MAY lag. Thus two consecutive operations MAY interact with different replicas, which introduce weird anomaly. The following consistency models are defined to enforce the real-time guarantee.

### Monotonic Writes

Alice deposits $100,$200, Bob MUST see the deposit in the same order.

Alice deposits $100. Bob check the balance twice, he MAY see the balance as: •$500, $500. •$500, $600. •$600, $600. He MUST NOT see$600, $500. ### Pipeline Random Access Memory, aka PRAM Alice deposit$100, $200, Bob deposits$300, $400 simultaneously, they MUST see the deposits in the topological order, such as$100 precedes $200, and$300 precedes $400. ### Writes Follow Reads Alice deposits$100, Bob MUST observes the initial deposit $500, and the current balance$600.

you can’t change that read’s past.

It is also known session causality.

### Casual Consistency

To encourage Alice to save more, Bob and his brother Chris agree to match any deposit made by Alice. Alice then deposit $100, Bob, then Chris deposit$100 each. All parties MUST see Alice’s deposit precedes Bob’s and Chris’, but the order MAY differ on each observer.

The operations causally-related MUST appear in the same order on all processes.

### Sequential Consistency

The sequential consistency guarantees that the operations to take place in a determined total order observed by all parties. It does not imply the real-time constraints though.

Using the above example, all parties MUST observe the same deposit order, either

• Alice, Bob, Chris
• or Alice, Chris, Bob

### Linearizability

Linearizability implies all operation to take place with the real-time ordering.

With above example, all parties MUST observe the same deposit order as the wall-clock, Alice, Bob, Chris.

### Strict Serializability

The strict serializability implies both Linearizability and Serializability.