---
# System prepended metadata

title: consistency models

---

# consistency models

(Some old notes on consistency models). A consistency model is a set of histories of operations

### Read Uncommitted

[https://jepsen.io/consistency/models/read-uncommitted](https://jepsen.io/consistency/models/read-uncommitted)

- Prohibits *dirty writes* where two transactions modify the same data, but allows all other behavior, including
    - $w_1(x) … r_2(x)$ - *dirty read*
    - $r_1(x) … w_2(x)$ - *fuzzy read (read by* `tx1` *then write by* `tx2`*)*

### Read Committed

[https://jepsen.io/consistency/models/read-committed](https://jepsen.io/consistency/models/read-committed)

- Strengthens Read Uncommitted to prohibit a dirty read, so like read uncommitted, it prohibits dirty writes and now also *dirty reads*, where a transaction is not allowed to observe a write of a transaction that does not commit. Still allows *fuzzy read* and *phantom read*

### Snapshot Isolation

[https://jepsen.io/consistency/models/snapshot-isolation](https://jepsen.io/consistency/models/snapshot-isolation)

- A system that is snapshot isolated appears for transactions to run on full consistent snapshots of the system state. Transaction execution is broken up into an interval from `StartTimestamp` to `CommitTimestamp`, and when a tx starts execution it does so on a consistent *snapshot.* Any writes the transaction makes are visible only to the transaction itself, and *externally*, writes are visible to all other transactions only at commit time and become visible atomically - thus at that point "creating" the next snapshot. The rule is that if `tx1` starts execution, and before it commits observes a commit `tx2` that then must be in the interval `[StartTimestamp - CommitTimestamp]`, then `tx1` aborts, since `tx2` committed first and we want to guarantee that no writes are lost. Snapshot isolation is therefore "first commit wins".
- In other formulation, can also be specified in terms of properties:
    1. *internal consistency -* writes that are local in `tx1` are visible to subsequent reads by `tx1`
    2. *external consistency* - reads without preceding writes (local) by `tx1` must observe the state as written by some tx `tx0` that has committed before `tx1`'s `StartTimestamp`
    3. transactions become visible to all nodes in same order
    4. if two transactions `tx1`, `tx2` modify the same object, then one of the transactions must be *visible* to the other, i.e. became visible as committed before the 'later' transaction started execution (any local reads) 

### Serializability

- Extends Snapshot Isolation to enforce a total order on events, as if the events were executed one at a single point in time
- Example of difference between Snapshot Isolation vs. Serializability
    
    Imagine a bag (equivalent of a storage table) with black and white marbles - we have 2 transactions:
    
    `tx1` - turn all marbles black
    
    `tx2` - turn all marbles white
    
    If we run these two transactions under Serializable consistency level, then only 2 states are possible: all black marbles or all white marbles. Why? Under serializable execution we can have two valid serializable orders:
    
    1. initial_state →`tx1` → `tx2` → final_state
    2. initial_state →`tx2` → `tx1` → final_state
    
    If we run these two transactions under Snapshot Isolation consistency level, then we have one extra state - assume that both transactions start execution at the *same exact time*, then `tx1` turns all white into black and `tx2` does the opposite, but when both commit and apply their writes we still have a mixed state with the colors reversed.
    

### Strict Serializability

- Extends Serializability to enforce a real-time ordering on events, with real-time ordering given by theoretical "observer" clocks, such that, if each operation has an invocation time and, should it complete, a strictly greater completion time, both are given by this perfectly synchronized, globally accessible clock
- Can think of a strictly serializable database a single linearizable object in which the object is all of the database state
- Fixes issues with serializability without linearizability when running in a distributed manner

### Serializability vs. “Strict” Serializability

- When running on single-machine deployments, serializable systems are practically also strictly serializable
- When running in distributed system and attempting to do distributed transactions, have problems such as
    - *Stale read* — `tx1` reading and modifying state on replica 1 while `tx2` is routed to replica 2 which has not yet "heard from" via replication (perhaps asynchronous) from the primary replica, therefore resulting in an order `tx2` → `tx1` which violates strict serializability as it violates the real-time order in which the transactions have arrived
    - *Causal reverse —* if performing two transactions on disjoint sets, such as transferring funds from a savings account to a checking account and then again from a savings account as a payment to another account, if the two transactions get re-ordered, then the state of the checking account may be different and thus violate some safety constraints (such as balance being greater than 0). Example:
        
        ```python
        Checking = 0
        Savings = 100
        
        TRANSACTION tx_1
        	Checking += 100
        	Savings -= 100
        
        TRANSACTION tx_2
        	Checking -= 100
        	Other_bank_account += 100
        ```
        
        if `tx_1` and `tx_2` get re-ordered, then the balance of Checking will dip below zero before arriving at the final balance state
        

---

## Single-object consistencies

### Causal consistency

- Causally related events should appear in the same order on all processes, although causally independent events are arbitrarily ordered
- Captures the notion of "happened before" relation from Lamport's definition
- Example — In a chat application, assume Alice sends a message "lunch?", after which Bob responds "yes" and Zoe responds "no". Causal consistency allows Alice to observe
    1. `"yes"` → `"no"`
    2. `lunch?` → `"no"` → `"yes"`
    
    but never `lunch?` before either `"yes"` or `"no"`, since those are causally-related operations
    

### Sequential consistency

- All operations on processes appear to take place in *some* total order, and that order is consistent with the order of operations on each individual process

### Linearizability

- Strengthens Sequential Consistency such that operations appear to take place atomically in a single total order that is consistent with *real time ordering* of those operations
- If operation `A` completes before operation `B` begins, then operation `B` should logically take effect on the state after operation `A`

---

### Some notes on "**ANSI SQL Isolation Levels**"

*A Critique of ANSI SQL Isolation Levels* - [https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-95-51.pdf](https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-95-51.pdf)

"Isolation" defined with the three phenomena —

1. P1 (Dirty Read) - `tx1` applies a write, then `tx2` reads the modified data before `tx1` commits or aborts the transaction, so then if `tx1` does end up aborting, `tx2` read a value that is no longer there and thus never really existed
2.  P2 (Fuzzy Read or Non-repeatable read) - `tx1` performs a read, then `tx2` writes or deletes the record that `tx1` has read and commits, so then if `tx1` attempts to re-read the value, it finds it modified and not equal to the previous read 
3. P3 (Phantom) - `tx1` performs a read that satisfied a `< search condition filter >` , then `tx2` applies a write that also satisfies the same `< search condition filter >` and commits. If `tx1` performs the same read of `< search condition filter >` again, it finds a record that was not there in the previous read.