CSE 124 Lecture Notes - Lecture 20: Uptodate, Hulu, Netflix
19 May 2018
School
Department
Course
Professor
Network Partitions
- some failure keeps replicas from “communicating” w/ one another
- how to proceed w/ transactions in case where not ALL replicas can be contacted??
Quorum Consensus Techniques
Divide into 2 sets: write quorum W and read quorum R
W > ½ the total votes
R + W > total # of votes
Ex: 5 nodes, initially all Version 1
Define W = 3
- Write to 3 of the nodes in order for operation to be “complete”
- Write is NOW successful
AFTER the client is gone:
- Nodes will “update” in the background, so everyone is now on track
Issues:
- Makes “reading” more difficult!
- If the updates have NOT yet propagated, you HAVE to make sure you are reading the
most up-to-date version!
Fix?
- Use a “comparator” of versions to get the most “up-to-date” version
Why does this work? If we pick our Read size = 3, AND our Write size = 3, then it would
guarantee at least 1 of the nodes that was most updated will contain the up-to-date version we
want!
- If R + W > total, we are good!
- Write quorum is the majority of the notes (W > N/2), and so is Read quorum
What if |R| = 5, |W| = 1 ?
- R + W > 5 ensures overlap between any R/W quorum
- Optimized for writing! You only need to write to one quorum, and ANY quorum
How does this perform for reads? Reads are expensive
How does this perform for writes? Pretty good!
- Ideally, you want pick such numbers s.t. you maximize performance
What if |W| = 5, |R| = 1? Applicable to Hulu, Netflix, or Youtube, etc.
- Don’t get updated very often
- Keeps replicas consistent for clients to read!
- Writes are expensive
Distributed Transactions
We’d like to think about concurrent transactions as if they were running in isolation
- Sum appears to happen either completely before or completely after transfer
- I.e. before-after atomicity
Document Summary
Some failure keeps replicas from communicating w/ one another. Divide into 2 sets: write quorum w and read quorum r. R + w > total # of votes. Write to 3 of the nodes in order for operation to be complete . Nodes will update in the background, so everyone is now on track. If the updates have not yet propagated, you have to make sure you are reading the most up-to-date version! Use a comparator of versions to get the most up-to-date version. If we pick our read size = 3, and our write size = 3, then it would guarantee at least 1 of the nodes that was most updated will contain the up-to-date version we want! If r + w > total, we are good! Write quorum is the majority of the notes ( w > n/2 ), and so is read quorum. R + w > 5 ensures overlap between any r/w quorum.
