Consistency models

综合技术 2017-11-06

Consistency models

In distributed systems, a consistency model is a contract between the system and the developer who uses it.

Why this post?

I have found somehow difficult to find an authoritative source which describes what is the contract that a certain consistency model defines with the programmer. Moreover, some resources seem to contradict each other.

The idea of this post is to document my findings around some of the most common consistency models that can be found in distributed systems which we interact with. When possible I'll add the resource where I found the definition.

Sequential consistency

The result of any execution is the same as if the operations of all 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.

Conceptually there is one global memory and a switch that connects an arbitrary processor to the memory at any time. Each processor issues memory operations in program order and the switch provides the global serialization among all the processors.

Therefore:Sequential consistency is not deterministic because multiple execution of the distributed program might lead to a different order of operations.

In the example above, four possible execution orders are possible no matter what is the actual order in which the operations were issued.

Important:no matter what the order of the operations are, it is guaranteed that is the same among all the processors. This also means that each process will observe the same history of operations. For example, in the first case b.1 will read the state which is the result of all the operations completed before b.1 : so b.1 is going to read a value for the account which is '150'.

Strict consistency

Also called Strong consistency or Linearizability .

Like sequential consistency, but the execution order of programs between processors must be the order in which those operations were issued.

As analogy, this is pretty much what we would get from a multi threaded program in which there is no cache between the cores and the main memory, and neither the compiler nor the CPU is allowed to reorder instructions.

Therefore:If each program in each processor is deterministic, then the distributed program is deterministic.

Casual consistency

Relax sequential consistency allowing also reordering of the operations in the same processors when they are not 'casually related'.

PRAM consistency

The write operations (and only the writes) of each processor appear in the order specified by the program.

Serializability

Unlike the models described above, serializability defines guarantees on group of operations (called transactions). It guaranties the execution of a set of transactions (usually read and writes operations) over multiple items is equivalent to some serial execution of the transactions.

Unlike linearizability, serializability does not impose a deterministic order, in this sense is similar to sequential consistency but for a group of operations.

Strict serializability, instead, guaranties the same constraint expressed by linearizability but for transactions: transactions must be executed in the order they were issued.

The definition looks a bit different from the ones above because it comes from database people, while sequential consistency, etc. come from distributed system people.

Read after write

The model guaranties immediate visibility of updates to an item to all the clients. The concept is similar to the one of Memory Barrier present in modern processors.

Note:Sometimes what is called Read after write in some systems, it's actually Read after create (for example in S3 ).

Read after create

The model guaranties immediate visibility of newly created data to all the clients. Updates to an existing object might not be immediately visible to all clients.

Conclusions

Those were my two cents about one of the many aspects around distributed systems. I'll keep adding more as I go to the list. Of course, any feedback would be greatly appreciated!

Additional resources

The Practical Developer

责编内容by:The Practical Developer (源链)。感谢您的支持!

您可能感兴趣的

Bypassing LF Entry Systems Its taken a lot of motivation to start writing this, and I hope its okay, I have...
DevCentral’s Featured Member for September – Rob C... is a Senior Trainer/Professional Services Consultant with Red Education Pty in...
5G网络切片及其需求 5G网络切片能够支持特定连接类型的通信服务,并以特定的方式处理该服务的控制和用户平面。网络切片是在一个网络基础设施上提供了逻辑上独立的网络,以满足多样化的服务需...
Add a Data Collection Device to your BIG-IQ Cluste... Gathering and analyzing data helps organizations make intelligent decisions ab...
为什么经济学实证研究方法中,结构实证相比于简化实证难度较高?... 前言 最近在写毕业论文,是一篇结构实证的文章,有机会给知友们介绍一下自己的研究。这篇文章从大三开始做,到现在已经有一年半了,毕业论文形成的这个...