Understanding the Sequential Consistency Model

We are on a journey to survey and understand commonly used consistency models in databases and distributed systems. In this blog, we will discuss the sequential consistency model.

Let’s remind ourselves of the problems consistency models solve. In a replicated data store over geographically dispersed nodes, concurrent writes and reads to the data happen at different times due to inherent challenges in a distributed system (such as delays due to propagation and queuing). Clients’ requests can interleave. There are many possible interleavings of requests with substantial implications on data mutations and their visibility to others. Consistency models enforce some rules on the possible ordering/visibility of requests/data for the applications so that they can interact with the data in the correct way. What constitutes correct for an application will change from one consistency model to another. For example, if a replicated store claims to provide linearizable writes and reads to its client, applications assume that the model abides by a certain contract. If the replicated store is not really linearizableConsistency models are quite subtle and consequently their implementations are prone to bugs., it can have a disastrous impact on the application and its clients. The following is a hierarchy of consistency models.

Note: Sequential consistency is a non-transactional, single-object consistency model.

Sequential consistency model

The sequential consistency model is a level below linearizability. In linearizability, we require a total ordering on all operations consistent with the real clock. In sequential consistency, we drop the demand for ordering consistency with the real-time clock. The important aspects of sequential consistency can be summarized as follows:

1. For the operations originating from the same processA process is an incarnation of a program., causal ordering should be followed. That is, the program order is maintained within each process. For example, if statement 1 is written before statement 2, those statements should execute in that order—statement 1 and then statement 2.

2. Across processes, any one of the possible total ordering suffices if it conforms to the local program orders. However, each process needs to see the same total order. The following illustration highlights an example. Process $P1$ and $P2$ execute some writes and reads (labeled from $a$ to $f$). Another observer process, $P3$, observes one possible and sequentially valid interleaving of the operations of $P1$ and $P2$. The first non-example has the issue that the program order for $P2$ is violated. The issue with the second non-example is that two observers see different total ordering. If events $d$ and $c$ were writes to $x$, we would see that this type of interleaving would leave $x$ in inconsistent states at different processes.

3. Real time plays no role in sequential consistency.

Let’s see sequential consistency in action with many examples.

Example: Not linearizable but sequentially consistent

In the following illustration, there are three clients and two data nodes. Initially, the value of $x$ is $0$ at both replica nodes ($M$ and $N$). Concurrently, client $A$ sends a write request to $M$ for $x = 1$, while client $C$ reads $x$ via node $M$. Client $A$ can get the write done at node $M$ first, after which client $C$ reads the new value. Client $B$ reads $x$ via node $N$ and reads $x$ as $0$ (in real time after client $C$ has gotten $x$ as $1$) because the write from node $M$ hasn’t reached node $N$ yet. It is an example that is not linearizable. This is because real-time constraints were violated, and client $B$ saw a stale value when client $C$ had seen a new value. However, this interleaving is sequentially consistent.

You might think that client $B$ read a $0$ while client $C$ read $x$ as $1$. How is that right? Well, if client $C$ had read a bit earlier, it would have gotten $x$ as $0$ and then $1$. Similarly, client $B$ will read $x$ as $1$ when the message reaches node $N$. So it’s the same order: $x = 0$ and then $x = 1$.

Let’s see another example in the context of four concurrently executing processes. We can consider them data nodes acting on some  clients’ requests. This interleaving is sequentially consistent and both $P3$ and $P4$ see the same ordering of events. $W(x) a$ means that a process is writing the value $a$ to a variable $x$. $R(x) a$ means that a process did a read operation on x and got a value $a$ back.

Example: Not sequentially consistent

Now let’s see an example that is not sequentially consistent using the following illustration. Note that process $P3$ reads as $x = b$ and then $x =a$ as a final value. Process $P4$ reads $x$ as $a$ and then $b$ as the final value. That means if no more updates are coming, $P3$ and $P4$ have divergent values of $x$. As explained earlier, each process should have seen the same total ordering to be sequentially consistent.

Implementation of sequential consistency

We saw in an earlier blog post that to implement linearizability, each data replica needs to coordinate both writes and reads among themselves. One way to do so was via consensus algorithms such as Paxos and Raft. Communicating every read and write to everyone requires sending many messages to each other before they converge on a value. We expect to have a lightweight implementation for sequential consistency because it is a relaxed model compared to linearizability.

