Module 9a - Consistency and Replication (part 1)

Question 1

Why do we need to replicate Data?

Answer 1

• Improves dependability. Data loss can be prevented in the event of a replica failing, since there are numerous copies
• Increases throughput. Replicas can be read/written to in parallel
• Decrease Latency. We can keep a data replica close to the client in different geographical regions

Question 2

What makes it difficult to design systems that deal with shared mutable states?

Answer 2

We have to account for both Concurrency and Failures

Question 3

In a replicated data store, each data object (ex: a row in a table) is _______ at multiple ______.

Answer 3

replicated

hosts

Question 4

A replica of an object may be ______ to a process meaning that it resides on the same host, or it may be _______

Answer 4

local

remote

Question 5

Why is replicating read-only data straightforward?

Answer 5

Because we don’t have to worry about keeping the data perfectly synchronized across hosts

Question 6

If a data store holds ______ state, then we can never keep _______ of this state perfectly _______

Answer 6

mutable
replicas
sychronized

Question 7

Why can’t mutable state/object replicas be perfectly synchronized all the time?

Answer 7

• Variations in processing speeds

- Network Delays

Question 8

What does a consistency model help us with? and how does it do it?

Answer 8

Make a sense of concurrent reading and updating data objects in a distributed system by describing the extent to which replicas are permitted to disagree on the state of data

Question 9

What makes it difficult to select a good consistency model?

Answer 9

Application requirements in general do not map neatly to a specific consistency model

Question 10

Under what condition is a data store sequentially consistent?

Answer 10

Whenever the result of any execution is the same as if the read/write operations by all processes on the data store were executed in some sequential order and the operations of each individual process appear in this sequence in the order specified by its program.

i.e: the order of execution is the same for sequential or concurrent

There are no contradictions in the order of operations in an execution.

Question 11

How do you prove if an execution is sequentially consistent in practice?

Answer 11

You must brute force every possible outcome of the execution order, and find a path which corresponds to a outcome in which the result is the same for reads after writes

Alternatively, you can construct a graph with all the order dependencies of all operations. If there are no cycles in this graph, then the execution is not sequentially consistent

Question 12

Under what condition is a data store causally consistent?

Answer 12

Whenever the “causally precedes” condition is met for all processes which read/write the data object in the execution

1. Op1 occurs before Op2 in the same process
2. Op2 reads a value written by Op1

Question 13

How do you prove that an execution is causally consistent in practice?

Answer 13

You must show that the total order (Ti) for each process (Pi) has these 3 properties:

1. Ti contains all the operations executed by Pi as well as the writes of any values read by Pi, and nothing else
2. Each read in Ti returns the value of the most recent write to the same object in Ti (i.e., order is legal)
3. If 2 operations occur in Ti and also occur in some other Tj, then they must be consistent in order

Question 14

______ consistency, _______, and ______ consistency are different ways to define the correct behaviour of operations on shared objects under concurrent access

Answer 14

Sequential
Linearizability
Causal

Question 15

The _______ property assumes that operations have well-defined start and finish events. which are ordered by a _____ _____

Answer 15

Linearizability
global
clock

Question 16

Under what condition is a data store / execution linearizable?

Answer 16

Whenever the result of the execution is the same as if the operations by all processes on the data store were executed in some sequential order that extends the “happens before” relation - with respect to a global clock:

In other words, if Op1 finishes before Op2 begins, then Op2 must precede Op1 in the sequential order.

Essentially, the order of execution must be serializable sequentially

extra note: linearizability is with context to a global clock whereas sequential consistency is not

Question 17

How do you prove that an execution is linearizable in practice?

Answer 17

You must find some total order of execution (T) that satisfy 3 properties:

1. T must only contain all the operations present in the execution from all processes
2. Each read in T returns the value of the most recent write to that same object in T (i.e. the order is legal)
3. Draw linearization points from start to finish within the intervals of time which are legal

Question 18

To prove that an execution is ________ consistent or ________, it suffices to exhibit a total order on the operations of that execution that satisfies certain properties. For ________ consistency, a total order is defined separately for each process.

Answer 18

sequentially
linearizable
causal

Question 19

To prove that an execution violates _______ consistency or _______, we draw a special graph and exhibit a cycle. For _______ consistency, a graph is defined for each process.

Answer 19

sequential
linearizability
causal

Question 20

Define eventual consistency

Answer 20

In a replicated system, if no updates take place for a long time, then all replicas will gradually become consistent.

If replicas are never consistent even after infinite time, then they do not have “eventual consistency”

Question 21

Eventual consistency is when in the ______ of new writes from ______, all servers will ______ hold the same data

Answer 21

absence
clients
eventually

Question 22

Give a negative example of eventual consistency

Answer 22

the following steps:

1. P1 executes Write(a, x)
2. P2 executes Write(b, x)
3. P3 executes Read(x), gives a
4. P4 executes Read(x), gives b
5. step 3 and step 4 repeat forever infinitely

Question 23

Session guarantees are used to augment eventual consistency. One property of a session guarantee is monotonic reads. What are monotonic reads?

Answer 23

Whenever a process reads the value of a data item key x, then any successive read operations on x by that process will always return that same value or a more recent value.

i.e. there is no stale data

Question 24

Session guarantees are used to augment eventual consistency. One property of a session guarantee is “read your own writes”. What is this property of “read your own writes”?

Answer 24

Whenever a process writes data item key x and then reads it, the read operation should return either the value written by the same process earlier, or a more recent value.

Question 25

______ consistency does not promise anything in the case when updates are applied continuously. Therefore, it is augmented with ______ ______ which ______ the behaviour of operations applied by a single process in a single session

Answer 25

eventual
session guarantees
restrict

Question 26

Is Eventual consistency a property of a strong system or a weak system?

Answer 26

Weak system. It does not guarantee that a resource in a system will be consistent across all replicas at a given period of time