Replicated Data Consistency Explained Through Baseball

A key feature of all distributed storage systems is their ability to replicate data not just across machines within a data center but also across geographically distributed data centers. Replication, while it aids ensuring higher availability of the data segments also necessitates keeping multiple replicas somehow in sync to ensure what you’ve written is what you will see when reading.
 We have taken this ability of getting back exactly what was just written for granted in the case of monolithic storage systems. Entire applications are built on this premise. When it comes to distributed storage systems ensuring this guarantee tends to be much more complex affair.
This paper attempts to classify and explain the possible variations of this guarantee. It also describes the relevance of each of these variations based on a lively illustration of a game of baseball!

An imminent need to understand consistency models

When working with a distributed database it quickly becomes important to understand the consistency model that a distributed data store (be it a file system or a NoSQL or SQL database) offers. Most cloud storage systems make this choice for us and a few offer some limited ability to choose from a set of idiosyncrasies.

Intuitively, we can describe two extreme approaches to ensuring consistency. Namely, strong consistency and weak/eventual consistency. To make things more interesting researchers have formulated many different consistency models that lie between these two extremes.

How useful are these? Should storage systems offer many different types of guarantees?

There are some less-than-ideal behaviors that we have to settle for with each type of guarantee. For example stronger consistency means increased latency and hence slower performance and reduced availability.
What are the different tradeoffs that come with each type of guarantee? And how does some type of guarantee semantics impact application developers?

These are some of the questions this paper tries to answer by examining read operations on distributed data stores.

A typical distributed data store

Within a distributed data store data is replicated on a subset of nodes from within a pool of servers as clients perform reads and writes. Writes eventually make it to different replicas in the same order as submitted by the client. While replication is in progress if a client tries to read a record there is no guarantee that the value that is returned is going to be the latest.

In such systems the read operation allows (or must allow) the client to specify a “tolerable extent of staleness” as an input parameter. Based on the extent of staleness an application’s use case can tolerate, the store could return a value that may vary from being the very latest to something that could be stale by an order of minutes. The magnitude of delay really depends on how geographically wide the data has to travel in order to reach its replicas.

The paper distills different kinds of guarantees a distributed data store can offer into six of them. These consistency guarantees are based on a simple model in which clients perform read and write operations to a data store. The data is replicated among a set of servers.

Shades of Grey : Six Read Consistency Guarantees

Strong Consistency : A data store that offers a strong consistency guarantee assures the user that whenever a write operations modify a record the read operation returns a result which is an outcome of applying all updates to the record. Its the strongest form of all consistency guarantees.

Consistency Prefix : The read operation will return values from an ordered sequence of writes starting with the first written value of the record. This is similar to Snapshot Isolation guarantee in an RDBMS.

Bounded Staleness : This form of guarantee assures that the returned value is not too out of date from the latest value. It quantifies “not too out of date” by some time interval T. The client can ask the storage system to return the value of a record which is not older than T minutes. Thereby putting an upper limit to how stale the value of a record is.

Monotonic Reads : This form of guarantee is something that is offered to a single client of the storage system. It assures the client that the returned value

  • is either the same across multiple read calls issued by the same client
  • or is more recent than what was returned in the previous call from the same client.

i.e for the duration of the client’s session.

Read My Writes : This form of guarantee is also an assurance that is offered to a single client of the storage system. It guarantees that all writes made by this client will be returned on subsequent reads performed by the same client.

Eventual Consistency : This is the weakest form of consistency guarantees. A store that offers this guarantee assures users that a read operation can return any value that a record had in its past. It depends on which replica of a dataset will be accessed to return this call. Depending on how stale the replica is it can be the latest or the earliest or some intermediate value from the set of updates that have been completed for a record.

Are these guarantees useful? To whom and when?

The paper tries to answer to this question based on an illustration of a hypothetical distributed key-value store which is used to record the scores for a game of baseball. The different actors in the game ranging from the umpire to the casual observer of the game represent the applications that access the information persisted in this key value store. By virtue of the role they play each of these participants can naturally tolerate different extents of staleness/out-of-date-ness of the scores. The different consistency guarantees are in turn mapped to the read operations performed by these participants to fulfill their information needs. Some of these participants include –

The Official Score keeper – He is one (and the only one) responsible for updating the scores. So he has to work with the latest score and increment it every time there is an update. While the scorekeeper requires strongly consistent data, he does not need to perform Strongly Consistent reads. Since he is the only person who updates the score, he can request the Read My Writes guarantee and receive the same effect as a strong read.

The Umpire – For all practical purposes the umpire never cares about the score except to decide if the game has been won or not by the home team at the beginning of the second half of the last innings. Its quite likely that the home team has already won the game. While accessing the score for both the teams the Umpire needs to read the last values as written by the score keeper. For this he performs Strongly Consistent reads.

The Radio Reporter – Radio stations periodically broadcast the scores of the games that are in progress about once every 30 minutes. The reporter does not necessarily have to broadcast the most up to date score. Its ok to be a little behind. So some form of eventual consistency is acceptable here. Given that its ok to be out of date by quantum of time, the Bounded Staleness guarantee gives ample flexibility to the reporter to decide on how much he wants to lag by. Even Monotonic Reads could work but Bounded Staleness offers better control to the reporter.

The Casual Observer – For a casual observer of the game who is only interested in something as coarse grained as the final outcome or the total number of runs scored by a team etc Eventual Consistency works quite well. A fan can make an eventually consistent read call and get a reasonably up to date answer.

Conclusions

Although the example is simple it drives home some key lessons for us –

  • At the outset the idea of a data store offering different consistency guarantees for the same data set might seem a bit novel to application developers. As the adoption of distributed data stores increases we’ll have to embrace some of their idiosyncrasies.
  • Typically we correlate guarantee semantics with a class of applications/data sets. For instance banking apps generally require strong consistency. The example shows that deciding to go with a kind of guarantee also depends on who is reading the data.
  • The data store cannot predict the consistency needs of a client. Only clients that use a dataset can decide on how much staleness their applications can tolerate.
  • Embracing eventual consistency does put some extra burden on application developers. The way developers can start is by first understanding the guarantee semantics offered by different distributed stores.
  • And finally – “If the storage system can perform write operations in a strict order, developers can avoid the complication of dealing with update conflicts from concurrent writes. This leaves developers with the job of choosing their desired read consistency. This choice requires a deep understanding of the semantics of their application, but need not alter the basic structure of the program.”