Memory Models of Distributed Systems

Hello, my name is Dmitriy Karlovskiy and I am.. I try to tell complicated things in simple language, and simple things in aesopian language. And it often turns out that in the process of simplification and structuring, skeletons of ancient dinosaurs are found in the most prominent place, sprinkled with murky formulations so that for many years no one notices them. Well, if you want to finally understand the levels of transaction isolation and guarantees of the order of operations, let's dig together. This classification is a consistent reinterpretation of the well-known classification from Jepsen in a more concise and clear form. How to read a chart: It presents memory models and phenomena that they do not allow. All models are divided into 2 orthogonal groups: one determines the order of operations, and the other determines the level of transaction isolation. All models are classified by availability level when dividing the network in a distributed system: Total Available — guarantees are provided on any node. Sticky Available — guarantees are provided if you do not switch between nodes. Unavailable — some or all nodes will not be able to provide guarantees. Formal timeline representation Writing version 5 data to the X state: 5=>X Writing the value of state X to state Y: X=>Y Writing a new value to state X based on its version 5: 5+=>X Reading the state of X with receiving version 6 data: X=>6 History of operations where Y came after X: X | Y Histories of operations X and Y of two agents occurring in parallel: X Y Histories of operations X and Y of two agents occurring sequentially: X | | Y Transaction history of X and Y within a single successful transaction: [ X | Y ] Transaction history of X and Y within a single cancelled transaction: { X | Y } General definitions Agent is an active actor executing application logic. Node is a passive entity providing access to data. In a client-server architecture, a node is a DBMS instance, and an agent is its client. In a peer-to-peer architecture, each agent is a node of the network. Guarantees of the order of operations Operation is an atomic action that cannot be broken down into a sequence of smaller actions. Monotonic Monotony is a guarantee that time moves only forward, without any state reversals. The following phenomena are not allowed: Chaotic Read Chaotic reading is the phenomenon of traveling back in time, when another reading of the same state returns an older value than it was read earlier. A=>1 | A=>0 Chaotic Write Chaotic writing is the phenomenon of rearranging records of different states when the order of their appearance does not coincide with the order of their execution. 1=>A | 1=>B | | B=>1 | A=>0 | A=>1 Causal Causality is a guarantee that the effects observed by operations follow strictly after the operations that caused them. The following phenomena are not allowed, apart from those that prohibit monotony: Invisible Write Invisible writing is the phenomenon of an unobservable change made by the same agent on the same node. 1=>A | A=>0 Causeless Write Causeless writing is the phenomenon of an unobservable change on which another change is based. A=>1 | A=>B | | B=>1 | A=>0 Since coordination with other nodes is not required to maintain causality, these and weaker guarantees are preserved even when the network is divided, but only if the agent does not switch between nodes. Sequential Sequencing is a guarantee of a uniform order of all changes, observed by all agents. The following phenomena are not allowed apart from those prohibited by causality: Variable Order Variable ordering is the phenomenon of observing changes in different order by different agents. A=>1 | B=>0 | B=>1 B=>1 | A=>0 | A=>1 Since coordination between nodes is required to ensure uniform order, these and stronger guarantees cannot be provided when the network is divided. Linearizable Linearizability is a guarantee that the order in which changes are observed corresponds to the order in which they are made in real time. The following phenomena are not allowed, apart from those that forbid sequencing: Stale Read Stae reading is the phenomenon of reading an outdated version of a value when reading after making a more recent change by another agent. 1=>A | 2=>A | | A=>1 Guarantees of transaction isolation Transaction is a sequential group of operations with a common lifecycle. Either all or none of the operations from the transaction are applied. Read Uncommitted The visibility of the uncommitted is a guarantee of the atomicity of transaction writes. Write operations of different transactions do not mix with each other, but already made changes to sepatate states ar

Apr 23, 2025 - 09:30

Hello, my name is Dmitriy Karlovskiy and I am.. I try to tell complicated things in simple language, and simple things in aesopian language. And it often turns out that in the process of simplification and structuring, skeletons of ancient dinosaurs are found in the most prominent place, sprinkled with murky formulations so that for many years no one notices them. Well, if you want to finally understand the levels of transaction isolation and guarantees of the order of operations, let's dig together.

This classification is a consistent reinterpretation of the well-known classification from Jepsen in a more concise and clear form.

How to read a chart:

It presents memory models and phenomena that they do not allow.
All models are divided into 2 orthogonal groups: one determines the order of operations, and the other determines the level of transaction isolation.
All models are classified by availability level when dividing the network in a distributed system:
- Total Available — guarantees are provided on any node.
- Sticky Available — guarantees are provided if you do not switch between nodes.
- Unavailable — some or all nodes will not be able to provide guarantees.

Formal timeline representation

Writing version 5 data to the X state:

5=>X

Writing the value of state X to state Y:

X=>Y

Writing a new value to state X based on its version 5:

5+=>X

Reading the state of X with receiving version 6 data:

X=>6

History of operations where Y came after X:

X | Y

Histories of operations X and Y of two agents occurring in parallel:

X
Y

Histories of operations X and Y of two agents occurring sequentially:

X |
  | Y

Transaction history of X and Y within a single successful transaction:

[ X | Y ]

Transaction history of X and Y within a single cancelled transaction:

{ X | Y }

General definitions

