Replication and Data Consistency

Question 1

What is the read/write coherence?

Answer 1

A READ of a variable must always be the value of the last WRITE of the same variable.

Question 2

What is transparency in replication and consistency?

Answer 2

Users should only think one copy of a file exists.

It should look like one system.

Question 3

What is used to achieve consistency?

Answer 3

Consistency models

Question 4

What is a consistency model?

Answer 4

Contract between processes and data stores.

If processes obey certain rules, data store will work correctly.

Question 5

What is a strong Consistency Model?

Answer 5

Model that requires global ordering of updates.
When updates are commited, replicates need to reach agreement on global ordering.
Different models depending on guarentees of total ordering.

Question 6

What is a weak Consistency Model?

Answer 6

Model that doesn’t require global ordering, more relaxed guarentees on consistency.

Question 7

What is passive/active replication?

Answer 7

Passive: Client communicate with single replica, the primary, and one or more replicas act as backup.
Active: Client communicates with a group of k replicas.

Question 8

What is the passive replication process? (4)

Answer 8

Client sends request to primary.
If primary is active it responds, otherwise Leader Election chooses new primary.
Any changes that the clients makes to the primary is shared with the backups.
Once all backups are updated, the primary responds to the client.

Question 9

What is the active replication process? (3)

Answer 9

Client uses local copy of data.
Any changes made are propagated across the replicas using TO multicast.
Depending on Consistency Model, a read request may be forwarded to other servers before the response is generated.

Question 10

What is strict consistency?

Answer 10

Requires all processes to receive responses consistent with the real value, regardless of the number of replicas.

Question 11

What is linearisability?

Answer 11

Traces are interleaved to form a single total order (respecting local ordering)

Question 12

What are the 2 conditions of linearisability?

Answer 12

Consistent

If t1 and t2 belong to Pi, and t1 < t2, then t1 < t2 in the combined order.

Question 13

What is sequential consistency?

Answer 13

Read returns local copy immediately.
Write trigger TO Multicast.
Local copies on severs updated.
All replicas see the writes in the same order.

Question 14

What is eventual consistency?

Answer 14

All replicas will eventually be consistent.

Good when inconsistency can be tolerated.

Question 15

What guarentee is required for eventual consistency?

Answer 15

All updates are guarenteed to reach all replicas.

Update locally, and propagate in the background

Question 16

How does eventual consistency deal with conflict?

Answer 16

Delegate to application.
Roll back to previous version.
Uss consensus to determine most recent value

Question 17

What are the advantages and disadvantages of eventual consistency?

Answer 17

Advantages: R/W fast (consensus moved to background).
Can make progress even with network partition.

Disadvantages: Weak consistency
Still need to use consensus for conflicts.

Question 18

What is a quorum?

Answer 18

A partial set of replicas intended to improve availability.

Question 19

What are the 2 required quorums in Quorum-based protocols?

Answer 19

A READ quorum, and a WRITE quorum.

Question 20

What is the requirement on the READ and WRITE quorums in a QBP?

Answer 20

They must be intersecting.

Question 21

What is the goal of QBPs?

Answer 21

For correctness, it is sufficient to read from a READ quorum and write to a WRITE quorum.

Question 22

How can a file be read in a QBP?

Answer 22

The client needs to assemble a READ quorum of R server replicas.

Question 23

How can a file be written in a QBP?

Answer 23

The client needs to assemble a WRITE quorum of W server replicas.

Question 24

What are R and W?

Answer 24

R = minimum number of nodes that must participate in a read operation.
W = minimum number of nodes that must participate in a write operation.

Question 25

What are the ffg constraints of R and W?

Answer 25

R + W > N (prevents read/write conflicts)

W > N/2 (prevents write/write conflicts)

Question 26

How can we introduce bias of availability?

Answer 26

By variying R and W.

Question 27

What is the extreme availability scheme?

Answer 27

W = N, R = 1 (used when writes are very infrequent)