9 Consistency

 

This chapter covers

  • Consistency
  • Linearizability
  • Eventual consistency
  • The CAP conjecture and theorem

In database systems, consistency has a tangible interpretation: A transaction transitions the database from one valid state to another valid state, where validity is defined by application-level constraints (ensuring, for example, that an account balance is always non-negative).

In distributed systems, components may fail and messages may be delayed, reordered, or lost; consistency can take on multiple interpretations. In this chapter, we’ll explore several consistency models and discuss common scenarios in which they arise.

9.1 Consistency models

To focus on consistency, in this chapter we reason about a distributed system as a collection of concurrent processes operating on a collection of objects. A process is a sequence of operations on objects. The object’s type defines the set of possible values and the set of possible operations to create and manipulate object instances. An operation is not instantaneous; instead, it is delineated by its invocation and completion. We model an operation on an object as an invocation and completion pair:

Operation = Invocation • Completion

Processes are strictly sequential. That is, each process issues a sequence of operations to objects, alternately issuing an invocation and waiting to receive the associated response (see figure 9.1).

9.1.1 Common consistency models

9.1.2 Virtues and limitations

9.2 Linearizability

9.2.1 Queue and stack

9.2.2 Formal definition of linearizability

9.3 Eventual consistency

9.3.1 The shopping cart

9.3.2 Variants of eventual consistency

9.3.3 Implementation

9.4 Consistency, availability, and partition tolerance

9.4.1 History

9.4.2 Conjecture vs. theorem

9.4.3 CAP theorem

Summary