Agent is an active actor executing application logic.
Node is a passive entity providing access to data.

In a client-server architecture, a node is a DBMS instance, and an agent is its client. In a peer-to-peer architecture, each agent is a node of the network.

Guarantees of the order of operations

Operation is an atomic action that cannot be broken down into a sequence of smaller actions.

Monotonic

Monotony is a guarantee that time moves only forward, without any state reversals.

The following phenomena are not allowed:

Chaotic Read

Chaotic reading is the phenomenon of traveling back in time, when another reading of the same state returns an older value than it was read earlier.

A=>1 | A=>0

Chaotic Write

Chaotic writing is the phenomenon of rearranging records of different states when the order of their appearance does not coincide with the order of their execution.

1=>A | 1=>B |
            | B=>1 | A=>0 | A=>1

Causal

Causality is a guarantee that the effects observed by operations follow strictly after the operations that caused them.

The following phenomena are not allowed, apart from those that prohibit monotony:

Invisible Write

Invisible writing is the phenomenon of an unobservable change made by the same agent on the same node.

1=>A | A=>0

Causeless Write

Causeless writing is the phenomenon of an unobservable change on which another change is based.

A=>1 | A=>B |
            | B=>1 | A=>0

Since coordination with other nodes is not required to maintain causality, these and weaker guarantees are preserved even when the network is divided, but only if the agent does not switch between nodes.

Sequential

Sequencing is a guarantee of a uniform order of all changes, observed by all agents.

The following phenomena are not allowed apart from those prohibited by causality:

Variable Order

Variable ordering is the phenomenon of observing changes in different order by different agents.

A=>1 | B=>0 | B=>1
B=>1 | A=>0 | A=>1

Since coordination between nodes is required to ensure uniform order, these and stronger guarantees cannot be provided when the network is divided.

Linearizable

Linearizability is a guarantee that the order in which changes are observed corresponds to the order in which they are made in real time.

The following phenomena are not allowed, apart from those that forbid sequencing:

Stale Read

Stae reading is the phenomenon of reading an outdated version of a value when reading after making a more recent change by another agent.

1=>A | 2=>A |
            | A=>1

Guarantees of transaction isolation

Transaction is a sequential group of operations with a common lifecycle. Either all or none of the operations from the transaction are applied.

Read Uncommitted

The visibility of the uncommitted is a guarantee of the atomicity of transaction writes. Write operations of different transactions do not mix with each other, but already made changes to sepatate states are visible between transactions.

The following phenomena are not allowed:

Dirty Write

Dirty write is the phenomenon of mashing a state change by another transaction before the current one is completed, which leads to a partial loss of changes.

[ 1=>A |      | A=>2 ]
       [ 2=>A ]

Read Committed

Visibility of commited is a guarantee of invisibility of changes in running transactions.

The following phenomena are not allowed, apart from those that prohibit read uncommited:

Dirty Read

Dirty reading is the phenomenon of visibility of a change made by another transaction before it is completed. Thus, rolling back a transaction may not roll back the side effects it provoked.

{ 1=>A |      } | [ A=>0 ]
       [ A=>1 ]

Repeatable Read

Repeatable reading is a guarantee of the immutability of visible states within a transaction that did not change these states itself.

The following phenomena are not allowed, apart from those that prohibit read commited:

Phantom / Fuzzy Read

Fuzzy reading is the phenomenon of obtaining different values when reading the same state sequentially.
Phantom reading is a special case of fuzzy reading, concerning the reading of an index by one transaction, while another changes the indexed records themselves.

[ A=>0 |      | A=>1 ]
       [ 1=>A ]

The SQL standard recklessly does not exclude the phenomenon of phantom reading from repeatable reading, which is incorrect, since phantom reading is a manifestation of fuzzy reading of a whole table or an index based on it.

...

So as to maintain repeatability coordination with other nodes is not required, then these and weaker guarantees can be achieved even when the network is divided. A degenerate case is isolated client-side transactions.

Serializable

Serializability — guarantees the visibility of transactions on any node, equivalent to executing them sequentially on one node without mixing any operations between transactions.

The following phenomena are not allowed in addition to those prohibited by repeatable reading:

Lost Update

Lost update is the phenomenon of mashing the changes of one transaction with the changes of another, which does not take into account the changes of the first one.

[ A=>0 | 0+=>A ]       | [ A=>1 ]
[ A=>0 |       | 0+=>A ]

With such a guarantee, transactions can themselves be considered as atomic operations that satisfy the guarantees of sequential, that is, having a global order, which means that these and stronger guarantees cannot be provided when the network is divided.

Strict Serializable

Strict serializability — guarantees the visibility of serializable transactions in accordance with their execution in real time, that is, transactions behave like linearizable atomic operations.

High availability

To ensure high availability, we have to abandon the total sequence of transactions. This means that you need to be prepared for some phenomena.

Some of them can be leveled by using CRDT structures, which give the same result even when swapping operations. But even they cannot protect against stale reading. So you still have to choose between availability and linearizability — this dilemma is also known as the CAP theorem.

If we allow agent switching between nodes, then although it is possible to provide some level of transaction isolation, temporary anomalies are still inevitable, which negates all the benefits of transactions. Therefore, one or another form of binding agent to node and refusal of availability in case of failure of this node seems reasonable.

A social phenomenon

Help to improve this classification and support my researches.