Using a pub-sub system honoring FIFO order

In sequential consistency, processes/replicas don’t care to tell about their reads to the other processes. However, they need to disseminate their writes to everyone. One way to achieve this is to publish a write to a pub-sub system that will disseminate the writes to all the subscribers in the order they were entered at the queue. Note that writes from across processes can interleave in any order, but once they are in the queue, each process will get and process the writes in the queue order.

Note: You can review how a distributed queue and pub-sub system work.

Using a primary

If each data item has a single custodian such that each mutation happens only at that custodian/primary node, then that node will provide an order to the mutations and everyone will get the same order. This scheme will provide sequential consistency. The following slides show how writes and reads happen in such a primary-secondary system.

When to use sequential consistency (and when not to)

If we need to honor the real-time happening of the events, we should use linearizability. If not, then sequential consistency is a better option. When we are okay with any ordering for concurrent events, causal ordering might be a better choice (that is a topic of our next blog).

Note that under sequential consistency, the output of different processes will not match. For example, when an update value of a variable hasn’t reached some replica, it will print an old local value). For some use cases, such an outcome might not be desirable; therefore, linearizability might be a better choice there.

Sequential consistency is a single-object model. If we use it for more than one object, the cumulative result will not be sequentially consistent. To understand this point, consider the following example. Here, if we take $x$ and $y$ individually, they are sequentially consistent. However, taken together, they are not. $W(x) a$ means to write the value $a$ to $x$. $R(x) a$ means to read $x$, and the result of this read is $a$. The subscripts with $W$ or $R$ specify the respective process doing the operation. For example, $W_1 (x) a$ means that process one writes $a$ on $x$.

See that getting $R(x) a$ and $R(y) b$ is impossible in any legal re-ordering. The following table shows some of the $4!$ possible orderings to highlight why, in the above example, it is not possible to have a sequentially consistent ordering with more than one object ($x$ and $y$) involved. We need a different model with transactional support to work with more than one object at a time.

Availability when network partitions

If network partitioning happens such that the pub-sub system or custodian replica becomes unreachable for a few clients/secondary replicas, they can’t complete their writes. This means that sequential consistency-compliant nodes must seize their operations under certain network failures until the network heals.

Real-world examples providing sequential consistency

Many real-world applications claimMany popular systems have consistency bugs. A service called Jepsen has found and analyzed many of them. They can be found here: https://jepsen.io/analyses to provide sequential consistency. The following are a few examples:

Relational databases such as MySQL

Single-threaded replication of MySQL provides sequential consistency, while multi-threaded replication can be configured to provide sequential consistency.

Note: Most modern systems can be configured to choose one of the few consistency models they have implemented.

Git version control system with a common custodian

Git is a distributed version control system with no notion of any centralized entity in it. In many use cases, a git node is designated a custodian to provide a common reference point for everyone. All other git instances push their changes to that custodian node and fetch all the new stuff from everyone else via a pull from the custodian node. Because the custodian node is a single point to order all writes, such a git set up provides sequential consistency.

Distributed file systems: Hadoop Distributed File System (HDFS) and Google File System (GFS)

• HDFS allows only one write at a time. If there are concurrent writers to a file, a centralized name node will decide which writer will get to write the file. Therefore, such a scheme provides sequential consistency. HDFS borrows many traits from GFS.

• GFS allows concurrent writes to a file, and each file is divided into chunks of 64 MB. Each chunk has a primary node that decides the order to the writes. One might assume that GFS provides a sequential consistency model, though, in reality, it provides a custom, much more nuanced consistency model.

Conclusion

Sequential consistency is a relaxed model compared to linearizability. Sequential consistency does not care about the real times of the events while ordering them. As a consequence, implementing sequential consistency is easier than linearizability. For many real applications, sequential consistency is an adequate model.

Note: The topic of distributed systems has many subtle concepts such as sequential consistency. For an in-depth study of these concepts, we recommend Educative's following courses:

• Distributed Systems for Practitioners

• Grokking Modern System Design Interview for Engineers & Managers

• Grokking the Principles and Practices of Advanced System Design