6 - Consistency and Replication

Question 1

Why Replicate data?

Answer 1

System Performance- lowered latency
System Reliability

Question 2

Data Consistency

Answer 2

Corrrectness of Data according to a model

Question 3

Read-write conflict

Answer 3

Two read operations on the same data that read different values

Question 4

Write-Write Conflict

Answer 4

Two concurrent write operations on same data result in different versions

Question 5

Data centric consistency model

Answer 5

Specifies what is allowed and what the results of read/write ops are in presence of concurrency

Question 6

Data store model

Answer 6

Distributed storage collection
Read/Write
Read one, write all (datastores)
Consistency

Question 7

Tight Consistency

Answer 7

Synchronous Replication

Update every replica before next op

Question 8

Problems of Tight Consistency

Answer 8

Replicas must agree on next operation
Requires a lot of comms
Delay before next operation.

Question 9

Consistent Ordering

In terms of what processes work on

Answer 9

Processes work on different copies of the same data

Question 10

Sequentially Consistent

Answer 10

Any result is the same as if the operations of all processes were executed in some sequential order
All processes execute operations in the issued order

Question 11

Causally Consistent

Answer 11

causally related writes are exec in same order by all processes

all operations are executed by all processes in the order of issuing

Question 12

FIFO Consistent

Answer 12

individual processes operations are exec by all in the order they were issued

Question 13

Hierarchy of Consistencies

Answer 13

(Top Down)
Tight
Sequential
Causal
FIFO

Question 14

Eventual Consistency

Answer 14

Weak consistency model where no or rare parallel write accesses.
Updates are forwarded at some point.
All eventually consistent

Question 15

Critical Section

Answer 15

Processes must acquire lock to access critical sections

Question 16

Continuous Consistency

Answer 16

Divide data into consistency units
Non uniform consistency model

Question 17

Client Centric Consistency

Answer 17

Consistency guaranteed for the same client

Question 18

Types of continuous consistency constraints

Answer 18

Absolute/relative numerical division
Relative staleness of data
Order and number of updates

Question 19

Types of client centric consistency requirements

Answer 19

Monotonic reads/writes
Read Your Writes
Writes Follow Reads

Question 20

Monotonic Reads

Answer 20

If a process reads item x, any successive read on x by that process is always same or more recent value

Question 21

Monotonic Writes

Answer 21

A write by process on item x is completed before any further write on x by the same process

Question 22

Read Your Writes

Answer 22

Effect of write on item x will always be seen by success read operation on x by the same process

Question 23

Writes Follow Reads

Answer 23

Write on item x following a previous read by same process will take place on same or more recent value of x

Question 24

Lazy Updates

Answer 24

Server that has not been recently accessed can be updated before it replies (lazy update)

Question 25

Permanent Replicas

Answer 25

Initial set usually small

At one location or mirrored sites

Question 26

Server-initiated Replicas

Answer 26

Created ad-hoc

Either at one location or close to client

Question 27

Clustering

Answer 27

Partition space into cells and place servers at high demand

Question 28

Client initiated replicas

Answer 28

Caching of data. Usually on the same LAN.

Can have limited size and become stale

Question 29

Invalidation Protocol

Answer 29

Propagate notifications for updates

Question 30

Passive Replication

Answer 30

Transfer data from one copy to another

Question 31

Active Replication

Answer 31

Propagate update operation to other copies

Question 32

Primary-based protocol: Remote Write

Answer 32

Request forwarded to remote primary which distributes it

Question 33

Primary-based protocol: Local Write

Answer 33

Replica receiving request is made new primary

Question 34

Quorum based protocols

Answer 34

Only a certain number of replicas written to (write quorum)

Read a few (read quorum) replicas and return latest version

Question 35

What expression for n prevents read-write conflicts?

Answer 35

nw + nr > n

The addition of write and read quorums must be more than n or the updates may not be read

Question 36

What expression for n prevents write-write conflicts?

Answer 36

nw > n/2
The write quorum must exceed n or it is possible to have multiple writes with the same version number

Question 37

Quorum based protocols: Advantages over ROWA

Answer 37

ROWA requires all replicas to be available but Quorum allows max{n-nw,n-nr} unresponsive.

When single replicas fail or are expensive to update this may be more efficient

Question 38

ROWA

Answer 38

Read One Write All

Question 39

What consistency is probably sufficient for a stock market?

Answer 39

Causal.

Changes in stock value should be consistent but independent changes can be seen in different orders

Question 40

What client-centric consistency is most appropriate for a mobile user’s mailbox?

Answer 40

All of them.

The owner should always see the same mailbox.