Consistency Models and Replicache

Consistency Model

Consistency Model is a set of regulations on how much consistency will be provided in a distributed system. Among the previous posts, there is information about the trade-off between Latency and Consistency in PACELC theory, and it is about how much consistency will be provided according to this trade-off.

Replicache, discussed in the previous post, is also a type of distributed system. Replicache is said to follow Causal Consistency.

Source

Strict Consistency

Consistency that allows you to always read values ​​in chronological order. Any reads that occur after the value is written will always read that value. To satisfy this, two conditions are necessary. There is a global clock shared by all nodes and must be synchronized to it, and Write must be performed immediately.

w(x)a: Write the value a to x, r(x)a: Read the value a from x

When w(x)a occurs in node 1 at time t, and r(x) occurs in node 2 after t delta (0.0000000000000001s), node 2 must read the value a.

A global clock must exist to serialize the operation so that the operation is not performed at the same t time, and the write must be performed immediately so that the written value must be read at t delta time.

But this is actually impossible. Therefore, Strict Consistency exists as a theory.

If Strict Consistency is complied with in the situations below

The correct answer is as follows.

Sequential Consistency

The core keyword of Sequential Consistency is ‘Global Ordering’. All write/read operations must behave as if there is a single unified sequence. Also, the operations performed by each process (client) must be executed in that order.

In the case below, what values ​​can p3 and p4 read?

The following is the same as Strict Consistency, so Sequential Consistency is also satisfied.

You can find Global Ordering below, so Sequential Consistency is correct.

Global Ordering: w(x)a, r(x)a, w(x)b, r(x)b

However, in the case below, a is written before b, but is read later. In this case, Sequential Consistency is not satisfied.

Causal Consistency

Causal means cause-effect relationship. "Happens-before (→)" It is important to understand that it is a relationship.

A → B holds in the following cases.

1. A occurs before B in the same process (client)
2. After A, the message is sent and the party who received the message performs B.
3. If A → B and B → C, then A → C.

Causal Consistency is a rule in which this cause-effect relationship is visible in all nodes.

The case below is Causal Consistency.

The only “Happens-before” relationships that can be found here are w(x)a → r(x)a and w(x)b → r(x)b, which are satisfied by all processes. It is okay for P3 to read b first. This is because the two write operations are independent, so there is no cause-effect relationship of w(x)a → w(x)b.

The following does not establish Causal Consistency. The reason is that there is a cause-effect relationship of w(x)a → w(x)c, and c is read before a in P3.

Eventual Consistency

Eventual It is a rule that (eventually) becomes consistent. At some point, when there are no write operations and the network stabilizes, all nodes will eventually see the same value. It is a very finite convention.

Consistency in Replica

Replicache is said to follow Causal Consistency. This is a slightly stronger Causal Consistency, so let’s find out later.

The above is the detailed content of Consistency Models and Replicache. For more information, please follow other related articles on the PHP Chinese website!