Why need more than one copy of data?
- Availability even under failures.
- Low latency, some replicas are closer to users.
- High throughput, mutiple replicas share the (read) load.
A copy of data is called a replica
- Replicas follow some protocol to provide a consistent view of the data item
- We cannot allow replicas to “naively” execute data requests
- In general, consistency defines the ordering of the operations in the system
- Replica consistency specifies the ordering of the operations executed on each replica, all replicas together provided some consistent view of the data
- System developers design and implement protocols that guarantee some ordering properties X (consistency), which prevents anmalies Y
Consistency Models
- A spectrum of consistency models, from weak to strong
- The stronger the model is, the group of replicas behave more like a single copy.
- The strongest model is strict serializability: as if requests are executed by a single threaded machine one by one
- e.g., you are always able to see the most recent update, even if you read from replica A while the most recent update was done on B
Eventual Consistency
- All replicas will eventually converge to the same state.
- Each replica will eventually receive all updates
- All updates will eventually take effect in the same order on each replica
- If the system stops receiving updates, then after a while, all replicas of a data item will contain the same value (converge)
- Commonly adopted by applications like VCS (git), collaborative editors (overleaf), dropbox, and shared calendar, etc.
- People work on their local copies (fast) and lazily synchronize with each other
- Can still work on local copy without network conenction
What happens before “converge”
- Replicas may have different views from each other
- A replica’s view may be a subset of that of all replicas
- e.g., missing some updates that originated in other replicas
- A replica’s view may be conflicting with that of other replicas
- e.g., writes on different replicas update the same data item, but appear in different orders on different replicas
- A replica’s view may be a subset of that of all replicas
Providing Eventual Consistency
- Make sure all replicas receive all updates to the data item
- Make sure updates take effect across all replicas in the same order eventually
- Non-conflicting writes are applied in some defined order
- Conflicting writes are resolved deterministically
- i.e., different replicas resolve the conflict in the same way that results in the same final state
Bayou: A Weakly Connected Replicated Storage System
Context
Early 90s, internet connectivity was poor, wireless was not widely deployed, mobile data was expensive.
For many applications, people want to work on it without network connection, either because there is none or they don’t want to pay; then later incoporate all work has been done by different people when connected to the internet
How Bayou Provides Eventual Consistency
Eventual Consistency needs
- all replicas receive all updates
- Anti-entropy: A server periodically sends its recent updates to another randomly selected replica
- all replicas apply updates in the same order eventually
- How Bayou ensures a total order?
Bayou Ensures A Total Order of Updates with Lamport Timestamps
- Each update is associated with a Lamport timestamp
- Each replica’s local updates are totally ordered by Lamport timestamps in a write log
- Each replica periodically receives replicated updates from other replicas via anti-entropy (it also sends out its local log to other replicas)
- Each replica merges its local updates and replicated updates in the timestamp order
Challenge: What if merging with replicated writes “invalidates” some of my local writes?
Solution: updates are marked tentative until we are sure they will not be changed
When is an update stable and finalized so Alice and Bob knows their reservations are confirmed?
Write Stabilization
- One of the replicas is chosen as the Primary who commits the tentative writes in order
- Committed writes are final and will not change in the future
- Primary commits the updates in its write log
- Tentative updates are committed in their timestamp order, specified with monotically increasing commit numbers (e.g., 1, 2, 3, …)
- Newly arrived tentative updates are ordered after already-commited writes
- Tentative writes may be reverted/undone during write stabilization
- This commit order is learned by other replicas via anti-entropy, and other replicas commit those tentative writes in that order
Example
Format: <ts = (int, replica node), write #, “commit status”>
Suppose three replicas and replica A is the primary:
Replica A: <ts = (2, A), W1, "tentative">, <ts = (5, A), W2, "tentative">
Replica B: <ts = (2, B), W3, "tentative">, <ts = (4, B), W4, "tentative">
Replica C: <ts = (3, C), W5, "tentative">
Anti-entropy from B to A:
Replica A: <ts = (2, A), W1, "tentative">, <ts = (2, B), W3, "tentative">, <ts = (4, B), W4, "tentative">, <ts = (5, A), W2, "tentative">
^
|
Anti-entropy
|
Replica B: <ts = (2, B), W3, "tentative">, <ts = (4, B), W4, "tentative">
Replica C: <ts = (3, C), W5, "tentative">
A commits its write log:
Replica A: <ts = (2, A), W1, "commit">, <ts = (2, B), W3, "commit">, <ts = (4, B), W4, "commit">, <ts = (5, A), W2, "commit">
^
|
Anti-entropy
|
Replica B: <ts = (2, B), W3, "tentative">, <ts = (4, B), W4, "tentative">
Replica C: <ts = (3, C), W5, "tentative">
Anti-entropy from A to B:
Replica A: <ts = (2, A), W1, "commit">, <ts = (2, B), W3, "commit">, <ts = (4, B), W4, "commit">, <ts = (5, A), W2, "commit">
|
Anti-entropy
|
v
Replica B: <ts = (2, A), W1, "commit">, <ts = (2, B), W3, "commit">, <ts = (4, B), W4, "commit">, <ts = (5, A), W2, "commit">
Replica C: <ts = (3, C), W5, "tentative">
Anti-entropy from C to A; tentative log always go after commit logs:
Replica A: <ts = (2, A), W1, "commit">, <ts = (2, B), W3, "commit">, <ts = (4, B), W4, "commit">, <ts = (5, A), W2, "commit">, <ts = (3, C), W5, "tentative">
^
|
Anti-entropy
|
|Replica B: <ts = (2, A), W1, "commit">, <ts = (2, |B), W3, "commit">, <ts = (4, B), W4, "commit">, <ts | =(5, A), W2, "commit">
|
Replica C: <ts = (3, C), W5, "tentative">
Conflict Detection and Resolution
Detection
- Allow the application to specify what a conflict means in the context of the application
- e.g., the meeting room scheduler may detect a conflict if a room is being reserved for two different meetings whose times overlap
- Use “a dependency check” and “the expected result of the check” in each write to detect conflicts
- e.g., a check =
SELECT key FROM Meetings WHERE day=10/1 AND start_time > 2PM and end_time < 3PM. Expected result = {}, assuming I want to use the room from 2 PM to 3 PM on 10/1.
- e.g., a check =
Resolution
- Application may have different ways of resolving conflicts
- Google calendar may keep and show all conflicting meetings
- For meeting room scheduler, we may want to find alternative times for conflicting meetings
- Use “merge procedures” in each write to tell the system how to resolve the conflicts after they are detected, usually produce a revised update to apply.
Conclusion
- Eventual consistency: if updates stop, all replicas eventually the same
- Tentative partial orders of replicas eventually form a total commit order
- App-specific conflict resolution