Consistency in Distributed Systems

How consistency guarantees can be considered during understanding trade-offs?

Context and Background:

In earlier days of computational systems (as people call it Web 1.0), most of the computation or data processing used to happen on single machine. As world progressed to Web 2.0 (rise of social media, video sharing etc.), doing those stuff on single machine was not feasible anymore even with vertical scaling of that machine (as vertical scaling has it’s limit and after some point of diminishing returns, it’s not really an option). In comes horizontal scaling, where multiple machines can work in synchronization to get the work done. To achieve the synchronization, the co-ordination and data consistency turned out to be major factors to consider as machines needed to communicate with each other over (not so reliable) networks.

To understand topic of data consistency, let’s consider example of a distributed database which has one master/leader node (which takes write requests) and 2 slave/follower/replica nodes. The reason of having slave nodes is to delegate read request based workload (and to reduce read latencies for users situated in certain region). Now users can only write on master node, and then master node will asynchronously replicate those changes into replica nodes with help of something called as replication log (the logfile which contains changes i.e. writes made on master) over network. During this process there’s some replication lag that happens due to unreliable networks.

Now you might’ve noticed, we have consistency problem here. There is no way that writes made master are immediately available at replica nodes. To achieve more strict form of consistency, some trade-offs need to be considered. In this article, I’ve tried to explain different consistency models. For more depth information around this topic.

Eventual Consistency:

As name suggests, the replicated data will be eventually consistent, not strongly consistent. It is the default setting of many asynchronously replicated systems. It’s fast and simple and highly available (important factor to consider while understanding trade-offs), at the expense of consistency and potential data loss due to the last-write-win conflict resolution strategy.

The term ‘eventual’ is highly qualitative and doesn’t give much insight into what’s time period required to get whole system consistent. Time required to reach consistency is usually calculated as time required for all the replicas to receive and implement (depending upon type of replication log sent out. If it’s query based and not result based replica needs to implement the queries) the replication log.

Causal Consistency:

This model of consistency is based on having causally related operations MUST appear in the way they should. For example, imagine having conversation with your friend over WhatsApp group chat. You asked “How are you, mate?”, and he replies “Doing great”. For a third person reading the chat, the ordering of these operations must be same or constant. Question must come before answer and vise versa cannot happen under causal consistency model.

This is stronger consistency model than eventual consistency and weaker than sequential as we are only concerned about related events, which are question and answer in above example.

Sequential Consistency:

Sequential consistency implies total ordering of operations on every node. It is formally defined as “the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program”.

This model is stronger than causally consistent model as we are dealing with total ordering of operations and not only ordering of related operations. Using this model, we can get idea about ordering of operations to identify the latest state of the system which will be consistent by nature of sequential consistency.

Linearizable Consistency:

This is strictest form of atomic consistency. i.e. consistency while dealing with single object. Informally it can be thought as sequential consistency PLUS guarantee of real time consistency. If operation A finishes before operation B, then resulting state of system after implementation of operation A must be visible to operation B in real time.

This is stronger than sequential consistency because additional real time constraint.

Serializable Consistency:

This model provides the guarantee of linearizable consistency plus total order multi-object consistency in real time. Multi-object implies that this is transactional (you might’ve heard this term in your relational database course). Formally this is defined as “A history is serializable if it is equivalent to one in which transactions appear to execute sequentially, i.e., without interleaving. A (partial) precedence order can be defined on non-overlapping pairs of transactions in the obvious way. A history is strictly serializable if the transactions’ order in the sequential history is compatible with their precedence order.”

This is the strongest consistency model which provides transactional multi-object consistency guarantee in real time.