🐏 mogoz

Search

SearchSearch

Concurrency Consistency Models

Sep 16, 2024, 4 min read

tags : Distributed Systems, Database, Correctness criteria, Eventual Consistency

FAQ

Strong Consistency(Linearizable) vs Sequential Consistency

  • Both care about giving an illusion of a single copy.
  • Sequential Consistency
    • Cares about program order
    • P(A) executes T1 and T2
    • then P(B) executes T3
    • Order could be: (T1-T2)-T3, T3-(T1-T2), T1-T3-T2 but not T3-T2-T1. Because this will violate order of P(A)
    • There’s no global real time order
  • Strong consistency (Linearzability)
    • Cares about real time order
    • P(A) executes T1 and T2
    • then P(B) executes T3
    • Order would be: (T1-T2)-T3

Strong and Weak?

Not all consistency models are directly comparable. Often, two models allow different behavior, but neither contains the other. Different consistency models fall in the spectrum of strong and weak.

  • Stronger
    • More restrictive consistency models
    • Slower
    • More time spent in doing coordination (See Consensus Protocols)
    • Easier to reason about
  • Weaker
    • More permissive consistency models
    • Faster
    • Harder to reason about

Different meanings of consistency

  • ACID
    • Related to Database
    • Satisfying application specific constraints.
    • E.g. “every course with students enrolled must have at least one lecturer”
  • Replication
    • See Data Replication
    • Replicas should be “consistent” with other replicas
    • This is similar to what consistency means in CAP
    • Brewer originally defined consistency as single copy serializability. (As if we’re interacting with only one copy of the object, even though multiple things might be modifying it)
    • Gilbert & Lynch defined consistency as linearizability of a read write register
  • Different consistency models have their own meaning of consistency

Which consistency model to pick for my application?

  • General rule: Pick the weakest consistency model that satisfies your needs

What’s total ordering?

  • To the user it seems like they’re interacting with one single system
  • In the total ordering, a read operation sees the latest write operation.
  • We can always compare the logical timestamps. (i.e figure out who was last)
  • Transactions and locks can be used together to provide serializability (isolation)
  • Transactions provide atomicity
  • Transactions + locks provide serializability

Consistency models

How to read this image?

  • Think of the parent node as the combination of the nodes under it.
    • Eg. Strict Serializable = Serializable + Linearizable
  • We say that consistency model A implies model B if A is a subset of B. For example, linearizability implies sequential consistency because every history which is linearizable is also sequentially consistent.

Models

These consistency models are enabled by concurrency control (CC). You can come up with your own too. Infact many have, S3 consistency, Consistent Prefix etc.

Jespen

  • Strict Serializable

    • Eg. Strict Serializable = Serializable + Linearizable

  • Linearizable

    • Strong Consistency = Linearizable
    • Cares about real time order
    • Serializability does not take the flow of time into consideration. Linearizability implies time-based ordering.
    • Modifications happen instantaneously, any read operation will see the latest and same value.
      • Read should return the most recent write
      • Subsequent reads should return same value, until next write
    • So if the replication happened asynchronously, there will be lag and ultimately reads will not see the latest value or if replicated un-uniformly, different reads will see different values.
    • So we can’t do async replication, we can’t do sync replication(too slow), so the answer is Consensus Protocols like Raft and Paxos which provide strong consistency.

  • Serializable

    • AKA one-copy serializable
    • Allows truly parallel execution of instructions
    • Could bring in performance improvements but this also means stricter controls so that can slow things down as-well. (Tradeoff)
    • Even with parallel executing transactions, the end result is same as if the transactions where executed serially.

  • Sequential Consistency

    • This is weaker than Strong consistency(Linearizable)
    • Cares about program order/thread order and legal sequencing

  • Read your writes / Read-after-writes

    • If a process writes, if it reads again it should see what it wrote

  • Monotonic Reads (Readonly)

    • Time-order(fwd only), same process
    • Either get the same read, else a newer read, never an older read than the first read in the process

Others

  • Consistent prefix
  • Bounded Staleness

Resources

Graph View

Backlinks