# Replicating Data Consistency Explained Through Baseball
## Main Idea
* Replication protocols often involve complex trade-offs between consistency, performance, and availability
* Shed lights on the consistency models offered by cloud providers, what might be offered in the future, and why vendors are offering consistency choices
## Intro
### Consistency provided by cloud storage today
* Azure: strongly consistent storage
* Always see the latest value that was written for a data object
* Reasonable to provide within a DC
* But raises concern for geo-replicated storage
* AWS S3: designed with weak consistency
* Better performance and availability: read might be with stale data
* Eventually consistent: read operation is directed to a replica that has not yet received all the writes that were accepted by some other replica
* AWS DynamoDB: both eventually consistent reads and strongly consistent reads
* AWS SimpleDB: same choices for clients that read data
* Google App Engine Datastore: eventually consistent reads + default strong consistency
* Yahoo's PNUTS: read-any, read-critical, read-latest
* Quorum-based storage systems: eventual + strong consistency \[by selecting different read and write quorums)
### Consistency models proposed from research community
* Trade-offs between consistency, performance, and availability
* Availability is the likelihood of a read operation successfully returning suitably consistent data in the presence of server failures
* Performance refers to the time it takes to complete a read operation, that is, the read latency
* Two ends: strong and eventual
* Stronger: lower performance but reduced availability for reads or writes or both
### Questions to cope with
* Are different consistencies useful in practice?
* Can application developers cope with eventual consistency?
* Should cloud storage systems offer an even greater choice of consistency than the consistent and eventually consistent reads offered by some of today’s services?
## Read Consistency Guarantees
### Model
* Multiple clients perform read and write operations to a data store, concurrently access shared information
* Data is replicated among a set of servers, but the details of the replication protocol are hidden from clients
* Write: any operation that updates one or more data objects
* Eventually received at all servers and performed in the same order
* Order is consistent with order in which write operations are submitted by clients
* In practice
* the order could be enforced, even for concurrent writers
* by performing all writes at a master server or by having servers run a consensus protocol to reach agreement on the global order
* Read: return values of one or more data objects that were previously written
* Not necessarily the latest values
* Can request a consistency guarantee, which dictates the set of allowable return values
* Each guarantee is defined by the set of previous writes whose results are visible to a read operation
#### Strong Consistency
* Guarantees that a read operation returns the value that was last written for a given object
* Append? applying all writes to that object
#### Eventual Consistency
* The weakest of the guarantees
* Allows the greatest set of possible return values
* The term derives from:
* Each replica eventually receives each write operation
* If clients stopped performing writes then read operations would eventually return an object’s latest value
#### Consistent Prefix or Similar to Snapshot Isolation
* A reader is guaranteed to observe an ordered sequence of writes starting with the first write to a data store
* E.x. the read may be answered by a replica that receives writes in order from a master replica but has not yet received some recent writes
* Reader sees a version of the data store that existed at the master at some time in the past
* Similar to "snapshot isolation" consistency offered by many DBMS
* For reads to a single data object in a system where write operations completely overwrite previous values of an object
* Eventual consistency reads observe a consistent prefix
* Main benefit
* When reading multiple data objects \[Q: why?]
* Or when write operations incrementally update the objects
#### Bounded Staleness
* Ensures that read results are not too out-of-date
* Staleness defined by a period T, e.x. 5 mins or # of missing writes or the amount of inaccuracy in a data value
* Guarantees that a read operation will return any values written more than T minutes ago or more recently written values
* "Most natural concept for application developers"
#### Monotonic Reads / "Session Guarantee"
* Applies to a sequence of read operations that are performed by a given storage system client
* A client can read arbitrarily stale data, as with eventual consistency, but is guaranteed to observe a data store that is increasingly up-to-date over time
* E.x. client issues a read operation and then later issues another read to the same object(s)
* the second read will return the same value(s) or a more recently written value
#### Read My Writes
* Also applies to a sequence of operations performed by a single client
* Guarantees that the effects of all writes that were performed by the client are visible to the client’s subsequent reads
* E.x. If a client writes a new value for a data object and then reads this object
* the read will return the value that was last written by the client (or some other value that was later written by a different client)
* For clients that issue no writes, the guarantees = eventual consistency
#### Summary
* Last four read guarantees are all a form of eventual consistency, but stronger than what is typically provided in cloud storage system
* None is stronger than any of the others
* Applications can request multiple of these guarantees
* E.x. a client could request both monotonic reads and read my writes so that it observes a data store that is consistent with its own actions
* Strong consistency: desirable from consistency view point, but worst performance and availability
* Generally requires reading from a designated primary site or from a majority of replicas
* Eventual consistency: weakest consistency, but better performance and availability
* Allows the clients to read from any replicas
* Others
* The “strength” of a consistency guarantee does not depend on when and how writes propagate between servers, but rather is **defined by the size of the set of allowable results for a read operation**
* **Smaller sets of possible read results indicate stronger consistency**
### Baseball as a Sample Application
* Two teams' scores
* 
* 
* Many of the scores returned by eventually consistent reads were never the actual score
* Consistent prefix limits the result to scores the actually existed at some time
* Bounded staleness depend on the desired bound
* For bounded of 7 innings or more, result is the same for eventual consistency
* Monotonic reads: possible values depends on what has been read in the past
* Read my writes: depend on who is writing to the key-value store
### Read Requirements for Participants
#### Official Scorekeeper
* Task: responsible for maintaining the score of the game by writing it to the persistent key- value store
* 
* What consistency?
* Read the most up-to-date previous score before adding one to produce the new score
* Otherwise could write an incorrect score and undermining the game
* He needs strongly consistent data, but he does not need to perform strong consistency reads
* If there were multiple people playing the role of scorekeeper and taking turns updating the score, then they would need to perform reads that request strong consistency
* The scorekeeper is the only person who updates the score
* can request the *read my writes* guarantee and receive the same effect as a strong read
* If scorekeeper changes in the middle of the game
* the new scorekeeper could perform a strong read when he first updates the score
* but can use read my writes for subsequent reads
* Uses application-specific knowledge to obtain the benefits of a weaker consistency read without actually giving up any consistency
* In real life
* Strong consistency read
* pessimistically assume that some client, anywhere in the world, may have just updated the data
* system therefore must access a majority of servers (or a fixed set of servers) in order to ensure that the most recently written data is accessed by the submitted read operation
* Read my writes
* Simply needs to record the set of writes that were previously performed by the client and find some server that has seen all of these writes
* In baseball games where the previous write was performed by the scorekeeper may have happened many minutes or even hours ago
* Almost any server will have received the previous write and be able to answer the next read that requests the read my writes guarantee
* \[Q: essentially eventual consistency?]
#### Umpire
* Task: officiates a baseball game from behind home plate
* For the most part, does not really care about the current score of the game
* Only care during the top half of the 9th inning (i.e. after the visiting team has batted and the home team is about to bat)
* 
* Never writes, only reads the values written by official scorekeeper
* In order to receive up-to-date info, the umpire must perform strong consistency reads
* Otherwise might end the game early
#### Radio Reporter
* Task: periodically announce the scores of games that are in progress or have completed
* E.g. every 30 mins
* 
* Broadcasts scores that are not completely up-to-date is okay
* But don't want to report wrong scores
* The reporter wants both his reads to be performed on a snapshot that hold a consistent prefix of the writes that were performed by the scorekeeper
* But this is still not sufficient!
* Could read a score of 2-5, the current score, then 30 mins later, read a score of 1-3
* If reporter reads from a primary server and later reads from another server
* \[Q: need to understand this]
* This can be avoided if the reporter requests the *monotonic reads* guarantee in addition to requesting a *consistent prefix*
* \[Q: why do I still need consistent prefix in this case?]
* Or obtain the same effect as a *monotonic read* by requesting *bounded staleness* with a bound of less than 30 minutes
* Since the reporter only reads data every 30 minutes, he must receive scores that are increasingly up-to-date
#### Sportswriter
* Task: watches the game and later writes an article that appears in the morning paper or that is posted on some web site
* 
* Want the effect of strong consistency read (to report the final correct score), but he does not need to pay the cost
* a *bounded stalene*ss read with a bound of one hour is sufficient to ensure that the sportswriter reads the final score
* In practice, any server should be able to answer such a read
* Eventual consistency: likely to be correct after an hour
* But request bounded staleness is the only way to be 100% certain about it
#### Statistician
* Task: keeping track of the season-long statistics for the team and for individual players
* 
* Sometime after each game has ended, adds the runs scored to the previous season total and writes this new value back into the data store
* Requirements
* Obtain the final score --> strong consistency read, or waits with bounded staleness
* For reading the statistics for the reason, also wants strong consistency
* Since she is the only person who writes statistics to the data store, she could use "read my writes" guarantee to get the latest value
#### Stat Watcher
* Task: periodically check on the team’s season statistics
* Requirements: are usually content with eventual consistency
* Updated once per day, and numbers that are slightly out-of-date is okay
* 
### Conclusion
#### Take
* All presented consistency guarantees are useful
* Different clients may want different consistencies even when accessing the same data
* Even simple databases may have diverse users with different consistency needs
* Clients should be able to choose their desired consistency
* The preferred consistency often depends on *how* the data is being used
* knowledge of *who* writes data or *when* data was last written can sometimes allow clients to perform a relaxed consistency read
* Others
* Cloud providers should offer a wider range of read consistencies for better resource utilization and cost savings
