Consistency models Flashcards
Strong consistency
Strong consistency gives the illusion that there is a single
database (despite the fact that the implementation is replicated
and partitioned).
Strong consistency offers linearizability.
1. A read is guaranteed to return the most recently committed
version of an item.
2. A client never sees an uncommitted or partial write.
linearizability
- A read is guaranteed to return the most recently committed
version of an item. - A client never sees an uncommitted or partial write.
Bounded Staleness
The database state evolves by applying all updates in a total order – all
updates outside the staleness window are applied in the same total order in
all replica.
Updates inside the staleness window - when there is a single write region
- For clients in that region, updates are totally order immediately
(equivalent to strong consistency) - For clients in other regions, clients may miss updates inside the staleness
window, but they will see them in order (leading to consistent prefix)
Updates inside the staleness window - when there are multiple write regions
- For clients writing to a single region, clients will observe those updates
updates in order (equivalent to consistent prefix) - When client write to different regions, updates are applied locally but
may be reorder later (leading to eventual consistency)
Bounded staleness garantees
- Reads observe a consistent-prefix, i.e., all updates are
totally ordered except within the “staleness window”. - Monotonic read, meaning that clients observe a version
that is later that the previously read. Why is this interesting? - A read might return an old value of the data item, configured
as:
* The number of versions (K) behind the current version that the
read can return;
E.g. with K = 5, the client knows that it might miss up to 5 writes.
* The time interval (T) for which it might miss a write.
E.g. with T = 10ms, the client knows that it might miss updates
executed in the last 10 ms.
How to implement bounded staleness
- Master region orders and propagates updates to other regions.
- A region can receive operations that propagate to the master
region to be ordered – while the order is not established by
the master, these updates are visible out-of-order in the local
region. - Read can be performed in the local region, given that the
bounded conditions can be established locally – e.g. from the
last message received from the master, a replica know the
potential staleness.
Session (Intuition)
The client has a session, where she sees the database evolving
as if it was a single replica. Updates from other clients/regions
are integrated in the view of the session.
Note: different clients with this consistency level may see
different database states.
Monotonic writes
Writes are propagated after writes that
logically precede them.
Write-follows-reads
A write is propagated always after the
read updates.
Read your writes
a read always reflects the writes executed
in the session.
Guarantees
Within a single client session, reads are guaranteed to
honor the consistent-prefix (assuming a single “writer”
session), monotonic reads, monotonic writes, read-yourwrites, and write-follows-reads guarantees
Clients outside of the session performing writes will see:
* Clients in the same region (either reading only or writing) will see
updates in order (leading to consistent prefix)
* Clients in other regions, with updates performed in a single region,
will see update in order (leading to Consistent prefix)
* For client writing in other regions, they may see their update being
reorder in relation to the writes of other regions (leading to Eventual
consistency)
How to implement session
Client maintains version vector (token, context) with a
summary of the operations observed;
* Reads request a state that is at least as recent as the vector;
* Updates in each region are ordered and this order is
respected when applying them to other replicas).
Consistent prefix (intuition)
The client sees a prefix of the updates from every region, but
might miss recent updates from different regions.
Guarantees (Consistent prefix)
- Results that are returned contain some prefix of all the
updates, with no gaps; - Reads never see out-of-order writes from a region (i.e., it
always observes updates executed in region in the same
order).
