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 staleness 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